Section Number Points Comments
4.2 3 4 DAM2: 4.2, 2
5 2 DAM2: 4.2, 4
14 3 DAM2: 4.2, 12
4.3 3 3 DAM2: 4.3, 2
5 3 DAM2: 4.3, 4
7 4 DAM2: 4.3, 6, Give two different interpretations of the problem
10(c) 2 DAM2: 4.3, 8(c)
12(a) 3 DAM2: 4.3, 10
14 3 DAM2: 4.3, 12
26 4 DAM2: 4.3, 22
4.4 4 3 DAM2: 4.4, 4
8 4 DAM2: 4.4, 8
15 6 DAM2: 4.4, 14
20 3 DAM2: 4.4, 19. Digraphs are defined in Chapter 3.
21 3 DAM2: 4.4, 20
Extra problem [5 points] (due to Jon Kleinberg:}
(1) The phone rings one day and you pick it up. The voice at the other
end says, ``Hello, is this Professor Rivest?" You meant to say ``No,"
but
for some reason you said ``Yes" instead; the next thing you know, people
from this mysterious company arrange to y you out to the
West Coast to advise them on their security system.
``We have a system where we put 100 agents out in the field," they
explain to you, in a sub-basement surrounded by electromagnetic
shielding. ``Each agent announces an RSA public key, and then they use
the RSA cryptosystem to send messages to each other using these public
keys. We're not concerned about whether the agents know each other's
private keys or not -- we're all on the same team, after all -- but
we're very worried about outsiders learning the private keys.
Here's the basic code we planned to use to assign a public key to each
agent:
Method I:
For i = 1, 2, 3, ... , 100
Generate a prime number pi.
Generate a prime number pi'.
Compute the public and private keys for agent i from pi and pi'
After looking at this for a while, we thought: `Isn't Method I sort of
wasteful of primes?'
So we came up with Method II:
Method II:
First generate prime numbers p1, p2, ..., p101
For i = 1, 2, 3, ... , 100
Compute the public and private keys for agent i from pi and pi+1.
Notice how we only use about half as many primes in Method II. But we're
worried that Method II is somehow insecure -- that is, if our enemies knew
we were using Method II to compute keys, they could compute the private
keys from the public keys by a good algorithm."
So here's the question: show that in fact the company's fears are
well-founded. Given a set of 100 public keys known to be generated by
Method II, show how to compute the 100 corresponding private keys by a
good algorithm. (Although this is not critical for answering the
question, you can assume for simplicity that each public key is
publically labeled with the ID number, from 1 through 100, of the agent
that possesses it.)
Note: The point is that, in trying to break the keys, you know that
Method II was used, but you (obviously) don't know at the outset what
the primes p1, p2, ... , p101 are. Nevertheless, your algorithm should
be able to figure them out. Also, here is a crucial thing: your good
algorithm is allowed to have a factor proportional to the number of
agents (or some small power of the number of agents) in its running
time, since the number of agents is simply the (small) constant 100.)