# Looking to verify my understanding of RSA math

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$$

• 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---

• a few quick comments: 1. you use p for both the plaintext and one of the prime factor, it might be very confusing for the audience. 2. Are they supposed to know what "128 bits of security" means? 3. If they understand what "polynomial time" means, the explanation of decryption as "c multiplied by himself d times is misl – Geoffroy Couteau Feb 16 at 0:27
• woops, miscliked the post. ... is misleading, for computing c^d this way would take exponential time (unless d is very small, in which case the scheme can be broken in polynomial time). I have more comments which I might develop in an answer later, but I am on my phone right now :) – Geoffroy Couteau Feb 16 at 0:29
• Make sure you point to the security issues of textbook RSA, such as malleability, and emphasize the need for proper message padding to avoid attacks due to a low exponent without padding. – yanjuna Feb 16 at 1:01
• We need a name other than $p$ for the plaintext; the usual such name is $m$. Emphasis should be made that $n$ and $e$ are public, allowing anybody to encipher. You describe textbook RSA which has serious weaknesses: in particular, enciphering a plaintext taken from a small set like a class roll is insecure, because a guess can be verified; it should at least be mentioned that correct use of RSA uses a random-like $m$. $\phi(n)=(p-1)(q-1)$ when $p$ and $q$ are distinct primes. RSA is no harder to break than factoring $n$ into primes (we know no proof of the converse). – fgrieu Feb 16 at 8:03
• @fgrieu If I am not mistaken, Although we don't have proof of that breaking RSA is equivalent to factoring in general models, we have proof that it is in the generic ring model. This not relevant to the question though. -;) – Marc Ilunga Feb 16 at 23:15

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...)

• I'll add a bit on fast exponentiation. – Bastien Feb 16 at 8:30