课程名称︰密码学
课程性质︰选修
课程教师︰雷钦隆
开课学院：电资学院
开课系所︰电机所
考试日期（年月日）︰2021/04/22
考试时限（分钟）：170
试题 :
密码学期中考 (Cryptography)
04/22/2021
1. (5 points) If a function f: A→B satisfies the following properties (a) and
(b).
(a) The function is polynomial time computable, and
(b) For most (say 99.999%) of elements y∈B, computing f^-1(y) needs
at least exponential time.
Explain why f is not a good candidate for a one-way function.
2. (10 points) Let A denote the set of collision resistant functions, B denote
the set of preimage resistant functions, and C denote the set of second
preimage resistant functions. Draw a figure to show the relationship among
the three sets A, B, and C.
3. (5 points) Why are the non-zero integers not a group under multiplication?
4. (5 points) What is the number of elements in Z_2021 ^* ?
(Hint: 2021 is not a prime)
5. (5 points) Compute 31^2021 mod 13.
6. (5 points) In Z_19 ^*, g=10 is a generator. What is the discrete logarithm
of 9 to the base 10?
7. (5 points) What are the generators of Z_19 ^* ?
8. (5 points) What are the square roots of 4 in Z_21 ^* ?
9. (5 points) What property must a cipher have for it to be called information
theoretically secure?
10. (5 points) If random variable X takes at most m values and random variable
Y takes at most n values, what are the maximum and minimum values possible
for H(X,Y)?.\
11. (10 points) Let P, K, C be the set of possible messages, keys and
ciphertexts with associated random variables P, K, C.
Explain why H(P|K,C) = 0 and H(C|P,K) = 0,
Then, prove that H(K) + H(P) = H(K,C).
12. (5 points) Consider a block cipher based on Feistel structure.
The operations of an encryption round are shown in the following figure:
https://i.imgur.com/3rnrhIg.png
Describe the operations in a decryption round.
13. Consider the ECB, CBC, CFB, OFB, and Counter modes:
(a) (2 points) Which mode is most suitable for high-speed network encryption?
(b) (2 points) Which mode is most suitable for noisy channel?
(c) (2 points) Which mode is usually used for short message encryption?
(d) (3 points) Which of them allow random access to encrypted data blocks?
(e) (3 points) Which of them allow precomputation?
(f) (4 points) Which of them will result in self-synchronizing cipher(s)?
(g) (4 points) Which of them will not propagate errors?
14. (5 points) Explain why triple-DES uses C = E_K3[D_K2[E_K1[P]]] instead of
C = E_K3[E_K2[E_K1[P]]] to compute the ciphertext C?
15. (10 points) In the “Mix Columns” operations of AES, the resulting column
of a column
┌ ┐ ┌ ┐ ┌ ┐┌ ┐
│a│ │a'│ │ 2 3 1 1 ││a│
│b│ after the “Mix Columns”operation is │b'│ = │ 1 2 3 1 ││b│,.
│c│ │c'│ │ 1 1 2 3 ││c│
│d│ │d'│ │ 3 1 1 2 ││d│
└ ┘ └ ┘ └ ┘└ ┘
For example, a' = 2a⊕3b⊕c⊕d, each of the 4 terms (2a,3b,1c,1d) is
effectively a multiplication in GF(2^8) using prime poly.
m(x) = x^8 + x^4 + x^3 + x + 1
If a=(2B)_16, b=(D4)_16, c=(DE)_16, d=(AD)_16. What is the value of b'?
Note that (2B)_16 denote the hexadecimal byte 2B.
16. (5 points) Let h be a hash function with block size of 512 bits.
We can use h to construct a MAC function as follows:
HMAC_k(m) (m) = h(k||p_1||h(k||p_2||m)), with p_1, p_2 are fixed strings
used to pad k to full block. Let m be a message of 62.5K Bytes. Assume it
takes 1 ms to compute h(m). Roughly, how much time does it take to compute
HMAC_k(m)?
17. (10 points) Describe the possible padding schemes (including the ciphertext
stealing method) for block ciphers.