1. Each employee in your company has chosen a password for logging in to the computer system. Recently, your company has decided that each employee's password should be secret-shared among two other employees, just in case. Each password can be represented by a number from 0 to 9999. Your job is to choose the secret-sharing scheme. You can assume that the two employees holding shares of their co-worker key will not collaborate to determine the key except in an official emergency. You consult with your three underlings, Larry, Moe, and Curly...

•Larry says:

"For each secret password s to be shared, choose a random number b uniformly from 0 to 9999. The number b is the first share. Let c = s - b (mod 10000). The number c is the second share."

•Moe says:

"I agree with Larry's suggestion except for one thing. If the random number b is 0, the share c is the same as the secret. That's not very secure! I therefore propose that the number b be chosen uniformly from 1 to 9999 instead of from 0 to 9999."

•Curly says:

"I agree with Moe's suggestion except for one thing. If the random number b is less than 10, then the share c will probably have the same hundreds place digit and the same thousands place digit as the secret s. That's not very secure! I therefore propose that the number b be chosen uniformly from 10 to 9999."

Whose scheme is most secure, and why? Consider in particular how much the person receiving the share c thereby learns about the secret s.

2. In order that the secret combination to the CS007 safe would be available in an emergency situation, the TAs have each been given part of the secret. The secret consists of four mod-7 blocks. For each of these numbers, Prof. Klein chose a mod-7 line-the slope of the line is the secret number and the y-intercept was chosen randomly. Prof. Klein then provided each TA with an (x, y) point on each of the lines. Thus Kevin got a point on each of the four lines (namely the points with x-coordinate 1), Mark got a point on each of the four lines (namely the point with x-coordinate 2), and Sheryl got a point on each of the four lines (with x-coordinate 3). Due to a security slipup, you happen on a few of the y-coordinates, as shown in the following table.

(a) For each block of the secret that can be determined from the information given you, give us the block, showing your work.

(b) For each block of the secret that cannot be determined from the information you have, tell us why it cannot be determined and tell us what possible values that block has.

3. You have seen the threshold secret-sharing scheme: each person who is supposed to share the key gets a point on a line and the secret is the y-intercept of that line. Say we have divided up the key among several people, and you and one other person have gotten together to combine your keys. Your point is x = 4 and y = 8, and your partner's point is x = 5 and y = 0. The modulus is 11. What is the secret?

4. In this problem we address the use of a MAC (message authentication code). The modulus for this problem is 11. Alice and Bob have previously agreed upon a secret key consisting of the two mod-11 numbers a and b. Thus the MAC function is

f (x) = ax + b

so when Alice sends a message X, she should accompany the message with the MAC f(X).

If Alice and Bob had been paying attention, they would know that the MAC is secure only if the key is used once. Unfortunately, they missed this fact, and they send two distinct messages with MACs derived using the same key (the same pair of numbers a and b). You, Eve, intercept these messages and MACs:

message: 4, MAC: 5
message: 1, MAC: 9

You decide to tamper with the second message, changing it to 3. What MAC should accompany this forged message to convince Bob that it is legitimate?

5. Alice plans to send Bob a message accompanied by a MAC. (The method for generating the MAC is the one described in the text.) They have previously agreed on a uniformly random secret key for use with the MAC. The message will be sent in plaintext. The set of possible messages is 0, 1, . . . , 12 and the set of possible values of the MAC is also 0, 1, . . . , 12. Calculation of the MAC value is done modulo 13.

Eve plans to intercept the message and MAC, and send her own (fake) message, namely 12. She must also pick a fake MAC to accompany this message; her hope is to fool Bob into accepting the fake message as really being from Alice. She therefore needs to know the probability distribution for the MAC that should accompany the message 12 (i.e., if Alice were to send the message 12, what is the distribution of the MAC that would accompany that message?) Eve knows that the key for the MAC was chosen randomly and uniformly.

In each of the following scenarios, help Eve by sketching the distribution of the value of the MAC that should accompany her fake message.
(a) Eve must choose her fake MAC before seeing either the true message or the true MAC. Give the distribution of the MAC that would accompany the message 12.

(b)Eve has intercepted the true message, 1, and the accompanying MAC, 2. Given what Eve now knows, sketch the distribution of the MAC that would accompany the message 12.

6. Prof. Klein wants to provide the CS007 safe's combination to the teaching assistants using secret-sharing. The combination is known to be an eight-digit number. Prof. Klein chooses mod-108 numbers p, q, r, s, t so that they obey the following equations.

p + q ≡ the safe's combination (mod 108)
r + s + t ≡ q (mod 108)
r + q ≡ the safe's combination (mod 108)

(Obviously, Prof. Klein has inhaled a bit too much chalk dust and has gotten confused about secret sharing.) He provides p to Kevin, q to Mark, r to Sandy, s to Sheryl, and, still confused, t to Kevin.

For each group of TA's given below, say whether or not the group can collectively figure out the combination.

(a)Sandy and Sheryl and Mark
(b)Kevin alone
(c)Sandy and Kevin
(d)Sheryl and Mark
(e)Sandy and Mark

7. (a) Wandering outside the TA Room, you notice that on the bulletin board in that room is the following message:

"Kevin: I looked over the midterm of one of the students. The student's score should be raised by 20 points. I have encrypted the initials of the student using a one-time pad with modulus 26: For each block,

cyph = plain + key (mod 26)

The cyphertext is 10 12. The key will appear on a note I'll slip under the door. Signed, Sandy"

You see the piece of paper containing the key on the floor just inside the (locked) door.

It's folded, so you can't actually read the key. However, you decide to choose your own, fake key, write it on a similar piece of paper, and slide it under the door in the hope Kevin sees your piece of paper instead of Sandy's.

Can you come up with a key that would lead Kevin to add twenty points to your midterm score? If so, give such a key. If not, explain why not. Show your work.

(b)Now you are Kevin. You visit the TA Room and see the following message:

Kevin: Another student deserves a higher midterm score. Using the same encryption scheme as before, one-time pad with modulus 26, I've encrypted the initials of the student. The cyphertext is 17 23. To avoid the fiasco of last week, I've also calculated a MAC for each block of the plaintext using the formula

f (x) = Ax + B rem 26

The MAC for the first block is 23, and the MAC for the second block is 7.

You see three folded-up sheets of paper with encryption keys written on them: "5 18," "12 20," and "19 0". You also see a sheet with a pair of MAC keys: "For first block, A = 1, B = 25, and for second block, A = 1, B = 10."

Assuming the MAC keys are correct, what is the correct plaintext?