Grandpa, Trust Me, You Can’t Just ‘Guess’ Someone’s RSA Key
During this past Thanksgiving, I learned a couple things. In hindsight, both are obvious & I’m embarrassed at my tardy realization(s):
- Gravy can make literally anything taste phenomenal.
- People falsely believe that since private encryption keys are just a sequence of bytes, they can be ‘guessed’.
I shall attempt to shine light upon the latter, for both the layman and mathematician alike.
But first, a couple sentences about generating RSA keys:
These days, it’s pretty standard to generate RSA keys that are 2048 bits long: this is accomplished by multiplying two 1024-bit prime numbers together. Therefore, in order to brute-force any given 2048-bit RSA key, you would need to multiply every 1024-bit prime number with every other 1024-bit prime number… until you get the key. So, how many 1024-bit prime numbers are there?
The number of primes smaller than an integer n is approximately n/ln(n).
2¹⁰²⁵ / ln(2¹⁰²⁵) - 2¹⁰²⁴ / ln(2¹⁰²⁴) = ~ 2.53 * 10³⁰⁵ (# of 1024-bit primes)
The number of 2048-bit RSA keys (i.e. pair of 2 distinct primes) is therefore:
(2.53 * 10³⁰⁵)² / 2 – 2.53 * 10³⁰⁵ = ~ 4.05 * 10⁶⁴¹
Wait for it. Things are about to get interesting.
The observabale universe contains about 10⁸⁰ atoms. Now, assume that we could leverage every single atom as a CPU, and each CPU could enumerate 1,000,000 RSA keys per second ← a very generous estimate.
Enumerating ALL 2048-bit RSA keys would take:
4.05 * 10⁶⁴¹ microseconds / 10⁸⁰
= 4.05 * 10⁵⁶¹ microseconds
= 4.05 * 10⁵⁵⁵ seconds
= 1.125 * 10⁵⁵² hours
= 1.28 * 10⁵⁴⁸ years
For reference, the Big Bang occurred 13.8 * 10⁹ years ago.
If every atom in the observable universe started brute-forcing a 2048-bit RSA key at the time of the Big Bang, we’d presently be less than a fraction of 0.000000000000000000000000000000000000000000000001% complete.
It’s. Just. Not. Possible.
If you’ve made it this far, I hope you’ve adopted the reality — being that no one can brute-force a 2048-bit RSA key. Not even your favorite 3-letter organizations ❤