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