Rabin Signatures

The Rabin signature scheme has the benefit of being incredibly user friendly for the user, the only requirement to validate a signature is knowledge of the signatory’s public modulus, N, and the ability to square a number. This operation is incredibly fast, allowing a signature to be verified immediately.

A traditional RSA Digital Signature requires a more complicated procedure on the part of the verifier, raising a large integer to a large power (typically 65537).

We will investigate the security mechanism of Rabin’s signatures later in this post, but simply put, mathematically the security is identical to RSA digital signatures schemes. RSA relies on the difficulty computers have factoring large composite numbers, Rabin signatures rely on the difficulty finding square roots within a finite field. Mathematically factoring a number N and finding square roots in the finite field $\mathbb{Z}_N$ are identical concepts, and therefore have equal difficulty.

{There is a proveable correlation: one can factor N iff one can find square roots within $\mathbb{Z}_N$ .

The tradeoff
If Rabin Signatures are faster and of equal security, what’s the downside? There is more work required by the signatory. Instead of the traditional RSA digital signature scheme where the signatory is able to perform a single large integer raised to an exponent and simplified with a modulus, the Rabin signature requires the signatory to work through a series of calculations designed to find a specific type of value, a perfect square.

The Details

A Rabin signature is, like most signatures, a math function performed on the hash of the message. The standard hash is sha256, which is converted from a bytes-object to a long integer using bytes_to_long. That integer is what will require processing, the goal being to find an integer value which is a perfect square within the finite field $\mathbb{Z}_N$ .

The math
The power / mod function is at the heart of this scheme too, where we have a signature, s, a private key which is the factorization of a modulus, p*q = N, and a message which has been hashed and converted to an integer h.

$s = \sqrt{h} = h^\frac{1}{2}\hspace{2mm} mod \hspace{2mm} N$

To verify a signature
Verification is quite simple. Once a message and signature <m, s> are received, the user can take their own hash of the message, $h = \tt{sha256(m)}$ .

The received signature, s, is a long integer. This integer can be squared within the finite field $s^2 \hspace{2mm} mod \hspace{2mm} N$ , and converted back to bytes using long_to_bytes.

Finally this bytes-object should be compared to hash the user computed.

If the hashes match, the signature is validated, otherwise it’s invalid.

Some Variations!

The Original Rabin Scheme which uses an arbitrary value b and requires signatures to meet a requrement of

$s(s+b) \equiv H(m)$

with H being a hash of the message. This equation doesn’t quite align with what we think of as Rabin signatures since we now have

$s^2 + s*b \equiv H(m)$

Therefore, the first variation, once it was shown to maintain the same level of security, to Rabin’s signature removed b, so the signature would be simply $s^2 \equiv H(m)$ .

This variation makes calculation of the square roots a little bit easier. With p and q being equivalent to $(3 \hspace{2mm} mod \hspace{2mm} 4)$ , there is a formula which allows for quick calculation of a square root $s = h^\frac{p+1}{4} mod \hspace{2mm} p, q$ . Sometimes there will be no well-defined square root, and there is a process of padding the message before the hash which results in a solution after usually no more than four iterations.

Finding the square root $(mod \hspace{2mm} N)$ knowing the square roots $(mod \hspace{2mm} p, q)$ is a straight forward application of the Chinese Remainder Theorem:

$s_p \equiv H(m) \hspace{2mm} mod \hspace{2mm} p$

$s_q \equiv H(m) \hspace{2mm} mod \hspace{2mm} q$

$s = crt(s_p, s_q)$

With this scheme the public key is the value <N> and the private key is the factorization <p, q>.

There Rabin-Williams Variant was suggested by Hugh Williams. The value of p, q are chosen to be $p \equiv 3 \hspace{2mm} mod \hspace{2mm} 8$ , and $q \equiv 7 \hspace{2mm} mod \hspace{2mm} 8$ . Notice p, q still retain the quality above that $p,q, \equiv 3 \hspace{2mm} mod \hspace{2mm} 4$ .

Using this variation and a slight variation to the square root it is possible to create the signature outright with no iterative attempts.

CyberBear