Rabin signature algorithm

<h2 id="definition">Definition</h2>
The Rabin signature scheme is parametrized by a randomized <a href="/facts/Cryptographic_hash_function/cuxkgbST">hash function</a> 
 
 
 
 H
 (
 m
 ,
 u
 )
 
 
 {\displaystyle H(m,u)}
 
 of a message 
 
 
 
 m
 
 
 {\displaystyle m}
 
 and 
 
 
 
 k
 
 
 {\displaystyle k}
 
-bit randomization string 
 
 
 
 u
 
 
 {\displaystyle u}
 
.

Public key
A public key is a pair of integers 
 
 
 
 (
 n
 ,
 b
 )
 
 
 {\displaystyle (n,b)}
 
 with 
 
 
 
 0
 ≤
 b
 <
 n
 
 
 {\displaystyle 0\leq b<n}
 
 and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 odd. 
 
 
 
 b
 
 
 {\displaystyle b}
 
 is chosen arbitrarily and may be a fixed constant.
Signature
A signature on a message 
 
 
 
 m
 
 
 {\displaystyle m}
 
 is a pair 
 
 
 
 (
 u
 ,
 x
 )
 
 
 {\displaystyle (u,x)}
 
 of a 
 
 
 
 k
 
 
 {\displaystyle k}
 
-bit string 
 
 
 
 u
 
 
 {\displaystyle u}
 
 and an integer 
 
 
 
 x
 
 
 {\displaystyle x}
 
 such that 
 
 
 
 x
 (
 x
 +
 b
 )
 ≡
 H
 (
 m
 ,
 u
 )
 
 
 (
 mod
 
 n
 )
 
 .
 
 
 {\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}.}

Private key
The private key for a public key 
 
 
 
 (
 n
 ,
 b
 )
 
 
 {\displaystyle (n,b)}
 
 is the secret odd prime factorization 
 
 
 
 p
 ⋅
 q
 
 
 {\displaystyle p\cdot q}
 
 of 
 
 
 
 n
 
 
 {\displaystyle n}
 
, chosen uniformly at random from some large space of primes.
Signing a message
To make a signature on a message 
 
 
 
 m
 
 
 {\displaystyle m}
 
 using the private key, the signer starts by picking a 
 
 
 
 k
 
 
 {\displaystyle k}
 
-bit string 
 
 
 
 u
 
 
 {\displaystyle u}
 
 uniformly at random, and computes 
 
 
 
 c
 :=
 H
 (
 m
 ,
 u
 )
 
 
 {\displaystyle c:=H(m,u)}
 
. Let 
 
 
 
 d
 =
 (
 b
 
 /
 
 2
 )
 
 mod
 
 n
 
 
 
 
 {\displaystyle d=(b/2){\bmod {n}}}
 
. If 
 
 
 
 c
 +
 
 d
 
 2
 
 
 
 
 {\displaystyle c+d^{2}}
 
 is a <a href="/facts/Quadratic_nonresidue/rHD2uQdQ">quadratic nonresidue</a> modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
, the signer starts over with an independent random 
 
 
 
 u
 
 
 {\displaystyle u}
 
.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>: p. 10  Otherwise, the signer computes 
 
 
 
 
 
 
 
 
 x
 
 p
 
 
 
 
 
 :=
 
 
 (
 
 
 −
 d
 ±
 
 
 c
 +
 
 d
 
 2
 
 
 
 
 
 
 )
 
 
 
 mod
 
 p
 
 
 ,
 
 
 
 
 
 x
 
 q
 
 
 
 
 
 :=
 
 
 (
 
 
 −
 d
 ±
 
 
 c
 +
 
 d
 
 2
 
 
 
 
 
 
 )
 
 
 
 mod
 
 q
 
 
 ,
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}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{aligned}}}
 
 using a <a href="/facts/Quadratic_residue/rHD2uQdQ">standard algorithm for computing square roots modulo a prime</a>—picking 
 
 
 
 p
 ≡
 q
 ≡
 3
 
 
 (
 mod
 
 4
 )
 
 
 
 {\displaystyle 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;<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> in any case, the signer must ensure not to reveal two different roots for the same hash 
 
 
 
 c
 
 
 {\displaystyle c}
 
. 
 
 
 
 
 x
 
 p
 
 
 
 
 {\displaystyle x_{p}}
 
 and 
 
 
 
 
 x
 
 q
 
 
 
 
 {\displaystyle x_{q}}
 
 satisfy the equations 
 
 
 
 
 
 
 
 
 x
 
 p
 
 
 (
 
 x
 
 p
 
 
 +
 b
 )
 
 
 
 ≡
 H
 (
 m
 ,
 u
 )
 
 
 (
 mod
 
 p
 )
 
 ,
 
 
 
 
 
 x
 
 q
 
 
 (
 
 x
 
 q
 
 
 +
 b
 )
 
 
 
 ≡
 H
 (
 m
 ,
 u
 )
 
 
 (
 mod
 
 q
 )
 
 .
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}}
 
 The signer then uses the <a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a> to solve the system 
 
 
 
 
 
 
 
 x
 
 
 
 ≡
 
 x
 
 p
 
 
 
 
 (
 mod
 
 p
 )
 
 ,
 
 
 
 
 x
 
 
 
 ≡
 
 x
 
 q
 
 
 
 
 (
 mod
 
 q
 )
 
 ,
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}}
 
 for 
 
 
 
 x
 
 
 {\displaystyle x}
 
