Blog Post May 14

 What’s up code-breakers and friends?

(Nick) Morning Session:

We began our cryptology journey with the basics. The plaintext is the message of sensitive information that the sender wants to hide. To do so, they choose a cipher (algorithm for encoding text) and a key, and turn the message into the ciphertext, an unreadable jumble of letters. To the intended receiver, this text holds all the information and can be decoded by applying the cipher in reverse. To the snooping third party however, the message is useless unless they can somehow figure out the cipher and key used.

Then we jumped into one of the simplest ciphers, the Caesar Shift. Encoding with this cipher is as simple as taking a letter and encoding it as another letter n places down in the alphabet. If this would come after z, the encoder starts back at a and continues counting the shift to the proper letter. For example, with a shift of 3, a encodes to d. We used a Vigenère square, as shown in the photo below. The top row is the plaintext letters, and the left column is the key. To encode with a key shift of 3 (a encodes to d) for example, we look only at the top row and the row that begins with D . Then we would trace down the column of each letter in the plain text, to the proper cell in the D-row to encode. Likewise, to decode, we started in the D-row and traced back up to the top row.

Vigenère square

Caesar Shifts are a particular type of Monoalphabetic Substitution Ciphers (MSC), which can be thought of as an unpatterned rearrangement of the alphabet to itself. Each plaintext letter will be encoded to a unique ciphertext letter, and no two plaintext letters encode to the same ciphertext letter. Because the Caesar Cipher is so restrictive in maintaining the order of the shifted alphabet, it is also much easier to break. General MSC’s on the other hand have about 26x25x24x…x2x1 possible keys. This is MUCH more secure, but the key is 26 letter pairs, a much harder key to remember. The key takes the form of two rows, the top row being the plaintext alphabet in order, and the bottom row being that alphabet scrambled.

(Anya) Afternoon Session:

In our afternoon class session, we spent the entire afternoon class focusing on the Vigenère cipher, our first polyalphabetic cipher. (This means that each letter in the plaintext has several possible ciphertext letter options, and each ciphertext letter has several possible plaintext options - as opposed to an MSC.) The Vigenère cipher requires a key - this could be a word, phrase, or any combination of letters - which is written out over and over above the plaintext. For each letter in the plaintext, the keyword letter above it determines which Caesar shift to use. For example, if our keyword was “code” and the first word in our plaintext was “London,” we would use a Caesar shift of A to C to encrypt L as N. The second letter, O, would use a shift of A to O, so O would become C. N would be encrypted with A to D, and D would be encrypted with A to E. Then the next letter O would use an A to C shift again, because the code word would wrap around.

Vigenère has a huge advantage over a simple Caesar shift for a couple of reasons. First, since basically any word, phrase, or letter combination is possible, the number of keys is nearly infinite. Second, the shift algorithm changes for each letter instead of remaining consistent throughout the entire message, meaning that what worked for one letter will not automatically work for the next. Third, because each plaintext letter has multiple possibilities of ciphertext representation, individual letter frequency analysis is useless.

However, the Englishman Charles Babbage discovered a way to exploit the frequency of groups of letters to decrypt the Vigenère cipher. The first and most important step is to find the length of the key word. This can be done by finding groups of 3+ letters that repeat and analyzing the distance between them. (Provided the ciphertext is long enough, the way the plaintext letters will line up relative to the repeated key word means that when the distance between a repeated string of letters in the plaintext is an exact multiple of the length of the key word, they will be encrypted in the same repeated way in the ciphertext.) By comparing the distances between different groups of repeated letters, we can find a common divisor which would correspond to the length of the keyword. From there, we can move to the second step of separating the ciphertext into letter chunks that correspond to the length of the keyword. We can then use individual letter frequency analysis on the “alphabet” of the first letters of each group, the second letters of each group, and so on. This gives us the Caesar shifts used for each “alphabet,” which allows us to discover the keyword and decrypt the ciphertext.

In conclusion then, a Vigenère cipher is a polyalphabetic cipher that uses a key word written above the plaintext to allow for multiple Caesar shifts. It is more secure than a simple MSC but can be broken with the right strategy, some trial and error, and lots and lots of time.

Authors:

Nick:

ZKB LV LW WKDW PLALQJ VRGD DQG LFH FUHDP LV RNDB EXW PLNLQJ VRGD DQG PLON LVQ'W?

(Encoded with Caesar Shift)

Anya:

"...I don't know. I'm just drinking coffee"