[net.crypt] Is RSA useful?

don@allegra.UUCP (Don Mitchell) (07/26/85)

I am not too worried about RSA patents.  Have you tried coding it?  We
are talking SLOW.  The BYTE article was a joke because the guy was
using a modulus small enough to factor in a second.  For a 512 bit
block size (about right for security) using the UNIX libmp package,
minutes are required [to do one block].  I got it down to about 10
seconds with some bizarre algorithms for multiplication and division.
That is still ridiculous.  Of course, special hardware has been
designed to do it faster (altho I have read reports of RSA hardware
that is slower than my software!).

Anyway, if you can do A**B mod C fast, what it is really good for is
key exchange.  I wonder if that is patented too?

The algorithm is:

	N is a publicly known number

	Alice tells Bob N**A mod C  (A is secret)

	Bob tells Alice N**B mod C  (B is secret)

	Bob doesn't know A, but he can compute (N**A)**B mod C and
	likewise, Alice computes (N**B)**A mod C.  Now they both have a
	common key that no one can compute just from seeing the
	messages, N**A and N**B.

loyola@gargoyle.UUCP (Loyola Math Dept) (07/27/85)

In response to the recently posted article which questioned the usefulness
of the RSA Public-Key Cryptosystem because of its inherent slowness, I offer
the following benchmarks:

				             modulus (decimal digits)
		function	        116              77             39

key generation (average time		6 mins.		4 mins.		1 min.
   required to find a pair of primes)
encryption (per block)		      2.3 secs.       .88 secs.       .28 secs
decryption (per block)		      22  secs.         9 secs.       4.5 secs

Theses timings were obtained on an IBM PC (4.77 MHz 8088) with all arithmetic
routines written in assembly language.  Each function runs approximately 3-4
times faster on an IBM AT.  (Encryption uses 211 as the exponent except in 
the unlikely event that 211 divides the Euler totient, in which case
successively larger primes are considered.)

While the smallest version (39 digits) is unacceptable for security reasons,
the middle version could only be broken by the folks at Sandia (or the NSA,
I presume).  The largest version seems quite secure at the present time.

While admittedly not spectacular, these times make it quite feasible to use
RSA to apply digital signatures to short messages, such as electronic funds
transfer orders, or to encrypt DES keys in a secure key distribution scheme.

Comments?  (I'm carefully avoiding the patent issue!)

					Michael J. Markowitz
					ihnp4!gargoyle!cantor!abel!mjm