Rabin signature algorithm

In cryptography, the Rabin signature algorithm is a method of digital signature originally published by Michael O. Rabin in 1979.^{[1] [2]}

The Rabin signature algorithm was one of the first digital signature schemes proposed. By using a trapdoor function with a hash of the message rather than with the message itself, in contrast to earlier proposals of one-time hash-based signatures or trapdoor-based signatures without hashing,^{[3] [4]} Rabin's was the first published design to meet what is now the modern standard of security for digital signatures for more than one message, existential unforgeability under chosen-message attack.^[5]

Rabin signatures resemble RSA signatures with exponent ${\displaystyle e=2}${\displaystyle e=2}, but this leads to qualitative differences that enable more efficient implementation^[5] and a security guarantee relative to the difficulty of integer factorization,^{[1] [2] [6]} which has not been proven for RSA. However, Rabin signatures have seen relatively little use or standardization outside IEEE P1363 ^[7] in comparison to RSA signature schemes such as RSASSA-PKCS1-v1_5 and RSASSA-PSS.

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

Public key

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

Signature

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

Private key

The private key for a public key ${\displaystyle (n,b)}${\displaystyle (n,b)} is the secret odd prime factorization ${\displaystyle p\cdot q}${\displaystyle p\cdot q} of ${\displaystyle n}${\displaystyle n}, chosen uniformly at random from some large space of primes.

Signing a message

To make a signature on a message ${\displaystyle m}${\displaystyle m} using the private key, the signer starts by picking a ${\displaystyle k}${\displaystyle k}-bit string ${\displaystyle u}${\displaystyle u} uniformly at random, and computes ${\displaystyle c:=H(m,u)}${\displaystyle c:=H(m,u)}. Let ${\displaystyle d=(b/2){\bmod {n}}}${\displaystyle d=(b/2){\bmod {n}}}. If ${\displaystyle c+d^{2}}${\displaystyle c+d^{2}} is a quadratic nonresidue modulo ${\displaystyle n}${\displaystyle n}, the signer starts over with an independent random ${\displaystyle u}${\displaystyle u}.^{[1] : p. 10} Otherwise, the signer computes $${\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {p}},\\x_{q}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {q}},\end{aligned}}}$${\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {p}},\\x_{q}&:={\Bigl (}-d\pm {\sqrt {c+d^{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}}}${\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;^[5] in any case, the signer must ensure not to reveal two different roots for the same hash ${\displaystyle c}${\displaystyle c}. ${\displaystyle x_{p}}${\displaystyle x_{p}} and ${\displaystyle x_{q}}${\displaystyle x_{q}} satisfy the equations $${\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}}$${\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}} The signer then uses the Chinese remainder theorem to solve the system $${\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}}$${\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}} for ${\displaystyle x}${\displaystyle x}, so that ${\displaystyle x}${\displaystyle x} satisfies $${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}} as required. The signer reveals ${\displaystyle (u,x)}${\displaystyle (u,x)} as a signature on ${\displaystyle m}${\displaystyle m}.

The number of trials for ${\displaystyle u}${\displaystyle u} before ${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}} can be solved for ${\displaystyle x}${\displaystyle x} is geometrically distributed with an average around 4 trials, because about 1/4 of all integers are quadratic residues modulo ${\displaystyle n}${\displaystyle n}.

Security against any adversary defined generically in terms of a hash function ${\displaystyle H}${\displaystyle H} (i.e., security in the random oracle model) follows from the difficulty of factoring ${\displaystyle n}${\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}}${\displaystyle x_{1}} and ${\displaystyle x_{2}}${\displaystyle x_{2}} of a random integer ${\displaystyle c}${\displaystyle c} modulo ${\displaystyle n}${\displaystyle n}. If ${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}} then ${\displaystyle \gcd(x_{1}\pm x_{2},n)}${\displaystyle \gcd(x_{1}\pm x_{2},n)} is a nontrivial factor of ${\displaystyle n}${\displaystyle n}, since ${\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}${\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})}${\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}}${\displaystyle n\nmid x_{1}\pm x_{2}}.^[2] Formalizing the security in modern terms requires filling in some additional details, such as the codomain of ${\displaystyle H}${\displaystyle H}; if we set a standard size ${\displaystyle K}${\displaystyle K} for the prime factors, ${\displaystyle 2^{K-1}<p<q<2^{K}}${\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}}${\displaystyle H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}}.^[6]

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^[2] and resilience to collision attacks on fixed hash functions.^{[8] [9] [10]}

The quantity ${\displaystyle b}${\displaystyle b} in the public key adds no security, since any algorithm to solve congruences ${\displaystyle x(x+b)\equiv c{\pmod {n}}}${\displaystyle x(x+b)\equiv c{\pmod {n}}} for ${\displaystyle x}${\displaystyle x} given ${\displaystyle b}${\displaystyle b} and ${\displaystyle c}${\displaystyle c} can be trivially used as a subroutine in an algorithm to compute square roots modulo ${\displaystyle n}${\displaystyle n} and vice versa, so implementations can safely set ${\displaystyle b=0}${\displaystyle b=0} for simplicity; ${\displaystyle b}${\displaystyle b} was discarded altogether in treatments after the initial proposal.^{[11] [2] [7] [5]} After removing ${\displaystyle b}${\displaystyle b}, the equations for ${\displaystyle x_{p}}${\displaystyle x_{p}} and ${\displaystyle x_{q}}${\displaystyle x_{q}} in the signing algorithm become:$${\displaystyle {\begin{aligned}x_{p}&:=\pm {\sqrt {c}}{\bmod {p}},\\x_{q}&:=\pm {\sqrt {c}}{\bmod {q}}.\end{aligned}}}$${\displaystyle {\begin{aligned}x_{p}&:=\pm {\sqrt {c}}{\bmod {p}},\\x_{q}&:=\pm {\sqrt {c}}{\bmod {q}}.\end{aligned}}}

The Rabin signature scheme was later tweaked by Williams in 1980^[11] to choose ${\displaystyle p\equiv 3{\pmod {8}}}${\displaystyle p\equiv 3{\pmod {8}}} and ${\displaystyle q\equiv 7{\pmod {8}}}${\displaystyle q\equiv 7{\pmod {8}}}, and replace a square root ${\displaystyle x}${\displaystyle x} by a tweaked square root ${\displaystyle (e,f,x)}${\displaystyle (e,f,x)}, with ${\displaystyle e=\pm 1}${\displaystyle e=\pm 1} and ${\displaystyle f\in \{1,2\}}${\displaystyle f\in \{1,2\}}, so that a signature instead satisfies $${\displaystyle efx^{2}\equiv H(m,u){\pmod {n}},}$${\displaystyle efx^{2}\equiv H(m,u){\pmod {n}},} which allows the signer to create a signature in a single trial without sacrificing security. This variant is known as Rabin–Williams.^{[5] [7]}

Further variants allow tradeoffs between signature size and verification speed, partial message recovery, signature compression (down to one-half size), and public key compression (down to one-third size), still without sacrificing security.^[5]

Variants without the hash function have been published in textbooks,^{[12] [13]} 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}${\displaystyle x=2} can be forged by anyone as a valid signature on the message ${\displaystyle m=4}${\displaystyle m=4} if the signature verification equation is ${\displaystyle x^{2}\equiv m{\pmod {n}}}${\displaystyle x^{2}\equiv m{\pmod {n}}} instead of ${\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}${\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}.

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

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

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

• Rabin–Williams signatures at cr.yp.to

• Digital signature schemes

• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata