The Birthday Paradox
posted November 2014
I'm studying the internals of hash functions and MACs right now. One-way Compression Functions, Sponge functions, CBC-MAC and... the Merkle–Damgård construction. Trying to find a youtube video about it I run into... The Cryptography course of Dan Boneh I already took 3 years ago. I have a feeling I will forever return to that course during my career as a cryptographer.
The whole playlist is here on youtube and since his course is awesome I just watched again the whole part about MACs. And I thought I should post this explanation of the birthday paradox since as he says:
Everybody should see a proof of the birthday paradox at least once in their life
Something that always bugged me though is that he says the formula for the birthday is
1.2 sqrt(365) whereas it should be square root of 366 since there are indeed 366 different birthdays possible.