The Math of Secrecy: RSA Cryptography (and Shapes You Can Draw?)

When Gauss was 19, he discovered that of the infinite number of polygons that have a prime number of sides, a mere five of them can be constructed with a ruler and compass (i.e., using only straight lines and circles). These prime-sided polygons can have 3, 5, 17, 257, or 65537 sides, but only these five are possible (probably).

Indeed, the only shapes you can draw with an odd number of equal-length sides are the multiples of these 5 Fermat primes: 3, 5, 15, 17, 51, 85,..., 4294967295
(amazingly, all constructable polygons must have a number of sides that is a multiple of a Fermat prime and a power of 2!). There are good reasons why this is true, but they are confusing and would belabor this post.

Apparently, Gauss was so happy with his finding that he requested a regular heptadecagon on his tombstone; the stonemason declined, stating that it would essentially look like a circle. After watching the requisite process below, one begins to sympathize with the stonemason (diligent wikipedian Aldoaldoz made both of these; in case you want to build your own 17-gon, you can break out the compass and follow along at home). It's hypnotically beautiful, but the .gif alone is 462 frames and takes a full 1:26 to watch...

These strange numbers are known as Fermat primes, and take the form 2²ⁿ+1. Though there are infinitely many numbers of this form, only the first 5 (above) are prime. As I was reading about these yesterday, I found that they have an important application in the most common form of public-key cryptosystems, whereby messages are encoded so as to conceal their meaning.

This method of encryption is used to secure electronic communication over the internet; even if a third party somehow manages to nab your encrypted message, it will be almost impossible for them to crack it. If you've used SSH, SSL/HTTPS, PGP, or had to verify a digital signature, you've used RSA encryption or one of its descendants.

On personal websites, you may have run into these before:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.4.11 (GNU/Linux)

mQENBFPCyXEBCACuHid62W3FI3DegXw3G6Xyjdj3SBl3+f/fBNIN4Yrx0auPjuZG
TqtA6opOH7jzAEBdBBysiQ+1frQlfiWlmdzJ/GQR7KGhuZNx33pyCwXV85bcKtno
A4CQK8r2sfrRF796voNWxW/MaStT7IWQfHrMYsgcl+7cZogBu/nl3nnHuZz+oMMG
ZZl+uziKF1+M4naOr6gH3UMTECk2Xib2lk58RFN4pmqPzbWG5gUU5ugN13c6hO7S
eKN/cbGSHRHPQci0aZo743rIoWgQZ+S88j3BweGFbD78tw5UYJUW+rnyYISzDbVi
R+i8luzVtVhkHZnetcQoz6IBsDyfnK0dKMLhABEBAAG0K05hdGhhbmllbCBSYWxl
eSA8bmF0aGFuaWVsLnJhbGV5QGdtYWlsLmNvbT6JATgEEwECACIFAlPCyXECGwMG
CwkIBwMCBhUIAgkKCwQWAgMBAh4BAheAAAoJEH4levi+sCboeHoH/3IyNGGwxVWy
VVnjKj2vpbgysU4W4xieL9sWvMBFnKDhpHZsazBEhXnmhEbDouixZaFeMmul8C7J
2/5Ljync/fkPCKtyF+Ibovs3ALuHnY4Iu8vukxMbr7cmB1lOkVGxHIKcjGX4H9F7
6qnGYmJWpz+pgYIbq5xO07aCcwE9/EUQwh0MdDml0euRiDWio1HOM7XTVJJ7AmyX
MKroqF+Ik/93mSl4vGlKKqDhPr3hcxqFsE8LhHgMxeI2NGomhka064mwWqRpFf0f
ce33cWaFSgl+rRAqkQkZUdiMnbIj9P89OH/PqOQgaB/nXIVXmjMb6HluhJA/2ZnM
h+Y8e0pF2j+5AQ0EU8LJcQEIAK38D6Bnho1cennrFOVcCj1nmlG4UW9mWr2ox+WJ
QBEqw8IUsWg/0LEe5K3MPoOE3lO3VTHnKqLMJSbA9byjSwYxIE3Y1QoY1Uq43Da1
sYkeETVkMgnAGmIwSQgsdfdAGhXv5uF/Ck3O+QMdUW5qZ4s+WXUCMWcj4ZgomUxC
i0bQgE/w/TDc0JAisma2oOuOTVjpfyX5VCk6XtwmDxE+STHZTCIKvSnyodx3Hlke
1gr+f/ejpbAnYiyjjWpiQGS47YCjAzGAsn0CRJ4dQYsjv6RVL/O/EYEJDUs49cLW
ccYhj0BQZyeMqWxZqP8ZUIGsoPfzh/ahLNXnxlqVTD53eA8AEQEAAYkBHwQYAQIA
CQUCU8LJcQIbDAAKCRB+JXr4vrAm6OFPB/9P4GkEV+XpejL4TO17Sh7vj3nZvKxd
AoPKKG1qbJNuYqasz0d5C0hfZN4aLaKdiWide9sIMfjRrG1gbN8o34uR3i3887Eg
zrhZWS/E01jGqR4ey/iACyfXvDfEFEwthfChyS9qQVYw7fWWSBtpZqJ5iul7Jf7b
tHPeqizK2FqOSnJy9ovaHHcZL4Wt26Y+IDWq0WQKB89guhN6LhlaQQXrAhlbwW2N
DcvTrHm3g4sVxeuAujGJzJGRmf5hkV+YxG2OrpLQjx+n4XsZSFO3tdfNwTwDn1Xj
9AFqGhRzm9j1Cq3iqcTbJtQwwJknkNm7CLFeHuy4zurzP3gmwnRvZ2UM
=X1Q+
-----END PGP PUBLIC KEY BLOCK-----

