Is this toy RSA demonstration flawed?

Question

I want to present the basics of how RSA works to an audience of beginners in cryptography. The problem is that I am lightyears from being an expert.

After reading about how RSA works in wikipedia, this is the "toy" demonstration I created:

---

• We shall assume that Bob has a secret natural number that he wants to tell Alice.
• We shall assume that they will be speaking to each other, and there are lots of people around (including cryptographers!) that can hear them.

• This is how the talk will proceed:

  1. Bob says out loud: "Hey Alice, I want to tell you a secret natural number!"
  2. Alice replies out loud: "Ok, wait a second, let me create the encryption keys."
     • Now Alice secretly chooses two distinct prime numbers, $p$ and $q$, and calculates two things: $n = pq$ and $\lambda = \text{lcm}(p-1, q-1)$.
     • Then Alice secretly chooses any number $e$ which satisfies $e < n$ and $\text{gcd}(e,λ) = 1$
     • Then Alice says out loud the values of $n$ and $e$.
  3. Alice says out loud: "Very well, the public key is $(n=391, e=75)$!"
  4. Bob replies out loud: "Understood, give me a second!"
     • Then bob takes his secret number $m$ and calculates $c = m^e \text{ mod } n$ and says it out loud
  5. Bob says out loud: "Okay, after encrypting my secret number I got 240"
  6. Alice replies: "Great! I've got your secret number!"
     • She did it by first calculating $d = e^{-1} \text{ mod } \lambda$ and then calculating $m = c^d \text{ mod } n$.

• Then I will choose two people in the audience and let them do it, with everyone else listening, and claim that this is basically what happens with RSA encryption. The rest of the audience will not be able to find out the message efficiently, even though they heard absolutely everything.

---

The above is what I plan on presenting.

QUESTION: I don't want to be a Dave. I think I'm not a Dave because I am following RSA. Are there any big problems with the above? Does it present the idea of RSA correctly? What gotchas should I mention, if any?

---

Bonus points for anyone who figures out Bob's secret number above. Of course I know it can be done by brute force because I chose ridiculously small prime numbers...

Answer 1

You wouldn't be a Dave for presenting RSA, but you would be a Dave for following this description to implement anything, and you risk creating Daves with this presentation. I'm not saying you shouldn't do it, but you should emphasize that this is only the mathematical basis of RSA and a lot more is involved in making it do something useful.

Your description is mostly correct, with just one minor error: in any remotely modern use of RSA, key generation is done a bit differently: first you choose either $e=3$ or $e=65537$, and then you choose $p$ and $q$. It's done that way for performance, but it also highlights an important thing: $e$ and $d$ are not symmetric. You cannot swap them. You cannot “encrypt with the private key”: that's just a bit of popular nonsense that stems from an incomplete understanding of RSA.

There are also few inaccuracies that don't really matter. Alice calculates $d$ at step 2, not each time she receives an encrypted message. Or Alice might not calculate $d$ at all, because rather than calculate $m = c^d \bmod n$ to decrypt a message, she might perform an equivalent calculation nicknamed “CRT” which is a bit faster. But at this level of detail, these are unimportant.

This is a nice application of mathematics that's generally understandable by people with just a bit more than high school math. But it is of no direct use to anyone using RSA: your cryptography library hides the details for you. In fact, ideally, when you're writing code that uses cryptography, you shouldn't have the letters "RSA" in your code any more than you should have the letters "AES". But in the real world, programmers often need to care about more details. And as a point of interest for non-programmers, this does not give an accurate insight in the kinds of problems that cryptographers and cryptography implementers work on.

As a cryptography implementer, here's the kind of things I've worried about that are related to RSA:

