Question

A birthday attack (Links to an external site.) is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory (Links to an external site.).

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!)

Start 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;

e − ( n ( n − 1 ) ) 2 d

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!

Answer 1

ANSWER: