RSA Encryption & the Quantum Computer Threat— A very simple explanation

Learn in detail how prime numbers lay the foundation of the widely used RSA encryption and why Quantum Technology can break it.

Increasingly we hear about how Quantum Computers are on the rise and how they could threat our current encryption systems. And there is a fair reason to worry. The White House is in fact exploring possibilities to limit China´s access to these innovations, since Quantum Computers could soon hack literally everything and destroy our internet security. If the technology ends up in the wrong hands, meaning even just one person, we are all at risk.

But let´s understand how exactly these super computers pose a threat!
I´ll keep it as simple as possible with some visual explanations for you to get smart on the topic.

Our encryption model, the commonly used RSA, is based on prime number factorization. It is easy to multiply two prime numbers like 3 and 7, making up 21, however as numbers get bigger, let´s take 7393 and 739391, it takes a computer decades to find out the prime factorisation of 5466317663. Everything is based upon this set-up and we´ll see in detail how exactly in a moment.

Let´s go through it step by step

1. The public key n // First to generate your public key n, you need to find two prime numbers that you multiply. Let´s take 17 and 11, they make n=187.
   The prime numbers you used are secret, and should not get public.
2. Finding Φ(n) // How many integers does n not share a common factor greater than 1 have? If you scroll down a bit, I created a visual explantation on how to find it for any number.
   Finding Φ of two multiplied prime numbers is very simple, and you use this equation.
   (Prime Number 1–1) x (Prime Number 2 -1)
   In our case it would be (11–1) x (17–1) = 160.
   Therefore as only you know the secret prime numbers making up n, it is very quick to calculate Φ(n).
3. Finding the encryption key = e // To do that you need to identify a number between 1 and Φ(n), that is coprime with n = 187 and Φ(n) = 160. Coprime numbers do not have any common factor other than 1. In our case e=3.
4. Finding the decryption key = d // In this case e *d = 1 mod Φ(n), therefore in our case d = 267. Other possible decryption keys can be 427, 587, 747 and 907.
5. CONGRATULATIONS! We now have n= 187, the encryption key = 3 and decryption key = 267.
6. Encrypting a message = c// Bob encrypts “hi” with the ASCII code, returning him 104,105. We use the formula M^e mod n and get returned our encrypted message = c = 59,95.
   Now Bob sends it over to Alice, and no one can decrypt it except for her.
7. Decrypting a message // We use the formula c^d mod n and get returned 104,105 in the ASCII code = “hi”.

RSA Encryption — Visual Explanation

Phi of a Number

Trap door functions

The RSA algorithm uses so called trap door functions, basically easy to do in one way and hard to do the other way round, yet not impossible.
Let´s see two examples.

Get Tech Talk With Alex’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

EASY // Prime number multiplication
HARD // Prime number factorization

EASY// Φ(n) knowing the secret prime numbers
HARD // Φ(n) without knowing the prime numbers making up n

So imagine you are a hacker and know n of someone else, it would take you decades if not hundreds of years, even with a powerful computer, to calculate the prime factorization and then find the decryption key. Well, with quantum computers that will take seconds.

“It is estimated that a powerful quantum computer, for example a 4,099-qubit one, would only need 10 seconds to break the same RSA encryption that would require 300 trillion years from traditional computers. No quantum computer has reached this level yet” — www. csis.org

It is therefore time to prepare for post quantum cryptography, protocols that keep private information safe in the future (especially our bank accounts!).

An initiative worth quoting is the program and competition NIST Post-Quantum Cryptography Standardization, led by NIST itself, to update their standards to include post-quantum cryptography.

NIST Post-Quantum Cryptography Standardization - Wikipedia

Create public and private keys yourself

I have found this great website, you can use to develop public and private keys, as well as encrypt and decrypt messsages.

RSA Calculator by Syed Umar Anis

Disclaimer: The author of this article assumes no responsibility or liability for any errors or omissions in the content of this site. The information contained in this site is with no guarantees of completeness, accuracy, usefulness or timeliness.