IDEA vs DES

Now that I've got DES running about as fast as it can go on the 486, I
did a little analysis on IDEA. The algorithm is definitely more
straightforward to implement than DES, but not necessarily that much
faster. It uses three primitive operations, all on 16-bit quantities:
XOR, ADD and multiplication modulo 65537.  Each encryption involves 48
XORs, 34 adds and 34 multiplies, plus a few exchanges.

The multiplies are a problem. On the 486, a 16x16 integer multiply
takes from 13-26 clocks, depending on how many significant bits there
are in the multiplicand. Random data usually has 15-16 significant
bits, so this distribution is probably weighted more toward the 26
clock figure. So I count an optimistic total of 990 clocks per 64-bit
encryption, assuming plenty of registers (which I don't have), not
counting the modular reduction steps for each multiply, and ignoring
the memory references for the subkeys.

I figure my DES code is currently taking about 1300 clocks per
encryption. So IDEA won't be much faster, though it may be more
secure.

Anybody know the speed of the integer multiply instruction on the
various PowerPC chips? Along with modular exponentiation and vocoders,
which also do a lot of multiplies, it looks like fast multiplication
is becoming rather important in secure communications.

Phil

Excerpts from internet.cypherpunks: 7-Aug-94 IDEA vs DES by Phil
Karn@unix.ka9q.ampr 
> Anybody know the speed of the integer multiply instruction on the
> various PowerPC chips? Along with modular exponentiation and vocoders,
> which also do a lot of multiplies, it looks like fast multiplication
> is becoming rather important in secure communications.

PowerPC integer performance is rather impressive, i.e. faster than
Pentium by a bit. One craveat, tho, Apple says "No!" to programming in
assembly, and I doubt that IBM is all this happy about it either. My
guess is that MacOS is approaching the Unix "distribute source, 'cause
you're gonna have to do lots of re-compiles" type of thing. Just a
guess, though. Anyway, there is one assembly interpreter out for
PowerMacs, I don't know about the IBM PowerPCs, though.

Back to lurking,
jer

darklord@cmu.edu | "it's not a matter of rights  / it's just a matter of war
finger me for my |  don't have a reason to fight / they never had one before"
   Geek Code and |                                    -Ministry, "Hero"
  PGP public key | http://www.cs.cmu.edu:8001/afs/andrew.cmu.edu/usr25/jbde/

Jeremiah A Blatz writes:

> PowerPC integer performance is rather impressive, i.e. faster than
> Pentium by a bit. One craveat, tho, Apple says "No!" to programming in

Actually, the reverse is true. Pentium integer performance (as
measured in SPECints) is somewhat better than 601 PowerPC performance,
MHz for Mhz. Thus, a 66 MHz Pentium has slightly better integer
performance than a 66 MHz PowerPC. Not by much, but slightly. 

However, 90 MHz Pentium machines are now available in volume, even for
under $2000, while PowerPC is not yet at this level. (Experimental
Pentia running at 150 MHz have been shown..601s running at 120 MHz
have been shown...and both Intel and IBM/Motorola/Apple have newer
designs about to appear--the P6 and the 604.)

Floating point is another story, with the PowerPC 601 significantly
outperforming the Pentium. The exact numbers for all of these
benchmarks are published and republished constantly, so I won't do so
here.

I happen to use Macs exclusively, but I worked for Intel for 12 years
and still own their stock, so make of my comments what you will.

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

I'm specifically interested in *fixed point* multiply and divide
performance, since these operations appear to be crucial to IDEA and
high quality speech coding, not to mention multiple precision modular
exponentiation functions.

My 486 reference shows 13-42 clocks for a 32x32 multiply and 40 clocks
for a 64/32 divide.

I've heard that the PowerPC can do a multiply-accumulate (the basic
operation of a FIR digital filter) in one clock cycle, which qualifies
it as a DSP chip in my mind. If true, then it may become possible to
do high quality speech coding (essential for a secure phone) in
software on a widely available general purpose computer instead of
needing a high performance DSP subsystem that may be costly and/or
less readily available.

Here are some figures on my latest DES code. I'm placing it into the
public domain; how do I go about putting it on soda.berkeley.edu?

Measured execution speeds in crypts/sec:

11,488 (C version, 486DX-50, DOS, Borland C++ 3.1 -O2, 16-bit real mode)
39,185 (assembler version, same system)
62,814 (assembler version, 60 Mhz Pentium)
24,172 (C version, 486DX2-66, BSDI 1.1, GCC 1.42 -O, 32-bit prot mode)
64,185 (C version, 50 Mhz Sparc 10, GCC 2.5.8 -O)

The C version is essentially identical to Outerbridge's code in
Applied Cryptography, with a few extra tricks. The assembler version
is the same thing rewritten in assembler, with numerous optimizations
that were possible only in assembler.

Anybody have a tool for translating Intel 486 assembler code to the
Gnu assembler format?

--Phil

According to my references, the PowerPC 601 does an integer multiply
in 9 cycles (5 if the 2nd operand is 16 bits or less).  An integer
divide takes 36 cycles.  Adds, etc. take 1 cycle.

Floating-point multiplies take 1 cycle for single precision, 2 for double.
However, they are pipelined, so if you need to use the results of the
multiply on the next instruction, they will take 3 cycles.  Floating-point
adds take 1 cycle, again with the results available in 3.

There is a floating-point (but no integer) multiply-and-add instruction.
It has the same timing as the multiply.

Hal