US patent 7774607, Ferguson, signature verification

• 1. One or more computer-readable media comprising computer-executable instructions for verifying a signature, the computer-executable instructions directed to steps comprising: receiving a signed message comprising message data and the signature, the signed message having been signed using a private key comprising a modulo value, the private key being paired with a public key comprising a public exponent and the modulo value; receiving a pre-computed value corresponding to a quotient of the signature raised by the public exponent then divided by the modulo value; and using the pre-computed value to verify the signature.
• 8. One or more computer-readable media comprising computer-executable instructions for aiding in the verification of a signature, the computer-executable instructions directed to steps comprising: transmitting a signed message comprising message data and the signature, the signed message having been signed using a private key comprising a modulo value, the private key being paired with a public key comprising a public exponent and the modulo value; generating a pre-computed value corresponding to a quotient of the signature raised by the public exponent then divided by the modulo value; and transmitting the pre-computed value.
• 14. A method of verifying a signature comprising: receiving a signed message comprising message data and the signature, the signed message having been signed using a private key comprising a modulo value, the private key being paired with a public key comprising a public exponent and the modulo value; receiving a pre-computed value corresponding to a quotient of the signature raised by the public exponent then divided by the modulo value; and using the pre-computed value to verify the signature.

Prior art:

• 1997.03.11, Bernstein, The world's fastest digital signature system: "Modification: Include (s^2 - h)/n in the signature. ... Gamblers may prefer to select one or two small random primes, then check s^2 = nk + h modulo those primes; the chance of a bad signature slipping through is very small."
• 2000.08.09, Bernstein, A secure public-key signature system with extremely fast verification: "In March 1997 on sci.crypt I suggested providing t = (s^2-fh)/pq as part of the signature. This makes verification much easier with no effect on security. The new signature equation s^2 = tn+fh is a ring equation; testing a ring equation by mapping it to a random quotient ring is a standard technique, as is proving a ring equation by mapping it to enough quotient rings." At another point: "A receiver can discard the extra information to save space, and regenerate the extra information later."
• 2000.08.18, Bernstein, Protecting communications against forgery (video also published by MSRI): "Modify signatures to save time: ... Verifier computes s^2-fh-tn modulo a secret 40-digit prime."
• 2000.10.20, Bernstein, Design and implementation of a public-key signature system (video also published by MSRI): "s^2 mod n = fA(r,m): The Rabin-Williams system. Unbroken. s^2 - tn = fA(r,m): The RWB system. Unbroken. ... Can compute s^2-tn-fh, check if result is 0. Faster: Reduce s^2-tn-fh modulo a secret prime l with 2^114<l<2^115, l mod 5 in {2,3}; check if result is 0. Chance <2^-100 of error for uniform random l."
• 2002.06.24, Wagner, Re: Shortcut digital signature verification failure: "A signature on message m is a tuple (h,s,k) such that s^3 = kn + h, h = H(m), and 0 <= h,s,k < n."
• 2003.11.08, Bernstein, More news from the Rabin-Williams front: "Signature: (e,f,r,s) such that s^2 = blah (mod pq). Expanded: (e,f,r,s,t) such that s^2-blah-pqt = 0. Fast randomized verification: Check ((s mod n)^2 - (blah mod n) - (pq mod n)(t mod n)) mod n = 0 for secret random 100-bit prime n."