Hash functions

A hash function generally produces a 256 or 512 bit long hash value (shorter values are not considered safe, because it is possible to force collisions with enough compute).

Given a and a with a \neq a and a hash function f, if f(a) = f(a) it's called a collision. A digital signing method, where there is a practical way to create those collisions is not secure.

For a hash function to be considered safe it must fulfill the following 2 properties:

1. Collision resistant: It's practically impossible to find two inputs a and b with a \neq b for which H(a) = H(b). You should need to execute H roughly 2^{n\div 2} times.
2. Preimage-Security: It is practically impossible for any given y=H(x) to find a random x\in\{0,1\}* a value x' (preimage) with H(x')=y. The effort needed to invert y should be roughly 2^n executions of H. A functions that fulfills such a property is refereed to as a one way function

Birthday Paradox

To calculate the probability b people in a room share the same birthday, the following formula can be applied:

\begin{align} Pr(A_{b}) &= \frac{365!}{(365 - b)! \cdot 365^{b}} \\ Pr(\bar{A_{b}}) &= 1-Pr(A_{b}) \end{align}

This can be used to guesstimate the probability of collisions (people sharing the same birthday) by using Pr(A_{b}), which is roughly equal to s(N) = 1.2 \cdot \sqrt{N}

Cryptographers are optimists so they just use t(N) = \sqrt{N} .