Is it possible to crack Bitcoin’s private key with quantum computers?

A frequently mentioned problem is that ECDSA encryption can be cracked via quantum computers using this Shor algorithm. This is a very big problem, because the ECDSA encryption generates the public key from the private key. In order to crack an ECDSA encryption, the computational effort for determining a private key from a public key using the Shor algorithm would be reduced by a factor of 10^-34. Even a very slow computer, which can perform one calculation per second, would not even need two days to find the private key.

Is cryptosoft really insecure then?

What many people often overlook, however, is that in the case of Bitcoin there are two cryptosoft encryptions between the attacker and the private key. It is known that you have to determine a private key from a public key. This can be done as shown using the Shor algorithm. However, the attacker will normally not see the public key itself, but his hash. This hash is the wallet address.

Specifically, the following cryptographic processes interlock: From the 256-bit private key, a 512-bit public key can be generated via ECDSA encryption. A SHA256 algorithm converts this into a checksum, which in turn can be converted into the wallet address. The attacker does not only have to determine the private key from the public key. He must first generate the public key from the wallet address.

Hackers can in principle crack SHA256 using the Grover algorithm. However, this algorithm only achieves a quadratic acceleration. This means that an attack on a hash generated by SHA256 requires approximately 2^128 or 3.4*10^38 computing cycles. Currently the supercomputers of the world can process about 10^17 operations per second. This set is assumed to be the upper limit. In principle, it cannot be assumed that a so-called entangled state can be prepared again in such short time intervals after measurement processes have taken place. A quantum computer with so many Qubit operations per second would need only 107.9 trillion years instead of 4*10^52 years to find the Public Key. This is still much greater than the age of the universe!

Admittedly, there is another algorithm that promises a cubic runtime optimization. With this a quantum computer, in the case of 10^17 Qubit operations per second, could break the connection between wallet address and public key in 15 years.

Even under the assumption of a supercomputer that is currently physically impossible, and using a comparatively unknown algorithm, the cost of hacking would dramatically exceed the benefit.

What does Bitcoin do and what can you do?

It turns out: Bitcoin is comparatively quantum safe. Of course, this is only true as long as nobody develops a better algorithm than Grover for finding the public key. That’s why it’s still interesting to see whether Bitcoin developers even take up this question.

True to the motto „Be your own bank“, it would also be desirable if the individual Bitcoin user were not only crypto-fit, but quantum safe. In part two of this series of articles, we therefore discuss the possibilities we have for better protection of our Bitcoins.