Cryptography Reference
In-Depth Information
It so happens that the last root is again the correct one. The redundancy is discarded to
give
x
2
= 7701. Since no one can do this except B, privacy is assured. Finally, B reforms the
message
x
= 59917701 and uses A's public modulus to recover the plaintext
P
(with salt):
59917701
2
16960824
P
(mod 133).
The salt is removed, and the plaintext is regained:
P
= 1696082.
16.6
MESSAGE DIGESTS
A message digest is basically a fixed-size compressed version of an arbitrary length mes-
sage. This compression is done by way of something called a digest function, which is really
a special type of hash function.
You have probably heard the term hash function before, for we use them when we con-
struct hash tables. A hash table is a way of storing data so that it can be retrieved very
quickly. The hash function maps a data item to an index in a table; a “good” hash function
is one that very rarely maps two different data items to the same index. This property is
known as collision resistance.
E
XAMPLES
.
Suppose we represent the data as large integers, and suppose the hash function
is defined as
h
(
x
) = lnr of
x
modulo 2
64
.
Thus, the hash value is merely the trailing 64 bits of the binary representation of
x
. If the
data items are evenly distributed, this may be a suitable mapping for a hash table.
For example, if
x
= 200900995406429488306921947010403054300, then
h
(
x
) = 12493796564522152668
200900995406429488306921947010403054300 (mod 2
64
)
or
h
(
x
)=1010110101100010111000011100011111001100010101101011001011011100
base 2
.
However, since data are rarely evenly distributed, we might choose a hash function such
as this one:
g
(
x
) = lnr of
x
modulo
p
where
p
is a large prime. Since any message
x
not divisible by
p
will be relatively prime to
p
, an overabundance of messages having the same trailing digits will tend to be spread out
among the range of hash values.
Most of these “classical” hash functions are not suitable for cryptography, however. For
reasons which will become apparent, a hash function, say
h
, used to produce message digests
must also satisfy the following properties:
Search WWH ::
Custom Search