Introduction to Cryptography with Open-Source Software

150 Cryptography with Open-Source Software

7.3 Rabin digital signatures

The Rabin signature scheme starts with similar parameters as in the RSA

scheme: two primes p and q, a nd their product N = pq. Like the RSA scheme,

the Rabin scheme is encryption “worked backwards.”

Signing the message. Alice computes a square root s o f the messa ge m

(recall that this is easiest if both p and q are congruent to 3 mod 4):

s

2

= m (mod N )

and sends the pair (m, s) to Bob.

Verifying the s ignature. Bob receives the pair (m, s). He squa res s to

compute

m

′

= s

2

(mod N )

and then compares m with m

′

. If they are equal, he acc e pts the signature.

Bob may be sure that the