• Am I using the right tool for the job? RSA is more popularly known for encryption, but signature is at least as important an application. Signature is not quite dual to encryption: there are symmetries, but there are also many differences.
• Is my implementation of computation on large integers (bignums) vulnerable to timing attack and other side channel attacks?
• Is my use of RSA properly padded? Plain RSA has more holes in it than Swiss cheese. The reverse side of the coin of RSA's mathematical simplicity is that it's easy to construct relations involving plaintexts or ciphertexts. For example, $c_1^d c_2^d = (c_1 c_2)^e \bmod n$, so if I happen to know what $c_1$ and $c_2$ decrypt to, I can decrypt $c_1 c_2$. And that's just the simplest example.
• There are two ways to solve this problem. One is to restrict what gets encrypted. This is the approach in RSA-KEM, where RSA is used solely to encrypt a freshly generated random number. Not a number within a certain range or anything fancy like that: it would defeat the point. And then you have to use that random number in a very specific way. The other solution is to add padding, which restricts which ciphertexts are valid, in order to break mathematical relationships between ciphertexts.
• Oh, but if we restrict which ciphertexts are valid, then we open a whole class of attacks: padding oracle attacks. The basic principle is that Eve sends a message $c$ and gets Alice to try to decrypt it. So Alice calculates $c^d \bmod n$ and finds that $c$ is invalid. She might reply to Eve, or she might keep silent but Eve still finds out that the message is invalid because Alice doesn't do what she would do with a valid message. Maybe the difference is even just in the timing of Alice's response. Whatever it is, if Alice is not careful, merely probing with a few thousand ciphertexts, just to know whether each ciphertext is valid or not, can let Eve reconstruct the key. This type of attack is known as an adaptative chosen ciphertext attack.
• Historically, the first padding mode for RSA was the one known as PKCS#1 v1.5, and it is prone to this kind of oracle-based adpatative chosen ciphertext attack, mainly Bleichenbacher's attack (one of them) and Manger's attack. The math behind this attack is a little heavier than the basics of RSA, but it doesn't need anything advanced, it just requires somewhat more equations.
• Historically? Not just historically. Bleichenbacher's original paper was published in 1998. The latest variant of his attack, with practical impact on many TLS implementations, was The Nine Lives of Bleichenbacher's CAT, published in 2018. Another year, another Bleichenbacher variant.
• PKCS#1 v.5 is deprecated, but still in real-world use. For encryption, OAEP should be used instead. For signature, PSS should be used instead. They aren't panacea, but they're considerably easier to get right. They're more complex functionally than PKCS#1 v1.5, but they leave less room for subtle implementation mistakes that break the security.
• Decryption is the hardest operation to implement, because it combines the secret key with an input (the ciphertext) that's potentially chosen by an adversary. After calculating $m^d$, you need to decode the padding, and this is where mistakes are very easily made. The slightest timing difference in reacting to invalid padding can allow an adversary to reconstruct the key via Manger's attack or Bleichenbacher's attack.
• Signature is usually easier than decryption because the input is more constrained. Encryption and verification are easier because they don't involve the secret key. But that's not to say that they're easy. For example, even in the past few years, implementations of RSA signature verification have been caught forgetting to verify some parts of the input, allowing forged signatures to go through — another type of attack due to Bleichenbacher.
• RSA key generation must obviously involve a random generator, and getting random generation right is a hard problem. (Fortunately your operating system often solves it for you. I'm not so lucky: I often work on the part of the operating system whose job it is to solve it for you! But if your operating system solves it for you and you don't hook directly onto that, you're definitely being a Dave.)
• RSA encryption must also involve a random generator, because it must not be deterministic. If encrypting the same message twice lead to the same ciphertext, it would be very easy to guess mostly-predictable ciphertexts. For example, if I know that a ciphertext is the encryption of either "Yes" or "No", with a deterministic public-key encryption scheme, I would just need to encrypt those two plaintexts, and to compare the results with the ciphertext. Thus all public-key encryption schemes are non-deterministic. PKCS#1 v1.5 and OAEP both do it by concatenating the message with some random bytes, as part of the padding. PSS also uses random padding, although for signature the randomness is not an absolute necessity.
• Of course there's the usual risk of implementation mistakes. What if someone claims their public key has $n=0$? or $e=1$? or $e=n$? or $n$ is a 1210463558412104635584-bit number? or $n$ is a 2049-bit number?

Twenty years of Attacks on the RSA Cryptosystem by Dan Boneh is good reading. 20 years later, a lot of it is still relevant. RSA is so difficult to get right that there's a push to stop using it. Of course, it helps that elliptic-curve cryptography can do pretty much everything that RSA can do, and for the most part does it faster and with smaller ciphertexts and signatures. ECC math is considerably harder, but it's easier to translate to secure implementations (perhaps not so much for intrinsic reasons than because people have learned from RSA and ECC is standardized with formats and protocols that leave less room for mistakes).

Answer 2

Are there any big problems with the above? Does it present the idea of RSA correctly? What gotchas should I mention, if any?

Alice says out loud: "Very well, the public key is (n=391, e=75)!"

In general, the public key needs to be transmitted by an authenticated channel. Otherwise, Eve can simply say "I'm Alice, here's my public key".

This would leave Bob with a secure channel to Eve, rather than to Alice, which doesn't do him much good.

Maybe Bob hears two different people say "I'm alice, here's my public key". How does he decide which one to trust? The analogy breaks down here, because people have voices that are relatively unique.

Then bob takes his secret number m and calculates c = (m^e) mod n and says it out loud

m is not well-defined, and this may or may not be a problem.

Most people will naively interpret m to be a "message", which is something meaningful Bob wants to send to Alice. Meaningful information has structure, and structure can be guessed.

Additionally, Eve could simply iterate over all the values of m (in order of likelihood to save time), and compute $c' = m'^e \bmod N$ and check if $c' = c$. She can learn the value of m by doing this.

There are two solutions to this problem:

• One is to use randomized padding. This prevents the guess-and-check attack.
• Send a randomly-generated value for m, and use that value as a key for a symmetric cipher

The second option is far more practical. RSA cannot encrypt very large messages. Using it directly on the plaintext will be slow and much more fragile.

There is another issue with the malleability of unpadded "textbook" RSA. Anyone can take two ciphertexts $c, c'$ and multiply them together and get another valid ciphertext.

Suggestions

• Mention that the description you are giving omits details that are crucial for security in order to present a simplified explanation of the core algorithm
• Instead of Alice and Bob shouting at each other, have them pass notes through an untrusted and/or malicious courier.
  • This will help to highlight the vulnerability to the man-in-the-middle attack
• Cast Alice and Eve as twins
  • This highlights the need to authenticate who you think you're talking to. Is Bob talking to his friend Alice, or her evil twin sister Eve?