Method and apparatus for efficiently implementing the advanced encryption standard

• US 10,050,778 B2
• Filed: 12/12/2014
• Issued: 08/14/2018
• Est. Priority Date: 12/28/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kounavis, Michael E., Gueron, Shay, Krishnamurthy, Ram, Mathew, Sanu K.
• Primary Examiner(s): Rashid, Harunur
• Application Number:
  US14/569,428
• Publication Number:
  US 20170195116A1
• Time in Patent Office: 1,341 Days
• Field of Search: 380 28, 380 29
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06F 9/30007 to perform operations on data operands
• CPC Class Codes: G06F 9/30112 comprising data of variable length
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/30149 of variable length instructions
• CPC Class Codes: G06F 9/30196 using decoder, e.g. decoder per instruction set, adaptable or programmable decoders
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms

Abstract

Implementations of Advanced Encryption Standard (AES) encryption and decryption processes are disclosed. In one embodiment of S-box processing, a block of 16 byte values is converted, each byte value being converted from a polynomial representation in GF(256) to a polynomial representation in GF((2²)⁴). Multiplicative inverse polynomial representations in GF((2²)⁴) are computed for each of the corresponding polynomial representations in GF((2²)⁴). Finally corresponding multiplicative inverse polynomial representations in GF((2²)⁴) are converted and an affine transformation is applied to generate corresponding polynomial representations in GF(256). In an alternative embodiment of S-box processing, powers of the polynomial representations are computed and multiplied together in GF(256) to generate multiplicative inverse polynomial representations in GF(256). In an embodiment of inverse-columns-mixing, the 16 byte values are converted from a polynomial representation in GF(256) to a polynomial representation in GF((2⁴)²). A four-by-four matrix is applied to the transformed polynomial representation in GF((2⁴)²) to implement the inverse-columns-mixing.

Claims

1. An apparatus implementing an Advanced Encryption Standard (AES) S-box encryption process on a 128-bit block including 16 byte values, the apparatus comprising:

a first field conversion circuit to convert each of the 16 byte values, respectively, from a first corresponding polynomial representation in GF(256) to a second corresponding polynomial representation in GF((2²)⁴);

a multiplicative inverse circuit to compute for each of the second corresponding polynomial representations in GF((2²)⁴) of the 16 byte values, respectively, a corresponding multiplicative inverse polynomial representation in GF((2²)⁴); and

a second field conversion circuit to convert each corresponding multiplicative inverse polynomial representation in GF((2²)⁴) and to apply an affine transformation to generate, respectively, a third corresponding polynomial representation in GF(256), wherein the conversion, in the second field conversion circuit, of each corresponding multiplicative inverse polynomial representation in GF((2²)⁴) and application of the affine transformation is performed by multiplication of each byte value with an 8-bit by 8-bit matrix and XORs with a set of constants according to;

b₀=a₀⊕

a₁⊕

a₂,

b₁=a₀⊕

a₃⊕

a₅,

b₂=a₀⊕

a₂⊕

a₆,

b₃=a₀⊕

a₁ ⊕

a₃ ⊕

a₄⊕

a₅,

b₄=a₀⊕

a₁ ⊕

a₄ ⊕

a₅⊕

a₇,

b₅=a₄,

b₆=a ₃⊕

a₆,

b₇=a₂⊕

a₃,

where [a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀] is the multiplicative inverse polynomial representation in GF((2²)⁴) and [b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀] is the third corresponding polynomial representation in GF(256).

2. The apparatus of claim 1 wherein converting each of the 16 byte values to a second corresponding polynomial representation in GF((2²)⁴) is performed by a multiplication of each of the 16 byte values with an 8-bit by 8-bit conversion matrix.

3. The apparatus of claim 2 wherein the multiplication of each byte value with an 8-bit by 8-bit conversion matrix is implemented by a series of XORs according to:

b₀=a₀⊕

a₁⊕

a₆,

b₁=a₁⊕

a₄⊕

a₆,

b₂=a₅⊕

a₆⊕

a₇,

b₃=a₃⊕

a₄,

b₄=a₁⊕

a₂⊕

a₃⊕

a₄⊕

a₅,

b₅=a₃⊕

a₄⊕

a₅ ⊕

a₇,

b₆=a₂⊕

a₅⊕

a₆,

b₇=a₃⊕

a₇,

where [a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀] is the first corresponding polynomial representation in GF(256) and [b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀] is the second corresponding polynomial representation in GF((2²)⁴).

4. A method comprising:

converting, in a first field conversion circuit, each of a plurality of 16 byte values of a block, respectively, from a first corresponding polynomial representation in GF(256) to a second corresponding polynomial representation in GF((2²)⁴);

computing, in a multiplicative inverse circuit, for each of the second corresponding polynomial representations in GF((2²)⁴) of the 16 byte values, respectively, a corresponding multiplicative inverse polynomial representation in GF((2²)⁴);

