I have two sets $M$ and $H$. $M$ is an arbitrary string of length $k$ and $H$ is an string of length $p$. Both are constructed from a charset of length $r$. And $p Hash function $f(m)=h$. I understand that $r^p$ hashes are possible and that $r^k-r^p$ collisions occur for the complete set $M$. But how can I predict the overall probability for finding any element of $M$ that correctly maps to a given element of $h$?
Understanding birthday attack probabilities
1
$\begingroup$
probability
cryptography
1 Answers
1
If the hash function is well constructed, the elements of $M$ will be equally distributed across the hash values. So each element of $M$ will have $r^{-p}$ chance of mapping to a given element of $H$.
In this model, I'm not sure how you are counting collisions. Each element of $H$ will receive $r^{(k-p)}$ of the strings in $M$. If your count is to go through all the strings in $M$ and count one for each that hashes to an already used value, you are correct.