COS 109: Problem Set 8     (Last one!!)

Due midnight Wednesday November 15

Problem set answers need not be long, merely clear enough that we can understand what you have done, though for computational problems, show enough of your work that we can see where your answer came from. Please type your answers if at all possible. Thanks.

Don't forget that if the data you start with is approximate, the results cannot be precise.

1. Bits, Bytes, Binary

(a) The image below comes from a short-lived Wendy's advertisement. List all the positive integer pairs of x and y for which x^y is 256.

(b) Assuming that the options are simple alternatives like "do you want cheese or not?", what's the most likely number of options that a customer is offered?

(c) A home wi-fi router acts as a NAT. It usually uses the IPv4 address range 192.168.0.0 to 192.168.255.255 internally, assigning a unique IP address in this range to each device in the home. In principle, how many devices could this range support? Express it as a power of 2.

(d) Old versions of Excel supported a maximum of 65,536 rows; columns were labeled A, B, ..., Z, AA, AB, ..., through IV. Give a plausible explanation of why the last column has the label IV.

2. What's Your Password?

For this problem, a "key" is just "a password" that is potentially shared with other people.

(a) Suppose that Alice, Bob and Carol have a relationship in which

• each one of them needs to protect their own personal information, for which they need an individual password;
• each person needs to carry on private conversations with each other person (i.e., Alice and Bob want to talk without Carol being able to know what they are saying, Alice and Carol want to talk without Bob, and so on), and each such combination requires a different password;
• Alice, Bob and Carol need to talk among themselves while preventing outsiders from understanding those conversations as well -- yet more passwords.

(b) Suppose that David joins the group, and relationships are even more complicated: they need passwords for each individual and each possible combination of private conversations among subgroups (e.g., Alice, Carol and David want to be able to talk among themselves while excluding Bob) as well as excluding outsiders from all combinations. How many different secret passwords are now needed? List the passwords by the people who will share them.

(c) As the group grows, more and more passwords will be needed. Give a general formula or way to express how the number of passwords varies as a function of N, the number of people in the group. If you don't see a formula, then give the numbers you have computed, for 1 through 6 people.

(Hint: figure out how many passwords are needed for one person, for two people, and so on up to five people, combine that with what you did above, and look for a pattern.)

3. Password Cracking

(a) AOL used to generate initial passwords by joining two five-letter words with a colon ":", such as "cheap:skate" or "tiger:tunes". Suppose that AOL's list has 10,000 5-letter words, and that all words are entirely in lower case. How many passwords does this scheme provide?

(b) One way to make AOL's original scheme more secure is to allow upper case as well as lower case anywhere in the words, and treat upper-case and lower-case letters as distinct (so that "Tiger:tunes" is not the same as "tiger:tunes"or "tigEr:TuNeS"). By what factor does this scheme increase the number of different passwords?

(c) How does the difficulty in cracking such passwords grow in proportion to the number of words in AOL's dictionary?

Submission

Please use this Google doc for your answers.

Submit your problem set in PDF format by uploading a file called pset8.pdf to Gradescope. You can submit as many times as you like; we will only look at the last one.

xkcd.com/926