Cryptography Reference
In-Depth Information
you have to continually add new names and have no time to sort things (or
your computer would be busy sorting all the time). On the other hand, you have
to continually search for names previously entered. Though searching through
the names is much faster than sorting them, it has to be done so often that your
computer lags behind.
The way out of this dilemma is pretty simple. As you enter names, you cal-
culate the 'sum of the digits' for each name, i.e., you simply add all the bytes
in a name. In addition to the database, you create a
hash table
with 256
entries — one entry for every possible sum of digits. This entry contains refer-
ences to all database records in which a customer name matches the given sum
of digits. So when searching for a name, you first calculate its sum of digits,
then you look up that entry in the hash table and search only for the references
given there. Since all sums of digits will occur roughly equally when there are
many names, searching based on the hash table is 256 times faster!
Calculating the sum of digits is a very simple example of a
hash function
. The
sum of digits itself is called a
hash value
or
hash sum
. The most important
properties of hash functions are:
1. It takes an extensive piece of information (a name) and computes a
compressed piece of information (a one-byte sum of digits).
2. The values of the hash function for different names should differ with
a sufficiently high probability (to make the rows in the hash table about
equally long).
The
one-way hash functions
used in cryptography differ considerably
from the hash functions used in information technology. Though they
also meet the requirements 1 and 2 above, they add at least a third
property:
3. With a given hash value, it is not possible to construct a byte sequence
that produces this hash value at reasonable cost.
So the difference between common hash functions and one-way hash
functions is as big as the difference between a simple conversion of
character sets and a cryptographic algorithm.
For example, if a one-way hash function is applied only to readable texts,
then it should basically suffice to ensure that no readable text can be con-
structed from a given hash value. However, this demand can hardly be
checked in practice. So we try to stay on the safe side and ask for more.
One-way hash functions should generally not be 'reversible'. But these