converting, in a second field conversion circuit, each corresponding multiplicative inverse polynomial representation in GF((2²)⁴) and applying an affine transformation to generate, respectively, a third corresponding polynomial representation in GF(256), wherein the conversing, in the second field conversion circuit, each corresponding multiplicative inverse polynomial representation in GF((2²)⁴) and applying the affine transformation is performed by multiplication of each byte value with an 8-bit by 8-bit matrix and XORs with a set of constants according to;

b₀=a₀⊕

a₁⊕

a₂,

b₁=a₀⊕

a₃⊕

a₅,

b₂=a₀⊕

a₂⊕

a₆,

b₃=a₀⊕

a₁⊕

a₃⊕

a₄ ⊕

a₅,

b₄=a₀⊕

a₁⊕

a₄⊕

a₅⊕

a₇,

b₅=a₄,

b₆=a₃⊕

a₆,

b₇=a₂⊕

a₃,

where [a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀] is the multiplicative inverse polynomial representation in GF((2²)⁴) and [b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀] is the third corresponding polynomial representation in GF(256).

5. The method of claim 4 wherein converting each of the 16 byte values to a second corresponding polynomial representation in GF((2²)⁴) is performed by a multiplication of each of the 16 byte values with an 8-bit by 8-bit conversion matrix.

6. The method of claim 5, further comprising multiplying each byte value with the 8-bit by 8-bit conversion matrix according to:

b₀=a₀⊕

a₁⊕

a₆,

b₁=a₁⊕

a₄⊕

a₆,

b₂=a₅⊕

a₆⊕

a₇,

b₃=a₃⊕

a₄,

b₄=a₁⊕

a₂⊕

a₃⊕

a₄⊕

a₅,

b₅=a₃⊕

a₄⊕

a₅⊕

a₇,

b₆=a₂⊕

a₅⊕

a₆,

b₇=a₃⊕

a₇,

where [a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀] is the first corresponding polynomial representation in GF(256) and [b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀] is the second corresponding polynomial representation in GF((2²)⁴).

7. An apparatus implementing an Advanced Encryption Standard (AES) S-box encryption process on a 128-bit block including 16 byte values, the apparatus comprising:

a first field conversion circuit to convert each of the 16 byte values, respectively, from a first corresponding polynomial representation in GF(256) to a second corresponding polynomial representation in GF((2²)⁴), wherein converting each of the 16 byte values to a second corresponding polynomial representation in GF((2²)⁴) is performed by a multiplication of each of the 16 byte values with an 8-bit by 8-bit conversion matrix and the multiplication of each byte value with an 8-bit by 8-bit conversion matrix is implemented by a series of XORs according to;

b₀=a₀⊕

a₁⊕

a₆,

b₁=a₁⊕

a₄⊕

a₆,

b₂=a₅⊕

a₆⊕

a₇,

b₃=a₃⊕

a₄,

b₄=a₁⊕

a₂⊕

a₃⊕

a₄⊕

a₅,

b₅=a₃⊕

a₄⊕

a₅⊕

a₇,

b₆=a₂⊕

a₅⊕

a₆,

b₇=a₃⊕

a₇,

where [a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀] is the first corresponding polynomial representation in GF(256) and [b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀] is the second corresponding polynomial representation in GF((2²)⁴);

a multiplicative inverse circuit to compute for each of the second corresponding polynomial representations in GF((2²)⁴) of the 16 byte values, respectively, a corresponding multiplicative inverse polynomial representation in GF((2²)⁴); and

a second field conversion circuit to convert each corresponding multiplicative inverse polynomial representation in GF((2²)⁴) and to apply an affine transformation to generate, respectively, a third corresponding polynomial representation in GF(256).

8. A method comprising:

converting, in a first field conversion circuit, each of a plurality of 16 byte values of a block, respectively, from a first corresponding polynomial representation in GF(256) to a second corresponding polynomial representation in GF((2²)⁴), wherein converting each of the 16 byte values to a second corresponding polynomial representation in GF((2²)⁴) is performed by a multiplication of each of the 16 byte values with an 8-bit by 8-bit conversion matrix and multiplying each byte value with the 8-bit by 8-bit conversion matrix according to;

b₀=a₀⊕

a₁⊕

a₆,

b₁=a₁⊕

a₄⊕

a₆,

b₂=a₅⊕

a₆⊕

a₇,

b₃=a₃⊕

a₄,

b₄=a₁⊕

a₂⊕

a₃⊕

a₄⊕

a₅,

b₅=a₃⊕

a₄⊕

a₅⊕

a₇,

b₆=a₂⊕

a₅⊕

a₆,

b₇=a₃⊕

a₇,

where [a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀] is the first corresponding polynomial representation in GF(256) and [b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀] is the second corresponding polynomial representation in GF((2²)⁴);

computing, in a multiplicative inverse circuit, for each of the second corresponding polynomial representations in GF((2²)⁴) of the 16 byte values, respectively, a corresponding multiplicative inverse polynomial representation in GF((2²)⁴);

converting, in a second field conversion circuit, each corresponding multiplicative inverse polynomial representation in GF((2²)⁴) and applying an affine transformation to generate, respectively, a third corresponding polynomial representation in GF(256).