15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 11 - due Friday, November 16 in class

Reading Assignment

Read Chapter 5 of Blown to Bits.

Instructions

• Type or neatly write the answers to the following problems.
• Please STAPLE your homework before you hand it in.
• On the first page of your homework, include your name, andrew ID, lab section (A-N), and the assignment number.
• You must hand in your homework at the start of class on the given due date.

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 ig would give you information about what dig does and how to use it.
   1. hostname

   2. /sbin/ifconfig

   3. host 128.2.13.134

   4. host www.google.com

   5. ping -c 10 www.google.com

   6. traceroute www.cmu.edu

   7. traceroute www.nytimes.com

   8. dig +trace apple.com

   9. whois cmu.edu

2. (2 pts) Find out the following information by using the commands from the previous question. Write the name of the command (or commands if you used more than one) and the options and arguments you used.

   1. What is the IP address of the computer you are using?

   2. Is the host www.cs.cmu.edu up and running (able to send and receive packets)?

   3. What steps does the domain name resolution process go through to resolve the name of the host you are currently using? ("Resolving" a name means converting it to an IP address.)

   4. What route (and some information about it) does the packets from your host take to reach another network host such as amazon.com?

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. There is no formal proof that shows that the RSA algorithm cannot ever be broken. Why do we still believe that using RSA provides us with the needed security in e-commerce?

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