The CooperToons Explanation
Public Key Cryptology
(Or Keeping Secret What the World Knows)
It can be made public.
People have been writing coded messages for millennia. And people have been cracking those codes for millennia.
So for millennia people kept trying to make more and better codes. But try as they might, even "unbreakable" codes - like the Germany's Enigma - were broken.
But in the 1970's code makers realized they had it all wrong. You don't keep the code secret. You tell everyone about it. That way no one can decipher the message.
Ha? (To quote Shakespeare.) We'd really like to know how that is possible.
I though you would, as Captain Mephisto said to Sydney Brand. So if you just read on, you'll be able to say "I understand."
The Great Unwashed Public (Key)
You want to make a secret code that you can still tell everyone about? Well, it's actually pretty easy. We won't bore you with nerdy number-theoretical theorems, but just give you the rules.
"Tell the world about it."
- Harry Houdini to John Scarne
Aunt Ellie's Friend
OK. We have our public key (7, 33). So how do we code our message?
Suppose your rich Aunt Ellie wants to send you the message "Who shall I give my $100,000,000 inheritance to? I will follow your recommendation."
But your aunt wants you to keep your answer secret from your Evil Twin Brother, Oliver. So she goes to her friend who is a world famous television newscaster and asks him to broadcast the key. So that night at the end of the broadcast Walter says:
And in closing, Aunt Ellie wants her nephew to use the public key, (7, 33) in his response to her question, "Who shall I give my $100,000,000 inheritance to? I will follow your recommendation."
And that's the way it is
Note two things. It is the recipient of the coded message - Aunt Ellie - who gives the key to the sender, who happens to be you, her nice nephew.
And neither you nor Aunt Ellie has to keep the key secret from anyone. So if that's the case,, we ask, do we now proceed to send a secret message?
First, the sender has to code the message. You do that by changing the text to a number. Yes, that is sort of a code in itself, but one that can be easily broken. And since you want to answer "I" we'll use the alphabet location of the letter, which is 9 as the number. For shorthand, we'll call our uncoded "message" M (which is now "9") and the coded (encrypted) message as R - which we now have to determine.
And the coded message?
Why, you simply take the public key, which is (g, n), and the uncoded message, M, and use the following formula.
R = Remainder of Mg ÷ n
And R is our coded message.
Now the way mathematicians represent "taking the remainder" is to use the modular formula.
R = Mg mod n
... which just means divide Mg by n and take the remainder.
That is, for our message where g = 7 and n = 33 and the message, M = 9, the encrypted message, R, is:
R = 97 mod 33
= 4782969 mod 33
In other words if you divide 4782969 by 33 the remainder is 15.
And that's our coded message.
So now you go to two other famous broadcasters. And you ask them to send your aunt the message. So they close their broadcast with:
And one of our viewers wishes to pass on the message to his Aunt Ellie. And that message is "15".
Goodnight, David. And goodnight from Aunt Ellie.
They broadcast the answer.
Of course, your Evil Twin Brother Oliver hears the broadcast. He figures the number "15" means the 15th letter of the alphabet which is "O". So "O" must mean "Oliver" and he thinks he will get the money.
And by the time he realizes he won't, it's too late.
Figuring It Out
But wait, your Evil Twin Brother Oliver watched the broadcasts and so he knows the public key. And he knows the coded answer. So why can't he just simply back calculate the orignal message?
Well, give it a try. Remember, the basic equation was:
R = Mg mod n
And that R is a remainder of dividing Mg by n.
The question, then, is how do you work backwards if all we are given is a remainder?
Actually you can't.
Or look at it this way. Let's express division with a remainder as:
W = X ÷ Y Remainder Z
where W is the quotient, X is the numerator, Y is the divisor, and Z is the remainder.
This can also be written as multiplication:
X = W × Y + Z
And we assign the values for our coding as:
So to back-calculate M from our coded message R knowing g and n, we simply need to solve the equation:
Mg = W × n + R
... for M.
Using a bit of middle school algebra we rearrange the equations:
ln(Mg) = ln(W × n + R)
... and end up with:
M = e[ln(W × n + R)]/g
So since we know R, n, and g, we now want to calculate M.
But we're missing one little thing: That's the quotient, W.
And here's the kicker. There's no way to figure what W is.
Why? Well, that's because if we are given only a remainder and a divisor, there are infinite possibilities for the quotient.
Suppose I give you two numbers, the divisor 3 and the remainder 1. But I don't give you the numerator. Now tell me what the quotient was.
You can't because there are too many - in fact, infinite - ways to get the remainder 1 with a divisor 3. And so there are an infinite number of possible quotients. This is true for any divisor or any remainder.
But how, you ask, if you can't decipher the coded message with the public key, how can Aunt Ellie do it?
Well, normally she couldn't. But fortunately the nerds will come to the rescue.
Leave It to the Nerds
Let's be honest. The true nerds of mathematics are the number theorists. These are the guys and gals that love to play with numbers and find all sorts of kooky equations. They will go into raptures explaining how Collatz's Conjecture has never been proven or how the Continuum Hypothesis is undecidable. Number theorists have been around literally for thousands of years, and they're still going strong.
And it was three number theorists at MIT who took some theorems and developed the algorithm we've used. It's called the RSA Algorithm after the chaps' initials.
In developing the code, they knew that under certain cases you can take a remainder and a divisor and get the numerator without the quotient. Or rather, you can disguise the quotient in the other numbers in the public key.
Now what we're calling g is the Encryption Exponent. Remember you picked that number out yourself and it is part of the public key.
But to back calculate the original message, we will calculate a new number d called (commensicially) the Decryption Exponent. And our friends at MIT found that if you pick the prime numbers p and q and the other numbers as we did, then g and d are related by the equation:
(g × d) mod φ = 1
That is, if you multiply g and d and divide by φ the remainder must be 1.
So we define the Private Key as (d, n).
Private Key = (d, n).
And if you have the private key you know d and n and if you are given the coded message R, you can calculate the original message M.
M = Rd mod n
In other words divide Rd by n and the remainder is the original message M.
So let's see how you calculate d with our sample code. Well, first we need to know the value of φ. It is, you'll remember:
φ = (p - 1) × (q - 1)
And with our numbers we got:
φ = (3 - 1) × (11 - 1) = 2 × 10 = 20
And we need to find the number where we multiply it by g and divide by φ we get 1.
In this case, we can find d by trial and error:
|d (Trial Value)||g||φ||Quotient||Remainder|
And d = 3 is the lowest possible value for our decryption exponent. So Aunt Ellie selects her private key as:
Private Key = (3, 33).
... and she keep this private key - that is, d - to herself.
You can, of course, use other values for d as long as the remainder is 1. For instance d = 23 is the next number that works but it makes our sample calculations more onerous.
Now the trial and error method is sometimes too difficult to calculate d. So there is a method - called the Extended Euclid Algorithm - that lets you calculate d directly from the modular exponential inverse of g. Later we'll use this method but we'll skip the details.
At this point it's worthwhile pausing and tabulating the numbers so far.
|p||q||n = p X q||φ = (p - 1) X (q - 1)||g||d|
And the keys are:
And It Really, Really Works.
So although we code the message with the Public Key, it is with the Private Key that you decrypt the code. That is we can determine M from d, n, and R. And we do that from using what is really the same equation for calculating R.
M = Rd mod n
And like the commercials say, it really, really works.
So let's just take our numbers, R = 15, n = 33, and d = 3 and plug them in:
M = 153 mod 33
M = 3375 mod 33
M = 9
... which is our original message.
And so Aunt Ellie gets the message, 9 = "I", and you get your $100,000,000.
A Little Realism Please!
Now this is all well and good. But can we get a real example? Like sending a real message?
Well, yes. And we can then really say "I understand."
OK. First we need to code a real message.
Treating a lengthy message as a single number is possible, yes. But it's also not something that is feasible for all but the shorter messages.
So what we do is divy the message into blocks. For instance, let's send the message.
Do not spit on the floor.
Now if you coded each letter individually, that would make things easier. But you would just be substituting a letter for a number. Such codes can be cracked even by amateurs.
So we break up the message into blocks of three. And we'll skip punctuation and indicate a space by an underscore.
Now there's various ways to represent the blocks of letters as numbers. You could simply take the alphabet location, Space (_) = 0, a = 1, b = 2, ... y = 25, z = 26, and put them together.
So we'd have:
do_ = 4150
Now this isn't too big a number. But what if you have the word "not"? You get:
not = 141520
Now in big computers these numbers can be handled. But we'll show a way to keep the numbers a bit more manageable. We do this by treating the alphabet as a number system of base 27 (without a space it would be base 26). The "numerals" are simply the letters.
So what is the decimal equivalent of our first block? Well, if you dredge back your mind to middle school, you'll remember to convert to different bases is pretty easy. Multiply the decimal equivalent of the digit times the base to the proper exponent.
do_ = 4 × 272 + 15 × 27 + 0
= 2916 + 405 + 0
do_27 = 332110
And doing the same for the other blocks, we get:
Now here we do our coding.
One rule we haven't stated explicitly is that the value of n must be larger than the value of the largest block. Since in our example "zzz" is the highest base 27 number we can have, this means we must have n greater than:
zzz = 26 × 272 + 26 × 27 + 26
= 18954 + 702 + 26
With this priviso we can now pick out our primes p and q as we like. So we'll select
p = 101
q = 199
And n is given by:
n = p × q = 101 × 199
which fits the bill.
Since we have n and q, we can calculate φ:
φ = (p - 1) × (q - 1) = (101 - 1) × (199 - 1)
We now have to pick g. So we must factor 19800. That's pretty easy.
φ = 19800
= 198 x 100
=9 × 22 × 10 × 10
= 3 × 3 × 2 × 11 × 2 × 5 × 2 × 5
= 2 × 2 × 2 × 3 × 3 × 5 × 5 × 11
So we are excluded using 2, 3, 5, and 11, but we can have g equal to any number less than φ and which has no common factors with φ. But it's easiest to pick a prime, and we'll choose 29. So our private key, (g, n) is:
Private Key: (29, 20099)
Here's where we get into intensive calculations. Remember. With the original message M and the public key (g, n), our coded message, R, is:
R = Mg mod n
So our first block, do_, which is the number 3321, is encrypted as:
R = 332129 mod 20099
= 1308571304129255741961364501313711249025746245942024210334905416355985250332830617434074265710493622681 mod 20299
This calculation was done with a program that determined the modular multaplicative inverse of 332129 and 20099. So we got 11723 directly.
If you repeat the process with each of the other blocks, we get the new numbers:
We can, of course, simply send the numbers as the coded message. But you could also convert these base 10 numbers back to three digit base 27 numbers (again middle school math). That is, back to the alphabet:
And put 'em all together and we get our encrypted message as:
Well, decrypt is where dey bury de people in Brooklyn.
Seriously, folks, you simply break the coded message into groups of three letters and then go back to our private key.
Let's pick the first three letters
And we turn this back to the decimal number:
= 16 × 272 + 2 × 27 + 5
= 11664 + 54 + 5
Now remember we get our Private Key whose exponent is:
d = MultModInv(g) mod φ
where once more MultModInv(g) is the modular multaplicative inverse of g which we get from a website that does it for us.
In our case, we find that.
d = MultModInv(29) mod 19800
What was that number again?
That's a heck of an exponent.
Indeed it is. But that's the number.
OK. Can you get the original message back?
Well, let's try.
First we take the coded block. This value is 11723.
So the decrypted number is:
R (Block 1) = 1172317069 mod 20099
Now we admit that 1172317069 is a big number. So we'll call it B for "Big"
We won't list the exact number on this page although you can see it in another window if you click here.
But - and may we die the deaths of dogs if we lie - if you divide B by 20099 and get the remainder, you do indeed get the original message:
B mod 12009 = 3321
This and the other coded blocks can recover the message:
(29 , 20099)
(17069 , 20099)
|Original Block Letters|
In summary, using our public code we take the message:
Do not spit on the floor.
which we translate to:
... and with the public key, (29, 20099), turn this into
... which you send to the rude people. Then they take their private key, (17069, 20099), and convert this code to:
... and they are duly admonished:
Do not spit on the floor.
But all of this raises a new question.
Your Evil Twin Brother Oliver knows the code and has the public key. So he knows the value of g, but most of all, he also knows the value of n. He also knows n is the multiple of two unique primes p and q. He can then simply have a computer factor n into p and q and he can now calculate φ which is the product of p - 1 and q - 1. From φ, and g, he can now calculate a value for d - which you remember does not need to be unique. So as long as he has the public key, he can indeed calculate a valid private key, and decrypting the coded message is easy.
All that's true. Except for the "easy" part.
True, even with the big numbers generated by the last code, the message can easily be cracked. That's because the value of n = 20099 is still pretty small. Even online web programs can factor this back to p and q in a trice. And with p and q you can get your private code.
And even if you're given a number like:
n = 376188795978556571
... a quick search on the internet will find a site that will tell us:
p = 593441861 and q = 633910111.
... and you can figure out the private key.
OK. But what if I give you a value of n like:
... and tell you it's the product of two primes (which it is). Now you and your computer will have more trouble. (If you want to see what p and q are just click here.)
So yes. It is possible to crack the code if you have the public key. But it isn't - to quote Arlo Guthrie - very likely and we don't expect it.
Introduction to Cryptography: Principles and Applications, Hans Delfs, Helmut Knebl, Springer, 2002.
"Cryptographic communications system and method", Ronald Rivest, Adi Shamir, Leonard Adleman, U.S. Patent 4,405,829, December 14, 1977.
Modular Exponentiation, http://www.dcode.fr/modular-exponentiation-calculus
Modular Multiplicative Inverse, http://planetcalc.com/3311/
Great Internet Mersenne Prime Search, GIMPS, http://www.mersenne.org/
"Base 27: The Key to a New Gematria", Lee Sallows, Word Ways, Vol. 26, No. 2, 1993.