Granted Patent B1

US 8,331,555 · App. 12/277,039 · Granted Dec 11, 2012

Abstract

Claims (62)

1. An MD5 processing apparatus comprising a programmable device programmed to include:

a plurality of processing engines, wherein each processing engine is configured to perform one stage of an MD5 process, wherein each MD5 process stage comprises four MD5 operations in a corresponding MD5 round, each processing engine comprising:

a 32-bit A register;

a 32-bit B register;

a 32-bit C register;

a 32-bit D register and

first, second, third and fourth sub-stage units, each sub-stage unit being configured to perform a corresponding one of the four MD5 operations in the corresponding MD5 round and each sub-stage unit comprising:

a first adder comprising a plurality of logic cells configured to modulo add an A register value and an MD5 pre-adder value, wherein the MD5 pre-adder value comprises the modulo sum of an MD5 message segment and an MD5 constant value;

a fixed MD5 nonlinear function processing unit comprising a plurality of logic cells configured to perform a fixed nonlinear function on inputs comprising a B register value, a C register value and a D register value;

a second adder comprising a plurality of logic cells configured to modulo add an output of the fixed MD5 nonlinear function processing unit and the first adder;

a fixed 32-bit-shift unit comprising routing circuitry configured to effect a fixed bit shift on an output of the second adder; and

a third adder comprising a plurality of logic cells configured to modulo add the B register value and an output of the fixed 32-bit-shift unit; and

a generator coupled to each of the processing engines, the generator being configured to pre-calculate a plurality of MD5 pre-adder values including the MD5 pre-adder value concurrently with the performing of the stages of the MD5 process by the processing engines;

wherein each stage of the MD5 process performs the four MD5 operations of the corresponding MD5 round via the corresponding sub-stage units for advancing register values in the A register, B register, C register and D register respectively from A n , B n , C n , D n to A n+4 , B n+4 , C n+4 , D n+4 , respectively, and

wherein each of the processing engines is configured to perform four iterations of the corresponding stage of the MD5 process to complete the corresponding MD5 round before supplying a corresponding output value,

wherein a first processing engine of the processing engines is configured to supply the corresponding output value to a second processing engine of the processing engines; and

wherein the second processing engine is configured to output an MD5 digest value as the corresponding output value.

2. The MD5 processing apparatus of claim 1 wherein the programmable device is an FPGA.

3. The MD5 processing apparatus of claim 1 wherein one of the stages further comprises a multiplexing branch comprising:

a multiplexer comprising a plurality of logic cells having first and second multiplexer inputs and a multiplexer output;

a pre-multiplexing adder comprising a plurality of logic cells configured to modulo add a final stage C register value and a digest B register value to generate the second multiplexer input;

wherein the first multiplexer input is the final stage C register value;

further wherein the second multiplexer input is selected as the multiplexer output when the processing engine is performing a final MD5 operation of the MD5 process; and

further wherein the first multiplexer input is selected as the multiplexer output when the processing engine is not performing the final MD5 operation.

4. The MD5 processing apparatus of claim 1 wherein the fixed nonlinear function comprises a hardware-implemented nonlinear function implemented without using a multiplexer or any other selective logic.

5. The MD5 processing apparatus of claim 1 wherein the fixed bit shift comprises a hardware-implemented bit shift performed using direct routing of bit values.

6. An MD5 hashing hardware implementation comprising a field programmable gate array (FPGA) programmed to include:

four processing engines, wherein each processing engine is configured to perform one stage of an MD5 process, wherein each MD5 process stage comprises four MD5 operations in a corresponding MD5 round, each processing engine comprising:

four 32-bit registers designated A, B, C and D, wherein each register holds a value; and

four serially connected sub-stage units, each sub-stage unit being configured to perform a corresponding one of the four MD5 operations in the corresponding MD5 round and each sub-stage unit comprising:

a first adder configured to modulo add the A register value and an MD5 pre-adder value, wherein the MD5 pre-adder value comprises the modulo sum of an MD5 message segment and an MD5 constant value;

a fixed MD5 nonlinear function processing unit configured to perform a fixed nonlinear function on the B, C and D register values, wherein the fixed MD5 nonlinear function processing unit implements only a single hardware-implemented MD5 nonlinear function;

a second adder configured to modulo add an output of the fixed MD5 nonlinear function processing unit and the first adder;

a fixed 32-bit-shift unit configured to effect a fixed bit shift on an output of the second adder, wherein the fixed 32-bit-shift unit implements only a single hardware-implemented MD5 shift value;

a third adder configured to modulo add the B register value and an output of the fixed 32-bit-shift unit; and

a generator coupled to each of the four processing engines, the generator being configured to pre-calculate a plurality of MD5 pre-adder values, including the MD5 pre-adder value, concurrently with the performing of the stages of the MD5 process by the four processing engines,

wherein each stage advances A, B, C and D register values from A n , B n , C n , D n to A n+4 , B n+4 , C n+4 , D n+4 ;

wherein each processing engine is configured to perform four iterations of the corresponding stage of the MD5 process to perform the corresponding MD5 round before supplying a corresponding output value; and

wherein a first processing engine of the processing engines is configured to supply the corresponding output value to a second processing engine of the processing engines; and

wherein the second processing engine is configured to output an MD5 digest value as the corresponding output value.

7. The MD5 hashing hardware implementation of claim 6 wherein one sub-stage unit of one of the processing engines further comprises a multiplexing branch comprising:

a multiplexer comprising a plurality of logic cells having first and second multiplexer inputs and a multiplexer output;

a pre-multiplexing adder comprising a plurality of logic cells configured to modulo add a final stage C register value and a digest B register value to generate the second multiplexer input;

wherein the first multiplexer input is the final stage C register value;

further wherein the second multiplexer input is selected as the multiplexer output when the processing engine is performing a final MD5 operation of the MD5 process; and

further wherein the first multiplexer input is selected as the final stage C register value when the processing engine is not performing the final MD5 operation.

8. The MD5 hashing hardware implementation of claim 6 wherein the single hardware-implemented MD5 shift value is implemented by performing direct routing of bit values.

9. An MD5 hashing hardware implementation comprising an FPGA programmed comprising:

a processing engine configured to perform one stage of an MD5 process, the processing engine comprising:

four 32-bit registers designated A, B, C and D, wherein each register holds a value; and

a time-critical path comprising four serially connected sub-stage units, each sub-stage unit being configured to perform a corresponding one of four MD5 operations in the one stage of the MD5 process and each sub-stage unit comprising:

a first adder configured to modulo add the A register value and an MD5 pre-adder value, wherein the MD5 pre-adder value comprises the modulo sum of an MD5 message segment and an MD5 constant value;

a fixed MD5 nonlinear function processing unit configured to perform a fixed nonlinear function on the B, C and D register values, wherein the fixed MD5 nonlinear function processing unit implements only a single hardware-implemented MD5 nonlinear function;

a second adder configured to modulo add an output of the fixed MD5 nonlinear function processing unit and the first adder;

a fixed 32-bit-shift unit configured to effect a fixed bit shift on an output of the second adder, wherein the fixed 32-bit-shift unit implements only a single hardware-implemented MD5 shift value;

a third adder configured to modulo add the B register value and an output of the fixed 32-bit-shift unit, wherein the output of the fixed 32-bit-shift unit is provided to the third adder via direct bit routing to the third adder; and

a generator coupled to the processing engine and another processing engine, the generator being configured to pre-calculate a plurality of MD5 pre-adder values, including the MD5 pre-adder value, concurrently with the performing of the stage of the MD5 process by the processing engine,

wherein the A, B, C and D register values at the beginning of the time-critical path are A n , B n , C n , D n , and further wherein the A, B, C and D register values at the end of the time-critical path are A n+4 , B n+4 , C n+4 , D n+4 ;

further wherein the processing engine is configured to perform four iterations of the stage to complete one MD5 round of the MD5 process before supplying an output value to the another processing engine;

wherein the MD5 process comprises four MD5 rounds; and

wherein the another processing engine being configured to perform another stage of the MD5 process and to output an MD5 digest value.

10. The MD5 processing apparatus of claim 9 wherein one of the stages further comprises a final operation branch that adds a digest B register value to the output of the third adder of the third sub-stage unit during a final MD5 process stage of the MD5 process to generate a final operation adjustment value that the third adder of the fourth sub-stage unit modulo adds to the output of the fourth sub-stage unit fixed 32-bit-shift unit instead of the B register value.

Assignments (8)