October 7, 2015

A step-by-step walkthrough of public key cryptography

The basic concept of public-key cryptography (specifically, the RSA version) is always described as “finding the factors of large numbers is hard”.   So if you can find two large prime numbers, and multiply them together, you get a very large number that is incredibly hard to factorize.

But I’ve struggled with understanding how you get from that fact to encrypted text.     So, using some resources, I finally sat down and tried to walk through a simple example, just so I could get the concept.   This is my story.

Here are two links that describe the basic algorithm:

I used Google Sheets to do my work, and I ran into a problem right away – Google Sheets (and also Excel) can’t handle the ridiculously large numbers that get produced during the algorithm.    So I found a website that provides an arbitrarily large number calculator:

Armed with these four resources, I was able to walk through a toy problem:

It is April 14th, 1775.  Paul Revere is waiting for an encrypted message from Robert Newman, the sexton of the North Church.   Robert will email him a message using Paul’s public key.  Because ‘1’ is boring, the encrypted contents will either be ‘2’ if the British are coming by land, or ‘3’ if the British are coming by sea.

Calculating the Public and Private Key Pair

So first, Paul needs to calculate his public and private key pair.    This being the 18th century, his mathematics are limited.   So he uses very small prime numbers for p and q:

  • p = 11
  • q = 19

Using p and q, he can calculate n  ->  p x q = n == 209


  • n = 209

Now, per the algorithm, he needs to calculate “Theta N” or Theta PQ” depending on who you ask.   I’ll use Theta N

Theta N is (p-1) x (q – 1)  == 180


  • Theta N = 180

Now he has to find a number e such that e is relatively prime to Theta N.   Relatively Prime, in this case, means a number x that doesn’t share any common factors with y.   The simplest version of this is y – 1.    In this case, y is Theta N which is 180.   Which means that e is 180 – 1


  • e = 179

Lastly, he needs to determine d.   d is a number such that d x e modulo Theta N is 1   .   There are a lot of numbers that fulfill this, but a relatively small one is 359  (179 * 359 == 64261) and then that number modulo Theta N is 1:   (64261 % 180 == 1)


  • d = 359

Paul keeps p, q and d a secret.   He gives e and n  to Robert Newman (the sexton of North Church, remember)?


It is now the evening of April 18th, 1775.   Robert Newman is watching from his church steeple, and he sees the British rowing across the Charles river.   “Two if by land, Three if by sea!” Robert Newman cries out.   He quickly gets out his abacus and starts calculating.


The encrypted message is the number 3   . The algorithm says  to raise the message to the power of e, and then modulo n .  Remember, Paul gave Robert e and n on the 14th.


  • M = 3

First step, he raises M to the power of e :   3 ^ 179

which is:


And then he uses modulo to calculate the remainder of division by n  (or 209)

766247770432944429179173513575154591809369561091801088 % 209 == 70

so the Ciphertext (C) is 70

This value “70” is what Robert Newman emails to Paul Revere.


Minutes later,  Paul Revere receives the encrypted Ciphertext “70”.   He quickly rushes to his abacus.   To decrypt this message, he needs to raise the value C to the value of d, and then modulo n :

C ^ d is 70 ^ 359 which is the very large number:


(The poor abacus is melting down)

Now he just needs to divide this incredibly large number by n to get the answer.   n is 209, and that incredibly large number modulo 209 is:


3    !!!


Now, the question for you, dear reader, is to determine what the ciphertext would be if the British had been coming by land.    I’ll give you a hint, C ^ d is 726 digits long, the first two digits are 40 and the last two digits are 25.