課程名稱︰橢圓曲線密碼學
課程性質︰選修
課程教師︰陳君明
開課學院：理學院
開課系所︰數學系
考試日期（年月日）︰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).