A birthday attack r: is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory :5. Birthday matching is a good model for collisions between items randomly inserted into a hash table. What is the probability that some birthday is shared by two people in a class of n randomly and independently selected students? To work this out, we'll assume that the probability that a randomly chosen student has a given birthday is 1/d (of course we still work with 365 day calendars!) Sta rt with : There are d"n sequences of n birthdays, and under our assumptions, these are equally likely. There are (d)(d-1)(d-2)...(d-(n-1)) length n sequences of distinct birthdays. That means the probability that everyone has a different birthday is; ................................................................................ do the math and show; _ (non1)) 6 2d 2. Now show that it implies that to use a hash function that maps n items into a hash table of size d, you can expect many collisions if n"2 is more than a small fraction of d. This is how Birthday attacks work