Shore as a threat to modern cryptography

Quantum computers have unlimited potential and special talents – attack vectors such as Shor’s and Grover’s algorithms that can break cryptography. The reason these two haven’t finished the race yet is because all the necessary calculations on regular computers can take years. But many expect this to change as the scale and speed of quantum computers grows.

Y2Q problem

Researchers have come up with a term for the moment when the “turtle” will pass the “hare”. This is the year Y2Qwhen the possibilities of quantum code breaking will become a threat to the existence of classical cryptography. When this happens, one can only guess, but the question of whether this will happen has already been resolved for many. In 2018, the report US National Academy of Sciences, Engineering and Medicine (NASEM) it was predicted that a powerful quantum computer using Shor’s algorithm would be able to crack a 1024-bit encryption implementation RSA in less than 24 hours.

The mathematician Peter Shor, who is responsible for one of the algorithms, added his own warning at the end of 2020: “I think the only obstacle to replacing RSA [криптосистемы с открытым ключом] there will be willpower and programming time for a secure post-quantum cryptosystem … If we wait too long, it will be too late. “

Nature Editors Explained Food Risks In Late 2018 blockchain… So, blockchain security is based on one-way math functions… They are easy to run on a regular computer and difficult to reverse engineer. For example, multiplying two large primes is easy, but finding the prime factors of a given product is difficult — a typical computer can take many years to solve.

But Shor’s algorithm is designed to run on a quantum computer that can take a number and output its factors in a short amount of time. Mathematically, this would require a polynomial not exponential amount of time. Grover’s Algorithm is also a quantum algorithm designed to speed up searches in unsorted databases.

RSA today depends on the complexity associated with large primes. Scientists predict that within ten years, quantum computers will be able to compute one-way functions, including blockchains, which are used to secure the Internet and financial transactions. Widespread one-way encryption will instantly become obsolete.

Shor’s algorithm

In this section, we will briefly consider Shor’s algorithm itself. The purpose of the algorithm: for an odd composite numberyou need to find an integer(strictly from 1 towhich is divisible by

Shor’s algorithm consists of the following parts:

• Transformation of the factorization problem into the problem of finding the period. This part can be realized by classical means.

• Finding the quantum period using quantum Fourier transformwhich is responsible for quantum acceleration and uses quantum parallelism.

General sequence of actions:

Shor’s algorithm contains several steps, and only on second step requires the use of quantum computers.

1. Choose any random number such that and – coprime numbers.

2. A quantum computer is used to determine an unknown period functions

3. If – an odd integer, return to step 1. Otherwise, go to the next step.

4. Insofar as Is an even integer, then

5. Now if the value then we return to step 1.

6. If the value go to the next step.

7. We calculate

8. We get the required value

1. Choose any random number such thatand – coprime numbers.

2. A quantum computer is used to determine an unknown period functions

3. If – an odd integer, return to step 1. Otherwise, go to the next step.

4. Insofar asIs an even integer, then

5. Now if the value then we return to step 1.

6. If the value go to the next step.

7. We calculate

8. We get the required value

Development prospects

By adopting the “if you can’t beat someone, join them” strategy, the race for the right to use the same quantum computing is starting now. Perhaps this race is even underway for the power of the “quantum Internet”, which will lead to the creation of new, more sophisticated encryption procedures. Final goal – post-quantum cryptography…

It should be noted that the problem of the mass disappearance of information security is not new. The encryption created by the German Enigma war machines during World War II was eventually hacked by the Allies, but the cryptography didn’t end there. And in 1977, during a public competition, the modern data encryption standard (DES).

Today Peter Shor’s warning about timely implementation of decisions requires special attention. Obviously, the pressure is coming because encryption technologies are deeply embedded in many different systems. For this reason, breaking them and introducing new ones can take a long time.

Not everyone predicts the race will end in a few years. For example, Roger Grimes, Security Specialist KnowBe4, announced that 2021 is likely to be the first public recognition of quantum cryptographic hacking, when quantum computers are capable of cracking traditional public key cryptographic keys. As we can observe, this has not happened yet.

Conclusion

So, in our article we examined the danger of quantum computing for classical Y2Q encryption, presented a short description of Shor’s algorithm and talked about the prospects for the development of cryptography.

It is obvious that once the entire scientific community believed in the absolute security of classical cryptographic systems. But the world does not stand still, and now we are talking not just about quantum cryptography, but about post-quantum systems. Surely, in many years people will write about Shor’s algorithm we are considering as outdated and very slow, but this is called progress…

Thank you for the attention!