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)


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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: