Rabin signature algorithm
Encyclopedia
In cryptography
the Rabin Signature Scheme is a method of Digital signature
originally proposed by Michael O. Rabin
in 1979. The Rabin Signature Scheme was one of the first digital signature schemes proposed, and it was the first to relate the hardness of forgery directly to the problem of integer factorization. Because of its simplicity and prominent role in early public key cryptography, the Rabin Signature Scheme is covered in most introductory courses on cryptography. The Rabin Signature Scheme is existentially unforgeable in the random oracle
model assuming the integer factorization
problem is intractable. The Rabin Signature Scheme is also closely related to the Rabin cryptosystem
.
The hash function H is assumed to be a random oracle
and the algorithm works as follows
In some treatments, the random pad U is eliminated and instead we add two numbers a and b to the public key with
and 
where 
denotes the legendre symbol
. Then for any r modulo n exactly one of the four numbers
will be a square, and the signer chooses that one for his signature.
then, forging a signature on any message m is as hard as
calculating the square root of a random element in
. To see that taking a random square root is as hard as factoring, we first note that any square modulo n has four square roots since n has two square roots modulo p and two square roots modulo q, and each pair gives a unique square root modulo n by the chinese remainder theorem
. Now, if we have two different square roots, x,y such that
but 
, then this immediately leads to a factorization of n since n divides 
but it does not divide either factor. Thus taking 
will lead to a nontrivial factorization of n. Now, there exists an algorithm to take square roots, we pick a random r modulo n and square it 
, then, using the algorithm to take the square root of R modulo n, we will get a new square root 
, and with probability half 
.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
the Rabin Signature Scheme is a method of Digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
originally proposed by Michael O. Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
in 1979. The Rabin Signature Scheme was one of the first digital signature schemes proposed, and it was the first to relate the hardness of forgery directly to the problem of integer factorization. Because of its simplicity and prominent role in early public key cryptography, the Rabin Signature Scheme is covered in most introductory courses on cryptography. The Rabin Signature Scheme is existentially unforgeable in the random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
model assuming the integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
problem is intractable. The Rabin Signature Scheme is also closely related to the Rabin cryptosystem
Rabin cryptosystem
The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization, which is...
.
Original Algorithm
The algorithm relies on a collision-resistant hash function- Key Generation
- The signer S chooses primes p,q each of size approximately k/2 bits, and computes the product
- S then chooses a random b in
. - The public key is (n,b)
- The private key is (p,q)
- The signer S chooses primes p,q each of size approximately k/2 bits, and computes the product
- Signing
- To sign a message m the signer S picks random padding U and calculates H(mU)
- S then solves
- If there is no solution S picks a new pad U and tries again. If H is truly random the expected number of tries is 4.
- The signature on m is the pair (U,x)
- Verification
- Given a message m and a signature (U,x) the verifier V calculates x(x+b) and H(mU) and verifies that they are equal
Modern Terminology
In modern presentations, the algorithm is often simplified as followsThe hash function H is assumed to be a random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
and the algorithm works as follows
- Key Generation
- The signer S chooses primes p,q each of size approximately k/2 bits, and computes the product
- The public key is n
- The private key is (p,q)
- The signer S chooses primes p,q each of size approximately k/2 bits, and computes the product
- Signing
- To sign a message m' the signer S picks random padding U and calculates H(mU)
- If H(mU) is not a square modulo n, S picks a new pad U
- S solves the equation
- The signature on m is the pair (U,x)
- Verification
- Given a message m and a signature (U,x) the verifier V calculates x2 and H(mU) and verifies that they are equal
In some treatments, the random pad U is eliminated and instead we add two numbers a and b to the public key with
and where denotes the legendre symbolLegendre symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....
. Then for any r modulo n exactly one of the four numbers
will be a square, and the signer chooses that one for his signature.Security
If H is a random oracle, i.e. its output is truly random in then, forging a signature on any message m is as hard ascalculating the square root of a random element in
. To see that taking a random square root is as hard as factoring, we first note that any square modulo n has four square roots since n has two square roots modulo p and two square roots modulo q, and each pair gives a unique square root modulo n by the chinese remainder theoremChinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
. Now, if we have two different square roots, x,y such that
but , then this immediately leads to a factorization of n since n divides but it does not divide either factor. Thus taking will lead to a nontrivial factorization of n. Now, there exists an algorithm to take square roots, we pick a random r modulo n and square it , then, using the algorithm to take the square root of R modulo n, we will get a new square root , and with probability half .