RSA Cryptography

Introduction #

The internet is built upon the fact that stuff needs to go from point A to point B quickly, accurately, and securely. We’ll talk about the secure part of that now (the accurate part will be addressed soon!).

One of the ways we can make sure our top-secret messages can’t get intercepted is to encrypt them- mix them up to become incomprehensible using some secret code, then decrypt it at the other end. This has a major problem though- how can you agree to use the same secret code as someone else if you’ve never met them before?

RSA (named after creators Rivest, Shamir, Adleman) is an encryption scheme that takes advantage of public keys to solve this very problem. In the RSA system, everyone broadcasts their public key all over. When encrypting a message, the sender can lock their message using their private key paired with the sender’s public key, such that only the sender themselves can unlock the message using their own private key.

This poses yet another problem: how can we choose these public and private keys so that they work nicely with each other? Well, we can use modular arithmetic of course!! :smile:

The RSA Cheat Sheet #

Variables:
-$p, q$are two distinct prime numbers.
- $e$is relatively prime to $(p-1)(q-1)$.
- $N = pq$
- $x$is the original message; $y$is the encrypted message

Public Key: $(N, e)$
Private Key: $d = e^{-1} \pmod{(p-1)(q-1)}$****

Encryption: $E(x) = x^e \pmod{N}$
Decryption: $D(y) = y^d \pmod{N}$****

Example #

Let our two prime numbers be $p = 5, q = 11$. (In the real world, these would be much larger for security purposes- but let’s not make this too hard on ourselves!)

The first step is to choose our public key. We know e must be relatively prime to $(p-1)(q-1) = (4)(10) = 40$. A small number that satisfies this is $3$, so we can go ahead and use that. Therefore, our public key is $(N, e) = (55, 3)$.

The next step is to compute the private key. Using the formula, $d = 3^{-1} \pmod{40}$. We could use Euclid’s Extended Algorithm to compute this value, which ends up being $27$. Therefore, $d = 27$.

After we have computed our keys, we must encrypt the message. This yields $y = x^3 \pmod{55}$for some arbitrary message $x$.

Finally, we must decrypt the message by passing $y$into the decryption formula. This yields $x = y^{27} \pmod{55}$.

If all goes well, the decrypted message should be the same as the original message!