Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site allegra.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!don
From: don@allegra.UUCP (Don Mitchell)
Newsgroups: net.crypt
Subject: Is RSA useful?
Message-ID: <4820@allegra.UUCP>
Date: Fri, 26-Jul-85 01:10:08 EDT
Article-I.D.: allegra.4820
Posted: Fri Jul 26 01:10:08 1985
Date-Received: Sat, 27-Jul-85 02:49:04 EDT
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 25

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.