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]

Reply via email to