Cryptography Reference
In-Depth Information
In this definition, the domain of the hash function is Σ
in
.Thismeansthat
it consists of all strings over Σ. In theory, these strings can be infinitely long. In
practice, however, one usually has to assume a maximum string length
n
max
for
technical reasons. In this case, a hash function is formally expressed as
h
:Σ
n
max
in
Σ
out
.
→
In either case, note that the hash function must be efficiently computable and
that we further explain the notion of an “efficient computation” in the context of
complexity theory in Chapter 6. Also, note that the two alphabets Σ
in
and Σ
out
can
be (and typically are) the same. In this case, Σ is used to refer to either of them. In
a typical (cryptographic) setting, Σ is the binary alphabet (i.e., Σ=
)and
n
is
128 or 160 bits. In such a setting, a hash function
h
generates binary strings of 128
or 160 bits.
{
0
,
1
}
!"#!$!"#%$$&'(
Figure 2.2
A cryptographic hash function.
In cryptography, we are mainly interested in hash functions with specific
properties. Some of these properties (i.e., preimage resistance, second-preimage
resistance, and collision resistance) are formally introduced and discussed in Chapter
8. A
one-way hash function
is then a hash function that is preimage resistant and
second-preimage resistant (or weak collision resistant), whereas a
collision resistant
hash function
is a hash function that is preimage resistant and collision resistant (or
strong collision resistant). As suggested in Definition 2.4, either of these functions
is called
cryptographic
and can be used for cryptographic purposes (e.g., for data
integrity protection, message authentication, and digital signatures).
