In
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, the Rabin signature algorithm is a method of
digital signature originally proposed by
Michael O. Rabin
Michael Oser Rabin (; born September 1, 1931) is an Israeli mathematician, computer scientist, and recipient of the Turing Award.
Biography Early life and education
Rabin was born in 1931 in Breslau, Germany (today Wrocław, in Poland), th ...
in 1978.
The Rabin signature algorithm was one of the first digital signature schemes proposed. By introducing the use of
hashing as an essential step in signing, it was the first design to meet what is now the modern standard of security against forgery,
existential unforgeability under chosen-message attack, assuming suitably scaled parameters.
Rabin signatures resemble
RSA signatures with exponent
, but this leads to qualitative differences that enable more efficient implementation
[ (additional information at https://cr.yp.to/sigs.html)] and a security guarantee relative to the difficulty of
integer factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
,
which
has not been proven for RSA.
However, Rabin signatures have seen relatively little use or standardization outside
IEEE P1363
IEEE P1363 is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public-key cryptography. It includes specifications for:
* Traditional public-key cryptography (IEEE Std 1363-2000 and 1363a-2004)
* Lattice-ba ...
in comparison to RSA signature schemes such as
RSASSA-PKCS1-v1_5 and
RSASSA-PSS.
Definition
The Rabin signature scheme is parametrized by a randomized
hash function
A hash function is any Function (mathematics), function that can be used to map data (computing), data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a ...
of a message
and
-bit randomization string
.
; Public key
: A public key is a pair of integers
with
and
odd.
is chosen arbitrarily and may be a fixed constant.
; Signature
: A signature on a message
is a pair
of a
-bit string
and an integer
such that
; Private key
: The private key for a public key
is the secret odd prime factorization
of
, chosen uniformly at random from some large space of primes.
; Signing a message
: To make a signature on a message
using the private key, the signer starts by picking a
-bit string
uniformly at random, and computes
. Let
. If
is a
quadratic nonresidue
In number theory, an integer ''q'' is a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; that is, if there exists an integer ''x'' such that
:x^2\equiv q \pmod.
Otherwise, ''q'' is a quadratic nonresidue modu ...
modulo
, the signer starts over with an independent random
.
Otherwise, the signer computes
using a
standard algorithm for computing square roots modulo a prime—picking
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
.
and
satisfy the equations
The signer then uses the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
to solve the system
for
, so that
satisfies
as required. The signer reveals
as a signature on
.
: The number of trials for
before
can be solved for
is geometrically distributed with an average around 4 trials, because about 1/4 of all integers are quadratic residues modulo
.
Security
Security against any adversary defined generically in terms of a hash function
(i.e., security in the
random oracle model
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every tim ...
) follows from the difficulty of factoring
:
Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots
and
of a random integer
modulo
.
If
then
is a nontrivial factor of
, since
so
but
.
Formalizing the security in modern terms requires filling in some additional details, such as the codomain of
; if we set a standard size
for the prime factors,
, then we might specify
.
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.
Variants
Removing
The quantity
in the public key adds no security, since any algorithm to solve congruences
for
given
and
can be trivially used as a subroutine in an algorithm to compute square roots modulo
and vice versa, so implementations can safely set
for simplicity;
was discarded altogether in treatments after the initial proposal.
After removing
, the equations for
and
in the signing algorithm become:
Rabin-Williams
The Rabin signature scheme was later tweaked by
Williams in 1980
to choose
and
, and replace a square root
by a tweaked square root
, with
and
, so that a signature instead satisfies
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.
Variants without the hash function have been published in textbooks,
crediting Rabin for exponent 2 but not for the use of a hash function.
These variants are trivially broken—for example, the signature
can be forged by anyone as a valid signature on the message
if the signature verification equation is
instead of
.
In the original paper,
the hash function
was written with the notation
, with ''C'' for ''compression'', and using juxtaposition to denote concatenation of
and
as bit strings:
By convention, when wishing to sign a given message, , he signer adds as suffix a word of an agreed upon length .
The choice of is randomized each time a message is to be signed.
The signer now compresses by a hashing function to a word , so that as a binary number …
This notation has led to some confusion among some authors later who ignored the
part and misunderstood
to mean multiplication, giving the misapprehension of a trivially broken signature scheme.
References
{{reflist
External links
Rabin–Williams signatures at cr.yp.to
Digital signature schemes