Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
The discrete log hash function described in Section 7.4 is due to Chaum, van Heijst, and Pfitzmann [CvHP92]. A hash function that can be proved secure provided that a composite integer n cannot be factored is given by Gibson [GIB91] (see Exercise 7.4 for a description of this scheme).
The material on extending hash functions in Section 7.5 is based on Damgård [DA90]. Similar methods were discovered by Merkle [ME90].
For infomation concerning the construction of hash functions from private-key cryptosystems, see Preneel, Govaerts, and Vandewalle [PGV94].
The MD4 hashing algorithm was presented in Rivest [RI91], and the Secure Hash Standard is described in [NBS93]. An attack against two of the three rounds of MD4 is given by den Boer and Bossalaers [DBB92]. Other recently proposed hash functions include N-hash [MOI90] and Snefru [ME90A].
Timestamping is discussed in Haber and Stornetta [HS91] and Bayer, Haber, and Stornetta [BHS93].
A thorough survey of hashing techniques can be found in Preneel, Govaerts, and Vandewalle [PGV93].
and denote sy = |h-1(y)|. Define
Note that N counts the number of unordered pairs in X that collide under h. Answer the following:
so the mean of the sy s is
Figure 7.13 Hashing 4m bits to m bits
Further, show that equality is attained if and only if
for every y ∈ Y.
for any y ∈ Y. Let ∈ denote the probability that h(x1) = h(x2), where x1 and x2 are random (not necessarily distinct) elements of X. Prove that
with equality if and only if
for every y ∈ Y.
compute logα β.
Now, suppose that n = 603241 and α = 11 are used to define a hash function h of this type. Suppose that we are given three collisions for h: h(1294755) = h(80115359) = h(52738737). Use this information to factor n.
Figure 7.14 Hashing 2i m bits to m bits
where 1 ≤ i < j ≤ 15, use a computer program to determine λij, which denotes the number of X[k]s (16 ≤ k ≤ 79) such that X[i] and X[j] both occur in the expression for X[k]. What is the range of values λij?
Previous | Table of Contents | Next |
Copyright © CRC Press LLC