The birthday paradox is well known and appears in many popular books
on mathematics. In the form in which it is most commonly stated, it says that
if 23 (or more) randomly chosen guests attend a party, then the probability
of two of them sharing the same birthday is greater than 50%. This is considered “paradoxical,” presumably because most people would guess that the probability is much lower (or, equivalently, would suspect that many more
guests would be required for a 50-50 chance of having a pair of matching
birthdays). In the next section, we derive an expression for the probability of a "matching" in the birthday and similar settings. The remainder of this article is concerned with the implications of this results for cryptology. In particular, we shall show that, under certain circumstances, there is little advantage to be gained from repeated encryption. Next, we show that when using a so-called hash function to prepare a "digest" of a message that can be signed, the length of this digest is of crucial importance. Finally, we give an outline of Pollard's rho method for factoring and show how its efficiency follows from the birthday paradox.
Table of Contents:
INTRODUCTION
THE BIRTHDAY PARADOX
MEET-IN-THE-MIDDLE ATTACKS
BIRTHDAY PROBLEMS IN TWO GROUPS
GROUPS OF PERMUTATIONS
IS DES A GROUP?
MESSAGE DIGESTS
POLLARD'S RHO METHOD OF FACTORING
ACKNOWLEDGMENTS
REFERENCES
ABOUT THE AUTHOR
|
