Nomen Nescio wrote: >[asks good questions about my re-telling of Dan Bernstein's signature trick]
Great questions! The explanation is that I botched the description of Bernstein's trick. Let me try again and see if I can get it right this time. 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. A reasonably fast way to check the validity of a claimed signature is to apply the hash, verify h = H(m), then compute s^3 mod n using modular arithmetic and check that s^3 = h (mod n). This requires a few multiplications and reductions modulo n. A faster way to verify the validity of a claimed signature is to secretly pick a random 31-bit prime p. We will verify that h = H(m) and s^3 - kn - h = 0 (mod p). Note that the latter can be tested quickly by computing s mod p, s^3 mod p, k mod p, n mod p, and h mod p, and then doing a few subtractions mod p. We can see that the second method is faster than the first method: it replaces a few operations modulo n by a few operations modulo p. Since p is much smaller than n, this is a win. Did I get it right this time? Is it clearer? If there are any errors above, I take full responsibility for them. The authoritative description of Bernstein's trick can be found in his paper (cited in my previous email). --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
