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

May 19, 2010 at 5:03 am

do you have anything on el gamal?

i cant understand the function of it!

May 19, 2010 at 9:42 am

I do, but its not complete.

I’ve written out a simple run-through the same as the RSA one, but there’s an error in the decryption.

I’ll have a look as soon as I get a chance and will post it.

May 19, 2010 at 11:37 am

can u send me what you have for elgamal first?

may be the just the formulas?

i tried searching on the net but not as helpful as you have,…. its easier to understand here…

May 19, 2010 at 4:44 pm

Just added it as another post. I was aiming to figure out that I’ve been doing wrong first, but it should help you understand the process.