🚀 go-pugleaf

In article <1992Oct13.864.271@ALMAC>, keith.willis@almac.co.uk writes:
> 
>         I have come across an implementation of RSA distributed by a
>         company in Wales, UK, which claims to perform RSA encryption
>         on the entire file, rather than just on a session key for a
>         conventional algorithm.  The program may be common knowledge,
>         but it is the first time I have come across it.  It is called
>         MCRYPT, and is distributed by a company called Digital
>         Crypto as shareware.
> 
>         What puzzles me is that encryption is very fast - less than 2
>         minutes for a 40k text file using a 250 digit key - but
>         decryption is _glacial_ - over 3 hours for the same file on
>         the same PC.

A common speedup is to use an extremely small encryption exponent, such
as 3.  I believe Knuth even proposed this at one point.  Raising something
to the third power is *VERY* much faster than raising to large powers.
Unfortunately, a corresponding decryption exponent will necessarily (it
seems) be very large, and the modular exponentiation will be correspondingly
hugely slower.

The big problem with a small exponent is if you use it to communicate with
more than "n" people, where "n" is the encryption exponent, but the details
have been lost as I read the paper on that quite some time ago.

Also, if it is known by an enemy that many of your plaintext blocks
happen to contain very small numbers (lots of leading zeros) then
cubing it isn't different than cubing mod m.  Then just take the integer
cube root, and you've decrypted that block.  Rare, though.  (In any case,
avoid blocks equal to zero).

Jim Kirkpatrick       jimkirk@corral.uwyo.edu