WHAT IS THE RSA ALGORITHM?

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

A simple 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.c 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

Choose two prime numbers 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

 The complete inequality is 1< e < gcd F(x) =1, but this means it has to be true for each factored term of 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 one 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 that the two numbers p and q are co-prime. That is, they have no factor between them, except 1.

There is a way to determine if the two numbers have only 1 as a 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 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, 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 Web (I was NOT going to manually go through several primes until I found a suitable pair, so I looked up a numerical example of RSA). They are p=137 and q=131. Let's do it, 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 1767,9, and it equals 1.

So, now we have everything to form our public key, which is (n,e), and the 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, which 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 to 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.

􀀀

Return to Portal List of Articles