Cryptography Reference
In-Depth Information
reserve of scare quotes: “Therefore, Alice has received a message 'signed' by
Bob, which she can 'prove' that he sent, but which she cannot modify.”
8
A few issues had to be resolved before RSA signatures could become a
practical reality, among them computational performance. A major disad-
vantage of public-key algorithms is their relative inefficiency: in contrast
to secret-key algorithms, the arithmetic operations required by RSA are
orders of magnitude more computationally intensive. Furthermore, in
1982, cryptographer George Davida discovered an attack against RSA sig-
natures that would eventually prove of considerable import.
9
Under the
assumption that it could get a user to sign arbitrary messages (see “chosen-
message attacks” in “The Threat of Forgery,” later in this chapter), an
adversary could break the system and obtain valid signatures on any
message of his choice. In 1984, Dorothy Denning proposed to resolve both
issues at once.
10
To improve the efficiency of the signing process and thwart
Davida's attack, messages should be first compressed using
hash functions
and signed in a single application of the public-key algorithm.
Cryptographic hash functions are algorithms that compress messages
into fixed-length strings of bits (usually called hashes, message digests, or
fingerprints). That is, given as input a digital object of arbitrary length (e.g.,
a document, an image, a software program), the hash function will output
a fixed-length (e.g., 128- or 160-bit) fingerprint. Because there are only a
finite number of strings of 128 or 160 bits, multiple digital objects are
bound to have identical fingerprints, in what is a called a “collision.”
Cryptographic hash functions are designed to be resistant to an adversary
taking advantage of such collisions: given an object
x
and its fingerprint
h
, it is presumed computationally infeasible to find another object
y
with
the same fingerprint
h
. Additionally, given a fingerprint
h
, it is presumed
computationally infeasible to reverse the function, that is, to find an object
x
that hashes to
h.
In both cases, collision resistance means the best strat-
egy available to an adversary is that of exhaustive search, that is, trying all
objects one at a time.
11
Cryptographic hash functions are now an integral part of the mechanics
of RSA signatures, both in theory and practice.
12
Davida's attack and its
solution underlined an issue that would become increasingly important
over time: the provable security of number-theoretic
algorithms
did not
translate without effort in that of cryptographic
protocols
. As Denning
noted, “it is not enough to have an encryption algorithm that is compu-
