This is a follow-up to yesterday’s post, where I wrote “I also gave a second talk, in a breakout session, on cryptography.”
The crypto talk was a bit more informal than the keynote; it had an audience of about a dozen people in a small classroom, as is typical for breakout sessions, since many of them are held simultaneously (five in the case of this conference). As the title of this post indicates, my talk’s subtitle was “The KEY to Algebra,” because I emphasized connections between crypto and algebra. (Of course I had to throw in a few brief references to statistics as well, whenever the issue of cryptanalysis came up, but that wasn’t my focus.) I opened with a brief puzzle:
All I told the audience was that this was a secret message from Alice to Bob. Both of them know the system being used, but you (the audience) don’t. Eve, the eavesdropper, also doesn’t know and is trying to break the code. After a little time to think, someone suggested that the second word might be THE, which happened to be correct, so we talked about the importance of being willing to make hypotheses and check them out. It’s a standard convention in crypto for Alice to be sending messages to Bob, even though there’s no need for those names, just as x and y are standard in algebra but you certainly don’t need to use them. If I had changed Alice’s name to Seer and Bob’s to Julius, it might have been too obvious.
OK, want to know the answer? Maybe it should have been March 15 instead of April 6. The plaintext turns out to be BEWARE THE IDES OF MARCH, and this is an example of what’s called a Caesar Cipher, since Julius Caesar is credited with inventing the idea of moving each letter a constant number of positions later in the alphabet, 3 in this case. (Probably it was really one of his speechwriters.) We write this in algebra as C = P + 3, where C stands for “ciphertext” and P for “plaintext.” And then we’re off to the races, since algebra lets us use any formula we wish, not just a simple linear function.
Of course there are plenty of complications, since we’re in a system with no negatives, no fractions, no decimals, and no large numbers. Given those constraints, you still want your formula to be invertible, or else poor Bob will never be able to read the message! So we explored that for a while. And then we extended the simple linear function (called “affine” in this context) to more complicated systems such as Vigenère and matrix ciphers. With our limited time, we could only touch briefly on those, especially since I needed time to introduce public-key cryptography and say something about RSA. We took a look at the algebra involved in RSA, and discussed how multiplication is easy but factoring is hard — unfeasible, in fact, if the numbers are big enough. For instance:
Pointing out that so much of the world economy depends on secure communications — passwords, credit card numbers, and the like — we discussed how this topic provides a real-world example of applied algebra that is motivating to a lot of students, even those who think they have no use for algebra.