Apparatus and method for implementing a block cipher algorithm

• US 7,570,760 B1
• Filed: 09/13/2004
• Issued: 08/04/2009
• Est. Priority Date: 09/13/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Olson, Christopher H., Grohoski, Gregory F.
• Primary Examiner(s): Parthasarathy; Pramila
• Application Number:
  US10/939,829
• Time in Patent Office: 1,786 Days
• Field of Search: None
• US Class Current: 380/37
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]

Abstract

An apparatus and method for implementing a block cipher algorithm. In one embodiment, a cryptographic unit configured to implement a block cipher algorithm may include state storage configured to store cipher state, where the cipher state includes a plurality of rows and a plurality of columns. The cryptographic unit may further include a cipher pipeline comprising a plurality of pipeline stages, where each pipeline stage is configured to perform a corresponding step of the block cipher algorithm on the cipher state, and where a given one of the pipeline stages is configured to concurrently process fewer than all of the columns of the cipher state.

Claims

1. A cryptographic unit configured to implement a block cipher algorithm, said cryptographic unit comprising:

state storage configured to store cipher state, wherein said cipher state includes a plurality of rows and a plurality of columns; and

a cipher pipeline comprising a plurality of pipeline stages, wherein each pipeline stage is configured to perform a corresponding step of said block cipher algorithm on said cipher state, wherein a given one of said pipeline stages is configured such that a maximum number of columns that said given pipeline stage is operable to concurrently process is fewer than all of said columns of said cipher state, and wherein during execution of a given round of said block cipher algorithm, said given pipeline stage is operable to process said cipher state in portions over multiple distinct cycles of operation.

2. The cryptographic unit as recited in claim 1, wherein an implementation area of said given pipeline stage is proportional to a number of said columns said given pipeline stage is configured to concurrently process.

3. The cryptographic unit as recited in claim 1, wherein said block cipher algorithm is compliant with a version of Advanced Encryption Standard.

4. The cryptographic unit as recited in claim 1, wherein said block cipher algorithm comprises a byte-substitution step and a row-shifting step, and wherein during an encryption operation, said row-shifting step is performed prior to said byte-substitution step.

5. The cryptographic unit as recited in claim 1, wherein said block cipher algorithm comprises a byte-substitution step, a column-mixing step and an add-round-key step, wherein a first one of said plurality of pipeline stages is configured to implement said byte-substitution step, and wherein a second one of said plurality of pipeline stages is configured to implement said column-mixing step and said add-round-key step.

6. The cryptographic unit as recited in claim 1, wherein each of said plurality of pipeline stages is configured to concurrently process two columns of said cipher state.

7. The cryptographic unit as recited in claim 1, wherein each of said plurality of pipeline stages is configured to concurrently process one column of said cipher state.

8. A processor, comprising:

the cryptographic unit as recited in claim 1; and

instruction fetch logic configured to issue a first instruction from one of a plurality of threads during one execution cycle and to issue a second instruction from another one of said plurality of threads during a successive execution cycle;

wherein said cryptographic unit is configured to execute independently of said instruction fetch logic.

9. A processor, comprising:

the cryptographic unit as recited in claim 1; and

instruction fetch logic configured to issue a plurality of instructions including a first and a second instruction, wherein said first instruction is issued from one of a plurality of threads during one execution cycle, and wherein said second instruction is issued from another one of said plurality of threads during a successive execution cycle;

wherein said cryptographic unit is configured to execute one of said plurality of instructions issued by said instruction fetch logic.

10. A method, comprising:

storing cipher state of a block cipher algorithm, wherein said cipher state includes a plurality of rows and a plurality of columns; and

executing said block cipher algorithm in a plurality of pipeline stages, wherein each pipeline stage is configured to perform a corresponding step of said block cipher algorithm on said cipher state;

wherein executing said block cipher algorithm comprises a given one of said pipeline stages concurrently processing a maximum number of columns of said cipher state that is fewer than all of said columns of said cipher state; and

wherein executing said block cipher algorithm further comprises, for a given round of said block cipher algorithm, said given pipeline stage processing said cipher state in portions over multiple distinct cycles of operation.

