※ 引述《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