According to RSA Factoring Challenge 829 bits were broken recently [0]. The total computation time was roughly 2700 core-years [1].

I would consider 1024 bits risky in the following 10 years. 2048 bits probably won't ever be broken without significant algorithmic breakthrough or quantum computers.

[0] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

[1] https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202...

Don't confuse brute forcing 2^65 possibilities with factoring a 2^65 bit semi-prime (n in RSA).

I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in milliseconds.

    // get two random primes (pretend P, Q)
    sage: random_prime(2^34)
    12697300267

    sage: random_prime(2^33)
    3962800609

    // make a semi-prime (pretend N)
    sage: 12697300267*3962800609
    50316869230723462603

    // check length of semi-prime (65-bits)
    sage: log(50316869230723462603,2).n()
    65.4476759618453

    // factor it in 18milliseconds.
    sage: time factor(50316869230723462603)
    CPU times: user 9.78 ms, sys: 9.07 ms, total: 18.8 ms
    Wall time: 23.2 ms

2^1024 bit RSA is about 2^80 in bit strength.

This example was 2^65 bit RSA, which is negligible in bit-strength.

GNU coreutils `factor` program can do so as well:

  bash$ time factor 50316869230723462603
  50316869230723462603: 3962800609 12697300267

  real 0m0.009s
  user 0m0.009s
  sys  0m0.000s

Bitcoin last peaked at a hash rate of 170EH/s[1]. That's about 2^61 double SHA256 hashes per second. There are about 31.6E6 seconds per year. So around 72.5E24 hashes/year, or 2^86. VERY expensive, but 2^80 is well within brute-force range. I'd consider any symmetric system with less than 112 bits of security to be potentially breakable within the next few years. For anything over 50 years, I'd want a 256-bit security level since general purpose quantum computers might be made within that time.

But RSA is about a thousand times slower than double-SHA256, yet it still needs such large keys for security. That's because nobody is going to brute-force RSA, there are far better options. Like the General Number Field Sieve. Of course that's still exponential, this paper claims to be polynomial time for the vector-finding portion, not sure about overall. I've only skimmed it, and it's rather dense.

[1] https://charts.bitcoin.com/btc/chart/hash-rate#5ma4

Comparing these two sets of O() estimates is a bit dubious. SHA256 uses almost no memory and hashing can effectively be distributed across machines at no cost. All of the current factorization mechanisms build vast sparse matrices and then perform reduction operations. At some threshold point the memory needed exceeds the capacity of a single machine. This means the O() estimates will hit a speed wall as it is necessary to distribute the computation. Single machine size / memory availability is of course a moving target! O() complexity bounds are great, but unless you've got a machine that can perform every one of the operations at a cost multiplier of effectively 1 it is not always possible scale things up or make this sort of algorithm comparison.

True! Comparing symmetric speeds for SHA256 to the operations needed in RSA is iffy at best. But for illustrating the point that brute-forcing the keys used in current RSA is a braindead way to attack things that doesn't really matter. It just further enhances the point. Brute force just isn't the attack to use for comparisons.

It's for various reasons, but one of them is that, from an attacker perspective, you don't have to strictly solve the factorization problem. You just need to be able to crack a tiny fraction of the keys in a reasonable amount of time in order for RSA at that key length to be considered unsafe to use. In that sense the attacker gets the benefit of best-case complexity.

ECM will easily factor 160-bit numbers https://doc.sagemath.org/html/en/reference/interfaces/sage/i...