Opterons used to solve RSA math problem

Sieving was done on 80 2.2-GHz Opteron CPUs and took 3 months. The
matrix step was performed on a cluster of 80 2.2-GHz Opterons connected
via a Gigabit network and took about 1.5 months.

http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

EdG wrote:
> Sieving was done on 80 2.2-GHz Opteron CPUs and took 3 months. The
> matrix step was performed on a cluster of 80 2.2-GHz Opterons connected
> via a Gigabit network and took about 1.5 months.
>
> http://mathworld.wolfram.com/news/2005-11-08/rsa-640/
>

So does this mean that now RSA is cracked? And if it is cracked, does it
mean that if someone wants to crack somebody's RSA messages, that it's
still going to take them 4.5 months, or now that the initial 4.5 month
step is taken, this will help people crack RSA messages in less time?

Yousuf Khan

Yousuf Khan <bbbl67@ezrs.com> writes:
>EdG wrote:
>> Sieving was done on 80 2.2-GHz Opteron CPUs and took 3 months. The
>> matrix step was performed on a cluster of 80 2.2-GHz Opterons connected
>> via a Gigabit network and took about 1.5 months.
>>
>> http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

>So does this mean that now RSA is cracked? And if it is cracked, does it
>mean that if someone wants to crack somebody's RSA messages, that it's
>still going to take them 4.5 months, or now that the initial 4.5 month
>step is taken, this will help people crack RSA messages in less time?

It has been known by everyone from the very beginning that being
able to factor the composite key would allow anyone to decode any
RSA message that was encrypted with that key. This is no surprise
to anyone who has read a bit of cryptography. And the factoring
software used is also widely available and understood.

As the speed of processors goes up, as the amount of available
memory goes up and as the number of processors someone is willing
to dedicate to the task goes up then the time needed to factor such
a key goes down.

This is partly why the recommended RSA key length has been increasing
each year, to keep the amount of work needed to factor a key
sufficiently challenging.

So what this means is that if you were to use about the same resources
and you had messages that someone had encrypted with a key of this
size then somewhere roughly like this amount of time might be needed
to find the factor and thus be able to decrypt the messages, factoring
is not something that always takes exactly the same amount of time.

If they or someone else uses a different key of the same length
then you start over and spend again roughly this amount of time.

Now, estimate the cost of a little grid of 80 (fast) pcs. Compare
that to the budget of your potential adversary, which in one case
is said to be beyond ten billion dollars a year and which is estimated
to have the most compute power in any one organization on the planet.
Plus they may or may not have found some methods that are faster
in their decades of research by an army of very very bright
individuals. Roughly guess how long it would take them if they
decided they had to factor your key.

Everything I have written here has been written by other folks in
the past, none of this is a secret or even a little bit surprising.

In article <VOCdndSpyfo9IureRVn-vg@rogers.com>,
Yousuf Khan <bbbl67@ezrs.com> wrote:
>EdG wrote:
>> Sieving was done on 80 2.2-GHz Opteron CPUs and took 3 months. The
>> matrix step was performed on a cluster of 80 2.2-GHz Opterons connected
>> via a Gigabit network and took about 1.5 months.
>> http://mathworld.wolfram.com/news/2005-11-08/rsa-640/
>So does this mean that now RSA is cracked? And if it is cracked, does it
>mean that if someone wants to crack somebody's RSA messages, that it's
>still going to take them 4.5 months, or now that the initial 4.5 month
>step is taken, this will help people crack RSA messages in less time?

This just means that one specific RSA key has been cracked. It doesn't
provide any help towards cracking any other RSA key. It doesn't represent
much, if anything, in the way of "new discovery"; it is just applying well
known techniques and throwing a certain amount of hardware at it.

Someone with similar resources could presumably crack any other 640 bit
key in about the same amount of time; to a fairly large degree adding
resources reduces the time and vice versa.

So, if you need to keep something secret for more than a couple weeks
against someone willing to spend low millions on figuring it out, then you
should be using keys longer than 640 bits. Suggestion on appropriate
keylengths can be found at:
http://www.keylength.com/

For more details about the RSA Factoring Challenge see:
http://www.rsasecurity.com/rsalabs/...nges/factoring/
The table at the end shows how small increases in keysize result in
enormous increases in amount of compute power needed. There is still
$600,000 up for grabs if you do crack RSA (or at least discover a vastly
less resource intensive way to factor numbers).
--
Jim Prescott - Computing and Networking Group jgp@seas.rochester.edu
School of Engineering and Applied Sciences, University of Rochester, NY