## RSA explained

### May 5, 2010

I’ve been struggling to learn the mathematics behind RSA encryption. This is my “aid Memoir” I’m trying to memories.

**Key Creation**

**• Choose primes p and q**

Pick two prime numbers, e.g. 7 & 17

**• Calculate the Modulus N, where N=pq**

Multiply the two prime numbers to create N (7×17)=119

**• Choose an e, where 1 < e <(p-1)(q-1) and GCD(e, (p-1)(q-1)) = 1**

Pick a prime number e that is less than (p-1)*(q-1). (6*16)=96 and where the Greatest common devisor (GCD) of all three (e, p-1, q-1) is 1 (i.e. no other common devisors)

In This case, we pick 37.

**• Public key is (N, e)**

Public key are the two numbers N & e. (119,37)

**• Compute d, where d = e^-1 mod (p-1)(q-1)**

e^-1 mod (p-1)(q-1)

37^-1 mod 6×16

37^-1 mod 96

37*13=1 (Mod 96)

**• Private key is d**

The Private key is 13

p=7, q=17

N= 119

e = 37

d = 13

Public Key is (119,37)

Private Key is (13)

**Encryption**

We will use the cleartext “14” for this example

Encryption uses the algorithm **C ^ e = E ( mod N )**

This is Cleartext to the power of The Prime number from the Public Key = answer (Mod N (the multiplication of the original two prime numbers)

14^37= “Huge Number” (Mod 119) =63 (By my calculator)

The Encrypted text (E) is “63”

**Decryption**

Decryption uses the algorithm** E ^ d = C ( mod N)**

63^13 =C (mod 119)

63^13 = 14 (Mod 119)

63^13 = “Huge Number” (Mod 119) = 14