Why Can’t Quantum Computers Break Bitcoin’s Security?

You might have heard a lot of rumors by now about quantum computers having the computational power to run through all 2^{256} combinations of private keys. That effectively means that Bitcoin’s security is broken because all private keys can be found.

Obviously, the ramifications of this would be enormous. Bitcoin’s price would take and many people would lose their life savings. And yet, at the present, how is it we haven’t found a single system that advertised itself with the ability to calculate all private keys?

The Math Behind Private Keys

To start, it helps to understand how private keys are created. Private keys are nothing more than a number that is multiplied by a special point. Without making things too complicated, this isn’t a regular coordinate point, but a point on an elliptic curve.

An elliptic curve is a gigantic set of (x,y) points which can be ordered in sequence and you can add a point to itself and get the next point in sequence, etc. The reason why it’s called “elliptic” is when you do the addition a certain amount of times, you get back to the original starting point. The list of points by themselves is sometimes called a Galois field, but we won’t be discussing this strange math construct any further.

In fact, you can take any point in that sequence and keep adding it to itself to get a completely different sequence. In that sense, elliptic curves have huge numbers of sequences made of the same points.

Alright, enough university lecturing and let’s see why this is important to Bitcoin’s security.

Why are Elliptic Curves Important to Bitcoin?

Let me make one thing clear – small elliptic curves are very insecure and weak because you can enumerate all of the different sequences. That is why only large elliptic curves are used in cryptocurrencies. A large elliptic curve is one that has a large number of points and therefore sequences. Bitcoin’s curve – called secp256k1 – has 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1 points and sequences inside it. As you can see, this is a huge number.

Computers cannot even count up to this large number in a lifetime. So, you might think, how can they generate that many elliptic curve points in a shorter span? Remember that creating one curve point is already computation-intensive.

And this, precisely is what makes Bitcoin so secure. Since every curve point is a bitcoin public key, the sequence number to make the curve is called the private key. (Yes, I know I said there are huge numbers of sequences in elliptic curves. Bitcoin and other crypto’s define a starting point G to some well-known arbitrary point so they only have to deal with one sequence.)

So while it’s possible to, for example, easily break the first and last few private keys in the sequence – and steal their contents – in practice, the elliptic curve is so large that wallets never generate these private keys in the real world.

Just how impossible is it?

A picture speaks a thousand words. No, don’t bother using them for brute-forcing purposes.

In case the image isn’t loading, I also placed the quote in text below:

Imagine you built a perfect computer; forget about GHash and Megahertz.

You built a computer which used the absolute mini-mum amount of energy theoretically possible to record a change in a single bit [1 to 0 or 0 to 1].

We are talking about the limits of thermodynamics; nothing more efficient is even possible.

Now imagine you used most of the natural resources in our star system to construct a dyson sphere and covered the entire surface of this sphere with a single star system sized super computer.

Now imagine you could keep this supercomputer cooled at roughly absolute zero and could do so without expending any additional energy.

If you had that and captured (with no inefficiency or loss] the entire energy output of our star (not just in a day or week but continually until it burned out] you couldn’t COUNT to 2^256 before you ran out of energy.

Keep in mind this is simply counting.

Just counting, not hashing, not comparing, not per-forming lookups just counting 1 .. 2 .. 3 .. …. 2^256-1.

These numbers have nothing to do with the technology of the devices, they are the maximums that thermodynamics will allow.

And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

Bitcoin — Your money is secured by the laws of the universe.


So next time someone tries to scare you with the “threat” of quantum computers or Shor’s algorithm or any of that stuff, just remember that even a Star Trek-esque computer can’t even brute force 256-bit private keys (but they might get a few lucky bits from the lower keys along the way).

Ali Sherief

By Ali Sherief

Editor-in-chief and serial coder & blogger.