### What is the
Rabin Signature Scheme?

The Rabin signature scheme is a variant
of the RSA signature scheme (see Question 8).
It has the advantage over RSA that finding the private key
and forgery are both provably as hard as factoring.
Verification is faster than signing, as with RSA signatures.
In Rabin's scheme, the public key is an integer n where n =
pq, and p and q are prime numbers which form the private key.
The message to be signed must have a square root mod n;
otherwise, it has to be modified slightly. Only about 1/4 of
all possible messages have square roots mod n.

Signature: s = m^{1/2} mod n
where s is the signature

Verification: m = s^{2} mod n

The signature is easy to compute if the
prime factors of n are known, but probably difficult
otherwise - anyone who can forge the signature can also
factor n. The provable security has the side-effect that the
prime factors can be recovered under a chosen message attack.
This attack can be countered by padding a given message with
random bits or by modifying the message randomly, at the loss
of provable security. (See [GMR86] for a
discussion of a way to get around the paradox between
provable security and resistance to chosen message attacks.)