uucp@ucdavis.UUCP (uucp) (06/05/87)
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.eduhanafee@cory.Berkeley.EDU.UUCP (06/06/87)
>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). [goes on to describe a proposed method for obtaining "good" keys] >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. I think your primary weakness is exactly the one you suggested; this reduces the number of possible keys. The RSA encryption scheme is well known, its strength lies in making decryption computationally infeasible. Given 60 unique bits, you have only 2**60 possible unique keys. I don't know how well this compares to just using DES, but I suspect it's not much better. A second, possibly more serious problem lies in the distribution of the "good" keys. Since you do a linear search from a "bad" key, looking for a "good" key, you will arrive at less than a one-to-one mapping of text to keys (e.g. if "aaa", "aab" and "aac" are bad, but "aad" is good, and you use a linear search, then all four text strings will yield the same key). You should *very* carefully study how rich your domain is in good keys before implementing your mapping. Finally, there is a well-known problem with any encryption based on user-entered keys. They tend to be anything but random, often with a strong correlation with the English/native language. System managers today have serious problems with people using words found in the dictionary as passwords, since they are found easily with brute force search. ----------------------------------------------------------------------------- My opinions are mine, and I take full responsibility. So there. (signed) Brian Hanafee UUCP: !ucbvax!cory!hanafee ARPAnet: hanafee@cory.Berkeley.EDU My opinions are mine, and I take full responsibility. So there. (signed) Brian Hanafee UUCP: !ucbvax!cory!hanafee ARPAnet: hanafee@cory.Berkeley.EDU
devine@vianet.UUCP (06/09/87)
In article <537@ucdavis.UUCP>, uucp@ucdavis.UUCP (uucp) writes: > 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). As I understand your proposal, the entire strength lies in the selection of a key by the user and in keeping the algorithm secret. It is unlikely that the algorithm can be kept secret very long in a hostile environment. So, the proposal seems to boil down to a sophisticated one-way password encryption. A brute force attack might guess some of the passwords. > 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. If you are using text, there will not be 6 random bits per char (on a CDC machine?). A reasonable guessing strategy would be to look at only certain ranges of characters (lower-case letters for instance). That yields a much lower range. A good paper that describes how to select primes for RSA's algorithm is by John Gordon of Cybermation Ltd in England entitled "Strong Primes are Easy to Find". He calculated a 76 decimal digit prime in about 20 minutes on a 1 MHz Apple II.
billc@prism.UUCP (06/11/87)
/* 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 */