Looking to verify my understanding of RSA math

Question

I want to explain RSA to a programming audience with no cryptography background and I want to be sure my explanation is correct. The goal is to help them understand how RSA works under the hood. You can assume the audience knows modular arithmetic at this point. Could you please let me know if this explanation is clear or if I've missed anything critical for a lay audience? Do you think I should cover more number theory? The actual delivery will be refined later and I'll cover OAEP further along. I just want to be sure I haven't made a mistake here.

---EXPLANATION BEGINS---

RSA's security is based on factoring primes. A problem which is considered hard though there's no formal proof of that.

We start by selecting two large primes, p and q. Each should be 2048 bits. We multiple p and q to yield n.

$n = p\times q$

n is referred to as the modulus and will be 4096 bits long, which is the recommended number of bits to achieve ~128-bit security.

Our plaintext, p, is then represented as a number less than n. We also have a public key (e) and a private key (d).

RSA works as follows. The ciphertext, c, is generated by raising p to the power e modulo n:

$c = p^e mod\ n$

The plaintext is recovered by raising c to the power of d modulo n:

$p = c^d mod\ n$

So encryption then is a matter of multiplying p by itself a certain number of times modulo n. And d is a matter of multiplying the ciphertext by itself a certain number of times modulo n to arrive back at the plaintext. Another way of looking at it is that encryption involves mapping the plaintext to another number (the ciphertext) in the finite set n. And decryption is about mapping the ciphertext back to the plaintext. You can look at it mathematically like this:

$c^d mod\ n = (p^e)^d mod\ n = p^{ed} mod\ n = p$

RSA's security comes from it being easy to map the plaintext to ciphertext, but being computationally infeasible (when the keys are sufficiently large) to do the reverse unless you know the decryption key (d).

So we need to generate keys e and d such that this scheme is possible. Specifically, d needs to be the inverse of e. To do this, we can use something called the totient of n, represented by $\Phi(n)$. The totient of n is the number of elements from 1 to n - 1 that are coprime to n. Two numbers are coprime if their only common divisor is 1. Finding $\Phi(n)$ when p and q are both prime is easy. It's: $\Phi(n) = (p-1)(q-1)$

So to take a toy example, let's say p = 3 and q = 11, in that case:

$n = 3 \times 11 = 33$

$\Phi(n) = (3-1)(11-1) = 20$

So there are twenty numbers from 1 to 33-1 inclusive which are coprime with 33.

To generate the public key (e), find a value of e such that the following is true:

$gcd(e, \Phi(n)) = 1$

In other words, e should be coprime to $\Phi(n)$. By doing this, we're guaranteed to be able to find an inverse (d) to serve as our private key.

From our toy example above, e could be 3. To find the corresponding private key, we need to find a value of d such that the following is true:

$d \times e \equiv 1 \ mod \ \Phi(n)$

$d \times 3 \equiv 1 \ mod \ 20$

We can find d using the Extended Euclidean Algorithm. In this case, that would be 7.

So now that we've generated our public (e) and private (d) pair, let's encrypt a piece of plaintext encoded as the value 29. Our ciphertext is then:

$c = p^e mod\ n = 29^3 mod\ 33 = 2$

Recovering the plaintext is then:

$p = c^d mod\ n = 2^7 mod\ 33 = 29$

Some additional notes:

• Common keys for e are {3, 5, 17, 257 or 65537}.
• Notice that when we generate the private and public keys we mod against $\Phi(n)$, and when encrypting and decrypting, we mod against n

---EXPLANATION ENDS---

Answer 1

Some random comments:

RSA's security is based on factoring primes.

Actually, it's based on the hardness of the RSA problem. It is still an open question whether its difficulty is equivalent to that of factoring.

RSA works as follows. The ciphertext, c, is generated by raising p to the power e modulo n

At this stage, you probably don't want to go into the full details, but you should mention (perhaps in passing) that we never use 'textbook RSA' as you described, but when doing public key encryption, we perform 'padding' before doing the raw RSA operation.

You mentioned that you'll be covering OAEP later; you should give a few words to the effect that 'I'll cover this more fully later; this is a simplified version for now...'

So encryption then is a matter of multiplying p by itself a certain number of times modulo n.

Not an issue with what you said, but (depending on the time) might want to discuss how we raise p to such enormous powers without taking an enormous amount of time; I believe that your audience should be able to follow that.

To do this, we can use something called the totient of n, represented by $\Phi(n)$.

Actually, it is more typically represented by a lower case phi, that is, either $\phi(n)$ or $\varphi(n)$.

To generate the public key (e), find a value of e such that the following is true:

I don't know if you want to go into these sorts of details; however it is more common in practice to select e first, and then select p and q such that $p, q \not\equiv 1 \pmod e$ (which will ensure (for prime e) that $\gcd( \phi(n), e ) = 1$)

Everything else would appear to be reasonable (if simplified...)