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

This is why the congruence defining s was taken mod N .
If Eve can calculate discrete logs, then she can use A and B to find a .
In this case, she can put Alice's signature on any message. Alternatively,
Eve can use A and R to find k . Since she knows s, f ( R ) ,m , she can then
use ks =1,then

af ( R ) ≡ m − ks (mod N )has d solutions for a .Aslongas d is small, Eve
can try each possibility until she obtains B = aA . Then she can use a ,as
before, to forge Alice's signature on arbitrary messages.
As we just saw, Alice must keep a and k secret. Also, she must use a
different random k for each signature. Suppose she signs m and m using the
same k to obtain signed messages ( m, R, s )and( m ,R,s ). Eve immediately
recognizes that k has been used twice since R is the same for both signatures.
The equations for s, s yield the following:

≡ m − af ( R )(mod N ) to find a . f d =gcd( f ( R ) ,N )

ks ≡ m − af ( R )(mod N )
ks ≡ m − af ( R )(mod N ) .

Subtracting yields k ( s−s ) ≡ m−m (mod N ). Let d =gcd( s−s ,N ). There
are d possible values for k . Eve tries each one until R = kA is satisfied. Once
she knows k , she can find a ,asabove.
It is perhaps not necessary for Eve to solve discrete log problems in order to
forge Alice's signature on another message m . All Eve needs to do is produce
R, s such that the verification equation V 1 = V 2 is satisfied. This means that
she needs to find R =( x, y )and s such that

f ( R ) B + sR = mA.

If she chooses some point R (there is no need to choose an integer k ), she
needs to solve the discrete log problem sR = mA f ( R ) B for the integer s .

If, instead, she chooses s , then she must solve an equation for R =( x, y ). This
equation appears to be at least as complex as a discrete log problem, though it
has not been analyzed as thoroughly. Moreover, no one has been able to rule
out the possibility of using some procedure that finds R and s simultaneously.
There are ways of using a valid signed message to produce another valid signed
message (see Exercise 6.2). However, the messages produced are unlikely to
be meaningful messages.
The general belief is that the security of the ElGamal system is very close
to the security of discrete logs for the group E ( F q ).
A disadvantage of the ElGamal system is that the signed message ( m, R, s )
is approximately three times as long as the original message (it is not necessary
to store the full y -coordinate of R since there are only two choices for y for
agiven x ). A more ecient method is to choose a public hash function H
and sign H ( m ). A cryptographic hash function is a function that takes
inputs of arbitrary length, sometimes a message of billions of bits, and outputs
values of fixed length, for example, 160 bits. A hash function H should have
the following properties:

−