Mike Ingle <MIKEINGLE@delphi.com> wrote:

Is the e exponent in PGP too small? It's usually 17 decimal.

Applied Cryptography pp. 287-288 says:

"Low Exponent Attack Against RSA

Another suggestion to 'improve' RSA is to use low values for e, the public key. This makes encryption fast and easy to perform. Unfortunately, it is also insecure. Hastad demonstrated a successful attack against RSA with a low encryption key [417]. Another attack by Michael Wiener will recover e, when e is up to one quarter the size of n [878]. A low decryption key, d, is just as serious a problem. Moral: Choose large values for e and d."

smb@research.att.com wrote in reply:

There was some discussion on this on sci.crypt. Briefly, the folks from RSA don't agree that it's a problem in practice. If you always include some random padding in the message, you're safe, if I remember what Kaliski posted.

Not true. If the RSA folks really believe that, they are kidding themselves. I don't see what adding padding will do to provent solving for the key (although it is a good idea for other reasons). Here's why you shouldn't use low powers of d: Remember that d and e are factors of (p-1)(q-1)+1. Doing a little math, we can rewrite that as de=pq-p-q+2. Unless p or q is very small, (which is unlikely because a small factor is easy to find, which would weaken the key), the product (p-1)(q-1)+1 is going to be somewhere near pq-2*SQRT(pq). (Actually, it will always be greater than pq-2*SQRT(pq)+2. SQRT=SquareRoot) By first trying obvious, small factors of pq, it would be possible to establish a lower bounds on (p-1)(q-1)+1. Consider the following example using small numbers: pq=161 Now, suppose you have a public key exponent 7. You try a few factors say, 2 and 3 on 161, which don't factor it. You now know that p>3 and q>3. Therefore, the smallest value pq could be would be pq-3-pq/3+2, which is 161-3-53.6+2=106.4 The square root of 161 is ~12.7. Therefore the upper limit of (p-1)(q-1)+1=pq-2(12.7)+2=161-25.4+2=137.6 Since we are only dealing with whole numbers, we have 107<de<137 since we know e is 7, we have 107<7d<137 -> 15<d<20 Then try the four possible values of d (16,17,18,19) and break the code: d=19 If d (the secret key) is small, (suppose e was 19 and d was 7) it makes things even easier. Consider 107<19d<137 -> 5.6<d<7.2 -> d=6 or d=7 Only two possibilities! This attack can be used on large numbers too. Suppose pq=10^50 (approximately). Then suppose you try dividing with the first billion (10^9) numbers and are not able to find a factor of pq. You then know that p>10^9 and q>10^9. Therefore (p-1)(q-1)+1 lower bound is 10^50-10^9-10^41+2, and the upper bound is 10^50-2*10^25+2. Although that is still a lot of possibilities, it does eliminates 99.9999999% of possibilities for d. If d is small, it would be a relatively quick search. If e was greater than 10^48, there would be fewer than 100 possibilities for d. This attack can be avoided. Consider again the previous example: p=7 q=23 pq=161 de=(p-1)(q-1)+1=133 d=19 e=7 If for any x, x mod pq = x^(de) mod pq then, by substitution, we have: x^(de) mod pq = x^(2de) mod pq therefore, x^(2de) mod pq = x^(3de) mod pq combining this, we have: x mod pq = x^(de) mod pq = x^(2de) mod pq = x^(3de) mod pq = x^(4de) mod pq ... and so on. Taking 2(p-1)(q-1) where p=7, q=23 gives 265. That factors into 53*5. We have another keypair in additon to the 7,19 already found. Continuing on, we find many more keypairs: (7-1)(23-1)+1=133=7*19 2(7-1)(23-1)+1=265=53*5 3(7-1)(23-1)+1=397 (prime) 4(7-1)(23-1)+1=529=23*23 5(7-1)(23-1)+1=661 (prime) 6(7-1)(23-1)+1=793=61*13 7(7-1)(23-1)+1=925=25*37 8(7-1)(23-1)+1=1057=151*7 (duplicate of 19*7; 19+133=151) 9(7-1)(23-1)+1=1189=41*29 10(7-1)(23-1)+1=1321 (prime) 11(7-1)(23-1)+1=1453 (prime) 12(7-1)(23-1)+1=1585=317*5 (duplicate of 53*5) 13(7-1)(23-1)+1=1717=101*17 14(7-1)(23-1)+1=1849=43*43 15(7-1)(23-1)+1=1981=283*7 (duplicate of 19*7) 16(7-1)(23-1)+1=2113 (prime) 17(7-1)(23-1)+1=2245=449*5 (duplicate of 53*5) 18(7-1)(23-1)+1=2377 (prime) 19(7-1)(23-1)+1=2509=13*193 (duplicate of 61*13) 20(7-1)(23-1)+1=2641=139*19 (duplicate of 7*19) 21(7-1)(23-1)+1=2773=47*59 22(7-1)(23-1)+1=2905=35*83 23(7-1)(23-1)+1=3037 (prime) 24(7-1)(23-1)+1=3169 (prime) 25(7-1)(23-1)+1=3301 (prime) Some are duplicates, and some are primes, but we have found 8 key pairs: 7*19, 53*5, 61*13, 25*37, 41*29, 101*17, 47*59, and 35*83. We also found two self-reversing secret keys, 23 and 43. If you continue this on, you will find keypairs containing every prime number that is not a factor of (p-1)(q-1). By using this method, you can easily find a keypair with large enough numbers to defeat guessing techniques. For example, 47*59 and 35*83 might be good choices. Furthermore, d*e will not be simply (p-1)(q-1)+1, which defeats the method of guessing the range of values described earlier. Remember: In the RSA PK system, key generation is everything.