Cryptography Reference
In-Depth Information
Definition 2.4 (Cryptographic hash function)
A hash function
h
:Σ
in
→
Σ
out
is
cryptographic
if it is one way or collision resistant.
Most of the time, a cryptographic hash function
h
is used to hash arbitrarily
sized messages to binary strings of fixed size. This is illustrated in Figure 2.2,
where the ASCII-encoded message “This is a file that includes some important but
long statements. Consequently, we may need a short representation of this file.” is
hashed to
0xE423AB7D1767D13EF6EAEA6980
(in hexadecimal notation). The
resulting hash value represents a
fingerprint
or
digest
that is characteristic for the
message and uniquely identifies it. The collision resistance property implies that it
is difficult—or computationally infeasible—to find another message that hashes to
the same fingerprint.
Examples of cryptographic hash functions in widespread use today are MD5
(as used in Figure 2.2) and SHA-1. Cryptographic hash functions and their underly-
ing design principles are further addressed in Chapter 8.
2.1.3
Random Bit Generators
Randomness is one of the most fundamental ingredients of and prerequisites for the
security of a cryptographic system. In fact, the generation of secret and unpredictable
random quantities (i.e., random bits or random numbers) is at the heart of most
practically relevant cryptographic systems. The frequency and volume of these
quantities vary from system to system. If, for example, we consider secret key
cryptography, then we must have random quantities that can be used as secret keys.
In the most extreme case, we must have a random bit for every bit that we want
to encrypt in a perfectly secure way (see Section 10.4). If we consider public key
cryptography, then we must have random quantities to generate public key pairs.
In either case, a cryptographic system may be probabilistic, meaning that random
quantities must be generated for every use of the system. The required quantities
must then be random in the sense that the probability of any particular value being
selected must be sufficiently small to preclude an adversary from gaining advantage
through optimizing a search strategy based on such probability. This is where the
notion of a
random bit generator
as introduced in Definition 2.5 and illustrated in
Figure 2.3 comes into play.
Definition 2.5 (Random bit generator)
A
random bit generator
is a device or al-
gorithm that outputs a sequence of statistically independent and unbiased bits.
Alternatively, a random bit generator is sometimes also defined as an idealized
model of a device that generates and outputs a sequence of statistically independent
and unbiased bits. In either case, it is important to note that a random bit generator
