Method and apparatus for efficiently implementing the advanced encryption standard
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 2 ) 4 ). Multiplicative inverse polynomial representations in GF((2 2 ) 4 ) are computed for each of the corresponding polynomial representations in GF((2 2 ) 4 ). Finally corresponding multiplicative inverse polynomial representations in GF((2 2 ) 4 ) 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 4 ) 2 ). A four-by-four matrix is applied to the transformed polynomial representation in GF((2 4 ) 2 ) to implement the inverse-columns-mixing.
1. An apparatus implementing an Advanced Encryption Standard (AES) S-box encryption process on a 128-bit block including a first 16 byte values each byte having a polynomial representation in GF(256), the apparatus comprising:
a polynomial-powers generating circuit to compute for each of the first 16 byte values, respectively, a plurality of second byte values having polynomial representations in GF(256) corresponding to a plurality of powers of the polynomial representation of their respective byte value of the first 16 byte values;
a multiplier circuit to multiply together in GF(256) the plurality of second byte values for each of the first 16 byte values, respectively, to produce a third 16 byte values each having a polynomial representation in GF(256) corresponding to the multiplicative inverse of their respective byte value of the first 16 byte values; and
an affine transform circuit to apply an affine transformation to the multiplicative inverses of the 16 byte values to generate, respectively, a fourth 16 byte values each having a polynomial representation in GF(256) wherein applying the affine transformation to generate a fourth 16 byte values having polynomial representation in GF(256) is performed by a multiplication of each corresponding multiplicative inverse polynomial representation with an 8-bit by 8-bit product matrix and a subsequent XOR with a constant byte value.
2. The apparatus of claim 1 wherein the multiplication of each corresponding multiplicative inverse polynomial representation with an 8-bit by 8-bit product matrix and a subsequent XOR with a constant byte value is implemented by a series of XORs.
3. An apparatus implementing an Advanced Encryption Standard (AES) decryption 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 4 ) 2 );
an inverse-columns-mixing circuit to compute an inverse-columns-mixing transformation in GF((2 4 ) 2 ) of the 16 byte values to get corresponding transformed polynomial representations in GF((2 4 ) 2 );
a second field conversion circuit to convert each corresponding transformed polynomial representation in GF((2 4 ) 2 ) and apply an inverse affine transformation to generate, respectively, a third corresponding polynomial representation in a finite field other than GF((2 4 ) 2 ); and
a multiplicative inverse circuit to compute for each of the third corresponding polynomial representations of the 16 byte values, respectively, a corresponding multiplicative inverse polynomial representation in said finite field other than GF GF((2 4 ) 2 ) wherein the first converting of each of the 16 byte values to a second corresponding polynomial representation in GF((24)2) is performed by a multiplication of each of the 16 byte values with an 8-bit by 8-bit conversion matrix.
4. The apparatus of claim 3 wherein the multiplication of each byte value with an 8-bit by 8-bit conversion matrix is implemented by a series of XORs.
5. The apparatus of claim 3 wherein the third corresponding polynomial representations of the 16 byte values are in GF(256), the multiplicative inverse circuit comprising:
a polynomial-powers generating circuit to compute for each of the third corresponding polynomial representations, respectively, a plurality of fourth byte values having polynomial representations in GF(256) corresponding to a plurality of powers of the third polynomial representation of their respective byte value;
a multiplier circuit to multiply together in GF(256) the plurality of fourth byte values for each of the third corresponding polynomial representations, respectively, to produce a fifth 16 byte values each having a polynomial representation in GF(256) corresponding to the multiplicative inverse of their respective byte value of the third corresponding polynomial representations.
6. The apparatus of claim 3 wherein the second converting of each corresponding multiplicative inverse polynomial representation and applying an affine transformation to generate a third corresponding polynomial representation in a finite field other than GF((2 4 ) 2 ) is performed by a multiplication of each corresponding multiplicative inverse polynomial representation with an 8-bit by 8-bit product matrix and an XOR with a constant byte value.
7. The apparatus of claim 6 wherein the multiplication of each corresponding multiplicative inverse polynomial representation with an 8-bit by 8-bit product matrix and a XOR with a constant byte value is implemented by a series of XORs.
8. The apparatus of claim 3 wherein the third corresponding polynomial representations of the 16 byte values are in GF((2 2 ) 4 ), the multiplicative inverse circuit comprising:
an inversion circuit to compute for each of the third corresponding polynomial representations in GF((2 2 ) 4 ) of the 16 byte values, respectively, a corresponding multiplicative inverse polynomial representation in GF((2 2 ) 4 ); and
a third field conversion circuit to convert each corresponding multiplicative inverse polynomial representation in GF((2 2 ) 4 ) to generate, respectively, a fourth corresponding polynomial representation in GF(256).
9. A method for implementing an Advanced Encryption Standard (AES) S-box encryption process on a 128-bit block including a first 16 byte values each byte having a polynomial representation in GF(256), the method comprising:
computing for each of the first 16 byte values, respectively, in a polynomial-powers generating circuit, a plurality of second byte values having polynomial representations in GF(256) corresponding to a plurality of powers of the polynomial representation of their respective byte value of the first 16 byte values;
producing a third 16 byte values, each having a polynomial representation in GF(256) corresponding to the multiplicative inverse of their respective byte value of the first 16 byte values, in a multiplier circuit by multiplying together in GF(256) the plurality of second byte values for each of the first 16 byte values, respectively; and
applying an affine transformation to the multiplicative inverses of the 16 byte values in an affine transform circuit to generate, respectively, a fourth 16 byte values each having a polynomial representation in GF(256) wherein applying the affine transformation to generate a fourth 16 byte values having polynomial representation in GF(256) is performed by a multiplication of each corresponding multiplicative inverse polynomial representation with an 8-bit by 8-bit product matrix and a subsequent XOR with a constant byte value.
10. The method of claim 9 wherein the multiplication of each corresponding multiplicative inverse polynomial representation with an 8-bit by 8-bit product matrix and a subsequent XOR with a constant byte value is implemented by a series of XORs.