, so that 
 
 
 
 x
 
 
 {\displaystyle x}
 
 satisfies 
 
 
 
 x
 (
 x
 +
 b
 )
 ≡
 H
 (
 m
 ,
 u
 )
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}
 
 as required. The signer reveals 
 
 
 
 (
 u
 ,
 x
 )
 
 
 {\displaystyle (u,x)}
 
 as a signature on 
 
 
 
 m
 
 
 {\displaystyle m}
 
.
The number of trials for 
 
 
 
 u
 
 
 {\displaystyle u}
 
 before 
 
 
 
 x
 (
 x
 +
 b
 )
 ≡
 H
 (
 m
 ,
 u
 )
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}
 
 can be solved for 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is geometrically distributed with an average around 4 trials, because about 1/4 of all integers are quadratic residues modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
.
<h2 id="security">Security</h2>
Security against any adversary defined generically in terms of a hash function 
 
 
 
 H
 
 
 {\displaystyle H}
 
 (i.e., security in the <a href="/facts/Random_oracle_model/wK7MhxDq">random oracle model</a>) follows from the difficulty of factoring 
 
 
 
 n
 
 
 {\displaystyle n}
 
:
Any such adversary with high probability of success at forgery can, with nearly as high probability, find two distinct square roots 
 
 
 
 
 x
 
 1
 
 
 
 
 {\displaystyle x_{1}}
 
 and 
 
 
 
 
 x
 
 2
 
 
 
 
 {\displaystyle x_{2}}
 
 of a random integer 
 
 
 
 c
 
 
 {\displaystyle c}
 
 modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
.
If 
 
 
 
 
 x
 
 1
 
 
 ±
 
 x
 
 2
 
 
 ≢
 0
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}
 
 then 
 
 
 
 gcd
 (
 
 x
 
 1
 
 
 ±
 
 x
 
 2
 
 
 ,
 n
 )
 
 
 {\displaystyle \gcd(x_{1}\pm x_{2},n)}
 
 is a nontrivial factor of 
 
 
 
 n
 
 
 {\displaystyle n}
 
, since 
 
 
 
 
 
 
 x
 
 1
 
 
 
 
 2
 
 
 ≡
 
 
 
 x
 
 2
 
 
 
 
 2
 
 
 ≡
 c
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}
 
 so 
 
 
 
 n
 ∣
 
 
 
 x
 
 1
 
 
 
 
 2
 
 
 −
 
 
 
 x
 
 2
 
 
 
 
 2
 
 
 =
 (
 
 x
 
 1
 
 
 +
 
 x
 
 2
 
 
 )
 (
 
 x
 
 1
 
 
 −
 
 x
 
 2
 
 
 )
 
 
 {\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})}
 
 but 
 
 
 
 n
 ∤
 
 x
 
 1
 
 
 ±
 
 x
 
 2
 
 
 
 
 {\displaystyle n\nmid x_{1}\pm x_{2}}
 
.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Formalizing the security in modern terms requires filling in some additional details, such as the codomain of 
 
 
 
 H
 
 
 {\displaystyle H}
 
