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 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 2 ) 4 );
a multiplicative inverse circuit to compute for each of the second 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 second field conversion circuit to convert each corresponding multiplicative inverse polynomial representation in GF((2 2 ) 4 ) 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 2 ) 4 ) 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 0 =a 0 ⊕a 1 ⊕a 2 ,
b 1 =a 0 ⊕a 3 ⊕a 5 ,
b 2 =a 0 ⊕a 2 ⊕a 6 ,
b 3 =a 0 ⊕a 1 ⊕a 3 ⊕a 4 ⊕a 5 ,
b 4 =a 0 ⊕a 1 ⊕a 4 ⊕a 5 ⊕a 7 ,
b 5 =a 4 ,
b 6 =a 3 ⊕a 6 ,
b 7 =a 2 ⊕a 3 ,
where [a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ] is the multiplicative inverse polynomial representation in GF((2 2 ) 4 ) and [b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ] 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 2 ) 4 ) 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 0 =a 0 ⊕a 1 ⊕a 6 ,
b 1 =a 1 ⊕a 4 ⊕a 6 ,
b 2 =a 5 ⊕a 6 ⊕a 7 ,
b 3 =a 3 ⊕a 4 ,
b 4 =a 1 ⊕a 2 ⊕a 3 ⊕a 4 ⊕a 5 ,
b 5 =a 3 ⊕a 4 ⊕a 5 ⊕a 7 ,
b 6 =a 2 ⊕a 5 ⊕a 6 ,
b 7 =a 3 ⊕a 7 ,
where [a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ] is the first corresponding polynomial representation in GF(256) and [b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ] is the second corresponding polynomial representation in GF((2 2 ) 4 ).
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 2 ) 4 );
computing, in a multiplicative inverse circuit, for each of the second 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 );
converting, in a second field conversion circuit, each corresponding multiplicative inverse polynomial representation in GF((2 2 ) 4 ) 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 2 ) 4 ) 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 0 =a 0 ⊕a 1 ⊕a 2 ,
b 1 =a 0 ⊕a 3 ⊕a 5 ,
b 2 =a 0 ⊕a 2 ⊕a 6 ,
b 3 =a 0 ⊕a 1 ⊕a 3 ⊕a 4 ⊕a 5 ,
b 4 =a 0 ⊕a 1 ⊕a 4 ⊕a 5 ⊕a 7 ,
b 5 =a 4 ,
b 6 =a 3 ⊕a 6 ,
b 7 =a 2 ⊕a 3 ,
where [a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ] is the multiplicative inverse polynomial representation in GF((2 2 ) 4 ) and [b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ] 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 2 ) 4 ) 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 0 =a 0 ⊕a 1 ⊕a 6 ,
b 1 =a 1 ⊕a 4 ⊕a 6 ,
b 2 =a 5 ⊕a 6 ⊕a 7 ,
b 3 =a 3 ⊕a 4 ,
b 4 =a 1 ⊕a 2 ⊕a 3 ⊕a 4 ⊕a 5 ,
b 5 =a 3 ⊕a 4 ⊕a 5 ⊕a 7 ,
b 6 =a 2 ⊕a 5 ⊕a 6 ,
b 7 =a 3 ⊕a 7 ,
where [a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ] is the first corresponding polynomial representation in GF(256) and [b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ] is the second corresponding polynomial representation in GF((2 2 ) 4 ).
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 2 ) 4 ), wherein converting each of the 16 byte values to a second corresponding polynomial representation in GF((2 2 ) 4 ) 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 0 =a 0 ⊕a 1 ⊕a 6 ,
b 1 =a 1 ⊕a 4 ⊕a 6 ,
b 2 =a 5 ⊕a 6 ⊕a 7 ,
b 3 =a 3 ⊕a 4 ,
b 4 =a 1 ⊕a 2 ⊕a 3 ⊕a 4 ⊕a 5 ,
b 5 =a 3 ⊕a 4 ⊕a 5 ⊕a 7 ,
b 6 =a 2 ⊕a 5 ⊕a 6 ,
b 7 =a 3 ⊕a 7 ,
where [a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ] is the first corresponding polynomial representation in GF(256) and [b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ] is the second corresponding polynomial representation in GF((2 2 ) 4 );
a multiplicative inverse circuit to compute for each of the second 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 second field conversion circuit to convert each corresponding multiplicative inverse polynomial representation in GF((2 2 ) 4 ) 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 2 ) 4 ), wherein converting each of the 16 byte values to a second corresponding polynomial representation in GF((2 2 ) 4 ) 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 0 =a 0 ⊕a 1 ⊕a 6 ,
b 1 =a 1 ⊕a 4 ⊕a 6 ,
b 2 =a 5 ⊕a 6 ⊕a 7 ,
b 3 =a 3 ⊕a 4 ,
b 4 =a 1 ⊕a 2 ⊕a 3 ⊕a 4 ⊕a 5 ,
b 5 =a 3 ⊕a 4 ⊕a 5 ⊕a 7 ,
b 6 =a 2 ⊕a 5 ⊕a 6 ,
b 7 =a 3 ⊕a 7 ,
where [a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ] is the first corresponding polynomial representation in GF(256) and [b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ] is the second corresponding polynomial representation in GF((2 2 ) 4 );
computing, in a multiplicative inverse circuit, for each of the second 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 );
converting, in a second field conversion circuit, each corresponding multiplicative inverse polynomial representation in GF((2 2 ) 4 ) and applying an affine transformation to generate, respectively, a third corresponding polynomial representation in GF(256).