To the untrained eye someone's cat has been traipsing about on their keyboard, but in reality this string represents two (big, random) numbers that allows you to communicate with it's provider in a completely secure fashion. It is a "public key" and is used to encrypt messages sent to its owner; it has a mathematically precise twin, a "private key" which only the owner has access to. This private key is required to decode the message originally encoded by the public key.

For an extremely helpful analogy, consider a padlock. A public key can be thought of as an open padlock and a private key is the key that can unlock it once it is closed. In public key cryptosystems, you give your close friends copies of your personal padlock, open and unlocked (this is your public key). They can now send you messages securely by locking them in a box using your padlock (i.e., encrypting it with your public key) and sending it to you, because only you have the key (the private key) which can open it. Note that your friends don't need a key to close the padlock: they simply put their message in the box and shut the padlock.

How does this work mathematically? Here's a technically correct but very basic run-through of RSA for didactic purposes:

Let's say you want to communicate privately with another party. They're going to send you a secret message (message: "PRIVATE") over the internet, and they want to be sure that no one else can read it. In order to do so, they can encrypt this message using your public key and send it to you; you can then use your private key to decrypt and read it.

Let's assume you haven't yet generated public/private keys, and you want to do so by hand:

STEP 1
Choose a pair of prime numbers, p and q, at random.
To keep the math reasonable, let's take p=3 and q=17

STEP 2
Multiply p and q together to get their product n.
Here n = 3 x 17 = 51 (This is the step that is hard to reverse in practice!)

STEP 3
Multiply (q-1) x (p-1) to get the totient of n, φ(n)
φ(n)= (3-1) x (17-1) = (2) x (16) = 32.

STEP 4
For the first key, choose any number e that is smaller than φ(n) and has no common factors with φ(n). Since φ(n) = 32, we can choose any number besides 1, 2, 4, 8, 16, and 32.
Lets pick e =11.

STEP 5
Finally, the matching key d must be computed. This is achieved by "taking the inverse of e modulus φ(n)". All this means is that we need to find the number d to multiply e = 11 by so that when we divide their product by φ(n) =32, we get a remainder of 1. This isn't as hard as it sounds: φ(n)=32, and e=11. Since 11 x 3 = 33, and 33 divided by 32 leaves a remainder of 1, we know that the d, "the inverse of 11 modulus 32" , equals 3.

