課程名稱︰密碼學
課程性質︰選修
課程教師︰雷欽隆
開課學院：電資學院
開課系所︰電機所
考試日期（年月日）︰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.