I've factored the RSA keys of a Certificate Authority from the 90s

Posted by ahlCVA 9 hours ago

I've factored the RSA keys of a Certificate Authority from the 90s(mcpherrin.ca)

330 points | 56 commentspage 2

Retr0id 8 hours ago|

I went down the same line of thought in the past! But I guess I was less thorough with my search, I never found any certs that small.

excalibur 8 hours ago||

> Assuming you’re somehow running Netscape 4.51 with a clock set before E-Certify roots expired on 2003-10-16, you can use these private keys to issue certificates. This describes zero people on the planet… except for this VM I set up.

The planet has a lot of people.

ranger_danger 6 hours ago||

How was it actually factored though? Where is the code for that? How was the private key created and how are the new certs issued?

zatkin 6 hours ago|

The author mentions CADO-NFS right in the article: https://cado-nfs.gitlabpages.inria.fr/

andytratt 7 hours ago||

lol nice job Marc Andreesen

ggm 8 hours ago|

The cost per bit is a doubling in time. So factoring a 512 RSA, compared to a 1024 RSA is significantly cheaper. The OP used contemporary hardware to do this. so, we'd have to ask if the orders of magnitude improvement in tech (QC aside) would permit 1024 in tractable time. I tend to no, but I appreciate there are other points of view. And of course, the belief that one day we can apply Shor with success exists. At which point the question is moot. Not that Shor does not itself demand significantly more stable gates, per extra bit of RSA. I always wonder why people don't look at the trend line in stable QuBits and the trendline in cost of RSA. Do the lines intersect?

Remember, Shor is like a coded gate level algorithm expressed as sequences of interconnected stable QuBits. So, if you double the cost for each RSA bit you add, its not "nothing" in terms of how you wire the rig.

(not a cryptographer, or a QC person so I expect to be hit by a very cold but stable quantum clue-by-four shortly. Maybe they have to hit me 1 million times, to confirm I'm hit. Its statistics.)

mcpherrinm 8 hours ago||

It’s not quite a doubling per bit, which is why RSA keys are relatively large compared to similar-strength ECDSA keys, for example.

Steve Weis, who has been doing RSA factoring on some large GPU clusters, estimates factoring 1024-bit RSA would take about 2000 GPU-years, which is well within the range of anyone with a serious budget.

WhiteDawn 5 hours ago|||

Yeah, 2000 years sounds like a lot till you do the math. Apparently astra was trained on 100k Blackwell gpu’s. So just over 7 days to crack 1028-bit rsa on that cluster…

throwawayk7h 8 hours ago|||

out of curiosity, how long would 2048-bit RSA take to factor?

mcpherrinm 8 hours ago|||

It's hard to extrapolate that far, but maybe hundreds of thousands or millions of years.

Naively looking at scaling factors is going to be tricky, because computation of this scale is going to involve things like "how do I hijack every GPU on the planet", or worrying about when the sun will run out of hydrogen if you're using a single CPU.

mitxela 8 hours ago||||

https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_...

says approximately the same as a 112-bit symmetric key, so 1/65536 as fast as however your target platform does at AES128, but probably 2000 times slower again because RSA is a really slow algorithm.

128-bit security is the de-facto minimum standard. Anything less than that is suspect. That's a 3072-bit RSA key. We only ever tolerated shorter keys because RSA is so slow. You should switch to ed25519 if you can.

entrope 8 hours ago|||

2048-bit RSA gives something like 28 more bits of security than 1024-bit RSA has, so it would take about 250 million times as long to factor one 2048-bit key.

mitxela 8 hours ago|||

Doubling per bit is for symmetric encryption, where no attack better than brute force is known. RSA can be attacked using much faster techniques than brute force.

ColinWright 1 hour ago||

Can you point at some papers or articles that talk about attacks specifically on RSA? I've done a search and have a few references, but I'd be interested to know if you have any particular examples in mind.

I know that factoring (which attacks RSA) is sub-exponential, and I know that implementations of RSA (bad choices of primes, timing attacks, etc) can have weaknesses ... I'm just interested as to whether you have something else in mind.

Thx.

hannob 43 minutes ago||

I think you're looking for the large formula at the top here: https://en.wikipedia.org/wiki/General_number_field_sieve

Reference to a scientific paper is given: https://www.ams.org/notices/199612/pomerance.pdf

rcxdude 8 hours ago||

There are techniques to speed up the search for RSA keys quite significantly: they don't scale as with a pure brute force search, nor with a very useful rule of thumb (it's not even the case that doubling the RSA key length doubles its effective security, it's actually a fair bit less than that).