These keys e=11 and d=3 are mathematically linked through n=51, because
if you take the number you want to encrypt to the power of e and divide by n, you get a remainder. This remainder the encrypted version of your original number. To decode it, just raise it to power of d and divide by n.

As quick example, say the secret message you want to send is the number 4. To encrypt it using our public key (e=11, n=51), do

4¹¹ % 51 = 4194304 % 51 = 13.

The number 13 is our encrypted message, which can only be unlocked if you have the private key (d=3, n=51). The same procedure used to encrypt is used to decrypt, but take 13 to the power of d and find the remainder when dividing by 51.

13³ % 51 = 2197 % 51= 4, our original message

Without factoring n = 51  you can't easily compute φ(n) 32 and thus knowing one key, you can't easily compute the other.



But how do we send the secret message "PRIVATE"? First you should get a numerical representation of this message; commonly, a much longer messages is being sent and it is converted from ASCII to its decimal representation. For now, we can just take the number that corresponds to each letter's position in the alphabet, (A=1, B=2,..., Z=26). Doing so for this message yields "16 18 9 22 1 20 5".

To encrypt our message ("16 18 9 22 1 20 5") using one of the keys (now therefore the public key), we repeat the process used above for the number 4, but now we use it on each of the numbers in our numeric code:

encrypted = original^public_key mod n.

16¹¹ mod 51 = 17,592,186,044,416   % 51 = 16
18¹¹ mod 51 = 64,268,410,079,232   % 51 = 18
9¹¹   mod 51 = 31,381,059,609         % 51 = 15
22¹¹ mod 51 = 584,318,301,411,328 % 51 = 28
1¹¹   mod 51 = 1                               % 51 = 1
20¹¹ mod 51 = 204,800,000,000,000 % 51 = 41
5¹¹   mod 51 = 48,828,125                % 51 = 11

So our encrypted message is (16 18 15 28 1 41 11). This is the message we send to our intended recipient. Even if it is intercepted in transit, it remains unintelligible without the private key.

To decrypt the message, repeat the process except now we are raising the encrypted message to the power of the private key (3), which transforms it back into its original code.

original = encrypted^{(private_key)} mod n.

16³ mod 51 = 4096   % 51 = 16
18³ mod 51 = 5832   % 51 = 18
15³ mod 51 = 3375   % 51 = 9
28³ mod 51 = 21952 % 51 = 22
1³   mod 51 = 1        % 51 = 1
41³ mod 51 = 68921 % 51 = 20
11³ mod 51 = 1331   % 51 = 5

Resulting in the original message, (16 18 15 28 1 41 11 = "P R I V A T E").


The way this works in practice is that you generate your own set of keys, one public and one private. The public key is made known to others with whom you wish to communicate privately (often by posting it somewhere online). Then, if someone wants to send you an encrypted message, they simply encode their message using your public key and send it to you. At this point, the message is garbled and can only be decoded using your private key. Remember that big block of garbled nonsense above? That's my public key, analogous to (11, 51) in the example above except that in decimal form it has over 300 digits!

In the demonstrative example above, our n = 51. Numbers like 51, which are the product of two primes numbers, are called semiprimes. Its not hard to see that 51 = 17 x 3, and these factors are all you need to crack our code! So how is this secure? The strength of the security offered by RSA and similar cryptographic methods is that finding the original factors of a huge semiprime is computationally difficult. For small semiprimes its no big deal, but when the two prime factors are large (~300 digits, which is more than a "googol"!), randomly chosen, and about the same size, the search becomes impractical for even the most powerful computers. The number of operations required to perform the factorization exhausts all our of present computer power.

The largest RSA number that has even been successfully factored is 768 bits (232 decimal digits), and this took hundreds of computers more than two years to accomplish! Indeed, much smaller RSA numbers, many with large bounties in their day, remain unfactored. Still, this method of encryption is not "uncrackable" and the size of the numbers used will have to stay one step ahead of developments in computing power. There do exist uncrackable codes, however...

