beanz Magazine

Public Key Cryptography

Jeffrey Avellanosa on Flickr

This cryptography method is based on the fact some tasks are relatively easy to do, but extremely difficult to undo.

For thousands of years passing secret messages was extremely risky business. If a queen in Redland needed to tell a queen one hundred miles away in Greenland that the king of —– was planning an attack on her kingdom, she had a couple choices. She could travel to Greenland herself (and hope for a safe trip), or she could write a letter and send it with a trusted courier (and hope for a safe trip for him).

Queens, as well as other high-ranking government officials, rarely deliver top secret messages themselves. They need a trustworthy person to deliver their messages for them. And they know that there was always the risk of messages being lost or stolen, so they often do some sort of letter scramble or replacement to create a code that can only be read by someone with the key.

For example, if the queen of Redland (Queen Redalia) needs to tell the queen of Greenland (Queen Greensborogh) that her kingdom will be attacked on her land on April fifth at three PM, it would be too risky for her to write out “Attack April fifth, three PM”. Instead, she might create a key such as the one that follows:

a = c
b = d
c = e
d = f

z = b

And continue on down to z = b. Then she could send the message: cvvcemcrtknhkfvjvjtggro. Even if this coded message were to fall into the wrong hands, no one could read it without knowing the key. And so went creating and sending secret messages for centuries and centuries.

However, there are at least two major problems with this way of communicating sensitive information. One is that the receiver and sender must both know the key, and getting the key from one person to the other is risky business. The second problem is that those in power are very motivated to figure out how to crack such codes. Over the years, they often had their top mathematicians devise methods for decoding messages.

Code writing, code breaking, and code interception continued on as such until the 1970s. Around this time mathematicians Whitfield Diffie and Martin Hellman came up with a way in which two people, say Queen Redalia and Queen Greensborogh, could create a secret key and share it with each other without the need to pass any secret message. How did they do this?

Although the details of their method require at least high-school level mathematics, the basic idea is based on the fact that some tasks are relatively easy to do, but extremely difficult to undo.

A common example is mixing paints of different colors. It is easy to mix a teaspoon of red with a teaspoon of blue to produce purple, however it is extremely difficult (perhaps impossible), to “unmix” the purple to get back to the blue and red.

You may be thinking that just about everyone can guess that the purple was made using blue and red, however if we mix several colors together in various amounts to create a new color, most likely no one would be able to guess what colors and what quantities were used. Take a look at the example below.

Let’s say Queen Redalia pours out a teaspoon of dark red and doesn’t tell anyone.


Around the same time Queen Greensborogh pours a teaspoon of green, and also keeps this information to herself.


Then Queen Redalia tells Queen Greensborogh to mix her color with one teaspoon of dark blue to come up with another color.


Queen Redalia also mixes her color with one teaspoon of blue.


Everyone in the world is allowed to hear that both queens have mixed their secret colors with one teaspoon of dark blue, so no secret message needs to be delivered.

Now Queen Redalia sends her mixture of red and dark blue to Queen Greensborogh. Queen Greensborogh does likewise. Their mixtures are also not secret so it is ok for others to see them.

When the queens receive each other’s mixtures, they each add one teaspoon of their secret color to the mixture that the other queen created. What will each queen see?

Queen Redalia now has the following mix: one teaspoon of green mixed with one teaspoon of dark blue, mixed with one teaspoon of dark red.


Queen Greensborough now has one teaspoon of dark red mixed with one teaspoon of dark blue, mixed with one teaspoon of green.


The order that the colors were mixed in doesn’t matter! They both end up with the same “key”; the same color that is produced by mixing equal quantities of dark red, green, and dark blue (in this case a grayish color). To top it all off, they didn’t have to send a single secret message to produce a key that they can both see, but no one else can figure out!

In math, there are also tasks that can be done fairly easily, such a mixing paint, but that are much slower to undo.

For example, multiply 18 x 12. If you have practiced multiplication, it probably takes you under one minute to figure out the result is 216. Now give the number 216 to a friend whose knowledge of math is similar to yours, and ask her to guess what two numbers you multiplied to come up with 216. Most likely it will take her much longer to guess your numbers than it took you to complete the multiplication.

If we had multiplied two much bigger numbers to get something like 4,627,352,894,891,336 or even bigger, the task of guessing our numbers eventually gets so tedious that even computers would need hundreds of years to go through all possible combinations.

This is the basis (though far from the complete story) for how two the mathematicians, Duffie and Hellman, developed a method to create secret keys without sending a single secret message.

Their work is the foundation for what is known as public key cryptography. Today not only can government officials read and write secret warnings about military operations, but every person with a credit/debit card and access to the internet can share confidential information (card number) with sites such as Amazon to make purchases. And our confidential information is better encrypted than the most sensitive military information ever was all the way up through the cold war.

Without even realizing it, most Americans have established a public key with at least a few companies to conduct confidential transactions online. In fact, public key cryptography has been a major factor in transforming the way business around the world is conducted over the past twenty years!

Learn More

Public Key Cryptography

https://en.wikipedia.org/wiki/Public-key_cryptography

“Diffie-Hellman Key Exchange” in plain English

http://security.stackexchange.com/questions/45963/diffie-hellman-key-exchange-in-plain-english

Whitfield Diffie

https://en.wikipedia.org/wiki/Whitfield_Diffie

Martin Hellman

https://en.wikipedia.org/wiki/Martin_Hellman

What is Modular Arithmetic?

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

History of Codes

http://www.bitsbook.com/wp-content/uploads/2008/12/chapter5.pdf

Also In The February 2017 Issue

This cryptography method is based on the fact some tasks are relatively easy to do, but extremely difficult to undo.

There's a way to find out if your online passwords have been stolen, and how to prevent it.

Racket is a fun and easy programming language to learn because it's all about creating colors and shapes as you learn.

Networks are a mostly hidden but critical part of the internet.

Surveillance cameras, satellites, RFID tags, and social media activities all create unique digital footprints.

Developers deal with common problems in their work. Here’s are a few problems and how to overcome them.

Programmers use libraries but instead of books they create and share code, often for free, to help solve common problems.

These cards are a fun way to learn Scratch, look up how to do things, and make applications.

Another mysterious four-letter acronym that helps secure information online.

Dorothy Vaughn, Mary Jackson, and Katherine Johnson not only helped make history, they are part of a long line of women in computing

It's almost time to think about summer tech camps if your kids are interested. Here are a few questions to ask.

Your web browser knows (and tells) a lot more about you than you might realize.

When you pick a programming language to learn first, it helps to figure out what software you want to create.

This odd acronym offers security protection beyond your password. Here are a few examples of how 2FA works.

Links from the bottom of all the February 2017 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for February 2017.