Re: PGP's e exponent too small?

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."

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.

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.