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 0 \leq b 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) \equiv H(m, u) \pmod n. ; Private key : The private key for a public key (n, b) is the secret odd prime factorization p\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) \bmod n. If c + d^2 is a quadratic nonresidue modulo n, the signer starts over with an independent random u. 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 \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; 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) \equiv H(m,u) \pmod n as required. The signer reveals (u, x) as a signature on m. : The number of trials for u before x (x + b) \equiv H(m,u) \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 ==

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 \pm x_2 \not\equiv 0 \pmod n then \gcd(x_1 \pm x_2, n) is a nontrivial factor of n, since {x_1}^2 \equiv {x_2}^2 \equiv c \pmod n so n \mid {x_1}^2 - {x_2}^2 = (x_1 + x_2) (x_1 - x_2) but n \nmid x_1 \pm x_2. == Variants ==

Removing The quantity b in the public key adds no security, since any algorithm to solve congruences x (x + b) \equiv c \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. to choose p \equiv 3 \pmod 8 and q \equiv 7 \pmod 8, and replace a square root x by a tweaked square root (e, f, x), with e = \pm1 and f \in \{1,2\}, 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. Others 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. 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 \equiv m \pmod n instead of x^2 \equiv H(m, u) \pmod n. In the original paper, == References ==