RSA Phase 3 – Euclidean Algorithm

We discussed a couple important aspects of this encryption algorithm, Congruence and Equivalence Classes, in 2 is congruent to 9 mod 7. Then we went over some discussion about prime numbers, but do we really know them to be prime? Today we are going to walk through the Extended Euclidean Algorithm, which is very useful for finding the Greatest Common Divisor of two numbers, which for all prime numbers should be 1.

Lets take two numbers, 23 and 7.

The Euclidean Algorithm says that we should be able to solve this equation, given those numbers…

23 = X*7 + Y

With a few moments of brain work we can solve this equation as follows:

X = 3
Y = 2

We know Y = 2 because 23/7 = 3r2. You can see the modular arithmetic at work already!

23 = 3*7 + 2 = 21 + 2


We then take the two largest numbers on the right side of the equality and do this again:

7 = 3*2 + 1

And again until we get a remainder of 0.

2 = 2*1 + 0

And then we take a single step backward and declare our final remainder as our Greatest Common Divisor.

23 = 3*7 + 2
7 = 3*2 + 1
2 = 2*1 + 0
GCD(23,7) = 1

This works across the board, Let’s look at a few.

145 = 1*123 + 22
123 = 5*22 + 13
22 = 1*13 + 9
13 = 1*9 + 4
9 = 2*4 + 1 <<
4 = 4*1 + 0
GCD(145,123) = 1
----
512 = 3*160 + 32 <<
160 = 5 * 32 + 0
GCD(512,160) = 32
----
122 = 9*13 + 5
13 = 2*5 + 2
5 = 2*2 + 1 <<
2 = 2*1 + 0
GCD(122,13) = 1
----
139 = 2*64 + 11
64 = 5*11 + 9
11 = 1*9 + 2
9 = 4*2 + 1 <<
2 = 2*1 + 0
GCD(139, 64) = 1

You can do more with this number, by extending the Euclidean Algorithm. This extension is actually simply to back track through it and solve it interms of the two numbers we are testing against. These numbers may come in handy later, when doing our solving for the decoder values in our RSA Encryption scheme, observe. In our first example we solved the GCD of 145 and 123 to be 1. This last line can be expressed in the following format:

1= 9 – 2*4

We can substitute the previous line, also in this format, into the spot where the four is.

1 = 9 – 2 * (13 - 1*9) or 1 = 9 – 2(13) + 2*9 or 1 = 3*9 – 2*13

Which is a true statement. We continue along this road all the way back to the top, replacing the multiplicands as we go.

1 = 3*(22 – 1*13) – 2*13 = 3(22) – 3(13) – 2(13) = 3(22) – 5(13)
1 = 3(22) – 5(123 – 5*22) = 3(22) – 5(123) + 25(22) = 28(22) – 5(123)
1 = 28(145 – 1*123) – 5(123) = 28(145) – 28(123) – 5(123) = 28(145) – 33(123)
1 = 28(145) – 33(123) =  4060 – 4059

This is the process that we will use in a couple days when we finally step into the RSA Encryption Code. We now have all the tools to be able to piece it together.it isn’t a trivial process, even now. Recognize that there are books written on the RSA Encryption algorithm. There are entire tomes written to provide insight into the minutia of the algorithm, and others like it. What we have here are the pieces. Saying you understand the RSA code right now analogous to asserting your understanding of pointers in C/C++ because you can type on a keyboard at 12+ words per minute.

We all have our humbling experiences. This is one of mine.

  • jo from Germany

    You just saved my exam. Thank you very much, sir!