11. The method as recited in claim 10, wherein an implementation area of said given pipeline stage is proportional to a number of said columns said given pipeline stage is configured to concurrently process.

12. The method as recited in claim 10, wherein said block cipher algorithm is compliant with a version of Advanced Encryption Standard.

13. The method as recited in claim 10, wherein said block cipher algorithm comprises a byte-substitution step and a row-shifting step, and wherein during an encryption operation, said row-shifting step is performed prior to said byte-substitution step.

14. The method as recited in claim 10, wherein said block cipher algorithm comprises a byte-substitution step, a column-mixing step and an add-round-key step, wherein a first one of said plurality of pipeline stages is configured to implement said byte-substitution step, and wherein a second one of said plurality of pipeline stages is configured to implement said column-mixing step and said add-round-key step.

15. The method as recited in claim 10, wherein each of said plurality of pipeline stages is configured to concurrently process two columns of said cipher state.

16. The method as recited in claim 10, wherein each of said plurality of pipeline stages is configured to concurrently process one column of said cipher state.

17. The method as recited in claim 10, further comprising:

issuing a first instruction from one of a plurality of threads during one execution cycle; and

issuing a second instruction from another one of said plurality of threads during a successive execution cycle;

wherein executing said block cipher algorithm is configured to operate independently of issuing instructions from said plurality of threads.

18. The method as recited in claim 10, further comprising:

issuing a plurality of instructions including a first and a second instruction, wherein said first instruction is issued from one of a plurality of threads during one execution cycle, and wherein said second instruction is issued from another one of said plurality of threads during a successive execution cycle;

wherein executing said block cipher algorithm occurs in response to issuing one of said plurality of instructions.

19. A system, comprising:

a system memory; and

a processor coupled to said system memory and comprising a cryptographic unit configured to implement a block cipher algorithm, said cryptographic unit comprising;

state storage configured to store cipher state, wherein said cipher state includes a plurality of rows and a plurality of columns; and

a cipher pipeline comprising a plurality of pipeline stages, wherein each pipeline stage is configured to perform a corresponding step of said block cipher algorithm on said cipher state, wherein a given one of said pipeline stages is configured such that a maximum number of columns that said given pipeline stage is operable to concurrently process is fewer than all of said columns of said cipher state, and wherein during execution of a given round of said block cipher algorithm, said given pipeline stage is operable to process said cipher state in portions over multiple distinct cycles of operation.

20. The system as recited in claim 19, wherein an implementation area of said given pipeline stage is proportional to a number of said columns said given pipeline stage is configured to concurrently process.

21. The system as recited in claim 19, wherein said block cipher algorithm is compliant with a version of Advanced Encryption Standard.

22. The system as recited in claim 19, wherein said block cipher algorithm comprises a byte-substitution step and a row-shifting step, and wherein during an encryption operation, said row-shifting step is performed prior to said byte-substitution step.

23. The system as recited in claim 19, wherein said block cipher algorithm comprises a byte-substitution step, a column-mixing step and an add-round-key step, wherein a first one of said plurality of pipeline stages is configured to implement said byte-substitution step, and wherein a second one of said plurality of pipeline stages is configured to implement said column-mixing step and said add-round-key step.

24. The system as recited in claim 19, wherein each of said plurality of pipeline stages is configured to concurrently process two columns of said cipher state.

25. The system as recited in claim 19, wherein each of said plurality of pipeline stages is configured to concurrently process one column of said cipher state.

26. The system as recited in claim 19, wherein said processor further comprises instruction fetch logic configured to issue a first instruction from one of a plurality of threads during one execution cycle and to issue a second instruction from another one of said plurality of threads during a successive execution cycle, and wherein said cryptographic unit is configured to execute independently of said instruction fetch logic.

27. The system as recited in claim 19, wherein said processor further comprises instruction fetch logic configured to issue a plurality of instructions including a first and a second instruction, wherein said first instruction is issued from one of a plurality of threads during one execution cycle, and wherein said second instruction is issued from another one of said plurality of threads during a successive execution cycle, and wherein said cryptographic unit is configured to execute one of said plurality of instructions issued by said instruction fetch logic.