15110 Fall 2012 [Touretzky/Kaynar]
Problem Set 11 - due Friday, November 16 in class
Read Chapter 5 of Blown to Bits.
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.
- (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.
- host 220.127.116.11
- host www.google.com
- ping -c 10 www.google.com
- traceroute www.cmu.edu
- traceroute www.nytimes.com
- dig +trace apple.com
- whois cmu.edu
(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.
- What is the IP address of the computer you are using?
- Is the host www.cs.cmu.edu up and running (able to send and receive packets)?
- 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.)
- What route (and some information about it) does the packets from your host take to reach another network host such as amazon.com?
- (1 pt) Encryption.
- 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?
- How many distinct substitutions rules are there for an n-symbol
- 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.
- (2 pts) Consider a public key encryption system using RSA
encryption that starts with two prime numbers p = 137 and q = 241.
- 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.
- 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.
- Verify that the receiver can decode the messages from part (b)
using the private key pair. Show your work.
- (1 pt) Answer the following questions based on your reading of Blown to
Bits, in addition to your understanding of the lecture material.
- 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?
- What is meant by "security through obscurity"? Do cryptographers adopt this as a principle? Why or why not?