Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!husc6!cca!mirror!prism!billc
From: billc@prism.UUCP
Newsgroups: sci.crypt
Subject: Re: generating RSA keys
Message-ID: <201000005@prism>
Date: Thu, 11-Jun-87 14:24:00 EDT
Article-I.D.: prism.201000005
Posted: Thu Jun 11 14:24:00 1987
Date-Received: Sat, 20-Jun-87 12:48:26 EDT
References: <537@ucdavis.UUCP>
Lines: 49
Nf-ID: #R:ucdavis.UUCP:-53700:prism:201000005:000:1767
Nf-From: prism.UUCP!billc    Jun 11 14:24:00 1987


/* Written  3:41 pm  Jun  5, 1987 by uucp@deneb.UUCP in prism:sci.crypt */
/* ---------- "generating RSA keys" ---------- */
I have been working on a RSA encryption program and have come across an
interesting problem.  There are several rules by which you must pick
a key to achieve good RSA encryption.  Given p and q, these are:

1... d must be relatively prime to phi(n).  In other words
		gcd (d, phi(n)) = 1

2... max(p,q) < d < n

3... inv(d, phi(n)) > log(n)   {base 2}

Where n=pq, phi(n)=(p-1)(q-1), d=user key, e=inv(d,phi(n)),
	gcd is greatest common divisor, and inv is modulo inverse


I have been trying to come up with a scheme to implement an algorithm
that would allow the user to pick any key (presumably text), and map it 
to a _good_ key (as defined above).

The only scheme that I have come up with so far is as follows:

	A. Get key text from user.
	B. Map to a number (one to one mapping). 
	C. Verify that the key meets above requirements.
	D. If key does not meet above requirements, increment the
		key by one, and goto C.
	   Else done.


I have been trying to find any weaknesses in this scheme (such as dramatically
reducing the number of possible keys, etc.).  While the scheme does reduce
the number of keys, it also will guarentee the generation of a good key.
My feeling is that if the key text that is gotten from the user is long
enough (say 10 characters, 6 bits per char -- around 60 unique bits
or from 1 to 1E19), then the results should be fairly good.

Does this sound like a reasonable scheme?  Also, does anyone know of any
existing schemes to implement good RSA key choice?


			Thanks!
			   Bruce Martin

Bruce K. Martin   ...!ucbvax!iris!martin
		  iris!martin@ucbvax.berkeley.edu
/* End of text from prism:sci.crypt */