1

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?

4
  • 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. Feb 17, 2019 at 5:01
  • 2
    I'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, 2019 at 9: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, 2019 at 9:26
  • 1
    @LancePollard Those are enough even if your adversary harnesses the power of entire galaxies.
    – forest
    Feb 17, 2019 at 9:42

1 Answer 1

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .