課程名稱︰橢圓曲線密碼學 課程性質︰選修 課程教師︰陳君明 開課學院：理學院 開課系所︰數學系 考試日期（年月日）︰2015/12/29 考試時限（分鐘）：120分鐘 試題 : 1. Sketch the following two elliptic curves over R (the field of real numbers). Label all the x-intercepts and y-intercepts. (a) Y^2 = X^3 - 4*X (b) Y^2 = X^3 + 8 2. Let E:Y^2 = X^3 + AX + B be an elliptic curve over a prime field F_p, and let P_1 = (x_1, y_1) and P_2 = (x_2, y_2) be points on E. Define λ by λ = (y_2 - y_1) / (x_2 - x_1) for P1 ≠ P2, and λ = g(x1, y1) for P1 = P2. Let x_3 = h(x_1, x_2, λ) and y_3 = λ(x_1 - x_3) - y_1, then P1 + P2 = (x_3, y_3). Derive the formula of g(x1, y1) and h(x_1, x_2, λ). 3. Given a point P on an elliptic curve E. To compute 477P on E, note that 477 = 2^8 + 2^7 + 2^6 + 2^4 + 2^3 + 2^2 + 2^0 = (111011101) in binary expansion. (a) Compute 477P with standard double-and-add algorithm. How many doublings and additions are required respectively? (b) Write 477 in the non-adjacent form (NAF), i.e., a unique signed-digit ternary expansion that every 1 or -1 has to be adjacent to two zeros. (c) Compute 477P with 477 in NAF. How many doublings and additions are required? 4. Given a base point P and another point Q on an elliptic curve E. (a) What is the Elliptic Curve Discrete Logarithm Problem (ECDLP) ? (b) Describe the Pollard ρ algorithm to slove ECDLP. 5. The Menezes-Vanstone variant of the elliptic ElGamal encryption (MV-ElGamal) improves message expansion while avoiding the difficulty of directly attaching plaintext to points on a curve. ┌───────────────────────────────────┐ │Public Parameter Creation │ ├───────────────────────────────────┤ │A trusted party chooses and publishes a (large) prime p, and elliptic │ │curve E over F_p, and a point P in E(F_p). │ ├─────────────────┬─────────────────┤ │ Alice │ Bob │ ├─────────────────┴─────────────────┤ │ Key Creation │ ├─────────────────┬─────────────────┤ │Chooses a secret multiplier n_A │ │ │Computes Q_A = n_A P. │ │ │Publishes the Public key Q_A. │ │ ├─────────────────┴─────────────────┤ │ Encryption │ ├─────────────────┬─────────────────┤ │ │Chooses plaintext values m1 and m2│ │ │ modulo p. │ │ │Chooses a random number k. │ │ │Computes R = ▓▓ │ │ │Computes S = ▓▓ and write it │ │ │ as S = (x_s, y_s). │ │ │Sets c_1 ≡ ▓▓ (mod p) and │ │ │ c_2 ≡ ▓▓ (mod p). │ │ │Sends ciphertext (R, c_1, c_2) to │ │ │ Alice. │ ├─────────────────┴─────────────────┤ │ Decryption │ ├─────────────────┬─────────────────┤ │Computes T = ▓▓ and writes it │ │ │ as T = (x_T, y_T). │ │ │Sets m1' ≡ ▓▓ (mod p) and │ │ │ m2' ≡ ▓▓ (mod p). │ │ │Then m1' = m1 and m2' = m2. │ │ └─────────────────┴─────────────────┘ (a) Complete the algorithm in the table. (b) What is message expansion of MV-EIGamal encryption? (c) Eve, and eavesdropper, knows c_1, c_2, and E. Show how Eve can use this knowledge to write down a polynomial equation (modulo p) that relates the two pieces m1 ane m2 of the plaintext. If Eve figures out one piece of the plaintext, then Eve can recover the other piece by finding the roots of the polynomial modulo p. 6. Factor an integer N with Lenstra's Elliptic Curve Method (ECM): (a) Explain how to choose a random curve E:Y^2 = X^3 + A*X + B (mod N) and a random point P = (a, b) on E efficiently. (b) Keep computin n!・P (mod N) for increasing n until the computation of scalar multiplication over Z_N fails. If a prime factor p of N is obtained, what is deduced about P on E (mod p)? 7. Scalar multiplications of elliptic curves are particularly efficient on Koblitz curves. (a) The Frobenius map τ from the field F_{p^k} to itself is defined by τ(α) = ﹍﹍﹍﹍ (b) The Frobenius map τon an elliptic curve E(F_{p^k}) is define by τ(x, y) = ﹍﹍﹍﹍ (c) Give the definition of Koblitz curves. (d) Show that if P is a point on a Koblitz curve E(F_{2^k}), then τ(P) is also on E(F_{2^k}). (e) Explain why τ(P) is a group homomorphism on E(F_{2^k}), i.e., τ(P + Q) = τ(P) + τ(Q) (f) Explain how to compute 7P on E(F_{2^k}) using the equation τ^2 + τ + 2 = 0 withour point doubling computations. 8. Let E: y^2 = x^3 + x be the elliptic curve over a field K and suppose that K has α∈K satisfying α^2 = -1. Define a map ψ(x, y) = (-x, αy) and ψ(O) = O. Show that (a) ψ is a map from E(K) to itself. (b) ψ(P + Q) = ψ(P) + ψ(Q) for all P≠Q in E(K). (c) ψ(2P) = 2ψ(P) for all P ∈E(K). (d) ψ(nP) = nψ(P) for all P ∈E(K) and all positive integer n. 9. Denote e_m(P, Q) as the Weil pairing for P, Q ∈E[m] (the subgroup of m-torsion points). Denote e~m(P, Q) = em(P, ψ(Q)) as the modified Weil pairing for and m-distortion map ψ. (a) Suppose Alice, Bob and Carl want to agree a shared key online. Describe the tripartite Diffie-Hellman key exchange proposed by Antoine Joux. (b) e_m(P, Q) or e~m(P, Q) is used in the above protocal? Explain why the other map does not work in the protocol. 10. Let P = (2, 5) and Q = (21, 21) be two points one the elliptic curve as the figure.(y^2 = x^3 + 7x + 3 over F_23) (a) Find the point R = P + Q. (b) Find the divisor of the function f = x - 21. (c) Find the rational function g associated to the divisor (P) + (Q) - (R) - (O). --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.51.114 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1453454502.A.AD0.html ※ 編輯: dittoh (140.112.51.114), 01/22/2016 17:25:33 ※ 編輯: dittoh (140.112.51.114), 01/22/2016 17:25:45