[3396] in cryptography@c2.net mail archive
Re: Fwd: Re: r.e. quality of IDEA...
daemon@ATHENA.MIT.EDU (David G. Koontz)
Tue Sep 29 14:30:13 1998
Date: Mon, 28 Sep 1998 13:26:48 -0700
From: "David G. Koontz" <koontz@ariolimax.com>
To: cryptography@c2.net
Steven M. Bellovin wrote:
>
> 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.
I think you can do the reciprocal mod 2^^16 +1 in 6 - 8 K gates. You'd
have 4 copies along with the 4 multipliers which might be slightly
larger. These are four vanilla 16 x 16 multipliers with following 16
bit
ALUs.
A one clock per round implementation of Idea looks to be around 100K
gates,
a far cry from the 3K gates for DES. The multiplication modulo 2^^16 +
1
compromises the clock rate somewhat, too. The reciprocal look up can
be hidden by pipelining the key schedule.
