RSA-250 Factored

RSA-250 has been factored.

This computation was performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software.

The total computation time was roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz):

RSA-250 sieving: 2450 physical core-years
RSA-250 matrix: 250 physical core-years

The computation involved tens of thousands of machines worldwide, and was completed in a few months.

News article. On the factoring challenges.

Posted on April 8, 2020 at 6:37 AM • 15 Comments

Comments

CuriousApril 8, 2020 7:12 AM

This makes me wonder: If a certain popular computer operating system, was abused to have computers around the world perform some kind of number crunching task like maybe suitable for factoring large prime numbers, what kind of computational power would they have in theory?

anonApril 8, 2020 8:21 AM

@Curious

According to ark.intel, the reference CPU given here has 32 threads.

Folding@Home currently rates at 9,233,789 CPU cores (threads, for F@H).

That means F@H has 288,556 times more cores than the reference CPU.

I'll let others work out (presuming it was apples to apples):
(1) how much quicker F@H could have broken RSA-250
(2) what size RSA F@H could have broken in the same time

(F@H ALSO has 652,872 GPUs.)

MarkHApril 8, 2020 12:49 PM

It's a sign of the times, that this result wasn't posted here (and I didn't hear about it elsewhere) for a few weeks ... a lot of us have had other things on our minds.

As usual, first-class work by INRIA.

The slow progress on challenge numbers confirms my judgment, that the cost of factoring even a 1024 bit semiprime with randomly selected factors continues to be many millions of dollars.

If the key generation wasn't weakened in some way, and the asset under protection isn't worth quite a lot of money to somebody, then your RSA-1024 secrets remain safe from cryptanalysis1.
______________________________

I felt rather sad when I read the INRIA announcement, because I learned from their dedication that Peter Montgomery died just a few days before they completed the factorization2. He was a brilliant mathematician, who made vital contributions to computational number theory.

Every one of has made use of software implementing Montgomery multiplication3 ... whether or not we were aware of it.

Some of his work of special interest to readers here includes analysis of certain side-channel attacks, and an algorithm to frustrate side-channel leakage.
______________________________

1 I did learn along the way that for roughly the price of a new car, you can now buy an off-the-shelf Hewlett Packard machine which (if I understand correctly) might be capable of performing the last step, which requires several terabytes of RAM. However, ascertaining whether such machines would really be up to a 1024-bit semiprime factorization is beyond my present knowledge.

2 Montgomery played an important role in devising an algorithm which optimizes a gigantic matrix operation needed for factoring.

3 Years ago, when I realized that I needed to learn this "Montgomery multiplication" thing, I was able to download a facsimile of the first page of the paper in which he presented his work (the full paper was available only for purchase). I studied that page while riding somewhere on a train or plane; his presentation was so clear and succinct, that I was able from that fragment to make sense of what it was all about. For me, Montgomery multiplication remains one of those jewel-like innovations which is wonderful in its simplicity, and at the same time marvelous in its ingenuity.

Who?April 8, 2020 1:57 PM

Don't know a lot about the CADO-NFS open source project, but it looks like something that could be implemented on CUDA architectures—a simple task, repeated over and over on a huge input space.

If there is such a large computing infrastructure like the one run by Folding@Home to study proteins, or SETI@Home for the case, why a government will not have something comparable to violate our constitutional right to privacy?

CuriousApril 8, 2020 3:24 PM

@La Abeja

Afaik, there are no stored solutions for the factoring challenge (that was closed down, but I guess exist as some historical thing).

La AbejaApril 8, 2020 3:32 PM

@MarkH

cost of factoring even a 1024 bit semiprime with randomly selected factors continues to be many millions of dollars.

It's comparable to a murder-for-hire job. You've got to pick the pocket of a high-value target, steal his thumb drive, secretly record video of him entering his passphrase, etc., all without being offed by the CIA or Secret Service or private bodyguard security, depending on who he is.

I'm not buying that "factoring" bull$hit for one minute.

MarkHApril 8, 2020 4:03 PM

@La Abeja, curious:

"I don't believe it ..."

I try to anchor my comments in facts and (hopefully) valid reasoning about those facts. That I believe or don't believe something is a purely personal conclusion; since I'm not a recognized expert in any relevant field, why should anybody care what I do or don't believe?

The same with "credible" or "not credible", which are mealy-mouthed ways to say "I personally trust" or "I personally don't trust" some source of information ... rubbish!

If I have factual data on such a question, I'm pleased to write about it here.

Mr (or Ms) Bee: I don't know what you're talking about. Do you?
______________________________

1. When RSA Labs put up the challenge numbers, they explained the process by which they were generated. This was extraordinarily thorough-going, probably because substantial money prizes were connected to some of these numbers, and they wished to minimize any suspicion of prizes obtained by cheating.

As I recall, the process included isolation of the computers on which the semiprimes were made, and physical destruction of their hard drives after the moduli were "read out".

2. The INRIA results are, to the best of my knowledge, consistent with the "open literature" on GNFS factoring. The small population of experts who specialize in this stuff are always working on improvements to their factoring software.

GNFS is really complicated. The CADO-NFS package currently has about 440,000 source lines of code. To my limited understanding, most of the improvements are in some continuum between the fundamental algorithms and the mechanisms by which the software realizes those algorithms.

They've made remarkable progress, cutting running time by (at least approximately) constant factors of several, which will not be surprising to anyone who studies complexity theory in relation to such massive computations.

The extent to which they've published papers to document all of these improvements, I don't know. However, the entire source code is freely available to anyone who cares to look.

In fact, if you're interested, I believe you could install CADO-NFS on a small network of desktop computers, and try it yourself with smaller semiprimes of varying sizes. By plotting your results, and comparing them to the predicted running time formula, you could make your own informed judgment of how many core-years would be needed for semiprimes in the neighborhood of 800 bits.

La AbejaApril 8, 2020 4:55 PM

@MarkH

substantial money prizes were connected to some of these numbers,

That's a strong incentive.

the process included isolation of the computers on which the semiprimes were made, and physical destruction of their hard drives after the moduli were "read out".

And City Hall incumbents progressively stuff the ballot box after excluding political dissidents from the libraries, schools, and churches where elections are held.

The small population of experts who specialize in this stuff

This is not only a fraternization problem, but a small collection of high-value pockets to be picked unawares.

anon12April 9, 2020 4:52 PM

Does this mean that any key using RSA-250 (I know, weird choice and not in use) is crackable?

anon12April 9, 2020 4:59 PM

@anon12 (myself)

nvm, dummy here, realized that the RSA-250 number is a static number and anyone generated an RSA key would choose their own factors.

MarkHApril 10, 2020 4:03 AM

@anon12:

It's not such a dumb question after all. As you wrote, anyone applying RSA (in any sensible manner) would use a custom key.

Even so, what has been demonstrated is that up to roughly 850 bits, RSA is now practical to break in not many weeks, at a cost on the order of a few thousand dollars.

For ordinary applications, almost every implementation uses one of a few standard modulus bit-lengths. However, RSA is flexible enough that it's easy to choose a custom length based on application constraints. One example would be microcontrollers with very limited memory capacity.

The way computation sizes grow for the best available RSA modulus factoring algorithm, the General Number Field Sieve, factoring a 1024 bit modulus remains very expensive ... even though 1024 isn't dramatically bigger than 850.

There is still no public report that anyone has ever factored a (properly generated) 1024 bit modulus. It's sure to happen, but I wouldn't be surprised if we wait a decade, or even longer. However, people who follow security recommendations switched to RSA modulus sizes greater than 1024 bits at least 15 years ago.

QApril 11, 2020 1:53 AM

You couldn't have used RSA250 for your encryption anyway, because previously you didn't know the factors. And now that someone has factored it, you still can't use it because the factors are public and it wouldn't be secure.

And if someone had "broke in and obtained the private RSA key somehow" then why only the factors for RSA250? Wouldn't someone get much more coverage by claiming to have broken RSA2048? Since they would have already broken in, just steal the RSA2048 factors and now you can be famous. All you'll need is a cover story to pretend you invented some amazing new algorithm to crack 2048 bit semi-primes. I'm sure you could bullshit the entire mathematics community with some fancy looking made-up formulas. Go for it!

tom bApril 13, 2020 6:54 AM

@Curious,

GIMPS! Great internet Bessemer Prime Search was a distributed computing platform in the early 2000s that specialized in factoring. i was participating in the project when they discovered the two largest known primes at the time. but i moved onto F@H the help people and mining bitcoin to support the crypto geeks.

the only thing worth reading in my post: its beyond me why China isn't making it manditory to use it's citizens idle cpu/gpu cycles to decrypt sensitive documents. i remember reading SoS blog back when cracking 56 bit des was challenging so national security secrets were thought to be safe.

1&1~=UmmApril 13, 2020 12:52 PM

@tom b:

"its beyond me why China isn't making it manditory to use it's citizens idle cpu/gpu cycles to decrypt sensitive documents."

It's simple, they can not afford the electricity bill.

Have a look at how much electricity is used in BitCoin mining. Even usuing speciallised hogh efficiency hardware designs fairly usless for any other computation the usage of electricity is more than a number of European nations.

AdnaApril 14, 2020 9:29 AM

RSA-250 is 829 bits number. Something that low was never used in RSA. We stopped using even 1024 bit RSA a decade ago. Everyone right now is using at least 2048 bit RSA. It's funny they said 1024 bit number would be factored by like 10 years ago. It hasn't been factored yet 10 years later. It would be more interesting if someone actually factors a 1024 bit number which was RSA-309. I am not sure it will happen in the next 10 years. Computer power isn't progressing as rapidly as people thought they would. These predictions are lagging way behind, by 10 or 20 years. That gap would even get wider. Even quantum computers are mostly pipe dreams.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Sidebar photo of Bruce Schneier by Joe MacInnis.