The CooperToons Explanation
of
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.

1. First, pick two prime numbers, p and q. We'll choose 3 and 11.
   
   
2. Then define n as their product:
   
   n = p × q
   
   So with our numbers:
   
   n = 3 × 11 = 33
   
   
3. Next define a similar number called φ (i. e., phi), but defined a little bit differently.
   
   φ = (p - 1) × (q - 1)
   
   So again with our numbers:
   
   φ = (3 - 1) × (11 - 1)
   
   = 2 × 10
   
   = 20
   
   
4. Now pick a number, g which is less than φ but with no common factors.
   
   Since φ = 20, it has the prime factors:
   
   φ = 2 × 2 × 5
   
   And the prime numbers from 2 to φ are:
   
   2, 3, 5, 7, 11, 13, 19
   
   So we can pick any of these except 2 and 5:
   
   3, 7, 11, 13, or 19
   
   For simplicity we'll select
   
   g = 7
   
   
5. Finally we define the Public Key as:
   
   Public Key: (g, n)
   
   Which in our case is:
   
   Public Key: (7, 33).

 

"Tell the world about it."
     - Harry Houdini to John Scarne

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 M^g ÷ n

And R is our coded message.

Now the way mathematicians represent "taking the remainder" is to use the modular formula.

R = M^g mod n

... which just means divide M^g 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 = 9⁷ mod 33

= 4782969 mod 33

= 15

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, Chet.

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 = M^g mod n

And that R is a remainder of dividing M^g 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:

1. Numerator (X) = M^g
2. Divisor (Y) = n
3. Remainder (Z) = R

So to back-calculate M from our coded message R knowing g and n, we simply need to solve the equation:

M^g = W × n + R

... for M.

Using a bit of middle school algebra we rearrange the equations:

ln(M^g) = 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 = R^d mod n

In other words divide R^d 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
0	7	20	0	0
1	7	20	0	7
2	7	20	0	14
3	7	20	1	1
4	7	20	1	8
5	7	20	1	15
6	7	20	2	2
7	7	20	2	9
8	7	20	2	16
9	7	20	3	3
10	7	20	3	10

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 keeps 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
3	11	33	20	7	3

And the keys are:

Public Key:	(7,11)
Private Key:	(3,11)

 

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 = R^d 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 = 15³ 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.

Block #	Block
1	do_
2	not
3	_sp
4	it_
5	on_
6	the
7	_fl
8	oor

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 × 27² + 15 × 27 + 0

= 2916 + 405 + 0

= 3321

That is:

do_₂₇ = 3321₁₀

And doing the same for the other blocks, we get:

1	do_	3321
2	not	10631
3	_sp	529
4	it_	7101
5	on_	11313
6	the	14801
7	_fl	174
8	oor	11358

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 × 27² + 26 × 27 + 26

= 18954 + 702 + 26

= 19682

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

= 20099

which fits the bill.

Since we have n and q, we can calculate φ:

φ = (p - 1) × (q - 1) = (101 - 1) × (199 - 1)

= 19800

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)

 

Big Encryption

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 = M^g mod n

So our first block, do_, which is the number 3321, is encrypted as:

R = 3321²⁹ mod 20099

= 1308571304129255741961364501313711249025746245942024210334905416355985250332830617434074265710493622681 mod 20299

= 11723

This calculation was done with a program that determined the modular multaplicative inverse of 3321²⁹ and 20099. So we got 11723 directly.

If you repeat the process with each of the other blocks, we get the new numbers:

1	11723
2	16650
3	18373
4	2016
5	9798
6	9946
7	18789
8	9042

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:

1	11723	pbe
2	16650	vvr
3	18373	yem
4	2016	btr
5	9798	mkx
6	9946	mqj
7	18789	ytx
8	9042	ljx

And put 'em all together and we get our encrypted message as:

pbevvryembtrmkxmqjytxljx

And decrypt?

Well, decrypt is where dey bury de people in Brooklyn.

NyeahahahahahahaHAHAHAHAHAH!!!!!!!!!!!!!!

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

pbe

And we turn this back to the decimal number:

pbe

= 16 × 27² + 2 × 27 + 5

= 11664 + 54 + 5

= 11723

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

= 17069

What was that number again?

17069

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) = 11723¹⁷⁰⁶⁹ mod 20099

Now we admit that 11723¹⁷⁰⁶⁹ 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:

Original Blocks

Base 10 Code

Public Key (29 , 20099)

Base 27 Code

Base 27 "Numbers"

Base 27 Code

Private Key (17069 , 20099)

Base 10 Code

Original Block Letters

do_

→

3321

→

11723

→

pbe

→

11723

→

3321

→

do_

not

→

10631

→

16650

→

vvr

→

16650

→

10631

→

not

