The Rabin signature scheme is parametrized by a randomized hash function ${\displaystyle H(m,u)}$  of a message ${\displaystyle m}$  and ${\displaystyle k}$ -bit randomization string ${\displaystyle u}$ .

Public key

A public key is a pair of integers ${\displaystyle (n,b)}$  with ${\displaystyle 0\leq b<n}$  and ${\displaystyle n}$  odd.

Signature

A signature on a message ${\displaystyle m}$  is a pair ${\displaystyle (u,x)}$  of a ${\displaystyle k}$ -bit string ${\displaystyle u}$  and an integer ${\displaystyle x}$  such that

$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}.}$$

 

Private key

The private key for a public key ${\displaystyle (n,b)}$  is the secret odd prime factorization ${\displaystyle p\cdot q}$  of ${\displaystyle n}$ , chosen uniformly at random from some space of large primes. Let ${\displaystyle d=(b/2){\bmod {n}}}$ , ${\displaystyle d_{p}=(b/2){\bmod {p}}}$ , and ${\displaystyle d_{q}=(b/2){\bmod {q}}}$ . To make a signature on a message ${\displaystyle m}$ , the signer picks a ${\displaystyle k}$ -bit string ${\displaystyle u}$  uniformly at random, and computes ${\displaystyle c:=H(m,u)}$ . If ${\displaystyle c+d^{2}}$  is a quadratic nonresidue modulo ${\displaystyle n}$ , then the signer throws away ${\displaystyle u}$  and tries again. Otherwise, the signer computes

$${\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d_{p}\pm {\sqrt {c+{d_{p}}^{2}}}{\Bigr )}{\bmod {p}}\\x_{q}&:={\Bigl (}-d_{q}\pm {\sqrt {c+{d_{q}}^{2}}}{\Bigr )}{\bmod {q}},\end{aligned}}}$$

 

using a standard algorithm for computing square roots modulo a prime—picking ${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$  makes it easiest. Square roots are not unique, and different variants of the signature scheme make different choices of square root;^[4] in any case, the signer must ensure not to reveal two different roots for the same hash ${\displaystyle c}$ . The signer then uses the Chinese remainder theorem to solve the system

$${\displaystyle {\begin{aligned}x&\equiv x_{q}{\pmod {n}}\\x&\equiv x_{p}{\pmod {n}}\end{aligned}}}$$

 

for ${\displaystyle x}$ . The signer finally reveals ${\displaystyle (u,x)}$ .

Correctness of the signing procedure follows by evaluating ${\displaystyle x(x+b)-H(m,u)}$  modulo ${\displaystyle p}$  and ${\displaystyle q}$  with ${\displaystyle x}$  as constructed. For example, in the simple case where ${\displaystyle b=0}$ , ${\displaystyle x}$  is simply a square root of ${\displaystyle H(m,u)}$  modulo ${\displaystyle n}$ . The number of trials for ${\displaystyle u}$  is geometrically distributed with expectation around 4, because about 1/4 of all integers are quadratic residues modulo ${\displaystyle n}$ .

Security against any adversary defined generically in terms of a hash function ${\displaystyle H}$  (i.e., security in the random oracle model) follows from the difficulty of factoring ${\displaystyle n}$ : Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots ${\displaystyle x_{1}}$  and ${\displaystyle x_{2}}$  of a random integer ${\displaystyle c}$  modulo ${\displaystyle n}$ . If ${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}$  then ${\displaystyle \gcd(x_{1}\pm x_{2},n)}$  is a nontrivial factor of ${\displaystyle n}$ , since ${\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}$  so ${\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})}$  but ${\displaystyle n\nmid x_{1}\pm x_{2}}$ .^[3] Formalizing the security in modern terms requires filling in some additional details, such as the codomain of ${\displaystyle H}$ ; if we set a standard size ${\displaystyle K}$  for the prime factors, ${\displaystyle 2^{K-1}<p<q<2^{K}}$ , then we might specify ${\displaystyle H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}}$ .^[5]

Randomization of the hash function was introduced to allow the signer to find a quadratic residue, but randomized hashing for signatures later became relevant in its own right for tighter security theorems^[3] and resilience to collision attacks on fixed hash functions.^[7][8][9]

The quantity ${\displaystyle b}$  in the public key adds no security, since any algorithm to solve congruences ${\displaystyle x(x+b)\equiv c{\pmod {n}}}$  for ${\displaystyle x}$  given ${\displaystyle b}$  and ${\displaystyle c}$  can be trivially used as a subroutine in an algorithm to compute square roots modulo ${\displaystyle n}$  and vice versa, so implementations can safely set ${\displaystyle b=0}$  for simplicity; ${\displaystyle b}$  was discarded altogether in treatments after the initial proposal.^{[10][3][6][4]}

The Rabin signature scheme was later tweaked by Williams in 1980^[10] to choose ${\displaystyle p\equiv 3{\pmod {8}}}$  and ${\displaystyle q\equiv 7{\pmod {8}}}$ , and replace a square root ${\displaystyle x}$  by a tweaked square root ${\displaystyle (e,f,x)}$ , with ${\displaystyle e=\pm 1}$  and ${\displaystyle f\in \{1,2\}}$ , so that a signature instead satisfies

Variants without the hash function have been published in textbooks,^[11][12] crediting Rabin for exponent 2 but not for the use of a hash function. These variants are trivially broken—for example, the signature ${\displaystyle x=2}$  can be forged by anyone as a valid signature on the message ${\displaystyle m=4}$  if the signature verification equation is ${\displaystyle x^{2}\equiv m{\pmod {n}}}$  instead of ${\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}$ .

In the original paper,^[2] the hash function ${\displaystyle H(m,u)}$  was written with the notation ${\displaystyle C(MU)}$ , with C for compression, and using juxtaposition to denote concatenation of ${\displaystyle M}$  and ${\displaystyle U}$  as bit strings:

By convention, when wishing to sign a given message, ${\displaystyle M}$ , [the signer] ${\displaystyle P}$  adds as suffix a word ${\displaystyle U}$  of an agreed upon length ${\displaystyle k}$ . The choice of ${\displaystyle U}$  is randomized each time a message is to be signed. The signer now compresses ${\displaystyle M_{1}=MU}$  by a hashing function to a word ${\displaystyle C(M_{1})=c}$ , so that as a binary number ${\displaystyle c\leq n}$ …

This notation has led to some confusion among some authors later who ignored the ${\displaystyle C}$  part and misunderstood ${\displaystyle MU}$  to mean multiplication, giving the misapprehension of a trivially broken signature scheme.^[13]

• Rabin–Williams signatures at cr.yp.to