Worksheet 02: Cryptography I | Computer Security (Fall 2024)
Reveal ALL Solution

Worksheet 02: Cryptography I

Worksheets are self-guided activities that reinforce lectures. They are not graded for accuracy, only for completion. Worksheets are due by the start of the next lecture via Blackboard link as a single pdf document. Be sure to properly label each question.

Questions

  1. Define the following terms:

    • Plaintext
    • Ciphertext
    • Key
    • Encryption
    • Decryption

    Reveal Solution

  2. A classic example of an encryption routine is the Caesar cipher, which shifts each letter in the alphabet by three steps. For example, A becomes D, B becomes E, and so on, wrapping around, like below:

    ABCDEFGHIJKLMNOPQRSTUVYXYZ <-- input
DEFGHIJKLMNOPQRSTUVYXYZABC <-- output

    Encrypt the following plaintext using a Caesar cipher.

    THE WORLD IS A STAGE AND ALL THE PEOPLE PLAYERS

    Reveal Solution

  3. One of the problems with the Caesar cipher and other substitution ciphers is that they can be attacked with a frequency analysis for both common words and letters as this is preserved in the ciphertext. Below is some text encrypted with a Caesar cipher with a different shift, not 3, but shifting some unknown amount. Use your wits to determine the secret phrase.

    MP ESP NSLYRP ESLE JZF HTDS EZ DPP TY ESP HZCWO

    Reveal Solution

  4. The Viginère cipher is similar to the Caesar substitution cipher, but each letter is substituted using a different shift based on key word. For example, consider the Viginère table below

    If we use the key “GEORGE” then to encrypt the phrase “ATTACK AT DAWN” we would first use the column that begins with G to substitute A for G, then the column that begins with E to substitute T with X, and so on. When we reach the end of GEORGE, we cycle back to G again at the beginning. The resulting cipher text for “ATTACK AT DAWN” is then:

    GXHRIO GX RGCR

    Use the Viginère cipher with the key word SHERLOCK to encrypt the phrase ELEMENTRY MY DEAR WATSON.

    Reveal Solution

  5. Again, using the Viginère Cipher, consider the plaintext FRANK and ciphertext QUIET, find a key word that encrypts FRANK to QUIET

    Reveal Solution

  6. Recall that the notion of perfect secrecy occurs when the key is as long as the message. We can use the Viginère cipher to demonstrate an example of perfect secrecy. Consider the ciphertext BLOND, and if we assume that key word is at least 5 letters, find two keywords that could decrypt to the cipher text BLOND, one key that decrypts it to GRANT and one key that decrypts it to MAGIC.

    Explain how this example shows perfect secrecy. Another name for this is the One Time Pad

    Reveal Solution

  7. The Vignère cipher suffers a fatal flaw from a chosen planetext attack. Assume an attacker can choose the plaintext that is encrypted using the cipher, what could they choose to reveal the key workd.

    Reveal Solution

  8. Moving beyond simple substitution ciphers, modern computers use symmetric, block ciphers to encrypt content. The block sizes are the size of the keys used. Modern block ciphers use 128 bit keys. Approximately many possible keys are there in a 128-bit block cipher?

    You should estimate this using 2 significant digits and a power of 10. For example, \(12 \times 10^{5}\). (Note this is not the right answer.)

    Reveal Solution

  9. Why is it required to pad plain text message when using a block cipher? And what are two common filler characters?

    Reveal Solution

  10. The way we’ve previously been using the Viginère cipher is similar to that of the ECB, that is, when we use the keyword, we wrap around and use it again for the next part of the plain text until the entire message is encrypted. In other words, the block size is the length of the key, and we reuse the key for each block.

    Let’s consider a modification that produces CBC mode for Viginère cipher. In this version, we will chain together prior blocks to new blocks. Since we are using letters instead of bits, we can’t use XOR, but we could still string together encrypted blocks using the encryption routine for Viginère using the diagram below. (Note E indicates an encryption routine.)

           iv   .---------.   .----- ... -----.
        |   |         |   |               |
        v   |         v   |               v
       .-.  |        .-.  |              .-.
