What is Cryptography? Cryptography is the science of encoding and decoding a message to be sent between people or machines. The goal is to protect the content of the message by using an algorithm to first encode the original content so it is hidden or obscured in some way, send the message to its destination, and then have it decoded back to its original message using another algorithm that (hopefully) only the intended recipient is aware of. If someone intercepts the message during its journey, they will only find the encoded message and will not understand its true content. Essentially, cryptography is the practice of sending secret messages. Caesar Shift A very simple encoding scheme is the Caesar Shift, used by Julius Caesar to communicate military matters during the rise of the Roman Empire. For this cipher, each letter of the alphabet is replaced by another letter a constant shift away. For example, say the message to send is AGENT 007, ATTACK AT DAWN . Encoding with a Caesar Shift of 1 would replace A with B, B with C, C with D, etc. (Z would wrap around and be replaced with A). If we call the original text “plaintext” and the encoded text “ciphertext,” we then have: plaintext: Agent 007, ATTACK AT DA WN! ⇓ (Caesar Shi ft of 1) ⇓ ciphertext: Bhfou 00 7, BUUBDL BU EBXO! Since the Caesar Shift just rotates the alphabet by a fixed number, it’s also called a ROT cipher. The above example is a ROT1 cipher. To decrypt a ROT1 cipher, you would use a ROT(-1) cipher (or a ROT25 cipher). Note that only letters are shifted; punctuation and numbers stay the same. Also, capital letters remain capital and lower case letters remain lower. A ROT13 cipher is very common on the Internet since it’s its own decryption cipher. Why should you never use a ROT26 cipher? Mathematically, the Caesar Shift can be written using the modulus operator %, which returns the remainder after dividing two numbers. For example, 10 % 7 returns the value of 3, since 10 divided by 7 is 1 with a remainder of 3. However, 7 % 10 returns the value of 7, since 7 divided by 10 is zero with a remainder of 7. Assign numbers to each letter of the alphabet (A = 0, B = 1, …, Z = 25). So, if p represents the plaintext and c represents the ciphertext and k is the shift number, then the i th letter of the ciphertext (ci ) is computed from the i th letter of the plaintext (pi ) by: ci = (pi + k) % 26 You might want to check out these short videos describing the Caesar Shift. And check out this video while you’re at it (encoded with, well, I’m sure you can figure out the shift number; it’s a web address after all; note that the “0” near the end is the number zero): pbbxa://eee.gwcbcjm.kwu/eibkp?d=sLKFui0d-nG Vigenère Cipher You’ve probably guessed that the Caesar Shift is not a very secure cipher. Since there are only 25 possible shifts (or keys), one could just try all 25 until the message was decoded. This is known as a brute-force attack. Also, since each letter is just substituted for another, the letter frequencies of the English language are preserved. This can help you determine what the appropriate key shift is just by looking at the ciphertext. For example, if the letter X appears most frequently in the ciphertext, then it probably corresponds to the letter E in the plaintext. A more secure approach is to use a different shift value for each letter of the plaintext. This can be done using a keyword. Say you want to encode the plaintext ATTACK using the keyword SECRET. The keyword tells what shift values to use by interpreting each letter as a number (A = 0, B = 1, …, Z = 25). So, for example, the keyword SECRET means to use shift values of 18 (S) for the first letter of the plaintext, 4 (E) for the second letter of the plaintext, 2 (C) for the third letter of the plaintext, and so on like so: A T T A C K ⇓ ⇓ ⇓ ⇓ ⇓ ⇓ (Shift of 18; S) (Shift of 4; E) (Shift of 2; C) (Shift of 17; R) (Shift of 4; E) (Shift of 19; T) ⇓ ⇓ ⇓ ⇓ ⇓ ⇓ S X V R G D Thus the plaintext ATTACK encoded with the keyword SECRET yields the ciphertext SXVRGD. You can see that the Vigenère Cipher is just a series of Caesar Ciphers with a different shift key for each letter of the plaintext. You can see one immediate advantage to the Vigenère Cipher: the letter frequencies of the plaintext are obscured. Even though the letters A and T occur twice in the plaintext, no letters are repeated in the ciphertext. This makes an attack by frequency analysis of ciphertext letters much more difficult. In the above example, the plaintext and keyword had the same length. Typically though, the plaintext is much longer than the keyword so one just repeats the keyword to the desired plaintext message length. For example, if the plaintext were AGENT 007, ATTACK AT DAWN! encoded with a keyword SECRET, we would have: plaintext: AGENT 007, ATTACK AT DAWN! keyphrase: SECRE TSECRE TS ECRE ciphertext: SKGEX 007, TLXCTO TL HCNR! To decrypt a Vigenère Cipher, just encode the ciphertext with the Vigenère Cipher again but use negative shifts for the keyword values. Mathematically, to encode plaintext pi into ciphertext ci , ci = (pi + ki ) % 26 where ki is the appropriate shift determined from the letter of the keyword. To decode ciphertext ci back into plaintext pi , do pi = (ci − ki ) % 26 Of course, the real challenge is decoding a Vigenère-encrypted message without knowing the keyword. In these cases, you first priority is to deduce the length of the keyword. Once the keyword length (call it n) is known, then there’s only 26n - 1 keywords that are possible. While that’s still a large number of keywords to check by hand (456,975 possible keys for n = 4), it isn’t a problem for a computer to check them all rather quickly. Standard Assignment (all must complete) 1. Write a C program (or a Python program) that can both encrypt and decrypt a message using the Caesar Cipher. The program should handle upper/lower cases and non-alphabet characters correctly. That is, upper case letters should be rotated to upper case letters, lower case letters should be rotated to lower case letters, and all other characters (numbers, spaces, punctuation, etc.) should remain unchanged. When prompted for a key, it should work for any reasonable positive integer key value (not just limited from 0 to 25). For example, here is a screenshot of what the program might look like when run: 2. Write a C program (or a Python program) that can both encrypt and decrypt a message using the Vigenère Cipher when the keyword is given by the user. The program should handle upper/lower cases and non-alphabet characters correctly. That is, upper case letters should be mapped to upper case letters, lower case letters should be mapped to lowercase letters, and all other characters (numbers, spaces, punctuation, etc.) should remain unchanged. The keyword should be provided by the user for both encryption and decryption, and the correctly constructed keyphrase using the keyword must be shown (see below). For example, here is a screenshot of what the program might look like when run: 3. Submit a video and answers to the standard questions outlined in the problem set rubric that we have been using since the beginning of the course. These submissions are in addition to your actual program. Hacker Assignment (optional) Write a C program (or a Python program) that attempts to determine the keyword for a given Vigenère ciphertext. There are two aspects of a keyword that make it hard to discover. First, longer keywords repeat less often which makes their discovery dependent on sufficient quantities of ciphertext. Second, keywords with duplicate letters can appear to repeat more often than they really do. Below are examples of an easy, a medium, and a hard challenge including plaintext, keyword, and ciphertext. These are for practice. To get the bragging rights associated with the hacker assignment you will have to bring your program to our office and discover the keyword for a ciphertext of our choosing. To complete this challenge, you’ll probably need to use a Hash and dictionary file. Easy plaintext: When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation. We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness. keyword: jefferson ciphertext: Fljs me lvr Lszwwv gt udqfs imwbgb, my gitgarb rjhijkoeh jtw sew drxtqj xf vwfbsqai kzs cxpnymtsz ojrix ayaqu qeaj gffbrlxji xywa jrxm frflvra, esi xf sgfdqj fqffu gqi utavjg bo xmj irjhu, clj xigsfnci fsh viinu wyfxzgb gx amngy lvr Uebx sw Fogdvj fru gt Ajxzwi'j Ycq nrynxcw hunq, f iitwbg aixuitl hb clj ttzfwbww tk qrfyvwh wjulafrb xmfx kzsl bltzpu vspuewj xyw qndwjx ayaqu rqujp kzsz cs ymi jwdnaeynse. Os uxpi ylvks gayymw kg pr biqk-imarrwx, ymek szy vis fvv ufrjxji ihmoy, clfy xywm nai jshfosq kc ymizj Qeneytv nahu liwyezf iajpnjrrtzr Amlmxj, lvnc ertrx lvrbi fwi Catr, Umgjvkq oam xmj tljghrx tk Lrhdvwixx. Medium plaintext: We may yet prevail. That's a conceit, but it's a healthy one. I wonder if the Emperor Honorius watching the Visigoths coming over the seventh hill truly realized that the Roman Empire was about to fall. This is just another page in history, isn't it? Will this be the end of our civilization? keyword: picard ciphertext: Lm oap btb rrvypqn. Tydi'a c cfqrmkt, sxi qv's r ktintyb dvg. I nrclgr zi ipg Edstzqr Yrcwtilv livcylco vhv Yxakgfwwa eodlco qvvu ipg svytvvh ylat vrlon zgaclomf tydi bje Irbip Edsxzg wrv pjquk wd nclc. Wwqu ij mjav aeripgr gdvm kn ylhbqrp, lhv'v ik? Zxtn tylh jg tyh tvf ow rjz eimlaqbakldv? Hard plaintext: So we beat on, boats against the current, borne back ceaselessly into the past. keyword: nickcarraway ciphertext: Fw yo derk oj, bmnbu kiazesp tfr kwbteek, bkrlr jcmm cvrsalcfani knkf tde nnav.