Re: Another Test on RSA Keys

Dan Bailey (dan@milliways.org)
Tue, 19 May 1998 19:49:14 -0400 (EDT)

• Next message: David Jablon: "re: question on campus computer security"
• Previous message: Brad Kemp: "re: question on campus computer security"

RSA keys may be explicitly constructed soas to avoid the "classical"
methods such as p-1. To do this, you must ensure that p +/- 1 and q +/- 1
both have "large" prime factors. Large here is a tunable parameter which
you may set to your level of risk tolerance: 2^80-2^100 is probably a good
choice. If you choose 2^100 as your factor size, the p-1 methods won't
succeed under standard assumptions. If you are concerned about these
attacks, you may build your keys to thwart them. As many point out,
however, the probability of an attacker succeeding in this way is
extremely remote.
                                Cheers
                                Dan

On Tue, 19 May 1998, Anonymous wrote:

> Algorithms like p-1 are not that bad if you are willing to accept that
> they have only a statistical chance of succeeding on a given key.
>
> Given a bunch of 512 bit RSA keys, we want to try to factor them using
> p-1. p-1 takes a threshold T, and will succeed if the largest prime
> factor of p-1 (where p is one of the factors of the 512 bit key) is
> less than T. The amount of work to find the factor is proportional to
> T.
>
> The fraction of numbers of bit length L whose largest prime factor is
> fewer than F bits is approximately u^(-u), where u = (L/F). For example,
> with L=256 and F=64, the fraction is one in 2^8. Applying the p-1
> algorithm with a threshold of 2^64 would break about one key in 256.
>
> The total amount of work for p-1 is proportional to the threshold, so we
> can produce the following table:
>
>
> T Number of keys to be tried Total work factor
> before finding one with a factor
> smooth at this level
>
> 2^64 2^8 2^72
> 2^40 2^17 2^57
> 2^32 2^24 2^56
> 2^24 2^36 2^60
> 2^20 2^47 2^67
> 2^16 2^64 2^80
>
> So the work to break a 512 key using p-1 is about 2^56. This involves
> trying about 2^24 keys with a threshold of 2^32. You don't know which
> one you will break but statistically you are likely to succeed.
>
> How would this compare with the effort to break a key of this size
> using more modern algorithms? The p-1 attack would appear comparable
> to the DES brute force search. This was larger than the RSA-129
> factoring effort. If we scale up RSA-129 to a 512 bit (~154 digit)
> key, but also take into consideration improvements in algorithms,
> perhaps it would be reasonable to suppose that the two efforts would
> be of similar orders of magnitude.
>
> So p-1 is close to competitive already in a statistical sense, and if
> there are improvements possible then it could in fact be a significant
> threat.
>
>
>

• Next message: David Jablon: "re: question on campus computer security"
• Previous message: Brad Kemp: "re: question on campus computer security"