Hacker News Reader

Comment by GracefullyShot | Hacker News Reader

I am not a cryptography expert but I am interested in the field. Having said that: I am lately having an hard time understanding the actual strength of a crypto suite based on the underlying problem, the sized of the material and the computation strength needed to break it either via optimization and parallelism capabilities.

> The Web PKI deprecated 1024-bit RSA over a decade ago, and while I don’t know of anyone factoring a key of that size, it’s within the realm of possibility for a government or other organization with a large number of computers.

Is it? How do I verify such claim?

---

> Just a few days ago, someone factored the 862-bit RSA-260 key from the RSA factoring challenge.

Yeah, but how much time it required? and what about the resources? It is just a number, it is not all the 861 bits n numbers.

View on HN

As you probably know, the computing time in the worst case scenario for brute forcing a cryptographic key generally doubles by each bit added. That is, it would take twice the effort to brute-force 129 bits compared 128 bits.

The security of RSA however depends on the factoring of very large numbers, and that means that for example, RSA-2048 doesn't translate into 2048 bits of security but 112 (roughly symmetric equivalent) bits based on the best factoring algorithms (for comparison, the RSA-512 the article mentions has an 56 bit equivalent and RSA-1024 has a 80 bit equivalent security, so RSA-1024 would take roughly 2^(80-56) ~= 17 million times to compute the worst-case scenario and RSA-2048 would take 2^(112-80) = 4.3 thousand million times more).

According to the Wikipedia article on RSA numbers, RSA-220 (66b) was factored in 2016, RSA-230 (69b) in 2018, RSA-240 (72b) in 2019 and RSA-260 (76b) this year, which is too close to RSA-1024 (80b) to be comfortable.

For RSA-250, the team reported it took "roughly 2,700 core-years, using Intel Xeon Gold 6130 CPUs at 2.1 GHz.". I am not going to (or feel qualified to) make estimates of how that would translate to RSA-1024, but it does sound plausible given enough resources.

RSA-1024 about 2000 GPU years. With clusters of size 100k typical right now. https://x.com/sweis/status/2095570657367278051

Consider it broken already for AI or NSA guys

This article from 2000 is about estimating what would be required to factor 1024 bit RSA:

A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths https://cr.yp.to/bib/2000/silverman.pdf

It was a response to the idea that 1024 bit RSA was under threat at the time.

> I am not a cryptography expert

> How do I verify such claim?

Step 1: Become a cryptography expert. ;)

Reply on news.ycombinator.com