Most random secure numbers are 256 to 512 bits. But given the size of the universe and eventually quantum computing, I am wondering what is a better sized randomly generated number, taking into account minimizing its size while also making it unique enough to cover that amount of space and quantum computing. Or is 2256 ≈ 1e77 large enough?
Asked
Active
Viewed 121 times
1
-
A secure random number is used in a specific context in which it needs to be random enough. Nothing is known about the context you are talking about and thus nothing can be said if this will be sufficiently secure in the future or not. Similar the claim of *"Most random secure numbers are 256 to 512 bits"* assumes a specific context: random numbers by themselves have no limit on the number of bits. It is just about collecting randomness and then stopping to collect when it is enough for the specific purpose. – Steffen Ullrich Feb 17 '19 at 05:01
-
2I'm not sure what you mean by "size of the universe". The universe is quite bit, but I fail to see how that impacts computer security or cryptography. – forest Feb 17 '19 at 09:23
-
By that I meant the amount of data you could possibly store in the universe, if you created a GUID for that, how big it would have to be so it could be randomly generated at that size (and so be anonymous so to speak). If 256 or 512 is enough given the amount of data theoretically storable in the quantum space. – Lance Feb 17 '19 at 09:26
-
1@LancePollard Those are enough even if your adversary harnesses the power of entire galaxies. – forest Feb 17 '19 at 09:42
1 Answers
3
Quantum computers are not magic. They can only accelerate a very specific class of problems in the so-called BQP complexity class. This includes integer factorization, which is why a cryptanalytic quantum computer is said to be capable of completely breaking RSA keys in polynomial time by utilizing the quantum Shor's algorithm. However, their ability to brute force through a keyspace is much more limited. The most efficient quantum algorithm for searching a keyspace is Grover's algorithm, which provides only a quadratic speedup over classical algorithms. This means that a quantum computer can brute force a 256-bit key in only 2128 operations instead of 2256 as with a classical computer. Luckily, this means all we need to do to resist quantum computers when choosing key size is choose a 256-bit key or larger. You only need to double the key bits to retain the equivalent classical security against quantum computers. If we consider 128-bit keys to be the minimum, then double them to 256 bits.
forest
- 64,616
- 20
- 206
- 257