Granted Patent B2

US 8,452,006 · App. 12/900,827 · Granted May 28, 2013

Abstract

Claims (356)

1. A cryptography processor comprising:

one or more arithmetic logic units (ALUs); and

a plurality of data registers, wherein the processor is adapted to:

receive an a-bit-long block of data, wherein the block of data is organized as a/n n-bit words;

store the a/n n-bit words as a state in the data registers, wherein the state is a matrix having b>1 rows and c>1 columns of p-bit state elements, wherein:

a, n, p, b, c, and a/n are positive integers;

p≧9;

p>n;

a/n>1;

each n-bit word of data is stored in a corresponding p-bit state element; and

b*c*n=a; and

perform a column-mixing transformation on the state using the one or more ALUs, wherein the column-mixing transformation involves generating finite-field products using bit-shifting and XOR operations.

2. The processor of claim 1 , wherein:

a is 128;

n is 8;

a/n is 16;

b is 4; and

c is 4.

3. The processor of claim 1 , wherein:

the processor is adapted to process the data block in a manner compatible with the Advanced Encryption Standard (AES); and

the processing comprises transforming the state over a plurality of rounds comprising an element-substitution transformation, a row-shifting transformation, a column-mixing transformation, and a round-key-adding transformation.

4. The processor of claim 3 , wherein:

the element-substitution transformation, ModSubBytes(k), is performed on an element k of the state, where k is a decimal representation of the value of the element, such that

ModSubBytes

⁡

(

k

)

=