Now, why are Fermat primes (2²ⁿ+1) useful in RSA cryptography? Often, the public key exponent is one of these five numbers, typically 65537. Consider their binary representation:

3 = (11)2
5 = (101)2
17 = (10001)2
257 = (100000001)2
65537 = (100000000000000001)2

They are computationally convenient! There are probably other reasons too... let me know if you think of any!

Circling the Square & Squaring the Circle!

In A Mathematician's Lament, Paul Lockhart roundly decries the way our school system sucks the soul out of mathematics; what was forced down most of our throats was an insipid husk of repetitive calculation, plug-in formulae, and rigid formality, all of which we were called upon biweekly to regurgitate. Most painful for him to see is the way geometry is taught:

"All metaphor aside, geometry class is by far the most mentally and emotionally destructive component of the entire K-12 mathematics curriculum. Other math courses may hide the beautiful bird, or put it in a cage, but in geometry class it is openly and cruelly tortured.
(Apparently I am incapable of putting all metaphor aside.)"

If you haven't read the Lament yet, definitely stop what you're doing and take the next 30 minutes to do so; if you have any interest at all in mathematics or education, it will be one of the best-spent half-hours of your life.

Having deep, abiding interests in both of these things, I was personally moved by the piece and feel a renewed enthusiasm for shapes and numbers, an enthusiasm that was all but aborted by my own early math education. Yours almost certainly was too! Here's what I mean...

          

Consider a line segment 2 units long. Now, make a square where each side is one of these segments. We have "squared" our 1D segment and we got a 2D shape 2 units long by 2 units wide. That's 4 square units total, because 2²=2x2=4. Thus, we say that the area of our square is 4 square units! (Area is just an arbitrary measure of what you get when you compare the shape to squares of a fixed size, in this case 1 square unit.)

We can take these 4 square units and arrange them however we want: if we put them all four in a row, we create a rectangle 4 units wide by 1 unit tall. It has the same area as the square; we can see this by inspection or by noticing that 2x2=1x4. It is true for all rectangles and parallelograms that area = length x width.

Instead of memorizing a formula, how could we find the area of a triangle?
Is there a way we can cut the square to make triangles? Yes, absolutely. Cut a square diagonally and you get two triangles. Are these the same size? Yes! So if two equal parts make 1, we know they have to be half of the original. Thus, the formula you had to memorize in grade school makes some obvious, visually verifiable sense. You were told, "base times height divided by 2" or "one half base times height". Well, now you see that "base times height" gives you the area of a rectangle, and "divided by 2" gives you exactly half of the rectangle's area, corresponding to a triangle.

 

Teaser: how much of the box is taken up by each of the triangles below?

 

Here's a hint:

Answer: It's always half! 

The Diagonal of a Square
Now then, let's take just one of our square units (from earlier). Here's a question: measure from corner to corner diagonally, and what do you get?

       

Well, we can see that it's longer than 1, but shorter than 2. Indeed, 1.5 is a pretty good guess, but it look to be a bit less. 1.4?  A bit more than this. 1.41?

Let's zoom in a bit... Uh oh, we're not quite there. 1.415? Close, but zooming in a bit more we can see we still overshot it. How long is this lousy diagonal line?! It's length doesn't seem to be representable in ordinary integers or fractions...

 
Have we made some mistake? This extremely regular shape has already produced for us a bit of a quandary; we're just trying to measure the length between a square's two corners! It's as if Well, whatever the length is, let make a square out of it too. Two squares might be easier to compare...

Take a minute to look at the two squares. Notice anything? It looks to me like half of our original square fits inside this new square exactly 4 times. 4 halves make 2 wholes, so 2 original squares = 1 new, diagonal square.

