Shortcut digital signature verification failure

[Nomen Nescio]

David Wagner describes a trick from Dan Bernstein to speed up
RSA signature verification with e = 3:

> 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

So the signer supplies s and k.  And our first step is to verify that
0 <= s^3 - kn < n.  But given that we've computed S = s^3 - kn and it
is in this range, isn't it the case that S = s^3 mod n?  And so we can
test test that H(m) = S = s^3 mod n and that verifies the signature
directly.

> 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).

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com