[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: PGP's e exponent too small?
Mike Ingle <[email protected]> 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."
[email protected] 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.