_sp

→

529

→

18373

→

yem

→

18373

→

529

→

_sp

it_

→

7101

→

2016

→

btr

→

2016

→

7101

→

it_

on_

→

11313

→

9798

→

mkx

→

9798

→

11313

→

on_

the

→

14801

→

9946

→

mqj

→

9946

→

14801

→

the

_fl

→

174

→

18789

→

ytx

→

18789

→

174

→

_fl

oor

→

11358

→

9042

→

ljx

→

9042

→

11358

→

oor

In summary, using our public code we take the message:

Do not spit on the floor.

which we translate to:

do_not_spit_on_the_floor

... and with the public key, (29, 20099), turn this into

pbevvryembtrmkxmqjytxljx

... which you send to the rude people. Then they take their private key, (17069, 20099), and convert this code to:

do_not_spit_on_the_floor

... and they are duly admonished:

Do not spit on the floor.

 

Hardly Ever

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:

1239150451164924321313157700983301987709508728869593714564304992672219157506464372158716202486218842228298320703856840630085832997427602911718945299940154081617420938271319914057441217012610808208678857065733881292965020697652399540894111305500796421187572074439665669229279386197175293773768299509334744810942069219616878623350574625232253165628469805548985333713022726117585605235723648760090226250092874834537191735515289084968916761645040275213952172212366706660823823052056084768690624349197563322751416006138831517558923650700516974324181296793416045697313072136966600513016340087503537624067648264640581168426917943390216356455313088950461750642516584233402087960351032962069664377462405610468096025075747293687779023529005132553849885306985658863137122649432534464558798917965146160444032483638639157779677583168443512049392261510228088049693066784147322088641071553920445822717120203330366821708868983907167434667926888180740719377590532391360076006938560970971891510685910615293245369065791950373833150825727677377343128386529823626296201399837742085433458821632818471237535461323488445898147205066745433674060359200993177674255417464542737063643460730266597767161645716695301413229946253406413690912425232109292961815928173780784415238541055371773145704144145385801997322843826459073033804294087933213342160584399197639302650949042258775013532596793616646524000953475987827522444337278901013972341773262714918200446522933066276824502483399262709694506226689232910908679970281529262795243545790963503443481939192395217788196405428975817266602645487925971466047854474325424464286342450421229122063279345375075423173763784631101886560978123224942507098279051713955527083165305542352130744855687575772085726855932480063813180722172618938069517022192935449867771361478256037951377543526184601375526031440187483183212546081034521701030200834485824618621263123612179475853025916448558083809626892198591066518702894294875412632604229633411738938871774716018200930189348478243901858108470756647145446488070916815171113440716281279243174685528493215769388024302328983386783201171871317420540769032937205568232790715994417207675331375362166876688178422765914754874689579329833029849434577832816640317358962231775626808577465373918513345609846871524046034036707872210285103789153143817408782273185292757155771585647031229565056260608626629604050774295357731618503016615046388849826070353428883427030739703294425464788664484556836928050398777505418337781056562103636345992285003990407275319693882188355370808201936370342716035847638116548765877591111596252801179927228255448684266557343927452170830349155468925288106209759312282369191343922495309563857572120046451443354101307314364745880284082326115462159804830296924579780441841879196482422558354809796676478814265622638606023180745248450657591975554303391228613179108554332815375981079322913421346302359919056204880946645426142292635836033810120059185299237376624622712929578111675842408919802744911066516760670938753861381453004632980566872267376681774157480727896573933205139701492584129941563572126635657036806776212091430439476384349340874820672677454526664328297036083520978173288526139885024135114681719326265967062141778336477694133346231680512198227261656537375463170347132822110208444682825271915328596904851528513002576036735668336287123648627615100577809878845497160928543985107286496690940583372237356805864108757989656987046529353327739779404002792198954758456168350125335855902918678093761028738811241091317099880359969453550609183673996174859756605121394873733981609124334176464845068284233709241130359823923079342839661140873404750074133278307130613139953455836074544944624862270051711386375910276837182072383227671627329781962742804022646197977711467695725908835541330463543451295378028663367987000577121324665156801076277690587673348002738858884648272218081208606445555866702658577847225395562929956037081443472506881

... 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.)

In other words, as easy as it was to find a simple Internet javascript program to calculate such a huge number from the two big primes, working backwards would not be so easy. In fact, this is the type of number a working RSA code would use, and even the biggest computers would take - not decades, not centuries - but literally millennia to factor this back into the two primes. So by the time the code could be cracked, the importance of the message would have faded.

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.

"I understand."

 

References

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.

RANDOM.ORG, https://www.random.org/

Big Number Calculator, http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm.

Prime Factors Calculator, http://www.javascripter.net/math/calculators/primefactorscalculator.htm

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.