#md5

I love writing pre-canon material

Buenas tardes amigos,

so during preparations to my previous post, I needed to do some digging about cryptography and I dig deep on the internet, haha. I have found an easy and interesting paradox (I have read about it before, but never knew it has applications :o), that actually was a base to create a cryptoanalysis approach that led to finding vulnerabilities in the MD5 algorithm. Today I want to tell you about that paradox and then I will briefly write how is it applied in cryptography.

Let me introduce to you: Birthday Paradox

I will start with a problem statement: What is the probability p that given n random people will have a birthday on the same day? Or let us ask: how many people do we need to have i.e. 50% probability that at least two of them will have a birthday on the same day?

(Quick definition reminder) As all of us know from high school, in the classic definition of probability, we divide the number of favorable events by the number of all the events that we might have and the product of this division is called probability :). What is more, the probability of a certain event equals 1 and the probability of the opposite event equals 1-p, where p - the probability of a wanted event. 

Uhh, so as now we are on the same page haha, let us think about the problem. First of all, how can we count the possibility of at least two people having a birthday on the same day? Intuition tells us to think about the question another way round, so we can ask ourselves ... what will be a probability of none of them having a birthday on the same day? It is simple, (adding additional assumptions that we do not take under consideration lap years) there are 365 possibilities for each of n people to have their special day, so all the events that we might have (number in our denominator) is equal to 365 to the power of n. How about favorable events? So let us assume that the first person can take any day (so there are 365 possibilities for him), second one can pick any day except the day that was chosen by the first one (so there are 364 possibilities of that day), the third person can pick any day except these two, and so on, and so on. In the end, we will have a probability(*) equal division 365(365-1)(365-2)...(365-n+1) by 365^n. And the opposite event will be the probability of a given statement :). Right now we need only to estimate the n number for example for p equal 50%. 

* = (1-1/365)...(1-(n-1)/365) and using 1+x<= e^x inequality (oh god, not using latex hurts so much, I will add in another post the exact equations, promise!) we can estimate that actual number for this requirements to be fulfilled is just 23! So it takes only 23 people to be more than 50% sure that two of them can have a birthday on the same day. Nice, huh?

This post is already long so I will go with application in the next one haha.

Gracias amigos, any feedback is super welcome!

xoxo,