課程名稱︰密碼學導論 (Introduction to Cryptography)
課程性質︰數學系選修
課程教師︰陳君明
開課學院：理學院
開課系所︰數學系
考試日期（年月日）︰2018 年 6 月 26 日
考試時限（分鐘）：15:30 ~ 18:20 (不延長)
注意事項：考試時會發一張標準期考作答卷當作計算紙，答案則是填在題本的最後一頁。
試題 :
Cryptography Final Exam 2018/06/26
Part I (3 points each)
____________
The right figure shows the graph of an elliptic curve over R. | |
The line BC is tangent to the curve at B. Both AC and BD | 此 |
are vertical lines. The point at infinity is denoted as E. | 題 |
On the elliptic curve group denoted as an additive group, | 圖 |
indicate the specified point on the figure in each of the | 請 |
following three questions. | 看 |
| 下方 |
1. Which point is 2B? | 連結 |
|____________|
2. Which point is B + C?
3. Which point is C - 2D?
4. Which is NOT a generator of a cyclic multiplicative group of order 11 in
(Z_89)*?
A. 3^((89–1)/11) B. 6^((89–1)/11) C. 9^((89–1)/11) D.12^((89–1)/11)
E. None of the above
5. How many square roots of 1 in Z_1155? That is, the number of solutions to
x^2 ≡ 1 (mod 1155).
A. 8 B. 12 C. 16 D. 20 E. None of the above
6. Which multiplicative group is NOT of order 12?
A. (Z_13)* B. (Z_21)* C. (Z_28)* D. (Z_36)* E. None of the above
7. Methods for key establishment are classified into key transport and key
agreement. Which is often used for key transport?
A. RSA B. DSA C. ECDH D. ECDSA E. None of the above
8. For the protection of Top Secret information of USA government, crypto-
graphic primitives of 192-bit security are required in NSA Suite B. What
is the signature size (in bits) of the corresponding ECDSA?
A. 96 B. 256 C. 384 D. 512 E. None of the above
9. Assume a company with 100 employees. A new security policy demands encrypted
message exchange with a symmetric cipher. How many keys are required, if a
secret communication is ensured for every possible pair of communicating
parties?
A. 2450 B. 4950 C. 5000 D. 9900 E. None of the above
10. Which statement about hash functions or MACs (Message Authentication Codes)
is FALSE?
A. A secret key is not required as input data for a MAC
B. Serious security weaknesses have been found in SHA-1
C. Both secret prefix MAC and secret suffix MAC are insecure
D. SHA-2 has four possible output lengths: 224, 256, 384, and 512 bits
E. None of the above
Part II (3 points each)
* [Chinese Remainder Theorem] (The same moduli as the ones in 孫子算經)
x ≡ ___ (mod ___) is the solution to the system of congruences
x ≡ 2 (mod 3), x ≡ 1 (mod 5), x ≡ 2 (mod 7)
* Consider the Diffie-Hellman key exchange scheme on Z_19 with the generator
g = 2. If Alice sent Bob 16 and the agreed key was 17, what did Bob send
Alice? There are two possibilities: ___ and ___.
* An RSA signature scheme is operated with the public modulus n = 133 = 7 * 19.
* Φ(133) = ___, the value of Euler Φ-function for n.
* If the public exponent for verification is e = 5, the corresponding private
key for signing is d = ___.
* Signing the message m = 3, the user obtains its digital signature s = ___.
* If a message m is divided into t blocks m1, m2, …, mt with appropriate padd-
ing, then the CBC-MAC with a cipher e and a key k is derived by the process:
* I1 = m1 and O1 = ek(I1)
* Ii = mi ⊕ ___ and Oi = ___ for i = 2, 3, …, t
* The output MAC value is Ot
* Alice and Bob will agree a key by ECDH (Elliptic _______________
Curve Diffie-Hellman key exchange) on the group | |
defined by y^2 = x^3 + 5x + 1 over GF_23. G = (0, 1) is | 此 |
taken as the base point. Alice chooses a = 27 and | 題 |
sends A = 27G = (22, 15) to Bob. | 圖 |
* The order of the elliptic curve group is ___. | 請 |
* A + 2018 G = ___. | 看 |
* Bob chooses b = 3 and sends B = ___ to Alice. | 下方 |
* The agreed key comes from the x-coordinate of | 連結 |
the point nG = ___, where n = ___. |_______________|
* All modern factoring algorithms, such as Number Field Sieve and Quadratic
Sieve, were inspired by Fermat's idea: Find x and y satisfying x^2 ≡ y^2
(mod N) to factor N. Suppose N = 43739 = p * q and the following relations
are obtained by one of the Sieve methods:
296^2 ≡ 138 = 2 * 3 * 23 (mod N)
302^2 ≡3726 = 2 * 3^4 * 23 (mod N)
305^2 ≡5547 = 3 * 43^2 (mod N)
363^2 ≡ 552 = 2^3 * 3 * 23 (mod N)
373^2 ≡7912 = 2^3 * 23 * 43 (mod N)
* To factor N, we compute gcd(a, N) which is likely to be a proper factor of
N, where a = ___ is derived from the above relations.
* Assume the prime factors p < q, then p = ___ and q = ___.
* Miller-Rabin primality test is extensively used for prime generations.
* The test is based on the following fact:
If r≠±1 (mod n) but r^2 ≡ 1 (mod n), then n must be a composite.
* Run the Miller-Rabin test to determine the primality of n = 2018369:
Write 2018369 – 1 = 2018368 in some specific form
Choose a ∈ {2, …, n–2} randomly
Compute b = ___ (mod n)
If (b≠1 and b≠(n-1))
i = 1
While (i < ___ and b≠(n-1))
b = ___ (mod n)
If (b = 1) Output (Composite, a)
i = i + 1
If (b≠(n-1)) Output (Composite, a)
Output “Probable Prime”
* Actually 2018369 is a prime number.
Part III (Write down all details of your work)
31. (5 points)
The elliptic curves P-256 and P-384 over prime fields standardized in FIPS
186 by NIST are required by NSA Suite B for ECDH (key agreements) and ECDSA
(digital signatures). The elliptic curve secp256k1 is adopted by major
cryptocurrencies such as Bitcoin and Ethereum. To make ECC (Elliptic Curve
Cryptography) secure, the underlying elliptic curve must be selected very
carefully.
(a) Show that x^3 + ax + b has no repeated roots if and only if
4a^3 + 27b^2 ≠ 0.
(b) Why the equations y^2 = x^3 + ax + b with 4a^3 + 27b^2 = 0 are avoided?
32. (5 points)
In 2014, people came to know about the NSA's ability to break Trillions of
encrypted connections by exploiting common implementations of the Diffie-
Hellman key exchange algorithm – thanks to classified documents leaked by
Edward Snowden. Here we consider a toy example of solving discrete logari-
thm by Index Calculus.
* Let the prime p = 18443. Note that g = 37 is a primitive root modulo
18443. That is, the order of 37, o(37) = 18442 in the multiplicative
group (Z_18443)*.
* Consider the "factor base" {2, 3, 5}. Denote the discrete logarithm
x_2 = log_g(2) satisfying g^(x_2) = 2 (mod 18443). Denote x_3 = log_g(3)
and x_5 = log_g(5) similarly.
* Take random powers of g = 37 modulo 18443 and pick out the ones that have
prime factors 2, 3, or 5 only. A couple of hundred attempts gives four
equations:
g^12708 ≡ 2^3 * 3^4 * 5 (mod 18443), g^11311 ≡ 2^3 * 5^2 (mod 18443),
g^15400 ≡ 2^3 * 3^3 * 5 (mod 18443), g^2731 ≡ 2^3 * 3 * 5^4 (mod 18443).
(For 1024-bit modulus in common implementations, such equations might be
obtained by the Number Filed Sieve with enormous amout of computation.
Dedicated hardware chips were likely produced by NSA to make it possible.)
* Then the four congruences become the following four linear relations:
12709 = 3*x_2 + 4*x_3 + x_5 (mod 18442),
11311 = 3*x_2 + 2*x_5 (mod 18442),
15400 = 3*x_2 + 3*x_3 + x_5 (mod 18442),
2731 = 3*x_2 + x_3 + 4*x_5 (mod 18442).
* Note that the formulas are congruences modulo p - 1 = 18442 = 2 * 9221
where 9221 is prime. So we need to solve the system of linear equations
modulo 2 and modulo 9221. Accomplished by Gaussian elimination, the
solutions are
(x_2, x_3, x_5) ≡ (1, 0, 1) (mod 2),
(x_2, x_3, x_5) ≡ (5733, 6529, 6277) (mod 9221)
* Combining these solutions by Chinese Remainder Theorem yields
(x_2, x_3, x_5) ≡ (5733, 15750, 6277) (mod 18442)
The solutions are checked by computing
37^5733≡2 (mod 18443), 37^15750≡3 (mod 18443), 37^6277≡5 (mod 18443)
These results are stored in a logarithm data base to break a lot of
Diffie-Hellman key exchanges using the same domain parameters.
* It is observed that Alice sends 211 to Bob. To find the agreed key betw-
een Alice and Bob, it is sufficient to solve 37^x ≡ 211 (mod 18443)
* Compute the value of 211 * 37^(-k) (mod 18443) for random values of k
until a value with prime factors 2, 3, or 5 only is found. After a few
attempts, a desired number appears: 211 * 37^(-9549) ≡ 2^5 * 3^2 * 5^2
(mod 18443)
* Finally, evaluate x = log_g(211) by setting up an equation and solving
for x with 1 <= x <= 18442. [You might need 28665 + 31500 + 12554 ≡
-1049 (mod 18442) to simplify computation.]