We begin by looking at the math behind encryption. We start with a simple rotation (shift) of the alphabet be N places, where N is an integer less than the number of characters in the alphabet. For this activity, an alphabet consists of all the characters we want to include in our code: letters, numbers, and maybe a few special symbols. For example:
Alphabet = a - z 0 - 9 (a b c d e ... x y z 0 1 2 ... 7 8 9)
N = 3 (look three characters to the right to get the corresponding character for your code)
To encrypt "hide:"
h --> k
i ---> l
d --> g
e --> h
hide --> klgh
To decode the message, we rotate to the left:
k --> h
l ---> i
g --> d
h --> e
klgh --> hide
[Notice that we use "shift" and "rotate" interchangeably throughout this discussion.]
For the characters at the end of the alphabet, we just wrap around to the beginning:
5 --> 8
6 --> 9
7 --> a
8 --> b
9 --> c
When we decode, we rotate in the opposite direction: c --> 9, b --> 8, a --> 7.
To analyze encryption mathematically, we assign numerical values to the characters, starting with 0:
a = 0
b = 1
c = 2
...
z = 26
0 = 27
1 = 28
...
8 = 34
9 = 35
Mathematically, we rewrite "three characters to the right of 8 is b" as 34 + 3 = 1 (sort of, read on).
What we have is the set of numbers {0, 1, ..., 34, 35} where 34 + 3 = 1.
That is, we are performing modular arithmetic, sometimes called clock arithmetic. The correct way to write the above summation is:
34 + 3 = 1 (mod 36)
Historical note: If various sources on the Internet are to be believed, Julius Caesar used a rotation method with N=3.
Activity 1: Encrypt a short message (for example, hurry up) and then decode it. Try two values of N.
Activity 2: Write a short message and exchange it with a message from a fellow student. See if you can decipher the code. Did you come up with any ideas as to how to decode a message? Write a short paragraph in your journal describing how you decoded, or tried to decode, the message.
Jump to the top of the page.
Rotational methods for encrypting messages are simple, but they are also simple to break. To add a level of complexity, we first write our method as a mathematical function: y = f(x), where x is the character to be encrypted, f is the rotation, and y is the encrypted character.
[For a reason we discuss later, we add a character to our alphabet. In this example, the dash is added. What character you choose to add is not important, increasing the alphabet size to 37 is what matters.]
The expression for shifting characters by three characters: y = f(x) = x + 3 (mod 37)
Plotting the equation on the X-Y plane:
If we write
y = x + 3
as
y = 1 * x + 3,
what do the "1" and the "3" represent?
The "1" is the slope and the "3" is the y-intercept.
When we change the amount of the shift (that is, change the value of the y-intercept), the line moves to the right or left, but keeps the same slope. We call this move a translation.
What if we change the slope? For example, let's set the slope equal to 2:
Character a still goes to d, but b now goes to f rather than e and d goes to j rather than g. By increasing the slope, we increase the gap between the target characters of our function.
Slope of 2 --> consecutive characters go to characters that are two apart (a --> d, b --> f).
Slope of 3 --> consecutive characters go to characters that are three apart (a --> d, b --> g)
To see what is going on, use the numerical representations of the characters:
a = 0,
| 2*0 + 3 = 3 (mod 37) = 3,
| character 3 = d
|
b = 1,
| 2*1 + 3 = 5 (mod 37) = 5,
| character 5 = f
|
c = 2,
| 2*2 + 3 = 7 (mod 37) = 7,
| character 7 = h
|
z = 25,
| 2*25 + 3 = 53 (mod 37) = 16,
| character 16 = q
|
Why does a always map to the same character (d in our examples), regardless of the slope? (Hint, use the numerical values for the characters.)
The use of a line to map one set of characters to another set of characters is called an affine cipher.
Encrypting a message is pretty straight forward. Just set x to the numerical value of the character and evaluate f(x). However, decoding a message is a bit more challenging. Before discussing the mathematical approach, here is a "low-tech" way to decode the text.
Create an Encrypted list that contains the encrypted characters found in the Original list. To encrypt a message, replace the character in the Original list with the corresponding character in the Encrypted list. To decode a message, replace the character in the Encrypted list by the corresponding character in the Original list. Here are partial lists derived from f(x) = 2 * x + 3 (mod 37):
Original
| Encrypted
|
a
| d
|
b
| f
|
| c | h |
x
| m
|
| y | o |
| z | q |
7
| 6
|
8
| 8
|
9
| -
|
If you need to decode h, count down to h's position in the Encrypted list (3). Find the corresponding character in the Original list (3rd character is c), so h is the code letter for c. Whenever the key changes you will need to recreate the Encrypted list. Hopefully, WIA has it together enough to make sure all our operatives know the proper key.
In the mathematical approach to decoding a message, we note that the opposite of multiplication is division, but how do we perform division mod N? For example,
y = f(x) = 2 * x + 3 mod 37,
encrypt r --> x = 17
f(x) = f(17) = 2 * 17 + 3 (mod 37)
= 37 (mod 37)
= 0 --> a
Thus, r gets mapped to a. If we receive an a in an encrypted message, how do we get back to r?
To decode a, we evaluate
x = (y - 3) / 2
The result (x) must be an integer. Turns out, division in modular arithmetic is not as easy as dividing one number by another. The most common way to perform division is to revert back to third grade arithmetic:
x = y / a --> y = x * a
We observe that the second expression (the one to the right of the arrow), states that y is a multiple of a. What we do not know, is the value of the multiple x: is y twice a? three times a? etc.
To find x:
Start with x = 1, compute 1 * a. If 1 * a = y, then we found the answer (x). Otherwise,
set x = 2, compute 2 * a. If 2 * a = y, then we found the answer. Otherwise,
set x = 3, compute 3 * a. If 3 * a = y, then we found the answer. Otherwise, ...
Here is why we added an extra character to our alphabet. For the above procedure to work, we need to know that eventually we will find the correct value of x, even if we end up testing every single character in our alphabet. As an exercise, try to show that if we left the alphabet size at 36, we would not test every character before we start repeating. (We looked at this phenomenon in class, but it is probably worth a second visit.)
The bottom line is that the slope of our equation must be relatively prime to the number of characters in our alphabet; that is, the slope and the modulus must not share any factors. (For our purposes, we consider this a "statement to believe," although it is worth a try at understanding the reason for this requirement.
Example: Suppose we need to encode numbers made up of the 10 digits, 0, 1, 2, ..., 9. The modulus is 10. Let's try the formula
coded = 2 * original + 3
0 --> 3
1 --> 5
2 --> 7
3 --> 9
4 --> 11 mod 10 = 1
5 --> 13 mod 10 = 3
6 --> 15 mod 10 = 5
7--> 17 mod 10 = 7
8--> 19 mod 10 = 9
9--> 21 mod 10 = 1
1583 --> 5399
Decoding,
5 --> 1 or 6, which one? Similar problem with 3 and 9.
We need to have the 10 digits map to 10 unique values. Try a slope of 3 (3 * original + 3):
0 --> 3
1 --> 6
2 --> 9
3 --> 12 mod 10 = 2
4 --> 15 mod 10 = 5
5 --> 18 mod 10 = 8
6 --> 21 mod 10 = 1
7--> 24 mod 10 = 4
8--> 27 mod 10 = 7
9--> 30 mod 10 = 0
We see that each digit is mapped to a unique digit. When we decode, we will have no ambiguities to confuse us.
One way to guarantee the relative prime requirement is to the size of the alphabet be a prime number.
Thus, we added one character to get to 37, a prime number.
Another option is to make the slope a prime number that is not a divisor of the modulus. If we want to keep the size of our alphabet at 36, we could use the first prime that does not divide 36; that is, slope = 5.
For an affine cipher, the key is the slope and y-intercept of the equation we use to map the original characters to their encrypted values. Remember, the slope must be relatively prime to the number of characters in the alphabet. The easiest way to guarantee this relationship is to add characters until we have a prime number in the set.
Activity 3: Encrypt a short message using an affine cipher. Exchange code with another student and see if you can decode each other's message. Exchange the coded message and the key with a different student and see if the code is easy to understand. Remember the two parts to an affine cipher's key.
Activity 4: Copy the Scratch program encryptByShifting from the Math Enrichment folder in ClassroomFolders/MiddleSchool to your desktop or another folder you created.
Double-Click the program icon to start it.
Click the green flag (upper-right) to initialize the program.
Click the Encode button to enter a message. Hit the Enter key or click the check mark when done entering your message.
The encrypted text is displayed on the screen.
Click the Decode button to see what the coded message would look like if sent to a "friendly."
Look at the code under the "when clicked."
Notice that keyTranslation is set to 3. Click on the 3 and replace it with a different number.
Click the green flag and then the Encode button to produce a new encrypted message.
What does this message have in common with the first one you created?
[Note: we have several Scratch programmers in the class who can help with this activity.]
What about the message at the beginning of the introduction: cxvn-0xy-0dybx5ognb0x5y?
The key is : slope = 5, y-intercept = 3 (y = 5x + 3). Now, you should be able to decipher the message.
Review:
We have seen how two mathematical concepts, modular arithmetic and prime numbers, join together to support the encryption of messages. We need modular arithmetic so that characters get mapped to characters. When we apply on encryption formula (e.g., encrypted character = 3 * original character + 2), we will end up with numbers that are out of the range of our alphabet. For example, if we are just using the 26 letters, j is represented by 9, so 3 * 9 + 2 = 29, which is greater than 25. (Remember, a = 0, b = 1, ..., z = 25.) Using modular arithmetic, addition and subtraction is mod 26:
3 * 9 + 2 (mod 26) = 29 mod 26 = 3, so j is coded as a d.
Prime numbers come in the side door. We saw that encryption formulas (affine codes) require that the slope and modulus must be relative prime. For the standard alphabet, a - z, the modulus is 26. A slope of 2 produces a sequence of characters that repeat before generating a code for all the characters; that is, two (or more) characters are mapped to the same coded character. In math, we say a function is "onto" when all the elements of the set "get hit" by the function. The function y = 2x + 3 on the set of 26 letters is not onto: only the "odd" characters (that is, the characters represented by odd numbers) are generated. (To really understand the need for relative primes, you need to work out the math by hand. Try y = 2x + 3 and y = 3x + 2 and compare the two sets of coded characters.)
Jump to the top of the page.
In this activity, we will investigate some properties of graphs. We are not talking about plotting values on an X-Y (Cartesian) plane, but rather the drawings we have been producing for several years with Inspiration.
We will define a graph by looking at its properties; that is, what we see when we are looking at a graph. We will also investigate a special property known as a perfect code. To illustrate our understanding of graphs, we will create a perfect code that we will use to hide an encrypted message. Just an FYI: the name "perfect code" comes from computer science - error correcting codes - and not from writing secret messages.
Describe the knowledge map (aka, mind map) shown above. At some point, you probably made a statement like "ovals connected by arrows or lines." If you did, then you pretty much defined a graph.
Definition: A graph is a collection of vertices (the ovals) and edges (the arrows) connected the vertices.
Some vertices may stand alone but edges must connect two vertices. The graphs we will use have no direction, so we will connect vertices with lines without the arrowheads.
Definition: The neighborhood of a vertex is the vertex itself and all the other vertices connected to it by an edge. We will call the vertex labeled with 0 the central vertex.
The vertices labeled 0, 1, 2, 3, 4, and 5 make up the neighborhood of vertex 0.
We now have two neighborhoods, one centered at 0 and another at a.
[Note: Vertex 5 has a neighborhood too, consisting of vertex 5 and vertex 0. Don't let the layout of the graphs confuse you; a neighborhood of a vertex does not mean that the vertex is located in the middle of a group of vertices. The actual layout is irrelevant. All that matters is what vertices are connected to a vertex by edges.]
How can we use graphs like those shown above to encrypt a message?
What if each neighborhood represents a character? The character is coded as a number, just like in the previous activity. To get the number, we sum all the numbers in the neighborhood. For example, the character's number in the first example is 15: 0 + 1 + 2 + 3 + 4 + 5.
Here are three neighborhoods that together spell "run:"
One problem writing coded messages as separate neighborhoods is that it is easy to spot the characters. To break the code you (just?) need to figure out how to combine the numbers to produce a character.
To make decryption more difficult, we will add more edges. We do not add edges willy-nilly; the restriction is that we cannot add an edge to our "center" vertex of the neighborhood. This restriction should be apparent: if we add an edge to the center vertex, then we will change the value of the character represented by that neighborhood.
The first neighborhood sums to 21 rather than 17; that is, a v rather than an r.
Here are the first two neighborhoods camouflaged with extra edges.
Even though we connected the vertices with labels 1 and -2, they have not joined each other's neighborhood.
We have created a perfect code: each vertex is in no more than one neighborhood of a central vertex.
The graph with the connected neighborhoods is more difficult to figure out; unfortunately, it may be too difficult for our own agents to understand. As part of the key that is associated with our code, we need to identify which vertices are the centers of the neighborhoods. For this activity, we will color the vertices in such a way that the centers will all have the same color and no other vertex will have that color.
We have created a perfect code:
We have a set of vertices and edges.
We have neighborhoods centered at different vertices.
No vertex is in more than one of these neighborhoods.
In our example, the neighborhoods are centered at the brown vertices. No non-brown vertex is in more than one brown-centered neighborhood.
Time to write your own coded message as a graph.
Activity 5: Write a secret message using a graph containing a perfect code. Start by creating the neighborhoods, one for each character. Then add extra edges and color. Since creating a graph takes time, make your message short; e,g, "hide."
Here is Amy's message. Can you decode it?
Hint: You know that a graph should include a perfect code. You need to remember the definition of a perfect code so that you can analyze the graph and find the centers of the neighborhoods that satisfy the definition. For example, the center vertices cannot be connected to each other. Can you find vertices in the graph satisfying this requirement? If you can, what do you do next? Try it.
Review:
A graph is a collection of vertices and edges. A vertex is represented by some geometric figure (oval, rectangle, sphere, etc.) and usually represents some bit of information. An edge connects two vertices. One vertex may be connected to several other vertices.
A neighborhood is a central vertex plus each vertex connected to the vertex by an edge.
A perfect code is a set of vertices such that each vertex resides in only one neighborhood of a central vertex.
We can code a message by assigning a character to a (small) graph. We connect the characters - the small graphs - with edges, but we maintain the convention of the perfect code: no vertex is used in constructing more than one character.
Jump to the top of the page.
Send a message to our Kaliningrad, Russia operatives that we are on the way. We maintain four safe houses in Kaliningrad, shown by the little houses on our WIA satellite imagery. (Actually, it's Google Earth, but it is much cooler to call it WIA satellite imagery). We need to visit the safe houses, passing over the five bridges shown in the image as well as the two tunnels marked with dotted red lines. To be safe, we will use each bridge and tunnel exactly once. Is this possible? If not, we better be extra careful.
Activity 6: Try devising a route that crosses the five bridges and two tunnels exactly once. You may find it easier to draw a picture of your own, similar to this one:
Here is an attempt to cross each bridge and tunnel once:
Notice that we cannot cross the bridge connecting the island with the land to the west.
If you cannot find a solution, is there something that consistently causes you to fail?
About 250 years ago, a mathematician named Leonhard Euler discovered an interesting property of graphs. Actually, he wrote up his answer in 1736; I'll let you do the math to compute how long ago the discovery was made.
[The actual problem in mathematics is called the Seven Bridges of Konigsberg. The city of Konigsberg is now called Kaliningrad. Euler really did use the city and its bridges to start up graph theory. Since we see only five bridges with Google Earth, we can guess that two of the bridges have fallen down, or otherwise have been removed. ]
To see what Euler did, redraw the map to look more like a graph:
Euler pointed out that to traverse each edge exactly once, all but two vertices must have an even number of edges connected to them. Why?
[Think of each vertex as a house and each edge as a trail between two houses. You enter and leave a house, so we can see why it makes sense to have an even number of edges. Can we ever have an odd number? What about the house where you start? You may leave there and not return again; thus, it is OK to have one house with an odd number of edges. What about the house where you stop? You may have already visited this house, so there can be two, four, six, etc. edges already leading in/out of the house. When you return for the last time, you are on an edge that makes the total an odd number.]
From the above parenthetical discussion, hopefully you can follow Euler's argument.
Look at the graph representing the map of Kaliningrad.
| Edge | Number of Edges |
| Left-most | 5 |
| Top | 3 |
| Bottom | 3 |
| Right-most | 3 |
Select two of the houses as our initial and final stop. Having an odd number of edges at these houses is OK (make sure you know why), but we still have a problem at the remaining two houses. The odd number of edges there implies that we enter but never leave, which is not possible.
Definition: A path in a graph is a sequence of vertices connected by edges. Essentially, you can visit each vertex by following the edges.
Definition: An Eulerian path is a path in a graph that follows each edge exactly once.
That is, once you have followed an edge, you cannot go on it again.
Definition: The degree of a vertex is the number of edges connected to it.
Mathematically speaking, Euler is saying that no more than two vertices have an odd degree.
Activity 7: Add a new safe house somewhere in Kaliningrad. Redo the links so that each hose is connected to all the other houses) so that the graph containing all the safe houses forms an Eulerian path. Draw the path over the edges to show how you would use each edge exactly once to visit the five houses.
Jump to the top of the page.
Hamiltonian Path (Traveling Salesman Problem)
For a slightly different look at graphs:
Definition: A Hamiltonian path is a path in an undirected graph that visits each vertex exactly once.
Redo the edges so that each house is connected to all the other houses. See the picture below.
Look at the graph with houses representing the vertices. We have labeled the vertices to make our discussion a little easier, plus we now rate each edge with a degree of danger, 1 being the safest and 5 being the most dangerous. We want to visit each of our five houses once, but we need to visit them using the safest path.
The general problem is called the Traveling Salesman Problem (TSP). If you continue with computer science in college, you will most definitely look at this problem again.
Activity 8: Visit each of the five houses (vertices) by following the safest path; that is, the path with the smallest sum of danger values.
Example: One path is A -> B -> C -> D -> E. The danger level is:
2+ 3 + 2 + 4=11.
Can you devise an algorithm (a set of steps) that anyone can follow to find the safest path?
The general idea is to check out every possible path connecting the five houses. One observation to make is that as you compute a new total danger score, if the total score already exceeds the smallest so far, there is no need to continue. The path you are currently trying cannot be the safest.
We will not spend any more time on this problem, but feel free to work out an algorithm for visiting the houses using the safest path.
A final observation about visiting vertices:
In the previous example, we can get from any one house to any other; that is, we can visit the houses in any order. Question: how many paths can we generate? We saw one path: A - B - C - D - E. We also have A - B - C - E - D. Etc.
To compute the number of paths, we draw a template for the answer:
____ ____ ____ ____ ____
How many houses can we select for the first option?
Five, any one of the houses.
Once we have selected one house, then how many houses can we select for the second option?
Four.
Continue ...
The numbers of houses per option are 5, 4, 3, 2, and 1.
In mathematics, the Product Rule states that if there are N ways to do one task and M ways to do a second task, then there are M*N outcomes to performing both tasks, assuming that the two tasks are independent of each other. With this rule in hand and thinking of the house selection tasks, we have that the number of paths (that is, the number of ways we can order the houses) is 5 * 4 * 3 * 2 * 1 = 120. The term factorial signifies the multiplication of n * (n-1) * (n-2) * ... * 2 * 1, written n!. So, there are 5! paths from which to choose.
Jump to the top of the page.
Jordan Curve (Gas, Water, Electric)
One more graph problem:
We need to reorganize our safe houses and divide the work between our Russian colleagues and our own team. We add another house to bring the total to six: three houses, labeled 1, 2, and 3 in the picture below, are the U.S. houses; three houses, labeled A, B, and C, are the Russian houses. We need to set up lines of communication (LOC) between each U.S. house and each Russian house; that is, we need a line from 1 to A, 1 to B, 1 to C, 2 to A, 2 to B, 2 to C, 3 to A, 3 to B, and 3 to C. The lines live on the earth (they cannot go underground) and they cannot cross each other. Can we do this?
Here is one attempt to connect our houses to our allies:
Can you already see the problem?
Try connecting house 3 with house B. The two lines, 1 - A (red) and 2 - A (yellow), form a region surrounding house B. (You cannot go through a house, so think of the yellow and red lines being connected at houses 2 and A.)
Since B is on the inside and 3 is on the outside, there is no way to connect them without crossing the boundary; that is, without crossing an existing LOC.
Formally, we have an example of the Jordan Curve Theorem.
Definition: A Jordan curve is a non-self-intersecting continuous loop in the plane.
Here is an example of an intersecting loop:
The Jordan Curve Theorem states that any continuous simple closed curve in the plane (a boundary), separates the plane into two disjoint regions, the inside and the outside. Furthermore, a continuous line connecting two points, one inside and one outside the boundary, must cross the boundary.
For us, continuous means you cannot pick up the pencil and put it down again so that there is white space in between the line segments: no gaps.
Simple means no loop-de-loops.
Since house 3 is on the outside region and house B is on the inside region, we cannot connect the two without crossing the boundary; that is, crossing an existing LOC.
Oh well, that's what satellites are for.
Review
A graph is a collection of vertices and edges. A vertex is represented by some geometric figure (oval, rectangle, sphere, etc.) and usually represents some bit of information. An edge connects two vertices. One vertex may be connected to several other vertices.
The degree of a vertex is the number of edges connected to it.
A path in a graph is a sequence of vertices connected by edges. Essentially, you can visit each vertex by following the edges.
An Eulerian path is a path in a graph that follows each edge exactly once. That is, once you have followed an edge, you cannot go on it again.
A Hamiltonian path is a path that visits each vertex exactly once.
Euler pointed out that if we want to follow each edge exactly once (that is, we want to follow an Eulerian path), all but two of the vertices must have an even degree. Using this observation, we see that we cannot follow an Eulerian path with the layout of houses (vertices) and bridges/tunnels (edges) shown at the beginning of this section.
A famous math problem is the traveling salesman problem. We want to visit each city (vertex) exactly once. The trick is that each edge has a cost associated with it. The cost can be the distance between two vertices, the actual cost to fly to one city from the other, or our danger rating. The path we take in the process of visiting all the cities should sum to the smallest value. If the cost associated with each edge is distance, then we have traveled the shortest distance while visiting all the cities.
Definition: A Jordan curve is a non-self-intersecting continuous loop in the plane.
The Jordan Curve Theorem states that any continuous simple closed curve in the plane (a boundary), separates the plane into two disjoint regions, the inside and the outside. Furthermore, a continuous line connecting two points, one inside and one outside the boundary, must cross the boundary.
Another famous problem is called the water, gas, and electric problem, or the utilities problem. The goal is to connect water, gas, and electricity to three houses without crossing a line. We see by the Jordan Curve Theorem that one of the houses will not get a utility.
Jump to the top of the page.
River Crossing Problems (Cannibals and Missionaries)
Trouble is brewing in Kaliningrad. The Cortemaderians have infiltrated our spy network and both the Russians and Americans need to get off the little island ASAP. We have three operatives on the island, as do the Russians. The problem is that we have just one small canoe, allowing only two people to cross the river at one time. To further complicate the evacuation, we do not trust the Russians: we never want to be outnumbered on either bank of the river. For example, it is OK to have two Americans and one Russian on the island, one American and no Russians on the mainland, leaving two Russians in the canoe. (Make sure you understand that this scenario is safe.)
The goal of the exercise is to start with three Americans and three Russians on the island and end up with the three Americans and three Russians on the mainland. Another way of saying this goal is that we want to go from three agents each to no agents on the island without ever allowing the Russians to outnumber us.
Activity 9: See if you can get all the operatives off the island satisfying the restrictions written above. Start with six operatives, three Americans and three Russians, on the island. With a canoe that holds only two people at most (it is OK for one person to cross), move everyone to the mainland but never allow the Russians to outnumber the Americans on the island or on the mainland.
The basis of the following discussion was sent to me by Michael Matsumoto of Adobe Systems. We will tie in a solution to the river crossing problem to graph theory by first representing the number of Americans and Russians on the island as the ordered-pair (a, r). The exercise begins with the state (3, 3) and ends (hopefully) with (0, 0). If the first crossing were to include two Russians, then the second state is (3, 1). Given that we cannot have more Russians that Americans, what are the acceptable states?
(3, 0) (3, 1) (3, 2) (3, 3)
(2, 0) (2, 2)
(1, 0) (1, 1)
(0, 0)
The layout of the acceptable states is not by accident. Think of an X-Y graph, this time with the number of Americans on the X-axis and the number of Russians on the Y-axis.