; if we set a standard size 
 
 
 
 K
 
 
 {\displaystyle K}
 
 for the prime factors, 
 
 
 
 
 2
 
 K
 −
 1
 
 
 <
 p
 <
 q
 <
 
 2
 
 K
 
 
 
 
 {\displaystyle 2^{K-1}<p<q<2^{K}}
 
, then we might specify 
 
 
 
 H
 :
 {
 0
 ,
 1
 
 }
 
 ∗
 
 
 ×
 {
 0
 ,
 1
 
 }
 
 k
 
 
 →
 {
 0
 ,
 1
 
 }
 
 K
 
 
 
 
 {\displaystyle H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}}
 
.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
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<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> and resilience to collision attacks on fixed hash functions.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h2 id="variants">Variants</h2>
<h3>Removing 
 
 
 
 b
 
 
 {\displaystyle b}
 
</h3>
The quantity 
 
 
 
 b
 
 
 {\displaystyle b}
 
 in the public key adds no security, since any algorithm to solve congruences 
 
 
 
 x
 (
 x
 +
 b
 )
 ≡
 c
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle x(x+b)\equiv c{\pmod {n}}}
 
 for 
 
 
 
 x
 
 
 {\displaystyle x}
 
 given 
 
 
 
 b
 
 
 {\displaystyle b}
 
 and 
 
 
 
 c
 
 
 {\displaystyle c}
 
 can be trivially used as a subroutine in an algorithm to compute square roots modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
 and vice versa, so implementations can safely set 
 
 
 
 b
 =
 0
 
 
 {\displaystyle b=0}
 
 for simplicity; 
 
 
 
 b
 
 
 {\displaystyle b}
 
 was discarded altogether in treatments after the initial proposal.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a><a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> After removing 
 
 
 
 b
 
 
 {\displaystyle b}
 
, the equations for 
 
 
 
 
 x
 
 p
 
 
 
 
 {\displaystyle x_{p}}
 
 and 
 
 
 
 
 x
 
 q
 
 
 
 
 {\displaystyle x_{q}}
 
 in the signing algorithm become:
 
 
 
 
 
 
 
 
 x
 
 p
 
 
 
 
 
 :=
 ±
 
 
 c
 
 
 
 mod
 
 p
 
 
 ,
 
 
 
 
 
 x
 
 q
 
 
 
 
 
 :=
 ±
 
 
 c
 
 
 
 mod
 
 q
 
 
 .
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}x_{p}&:=\pm {\sqrt {c}}{\bmod {p}},\\x_{q}&:=\pm {\sqrt {c}}{\bmod {q}}.\end{aligned}}}

<h3>Rabin-Williams</h3>
The Rabin signature scheme was later tweaked by <a href="/facts/Hugh_C._Williams/70ToIVyl">Williams</a> in 1980<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> to choose 
 
 
 
 p
 ≡
 3
 
 
 (
 mod
 
 8
 )
 
 
 
 {\displaystyle p\equiv 3{\pmod {8}}}
 
 and 
 
 
 
 q
 ≡
 7
 
 
 (
 mod
 
 8
 )
 
 
 
 {\displaystyle q\equiv 7{\pmod {8}}}
 
, and replace a square root 
 
 
 
 x
 
 
 {\displaystyle x}
 
 by a tweaked square root 
 
 
 
 (
 e
 ,
 f
 ,
 x
 )
 
 
 {\displaystyle (e,f,x)}
 
, with 
 
 
 
 e
 =
 ±
 1
 
 
 {\displaystyle e=\pm 1}
 
 and 
 
 
 
 f
 ∈
 {
 1
 ,
 2
 }
 
 
 {\displaystyle f\in \{1,2\}}
 
, so that a signature instead satisfies

e
        f
        
          x
          
            2
          
        
        ≡
        H
        (
        m
        ,
        u
        )
        
          
          (
          mod
          
          n
          )
        
        ,
      
    
    {\displaystyle efx^{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.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a><a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>

<h3>Others</h3>
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.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>
Variants without the hash function have been published in textbooks,<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a><a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> 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
 
 
 {\displaystyle x=2}
 
 can be forged by anyone as a valid signature on the message 
 
 
 
 m
 =
 4
 
 
 {\displaystyle m=4}
 
 if the signature verification equation is 
 
 
 
 
 x
 
 2
 
 
 ≡
 m
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle x^{2}\equiv m{\pmod {n}}}
 
 instead of 
 
 
 
 
 x
 
 2
 
 
 ≡
 H
 (
 m
 ,
 u
 )
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}
 
