Method and apparatus for generating secure hash functions
First Claim
1. A method for performing a hash function on a string of information elements, comprising the steps of:
- a. a stretch processor receiving an input string of information elements;
b. the stretch processor stretching the input string into a longer string;
c. a compression module receiving the longer string; and
d. the compression module compressing the longer string into a hash value.
11 Assignments
0 Petitions
Accused Products
Abstract
A secure hash function according to the present invention uses a stretch function 202 and a compression function 202 to provide a secure hash value. A stretch function is a function which increases an input string (pre-image). In one version of the invention, a stretch function ƒ maps l-bit inputs into 2m bit, where 2m>l. Preferably, the stretch function ƒ is one-way. The stretch function randomizes the input string. The output of the stretch function is fed into a compression function c, which compresses the stretch function output from 2m bits to 2n bits, where m>n. The compression function is preferably a cryptographic primitive selected from a family of compression functions. In a preferred embodiment, a standard key scheduling algorithm of the cryptographic compression function (such as DES) is replaced and an output of the stretch function is used as the key. The inventors find that using a stretch function output as the compression function key improves the security of the compression function. Moreover, because the stretch function output randomizes the input string, the security constraints on the compression function are less stringent. As a result, an efficient, simple, and secure hash function is provided.
59 Citations
41 Claims
-
1. A method for performing a hash function on a string of information elements, comprising the steps of:
-
a. a stretch processor receiving an input string of information elements; b. the stretch processor stretching the input string into a longer string; c. a compression module receiving the longer string; and d. the compression module compressing the longer string into a hash value. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 34, 35, 36, 37)
-
-
17. A hashing device, comprising:
-
a. a stretch processor configured to receive an input string of information elements and to stretch the input string into a longer string; and b. a compression module configured to receive the longer string, to perform a compression function on the longer string, and to output a hash value. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 38, 39, 40, 41)
-
Specification