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

Advertisements