Matthew L. Wright
Assistant Professor, St. Olaf College

Homework 17: Security

CS 121 ⋅ Spring 2016

Upload your solutions to the following questions to Moodle for HW17. You may type your solutions to questions 1, 2, and 3 in a single file, such as a text file or a Word document. For question 4, please upload a Python file.

  1. This question is about the Caesar cipher. You may wish to use the Caesar cipher Python program.

    1. The following text has been encrypted using a Caesar cipher with shift of 11. What is the plaintext (decrypted) message?

      Tyqzcxletzy dpnfctej td xzcp txazcelye ezolj esly pgpc mpqzcp.
    2. An English sentence has been encrypted using a Caesar cipher with some shift, producing the following ciphertext:

      M riih e vmhi xs xli emvtsvx xsqsvvsa.

      Analyze the letters and spaces to determine the shift. What is the shift? What is the plaintext (decrypted) message?

  2. This question is about using the SHA-1 hash function for password storage. You may wish to use the SHA-1 Python program.

    Suppose you are a system administrator, and you are building a login application that stores user passwords. Rather than storing plaintext passwords, you store the SHA-1 cryptographic hash of each user's password. For example, if a user chooses "password" as his or her password (this is a very poor choice), the system stores the SHA-1 digest of "password", which is:

    1. Suppose that a certain user chooses "kayak" as his or her password. What will the system store for this password?
    2. Suppose that you suspect that a different user has chosen a weak password. In your system, you can see that the stored digest of this user's password is:


      What password did this user choose? Use the list of worst passwords of 2015 and the SHA-1 program to find out.

  3. This question is about digital signatures. You may wish to use the SHA-1 Python program.

    Suppose that you want to send a message to a friend with a digital signature. You and your friend agree on the word "octagon" as your shared secret. You also agree to use the first 8 characters of the SHA-1 cryptographic hash as your message digest.

    Recall that to send a message with a digital signature, you first concatenate a shared secret onto the end of the message. Then compute the digest of message+secret. The transmission consists of message+digest. (The secret is not transmitted!)

    Likewise, when receiving the transmission, first remove the digest, and then add the secret. Then compute the digest of message+secret and see if it matches the received digest.

    1. If your message text is below, what will you send to your friend?

      Where are we meeting?
    2. Now suppose that your friend replies to your message, but an adversary intercepts the reply. The adversary then sends you several messages, trying to fool you. You receive the following four messages, only one of which is from your friend. Where should you plan to meet your friend?

      Meet me at the park.7531a2ad Meet me at the cafeteria.e53b06c8 Meet me at the lab.20132b74 Meet me at the dorm.b15d98c3
  4. This question asks you to use Python to write a recursive function.

    The greatest common divisor (GCD) of two integers is the largest number that divides both integers without remainder.

    Write a recursive function gcd(a, b) that finds the GCD of two integers a and b. Assume that a > b ≥ 0. The GCD can be computed by the following algorithm:

    • If b = 0, then gcd(a, 0) = a.
    • Otherwise, gcd(a, b) = gcd(b, a % b).

    For example, gcd(63, 24) should return 3, and gcd(90, 9) should return 9.