RSA Algorithm
The RSA algorithm is based upon the difficulty of finding the prime factorization of numbers whose prime factors are large primes—say 100 digit prime numbers. The RSA algorithm works as follows:
1. Select two prime numbers p and q.
2. Form n = pq. Note that n is public and can be published.
3. Form y = (p – 1)(q – 1). Note that y is secret and not published.
4. Select an integer e such that e < n and the gcd(e,y) = 1. Note the author’s requirement that e not divide y evenly is not strong enough. For the algorithm to work, e and y must be relatively prime-gcd(e,y) = 1.
5. To encode a letter use its ASCII value. For instance ‘A’ is at position 65 in the ASCII sequence, so it is encoded as:
c = 65e mod n
The letter to be encoded is said to be a plaintext letter and the message before it is encoded is said to be a plaintext message.
6. To decode a character, you must first calculate a value d that satisfies the equation:
e×d mod y = 1 (Eq. 6.1)
where y and e are the values calculated in 3 and 4 above, respectively. Since e and y are relatively prime, we know that there exist integers d and g such that
e×d + y×g = 1 (Eq. 6.2)
We can solve this equation by using the Euclidean Algorithm with back substitution. To illustrate the process, suppose we choose p = 11 and q = 13. Then n=143 and y = 10×12 = 120. Further, suppose that we select e=19. Note that e and y are relatively prime, gcd(19,120)=1.
To find d proceed as follows using the Euclidean Algorithm as if we were looking for the solution to the gcd(19, 120).
120 = 6×19 + 6
|
6 = 120 - 6×19
|
19 = 3×6 + 1
|
1 = 19 - 3×6
|
The values of d and g are found by working backwards from the last equation in the right column. The process is to substitute using the value from the equation the right column immediately above, simplify, and repeat until you get back to equation Eq. 6.2.
1 = 19 – 3×(6)
= 19 - 3×(120 - 6×19)
= 19 - 3×120 +18×(19)
= 19×(19) - 3×(120) Note that this equation is in the form e×d + y×g = 1, where d = 19 and g = -3.
The range for the mod y function (Modulus y arithmetic) is defined to be the interval 0 … y. So, had d come out to be negative we would convert it to a positive integer by adding y, that is we would use the value –d+y for d. In this example there is no need to do so since d is already positive. Also note that d just happened to equal e in this example. In general this will not be true.
7. Using the value of d, as calculated in step 6, the plaintext character is decoded as:
m = cd mod n
where c is an character that has been encoded as described in 5 above.
.gif)
