Previous lecture

Table of contents

Next lecture

Students handed in their papers about medical record privacy today. Several students were absent and others did not seem happy.

I began the class by asking groups of students to compute the multiplication and addition tables mod 4, 5, 6, and 7 and write the results on the board. I then wrote several linear equations and emphasized that I wanted the equations solved using only the information given in the tables. Several of the equations for composite modulus either did not have solutions or did not have unique solutions.

After some (guided) discussion we decided that the root of the "evil" in these tables was the fact that some of them had 0's "inside" their multiplication tables. We associated that with moduli which were NOT prime: a prime number is a positive integer which has no positive integer factors other than itself and 1. I named the two primes of the four integers we were inspecting, and asserted that other numbers (such as 9001 and 1234567891013) were also prime.

Then I asserted that the linear equation ax=b could have only 1 solution mod a prime number. To see this I subtracted and factored the consequence of having more than one solution. A number of students found this quite difficult to follow. After the fact was absorbed, I asked what the multiplication table of 9001 would look like (more than thirty million entries!) and asserted that if someone told me that on the 400^th row the number 208 appeared more than once, they were incorrect. I tried to tell them that this was a rather startling prediction based on what we knew.

Then I tried something harder: I asserted that since a non-zero number could appear at most once, and there were the same number of entries in each row, every non-zero number must appear exactly once. This was difficult to understand.

I concluded by saying that each row in a multiplication table mod a prime must contain every number possible, interchanged in some mysterious way.

I defined "cryptosystem" as an entire encryption/decryption scheme. I suggested that the rows of a multiplication table could give us a cryptosystem. For example, suppose a message was, "The troops invade from the west." If I numbered the words in the sentence, and exchanged them as suggested by the non-zero entries of row 4 (the encryption key) in the multiplication table for mod 7, then I had a jumbled (encrypted) sentence. I asked how decryption should work, and from the responses to this question learned that, actually, people didn't understand how to undo multiplication by 4 (hey, multiply by 2, so 2 is the decryption key). I remarked that this may seem easy, but what if we used a row of the multiplication table for a bigger prime? Would this be a good system?

I explained that this would not be too good, because it was actually easy to figure out how to get multiplicative inverses mod a prime (in fact, I asserted there would be a "lab" where they would do that soon). The word "easy" is not itself easy to make precise.

I then created a rather fraudulent cryptosystem using a phone book, by just copying numbers corresponding to the initial letters of people's last names. I encrypted a word given to me by a student by taking random last names with the given initial letters and writing the phone numbers for these names. We discussed how easy this would be to decrypt for a while. I got the idea for this demonstration by a remark in Salomaa's book, Public-Key Cryptography. All of the information is public -- in the phone book. But finding it out ("decryption") might be rather difficult.

I gave an approximate definition of "one-way function" as a function whose value is easy to compute, but whose inverse is hard to compute. I said that there were difficulties making the words "easy" and "hard" precise. I also talked about the existence of "trapdoors" or shortcuts making the computation of an inverse (or a decryption!) easy, for example, the use of a reverse telephone directory in the phone book cryptosystem.

What I would aim for in the next few days is a way of classifying computations as easy or hard.

Previous lecture

Table of contents

Next lecture