Time needed to factor large integers
5 days ago
- #Cryptography
- #Factoring Algorithms
- #RSA
- The GNFS (general number field sieve) algorithm is the fastest known factoring algorithm for numbers larger than a googol (10^100).
- The expected time to factor a number n using GNFS is proportional to exp(f(n) g(n)), where f(n) is relatively constant and g(n) varies more strongly with n.
- For cryptographic applications, the o(1) term in f(n) is significant, often around 0.27 for practical key sizes.
- A 1024-bit RSA key provides 80-bit security, comparable to breaking an 80-bit symmetric encryption key.
- The security level of an RSA key is proportional to g(n), which is (log n)^(1/3) (log log n)^(2/3).
- Empirical data shows that the security level of RSA keys is roughly 2.55 * x^(1/3) * log(x)^(2/3), where x = log(2) * b (b is the key size in bits).
- Factoring a 2048-bit RSA key would require more energy than the world produces in a year.
- RSA encryption is not broken by factoring keys but by exploiting implementation flaws.