p_0 -> |E|  | p_1 -> |E|  |       p_n -> |E| 
       '-'  |        '-'  |              '-'
        |   |         |   |               |
        v   |         V   |               V
       .-.  |        .-.  |              .-.
 k ->  |E|  |   k -> |E|  |         k -> |E|
       '-'  |        '-'  |              '-'
        |   |         |   |               |
        |---'         |---'               |
        |             |                   |
        v             v                   v
       c_0           c_1                 c_n

    That is we first encrypt the plaintext block \(p_0\) with the \(iv\), and that is then encrypted with key. The resulting cipher text block \(c_0\) is then the \(iv\) for the next step in the chain, and so on. The final encrypted message is \(c_0 c_1 c_2 \ldots c_n\) concatenated together.

    Using this form of CBC mode with a Vigère cipher, encrypt the following phrase

    WHENLIFEGIVESYOULEMONSMAKELEMONADE

    with the key BLOND and the \(iv\) of FRANK. You should ignore any spaces and pad your message to the block length (i.e., the length of the key) using Z’s.

    Hint 1: It’s totally reasonable to write a small program to do this, but you can also do it by hand. It will take a bit.

    Hint 2: Consider that the Viginère cipher is essentially a modulo cipher. For a key character K and a plaintext letter P, the resulting cipher text is the (K+P)%26. For example, if we number letters starting from 0, we get A=0,B=1,C=2,D=3, …, W=23,Y=24,Z=25. Then encrypting the plaintext letter D=3 with key Y=24 is D+Y=3+24=27 and 27%26=1 or B.

    Reveal Solution

  11. Now let’s try decrypting Vignère cipher in CBC mode in reverse. Decrypt the following phrase.

    KJZLKMZBOGYZGILXSZMOATCMDODOQL

    The key is TOPEKA and the iv is DORTHY

    Hint 1: Again, you’re welcome to write a small program.

    Hint 2: Try writing the diagram from above in reverse to get a sense of how this works

    Hint 3: Note that decryption in Viginère requires the modulo subtraction of two letters’ numeric values under the modulo. Again, consider numbering the letters starting from 0: A=0,B=1,C=2,D=3, …, W=23,Y=24,Z=25. In many cases, subtracting two numbers will give a positive number, which isn’t an issue for modulo, but sometimes subtraction gives a negative number. For example, if we wanted to decrypt the letter B=2 with the key Y=24 we would subtract the B-Y=1-24=-23 which is negative. To take the modulo of -23, we can simply add 26 because, under the modulo, 26 is 0 or 26%26=0, thus adding 26 doesn’t change the result (which is true for positive and negative numbers). This gives us -23+26=3 or the letter D=3. The final formula for decryption of ciphertext letter C with key K is (C-K+26)%26.

    Reveal Solution

  12. You should test your C# development environment on your computer using Docker and VSCode as this will be needed in HW2. You should first ensure the following are installed on your computer

    1. VSCode
    2. Docker Desktop
    3. If you’re on a windows machine, also install Git

    Make sure Docker desktop is running, and then open VSCode and install the following extensions:

    1. Search for and install the Remote Explorer extension
    2. Search for and install the Docker extension.
    3. Search for and install the Dev Containers extension.

    Next, download this zip file that contains the starter code for this project. Unzip it, and then open the directory in a new VSCode window. You should be prompted to open the folder in a container, say yes!

    Once the container is open, you should open a terminal window. You can do that from the menu bar, or by using the shortcut Ctrl-` (backtick).

    Then in the terminal dotnet run to run Program.cs – which is just a hello-world program. If you’re prompted to install the C# framework, you should select yes to that too.

    Your task is to edit Program.cs to be able to decrypt the following AES-CBC encrypted message (scroll ALL the way right!)

    5D78B9C5F652195E684ABABB75D542BFCBADA6E058C5D44599971DE0B694826D28BAEE232F2507A9AF5847C1550537B0FB8BC3A684A7D8C731D088F295933D642F9E77AE35A700CA07494C5A687D84B89E2B6C958ACD3A277D47DF28D441F8032B778391E0AAF86567C6ADD7D85F538C87DCF073CF6F60E4A0BE8C670D79803830626EF5868FEC0B88ED65181B4D7C54D83FB4E759ABA57946B0B06F5947775355FA6B0481A0AFBDCADE2840A64C87DEFB383A16CB72BB05065B0C409184CC34B22502A63540A67BFA99F345AD7180D1B48E0116786B8007715C5A994ADAB65A8D57BC36F3C25BCE873AD0D07CE9D50F9EF5145A0907E91BC5D4467535BFA5E192BD628251E4319A8C7858C0474C5559200003525A4DD2195730E4FA8AF924B90434B887198CC7B9DD6630DCE7D716E7BB9AAEE1421DB529E6E10577729FA951

    Using the following key

    84F9BDFF0CCF966B1D6559D07ADE97323F64224C2937FC4232C2AD9006CC2FC7

    And IV

    C09A954C993A7CADCF9FF82891B25240

    Tip 1: When you edit the program, running dotnet run will recompile and run it again

    Tip 2: The strings above are in hex-string format, you can convert them to byte arrays using Convert.FromHexString. Byte arrys is the format that the encryption/decryption routines use.

    Tip 3: When you decrypt the message, it will be a byte array in ASCII, but you need to rencode it to ASCII to print it. Try using Encoding.ASCII.GetString().

    Tip 4: You can set the key and iv of an AES instance directly via aes.key = KeyValue and aes.iv = ivValue.

    Tip 5: You’ll need the System.Security.Cryptography library

    Tip 6: C# is really a straightforward programming language, and vscode is great to help you find the methods you need. Feel free to google and find examples. The goal is to get familiar with the basic so you can do something more complicated later.

    Reveal Solution