[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
rc5 perf and rotates
Bill Sommerfeld <sommerfeld@apollo.hp.com> writes
>> So on the "variable shifts are efficient" front:
>>
>> yes: HP, IBM, DEC, Intel
>> no: Sun, SGI..
I would label your lists "yes" and "maybe". If the SPARC and MIPS
implementations use barrel shifters, I still claim its only a couple extra
cycles that might even be buried.
...
>> Of course, if the algorithm isn't secure, who cares how fast it is..
Right.
Who cares if a rotate is fast in an absolute sense? - the question is how
fast is the operation versus the operations needed for its cryptanalytic
inverse, i.e. its one-way-ness, compared to the alternative. Presumably the
crypto paper cited is well reasoned, I'll look it up.
If so then they do not depend on the claim that modern processors are
slow to rotate in an absolute cycle count sense, which is the claim I dispute.
I will need some convincing that algorithms incorporating rotates are inferior
in cryptographic efficiency to those excluding them. Rotates would seem to
be the best way of achieving information diffusion between bit positions (sub
modulo 8) without loss of information. Averaging over all possible shift counts,
shifts only move half as much information between bit positions as rotates. The
other ALU operations alone are much slower to diffuse information between bit
positions (other than adjacent ones).
>>
>> - Bill
Nice analysis.
...
>> *I was under the impression that the pentium had a barrel shifter,
>> though the 486 didn't, but I may be wrong...
You are right, I was mistaken, good catch. Although the RCL/RCR (rotate through
carry) variable count instructions take 7-27 clocks, the ROL/ROR variable count
instructions take a constant 4. Which only reinforces our point.
regards,
Oscar Strohacker
Advisory Engineer/Scientist
Data Compression Systems Architecture
IBM Microelectronics Division
11400 Burnet Road
Austin Texas 78758
o (512) 838-4077 f (512) 838-7004 Internet: stroh @ vnet.ibm.com
Follow-Ups: