Pipelined hardware implementation of a hashing algorithm

• US 6,091,821 A
• Filed: 02/12/1998
• Issued: 07/18/2000
• Est. Priority Date: 02/12/1998
• Status: Expired due to Term

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Inventors: Buer, Mark Leonard
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Myhre, James W.
• Application Number:
  US09/022,847
• Time in Patent Office: 887 Days
• Field of Search: 380/28, 380/30, 380/269, 708/491, 708/492, 708/521, 713/174, 713/189
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

A hardware implementation of a hashing algorithm is presented. In a first pipeline stage, a first memory stores input data for the hashing algorithm. Data is selected out of the first memory, for example, using a counter which is reset and incremented by differing values depending upon the round of the algorithm. A second memory stores constants used for the hashing algorithm. Constants are selected out of the second memory, for example, using a counter. An adder adds data from the first memory and a constant from the second memory with a state value selected, for example, using a multiplexer. The result is stored as an intermediate algorithm value in a first pipeline register. In a second pipeline stage a second adder adds one of a plurality of hashing function values to the intermediate algorithm value in the first pipeline register. The result is shifted. A third adder adds the shifted result to one of the plurality of state values and places the result into a second pipeline register.

Claims

1. Hardware which implements a hashing algorithm comprising:

a first pipeline stage comprising;

first storage means for storing input data for the hashing algorithm, the first storage means having a first storage means output,

first selection means, coupled to the first storage means, for selecting data from the first storage means to be placed on the storage means output,

second storage means for storing constants used for the hashing algorithm, the second storage means having a second storage means output,

second selection means, coupled to the second storage means, for selecting a constant from the second storage means to be placed on the storage means output,

third selection means for selecting one of a plurality of state values to be placed onto a third selection means output,

a first pipeline storage means, for storing an intermediate algorithm value, and

a first adding means for adding values on the first storage means output, the second storage means output and the third selection means output and placing a first adding means result into the first pipeline storage means; and

,

a second pipeline stage comprising;

fourth selection means for selecting one of a plurality of hashing function values to be placed on a fourth selection means output,

a second adding means for adding the intermediate algorithm value in the first pipeline storage means to a value placed on the fourth selection means output to produce a second adding means result,

shifting means for shifting the second adding means result to produce a shifted result,

a second pipeline storage means for storing an algorithm generated state value, and

a third adding means for adding the shifted result to one of the plurality of state values and placing a third adding means result into the second pipeline storage means.

2. Hardware as in claim 1 wherein the hashing algorithm is the RSA Data Security, Inc. MD5 Message-Digest Algorithm.

3. Hardware as in claim 1 wherein the algorithm generated state value is used as a first state value and wherein the third adding means adds the shifted result to a second state value.

4. Hardware as in claim 3 wherein the second pipeline stage additionally comprises:

fifth selection for selecting the second adding means to receive the intermediate algorithm value when the first state value is to be calculated.

5. Hardware as in claim 1 wherein the second pipeline stage additionally comprises:

a third pipeline storage means for storing the algorithm generated state value;

a fourth pipeline storage means for storing the algorithm generated state value;

a fifth pipeline storage means for storing the algorithm generated state value; and

,

fifth selection for selecting which of the second pipeline storage means, the third pipeline storage means, the fourth pipeline storage means and the fifth pipeline storage means is to receive the algorithm generated state value.

6. Hardware as in claim 1 wherein the first pipeline stage is a multi-cycle path.

7. Hardware as in claim 1 wherein the second pipeline stage is a multi-cycle path.

8. A method for implementing a hashing algorithm comprising:

(a) generating an intermediate algorithm value within a first pipeline stage comprising the following substeps;

(a.1) storing input data for the hashing algorithm in a first memory,

(a.2) storing constants used for the hashing algorithm in a second memory, the second memory having a second memory output,

(a.3) selecting data from the first memory to be placed on a memory output,

(a.4) selecting a constant from the second memory to be placed on the memory output,

(a.5) selecting one of a plurality of state values,

(a.6) adding the data selected in substep (a.3), the constant selected in substep (a.4) and the state value selected in substep (a.5) to produce the intermediate algorithm value, and

(a.7) storing the intermediate algorithm value; and

,

(b) generating an algorithm generated state value within a second pipeline stage comprising the following substeps;

(b.1) selecting one of a plurality of hashing function values,

(b.2) adding the intermediate algorithm value with the hashing function value selected in substep (b.1) to produce a result,

(b.3) shifting the result produced in substep (b.2) to produce a shifted result,

(b.4) adding the shifted result produced in substep (b.3) to one of the plurality of state values to generate an algorithm generated state value, and

(b.5) storing the algorithm generated state value.

9. A method as in claim 8 wherein the hashing algorithm is the RSA Data Security, Inc. MD5 Message-Digest Algorithm.

10. A method as in claim 8 wherein the algorithm generated state value stored in substep (b.5) is used as a first state value and in substep (b.4), the shifted result produced in substep (b.3) is added to a second state value.

11. A method as in claim 10 wherein substep (b.4) is performed when the first state value is to be calculated.

12. A method as in claim 8 wherein substep (b.5) includes

storing the algorithm generated state value in a first register when the algorithm generated state value is a first state value;

storing the algorithm generated state value in a second register when the algorithm generated state value is a second state value;

storing the algorithm generated state value in a third register when the algorithm generated state value is a third state value; and

,

storing the algorithm generated state value in a fourth register when the algorithm generated state value is a fourth state value.

13. A method as in claim 8 wherein in step (a) the first pipeline stage is a multi-cycle path.

14. A method as in claim 8 wherein in step (a) the second pipeline stage is a multi-cycle path.