Bill Frantz wrote: >If there is a digital signature algorithm which has the property that most >invalid signatures can be detected with a small amount of processing, then >I can force the attacker to start expending his CPU to present signatures >which will cause my server to expend it's CPU.
My 800MHz PIII can do about 2800 512-bit RSA verifies per second. Dan Bernstein has a signature algorithm where verification is significantly faster still [1], and his ideas could probably be used to quickly reject most invalid signatures with even better efficiency. One of the nicest ideas from his work is easy to describe. In plain RSA, s is a valid signature on m if H(m) = s^3 (mod n). Now suppose we ask the signer to also supply an integer k such that 0 <= s^3 - kn < n; clearly this can't hurt security, as k can be publicly computed from s. Then the recipient can efficiently verify the validity of the claimed signature (t,k) on m as follows: verify that 0 <= s^3 - kn < n; then secretly pick a random 31-bit prime p, compute t' = s^3 mod p, n' = n mod p, k' = k mod p, h' = H(m) mod p, and verify that t' - k'n' = h' (mod p). This requires a few reductions and multiplications modulo a 31-bit number, and thus is faster than verifying the RSA signature directly (the latter requires a few reductions and multiplications modulo a 512-bit number). Moreover, if the prime is chosen randomly, the probability that an adversary can forge a signature that passes this screening test is something like 2^-26 or so. In short, invalid signatures can be detected quickly with very high probability. [1] D. J. Bernstein. ``A secure public-key signature system with extremely fast verification.'' http://cr.yp.to/papers.html#sigs --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]