Introduction to Cryptography with Open-Source Software

Digital signatures 155

for A; there will be gcd(r, p −1) so lutions. Now a

A

can be computed for each

solution until B is obtained. The system has been completely broken, and

Alice’s private key A is now public.

One of the verification steps is to check that r < p. If Bob accepts signa-

tures for which r ≥ p, then a signature can be forged: r and s values can be

created for which the corresponding v

1

and v

2

are equal. This can be done

by starting with a message m for which gcd(m, p − 1) = 1 and a leg itimate

signature (r, s) for m. Then given any other message m

′

a sig nature (r

′

, s

′

)

can be forge d by first defining

u = m

′

m

−1

(mod p − 1)

and then setting

s

′

=