The world's fastest digital signature system

[D. J. Bernstein]

Consider a Rabin-Williams-style digital signature system. The public key
is a number n; s is a signature of h if n divides s^2 - h.

The best way to check divisibility of s^2 - h by n, as far as I know, is
to divide s^2 - h by n 2-adically. My current implementation uses 126370
Pentium cycles for 2048-bit numbers. I think this can be reduced down to
about 100000 cycles.

Modification: Include (s^2 - h)/n in the signature. Now a signature is a
pair (s,k) within reasonable bounds such that s^2 = nk + h.

Now there is a much faster way to check signatures: select m_1, m_2, ...
with least common multiple larger than |s^2 - nk - h|, and check whether
s^2 - nk - h is divisible by each m_i. My third implementation uses some
moduli of the form 2^32k - d, with k and d small, plus 0-adic and 2-adic
tests, to verify s^2 = nk + h in just 62056 Pentium cycles.

This is more than twice as fast as my RW implementation, more than three
times faster than anyone else's RW, more than six times faster than RSA,
and more than fifteen times faster than what's sold by RSADSI. I suspect
that careful modulus choices will save another factor of 3. The possible
hardware speedups are even more dramatic.

Gamblers may prefer to select one or two small random primes, then check
s^2 = nk + h modulo those primes; the chance of a bad signature slipping
through is very small. This is useful for non-gamblers as a quick way to
weed out most bad signatures without wasting computer time.

I've set up a mailing list to discuss the implementation of this system.
To subscribe, send a message to djb-sigs-...@koobera.math.uic.edu.

---Dan

[Michael Sabin]

>news:1997Mar1104...@koobera.math.uic.edu

Another approach is to verify the Rabin-Williams (RW) signature using
Montgomery multiplication. To make this fast, we move the Montgomery
precomputation from the signature verification to the signature
generation, as follows.

The signature is usually generated by finding s that satsifies s^2 = h
mod n. Instead, we'll redefine it as s that satifies s^2 = hR mod n,
where R = 2^B, and B is the number of bits in n (e.g., 2048). Then the
signature can be verified in two steps:

i) Y = s^2 (multiprecision multiplication, result has 2B bits)
ii) h' = Y/R mod n (Montgomery reduction, result has B bits)

The signature is verified if h' = h.

Step (i) is standard multiprecision multiplication. Step (ii) is
Montgomery reduction; its implementation is actually very similar to
step (i) and requires nearly identical effort. Thus signature
verification effort is twice the effort to compute a multiprecision
multiply (ie., B-bit * B-bit = 2B-bit).

Computing the signature as s^2 = hR mod n eliminates the need for the
verification to perform Montgomery precomputation steps, such as sR mod
n, which implicitly involve division. This saves a lot of time.

In fairness, the same trick can be done with RSA, i.e., the signature
can be computed to satisfy S^e = hR mod n, where e is the public
exponent. Then the RW verification is faster than RSA according to the
bit pattern of e. For the typical cases of e = 65537 and 3, RW is
faster by a factor of 17 and 2, respectively.

Montgomery reduction also requires precomputing v = 1/n mod W, where W =
2^b, and b is the number of bits in a word that is used to carry out the
multiprecision multiplication. Computing v is very fast, and I believe
it is negligible compared to either step (i) or (ii). If you like, v
can be included in the signature, with the verification checking that
v*n mod W = 1; this is a single-precision multiply step, definitely
negligible compared to (i) or (ii).

I have assumed the modulus n has no particular structure. If you allow
a structured modulus, step (ii) can be made negligible compared to step
(i). I think this is usually frowned upon, however -- it is considered
a better idea to pick the factors of n randomly rather than with special
structure.

mike

[D. J. Bernstein]

Michael Sabin <mike....@worldnet.att.net> wrote:
> Another approach is to verify the Rabin-Williams (RW) signature using
> Montgomery multiplication.

Well, I already mentioned a 2-adic divisibility test. There's no
advantage to the extra signing complexity of dividing by R. A 2-adic
test is indeed faster than the usual approach---compare my 126370 cycles
to the ~180000 cycles that most Rabin-Williams implementations take.

However, adding explicit quotients provides at least another 2x speedup.

Send a message to djb-sigs-...@koobera.math.uic.edu to join the
mailing list for further discussion.

---Dan
Let your users manage their own mailing lists. http://pobox.com/~djb/qmail.html