.
In the original paper,<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> the hash function 
 
 
 
 H
 (
 m
 ,
 u
 )
 
 
 {\displaystyle H(m,u)}
 
 was written with the notation 
 
 
 
 C
 (
 M
 U
 )
 
 
 {\displaystyle C(MU)}
 
, with C for compression, and using juxtaposition to denote concatenation of 
 
 
 
 M
 
 
 {\displaystyle M}
 
 and 
 
 
 
 U
 
 
 {\displaystyle U}
 
 as bit strings:

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

</blockquote>
This notation has led to some confusion among some authors later who ignored the 
 
 
 
 C
 
 
 {\displaystyle C}
 
 part and misunderstood 
 
 
 
 M
 U
 
 
 {\displaystyle MU}
 
 to mean multiplication, giving the misapprehension of a trivially broken signature scheme.<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://cr.yp.to/sigs.html">Rabin–Williams signatures at cr.yp.to</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Rabin, Michael O. (1978). "Digitalized Signatures". In DeMillo, Richard A.; Dobkin, David P.; Jones, Anita K.; Lipton, Richard J. (eds.). Foundations of Secure Computation. New York: Academic Press. pp. 155–168. ISBN 0-12-210350-5. <a href="0-12-210350-5" target="_blank">0-12-210350-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Rabin, Michael O. (January 1979). Digitalized Signatures and Public Key Functions as Intractable as Factorization (PDF) (Technical report). Cambridge, MA, United States: MIT Laboratory for Computer Science. TR-212. <a href="/wiki/Michael_O._Rabin" target="_blank">/wiki/Michael_O._Rabin</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bellare, Mihir; Rogaway, Phillip (May 1996). Maurer, Ueli (ed.). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8. <a href="978-3-540-61186-8" target="_blank">978-3-540-61186-8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bernstein, Daniel J. (January 31, 2008). RSA signatures and Rabin–Williams signatures: the state of the art (Report). (additional information at https://cr.yp.to/sigs.html) <a href="/wiki/Daniel_J._Bernstein" target="_blank">/wiki/Daniel_J._Bernstein</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Rabin, Michael O. (January 1979). Digitalized Signatures and Public Key Functions as Intractable as Factorization (PDF) (Technical report). Cambridge, MA, United States: MIT Laboratory for Computer Science. TR-212. <a href="/wiki/Michael_O._Rabin" target="_blank">/wiki/Michael_O._Rabin</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bellare, Mihir; Rogaway, Phillip (May 1996). Maurer, Ueli (ed.). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8. <a href="978-3-540-61186-8" target="_blank">978-3-540-61186-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Bernstein, Daniel J. (April 2008). Smart, Nigel (ed.). Proving tight security for Rabin–Williams signatures. Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science. Vol. 4965. Istanbul, Turkey: Springer. pp. 70–87. doi:10.1007/978-3-540-78967-3_5. ISBN 978-3-540-78966-6. <a href="978-3-540-78966-6" target="_blank">978-3-540-78966-6</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="0-7381-1956-3" target="_blank">0-7381-1956-3</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Rabin, Michael O. (January 1979). Digitalized Signatures and Public Key Functions as Intractable as Factorization (PDF) (Technical report). Cambridge, MA, United States: MIT Laboratory for Computer Science. TR-212. <a href="/wiki/Michael_O._Rabin" target="_blank">/wiki/Michael_O._Rabin</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Bernstein, Daniel J. (January 31, 2008). RSA signatures and Rabin–Williams signatures: the state of the art (Report). (additional information at https://cr.yp.to/sigs.html) <a href="/wiki/Daniel_J._Bernstein" target="_blank">/wiki/Daniel_J._Bernstein</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Bellare, Mihir; Rogaway, Phillip (May 1996). Maurer, Ueli (ed.). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8. <a href="978-3-540-61186-8" target="_blank">978-3-540-61186-8</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Bernstein, Daniel J. (April 2008). Smart, Nigel (ed.). Proving tight security for Rabin–Williams signatures. Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science. Vol. 4965. Istanbul, Turkey: Springer. pp. 70–87. doi:10.1007/978-3-540-78967-3_5. ISBN 978-3-540-78966-6. <a href="978-3-540-78966-6" target="_blank">978-3-540-78966-6</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Bellare, Mihir; Rogaway, Phillip (May 1996). Maurer, Ueli (ed.). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8. <a href="978-3-540-61186-8" target="_blank">978-3-540-61186-8</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Bellare, Mihir; Rogaway, Phillip (August 1998). Submission to IEEE P1393—PSS: Provably Secure Encoding Method for Digital Signatures (PDF) (Report). Archived from the original (PDF) on 2004-07-13. <a href="/wiki/Mihir_Bellare" target="_blank">/wiki/Mihir_Bellare</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Halevi, Shai; Krawczyk, Hugo (August 2006). Dwork, Cynthia (ed.). Strengthening Digital Signatures via Randomized Hashing (PDF). Advances in Cryptology – CRYPTO 2006. Lecture Notes in Computer Science. Vol. 4117. Santa Barbara, CA, United States: Springer. pp. 41–59. doi:10.1007/11818175_3. <a href="/wiki/Shai_Halevi" target="_blank">/wiki/Shai_Halevi</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Dang, Quynh (February 2009). Randomized Hashing for Digital Signatures (Report). NIST Special Publication. Vol. 800–106. United States Department of Commerce, National Institute for Standards and Technology. doi:10.6028/NIST.SP.800-106. <a href="https://csrc.nist.gov/publications/detail/sp/800-106/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-106/final</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Williams, Hugh C. "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. <a href="/wiki/Hugh_C._Williams" target="_blank">/wiki/Hugh_C._Williams</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Bellare, Mihir; Rogaway, Phillip (May 1996). Maurer, Ueli (ed.). The Exact Security of Digital Signatures—How to Sign with RSA and Rabin. Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-61186-8. <a href="978-3-540-61186-8" target="_blank">978-3-540-61186-8</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">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. <a href="0-7381-1956-3" target="_blank">0-7381-1956-3</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Bernstein, Daniel J. (January 31, 2008). RSA signatures and Rabin–Williams signatures: the state of the art (Report). (additional information at https://cr.yp.to/sigs.html) <a href="/wiki/Daniel_J._Bernstein" target="_blank">/wiki/Daniel_J._Bernstein</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Williams, Hugh C. "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. <a href="/wiki/Hugh_C._Williams" target="_blank">/wiki/Hugh_C._Williams</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Bernstein, Daniel J. (January 31, 2008). RSA signatures and Rabin–Williams signatures: the state of the art (Report). (additional information at https://cr.yp.to/sigs.html) <a href="/wiki/Daniel_J._Bernstein" target="_blank">/wiki/Daniel_J._Bernstein</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">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. <a href="0-7381-1956-3" target="_blank">0-7381-1956-3</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Bernstein, Daniel J. (January 31, 2008). RSA signatures and Rabin–Williams signatures: the state of the art (Report). (additional information at https://cr.yp.to/sigs.html) <a href="/wiki/Daniel_J._Bernstein" target="_blank">/wiki/Daniel_J._Bernstein</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). "§11.3.4: The Rabin public-key signature scheme". Handbook of Applied Cryptography (PDF). CRC Press. pp. 438–442. ISBN 0-8493-8523-7. <a href="0-8493-8523-7" target="_blank">0-8493-8523-7</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Galbraith, Steven D. (2012). "§24.2: The textbook Rabin cryptosystem". Mathematics of Public Key Cryptography. Cambridge University Press. pp. 491–494. ISBN 978-1-10701392-6. <a href="978-1-10701392-6" target="_blank">978-1-10701392-6</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Rabin, Michael O. (January 1979). Digitalized Signatures and Public Key Functions as Intractable as Factorization (PDF) (Technical report). Cambridge, MA, United States: MIT Laboratory for Computer Science. TR-212. <a href="/wiki/Michael_O._Rabin" target="_blank">/wiki/Michael_O._Rabin</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Elia, Michele; Schipani, David (2011). On the Rabin signature (PDF). Workshop on Computational Security. Centre de Recerca Matemàtica, Barcelona, Spain. <a href="https://www.math.uzh.ch/fileadmin/user/davide/publikation/SignatureRabin11.pdf" target="_blank">https://www.math.uzh.ch/fileadmin/user/davide/publikation/SignatureRabin11.pdf</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
</ol>

Rabin signature algorithm open-in-new

Rabin signature algorithm