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

### 4 Responses to “RSA explained”

1. oman Says:

do you have anything on el gamal?
i cant understand the function of it!

• mranthony Says:

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.

2. oman Says:

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…

• mranthony Says:

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.