RSA Full Explanation

Hey! If you're here, it's probably because you're coming from my video on YouTube about RSA Encryption (https://www.youtube.com/watch?v=EY6scAHNgZw). Thanks so much for watching!

For those of you interested, here is a full explanation of all the math behind how RSA Encryption works, including the specific choices I used in my implementation for this video (several of which are intentionally non-standard for educational purposes).

As you know from the video, I have set up a public key which can be used to send me messages. The public key consists of the public modulus, n, and the public exponent, e.

The values of n and e I chose for this video are:

n = 1000000000100000000002379, e = 65537

To send an encrypted message, first convert it to a number, m (more on how this is done in the appendix). Then compute m^e (mod n). This is the encrypted message. Note that computing m^e (mod n) can be done very efficiently since there is a modulus (otherwise the numbers would get way to big to even hope to compute). See https://en.wikipedia.org/wiki/Modular_exponentiation for more details.

To decrypt the message, I will use my private decryption exponent, d. d is chosen to have the property of reversing exponentiation by e in mod n, as in (x^e)^d ≡ x (mod n) for any number x. The encrypted message is of the form m^e (mod n), so to decrypt, I simply raise this to the power of d, which gives me (m^e)^d ≡ m, the original message. Again, this modular exponentiation can be computed very quickly.

The security of RSA lies in the fact that there is only one value of d that achieves this effect, and it's calculated with knowledge of the prime factors of n: p and q, which are secret (ensured by the fact that we don't know any efficient algorithm to factor big numbers). However, if you watched the video, you know that I have intentionally made n small enough so that a computer can factor it into the factors p and q, so if you're interested in breaking it and reading the messages with me, go for it!

Specifically, d is the multiplicative inverse of e in mod phi(n), where phi(n) counts how many numbers less than n are relatively prime. In modular arithmetic, the multiplicative inverse is "the number you multiply by to get 1." So d, the multiplicative inverse of e in mod phi(n) is a number such that e*d ≡ 1 (mod phi(n)). Due to some cool properties of number theory, when you exponentiate in mod n, the exponent "lives" in mod phi(n). So long story short, when you compute (m^e)^d = m^(e*d) (mod n), e*d ≡ 1 (mod phi(n)), which means you get m^1 = m. Also due to some cool properties of number theory, phi(n) = (p - 1)*(q - 1) when n is the product of two prime numbers, p and q. Computing phi(n) in general is actually very difficult, but if you know the prime factors, it's easy! To find the value for d (as in, compute the multiplicative inverse of e in mod (p - 1)*(q - 1), you can use the Extended Euclidean Algorithm: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).

Note that not all numbers have multiplicative inverses in modular arithmetic, so e must be chosen properly. Specifically, e must be relatively prime to phi(n) = (p - 1)*(q - 1), meaning it does not share any factors with (p - 1)*(q - 1). This ensures that d exists.

Appendix:

To convert a piece of text into a number, we will use ASCII: https://en.wikipedia.org/wiki/ASCII. In ASCII, each character gets assigned a number from 0 to 255. In the video I used the example of ":" which is the number 58 and a "D" which is the number 68 :D

For longer pieces of text, the system we'll use here is to string the digits of each character together into a longer number. For example, the word "encrypt" would get transformed into 101110099114121112116. ALL LEADING ZEROS ARE ALWAYS INCLUDED!!! As in the character ":" should be interpreted as 058. Make sure you understand how this example works before you proceed if you are trying to crack the code. Note that this way of doing the encoding is not very efficient, since the numbers are being represented in base 10 instead of base 256 or base 16. I chose to do it like this for the sake of example :)

Since these numbers get very big very fast, at a certain point they will start being bigger than the public modulus! This is a problem because in modular arithmetic, everything has to be less than the modulus. So a common solution (and what we do here) is split the message into chunks, applying the RSA encryption to each chunk separately. For our purposes, we will use a chunk size of eight characters. Again, note that in more practical applications this chunk size would be a lot bigger. But we're trying to keep the numbers relatively small. So the output of the encryption is actually a list of numbers, not a single number. The first number corresponds to the first eight characters, the next number corresponds to the next eight, and so on.

**UPDATE** I had to change the encoding slightly to avoid YouTube's spam filter automatically deleting comments. Long story short, what you need to know is that the first 30 characters of every comment is now going to be unaltered (only the rest of the comment is going to be encrypted), and the chunk size is still eight, but every three digits of every number, there is a random English word inserted.

That's it -- happy encrypting!