A hash function maps a bit vector onto another, usually shorter, bit vector. The result is uniformly distributed, which means that for an input vector chosen at random, each out bit is equally likely to be 0 or 1 and is not correlated with the other bits (unless the size of the range is not a power of 2 in which case the high bits will show correlations).
Typically, m > n and this is why hash functions are called compression functions in some applications. Because the function is non-invertible, it means that not all m-bit input vectors can be losslessly compressed by the same function, or even by different functions if you count the bits required to indicate which compression function is to be used.
Table of Contents
- Hash function basics
- Anatomy of a hash function
- Mixing, and Strict Avalanche Condition
- Search for the perfect mixing function
- Evaluating hash functions
- Evaluation of FNV
- Evaluation of Jenkins' hash
- Evaluation of CRC32
- Evaluation of SHA-1
- Use of S-Boxes in Hash Functions
Hash functions are functions that map a bit vector to another bit vector, usually shorter than the original vector and usually of fixed length for a particular function.
There are three primary uses for hash functions:
- Fast table lookup
- Message digests
Some great stuff to make you the life of the holiday party... :|
Well okay... In any case, I've been asked in the past what a MD5/SHA-1/Hash "is" and how they worked and didn't have a site in my magic bag to quickly share. Now I do... :)