{

SubBytes

⁡

(

k

)

for

⁢

⁢

0

≤

k

≤

255

SubBytes

⁡

(

k

⊕

283

)

for

⁢

⁢

256

≤

k

≤

511

;

SubBytes(k) represents the AES SubBytes( ) transformation for k; and

⊕ is an XOR operator.

5. The processor of claim 4 , wherein:

the processor is adapted to perform a ModSubBytesShiftRows( ) transformation, which combines the row-shifting and element-substitution transformations, on elements of the state;

ModSubBytesShiftRows(s i,j )=ModSubBytes(s i,j+i(mod 4) );

s i,j represents the value of the state element at row i and column j; and

mod represents modulo reduction.

6. The processor of claim 3 , wherein the row-shifting transformation ModShiftRows( ) circularly shifts each row of the state by d*p bits, wherein d is a non-negative integer.

7. The processor of claim 3 , wherein:

the four elements of column j of the state are represented as s 0,j , . . . , s 3,j ;

Shift(w) performs a 1-bit left shift on operand w;

the column-mixing transformation ModMixColumns( ) is performed after the element-substitution transformation of the round; and

the operations of the ModMixColumns( ) transformation for the elements of column j of the state are:

ModMixColumns( s 0,j )=Shift( s 0,j ⊕s 1,j )⊕ s 1,j ⊕s 2,j ⊕s 3,j ;

ModMixColumns( s 1,j )=Shift( s 1,j ⊕s 2,j )⊕ s 2,j ⊕s 3,j ⊕s 0,j ;

ModMixColumns( s 2,j )=Shift( s 2,j ⊕s 3,j )⊕ s 3,j ⊕s 0,j ⊕s 1,j ; and

ModMixColumns( s 3,j )=Shift( s 3,j ⊕s 0,j )⊕ s 0,j ⊕s 1,j ⊕s 2,j .

8. The processor of claim 3 , wherein:

b=c=4;

Shift(w) performs a 1-bit left shift on operand w;

rows 0, 1, 2, and 3 of the state are stored as sd 0 , sd 1 , sd 2 , and sd 3 , respectively, on four corresponding data registers of the plurality of data registers;

the operations of column-mixing transformation ModMixColumns( ) for the rows of the state are:

ModMixColumns( sd 0 )=Shift( sd 0 ⊕sd 1 )⊕ sd 1 ⊕sd 2 ⊕sd 3 ;

ModMixColumns( sd 1 )=Shift( sd 1 ⊕sd 2 )⊕ sd 2 ⊕sd 3 ⊕sd 0 ;

ModMixColumns( sd 2 )=Shift( sd 2 ⊕sd 3 )⊕ sd 3 ⊕sd 0 ⊕sd 1 ; and

ModMixColumns( sd 3 )=Shift( sd 0 ⊕sd 1 )⊕ sd 1 ⊕sd 2 ⊕sd 3 .

9. The processor of claim 3 , wherein:

the processor is adapted to:

combine the performance of the column-mixing and the round-key-adding transformations; and

generate an AES-expanded key schedule from a key corresponding to the data block, the expanded key schedule comprising expanded-key-schedule elements corresponding to elements of the state for particular rounds of processing;

b=c=4;

i is a non-negative integer;

Shift(w) performs a 1-bit left shift on operand w;

rows 0, 1, 2, and 3 of the state are stored as sd 0 , sd 1 , sd 2 , and sd 3 , respectively, on four corresponding data registers of the plurality of data registers;

the four elements of the expanded key schedule corresponding to row i of the state for a particular round are stored together in one of the plurality of data registers as kd i ;

kd i for round r, where r is a non-negative integer, is equivalent to the concatenation of prefix-padded bytes of the AES-expanded key schedule, namely key[16r+i], key[16r+4+i], key[16r+8+i], and key[16r+12+i];

key[n] refers to the nth byte of the AES-expanded key schedule; and

performing the combined column-mixing and round-key-adding transformation of the state for the particular round yields four new rows, new_sd 0 , . . . , new_sd 3 , wherein:

new — sd 0 =Shift( sd 0 ⊕sd 1 )⊕ sd 1 ⊕sd 2 ⊕sd 3 ⊕kd 0 ;

new — sd 1 =Shift( sd 1 ⊕sd 2 )⊕ sd 2 ⊕sd 3 ⊕sd 0 ⊕kd 1 ;

new — sd 2 =Shift( sd 2 ⊕sd 3 )⊕ sd 3 ⊕sd 0 ⊕sd 1 ⊕kd 2 ; and

new_sd 3 =Shift( sd 0 ⊕sd 1 )⊕ sd 1 ⊕sd 2 ⊕sd 3 ⊕kd 3 .

10. The processor of claim 3 , wherein:

the processor is adapted to:

generate an AES-expanded key schedule, key[ ], from a key corresponding to the data block, the expanded key schedule comprising expanded-key-schedule elements corresponding to elements of the state for particular rounds of processing; and

generate a 320-byte expanded key schedule, new_key[ ], from key[ ] using the following procedure, where temp1 and temp2 are temporary variables, vectode[e . . . f] refers to bytes e through f of array vector, and d∥0 g means suffix-padding g zeroes to d:

new_key[k] = key[k] for k = 0 .. 15;

new_key[k] = key[k − 72] for k = 232 .. 247; and

for r = 1 to 9

 {

 temp1 = key[16r] ⊕ (key[16r + 4] ||0 9 )

 temp2 = key[16r + 8] ⊕ (key[16r + 12] ||0 9 )

 new_key[24r + 4 .. 24r + 7] = temp1[0 .. 3]

 new_key[24r .. 24r + 3] = temp2[0 .. 3]

 temp1 = key[16r + 1] ⊕ (key[16r + 5] ||0 9 )

 temp2 = key[16r + 9] ⊕ (key[16r + 13] ||0 9 )

 new_key[24r − 8 .. 24r − 5] = temp1[0 .. 3]

 new_key[24r − 4 .. 24r − 1] = temp2[0 .. 3]

 temp1 = key[16r + 2] ⊕ (key[16r + 6] ||0 9 )

 temp2 = key[16r + 10] ⊕ (key[16r + 14] ||0 9 )

 new_key[8r + 240 .. 8r + 243] = temp1[0 .. 3]

 new_key[8r + 244 .. 8r + 247] = temp2[0 .. 3]

 temp1 = key[16r + 3] ⊕ (key[16r + 7] ||0 9 )

 temp2 = key[16r + 11] ⊕ (key[16r + 15] ||0 9 )

 new_key[24r + 8 .. 24r + 11] = temp1[0 .. 3]

 new_key[24r + 12 .. 24r + 15] = temp2[0 .. 3]

 }; and

using new_key[ ] instead of key[ ] for performing the round-key-adding transformations of the rounds.

11. The processor of claim 10 , wherein:

the key corresponding to the data block is 128-bits long;

i is a non-negative integer;

the four elements of new − key[ ] corresponding to row i in a particular transformation round are stored together as kd i in one of the plurality of data registers;

for the initial round, kd i =new_key[4i . . . 4 i +3];

for rounds 1 through 9, kd i =key1(r,i)⊕(key2(r,i)<<18), where key1(r,i) and key2(r,i) for round r and row i are obtained as follows:

key1( r, 0)=new_key[24 *r+ 4 . . . 24 *r+ 7];

key2( r, 0)=new_key[24 *r . . . 24* r+ 3];

key1( r, 1)=new_key[24 *r− 8 . . . 24 *r− 5];

key2( r, 1)=new_key[24 *r− 4 . . . 24 *r− 1];

key1( r, 2)=new_key[8 *r+ 240 . . . 8 *r+ 243];

key2( r, 2)=new_key[8 *r+ 244 . . . 8 *r+ 247];

key1( r, 3)=new_key[24 *r+ 8 . . . 24 *r+ 11]; and

key2( r, 3)=new_key[24 *r+ 12 . . . 24 *r+ 15]; and

for round 11, kd i =new_key[232+4i . . . 4i+235].

12. The processor of claim 11 , wherein, the processor is adapted to perform each of the key-adding transformations for rounds 1 through 9 using no more than four read operations and eight XOR operations.

13. The processor of claim 3 , wherein:

b=c=4;

i and r are non-negative integers;

rows 0, 1, 2, and 3 of the state are stored as sd 0 , sd 1 , sd 2 , and sd 3 , respectively, on four corresponding data registers of the plurality of data registers;

the four elements of the expanded key schedule corresponding to row i of the state for a particular round are stored together in one of the plurality of data registers as kd i ;

the content of a work register, which is one of the plurality of data registers, is stored as wd; and

the processor is adapted to:

generate an AES-expanded key schedule from a key corresponding to the data block, the expanded key schedule key[ ] comprising expanded-key-schedule elements corresponding to elements of the state for particular rounds of processing; and

populate the data register storing kd i by performing:

setting kd i to key[16r+i];

left-shifting kd i by 3*p bits;

setting wd to key[16r+4+i];

left-shifting wd by 2*p bits;

setting kd i to wd⊕kd i ;

setting wd to key[16r+8+i];

left-shifting wd by p bits;

setting kd i to wd⊕kd i ;

setting wd to key[16r+12+i]; and

setting kd i to wd⊕kd i .

14. The processor of claim 3 , wherein:

b=c=4;

i is a non-negative integer;

rows 0, 1, 2, and 3 of the state are stored as sd 0 , sd 1 , sd 2 , and sd 3 , respectively, on four corresponding data registers of the plurality of data registers;

the four elements of the expanded key schedule corresponding to row i of the state for a particular round are stored together in one of the plurality of data registers as kd i ;

the processor is adapted to perform the column-mixing and round-key-adding transformations in combination to generate transformed rows of the state referred to as new_sd 0 , new_sd 1 , new_sd 2 , and new_sd 3 , respectively, by performing:

for row 0:

M 0 =2 *sd 0 ;

t 1 (0) =sd 1 ⊕kd 0 ;

t 2 (0) =t 1 (0) ⊕M 0 ;

t 3 (0) =t 2 (0) ⊕M 1 ;

t 4 (0) =t 3 (0) ⊕sd 2 ; and

new — sd 0 =t 4 (0) ⊕sd 3 ;

for row 1:

M 1 =2 *sd 1 ;

t 1 (1) =sd 0 ⊕kd 1 ;

t 2 (1) =t 1 (1) ⊕M 1 ;

t 3 (1) =t 2 (1) ⊕sd 2 ;

t 4 (1) =t 3 (1) ⊕M 2 ; and

new — sd 1 =t 4 (0) ⊕sd 3 ;

for row 2:

M 2 =2 *sd 2 ;

t 1 (2) =kd 2 ⊕sd 0 ;

t 2 (2) =t 1 (2) ⊕sd 1 ;

t 3 (2) =t 2 (2) ⊕sd 3 ;

t 4 (2) =t 3 (2) ⊕M 3 ; and

new — sd 2 =t 4 (0) ⊕M 2 ; and

for row 3:

M 3 =2 *sd 3

t 1 (3) =sd 0 ⊕sd 1 ;

t 2 (3) =t 1 (3) ⊕M 0 ;

t 3 (3) =t 2 (3) ⊕sd 2 ;

t 4 (3) =t 3 (3) ⊕kd 3 ; and

new_sd 3 =t 4 (0) ⊕M 3 , wherein M x and t x (y) all represent temporary-data registers of the plurality of data registers for storing temporary values.

15. The processor of claim 14 , wherein multiplications by 2 are performed using one-bit left-shifts.

16. The processor of claim 3 , wherein the processor is adapted to perform the byte-substitution and row-shifting transformation for a round over 22 clock cycles by performing:

in the first clock cycle: E 2 and C 1 ;

in the second clock cycle: E 3 , C 2 , and U 1 ;

in the third clock cycle: E 4 , C 3 , and U 2 ;

in the fourth clock cycle: E 5 , C 4 , and U 3 ;

in the fifth clock cycle: E 6 , C 5 , and U 4 ;

in the sixth clock cycle: E 7 , C 6 , U 5 , and R 1 ;

in the seventh clock cycle: E 8 , C 7 , I 1 , U 6 , and R 2 ;

in the eighth clock cycle: E 9 , C 8 , I 2 , U 7 , and R 3 ;

in the ninth clock cycle: E 10 , C 9 , I 3 , U 8 , and R 4 ;

in the tenth clock cycle: E 11 , C 10 , I 4 , U 9 , and R 5 ;

in the eleventh clock cycle: E 12 , C 11 , I 5 , U 10 , and R 6 ;

in the twelfth clock cycle: E 13 , C 12 , I 6 , U 11 , and R 7 ;

in the thirteenth clock cycle: E 14 , C 13 , I 7 , U 12 , and R 8 ;

in the fourteenth clock cycle: E 15 , C 14 , I 8 , U 13 , and R 9 ;

in the fifteenth clock cycle: E 16 , C 15 , I 9 , U 14 , and R 10 ;

in the sixteenth clock cycle: C 16 , I 10 , U 15 , and R 11 ;

in the seventeenth clock cycle: I 11 , U 16 , and R 12 ;

in the eighteenth clock cycle: I 12 and R 13 ;

in the nineteenth clock cycle: I 13 and R 14 ;

in the twentieth clock cycle: I 14 and R 15 ;

in the twenty-first clock cycle: I 15 and R 16 ; and

in the twenty-second clock cycle: E 1 and I 16 , wherein:

b=c=4;

m is an non-negative integer;

1≦m≦16;

the processor comprises an address-generation unit (AGU);

Em represents an ALU-performed extraction operation for element m of the state;

Cm represents an ALU-performed calculation operation for that element m of the state;

Um represents an AGU-performed uploading operation for that element m of the state;

Rm represents an AGU-performed reading operation for that element m of the state;

Im represents an ALU-performed insertion operation for that element m of the state; and

the E 1 operation in the twenty-second clock cycle is performed for the subsequent round.

17. The processor of claim 3 , wherein the processor is adapted to perform the byte-substitution and row-shifting transformation for a round over 22 clock cycles by performing:

in the first clock cycle: E 3 , C 2 and U 1 ;

in the second clock cycle: E 4 , C 3 , E 5 , RK 2 , and RK 1 ;

in the third clock cycle: E 6 , C 4 , U 2 , and RK 3 ;

in the fourth clock cycle: E 7 , C 5 , U 3 , and RK 4 ;

in the fifth clock cycle: C 1 , C 6 , CK 1 , and U 4 ;

in the sixth clock cycle: E 8 , C 7 , CK 2 , E 10 , U 5 , and R 1 +I 1 ;

in the seventh clock cycle: E 9 , C 8 , U 6 , and R 2 ;

in the eighth clock cycle: E 12 , C 9 , I 2 , U 7 , and R 3 ;

in the ninth clock cycle: Ell, C 10 , CK 3 , I 3 , U 8 , and R 4 ;

in the tenth clock cycle: E 16 , C 11 , CK 4 , I 4 , U 9 , and R 5 ;

in the eleventh clock cycle: E 13 , C 12 , CK 5 , I 5 , U 10 , R 6 ;

in the twelfth clock cycle: E 14 , C 13 , E 15 , I 6 , U 11 , and R 7 ;

in the thirteenth clock cycle: C 14 , I 7 , U 12 , and R 8 ;

in the fourteenth clock cycle: C 15 , I 8 , U 13 , and R 9 +I 9 ;

in the fifteenth clock cycle: C 16 , U 14 , and R 10 ;

in the sixteenth clock cycle: I 10 , U 15 , and R 11 ;

in the seventeenth clock cycle: I 11 , U 16 , and R 12 ;

in the eighteenth clock cycle: I 12 , RK 5 , and R 13 ;

in the nineteenth clock cycle: I 13 and R 14 ;

in the twentieth clock cycle: CK 6 , I 14 , and R 15 ;

in the twenty-first clock cycle: E 1 , I 15 , and R 16 ; and

in the twenty-second clock cycle: E 2 and I 16 , wherein:

the processor comprises an address-generation unit (AGU);

b=c=4;

m and h are non-negative integers;

1≦m≦16;

Em represents an ALU-performed extraction operation for element m of the state;

Cm represents an ALU-performed calculation operation for that element m of the state;

Um represents an AGU-performed uploading operation for that element m of the state;

Rm represents an AGU-performed reading operation for that element m of the state;

Im represents an ALU-performed insertion operation for that element m of the state;

Rm+Im represents an AGU-performed combined reading and insertion operation for that element m of the state;

RKh represents an AGU-performed read-key operation for reading key values from an expanded key schedule;

CKh represents an ALU-performed combine-copy operation for combining key values from the expanded key schedule;

the E 1 operation in the twenty-first clock cycle and the E 2 operation in the twenty-second clock cycle are performed for the subsequent round.

18. A method for a cryptography processor comprising one or more arithmetic logic units (ALUs) and a plurality of data registers, the method comprising:

receiving an a-bit-long block of data, wherein the block of data is organized as a/n n-bit words;

storing the a/n n-bit words as a state in the data registers, wherein the state is a matrix having b>1 rows and c>1 columns of p-bit state elements, wherein:

a, n, p, b, c, and a/n are positive integers;

p≧9;

p>n;

a/n>1;

each n-bit word of data is stored in a corresponding p-bit state element; and

b*c*n=a; and

performing a column-mixing transformation on the state using the one or more ALUs, wherein the column-mixing transformation involves generating finite-field products using bit-shifting and XOR operations.

19. The method of claim 18 , wherein:

a is 128;

n is 8;

a/n is 16;

b is 4; and

c is 4.

20. The method of claim 18 , wherein:

the processor is processes the data block in a manner compatible with the Advanced Encryption Standard (AES); and

the processing comprises transforming the state over a plurality of rounds comprising an element-substitution transformation, a row-shifting transformation, a column-mixing transformation, and a round-key-adding transformation.

21. A cryptography processor comprising:

one or more arithmetic logic units (ALUs); and

a plurality of data registers, wherein the processor is adapted to:

receive an a-bit-long block of data, wherein the block of data is organized as a/n n-bit words;

store the a/n n-bit words as a state in the data registers, wherein the state is a matrix having b>1 rows and c>1 columns of p-bit state elements, wherein:

a, n, p, b, c, and a/n are positive integers;

p>n;

a/n>1;

each n-bit word of data is stored in a corresponding p-bit state element; and

b*c*n=a;

perform a column-mixing transformation on the state using the one or more ALUs, wherein the column-mixing transformation involves generating finite-field products using bit-shifting and XOR operations; and

process the data block in a manner compatible with the Advanced Encryption Standard (AES), wherein:

the processing comprises transforming the state over a plurality of rounds comprising an element-substitution transformation, a row-shifting transformation, a column-mixing transformation, and a round-key-adding transformation

the element-substitution transformation, ModSubBytes(k), is performed on an element k of the state, where k is a decimal representation of the value of the element, such that

ModSubBytes

⁡

(

k

)

=

{

SubBytes

⁡

(

k

)

for

⁢

⁢

0

≤

k

≤

255

SubBytes

⁡

(

k

⊕

283

)

for

⁢

⁢

256

≤

k

≤

511

;

SubBytes(k) represents the AES SubBytes( ) transformation for k; and

⊕ is an XOR operator.

22. The processor of claim 21 , wherein:

the processor is adapted to perform a ModSubBytesShiftRows( ) transformation, which combines the row-shifting and element-substitution transformations, on elements of the state;

ModSubBytesShiftRows( s i,j )=ModSubBytes( s i,j+i(mod 4) );

s i,j represents the value of the state element at row i and column j; and

mod represents modulo reduction.

23. A cryptography processor comprising:

one or more arithmetic logic units (ALUs); and

a plurality of data registers, wherein the processor is adapted to:

receive an a-bit-long block of data, wherein the block of data is organized as a/n n-bit words;

store the a/n n-bit words as a state in the data registers, wherein the state is a matrix having b>1 rows and c>1 columns of p-bit state elements, wherein:

a, n, p, b, c, and a/n are positive integers;

p>n;

a/n>1;

each n-bit word of data is stored in a corresponding p-bit state element; and

b*c*n=a;

perform a column-mixing transformation on the state using the one or more ALUs, wherein the column-mixing transformation involves generating finite-field products using bit-shifting and XOR operations; and

process the data block in a manner compatible with the Advanced Encryption Standard (AES), wherein:

the processing comprises transforming the state over a plurality of rounds comprising an element-substitution transformation, a row-shifting transformation, a column-mixing transformation, and a round-key-adding transformation; and

the row-shifting transformation ModShiftRows( ) circularly shifts each row of the state by d*p bits, wherein d is a non-negative integer.

Assignments (8)