CS70 Guide

Searchâ€¦

Discrete Math

Probability

Extra Probability

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?

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

ðŸ˜„

The RSA Cheat Sheet

$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$(N, e)$

$d = e^{-1} \pmod{(p-1)(q-1)}$

$E(x) = x^e \pmod{N}$

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

Last modified 1yr ago

Copy link