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.
We have an interesting situation with Shor’s algorithm. Cryptographers around the world lived in peace because even a super powerful computer would have to spend millions of years hacking asymmetric algorithms. By the way, in our blog, you can read about asymmetric algorithms, and in particular, widely used RSA and ECDSA.
And 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. 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 will 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 – simply due to the lack of a quantum computer. But already in 2001, Shor’s algorithm was tested by a group of specialists from IBM on a 7-qubit quantum computer – 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.
What does blockchain have to do with it?
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. And a potential attacker has whole 10 minutes (the block confirmation time in the Bitcoin network) to attack a public key, 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. In particular, encryption is used in VPN services, IT security systems (including government security), some messengers. Also let’s remember about banks that 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 quantum Shor’s algorithm at a time when quantum computers will be powerful enough.