Class started with looking at the power residues of 10 mod different values. I asked that students select different values of m to use in their groups so that they could see what happens. I asked students to consider using 3, 4, or 5 for values of m.
Although some students were still confused about how to calculate power residues, they were quickly put on track. The results for these values were put on the board:
| 1 | 10 | 100 | 1000 | 10000 | ... | |
| 3 | 1 | 1 | 1 | 1 | 1 | ... |
| 4 | 1 | 2 | 0 | 0 | 0 | ... |
| 5 | 1 | 0 | 0 | 0 | 0 | ... |
Students saw, as with yesterday, that eventually the power residues begin to repeat or revert to zero, in the case where 10 and m have a common factor. I mentioned that these results could be used to derive the division rules that we used earlier in the semester. [This is actually an interesting exploration if there is time to do it.]
From this, I asked the class what a0 mod m would be for any integers a and m? Students recognized that a0 equals 1 and 1 mod m would have a value of 1.
I pointed out that once residues start to repeat a pattern or once you reach a residue value of zero, you become locked into this pattern or your value must always remain zero.
Knowing the behavior of power residues is a tool that Eve can use when trying to unlock the private key that Alice and Bob exchange.
A second tool that Eve uses is Fermat's Little Theorem. Fermat's Little Theorem states
For any positive integer m and prime number p, with m not divisible by p
mp-1 ≡ 1 mod p.
An alternative form of the theorem states the congruence as mp ≡ m mod p.
I asked students to pick some values to confirm this worked. This process enables students to make a tangible connection to what appears to be a rather abstract statement.
I brought in Euler's theorem that relates the totient function to a very similar relationship
For any integers m and n that are relatively prime to each other
mφ(n) ≡ 1 mod n.
Due to time, I elected to not have students try some values to verify the result. The important aspect of this relationship is that φ(n) < n and so this guarantees that this congruence is satisfied for at least one value.
Fermat's Little Theorem is not bi-directional in nature. If p is prime, we know the congruence is satisfied. In reverse, knowing the congruence is satisfied does not guarantee that p is prime. As an example,
2340 ≡ 1 mod 341 but 341 = 11 x 31
Values that satisfy Fermat's Little Theorem but are not prime are known as pseudoprimes. Primality tests use these results with the idea that the more values tested that work, the greater the probability that the value is in fact prime.
Armed with these tools, Eve is guaranteed to find power residues that start repeating. At this point Eve can use the point of repetition to crack the code and identify the key being used by Alice and Bob.
To make the key exchange safer, large values are used. When thinking of large values, it is necessary to consider values that are hundreds of digits long.
At this point I asked students for questions and asked them to summarize their learning about cryptography, congruence relations, and modular arithmetic.
There was still some time left in class, so I decided to take a moment to introduce the idea of public key encryption and RSA public keys. Again, this is a topic that can be expanded and investigated over several days, time permitting.
I started off by explaining that we want to conduct a remote transaction in a secure way so that both parties know they are not being cheated. To illustrate the point I pick a student to play a coin flipping game with me. I stand at the opposite side of the room and ask the student to call heads or tails as I flip the coin. I flip several times and, regardless of the outcome, tell the student they guessed wrong. Needless to say, the accusation of cheating arises rather quickly.
I ask the class to consider how can we play this game to ensure that it is played fairly. We need to create a method to allow for an oblivious transfer, one in which neither party knows what the other will do but that one party's action will determine the ultimate success or failure of the other party.
This is illustrated by a lock box with two keys. Bob has a choice of 2 keys and selects one of the keys. Alice has the same two keys. She picks a key to send to Bob. If the sent key matches the one that Bob already has then Bob loses since he is unable to unlock the box. If Alice sends the non-matching key, Bob now possesses both keys, can open the box, and wins.
This is done digitally using prime numbers. Alice selects two prime numbers and sends the product to Bob. Bob attempts to factor the two numbers. He makes a guess and constructs a congruence relation based upon his guess and the product he received. Bob returns the value from his congruence relation to Alice. Alice than finds the two possible values that meet the corresponding congruence relation that she forms. One of the values is Bob's guess and the other is a second value. Alice does not know which is which but must return on of the values to Bob. If Alice returns Bob's guess then Bob loses since he has no additional information to resolve the factoring. If Alice returns the other value, Bob can use congruence relations to find Alice's two factors and he wins.
I walked students through this process with small values. The process is predicated on the idea that extremely large numbers that are the product of two large prime numbers are inherently hard to factor. This is believed to be true by mathematicians but has not been proven. One of the issues here is that if a government or some group were to demonstrate that this actually was not hard as is believed, it would open up that government or group's ability to hack into many diverse systems. Of course, if this were discovered it wouldn't be disclosed since that government or group would have a distinct advantage over everyone else.
With that, the exploration of number theory and cryptography comes to a close. For the final time available in the semester, the class will explore some ideas in graph theory.
Visit the class summary for a student's perspective and to view the lesson slides.
No comments:
Post a Comment