Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 186

Exercises

6.1 Show that the map β in Section 6.2 is an isomorphism (it is clearly
bijective; the main point is that it is a homomorphism).

6.2 (a) Suppose that the ElGamal signature scheme is used to produce

the valid signed message ( m, R, s ), as in Section 6.5. Let h be an
integer with gcd( h, N ) = 1. Assume gcd( f ( R ) ,N ) = 1. Let

R = hR, s ≡ sf ( R ) f ( R ) − 1 h − 1 (mod N ) ,

m ≡ mf ( R ) f ( R ) − 1 (mod N ) .

Show that ( m ,R ,s ) is a valid signed message (however, it is un-
likely that m is a meaningful message, so this procedure does not
affect the security of the system).
(b) Suppose a hash function is used, so the signed messages are of the
form ( m, R H ,s H ). Explain why this prevents the method of (a)
from working.

6.3 Use the notation of Section 6.5. Let u, v be two integers with gcd( v, N )=
1andlet R = uA + vB .Let s ≡−v − 1 f ( R )(mod N )and m ≡ su
(mod N ).

(a) Show that ( m, R, s ) is a valid signed message for the ElGamal sig-
nature scheme. (However, it is unlikely that m is a meaningful
message.)

(b) Suppose a hash function is used, so the signed messages are of the
form ( m, R H ,s H ). Explain why this prevents the method of (a)
from working.

6.4 Let E be an elliptic curve over F q and let N =# E ( F q ). Alice has a
message that she wants to sign. She represents the message as a point
M ∈ E ( F q ). Alice has a secret integer a and makes public points A and
B in E ( F q )with B = aA , as in the ElGamal signature scheme. There
is a public function f : E ( F q ) → Z /N Z . Alice performs the following
steps.

(a) She chooses a random integer k with gcd( k, N )=1.

(b) She computes R = M kA .

(c) She computes s ≡ k − 1 (1 − f ( R ) a )(mod N ).
(d) The signed message is ( M, R, s ).

−

Bob verifies the signature as follows.