1. A person chooses two prime numbers ( p and q ). When these numbers are very big, it takes more time to factor their product, which is a public value to everyone ( also known to be - n )
2. Calculates Ф(n), which is: Ф(n) = (p-1)*(q-1) which determines how many numbers are prime with respect to n.
3. Takes arbitrary e that should be prime, that satisfies e < Ф(n)          e - encryption key
4. Computes d that is multiplicative inverse of e; d * e = 1 mod(Ф(n))   d - decryption key
5. Uses encryption key to encrypt the message
6. Consequently, using decryption key will give the original message

To describe RSA algorithm, following quantities are required:

1. p and q are primes
          (secret)
2. n = p * q
                        (not secret)
3. Ф(n) = (p-1) * (q-1)
     (secret)
4. e is a private key
               (secret)
5. d is a public key
                (not secret)
6. X is the original
message    (secret)
7. Y is the ciphertext
              (not secret)

Now, I wanted to stop on the 3rd quantity we have defined. It is important concept in this system. This equation determines how many of the number are relatively prime to n.
The RSA algorithm is based on an extension of Euler's theorem, which says that

a^Ф(n) = 1 (mod n)

1. a must be relatively prime to n. They will be relatively prime if their Greatest Common Divisor, GCD, is 1
2. Ф(n) = n * (1 - 1/p₁) * (1 - 1/p₂) ... (1 - 1/p_n)
   where p₁, p₂, ..., p_n are the prime factors of n

For example, the composite number 10 = 2 * 5. It has two prime factors; 2 and 5. So there must be Ф(10) = 10 * (1-1/2)*(1-1/5) = 4 integers that are relatively prime to 10 {i.e., which have neither 2 or 5 as a factor}. They are: 1, 3, 7, 9 To obtain mathematical relationship between Private Key - e { from now one PK } and secret key - d{ SK }, Euler's theorem must be extended, but I will skip this part, because to understand this you must be familiar with Number Theory, at least you could take one course.

To make the protection more secure users must choose "good" prime numbers. When I say "good" it means that they must be very large, and their difference in length must not be very big. Their product n will be made public, keeping p and q secret.
The user selects these prime numbers, p and q, where they should not be equal. If you make them equal it will be easy to factorise it by taking square root of publicly known n.
Their difference must be unpredictable, since otherwise p and q could be determined from n using this way. ( p + q ) is the square root of ( p - q )² + 4n, and q will be half the difference of ( p + q ) - ( p - q )

LAST STEP

That would be encryption and decryption.
The message that one want to remain unknown for strangers is encrypted using e. Let's assume that our message is X, so convert is to the ciphertext we must perform this: Y = X^e ( mod n )
As you can see, if we take both sides, of this equation, to the power of d we will get: Y^d = X^e*d ( mod n) ; and from about as it was said previously e*d ( mod n ) = 1, so we end up with original message that was encrypted. X = Y^d ( mod n )
So, if people want to encrypt something with RSA, they take X to the power e, and to decrypt they have to take cyphertext to the power of d. It, actually, does not matter in what order people use this keys. It can be done in any order and there will be no difference.

EASY EXAMPLE

Let's take p = 47 and q = 61. Thus 47 * 61 = 2867 and Ф(n) = (p - 1)*(q - 1) = 2760

The method I will use to determine the GCD of two numbers, and therefore whether they are relatively prime or not is called Euclidian algorithm. This algorithm is based on the theorem that states that is a = b*m + c, then GCD(a,b) is equal to GCD(b,c). To illustrate this algorithm let's us find the GCD(38,26)

1. 38 = 26*1 + 12
2. 26 = 12*2 + 2
3. 12 = 2*6

1. 2760 = 167 * 16 + 88
2.   167 =  88 * 1 + 79
3.    88 =  79 * 1 + 9
4.     79 =   9 * 8 + 7
5.      9 =    7 * 1 + 2
6.      7 =    2 * 3 + 1
7.      2 =    1 * 2

If you have a small number, a variation of Euclid's Algorithm is used to calculate the multiplicative inverse of this number. In my previous essay I showed how to do this. The idea is to rewrite all your equations, starting from the one before last and going to the first, in the form:
       (factor₁ * SK) + (factor₂ * Ф(n)) = 1
where factor₁ will be our PK. This equation is also equal to SK * PK = 1 (mod Ф(n)), because when you take both sides (mod Ф(n)) you will see that (factor₂ * Ф(n)) mod Ф(n) will be equal to 0 and you got the 2nd equation.

