# 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!