Rabin signature algorithm

From HandWiki
Revision as of 21:47, 8 February 2024 by Steve Marsio (talk | contribs) (add)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: Digital signature scheme

In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.[1][2][3]

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 [math]\displaystyle{ e=2 }[/math]', but this leads to qualitative differences that enable more efficient implementation[4] and a security guarantee relative to the difficulty of integer factorization,[2][3][5] which has not been proven for RSA. However, Rabin signatures have seen relatively little use or standardization outside IEEE P1363[6] 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 [math]\displaystyle{ H(m, u) }[/math] of a message [math]\displaystyle{ m }[/math] and [math]\displaystyle{ k }[/math]-bit randomization string [math]\displaystyle{ u }[/math].

Public key
A public key is a pair of integers [math]\displaystyle{ (n, b) }[/math] with [math]\displaystyle{ 0 \leq b \lt n }[/math] and [math]\displaystyle{ n }[/math] odd.
Signature
A signature on a message [math]\displaystyle{ m }[/math] is a pair [math]\displaystyle{ (u, x) }[/math] of a [math]\displaystyle{ k }[/math]-bit string [math]\displaystyle{ u }[/math] and an integer [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ x (x + b) \equiv H(m, u) \pmod n. }[/math]
Private key
The private key for a public key [math]\displaystyle{ (n, b) }[/math] is the secret odd prime factorization [math]\displaystyle{ p\cdot q }[/math] of [math]\displaystyle{ n }[/math], chosen uniformly at random from some space of large primes. Let [math]\displaystyle{ d = (b/2) \bmod n }[/math], [math]\displaystyle{ d_p = (b/2) \bmod p }[/math], and [math]\displaystyle{ d_q = (b/2) \bmod q }[/math]. To make a signature on a message [math]\displaystyle{ m }[/math], the signer picks a [math]\displaystyle{ k }[/math]-bit string [math]\displaystyle{ u }[/math] uniformly at random, and computes [math]\displaystyle{ c := H(m, u) }[/math]. If [math]\displaystyle{ c + d^2 }[/math] is a quadratic nonresidue modulo [math]\displaystyle{ n }[/math], then the signer throws away [math]\displaystyle{ u }[/math] and tries again. Otherwise, the signer computes [math]\displaystyle{ \begin{align} x_p &:= \Bigl(-d_p \pm \sqrt{c + {d_p}^2}\Bigr) \bmod p \\ x_q &:= \Bigl(-d_q \pm \sqrt{c + {d_q}^2}\Bigr) \bmod q, \end{align} }[/math] using a standard algorithm for computing square roots modulo a prime—picking [math]\displaystyle{ p \equiv q \equiv 3 \pmod 4 }[/math] makes it easiest. Square roots are not unique, and different variants of the signature scheme make different choices of square root;[4] in any case, the signer must ensure not to reveal two different roots for the same hash [math]\displaystyle{ c }[/math]. The signer then uses the Chinese remainder theorem to solve the system [math]\displaystyle{ \begin{align}x &\equiv x_q \pmod n \\ x &\equiv x_p \pmod n\end{align} }[/math] for [math]\displaystyle{ x }[/math]. The signer finally reveals [math]\displaystyle{ (u, x) }[/math].

Correctness of the signing procedure follows by evaluating [math]\displaystyle{ x (x + b) - H(m, u) }[/math] modulo [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] with [math]\displaystyle{ x }[/math] as constructed. For example, in the simple case where [math]\displaystyle{ b = 0 }[/math], [math]\displaystyle{ x }[/math] is simply a square root of [math]\displaystyle{ H(m, u) }[/math] modulo [math]\displaystyle{ n }[/math]. The number of trials for [math]\displaystyle{ u }[/math] is geometrically distributed with expectation around 4, because about 1/4 of all integers are quadratic residues modulo [math]\displaystyle{ n }[/math].

Security

