## Lecture #2:  More basic crypto & meeting Maple

I wrote "How to get a grade of B or better in this course". There were 3 parts.

1. Attend and participate in class.
2. Try to do the homework.
3. Perform adequately on any exams (which will be announced well in advance).
I said truthfully that no one in the previous class had any quarrel with their final grade, using these criteria.

I reviewed the basic terminology of modern cryptology: "Alice" and "Bob" trying to communicate securely and secretly, with "Eve" (the eavesdropper) overhearing the interchange and trying to steal the message. I labelled the whole enterprise involving Alice and Bob by the word "cryptosystem" and used "plaintext" and "ciphertext" (or "cryptotext") to label what Alice sends to Bob. Then I returned to the previous lecture's example. I told people that it was the canonical first cryptosystem discussed in every crypto class, and was used by Julius Caesar (as described by Suetonius) about 2,000 years ago to transmit messages to his military commanders. The "Caesar cipher" involved cyclically shifting the alphabet by 3 letters, and when nearing the end of the alphabet, subtracting 26. I explicitly described what both Alice (enciphering) and Bob (deciphering) would have to do, trying to stress that the instructions would need to be simple and unambiguous. I remarked that I would like Bob's task to be described like Alice's, and therefore described it as adding 23 to letter positions (subtracting 26 when necessary). Caesar believed this rendered his messages secure. One might attribute this more to a general lack of literacy (rendering all writing nearly secret!), but under certain circumstances similar methods were used even in the twentieth century. Of course Caesar's alphabet was shorter. And even Augustus, following Julius, found the shift in letters hard to understand, making the last letter of his alphabet (X) not shift to the beginning of the alphabet. This material is partly derived from David Kahn's monumental history, "The Codebreakers".

DREI was a summer meeting on cryptography, with research workshops and an educational program. T-shirts commemorating this were sold. The front of the shirt was a Caesar cipher of the back. I displayed two of these t-shirts, one front and one back and invited people to try to understand the messages. After a while we realized that the front of the shirt was an encrypted version of the back. The encryption method was "rot13": a circular shift or rotation of the alphabet by 13, much used on the Internet to get some privacy of possibly offensive language. I defined the word "key" to be a selection of one of a class of cryptosystems. We discussed the possible cyclical shifts of the alphabet, and came to the conclusion that there were 25 (or 26 if "no shift" was also considered). "rot13" is nice because encryption and decryption are exactly the same. So convenience plays a part in even selecting a casual concealment system.

These were examples of substitution methods, where one letter is substituted for another.

I then displayed a different kind of encryption scheme, by writing a rectangular 3 by 5 array on the board, and writing horizontally the message "the giraffe hops", padding it appropriately on the end with an "x" and reading off vertically the message "trhhaoefpgfsiex" (see the illustration below).

thegi
raffe
hopsx

I described how Bob would decipher the message, insisting that his instructions be as unambiguous as possible and as similar to Alice's as possible. So the key in this case was the pair of numbers (3 and 5) which Alice used and which Bob reversed.

This is one example of a transposition method, where letters were permuted or interchanged.

Questions were raised about how to exchange keys, and I remarked that these were very valid, and that I would try to address them in the future. Even better was the comment that if keys could be exchanged securely, why not exchange the messages instead using that method. I remarked that I would try to address this, also. I should have given out a homework assignment here about how to use and misuse this system, but this inspiration did not occur until after this class! It resulted in a homework assignment for the next class -- confusion! It would also have been useful to give them a writing assignment in class at this time. The assignment could have been:

 Technical writing Write instructions for encrypting and decrypting with this system using complete English sentences. Your instructions should be valid for any key. Keys to this system are pairs of integers. Be clear and unequivocal. Shorter is better, but precision and correctness are most important.
I think this would be a rather difficult assignment, and would have been useful. But I was eager to rapidly go on to a new more technically substantial assignment. I should have waited until the next period to begin this, maybe.

I changed gears. I had students pair off, and convert their names into points in the following fashion: "stephen greenfield" would become the point (7,10): (letter count in first name, letter count in last name). I asked them to find the y-intercept of the straight line connecting the two points. I then collected the work, and used one student to illustrate that she and her co-worker had "shared a secret". Then I tried to describe how to share the secret of hiding the formula for Coca Cola so that 2 of the 3 board members would be able to get the combination for the safe. I was asked (certainly a valid comment!) how the line, points, etc. would be selected, since the "manager" would know the whole set-up, including the secret. I answered that this would be done by a machine. I also remarked that there was a lot of arithmetic which would have to be done. No one in real life does the arithmetic by hand. So we also will need "silicon slaves" to do this work.

I then passed out the homework sheet about "Meeting Maple" [PDF|PS|TeX].