Rabin signature algorithm

Rabin signature algorithm

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.

Original Algorithm

The algorithm relies on a collision-resistant hash function H : {0,1}^* ightarrow {0,1}^k

*Key Generation
**The signer "S" chooses primes "p","q" each of size approximately "k/2" bits, and computes the product n = pq
**"S" then chooses a random "b" in {1,ldots,n}.
**The public key is "(n,b)"
**The private key is "(p,q)"

*Signing
**To sign a message "m" the signer "S" picks random padding "U" and calculates "H(mU)"
**"S" then solves x(x+b) = H(mU) mod n
**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 follows

The hash function "H" is assumed to be a random oracle 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 n = pq
**The public key is "n"
**The private key is "(p,q)"

*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 x^2 = H(mU) mod n
**The signature on "m" is the pair "(U,x)"

*Verification
**Given a message "m" and a signature "(U,x)" the verifier "V" calculates "x"2 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 ( frac{a}{p}) = -( frac{a}{q}) = 1 and ( frac{b}{q}) = -( frac{b}{p}) = 1 where (cdot) denotes the legendre symbol. Then for any "r" modulo "n" exactly one of the four numbers r,ar,br,abr will be a square, and the signer chooses that one for his signature.

ecurity

If "H" is a random oracle, i.e. its output is truly random in mathbb{Z}/nmathbb{Z} then, forging a signature on any message "m" is as hard ascalculating the square root of a random element in mathbb{Z}/nmathbb{Z}. 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 x^2 = y^2 mod n but x e pm y mod n, then this immediately leads to a factorization of "n" since "n" divides x^2 - y^2 = (x-y)(x+y) but it does not divide either factor. Thus taking gcd(xpm y,n) 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 r^2 = R mod n, then, using the algorithm to take the square root of "R" modulo "n", we will get a new square root r^prime, and with probability half r e pm r^prime mod n.

References

* [http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf Original Paper]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Digital Signature Algorithm — The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature… …   Wikipedia

  • Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… …   Wikipedia

  • Merkle signature scheme — The Merkle signature scheme is a digital signature scheme based on hash trees (also called Merkle trees) and one time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 70s and is an alternative to… …   Wikipedia

  • String searching algorithm — String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. Let Σ be… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • E-imza — This article concerns cryptographic signatures. For signatures in digital form, see electronic signature. In cryptography, a digital signature or digital signature scheme is a type of asymmetric cryptography used to simulate the security… …   Wikipedia

  • Public-key cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key …   Wikipedia

  • Topics in cryptography — This article is intended to be an analytic glossary , or alternatively, an organized collection of annotated pointers.Classical ciphers*Autokey cipher *Permutation cipher*Polyalphabetic substitution **Vigenère cipher*Polygraphic substitution… …   Wikipedia

  • Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… …   Wikipedia

  • ElGamal encryption — In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public key cryptography which is based on the Diffie Hellman key agreement. It was described by Taher Elgamal in 1984 [Taher ElGamal, A Public Key… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”