Security against any adversary defined generically in terms of a hash function [math]\displaystyle{ H }[/math] (i.e., security in the random oracle model) follows from the difficulty of factoring [math]\displaystyle{ n }[/math]: Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots [math]\displaystyle{ x_1 }[/math] and [math]\displaystyle{ x_2 }[/math] of a random integer [math]\displaystyle{ c }[/math] modulo [math]\displaystyle{ n }[/math]. If [math]\displaystyle{ x_1 \pm x_2 \not\equiv 0 \pmod n }[/math] then [math]\displaystyle{ \gcd(x_1 \pm x_2, n) }[/math] is a nontrivial factor of [math]\displaystyle{ n }[/math], since [math]\displaystyle{ {x_1}^2 \equiv {x_2}^2 \equiv c \pmod n }[/math] so [math]\displaystyle{ n \mid {x_1}^2 - {x_2}^2 = (x_1 + x_2) (x_1 - x_2) }[/math] but [math]\displaystyle{ n \nmid x_1 \pm x_2 }[/math].[3] Formalizing the security in modern terms requires filling in some additional details, such as the codomain of [math]\displaystyle{ H }[/math]; if we set a standard size [math]\displaystyle{ K }[/math] for the prime factors, [math]\displaystyle{ 2^{K - 1} \lt p \lt q \lt 2^K }[/math], then we might specify [math]\displaystyle{ H\colon \{0,1\}^* \times \{0,1\}^k \to \{0,1\}^K }[/math].[5]

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[3] and resilience to collision attacks on fixed hash functions.[7][8][9]

Variants

The quantity [math]\displaystyle{ b }[/math] in the public key adds no security, since any algorithm to solve congruences [math]\displaystyle{ x (x + b) \equiv c \pmod n }[/math] for [math]\displaystyle{ x }[/math] given [math]\displaystyle{ b }[/math] and [math]\displaystyle{ c }[/math] can be trivially used as a subroutine in an algorithm to compute square roots modulo [math]\displaystyle{ n }[/math] and vice versa, so implementations can safely set [math]\displaystyle{ b = 0 }[/math] for simplicity; [math]\displaystyle{ b }[/math] was discarded altogether in treatments after the initial proposal.[10][3][6][4]

The Rabin signature scheme was later tweaked by Williams in 1980[10] to choose [math]\displaystyle{ p \equiv 3 \pmod 8 }[/math] and [math]\displaystyle{ q \equiv 7 \pmod 8 }[/math], and replace a square root [math]\displaystyle{ x }[/math] by a tweaked square root [math]\displaystyle{ (e, f, x) }[/math], with [math]\displaystyle{ e = \pm1 }[/math] and [math]\displaystyle{ f \in \{1,2\} }[/math], so that a signature instead satisfies [math]\displaystyle{ e f x^2 \equiv H(m, u) \pmod n, }[/math] which allows the signer to create a signature in a single trial without sacrificing security. This variant is known as Rabin–Williams.[4][6] Further variants allow tradeoffs between signature size and verification speed, partial message recovery, signature compression, and public key compression.[4]

Variants without the hash function have been published in textbooks,[11][12] crediting Rabin for exponent 2 but not for the use of a hash function. These variants are trivially broken—for example, the signature [math]\displaystyle{ x = 2 }[/math] can be forged by anyone as a valid signature on the message [math]\displaystyle{ m = 4 }[/math] if the signature verification equation is [math]\displaystyle{ x^2 \equiv m \pmod n }[/math] instead of [math]\displaystyle{ x^2 \equiv H(m, u) \pmod n }[/math].

In the original paper,[2] the hash function [math]\displaystyle{ H(m, u) }[/math] was written with the notation [math]\displaystyle{ C(MU) }[/math], with C for compression, and using juxtaposition to denote concatenation of [math]\displaystyle{ M }[/math] and [math]\displaystyle{ U }[/math] as bit strings:

