Peter Shor and his algorithm
Scientists are amazing people, they just can’t live without inventions or discoveries. And then the whole world has to think what to do with these discoveries. For example, atomic energy is as useful as it is dangerous. And Peter Shor with his algorithm is a good example of this.
Cryptographers around the world lived in peace. Because even a super powerful computer would have to spend millions of years hacking asymmetric algorithms. In particular, the widely used RSA and ECDSA were considered absolutely reliable. Until Shor’s algorithm.
In 1994, the American scientist Peter Shor devised an effective polynomial quantum algorithm for the factorization of integers. It sounds mysterious. Well, but why is it threatening?
And this is why. The matter is that asymmetric cryptography is based on the problem of integer factorization — the decomposition of a composite number into a product of smaller integers. The essence of the problem: there is a product of two integers, you need to find the original integers (factors). A classical computer is unable to solve this problem in an acceptable time. It would take millions of years. This is the basis of modern asymmetric encryption — it is impossible to quickly solve the problem of factorization and retrieve a private key.
But Shor’s algorithm applied on a quantum computer can solve this problem easily and quickly. Private key computation goes at about the same speed as the data encryption. We need only a quantum computer with a sufficient number of logical qubits which could compute the private key.
Shor’s algorithm testing
In 1994, Peter Shor didn’t have the possibility to apply the algorithm in practice. Just because a quantum computer didn’t exist. However, in 2001, Shor’s algorithm was tested by a group of specialists from IBM on a 7-qubit quantum computer. Thus, the integer 15 was decomposed into two factors 3 and 5. It would seem a very simple task which any pupil can solve. Not only without a quantum computer but even without a calculator.
It is not important the specific numbers but the ability to solve this problem by applying a quantum computer. In 2018, testing a quantum computer already with 72 qubits was started.
Shor’s algorithm against blockchain
The fact is that public key cryptography (asymmetric encryption) is the heart of blockchain. And of cryptocurrencies. For example, in the Bitcoin blockchain, a public key is transmitted to the network in unencrypted form during each transaction. Hence, a potential attacker has a whole 10 minutes (the block confirmation time in the Bitcoin network) to attack a public key. And to calculate a private key and replace the address to which coins were sent.
And not only against blockchain
Not only blockchains should tremble because of Shor’s algorithm. But any system that applies asymmetric encryption as well. In particular, encryption is used in VPN services, IT security systems (including government security), some messengers. Also let’s remember about banks. They use asymmetric cryptography for client authentication. And about ordinary companies applying digital signatures in electronic document management. So, modern cryptography must find fundamentally new solutions to stand firm against the Shor’s algorithm. Especially at the time when quantum computers will be powerful enough
EN 
RU