# RSA Cryptography

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

😄

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

****

****

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!

Last modified 3yr ago