Shortcut digital signature verification failure

[David Wagner]

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 majordomo at wasabisystems.com