RSA Algorithm

RSA Algorithm

Ken Wais 10/6/11

The RSA algorithm is a numerical method in cryptology to encrypt private keys for PKI digital signing.As such it utilizes some of the principles of algebraic sets and their relations. I will try to explain in plain terms how one key is created.

The Modulus

First we must understand the modulus to grasp RSA. The modulus is a way to relate number sets to each other using a base number to map one set to another. An example should illustrate the idea.

The simplest example would be 1 = 3 mod 2.What this means is if we only have two numbers we count with 0 and 1 to represent larger numbers we must put them in terms of 0 or 1. So, 3 is just going 1 beyond 2.What would 4 be? 4 would be just 2 twice so, it would be 0 again.How Ďbout 5? 5 would be 2 twice and then 1 more so it would be 1.How bout 6?6 would be 2 three times so it would be 0.Now letís put these examples together and show them below:

1 = 3 mod 2

0 = 4 mod 2

1 = 5 mod 2

0 = 6 mod 2

1 = 7 mod 2

0 = 8 mod 2

1 = 9 mod 2

Notice on the left side every time we increase the base 10 number it just keeps going between 0 and 1.Thatís because the only numbers we can use in base 2 are 0 and 1.If the base is 10 we can use 0 to 9 different numbers (0,1,2,3,4,5,6,7,8,9), and beyond that we could map small numbers to larger ones using the modulus again.As an example of a base 10 modulus we can make the base 12, and then every number we count will have to be a multiple of 12.This is what the 12 hour clock does.Again an example will illustrate this.

Midnight is 0 = 12 mod 12

1 oíclock is 1 = 13 mod 12

2 oíclock is 2 = 14 mod 12

3 oíclock is 3 = 15 mod 12


Here is a strange one. 1 =1/4 mod 5.

This equation is not integer division. It means if we divide 5/4 the remainder is 1.Mods are always integers.So one fourth of 5 is 1. You drop anything after the division.This is important because RSA uses a fraction in its algorithm.If this isnít clear now, when I give an actual numerical example below it should be.

The RSA Algorithm

First you choose two prime number p and q.

Then compute n=pq

Next form the factored function

F(x) = (p-1)(q-1).So far itís quite simple.

Next things get a little more complex. Now we have to choose an exponent e such that the following is true:

1 < e < gcd (greatest common denominator)(e, p-1) =1

and

1< e < gcd (greatest common denominator)(e, q-1) =1

Actually the inequality is 1< e < gcd F(x) =1, but this means it has to be true for each factored term of the F(x).

This means that e, (p-1), and (q-1) can have only one common denominator and that is 1. It is not important to know why p and q must have only common denominator to use RSA.It involves aspects of algebraic sets I wonít discuss here.Just know they have to have this property. What this means is the two numbers p and q are co-prime.That is the have no factor between them, except 1.

There is a way to determine if the two numbers have only 1 as common denominator. Itís called Euclidís algorithm.You take the two primes and divide them repeatedly until you get down to 1 as the remainder.If you donít get 1 as a remainder in this process then the two primes donít have 1 as their gcd.Here is an example with a table that shows how it works. On the top we have the dividend (the number to be divided), the divisor, the quotient and the remainder.We divide the two numbers across and move the divisor to the second row and repeat the process until we get 1 in a row.If we get 1, then the two numbers have only 1 as their GCD.We will use 140 and 21

 

Dividend

Divisor

Quotient

Remainder

140

21

6

14

21

6

3

3

6

3

2

0

3

2

1

1

In the first row we have 140/21 =6 (w/o the remainder). 6*21 =126-140 = 14 (remainder)

Moving the 21 to the 2nd row we have 21/6 =3 (w/o the remainder) 3*6 =18-21=3 (remainder)

Moving 6 to the 2nd row we have 6/3 = 2 and 0 remainder.

We repeat again and finally we get 1 as a remainder. This means 140, 21 have one gcd = 1

Now if we apply this procedure to two prime numbers we will quickly see they have only one gcd and itís 1.So, here is an example I found on the Net, (I was going to manually go thru several primes, so I looked up a numerical example of RSA. They are p=137 and q=131. Letís do itís Euclid table

137/131 = 1.0458. Drop the non-integer remainder and the only GCD they share is 1, so they are good primes to use. Now we are ready to compute the private key and the public key using RSA.

So, we go back to the above equations

P=137, Q=131

N = PQ = 137*131 =17947

F(x) =(137-1)(131-1) = (136)(130) =17680

Now we select prime e = 3. If we check GCD(3,136) = 1 it is.Look at the above equation to see why I plugged in that number

And GCD(3, 130) = 1 it is.

Now the hardest part comes Here, we form the modulus called d. It is

D =mod F(x)/e = mod 17680/3 = 11787.Now I must explain how this comes out like that. Alternately this is written D =3-1 mod F(x) = mod 17680/3 = 11787

The integer division 17680/3 = 5893.But remember this is not simple integer division.If we take 5893*3= 17679.17680-17679 = 1.Remember that is what (p-1) and (q-1) must equal, namely 1. So the modulus is saying take 5893, times and minus 17679 and it equals 1.

So, now we have everything to form our public key which is (n,e) and private key is (n,d).

The public key is the pair (17947, 3) and the private key is (17947, 11787).That would be the digital signature of the first sender.Notice 11787 is prime and hard to guess, that is why itís the private key.Of course in a real RSA algorithm, the prime numbers p and q would be about 125 digits long.But notice the public key is PQ and could be a non-prime number (it isnít in this case). But knowing that will never let you know the D, because D is the mod of two prime numbers, each minus 1 and only share a gcd of 1.That gets near impossible guess by brute force (trying combinations) the larger the prime numbers p and q and the exponent e becomes.To get the receiverís public and private key pair you reverse the process, but I wonít go into that.

􀀀