Rabin signature algorithm

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

; Public key

: A public key is a pair of integers $(n,\; b)$ with and $n$ odd. $b$ is chosen arbitrarily and may be a fixed constant.

; Signature

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

; Private key

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

; Signing a message

: To make a signature on a message $m$ using the private key, the signer starts by picking a $k$-bit string $u$ uniformly at random, and computes $c\; :=\; H(m,\; u)$. Let $d\; =\; (b/2)\; \backslash bmod\; n$. If $c\; +\; d^2$ is a quadratic nonresidue modulo $n$, the signer starts over with an independent random $u$.{{rp|p. 10}} Otherwise, the signer computes $$$$

\begin{align}

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{align}

using a standard algorithm for computing square roots modulo a prime—picking $p\; \backslash equiv\; q\; \backslash equiv\; 3\; \backslash pmod\; 4$ makes it easiest. Square roots are not unique, and different variants of the signature scheme make different choices of square root; in any case, the signer must ensure not to reveal two different roots for the same hash $c$. $x\_p$ and $x\_q$ satisfy the equations $$$$

\begin{align}

x_p (x_p + b) &\equiv H(m,u) \pmod p, \\

x_q (x_q + b) &\equiv H(m,u) \pmod q.

\end{align}

The signer then uses the Chinese remainder theorem to solve the system $$$$

\begin{align}

x &\equiv x_p \pmod p, \\

x &\equiv x_q \pmod q,

\end{align}

for $x$, so that $x$ satisfies $$x\; (x\; +\; b)\; \backslash equiv\; H(m,u)\; \backslash pmod\; n$$ as required. The signer reveals $(u,\; x)$ as a signature on $m$.

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

Security against any adversary defined generically in terms of a hash function $H$ (i.e., security in the random oracle model) follows from the difficulty of factoring $n$:

Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots $x\_1$ and $x\_2$ of a random integer $c$ modulo $n$.

If $x\_1\; \backslash pm\; x\_2\; \backslash not\backslash equiv\; 0\; \backslash pmod\; n$ then $\backslash gcd(x\_1\; \backslash pm\; x\_2,\; n)$ is a nontrivial factor of $n$, since $\{x\_1\}^2\; \backslash equiv\; \{x\_2\}^2\; \backslash equiv\; c\; \backslash pmod\; n$ so $n\; \backslash mid\; \{x\_1\}^2\; -\; \{x\_2\}^2\; =\; (x\_1\; +\; x\_2)\; (x\_1\; -\; x\_2)$ but $n\; \backslash nmid\; x\_1\; \backslash pm\; x\_2$.

Formalizing the security in modern terms requires filling in some additional details, such as the codomain of $H$; if we set a standard size $K$ for the prime factors, , then we might specify $H\backslash colon\; \backslash \{0,1\backslash \}^*\; \backslash times\; \backslash \{0,1\backslash \}^k\; \backslash to\; \backslash \{0,1\backslash \}^K$.

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 and resilience to collision attacks on fixed hash functions.{{cite report

|author1-last=Bellare

|author1-first=Mihir

|author1-link=Mihir Bellare

|author2-last=Rogaway

|author2-first=Phillip

|author2-link=Phillip Rogaway

|title=Submission to IEEE P1393—PSS: Provably Secure Encoding Method for Digital Signatures

|date=August 1998

|url=http://grouper.ieee.org/groups/1363/P1363a/contributions/pss-submission.pdf

|archive-url=https://web.archive.org/web/20040713140300/http://grouper.ieee.org/groups/1363/P1363a/contributions/pss-submission.pdf

|archive-date=2004-07-13

}}{{cite conference

|author1-last=Halevi

|author1-first=Shai

|author1-link=Shai Halevi

|author2-last=Krawczyk

|author2-first=Hugo

|title=Strengthening Digital Signatures via Randomized Hashing

|url=http://webee.technion.ac.il/~hugo/rhash/rhash.pdf

|editor-last=Dwork

|editor-first=Cynthia

|editor-link=Cynthia Dwork

|conference=Advances in Cryptology – CRYPTO 2006

|conference-url=https://link.springer.com/book/10.1007%2F11818175

|date=August 2006

|volume=4117

|series=Lecture Notes in Computer Science

|publisher=Springer

|location=Santa Barbara, CA, United States

|doi=10.1007/11818175_3

|doi-access=free

|pages=41–59

}}{{cite report

|last=Dang

|first=Quynh

|title=Randomized Hashing for Digital Signatures

|series=NIST Special Publication

|volume=800-106

|publisher=United States Department of Commerce, National Institute for Standards and Technology

|date=February 2009

|url=https://csrc.nist.gov/publications/detail/sp/800-106/final

|doi=10.6028/NIST.SP.800-106

|doi-access=free

}}

