Day 1: Symmetric Ciphers

What does it mean when you see a key in your web browser?

Substitution Cipher

A monoalphabetic substitution cipher replaces every letter in the plaintext message with a substitute letter in the ciphertext. The key is the mapping between plaintext letters and substitute letter. For example, the key could be:

Alphabet:	A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher:	u r d t g o n i p v f h w x m q l b s k j c z e a y

Example: To encrypt "DRAGON", we replace each letter with the corresponding cipher letter: "tbunmx".

Questions

1. Decrypt the message kmq sgdbgk using the monoalphabetic substitution cipher with the key given above.

2. How many different possible keys are there for monoalphabetic substitution ciphers? (Hint: you can start by mapping A to any letter.)

3. Here is a message encrypted with a monoalphabetic substitution cipher with an unknown key. Try to decrypt it. (Hint: what is the most common letter in the English language? Guess that the most common letter in the ciphertext maps to that letter.)

     NQWOO DGU BOOE G KOSWON, RY NIL LY NQOD GWO POGP.  
                                       (AOVCGDRV YWGVBHRV)

Better Ciphers

If you were able to break the cipher in question 3, you know that a monoalphabetic substitution cipher is not very secure. You may be able to use it to keep a secret from your little brother or sister, but not to keep a secret from an enemy army. To do that, we need to use math to make more secure ciphers.

First, we will need a way of converting messages made of letters into numbers. A simple way is to just number the letters starting with A as 0:

Letter:	A  B  C  D  E  F  G  H  I  J  K   L   M   N
Number:	0  1  2  3  4  5  6  7  8  9  10  11  12  13
Letter:	O   P   Q   R   S   T   U   V   W   X   Y   Z
Number:	14  15  16  17  18  19  20  21  22  23  24  25

Then, we would write "HELLO" as "7 4 11 11 14".

We will use modular arithmetic to make a better cipher. Modular arithmetic is like regular arithmetic, except instead of doing it on a line, you do it on a circle. Adding goes clockwise, subtracting goes counter-clockwise:

We write mod 26 to mean we are doing arithmetic on a circle with 26 numbers, 0 through 25. Here are some examples:

    20 + 4 mod 26 = 24
    20 + 5 mod 26 = 25
    20 + 6 mod 26 = 0
    21 + 6 mod 26 = 1
    2 - 3 mod 26 = 25

Questions

4. What is 2 + 2 mod 5 ?

5. What is 2 + 3 mod 5 ?

6. What is 22 + 7 mod 26 ?

The Caesar Cipher (used by the Roman emperor Julius Caesar) encrypts message by converting the letters to numbers using the numbering above, then adding a number to each number modulus 26, and converting the result back to a letter. Here's an example:

Message: J  U  L  I  U  S
Numbers: 9  20 11 8  20 18

Key = 7

Add 7 to each number, modulo 26:

9 + 7 mod 26  = 16
20 + 7 mod 26 =  1
11 + 7 mod 26 = 18
8 + 7 mod 26  = 15
20 + 7 mod 26 =  1
18 + 7 mod 26 = 25

Convert the numbers back into letters:

Numbers:    16  1  18 15 1  25
Ciphertext:  Q  B  S  P  B  Z

7. Decrypt this ciphertext that was encrypted using a Caesar cipher with key = 12: NQIMDQUPQEARYMDOT

Vigenere Cipher

The Vigenere Cipher is like the Caesar Cipher, but instead of using the same key for each letter, it uses a word as the key and cycles through the different letters in the key word. Here's an example:

Key = P  A  S  S   W   O   R  D
    = 15 0  18 18 22  14  17  3

To encrypt a message, use the first letter in the key to encrypt the first letter in the message, and the second letter in the key to encrypt the second letter in the message, and so on. Once you have used all the key letters, start over again with the first letter:

Message:     A  T  T  A  C  K  A  T  D  A  W  N
Numbers:     0  19 19 0  2  10 0  19 3  0  22 13

Key:         P  A  S  S  W  O  R  D  P  A  S  S
             15 0  18 18 22 14 17 3  15 0  18 18

Encrypt = Message + Key mod 26

             15 19 11 18 24 24 17 22 18 0  14 5
CipherText:  P  T  L  S  Y  Y  R  W  S  A  O  F

Note that the different T's in the message encrypt to different letters in the ciphertext based on where they are in the message! This makes it much more difficult to break than the monoalphabetic substitution cipher.

In fact, the French believe this cipher was unbreakable and used it during the Crimean War. Charles Babbage figured out how to break it, however, and the British were able to read many of the French army's secret messages. Modern ciphers use many of the same ideas as the Vigenere cipher, but do more complicated math to scramble up the letters even more.

Decrypting a Vigenere message is just like encrypting, except instead of adding the key we subtract it.

8. Decrypt this ciphertext that was encrypted using the Vigenere cipher with Key = SECRET: SFTRGTVEDIE

9. Encrypt a message of your choice using the Vigenere cipher and a your own key.