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

(a) He computes V 1 = sR − f ( R ) B and V 2 = sM − A .

(b) He declares the signature valid if V 1 = V 2 .

Show that if Alice performs the required steps correctly, then the ver-
ification equation V 1 = V 2 holds. (This signature scheme is a variant
of one due to Nyberg and Rueppel (see [12]). An interesting feature is
that the message appears as an element of the group E ( F q ) rather than
as an integer.)

6.5 Let p, q be prime numbers and suppose you know the numbers m =
( p +1)( q +1) and n = pq . Show that p, q are the roots of the quadratic
equation

x 2 − ( m − n − 1) x + n =0

(so p, q can be found using the quadratic formula).

6.6 Let E be the elliptic curve y 2 = x 3 + b mod p ,where p ≡ 2(mod3).

(a) Suppose E [ n ] ⊆ E ( F p )forsome n ≡ 0(mod p ). Show that n|p− 1
and n 2 | p + 1. Conclude that n ≤ 2.

(b) Show that E [2] E ( F p ).

(c) Show that E ( F p ) is cyclic (of order p +1).

⊆

6.7 Let p ≡ 3 (mod 4) be a prime number. Suppose x ≡ y 2 (mod p ).

(a) Show that ( y ( p +1) / 2 ) 2 ≡ y 2 (mod p ).

(b) Show that y ( p +1) / 2 ≡±y (mod p ).

(c) Show that x ( p +1) / 4 is a square root of x (mod p ).
(d) Suppose z is not a square mod p . Using the fact that − 1isnota
square mod p , show that z is a square mod p .

(e) Show that z ( p +1) / 4 is a square root of

−

− z (mod p ).

6.8 Let p =6 1and E be as in Section 6.9. The hash function H 1 in that

section inputs a string of bits of arbitrary length and outputs a point of
order on E . Onewaytodothisisasfollows.

−

(a) Choose a hash function H that outputs integers mod p . Input a
binary string B . Let the output of H be the y coordinate of a
point: y = H ( B ). Show that there is a unique x mod p such that
( x, y ) lies on E .
(b) Let H 1 ( B )=6( x, y ). Show that H 1 ( B )isapointoforder or 1
on E . Why is it very unlikely that H 1 ( B ) has order 1?