The quantity $b$ in the public key adds no security, since any algorithm to solve congruences $x\; (x\; +\; b)\; \backslash equiv\; c\; \backslash pmod\; n$ for $x$ given $b$ and $c$ can be trivially used as a subroutine in an algorithm to compute square roots modulo $n$ and vice versa, so implementations can safely set $b\; =\; 0$ for simplicity; $b$ was discarded altogether in treatments after the initial proposal. After removing $b$, the equations for $x\_p$ and $x\_q$ in the signing algorithm become:$$$$

\begin{align}

x_p &:= \pm \sqrt{c} \bmod p, \\

x_q &:= \pm \sqrt{c} \bmod q.

\end{align}

The Rabin signature scheme was later tweaked by Williams in 1980{{cite journal

|author-last=Williams

|author-first=Hugh C.

|author-link=Hugh C. Williams

|title=A modification of the RSA public-key encryption procedure

|journal=IEEE Transactions on Information Theory

|volume=26

|issue=6

|issn=0018-9448

|pages=726–729

|url=https://cr.yp.to/bib/entries.html#1980/williams

|doi=10.1109/TIT.1980.1056264

}} to choose $p\; \backslash equiv\; 3\; \backslash pmod\; 8$ and $q\; \backslash equiv\; 7\; \backslash pmod\; 8$, and replace a square root $x$ by a tweaked square root $(e,\; f,\; x)$, with $e\; =\; \backslash pm1$ and $f\; \backslash in\; \backslash \{1,2\backslash \}$, so that a signature instead satisfies

e f x^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.{{cite book

|date=August 25, 2000

|publisher=Institute of Electrical and Electronics Engineers

|isbn=0-7381-1956-3

|doi=10.1109/IEEESTD.2000.92292

|title=IEEE Standard Specifications for Public-Key Cryptography

|series=IEEE Std 1363-2000

}}

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.

Variants without the hash function have been published in textbooks,{{cite book

|author1-last=Menezes

|author1-first=Alfred J.

|author1-link=Alfred Menezes

|author2-last=van Oorschot

|author2-first=Paul C.

|author2-link=Paul van Oorschot

|author3-last=Vanstone

|author3-first=Scott A.

|author3-link=Scott Vanstone

|title=Handbook of Applied Cryptography

|publisher=CRC Press

|date=October 1996

|isbn=0-8493-8523-7

|section=§11.3.4: The Rabin public-key signature scheme

|url=http://cacr.uwaterloo.ca/hac/about/chap11.pdf#page=15

|pages=438–442

}}{{cite book

|author1-last=Galbraith

|author1-first=Steven D.

|title=Mathematics of Public Key Cryptography

|publisher=Cambridge University Press

|year=2012

|isbn=978-1-10701392-6

|section=§24.2: The textbook Rabin cryptosystem

|pages=491–494

}} crediting Rabin for exponent 2 but not for the use of a hash function.

These variants are trivially broken—for example, the signature $x\; =\; 2$ can be forged by anyone as a valid signature on the message $m\; =\; 4$ if the signature verification equation is $x^2\; \backslash equiv\; m\; \backslash pmod\; n$ instead of $x^2\; \backslash equiv\; H(m,\; u)\; \backslash pmod\; n$.

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

By convention, when wishing to sign a given message, $M$, [the signer] $P$ adds as suffix a word $U$ of an agreed upon length $k$.

The choice of $U$ is randomized each time a message is to be signed.

The signer now compresses $M\_1\; =\; MU$ by a hashing function to a word $C(M\_1)\; =\; c$, so that as a binary number $c\; \backslash leq\; n$…

This notation has led to some confusion among some authors later who ignored the $C$ part and misunderstood $MU$ to mean multiplication, giving the misapprehension of a trivially broken signature scheme.{{cite conference

|author-last1=Elia

|author-first1=Michele

|author-last2=Schipani

|author-first2=David

|title=On the Rabin signature

|conference=Workshop on Computational Security

|year=2011

|location=Centre de Recerca Matemàtica, Barcelona, Spain

|url=https://www.math.uzh.ch/fileadmin/user/davide/publikation/SignatureRabin11.pdf

}}

{{reflist}}

• [https://cr.yp.to/sigs.html Rabin–Williams signatures at cr.yp.to]

Category:Digital signature schemes