Let's see if we can find that diagonal now! We know that two squares whose sides are 1 add up to form a bigger square, whose side we don't know (besides knowing it's close to 1.4). Let's call that side length d, for diagonal. So, we can say 1²+1²=d².

Since 1² is just 1x1, which equals 1, and since 1+1=2, we know that d²=2. This says that our diagonal squared is equal to 2. We are almost there! At this point, you might just take the square root of both sides: the square root of d²= d, and the square root of 2 is, well, √2. So the diagonal of a square with side lengths of 1 is equal to √2.That's not satisfying at all!... what is
this √2 business?


How to Find √2
We know that our diagonal line d, times itself, equals 2, or d²=2, that's just saying that dxd=2, or d=2/d (if we divide both sides by d). We got close earlier just by measuring; we found that the diagonal length was less than 1.5, and probably around 1.4.

Let's let 1.5 be our first guess for d and then see if we can refine our guess to get closer to the answer: so d=1.5... since d=2/d, we should divide 2 by 1.5 to see what we get:

DIVIDE 2 BY OUR GUESS:
2 / 1.5 = 1.3                                                   ....in fractions, 2 / (3/2) = (4/3)

So, we know that 1.3 x 1.5 = 2, but we want 1.3 and 1.5 to be the same number: we want d x d = 2. Our next guess should be a number in between these two numbers, so lets average them! 

GET A NEW GUESS (average the old guess and the quotient):
(1.5  + 1.3) / 2 = 1.416                ....in fractions, ((3/2) + (4/3)) / 2 = (17/12)

Our next guess is 1.416, so we can do this process over again: divide 2 by our guess, and take the average of the quotient and the divisor:

2 / 1.416 = 1.4117647058823529           ....in fractions, 2/ (17/12)= (24/17)

We know the answer is somewhere in between 1.416 and 1.4117647058823529, that is, between (17/12) and (24/17). Average them!
((17/12)+(24/17)) / 2 = 1.414215...                         ....in fractions, (577/408)

If we were to repeat this process forever, we would converge on the square root of 2, which is the length of that diagonal. But until we do an infinite number of these averages, we won't know exactly how long the diagonal of a square is! Unbelievable! Chances are, you've already whipped out your calculator and found that √2  = 1.414213562..., so our averaging method worked well! After just 3 iterations, we're off by only 0.000015%! What does it mean, though that this "irrational" hole to infinity emerges when we try to do something as basic as measure a square? What does it mean?

What about π?

I don't know about you, but no one ever showed me what π (pi) was all about. I mean sure, as far as numbers it is culturally unique in having, for whatever reason, made its way onto t-shirts and bumper stickers like some kind of geek heraldry. we hear over and over again that this 3.14 is some number equal to ~22/7, and know it has to do with circles because we had to memorize that A=π r² and C=2π r. We may even know that it's "the ratio of the circumference to the diameter," which is simply a restatement of the formula ( π=2r/C=d/C). But what is π, what does it look like, and what do these equations really mean? Paul Lockhart discusses the educational disasters that can accompany this topic:

"To help students memorize formulas for the area and circumference of a circle, for example, [teachers will recite] this whole story about “Mr. C,” who drives around “Mrs. A” and tells her how nice his “two pies are” (C = 2πr) and how her “pies are square” (A = πr²) or some such nonsense. But what about the real story? The one about mankind’s struggle with the problem of measuring curves; about Eudoxus and Archimedes and the method of exhaustion; about the transcendence of pi? Which is more interesting... using a formula that someone handed you without explanation (and made you memorize and practice over and over) or hearing the story of one of the most beautiful, fascinating problems, and one of the most brilliant and powerful ideas in human history? We’re killing people’s interest in circles for god’s sake!"

 So let's talk about π, not because we have to memorize it, but because it is weird and fascinating and very much worth thinking about for its own sake!

 Above, we talked about how, when you take a square's diagonal and divide by its side, weird stuff happens (you get √2). Even weirder stuff happens when you measure around a circle (circumference) and divide by the distance across (diameter): you get π. Humans have been refining their calculations of this value since at least 1850 BC. We first noticed that, for any given circle, the distance around a circle is about 3 times the distance across. But as the figure above illustrates, this is not quite right: 3 diameters around almost gets us there, but leaves us coming up short by somewhat more than 14 hundredths. But how much more, exactly?

Around 250 BC, Archimedes came up with a new approach: because we can measure straight lines but not curves, just stick the circle inside a shape made from only straight lines (i.e., a polygon), and increase the number of sides to get closer and closer to a circle. Then measure the straight lines around the outside.



Here's an example of Archimedes' influential technique: put a circle with a diameter of 1 exactly inside a square: Our first guess for the area of a circle is the number of sides of the square times the length of each one (the perimeter of the square), which in this case is 4. To home in our pi, we keep increasing the number of sides and multiplying by the length of each one, as shown above for four more polygons (a hexa-, octa-, dodeca-, and 24-gon). Notice that, even when approximating with a 24-sided shape, our guess comes up pretty short (3.15966). 

Using this method, Archimedes proved that 3.1408 < π < 3.1429. More than 1800 years later, humans were still using this technique: the record in 1630 for calculating digits of π was 39 (this record still stands as the most accurate manual geometric calculation of π).

If you want to calculate these yourself, you need to know the side length of your n-gon. This can be calculated using the tangent function, opposite over adjacent. Since the radius is 1 in our case, we just do tan(π/n) where n is the number of sides*. (This was much more difficult for Archimedes!)

 

*Here's why: dividing π by the number of sides gives us the degree measure of the the top angle in a triangle formed by connecting  the polygon's to the center of the circle. Half of this measure is the angle measure of the right triangle shown above; if we take the tangent of this angle, it gives us the value of opposite/adjacent:  = (s/2)/(1/2) = s. AWESOME! Since  s is our side length, we found that simply taking tan(π/# of sides) gives us the length of one of those sides (in the case where the diameter is 1). In general, the length of the side is found by multiplying tan(π/n) by the diameter.

Infinite Series Calculations of π

This kind of calculation results when a pattern of numbers, being summed or multiplied repeatedly, converges on a mathematical constant (or some fraction thereof).

Though an Indian mathematician named Nilakantha discovered the idea of using an infinite series to calculate π around 1500, they weren't used in the West until the 1600s. Old Nilakantha's  series is actually pretty good:

 

After 4 terms it's at 3.1452...! The first known Occidental series was this one, found by Fracois Viete:

Notice that it is less than ideal because it depends on the square root of two, another difficult number. In the 1670s, the Gregory-Leibniz series was found:

The 20th century gave us computing and iterative algorithms that are calculating ever more digits. Interestingly, it also saw several new infinite series that are faster than these iterative algorithms and less memory-intensive. Ramanujan found this one in 1914:

And in 1987, the Chudnovsky brothers came up with this bad boy, which produces about 14 digits of pi per term!

 

Needless to say, it was used for several record-setting calculations. Including the first to surpass 1 billion digits (1989) the first to surpass a trillion (2009), and 10 trillion (2011).

Area of a Circle

One last thing for now: since we talked about pi, and since we talked about the area of squares (and triangles), we should definitely end with the area of a circle. For this, you probably memorized the formula A=πr², but what does this mean? It means that if we take the radius, make a square out of it, and multiply that square by pi, we have the area. Can we connect this to the way we found the area above, i.e, length-x-width or base-x-height? Absolutely! 

Imagine unpeeling tiny layers from a solid, filled-in circle and laying them side by side until there are no layers left (as in the picture below). The first layer you peel off is a circumference (its length is 2πr) the next layer is a tiny bit shorter, and the next is shorter still, and so on... Eventually, you will have unpeeled your whole circle to form a triangle with a base as long as the radius of the circle and a height as long as the circumference: this is the top triangle in the picture. Well, what's the area of this triangle? (Base x Height)/2, right? So that's radius times circumference divided by 2, or (2πr x r)/2 = πr² = Area!