cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-08-24 - Fast modular exponentiation

Header Data

From: Hal <hfinney@shell.portal.com>
To: cypherpunks@toad.com
Message Hash: 6a30f5c89adb8c4e1e70c845d334947e1f3dbde5dfd1a2418c261d5dec9150e7
Message ID: <199408241507.IAA15669@jobe.shell.portal.com>
Reply To: <199408240810.BAA27546@servo.qualcomm.com>
UTC Datetime: 1994-08-24 15:08:06 UTC
Raw Date: Wed, 24 Aug 94 08:08:06 PDT

Raw message

From: Hal <hfinney@shell.portal.com>
Date: Wed, 24 Aug 94 08:08:06 PDT
To: cypherpunks@toad.com
Subject: Fast modular exponentiation
In-Reply-To: <199408240810.BAA27546@servo.qualcomm.com>
Message-ID: <199408241507.IAA15669@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


Phil Karn <karn@qualcomm.com> writes:
>Now can we return to cryptography? How about a discussion of fast
>modular exponentiation algorithms, something we (or at least I) can
>put to more immediate and constructive use than nuclear bomb designs?

In the Crypto 93 proceedings, there is an article by Bosselaers, Govaerts,
and Vandewalle comparing the speed of three algorithms for modular reduction
which is the main time-consuming step in modular exponentiation.  They
compared the classical algorithm from Knuth, a modification to it by Barrett
which speeds up the estimate of the first digit of the quotient, and 
Montgomery multiplication (which is inherently modular).

Montgomery was the fastest for taking 1024 bit numbers modulo 512 bit
numbers, but not by a lot.  For exponentiation, though, where the reduction
happens a lot, Montgomery was fastest for all but the very smallest exponents.
512 bit exponents took  about 2.93 seconds for the classical algorithm,
2.85 seconds for the Barrett improvement, and 2.55 seconds for Montgomery.
The crossover point (below which Barrett is best) is exponents of about 32
bits.

So, Montgomery multiplication was best, but the percentage improvement is
not that large.

Sometimes, as I mentioned yesterday, you can restrict the size of the exponents
without losing security (as in DSS), but it depends on the algorithm.

Hal

Thread