Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2001-03-05
2004-12-07
Hua, Ly V. (Department: 2135)
Cryptography
Particular algorithmic function encoding
C380S030000, C380S046000, C380S037000, C380S042000, C380S262000, C380S255000, C713S189000, C713S192000, C713S152000, C713S180000, C711S216000
Reexamination Certificate
active
06829355
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates, in general, to cryptography and, in particular, to block/data stream enciphering.
BACKGROUND OF THE INVENTION
An n-bit hash function produces an n-bit hash value from an input of arbitrary length. An n-bit cryptographic hash function is a one-way n-bit hash function that is collision-resistant. A one-way cryptographic hash function is one that requires 2^n hash computations to be performed before an input is found that produces a given hash value from a given hash function. Collision-resistance indicates that about 2^(n/2) hash computations must be performed before two different inputs are found that produce the same have value. The collision-resistance factor is taken as the amount of security provided by the hash function.
Presently, the only one-way cryptographic hash function approved by the National Institute of Standards and Technology (NIST) is SHA-1 which is disclosed in Federal Information Processing Standards Publication 180-1 (FIPS PUB 180-1), entitled “Secure Hash Standard.” FIPS PUB 180-1 is hereby incorporated by reference into the specification of the present invention.
SHA-1 produces a 160-bit hash value with a corresponding collision resistance of 2^(160/2), whereas MD4 and MD5 each produce a 128-bit hash value with a corresponding collision resistance of 2^(128/2).
NIST requires a one-way cryptographic hash function with 128, 192, and 256 bits of security to go along with three versions of its proposed Advanced Encryption Standard (AES). The present invention is in response to this requirement.
U.S. Pat. No. 5,606,616, entitled “CRYPTOGRAPHIC APPARATUS WITH DOUBLE FEEDFORWARD HASH FUNCTION,” discloses, amongst other things, a device that uses a 64-bit DES algorithm to produce a hash value. Since the hash value is, effectively, 56 bits long, the cryptographic strength of this hash function is no more than 2^(56/2). This hash function is not adequate for use with AES and does not disclose the one-way cryptographic hash function of the present invention. U.S. Pat. No. 5,606,616 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,892,829, entitled “METHOD AND APPARATUS FOR GENERATING SECURE HASH FUNCTIONS,” discloses a device for and a method of dividing a string to be hashed into a number of blocks and hashing each block along with another value using an existing hash algorithm such as MD4, MD5, SHA-1, or DES. U.S. Pat. No. 5,892,829 provides no more security than the hash function employed therein, none of which are suitable for use in AES. Furthermore, U.S. Pat. No. 5,892,829 does not disclose the one-way cryptographic hash function of the present invention. U.S. Pat. No. 5,892,829 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,021,201, entitled “METHOD AND APPARATUS FOR INTEGRATED CIPHERING AND HASHING,” discloses a device for and method of performing ciphering and hashing in parallel instead of in series. However, U.S. Pat. No. 6,021,201 uses existing hash functions for its hash function such as MD
5
and SHA (now known as SHA-1) and does not disclose a new hash function as does the present invention. U.S. Pat. No. 6,021,201 is hereby incorporated by reference into the specification of the present invention.
SUMMARY OF THE INVENTION
It is an object of the present invention to hash a value in a one-way cryptographic manner.
It is another object of the present invention to hash a value in a manner that meets the security requirements of AES and is more secure than MD5 and SHA-1.
The present invention is a method of generating a hash value, or message digest, for a message. The first step is padding the message for which a hash value is desired so that the padded message has a bit length of 512m, where m is a user-definable positive integer. If m=1, the hash value generated is 256 bits. If m=2, the hash value is 512 bits.
The second step of the method is parsing the result of the first step into 16 32m-bit blocks M
i
.
The third step of the method is generating j values W
j
from the parsed message of the second step.
The fourth step of the method is initializing eight blocks a, b, c, d, e, f, g, and h with user-definable values H
1
, H
2
, H
3
, H
4
, H
5
, H
6
, H
7
, and H
8
, respectively, where H
1
-H
8
collectively represent the initial value for the hash value.
The fifth step of the method is converting the contents of a, b, c, d, e, f, g, and h.
The sixth step of the method is computing values that make up the hash value.
The seventh, and last, step of the method is either accepting a portion of the contents of H
1
(j)-H
8
(j) as the hash value of the message or returning to the fifth step for another step of the second shift register.
The device of the present invention includes a user-definable number of registers, a first mod 2
n
adder, a first nonlinear function block, a second nonlinear function block, a first shift function block, a second shift function block, a second mod 2
n
adder, a third mod 2
n
adder, a fourth mod 2
n
adder, a fifth mod 2
n
adder, a sixth mod 2
n
adder, and an accumulator.
The device may also include a message-scheduler device that includes a user-definable number of registers, a third shift function block, a fourth shift function block, a seventh mod 2
n
adder, an eighth mod 2
n
adder, and a ninth mod 2
n
adder.
The device of the present invention includes n 32m-bit blocks as a first shift register; a first function block &sgr;
0
(x); a second function block &sgr;
1
(x); a first logic block; a second logic block; a third logic block; a fourth logic block; p 32m-bit blocks connected as a second shift register; an accumulator; a third function block &Sgr;
0
(x); a fourth function block &Sgr;
1
(x); a fifth function block Maj(x); a sixth function block Ch (x); a sixth logic block; a seventh logic block; an eighth logic block; and a ninth logic block.
REFERENCES:
patent: 5606616 (1997-02-01), Sprunk et al.
patent: 5608801 (1997-03-01), Aiello et al.
patent: 5892829 (1999-04-01), Aiello et al.
patent: 6021201 (2000-02-01), Bakhle et al.
patent: 6141421 (2000-10-01), Takaragi et al.
patent: 6307938 (2001-10-01), Matyas et al.
patent: 6370247 (2002-04-01), Takaragi et al.
patent: 6408273 (2002-06-01), Quagliaro et al.
Bruce Schneier, “Applied Cryptography, 2nd. ed.”, John Wiley & Sons, New York, 1996, pps. 429-459.
FIPS POB 180-1, Secure Hash Standard, Apr. 17, 1995, pps. 1-16.
Hua Ly V.
Morelli Robert D.
The United States of America as represented by the National Secu
LandOfFree
Device for and method of one-way cryptographic hashing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device for and method of one-way cryptographic hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for and method of one-way cryptographic hashing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3323024