Will Quantum Computers break encryption?

 Will Quantum Computers break encryption?

In this article, I will show how a quantum computer works under the hood, how this new technology has the potential to break all the cryptography, in other words, it can be the ultimate cyberweapon.

How does a Quantum computer works?

Most people say that the difference between a quantum computer and a normal computer is that the normal computer used bits and the quantum used qubits. That’s not wrong at all, but is not completely accurate, the correct definition is: “ A current computer manipulate individual bits and the quantum computer leverage quantum mechanics to manipulate information; this information is represented in qubits.

They are 3 quantum properties that a quantum computer uses :

  • Superposition: the ability of a quantum system to be in multiple states at the same time until it is measured. Find out more
  • Entanglement: two or more particles are inextricably linked to each other; no matter the distance between, in other words, is the teleportation of information. Find out more
  • Interference: A byproduct of superposition, is what allows us to bias the measurement of a qubit toward a desired state or set of states. Quantum interference may therefore be disrupted by an incidental measurement of a system qubit. This phenomenon is called quantum decoherence and can be a major source of error when working with physical quantum computers. Find out more

But the most powerful and important is the superposition property:

To illustrate these quantum phenomena, let’s think about the simple game “head or tail”. It is the best example because when the coin is in the air you don´t know If is head or tail, the coin has 50% chance of being in the head and another 50% chance of being tail, but when the coin lands in your hand it collapses into one of those possibilities. So imagine that the coin when is in the air like in a superposition, like being in all 2 states at once.

This superposition is the main reason why quantum computers in the future will be more powerful than any other supercomputer. A normal computer processes information in bits; these bits can only be 1 or 0. On the other hand, a quantum computer uses qubits and these qubits can be in 1, 0, or both.

For example, a normal computer has 2 bits, the permutation of these bits can be 11,00,10,01. But this computer can only process one permutation at a time, on the other hand, a quantum computer can have all this permutation and process all the possibilities at once.

Let’s see an example with 4 bits:

The backbone of cybersecurity

Cybersecurity protocols are the basis of all the technologies that we use in our daily life, these protocols are not only an important but necessary part of the internet, without this protocol all the internet with be useless. They are 2 protocols that are essential for all the cybersecurity of the internet.

Asymmetric cryptography:

 It’s a process that uses a pair of related keys — one public key and one private key — to encrypt and decrypt a message and protect it from unauthorized access or use. A public key is a cryptographic key that can be used by any person to encrypt a message so that it can only be deciphered by the intended recipient with their private key. A private key — also known as a secret key — is shared only with the key’s initiator.

Many protocols rely on asymmetric cryptography, including the transport layer security (TLS) and secure sockets layer (SSL) protocols, which make HTTPS possible. The encryption process is also used in software programs — such as browsers — that need to establish a secure connection over an insecure network like the Internet or need to validate a digital signature.

Find out more: (https://searchsecurity.techtarget.com/definition/asymmetric-cryptography)

Hashing: 

It’s the process of changing a plain text or a key to a hashed value by applying a hash function. Usually, the input length is greater in size than the output hash value. Hashing is a one-way encryption process such that a hash value cannot be reverse engineered to get to the original plain text. Hashing is used in encryption to secure the information shared between two parties. The passwords are transformed into hash values so that even if a security breach occurs.

The 2 Quantum cyber weapons

Shor’s algorithm:

It’s a polynomial-time quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer N, find its prime factors. It was discovered in 1994 by the American mathematician Peter Shor.

If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor’s algorithm could be used to break public-key cryptography schemes, such as the widely used RSA scheme.

Find out more: https://en.wikipedia.org/wiki/Shor%27s_algorithm

That’s why this is so dangerous because RSA is used in Asymmetric cryptography, this actually means that all the internet communications are at risk of a super cyberattack; all the companies, governments, and normal people use the algorithm.

How RSA works?

  • This is the math side of the algorithm.
  • The important part is n, because is the product of prime numbers and if you know the prime numbers of n you can know the private key.
  • That’s when Shor’s algorithm comes, these prime numbers are really hard to find because are the product of a really large number so the main idea of Shor’s algorithm is to find 2 prime numbers. This algorithm is so powerful because a normal computer will take millions of years to find the answer but Shor’s algorithm has the potential to find these prime numbers in a matter of hours

The classical way to crack RSA. This is a simple program that I created, the program finds the prime numbers of a number.

As you can see the prime numbers of 15 are 3 and 5

But with big numbers is harder because there are more results. So you can understand the main picture of the math problem, imagine tries to factor a 10000000 number with all the prime numbers and try one by one…. It will take millions of years

Shor’s algorithm under the hood:

Steps of Shor’s algorithm

Grover’s algorithm

It’s a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(logN) storage space (see big O notation). It was invented by Lov Grover in 1996.

The main danger of this algorithm for cybersecurity is that it can reverse the hashed text to a normal plain text.in other words, it can crack any password.

The normal way to crack a password: A dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by trying hundreds or sometimes millions of likely possibilities, such as words in a dictionary.

Grover’s algorithm under the hood:

The conclusion:

Now with all this information, the answer to the question of Quantum Computers break encryption is……… yes.

Yes, quantum computers have all the potential to break the encryption, I think the real answer is not if these quantum computers can do it, the real question is when……

 If we see IBM’s plan for the next year we can think that we are closer to a powerful quantum computer that can break all the encryption.

But in order to make this possible, the ideal quantum computer will need a low error rate and a high number of qubits, in order to be useful.

About Pablo: I am one of the first quantum computer developers in the world, and also, I am a programmer who loves cybersecurity and focuses on prototype post-quantum solutions.

I also working on a post-quantum strategy to this threat if your company is interested you can write me an email at pablocoding2020@gmail.com  or talk to me on LinkedIn https://www.linkedin.com/in/juan-pablo-ibarbo-herrera-3798a1205/

AITECHNEWS

Related post