※ 引述《dittoh (ditto)》之铭言： : 课程名称︰椭圆曲线密码学 : 课程性质︰选修 : 课程教师︰陈君明 : 开课学院：理学院 : 开课系所︰数学系 : 考试日期（年月日）︰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 line: 2%; intercept: 1% for each; 10% in total for this problem : 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, λ). (5%) (5%) Note: You need to prove the formula, not just give the answer. 2 3x + A 1 2 g(x ,y ) = ————. h(x ,x ,λ) = λ - x - x . 1 1 2y 1 2 1 2 1 : 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? (a) 8 doublings and 6 additions are required. (4%) 2 5 9 (b) 477 = 1-2 -2 +2 . (4%) (c) 9 doublings and 3 additions are required. (2%) : 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. (a) Find n such that Q = nP onthe curve E. (4%) (b) (6%) : 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. (a) R = kP; S = kQ (1%). c = x m ; c = y m (1%). A 1 S 1 2 S 2 -1 -1 T = n R (1%). m' = c x ; m' = c y (1%) A 1 1 T 2 2 T (b) 2 or 1.5. (3%) -1 2 -1 3 -1 (c) (c m ) = (c m ) + Ac m + B (mod p). (3%) 2 2 1 1 1 1 : 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)? (a) First choose a point P = (a, b) randomly. Then choose A randomly. 2 3 Finally, let B = b -a -Ax (mod N). (5%) (b) [n!]P = O (mod p). (5%) : 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. P P P 2 3 2 (a) α (1%); (b) (x ,y ) (1%); (c) Y + XY = X + aX + 1, a∈{0,1}. (2%) (d) (2%); (e) (2%); (f) (2%). : 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. (a) (2%); (b) (3%); (c) (3%); (d) (By the Mathematical Induction)(2%) : 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. (a) (6%); (b) (4%). : 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). (a) R = (16,5). (3%) (b) div(f) = [Q] + [-Q] - 2[O]. (3%) y + 4x + 10 (c) ——————. (4%) x - 16 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 58.115.123.62 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1456050762.A.0C3.html