Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:17:29 ADT
Anonymous (nobody@replay.com)
Tue, 19 May 1998 21:25:08 +0200 (MET DST)
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.
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:17:29 ADT