By convention, when wishing to sign a given message, [math]\displaystyle{ M }[/math], [the signer] [math]\displaystyle{ P }[/math] adds as suffix a word [math]\displaystyle{ U }[/math] of an agreed upon length [math]\displaystyle{ k }[/math]. The choice of [math]\displaystyle{ U }[/math] is randomized each time a message is to be signed. The signer now compresses [math]\displaystyle{ M_1 = MU }[/math] by a hashing function to a word [math]\displaystyle{ C(M_1) = c }[/math], so that as a binary number [math]\displaystyle{ c \leq n }[/math]…

This notation has led to some confusion among some authors later who ignored the [math]\displaystyle{ C }[/math] part and misunderstood [math]\displaystyle{ MU }[/math] to mean multiplication, giving the misapprehension of a trivially broken signature scheme.[13]

References

  1. ↑ DeMillo, Richard A.; Dobkin, David P.; Jones, Anita K. et al., eds (1978). "Digitalized Signatures". Foundations of Secure Computation. New York: Academic Press. pp. 155–168. ISBN 0-12-210350-5. 
  2. ↑ 2.0 2.1 2.2 Template:Cite tech report
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Bellare, Mihir; Rogaway, Phillip (May 1996). "The Exact Security of Digital Signatures—How to Sign with RSA and Rabin". in Maurer, Ueli. Advances in Cryptology – EUROCRYPT ’96. 1070. Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8. 
  4. ↑ 4.0 4.1 4.2 4.3 4.4 RSA signatures and Rabin–Williams signatures: the state of the art (Report). January 31, 2008. https://cr.yp.to/papers.html#rwsota. 
  5. ↑ 5.0 5.1 Bernstein, Daniel J. (April 2008). "Proving tight security for Rabin–Williams signatures". in Smart, Nigel. Advances in Cryptology – EUROCRYPT 2008. 4965. Istanbul, Turkey: Springer. pp. 70–87. doi:10.1007/978-3-540-78967-3_5. ISBN 978-3-540-78966-6. https://cr.yp.to/papers.html#rwtight. 
  6. ↑ 6.0 6.1 6.2 IEEE Standard Specifications for Public-Key Cryptography. IEEE Std 1363-2000. Institute of Electrical and Electronics Engineers. August 25, 2000. doi:10.1109/IEEESTD.2000.92292. ISBN 0-7381-1956-3. 
  7. ↑ Submission to IEEE P1393—PSS: Provably Secure Encoding Method for Digital Signatures (Report). August 1998. http://grouper.ieee.org/groups/1363/P1363a/contributions/pss-submission.pdf. 
  8. ↑ Dwork, Cynthia, ed (August 2006). "Strengthening Digital Signatures via Randomized Hashing". Advances in Cryptology – CRYPTO 2006. 4117. Santa Barbara, CA, United States: Springer. pp. 41–59. doi:10.1007/11818175_3. http://webee.technion.ac.il/~hugo/rhash/rhash.pdf. 
  9. ↑ Dang, Quynh (February 2009). Randomized Hashing for Digital Signatures (Report). NIST Special Publication. 800-106. United States Department of Commerce, National Institute for Standards and Technology. doi:10.6028/NIST.SP.800-106. https://csrc.nist.gov/publications/detail/sp/800-106/final. 
  10. ↑ 10.0 10.1 "A modification of the RSA public-key encryption procedure". IEEE Transactions on Information Theory 26 (6): 726–729. doi:10.1109/TIT.1980.1056264. ISSN 0018-9448. https://cr.yp.to/bib/entries.html#1980/williams. 
  11. ↑ Handbook of Applied Cryptography. CRC Press. October 1996. pp. 438–442. ISBN 0-8493-8523-7. http://cacr.uwaterloo.ca/hac/about/chap11.pdf#page=15. 
  12. ↑ Mathematics of Public Key Cryptography. Cambridge University Press. 2012. pp. 491–494. ISBN 978-1-10701392-6. 
  13. ↑ "On the Rabin signature". Workshop on Computational Security. Centre de Recerca Matemàtica, Barcelona, Spain. 2011. https://www.math.uzh.ch/fileadmin/user/davide/publikation/SignatureRabin11.pdf. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Rabin_signature_algorithm&oldid=3433148"