Quantum Computing and Modern Cryptosystem

If not redirected, please click here https://www.thesecuritybuddy.com/encryption/quantum-computing-and-cryptography/

Quantum Computers are computing systems that make use of Quantum Theory. They are different from digital computers and are much more powerful. Quantum Computers are still in nascent stage. But, once they are in use, they can break modern cryptosystem.

Let's understand what Quantum Computers actually are and how they can break modern cryptosystem.

Evolution of Quantum Computers

Until the 19th century, Newtonian theory dominated physics. But, in early 20th century, physicists discovered that the laws of classical mechanics do not apply at the atomic scale.

In 1900, German physicist Max Planck introduced Quantum Theory as per which energy exists in individual units called 'quanta'.

Further developments on Quantum Theory were made gradually, as per which :

• Energy, like matter, consists of discrete units, rather than solely as a continuous wave.
• An elementary particle like an electron or a photon, can behave like either a particle or wave.
• Movements of elementary particles are random and unpredictable.
• The more precisely the position of some elementary particle is determined, the less precisely its momentum can be known. In other words, the more precisely one value is measured, the more flawed will be the measurement of the other value.

Later, the theory of quantum superposition was developed. As per this theory, any two quantum states can be added together or superposed to create another valid quantum state. In fact, as long as we do not check to see the state an elementary particle is in, it can be in all possible states simultaneously.

To illustrate the above principle, a thought experiment called Schrodinger Cat was described by Erwin Schrodinger in 1935. As per this :

Suppose, a cat is pinned up in a steel chamber along with a device that contains a tiny bit of radioactive substance, an atom from which may decay in an hour. And, when the atom decays, it would shatter a small flask of hydrocyanic acid killing the cat.

So, it would mean, the cat will be alive as long as no atom decays. But, if it does, the cat will be killed by the poisonous hydrocyanic acid. But, we would not be knowing whether the cat is alive or dead as long as we break the steel chamber.

So, to draw an analogy, the cat will be in a state of superposition of being alive and being dead, as long as it is in the steel chamber. And, when we would break the steel chamber, the cat will be either alive or dead.

And, as per theory of entanglement, two elementary particles can be entangled with each other, so that there is a correlation between the states they are in. For example, two electrons can be entangled such that both of them always spin in opposite directions. Quantum state of each particle cannot be described individually, instead both the particles will be in a quantum state as a whole.

And, based upon the principle of superposition and entanglement, Quantum Computers are evolved.

In a digital computer, a bit can be in a state '0' or '1'. So, n bits can represent exactly one value of the possible 2ⁿ values. We can apply some operation on it and convert it into some other value.

In case of Quantum Computers, elementary particles like an electron or a photon is used. This elementary particle called 'qubit' can be in state '0', '1' or in superposition of '0' and '1'. So, it is possible that n qubits are in a superposition of 2ⁿ states simultaneously. We can apply some quantum operation on these n qubits and change its state.

And, this theory enables Quantum Computers to write programs in a completely different way, which is much more powerful than classical digital computers.

How Quantum Computers can break Modern Cryptosystem

Modern cryptosystem relies heavily on the fact that, it is computationally infeasible to factorize a large number into its prime factors. For example, in an RSA cryptosystem, an attacker can easily derive the secret keys if he can take one particular parameter and factorize it into its two prime factors.

But, in Quantum Computing, a large composite number can easily be factorized into its prime factors in real time.

Let's understand how it can be done.

Let's say,

N = a product of two prime numbers p and q

x = a number not divisible by p and q

Let's take the series :

x mod N, x² mod N, x³ mod N, x⁴ mod N ...

As per Number Theory, these numbers in the series will repeat themselves after a period d and d will surely divide (p-1)(q-1)

So, in a Quantum Computer, we can perform the steps below :

• We can take all the numbers of the above series and create a superposition of all the numbers.
• We can then apply some quantum operation to reveal the period d. As said earlier, the numbers repeat themselves after a period d.
• We can repeat the steps with different values of x, which would give different values of d.
• If we can get enough different values of d, we can derive (p-1)(q-1), as d always divides (p-1)(q-1).
• From (p-1)(q-1), we can calculate pq which is equal to N.

So, we can first reduce the problem of factorization into another problem and then use Quanum Theoy of superposition and entanglement to derive the unique prime factors, which in effect beak the modern cryptosystem.

This was just an introductory article to give some basic information on Quantum Computing. Hope you liked it.