In $5\mathrm{.}1$ Introduction we discuss the devious secretary Bob having an automatic means of generating many messages that Alice would sign, and many messages that Bob would like to send. By the birthday problem, by the time Bob has tried a total of $2^32$ messages, he will probably have found two with the same message digest. The problem is$,$ both may be of the same type, which would not do him any good. How many messages must Bob try before it is probable that he'll have messages with matching digests, and that the messages will be of opposite types?

If there are $23$ or more people in a room, the odds are better than $50\%$ that two of them will have the same birthday. Analyzing this parlor trick can give us some insight into cryptogra$-$ phy$.$ We$$ll assume that a birthday is basically an unpredictable function taking a human to one of $365$ values $($yeah yeah, $366$ for you nerds$).$

Let$$s do this in a slightly more general way. Let$$s assume n inputs $($which would be humans in the birthday example$)$ and k possible outputs, and an unpredictable mapping from input to output. With n inputs, there are n$($n$1)/2$ pairs of inputs. For each pair there$$s a prob$-$ ability of $1/$k of both inputs producing the same output value, so you$$ll need about k$/2$ pairs in order for the probability to be about $50\%$ that you$$ll find a matching pair. That means that if n is greater than k $,$ there$$s a good chance of finding a matching pair.