Explaining RSA to non-scientists

Question

I am to give a small lecture on quantum computing in a months' time and I want to shortly give intuition to the fact that Shor's algorithm shows that quantum computers will break RSA. Ideally, I would just state that we have this "evil algorithm" shown by Shor which does prime factorization "much faster" than we know to be possible on normal computers. My problem is that these people don't know what RSA is, they don't know that all numbers consist of prime numbers... they barely know what prime numbers are.

So how I illustrate the concepts of RSA and its relationship to prime numbers without the use of "complicated math"? (I don't want to start throwing around too many terms like modulus and stuff like that).

I was thinking of finding some drawings of keys to illustrate how asymmetric cryptography works, but I feel like there's a decent leap from that to just stating that "hardness of prime factorization is necessary for RSA to be secure".

Any input is greatly appreciated

Answer 1

This should be the flow of the description of RSA

1. RSA is a public key crypto system that everyone in the room who doesn't live in a cave uses pretty much every day. If you are using a computer to get on the internet, chances are you use RSA a lot.
2. Being a public key crypto system that means there is a public key that everyone knows and can use to encrypt messages and send them to you. Decrypting those messages is done using a private key that only you have. Pictures of Alice and Bob are always helpful here.
3. RSA works by using numbers of the form $N=p\cdot q$ where $p$ and $q$ are prime. If I have $p$ and $q$, then computing $N$ is really easy. But if I give you $N$, it turns out that breaking $N$ apart into the primes $p$ and $q$ is really hard.

Everyone can understand the math in that description. If someone has a hard time believing that breaking $N$ into $p$ and $q$ is really hard, then show them this

cb 12 fd 3b 32 8c 65 17 ff 39 2f 25 27 e3 80 ba bf d7 e4 5f 9a 65 a9 96 70 96 ef f9 49 36 79 97 e4 22 23 4c 9d af 5b 27 56 ef 6a 36 3f 4a 5d d1 44 fb 5d ca 21 7a f3 7c 39 cb ab 07 1c 6a ec 2c 21 64 37 1d 16 11 73 3f 7e 1f 68 a9 ea b5 bd 7a 05 6d 38 05 8d ef ee 23 1c e2 cf ec aa 22 d9 4e 84 47 38 c2 cd bc 1b 72 51 a3 64 46 f0 55 95 57 ee de 87 db 39 96 57 c0 42 58 1b 48 bc 5c 79 20 d9 96 4e e9 49 86 67 78 4f fe 4b 66 b0 f6 7d b9 e7 07 de c6 da d8 20 96 65 a0 de 4e a0 c4 76 f3 41 e7 e4 de c0 32 47 8d 5f a9 96 09 b8 46 5e e8 c0 3e d1 d0 69 e8 4c 26 3c 8e 69 1c 01 eb 61 ec ec 77 f0 e9 c2 fe 2a bf 8d 68 c2 1a 55 7d 61 ac 85 c8 f7 16 e2 a0 73 97 ff 26 5c 05 38 e6 e1 a7 89 13 d6 ac 13 aa 7e 44 87 83 07 ab f2 da a6 cf 38 a7 6b cb 17 07 62 08 a9 10 8e 58 8d 73 c6 e9

That is the $N$ that Bank of America uses and tell them that if they really think you are wrong, then the two of you should get together after the presentation so that you can go make a lot of money.

Personally I also like to show off pictures like this

Those are the inventors of RSA (Rivest, Shamir, and Adleman). By their picture they are obviously very smart, so the audience should just trust you that they know what they are doing.

In other words, if the audience doesn't need to understand all of the details of RSA, don't even try. Give them just enough that they can understand what they need to know. If they want more, deflect and take it offline as much as possible. Otherwise you will loose everyone else and probably the person asking the question.

Use lots of pictures and try to add some humor.

Answer 2

You could use a Venn diagram. Make a circle that symbolizes the entire keyspace, then make another circle which only slightly intersects with the first; this second circle symbolizes only the keyspace of RSA keys. What you want to communicate is that an attack of the algorithm consists of numerous guesses about what the key could be, and the maximum number of guesses is limited to the size of the keyspace. Therefore, since RSA keys are only prime numbers, they are a smaller subset of all numbers, and are therefore symbolized by the second circle. Meaning that if you get a quantum computer to guess the RSA key at a significantly faster rate than modern computers can guess, then it can run through all the guesses contained within the second circle much more quickly than it could run through those of the first circle, because the second circle has fewer numbers in it than the first.

The point is to get the layman to understand the concept of the keyspace. The smaller the keyspace, the fewer guesses are required in order to compromise the algorithm. That's the principle that's involved, because the keyspace of an asymmetric algorithm like RSA is significantly smaller than the keyspace of a symmetric algorithm like AES.

Answer 3

RSA is an asymmetric algorithm that uses two keys: a public key and a private key. The private key uses calculations based on numbers generated using two large random prime numbers. Prime numbers are numbers - without fractional part - that cannot be divided by any other number without fractional part. The public key mainly consists of a number that is the multiplication of both numbers.

RSA can be used to build a secure system as long as it remains impossible to revert the public key into the private key. The only way to do that is to factorize the large number. Factorization is to take the very large number that is the main part of the public key and use it to derive the two prime numbers representing the private key. This should be impossible to do if the numbers are large enough. To have any kind of security the numbers of the private key consist of about 309 decimal digits and the larger number of a 618 digits - a 1024 bit RSA key pair. Usually the numbers are however at least double that size to form a 2048 bit key pair.

Shor's algorithm can be used to perform crypt-analysis. It is an algorithm designed to run efficiently on quantum computers. If it would be possible to run that algorithm then the factorization of the two prime numbers would become feasible. The only thing holding it back is that quantum computers are not big enough. Quantum computers rely on a memory element called a qubit which is able to store multiple values at once.

To factor a 2048 bit public key using Shor's algorithm you'd need four thousand to ten thousand interconnected qubits. Current quantum computers only have about 50 qubits and operate in limiting experimental environments. They can only be used to solve a Sudoku - something that a classic computer can easily do within just part of a second. To build a larger scale quantum computer a lot of issues need to be solved: interconnections should be possible between many qubits and the qubits would need to become much more reliable.