The birthday attack:

Suppose there are 23 people at a gathering. What is the chance that at least two people share the same birthday? This is known as the birthday paradox, for the answer is 50 percent, which at first seems surprisingly large. A variant of the puzzle is this: Suppose there are r people in each of two rooms. Each person holds a (random) number between 1 and n, where n is large compared to r. What is the probability that a pair of people, one from each room, possess the same number?

(a) Argue that the probability that such a pair exists is 

(b) Letr =  for some λ. Using the approximation 1-x ≈ e^-x, find the probability that such a pair exists in terms of λ.

(c) What is the probability of a matching pair if n = 250 and r = 230?

(d) Alice is planning to digitally sign the hash of a contract. The hash will be a reduced document 50 binary digits in length. She feels safe because there are 250 possible hash functions. Larry decides to launch a birthday attack by, first, preparing a fraudulent contract with terms unfavorable to Alice.

Then he selects 30 places in each of the contracts where a slight change can be made (adding a comma for instance), changes that Alice is likely to accept. He prepares 230 (approximately 1 million) versions of the contract by using all combinations either making a change or not at the 30 places. He then forms the hashed version of all of these, and looks for a match. What is the probability that there will be at least one pair of hashed versions, a good and a fraudulent, that match? If Larry finds a match, he can show Alice the corresponding fair contract and present the fraudulent hashed version for her digital signature.