Fun With Crypto – Keeping Secrets [From Ancient Greek Warriors, Enemies of the Roman Empire, Medieval English Kings, and Modern Superpowers] Jonathan A. Poritz jonathan@poritz.net or jonathan.poritz@csupueblo.edu www.poritz.net/jonathan Center for Teaching and Learning and Department of Mathematics and Physics Colorado State University-Pueblo 21 July 2018 This work is released under a Creative Commons Attribution 4.0 license. These slides can be found at https://poritz.net/j/share/FwCKS JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 1 / 23 Why Crypto? Why is this session called “Fun With Crypto?” Well... Crypto is short for cryptography, which comes from the Greek roots • kryptos, κρυπτ oς secret, hidden • grapho, γράϕω draw, write, written So cryptography means [the study of] secret writing. What is a secret? Why kinds of things do you keep secret? Why? From whom? Why would you write down a secret? Why would you send it to someone else? JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 2 / 23 Some Reasons for Secrecy Here are some things which are thought to be important to keep secret: • State secrets, particularly military ones • Commercial secrets – plans, contracts, methods, ideas • Financial secrets, both for individuals and companies • Health information – as a matter of a law (e.g., one called HIPAA) • Educational information – as a matter of law (e.g., FERPA) • Many other kinds of personal information, with different legal protections in different countries • Your own personal thoughts and ideas, which you might send from the past to the future by writing them down in a diary1 • Anything you send over the Internet, because of the way it is built 1 Leonardo Da Vinci kept a diary in which the writing was all mirror-reversed ... maybe to keep them secret? JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 3 / 23 Situations Requiring Secrecy: Ancient Greece Lots of wars, lots of military secrets... Wikimedia Commons: Thesevenseas / *derivative work Perhelion (derived from: World map longlat.svg:) [CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0] Wikimedia Commons: Map Peloponnesian War 431 BC-fr.svg: Marsyasderivative work: Aeonx [CC BY-SA 2.5, CC-BY-SA-3.0 https://creativecommons.org/licenses/by-sa/2.5, http://creativecommons.org/licenses/by-sa/3.0/] JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 4 / 23 The Scytale What is the relationship between the letters of the original message and the letters as they appear after they’ve been written onto a strip using the scytale? E.g., are there any new or missing letters? Suppose a spy got a quick look at someone using a scytale – maybe from a distance, in dim light. Would that spy later always be able to figure out what a captured message said, or would they need an extra piece of information to do this? JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 5 / 23 Terminology It helps to have special terms to talk about complicated things like crypto. The plaintext is a message someone wants to keep secret, in the original form that makes sense to human readers. The ciphertext is the scrambled version of the plaintext which has been transformed so that other people cannot read it. Making the ciphertext out of a plaintext is called encryption. Getting the plaintext back out of the ciphertext is called decryption. An extra piece of information that the sender has to choose to encrypt the plaintext, which the receiver usually needs also to know in order to decrypt the ciphertext, is called a key. What are encryption, decryption, and keys for the Scytale? JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 6 / 23 A Little Scytale Make up your own secret message – your own plaintext – and use your scytale to encrypt it. Find someone else who has a different sized scytale from you and trade messages with them. Decrypt their message with your scytale. Come write your decrypted message on the board. If your decrypted message makes sense, you’re done. If not, try again! [Meaning: find someone else with a different sized scytale, trade messages, and decrypt.] JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 7 / 23 Situations Requiring Secrecy: Ancient Rome Julius Cæsar wanted to conquer the whole “known” world. He made a good try. [He knew about India and didn’t get it, or Egypt, or Scotland....] All that conquering required lots of wars, and good secret [military] communications. Wikimedia Commons: by Cristiano64 [GFDL or CC-BY-SA-3.0, http://www.gnu.org/copyleft/fdl.html or http://creativecommons.org/licenses/by-sa/3.0/] JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 8 / 23 The Cæsar Cipher Cæsar decided to change the letters themselves, without moving them. Encryption of a plaintext went like this: take every letter in the plaintext and simply replace it with the letter three steps down the alphabet from the original. Wait a second: What should we do with the letters x, y, or z? What is the ciphertext for the plaintext “Lazy Romans don’t win empires”? How should decryption work for the Cæsar cryptosystem? Note: a good answer will have to do be careful with ciphertext letters a, b, and c. Decrypt the ciphertext “ahuahvzdvnlqjrishuvld”. What is the key we are using ... without really thinking about it? [Hint: when Cæsar sat down for the first time to encrypt a plaintext, what choice did he make that he could have easily made in a different way?] JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 9 / 23 The Tasty Math of Modular Arithmetic That thing we did with wrapping the letters around the end, where three steps after y was b, etc., is actually something we are all used to doing with numbers on a clock face. Imagine there might be n numbers on a clock face – so n would be 12 for a regular clock and would be 26 for the letters used in a Cæsar cipher. Then arithmetic on this weird clock is called arithmetic mod n. Arithmetic mod n is some very pretty, interesting, and useful mathematics. It was invented by Carl Friedrich Gauss around 1800 and has since become a basic but important tool in the toolbox of modern mathematics. The fact that we are comfortable doing modular arithmetic and related mathematical topics is part of why mathematicians are so useful in computer security and cryptography. JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 10 / 23 Back To The Cæsar Cipher: Different Keys So Julius Cæsar used the key k = 3. His nephew Octavian, who later took the name Augustus Cæsar, liked to use the key k = −1. How many possible keys are there? Suppose you intercept a ciphertext made with the Cæsar cipher, but you don’t know the key. What would you do to figure out the plaintext? What plaintext produced this ciphertext, and what key was used? nvyfcukyvjvkilkyjkfsvjvcwvmzuvekkyrkrccdverivtivrkvu vhlrckyrkkyvprivveufnvuspkyvzitivrkfinzkytvikrzelerc zverscvizxykjkyrkrdfexkyvjvrivczwvczsvikpreukyvglijl zkfwyrggzevjj JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 11 / 23 Cryptanalysis: Security Through Obscurity vs Kerckhoff’s Principle When you know what the method of encryption was to make a ciphertext, but not the key, trying to get the plaintext back by some other method is called cryptanalysis. Colloquially, this is breaking or cracking the code. You may say: “Why not keep the method of encryption a secret, too?” This approach is called security through obscurity and is a very bad idea unless you (a) really know what you’re doing and (b) will only be using this secret communications method once.2 The idea that we should make the encryption and decryption methods public and only keep the key secret is called Kerckhoff’s Principle and is named after a French military cryptographer from the 1880s. 2 See, e.g., the Voynich Manuscript. JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 12 / 23 “Brute-Force Attack” When we try cryptanalyzing a mysterious ciphertext by trying all possible keys, it’s called using a brute-force attack. This only works if there is a fairly small number of keys, so we can do all this work and not die of boredom (or old age). Let’s try decrypting just the first two letters of that long mystery message with all possible keys (Cæsar’s soldiers could have done that much work). 1: mu 5: iq 9: em 13: ai 17: we 21: sa 25: ow 2: lt 6: hp 10: dl 14: zh 18: vd 22: rz 26: nv 3: ks 7: go 11: ck 15: yg 19: uc 23: qy 4: jr 8: fn 12: bj 16: xf 20: tb 24: px We could keep going on the ones which might be real words... but it gets boring really fast. Which is why Cæsar would have liked a computer. JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 13 / 23 Teaching A Computer To Do The Boring Stuff, 1 Computers are very fast – they can do millions of calculations every second – but extremely stupid: you have to tell them exactly what to do, in very small, simple words [called a programming language]. Start your computers, and get Firefox and Octave running. Octave is a programming environment, we are going to teach it to do Cæsar en/decryption. Octave is free: gnu.org/software/octave/. To put some information in a container – called a variable – you just type x = <the information> [and hit the ENTER key] If that information is a bunch of letters (some text) – called a string in the programming world, just put it inside quotation marks (single or double, either work), like x = ‘this is a happy little string’ Or the information could be a number, like x = 17 JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 14 / 23 Teaching A Computer To Do The Boring Stuff, 2 If the variable x has a string which we want to do Cæsar encryption to, using the key k, we might try doing x + k Octave would do the right thing and add the number k to every letter of the string x. But it wouldn’t do that cool modular arithmetic stuff! We have to move all those letters to numbers, starting with “a” as 0, by x - ‘a’ and then do the Cæsar shifting the letters by k with x - ‘a’ + k and finally do the “wrapping around the end of the alphabet” thing we talked about before, using mod(x - ‘a’ + k, 26) Unfortunately, this will produce an result which is just a bunch of numbers, so we want to turn them back into a string by char(mod(x - ‘a’ + k, 26) + ’a’) JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 15 / 23 Cæsar’s Computer, 1 Using the Firefox browser, please just cut and paste the four lines from poritz.net/j/share/FwCKS/caesar.html into your running Octave environment. [This does exactly what we did above, but first it cleans up the plaintext by taking out all non-letter characters and making it all lower case.] Now your Octave knows how to do Cæsar encryption of a string in the variable x with key k by just typing caesar(x, k) Or you can input the data directly in either place, or both, with caesar(‘‘this is a test’’, k) or caesar(x, 3) or caesar(‘‘this is a test’’, 3) You can also store the output ciphertext in a variable y by doing y = caesar(x, k) JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 16 / 23 Cæsar’s Computer, 2 Use the program caesar in your Octave to do Cæsar encryption of a word or phrase you like (the name of the street where you live, the name of your favorite food, whatever) using as key whatever number you like. Write the resulting ciphertext on the board. Wait! How are we going to do Cæsar decryption in Octave? [Hint: you can do Cæsar decryption with key k using our encryption program caesar but giving it a different key!] Let’s decrypt one of the messages on the board, someone tell the key they used. Now let’s try to cryptanalyze the next message on the board, using the brute force approach. We could start typing in all the Octave commands JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 17 / 23 Cæsar’s Computer, 3 starting with caesar(x, -1) caesar(x, -2) caesar(x, -3) caesar(x, -4) ... But that gets boring really fast – and computers can do boring things really accurately and quickly! So we can make the computer try all possible keys for decryption by for i=1:26 caesar(x, -i) endfor and then we just pick the one that looks like a plaintext. JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 18 / 23 Another Approach To Cryptanalysis: Counting Things Another way to do cryptanalysis is to look at that mystery ciphertext nvyfcukyvjvkilkyjkfsvjvcwvmzuvekkyrkrccdverivtivrkvu vhlrckyrkkyvprivveufnvuspkyvzitivrkfinzkytvikrzelerc zverscvizxykjkyrkrdfexkyvjvrivczwvczsvikpreukyvglijl zkfwyrggzevjj and to notice that there are a lot of v’s, k’s, and j’s. Hmm.... But what are the three most common letters in the English language? Get the program histo from the site poritz.net/j/share/FwCKS/ histo.html (the same way we got caesar). Then you can see which letters are most frequent in a string contained in the variable x by typing histo(x) and looking at the pretty picture. If you want to cut-and-paste the above mystery ciphertext, it is in poritz.net/j/share/FwCKS/ciphertext.html Cryptanalysis using letter frequencies is called frequency analysis. JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 19 / 23 More Advanced Encryption: Vigenère and One-Time Pads If you want to prevent a brute-force attack, you have to make Cæsar stronger, somehow. One way, called Vigenère encryption, is to use different Cæsar keys for the first, second, and third letters of the message, and then repeat those three key values for the next letters, etc. Or even more than three different Cæsar keys! Vigenère encryption was unbreakable for hundreds of years, and was used by European royalty to protect their secrets. But it was eventually broken, too – I teach my students in a class here at CSU-Pueblo how. Except if there are as many Cæsar keys as letters in the plaintext, then the whole pile of Cæsar keys is called a one-time pad, and there is a mathematical proof that Encryption with a one-time pad is, and will always be, unbreakable. [Yes, unbreakable by everybody,3 including the US Government, because mathematics is more powerful than the world’s greatest superpower.] 3 Take that, Hollywood movies where someone says “There’s no such thing as an unbreakable code!” JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 20 / 23 Homework Assignment [Not really homework.] If you want to look over these slides in the future or share them with someone, I’ll put them on my website at poritz.net/j/share (I put everything I write or use in public up there, so you might have to look through the list to find this particular presentation.) If you are interested in crypto, there is a ton of interesting books, free software, videos, etc., that you can learn from. Send me an email (my contact info is at poritz.net/j) and I can make some suggestions. I also love to talk to students (and teachers) about all aspects of crypto, computer security, modular arithmetic, and many other areas of math and science. So don’t hesitate to contact me for anything at all related to math/science/computers! JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 21 / 23 Practice XYZABCDEFGHIJKLMNOPQRSTUVWXYZABC Encrypt, for Julius Cæsar, the plaintext Lazy Romans don’t win empires Julius’s spy sent him the ciphertext ahuahvzdvnlqjrishuvld What was the original plaintext the spy meant to send? JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 22 / 23 A Challenge Figure out what plaintext and what key produced this ciphertext rtgpxpjzfcetcpojzfcazzcjzfcsfoowpoxlddpdjplcytyrezmcpl espqcppesphcpenspocpqfdpzqjzfceppxtyrdszcpdpyoespdpesp szxpwpddepxapdeezdeezxptwtqexjwlxampdtopesprzwopyozzc [This can be cut-and-pasted from poritz.net/j/share/FwCKS/challenge.html .] Again, plaintext and key for this ciphertext – this one is harder. kllkofkdplrqxtxpmjxhfkdxkljfklrpplrkaxplrkaxhfkqlxhix ulkloxqlzpfkcifqpxylrqxrdrpqrptelexpexaxyxakfdeqpfqpr myifkhfkdxkamroyifka [This can be cut-and-pasted from poritz.net/j/share/FwCKS/harder.html .] JA Poritz (poritz.net/j & CSU-Pueblo) Fun With Crypto – Keeping Secrets 21 July 2018 23 / 23