ATTENTION READERS! Lucky's VB Gaming Site is no longer active. For updated game programming information and tutorials, please visit The Game Programming Wiki!
RSA Encryption, The Euclidean Algorithm and You
Welcome to the first step into the world of RSA Encryption. You might be asking yourself, what is RSA Encryption? Well, thats the kind of question you
should be asking me, because you obviously don't know the answer. RSA Encryption is the currently worldwide accepted method of cryptography. ATM's,
internet shopping sites and hundreds of other things use RSA encryption for things like credit card numbers, passwords and other equally private strings.
Would you like in?
This encryption works so brilliantly because of several reasons:
1) Everyone (in encryption) knows how to do it
2) Everyone knows how to crack it.
3) No one can crack it :) :) :)
4) Anyone can use it
5) I can use it
6) You can use it
7) Joe the leper can use it
Heres the cool part. Everyone knows how to crack this encryption. Everyone knows EXACTLY what they have to do to crack it. But NO ONE CAN
(Excepting maybe the NSA...who are very sneaky when it comes to this type of thing).
Well unfortunately there are quite a few things you need to know first. I'll make the process as painless as possible. This is the first installment of
up to about 3 tutorials on RSA encryption. The method itself is actually quite simple, unfortunately you need to be able to make a few things along the
way. The first of those things is "the inverse of a number MOD another number". This may sound odd, but you don't need to know how to make it, you need
to be able to use the tutorial file coupled with this tutorial (which is pretty idiot proof), but I've thrown in a bit of explanation for those with a
thirst for knowledge. Understanding the method used for finding the "inverse of one number MOD another" is quite "heavy" mathematically if you haven't
done modular arithmetic (the majority of you). You should be able to understand the manipulation of the equations though.
First things second:
MOD...Have you even used the mod function in VB? It stands for modulo.
Most of you prolly know this function as "the remainder when you divide one number by another".
4 mod 2 = 0
Because 4 divided by 2 is equal to 2 remainder *0*
3 mod 2 = 1
Because 3 divided by 2 is equal to 1 remainder *1*
2 mod 2 = 0
1 mod 2 = 1
---------------
8 mod 3 = 2
7 mod 3 = 1
6 mod 3 = 0
5 mod 3 = 2
etc
EXTRA NOTE (For enthusiasts): Modular arithmetic's foundation is the mod function. What mod really means is modulo, and that means to have regulated or
restricted. So effectively what you are doing is restricting the amount of numbers you have to use. A number system modulo 2 is binary. Bits and bytes.
The only 2 numbers you have to use is 0 and 1.
Some Code Please!!!!!!
All the code is in the tutorial file, it may be a little too complex to learn. I've put a heap of notes through it, and hopefully the following explanation
should help you understand it even more.
EXTRA NOTE (for ppl with a lesser mathematical background): The GCD of 2 numbers is the largest number that can divide them both. gcd(24,12)=12, gcd(6,7)=1
(GCD stands for the greatest common denominator)
NO. Alright. But first, theres another little thing you need to know about called the "Euclidean Algorithm". Invented by Euclid (fancy maths guy...invented
a whole heap of stuff you'll grow to hate when you hit university/college math), this method is to find the GCD of a number. VB alreadt has a built in GCD
function, so why use this prissy boy Euler's formula? Because we can also use his algorithm to find "the inverse of one number mod a second number" or an
"inverse of a number" for short.
How it Works:
The idea is simple. It is best illustrated with an example
Gee...whats the GCD of 34 and 87?
Well we start by using the 87 as what I like to call "the argument" and 34 as the "divisor" (divisor must be smaller than the argument. The equation WILL
still work, but for our purposes, just stick to what I say)
So we write down:
87 = _.34 + _
That will probably mean nothing to you until I mention that the "full stop" before the 34 actually means multiply, and the underscores(_) are going to be
exchanged with numbers.
The idea is to find the maximum number of 34's in 87 without going above 87.
With a little thought you can see that there are only 2 lots of 34 in 87. Two 34's give 68 which means that there is 19 left over
So 87 = 2.34 + 19
87 is equal to 2 times 34 plus 19.
Now that you get the idea I can go through it a bit quicker. We now move the divisor(34) into the spot the argument is (87) and we move the remainder to the
spot of the divisor (34)
Aha! This is where we stop. When we have a zero reminder. Then to get the GCD, you just read the remainder from the line directly above the zero (which in
this case is 1). And hence the GCD of 87 and 34 is 1.
Now if 2 numbers have the GCD of 1, that is the special case where you CAN FIND THE INVERSE OF A NUMBER!!!!!!!!!!!!!!!
To do that, just follow my lead:
Using the above example:
Now these all make sense...Looking at the second last one, 4 is definately equal to 1 lot of 3 plus 1...So I could write is, instead of
4 = 1.3 + 1 I could write it as
1 = 4 - 1.3 (remember "1.3" is not "1 point 3", it is "1 times 3")
This is simple maths, I shouldn't need to explain that any further.
Now, I want to work right back up the equation...so now I can look at the next equation "15 = 3.4 + 3" and rearrange it as "3 = 15 - 3.4"
I want to keep a 1 in the equation, so if I look back at the other equation:
1 = 4 - 1.3 <-----I can change this 3 to something else of the same value, and I know that 3 = 15 - 3.4 so I can write it as
1 = 4 - 1.(15 - 3.4)
Now to expand that:
1 = 4 - 1.15 + 3.4
Now I have one 4, minus one 15 and plus three more 4's.
So in total I have four 4's and minus one 15
1 = 4.4 - 1.15
Now I swap the values around
1 = -1.15 + 4.4
And find something that equals 4 (the next line up in the Euclidean algorithm) 19 = 1.15 + 4 which is the same as 4 = 19 - 1.15 so I can now write
Now to check we are correct, we just make sure the equation is true.
i.e. Is 1 = (-23 X 34) + (9 X 87)?
Indeed it is. And you have just found "the inverse of 34 MOD 87", and it's the number next to the 34.
In this case it's -23
Congratulations. You've sat through one of the most boring things I've even written.
It all leads to greater things my friends.
The only thing you have to really do is download the source and play around with the program til you totally get what's going on. THen you'll be set
for finding inverses when you need to (the program does the whole thing for ya) :)
Remember, this is all in the name of encryption. The beauty of RSA encryption is that it transforms words like "this" to "E+_:QdwDQ" and words like
"multidisestablishmentarianism" to "MM@"
It doesn't always make big words small and small words big, you basically have no idea how it'll turn out.
