Cryptology and the Birthday Paradox

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