Public Keys, One Way Functions and Hard Problems

Provided by TryEngineering - www.tryengineering.org

Student Resource: 
The following information will help you complete the exercises in this lesson.

A cipher is a simple kind of lock. For example, a password is a cipher.  It is a secret code that allows two parties (e.g. two people) to agree that they can share information. Only if you know the cipher or ‘password’ can you be trusted with the information.  

Any cipher can be broken. Eventually. This is a fundamental idea in theoretical computer science – that until you can prove that a lock is unbreakable, you cannot claim that it is. The best that computer science can do to protect information on the Internet is to make it extremely time consuming for someone to figure out your cipher. If it takes too long, trying to figure out the cipher becomes useless.

The scenario to imagine is that two people want to allow each other access to their rooms, without allowing anyone else to enter.  But they can’t speak to each other (e.g. sharing their password) because others are always listening in. If there is a time limitation on giving the secret password, then a third party can’t enter the room if they can’t figure out the password in time. 

The Internet protocols have a format that anyone can access. Otherwise the Internet wouldn’t work. This means that if you want to keep information private you have to encrypt it with a cipher.  But you can’t send your cipher on the Internet because it could be intercepted.  The paradox led to the idea of public keys. 

A public key is a kind of cipher that allows two parties to share information when they cannot establish a private code or password. They need a way to make public only part of their shared secret. The key will work if the two individual secrets are combined in a way that produces a one-way function.

A one-way function is a powerful idea in mathematics. One-way problems are those that are easy (and often immediate) to solve in one direction.  However, the inverse problem, that is, starting with the answer and calculating the starting value is almost impossible (e.g. takes an incredibly long time) unless you have some pertinent information.  Often, reversing a one way problem also involves trial and error, or from a mathematical standpoint trying all the combinations of possible solutions. Keeping part of the information needed in a one-way function secret is the basis of public key encryption. 

The Diffie-Hellman Algorithm uses the mathematical ideas of exponents and modulo (remainder) to create one-way functions so that two parties can share some, but not all information.  Worksheet #2 shows you how to use exponents and modulo arithmetic. 

Algorithmic Complexity is a computer science technique for determining how long it will take for an algorithm to produce a solution.  ‘Hard’ problems are those that will take an extremely long time to solve.  Matching paint color and reversing one-way functions are both hard problems because they require trial and error to solve without key information. 

Public Keys and One Way Functions
Student Worksheet 1:  Mixing Colors

Directions:
In this lesson you will directly experiment with the color example of public key encryption. Using the public key video shown by your teacher, write down the rules for color mixing on the back of this sheet or on a separate piece of paper.  Hint: there is an essential component to getting the color right that is not mentioned in the video.  What do you think it is?  Before you try to create secret colors, experiment with what it means to get the color right.  Don’t see it, or running out of time?  See if others in your class have figured it out!

In your group of three, assign someone to be the ‘spy’ and two others to be the ‘color makers’. When the color makers create their secret color, make sure the others are not watching.  Once you’ve established all the necessary colors, time how long it takes the ‘spy’ to try to generate the shared public color.  Is it even possible?

Questions:

1. What is the missing information in the color mixing technique?  Why is this important?

2. Were you successful in creating a public color using the secret colors? In other words, were the color makers able to consistently create it?  Was the spy able to create it, and if so, how long did it take?
1.	

Public Keys and One Way Functions
Student Worksheet 2: Diffie-Hellman

Practice with Exponents:
In your group, practice calculating exponent arithmetic by hand. Remind each other that exponents are shorthand for multiplying a number by itself, a number of times.  For example, 43 = 4*4*4.  (Note that computer scientists use ‘*’ for multiplication instead of ‘X’.) Make up problems for each other that are reasonable to solve, such as 25, 42, 104, 83.  Make sure everyone knows how to solve these problems.

Practice with Modulo:
In your group, practice calculating modulo.  Remind each other that modulo is the remainder when you divide.  For example, 11 modulo 4 is 3 because 11/4 results in a quotient of 2 and a remainder of 3.  Make up problems for each other that are reasonable to solve.  If your teacher allows it, use a modulo calculator such as http://www.miniwebtool.com/modulo-calculator to check your answers. You might also want a faster way to find the remainder without doing long division. Here is a hint: long division keeps track of the number of times you subtract the divisor. Some people find repeated subtraction to be easier (and faster) than long division.

Practice Exponents and Modulo:
The Diffie-Hellman encryption method relies on the fact that raising a result to another exponent is equal to multiplying the two exponents.  For example: 
Convince your group that is true, perhaps by multiplying 2 by itself twelve times. 

Creating a One-way Function with Secrets:
Try creating a public key using the Diffie-Hellman trick.  The public key encryption https://www.youtube.com/watch?v=YEBfamv-_do video uses ‘17’ for the prime modulus and ‘3’ for the generator. These numbers are public.  Don’t worry about why they were chosen. The first formula below calculates ‘P’ based on two secret numbers, ‘s1’ and ‘s2.’ Within your team, assign roles of ‘code maker’ to two people and ‘spy’ to the third.  One code maker secretly picks a number for ‘s1’, calculates ‘R1’ and shares it with everyone. The second code maker picks a value for ‘s2’, calculates ‘R2’ and shares it.  Your teacher will instruct you on whether you can use calculators or online resources, or whether you have to do arithmetic by hand. Start a timer. Both code makers should be able to calculate ‘P’ quickly and should note how long it took.  Give the spy at most five minutes to calculate ‘P’. Was that enough time? Discuss how to speed up the spy’s procedure.  Discuss how to make it harder for the spy?