15110 Spring 2013 [Kaynar/Gunawardena]

Problem Set 10 - due Friday, April 12 in class

Reading Assignment

Read Chapter 5 of Blown to Bits.

Instructions

  1. (4 pts) Open a command line terminal on an Andrew machine and run the following commands. Describe in a sentence or two what you understand from the output of each command. You are not expected to understand every detail; try to extract the most useful information you can from the output. You are encouraged to use the Web as a resource. You can also use the man command to read the manual pages about a given Unix/Linux command. For example, man who would give you information about what who does and how to use it.

    1. hostname

    2. /sbin/ifconfig

    3. host 128.2.210.145

    4. host www.google.com

    5. ping -c 5 www.facebook.com

    6. traceroute www.nytimes.com

    7. wget www.facebook.com (check your folder using command ls to see if there is a new file. what is it?)

    8. whois cmu.edu

  2. (2 pts) Briefly answer each of the following questions. Your answer should be constructed using few sentences

    1. How do you find the IP address of the computer you are using?

    2. Your friend uses his/her gmail account to send an email to your CMU email address? What is the minimum number of servers that will be involved in the transaction? Describe a possible path (hardware) of this email from your friends computer to your computer?

    3. What is the purpose of an ISP? Can an ISP determines which packets you are supposed to receive and which packets you are not? Briefly explain your answer.

    4. What is the purpose of a router? Does router knows if they are handling an email or an image? Why or why not?

  3. (1 pt) Encryption.
    1. Caesar ciphers are substitution ciphers using a uniform rule for substitutions: every symbol is shifted by the same amount. A more general way to build a substitution cipher is to use a substitution rule that cannot be described by a uniform shift. Any symbol can be substituted for any other symbol, as long as the mapping is unique and hence invertible.

      For a 3 letter alphabet consisting of A, B, and C, the possible shifts are 0 (giving ABC), 1 (giving BCA), and 2 (giving CAB), but the other substitution possibilities, which are not shifts, are ACB, BAC, and CBA. So there are a total of 6 substitution rules. Generalizing from this example, how many distinct subtitution rules are there for a 4 symbol alphabet?

    2. How many distinct substitutions rules are there for an n-symbol alphabet?

    3. What is a commonly used attack on substitution ciphers, other than brute-force attacks? How does a Vigenere cipher attempt to counter such attacks? Explain. Hint: Read Blown to Bits.

  4. (2 pts) Consider a public key encryption system using RSA encryption that starts with two prime numbers p = 137 and q = 241.

    1. Compute the public key pair (e, n) and the private key pair (d, n) for this system. Use Ruby to select the smallest value for e that will work, and then select the smallest value for d that will work given your value for e. Show your work.

    2. Consider the numerical messages 2012 and 15110 that are to be transmitted. What are the encrypted forms of these messages? You can use Ruby to find the answer, but show your work.

    3. Verify that the receiver can decode the messages from part (b) using the private key pair. Show your work.

  5. (1 pt) Answer the following questions based on your reading of Blown to Bits, in addition to your understanding of the lecture material.

    1. Suppose someone came up with an algorithm that can factor any large integer in less than a few seconds. How will that affect e-commerce as we know now?

    2. What is meant by "security through obscurity"? Do cryptographers adopt this as a principle? Why or why not?