MATH 195: CRYPTOGRAPHY HOMEWORK #14

Problem 6.28. Let E : y^{2} = x^{3} + x^{2} + 1 over 𝔽_{3}.

(a) Determine all points of E(𝔽_{3}).

(b) Make a group table for E(𝔽_{3}).

Problem 6.29. Let E be an elliptic curve over 𝔽_{q}, and define t_{0}, t_{1}, t_{2}, … by t_{0} = 2, t_{1} = q + 1 − #E(𝔽_{q}), and

t_{n} = t_{1} · t_{n−1} − qt_{n−2},

for n ≥ 2. Prove that for all n one has

#E(𝔽_{q^{n}}) = q^{n} + 1 − t_{n}.

[Use the theorem stated in class.]

Problem 6.30. Let E : y^{2} = x^{3} − x + 1 over 𝔽_{3}.

(a) Determine #E(𝔽_{3}).

(b) Prove: E(𝔽_{3}) = E(𝔽_{9}).
(c) Compute #E(𝔽_{27}) and #E(𝔽_{81}).

Problem 6.31. Alice and Bob do a Diffie-Hellman key exchange using the group E(𝔽_{3}), where E : y^{2} = x^{3} − x + 1, with g = (1, 1). They use secret exponents a = 2 and b = 3. What is the secret common key that they exchange?

Date: May 7, 2002.

6.28, 6.29, 6.30, 6.31.