To get PK you rewrite one before pre-last step like this:

1. 1 = 7 - 2*3
2. Then you have 2 = 5 - 3*1     Substituting it instead of 2 in the first equation will give us: 1 = 3 - (5 - 3*1)*1 ; which is also can be written as: 1 = 3*2 - 5*1
   Now you substitute what was before it in this one
3. 1 = 7 - (9 - 7*1)*3 => 1 = 7*4 - 9*3     Again substitute
4. 1 = (79 - 9*8)*4 - 9*3 => 1 = 79*4 - 9*35
5. 1 = 79*4 - (88 - 79*1)*35 => 1 = 79*39 - 88*35
6. 1 = (167 - 88*1)*39 - 88*35 => 1 = 167*39 - 88*74
7. 1 = 167*39 - (2760 - 167*16)*74 => 1 = 167*1223 - 2760*74

Now, we have transformed it into the form: (factor₁ * SK) + (factor₂ * Ф(n)) = 1    where it was said that factor₁ is equal to our PK, so PK = 1223 , which is multiplicative inverse of SK modulo n.

Let's assume that we want to encrypt Number:= 783
I will use e to do that. Recalling that Y = X^e (mod n) we have Y = Number^e (mod n). If we substitute all known values we would have: Y = 783¹⁶⁷ (mod 2867). And it will be equal to Y = 2865. I used this program to do this.
To decrypt it, using d we got: X = 2865¹²²³ = 783   which is our original message.
Since, PK is 1223d = 4C7h = 0100 1100 0111   that can be written as 0*2¹¹ + 1*2¹⁰ + 0*2⁹ + 0*2⁸ + 1*2⁷ + 1*2⁶ + 0*2⁵ + 0*2⁴ + 0*2³ + 1*2² + 1*2¹ + 1*2⁰ = 1223
1223 = 1024 + 128 + 64 + 4 + 2 + 1 => 783¹²²³ = 783¹⁰²⁴ * 783¹²⁸ * 783⁶⁴ * 783⁴ * 783⁴ * 783² * 783¹    You might find this easier to compute

SUMMARY

1. Two secret prime numbers, p and q, are selected randomly.
2. The publicly exposed product n = p*q is calculated
3. Secret Euler's function, Ф(n) = (p-1)*(q-1), is calculated
4. A number that is relatively prime to Ф(n), which must be also smaller than Ф(n). It is considered to be either your SK or PK
5. The Multiplicative Inverse of the Number, chosen in the previous step, modulo Ф(n) is computed using Euclid's Algorithm.
6. Encrypting is implemented taking X(whose value must be in the range of n-1) to the power of SK modulo n
7. Decrypting is implemenetd taking Y to the power of PK modulo n to obtain original message.

Using MIRACL
• First of all you will have to go to this page and download the package. I have showed you very easy programs, just to make you tempted to learn how to use it in our business. There are many sources included, made in C. Download documentation file and read it; everything that describes the internal representation till the description of the code in the source files
• Get a C or C++ compiler, it's good if you have Visual Studio 6.
• Start practicing with it.

Factoring Methods ( taken from Applied Cryptography )
1. Quadratic Sieve - is the fastest known algorithm for numbers less than 150 decimal digits long and has been used extensively.
   • Multiple Polynomial Quadratic Sieve - a faster algorithm of previous one
   • Double Large Prime Variation of the Multiple Polynomial Quadratic Sieve - the fastest version of the previous two
2. Number Field Sieve (NFS) - This is the fastest-known factoring algorithm. It was impractical when originally proposed, but that has changed due to a series of improvements over the last few years. The multiple polynomial quadratic sieve is still faster for smaller numbers ( the break-even point is between 110 and 135 decimal digits, depending on implementation ). The NFS was used to factor the ninth Fermat number.

3. Elliptic Curve Method - this method has been used to find 38-digit factors, but nothing larger. For larger factors, the other algorithms are faster.
4. Pollard's Monte Carlo Algorithm
5. Continued Fraction Algorithm
6. Trial Division - This is the oldest factoring algorithm, and involves testing every prime number less than the square root of the candidate number.

Final Thoughts

 

NOTE: People, who are in the list will receive homework next week. The assignment will consist of a simple and moderate problems. The crackme will be coded to test your abilities breaking this crypto-system. I will try to find a program that uses it.

Eclipse, DAMN, CORE