I started class by checking on the status of the cryptology research paper. Students felt good about where they were at on this project. I told them that the report is due on Tuesday and that presentations would take place on Thursday. This allows students to make use of the two Resource periods available to them on Wednesday and Thursday morning to finalize their presentations as a group.
We then looked at the Diffie-Hellman exchange process. I use an activity that I read about in NCTM's Mathematics Teacher. In this activity, two students act as Alice and Bob. They are each given a bag and asked to place colored disks in their bags, not allowing anyone else, including each other, to know what they placed in the bag. The rest of the class acts as hackers waiting on the internet.
The bags represent packets of information. Anyone can make a copy of a packet, they just don't know what the actual contents of the packet might be. Anyone may also add pieces into the bag.
Alice and Bob are located on opposite sides of the classroom. The two bags are passed around the classroom, ultimately with Bob receiving Alice's bag and Alice receiving Bob's bag. Along the way, any group or individual can acquire a copy of either bag; they just are not allowed to look inside the bag.
The challenge is for Alice and Bob to add pieces to their bags so that they will end up with the exact same content. Students with bag copies were allowed to add disks to their bags. The question to the class was how could Alice and Bob end up with the exact same content?
After some thought one student suggested that Alice could replicate the disks she originally put into her bag and place those disks into Bob's bag; Bob could do the same thing, adding his original quantities into Alice's bag. In this way, both Alice and Bob would have the same content in their two bags. As for the copies, unless a student was able to match Bob's content exactly and add it to Alice's copy or to match Alice's content exactly and add it to Bob's copy, they would not have broken the key. When the original content for Alice's and Bob's content were revealed, no one in class had matched the end content.
This established the basic process; it was now time to look at the math behind the process. The allowed me to review our journey to this point. We started by looking at properties of prime numbers. We then looked at data encoding and encryption. This led to the need to understand modulo arithmetic. We studied congruence relations and modulo arithmetic that now come back into play for secure transactions.
I stepped students through a simple example of the math involved in a Diffie-Hellman exchange. The steps are outlined in the image below.
The example used values of g = 5, p = 11, and secret key values of 2, and 3. Students were a bit confused by it all at first but were asking good questions to try to break down the process and why it worked.
I then asked students to break into groups of three and try it for themselves, with one person taking on the role of Alice, one the role of Bob, and the third the role of Eve. Again, some groups were a bit confused in working through the process but after asking questions and receiving some assistance they were able to successfully work through the math.
While this was going on, Eve was to use the public values that were known to try and break the code and uncover the final key. What Eve had to work with were the values for g and p and the two intermediate values exchanged by Alice and Bob. One student was able to crack the code and another was working through the values that would crack the code.
I discussed with the class that knowing the intermediary values and p enable Eve to look at equivalent congruence values for powers of the intermediate values. By doing this, Eve can determine the resulting key value.
At this point, students were asking if they could try it again. I suggested that they use double-digit values to make things a bit harder for Eve. Students worked through the process again. As they did so, some did not come out with the same key value. When looking at their results, I could see that they either didn't calculate their intermediate values correctly or did not raise the other person's intermediate value to the power of their private key.
Although students were not proficient in the process, they clearly saw how the process was working. I could relate their work back to the bag exchange. The private keys were the disks placed into the bag originally. The intermediate value was the bag being transported. The final key was adding back in disks to make the bag content look the same. This connection helped students feel more comfortable with why the steps were taking place.
I told students that using computers, small values for g and p could quickly be cracked. To ensure safety, larger values are needed. Even with larger values, hackers have tools and math that aid them. Specifically, there are tools that Eve has available to assist in cracking code.
The first has to do with what are called power residues. If we pick a value a and then proceed to raise a to various integral powers, starting with 0 and continuing up we produce a sequence of values. We now divide these values by an integer m. The remainders left over from this division are the residues. Since the residues come from powers of a value, they are called power residues.
I asked students to look at the power residues of 5 mod 3. The sequence of values being examined is 1, 5, 25, 125, ... These values are then divided by 3 and the remainder is captured. The result is the sequence 1, 2, 1, 2,... Students immediately saw the repetitive nature of these residues. The question that came up was would this happen for all values?
I love when this happens! Students are starting to work with the math and making conjectures about what this means, would the pattern recur, or why does this happen? This is thinking like a mathematician, examining relationships and patterns and trying to make sense of what you see and to extend those results.
Since the question was posed, we took a look at the power residues of 10 mod 2. In this case our sequence of values is 1, 10, 100, 1000,... and the remainders are 1, 0, 0, 0,... So we end up with a repeating pattern again.
We'll take closer look at what the implication of this is for Eve in trying to break the code and recover the key that Alice and Bob have exchanged.
Visit the class summary for a student's perspective and to view the lesson slides.
No comments:
Post a Comment