[3394] in cryptography@c2.net mail archive
Re: Fwd: Re: r.e. quality of IDEA...
daemon@ATHENA.MIT.EDU (Rieks Joosten)
Tue Sep 29 13:42:27 1998
From: "Rieks Joosten" <r.joosten@pijnenburg.nl>
To: "Steven M. Bellovin" <smb@research.att.com>
Date: Tue, 29 Sep 1998 08:24:30 +0100
Reply-to: r.joosten@pijnenburg.nl
CC: "David G. Koontz" <koontz@ariolimax.com>, cryptography@c2.net
In-reply-to: <199809252241.SAA00475@smb.research.att.com>
> In message <199809252106.HAA11077@avalon.qualcomm.com>, Greg Rose
> writes:
> >"David G. Koontz" writes:
> >>A quick look at the source for IDEA shows that the key for IDEA doesn't
> >>require
> >>prescheduling.
> >
> >It is true that for encryption, there is relatively little benefit from
> >the precomputed key schedule. For decryption, though... this is not
> >entirely true. The decryption keys require the modular multiplication
> >inverses. This can be done by lookup in a 128K table on the fly, but
> >that's back to real estate. Or they can be computed on the fly, but that
> >requires the extended Euclidean algorithm. There are probably tradeoffs
> >in there between these approaches, but it might be worth caching the key
> >schedules.
> >
> >Of course you could just encrypt all the time, and never decrypt... :-)
There is no need to use the extended Euclidian algorithm for the
multiplicative inverse: since 2^16+1 is prime, you can use simple
modular exponentiation. In particular: let p be prime, and a' be
defined such that a*a' = 1 (mod p) for non-zero a (mod p), so a' is
the modular inverse of a (mod p). Then a' = a^(p-2) (mod p). Since
2^16+1 is prime, you can calculate a' = a^(2^16-1) = a^(0xFFFF) (mod
2^16+1). This seems nasty, but there's this little algorithm that
calculates a' using only 19 modular multiplications (in the below, '*'
denotes multiplication mod 2^16+1)
s := a ; save a^1 = a^(2^1-1)
r := s*s ;r = a^2
r := r*s ;r = a^3
s := r ; save a^3 = a^(2^2-1)
r := r*r ;r = a^6
r := r*r ;r = a^12
r := r*s ;r = a^15
s := r ; save a^15 = a^(2^4-1)
r := r*r ;r = a^30
r := r*r ;r = a^60
r := r*r ;r = a^120
r := r*r ;r = a^240
r := r*s ;r = a^255
s := r ; save a^255 = a^(2^8-1)
r := r*r ;r = a^510
r := r*r ;r = a^1020
r := r*r ;r = a^2040
r := r*r ;r = a^4080
r := r*r ;r = a^9160
r := r*r ;r = a^18320
r := r*r ;r = a^36640
r := r*r ;r = a^73280
r := r*s ;r = a^73535 = a^(2^16-1)
s := r
Note that in the hardware, you might already have a multiplier that
does the '*' operation.
Rieks
r.joosten@pijnenburg.nl
