The RSA numbers are a set of numbers that are each the product of two large primes generated by RSA in 1991 as part of the RSA Factoring Challenge, to foster research in computational number theory and the practical challenges in factoring large numbers. While the Challenge was declared inactive in 2007 and RSA will no longer award prize money for it, researchers continue to try their hardware and software against the numbers. It has just been announced that a team including Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann has just factored RSA-240, a 795-bit number, taking 900 core-years on a 2.1 GHz Intel Xeon Gold 6130 CPU. They also demonstrated the calculation of a 795-bit discrete logarithm on the same hardware. The previous records were for RSA-768 in 2009 and a 768-bit discrete logarithm in 2016. The speed improvements that led to this work were attributable more to algorithmic improvements than better hardware.
Dear number theorists,
We are pleased to announce the factorization of RSA-240, from RSA's challenge list, and the computation of a discrete logarithm of the same size (795 bits):
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
[...] The previous records were RSA-768 (768 bits) in December 2009 [2], and a 768-bit prime discrete logarithm in June 2016 [3].
It is the first time that two records for integer factorization and discrete logarithm are broken together, moreover with the same hardware and software.
Both computations were performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software [4].
The sum of the computation time for both records is roughly 4000 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz).
[...] The acceleration can be attributed to various algorithmic improvements that were implemented for these computations. The CADO-NFS implementation was also vastly improved.
We used computer resources of the Grid'5000 experimental testbed in France (INRIA, CNRS, and partner institutions) [5], of the EXPLOR computing center at Université de Lorraine, Nancy, France [6], an allocation of computing hours on the PRACE research infrastructure using resources at the Juelich supercomputing center in Germany [7], as well as computer equipment gifted by Cisco Systems, Inc. to the University of Pennsylvania.
More details will be given in a forthcoming scientific publication.
(Score: 0) by Anonymous Coward on Friday December 06 2019, @12:10PM (18 children)
Classical algorithmic improvements are a big deal, but it will take quantum computers to nuke RSA-4096.
RSA-8192 is in use: https://www.zdnet.com/article/this-ransomware-uses-overkill-encryption-to-lock-down-your-pc/ [zdnet.com]
Maybe using stupidly large key sizes will secure data for an additional year against initial puny quantum systems.
(Score: -1, Disagree) by Anonymous Coward on Friday December 06 2019, @12:32PM (2 children)
The more bits you have the fewer possible primes there are. 4096 is already pushing it. 8192 and 16384 decrease the possibilities even further for any particular modulus. As a result increasing the size actually decreases the possibilities necessary to search.
Practically speaking, an alternative to RSA is needed in order to protect us going into the future.
(Score: 3, Interesting) by FatPhil on Friday December 06 2019, @01:52PM
Tl;dr: don't read.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by HiThere on Friday December 06 2019, @06:48PM
Perhaps you mean the larger the minimum number the fewer primes will be found within a range of a certain size. The number of primes is unbounded.
Javascript is what you use to allow unknown third parties to run software you have no idea about on your computer.
(Score: 4, Insightful) by FatPhil on Friday December 06 2019, @02:45PM (14 children)
1024 bits is looking like it's theoretically possible using cutting edge academic algorithmics and government agency budgets, but AFAIK, nobody's trying it yet because government agency budgets are hard to acquire, and the government agencies who have them are using them to do their real work. However, noone's making any predictions of how or when 1536-bit will be factored, that's verging on sci-fi levels of tech. So, back of a fag packet estimates, trust me, guv', say that 1536 is secure enough for most kinds of data.
The fear is not quantum computers, but primarily that there will be algorithmic Big-Oh improvements, of course, more than just constant factor tweaks, which is why you over-engineer. DJB's scaremongering over tha last 2 decades never seemed to come to ought, so I don't think that's influenced the growth of the keys, and I'm sure quantum hasn't. That's why the keys in typical informed use, really aren't growing that large.
Have you done a calculation of the number of qubits required to perform shor's algorithm on a 4096-bit key? At the rate quantum computing is progressing (we've spent 20 years to get us to the same level as semiconductors got to after a decade), I'm pretty sure we'll not be able to maintain coherency for anything that enormous for at least another half-century. Peter Shor himself doesn't believe his algorithm will ever factor a real world number that couldn't have been factored more easily factored using a classical algorithm on a classical computer. So I think all the QC stuff being bandied around is just woo-woo to scare people (sometimes, if not typically, for money).
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Interesting) by takyon on Friday December 06 2019, @03:20PM (12 children)
There is likely going to be at least a further 10x improvement in classical computing using 3DSoC, new types of transistors, or other advancements. 1000x or more is possible. I wouldn't rule out a 1 million times improvement in performance per Watt. Even that would not render cryptography obsolete, but it could help annihilate some of these lower key sizes.
I would not be quick to bet against quantum computing. A lot of R&D needs to be done, but an appropriate technology could win out and scale up rapidly since we already know how to mass produce chips with nanoscale features.
Quantum computing’s also-rans and their fatal flaws [arstechnica.com]
[SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
(Score: 2) by DannyB on Friday December 06 2019, @03:26PM (4 children)
Does a hundred or a million fold increase in factoring speed even matter if you can just add a couple dozen more bits to the size of the numbers? Each bit doubles the range of integer values. And it's easy to just add bits. You don't even need to go from 8192 to 16384 bits. Just go from 8192 to 9000 bits, how much bigger of a range is that? Does a million times factoring improvement even matter?
The lower I set my standards the more accomplishments I have.
(Score: 2) by takyon on Friday December 06 2019, @04:21PM (3 children)
The NSA apparently stores all encrypted information it can find. So there's a giant legacy trove of information that could be decrypted as the capabilities become available, including plenty of 1024-bit RSA. Classical computing and algorithmic improvements will help with that, and quantum could finish the job for some algorithms. Even if quantum computing is hyped, it is better to hype potential security threats than downplay them.
[SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
(Score: 2) by DannyB on Friday December 06 2019, @04:33PM (1 child)
<no-sarcasm>
Mini years ago, in the late 90's IIRC, I remember reading Applied Cryptography. One thing I learned is that the security of a key must be secure into the future for as long as the information remains valuable. Said differently, it must be resistant not only to today's attacks, but attacks for the foreseeable future as long as the information must be protected.
The book extrapolated to larger key sizes and how it be resistant to an attack even if all the entire mass of our solar system were converted into a gigantic dyson-sphere like computer.
That doesn't mean that everyone understood the need for future security when they chose 1024 bit RSA.
</no-sarcasm>
But then neither did people who use tripple-DES or tripple-ROT13.
The lower I set my standards the more accomplishments I have.
(Score: 2) by FatPhil on Saturday December 07 2019, @11:08AM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 1) by Ethanol-fueled on Friday December 06 2019, @10:11PM
Why oh why would that be, do you suppose?
(Score: 2) by sjames on Friday December 06 2019, @06:43PM (6 children)
OTOH, I wouldn't be so quick to bet on quantum computing either. I would say that if we compare it's timeline with conventional computing, QC is right around Babbage's attempts at an analytical engine.
That state of affairs is likely to improve, but for cryptography, the question is will it improve fast enough that it will even threaten anything currently encrypted soon enough that the encrypted information would still have any value? And an even bigger question, would it do so at a cost that makes it worthwhile?
The same cost-benefit questions will, of course, apply to other approaches to breaking cryptography.
(Score: 2) by takyon on Friday December 06 2019, @06:52PM (3 children)
https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/ [quantamagazine.org]
[SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
(Score: 2) by sjames on Friday December 06 2019, @07:38PM (2 children)
I wouldn't put too much stock in that either. See IBM's rebuttal to Google's recent claims. You really can't extrapolate much from the changes over a three month period while a new machine is being tuned.
On a side note, the Podunk Hawkettes assure me that the Podunk Hawks are the very best and that they'll FIGHT FIGHT FIGHT! But I'm not betting the car payment on it :-)
(Score: 2) by takyon on Saturday December 07 2019, @04:05PM (1 child)
I think the best part is that there are maybe 10+ technologies/approaches [wikipedia.org] in contention (not counting "quantum annealing" like D-Wave), and a lot of money floating around. Many avenues towards quantum computing are being explored.
IBM is a competitor and their own hand-waving needs to be taken with a grain of salt [quantamagazine.org]. If the Google man is right, then we shouldn't have to wait very long to figure out if they are full of it. It would become obvious by 2021 or so.
Quantum machine learning is a thing, so there's another good way to rake in funding.
[SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
(Score: 2) by sjames on Saturday December 07 2019, @11:49PM
Quantum machine learning is a theory.
It's worth keeping in mind that the Google calculation was not a useful computation. It was more akin to test code to make sure each part of the CPU actually works. As for the "quantum supremacy", they're basically claiming that only a quantum computer is a quantum computer.
It's all worthwhile research, but this is really not just around the corner, media hype and funding pitches notwithstanding.
(Score: 2) by HiThere on Friday December 06 2019, @06:53PM (1 child)
Yes, but it your argument for an infrastructure is that quantum won't work, you're betting against it on a large scale. Of course, it may be someone else who ends up paying the penalty.
Javascript is what you use to allow unknown third parties to run software you have no idea about on your computer.
(Score: 2) by sjames on Friday December 06 2019, @09:40PM
The bet was made decades ago on 512 bit RSA. Looks to be paying off well. Most of that information from 20 years ago isn't even of historical interest now.
It's mot really a bet that quantum won't work, it's a bet that it won't be practical fpr cracking sufficiently strong crypto before the value of the information goes to zero.
If a historian finds out my banking details in 2080, so what?
(Score: 2) by driverless on Saturday December 07 2019, @01:33AM
There's some discussion on Schneier's blog on this too, can't find the message at the moment but someone pointed out the massive disconnect between drawing a line on a graph of factoring over the last 30 years to see where things are going and "NIST numerologists" telling is we should be using 15Kbit keys because that's what they've read from sheep entrails or something.
(Score: 0) by Anonymous Coward on Friday December 06 2019, @12:46PM (5 children)
Why does the summary have to repeat itself:
Really is.
(Score: 3, Interesting) by FatPhil on Friday December 06 2019, @01:58PM (4 children)
I changed *absolutely nothing* *100% deliberately*, as Stormwyrm had done a great summarising of the story, and even after your complaint I stand by that. The amount of duplication is utterly negligible, and as I say, some repition is expected in inverted pyramid.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 0) by Anonymous Coward on Saturday December 07 2019, @12:40AM (1 child)
For a site that prides itself on copypasta reporting (like most, i come here for the comments anyway). Minimising your summary usage of nabla would be more appreciated please. Repetition, to me smacks of sending/selling a message, more than reporting.
That said, i should not have picked so muckh on this example is not so bad, just triggered me when tired on first reading.
(Score: 2) by FatPhil on Saturday December 07 2019, @11:55AM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by Common Joe on Saturday December 07 2019, @05:06AM (1 child)
I see AC replied to you with this:
I don't see any need to change what you guys are doing. Yeah, you have the occasional hiccup about something, but I just chalk that being human. ACs tend to forget that all of us (with perhaps the exception of the entity behind the "Bot" account) are human, the editors all have limited time, and perfection is not the goal. Overall, I'm pretty happy with how things are handled. Like most summaries, I found this particular summary pretty concise, clear, and pleasing to read.
I thought you'd like to hear a supportive voice. And a thank you for your hard work. Please make sure all the editors know how appreciated their efforts are.
(Score: 2) by FatPhil on Saturday December 07 2019, @11:57AM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 0) by Anonymous Coward on Saturday December 07 2019, @05:16PM
404040404 * 404040404 = enough said.....