ñòð. 29 |

+ +2

7500a302 = ( 7 5 ) ˜ ˜

(a3)y

(here we use the indeterminate y just to avoid confusion between word-

polynomials and defined above byte-polynomials). The arithmetic of these

word-polynomials is more complicated but we need not go into details. Now

we are ready to describe the Ftijndael transformations.

The transformation SubBytes(Y) is applied independently to each byte

b in block Y:

b-l(z) mod m ( z ) (0 t 0) ,

b(z) t

+

b(z) t ((z7+ z6+z5+z4+l)b(z) (z7+ z6+z2+ z)) mod (z8+ 1).

The results of this transformation computed for each byte from 0 to 255

beforehand, are stored in the table S (this is an S-box). Then the trans-

formation SubBytes(Y) is reduced to performing for each byte b in Y the

operation

S[b].

b +-

The content of table S is explicitly given in [Daemen and Rijmen (2002)].

The transformation ShiftRows(Y) acts upon each row ri in block Y,

i.e. upon the sequence of ith bytes of block words (i = 0,1,2,3). The op-

eration involved is the cyclic shift left a specified number of bytes, denoted

by e. The rule of the transformation is

i = 0,1,2,3.

(ri c, i),

ri t

For example, show the contents of the block before and after ShiftRows

transformation:

Y ShiftRows(Y)

03 02 01 00 03 02 01 00

13 12 11 10 12 11 10 13

23 22 21 20 21 20 23 22

33 32 31 30 30 33 32 31

The transformation MixColumns(Y) acts upon each column ci in block

Y , i.e. upon each machine word, i = 0,1,2,3, by the rule

+ 1)

a ( y ) . Ci(Y) mod (Y4

Ci(Y)

Modern Secret Key Ciphers 153

+ y2 + y + 2.

where a ( y ) = 3y3 This operation can be written in a matrix

form

Here all "elementary" operations are performed on binary polynomials

modulo m(z).

It is obvious that operation SubBytes can be swapped with ShiftRows

without affecting the result since these transformations act upon individual

bytes. Using the distributivity of polynomial multiplication we can write

MixColumns(Y @ Wi) = MixColumns(Y) @ MixColumns(Wi)

So, Mixcolumns transformation and the key addition can also be swapped

under the condition that the corresponding blocks of the round key (ex-

cept the first and last) were subjected to the inverse transformation

MixColumns-'( Wi). All these proves the identity of operation sequences

(8.6) and (8.7) with the modified key. As a result, we obtain the following

algorithm for the inverse cipher.

Algorithm 8.9 RIJNDAEL: DECRYPTION.

Block Y , round key W .

INPUT:

OUTPUT: Block X.

1. XeY$W,;

FOR2 = ˜ - 1 , T - 2 , . . . ,1 DO

2.

X t SubBytes-' (X),

3.

X t ShiftRows-l(X),

4.

X + MixColumns-'(X),

5.

X+X@WWi;

6.

X t SubBytes-l(X),

7.

X t ShiftRows-l(X),

8.

X+X@W,;

9.

10. RETURNX.

The inverse transformations used in the algorithm are defined by the

natural way.

Basics of Contemporary Cryptography for IT Practitioners

154

The transformation SubBytes-l(X) is applied to each byte b in X :

+ z6 + x2 + x))(˜' + x5 + x2)mod (x8+ 1),

b ( x ) +- (b(z) ('

-x

b(x) +- b-l(x) mod m ( z ) (0 c 0),

++++ +

where x7 + x5 + x 2 = (' x6 x5 x4 1)-l mod (x8 1). The results

x

are stored on the table S-l. The content of table S-' is explicitly given in

[Daemen and Rijmen (2002)].

The transformation ShiftRows-l(X) acts upon each row ri in block X

according to the rule

(here L--) denotes the cyclic shift right i bytes).

The transformation MixColumns-' (X) acts upon each column ci in

block X by the rule

+ 13y2+ 9y + 14. The same in the matrix form looks

where u-l(y) = l l y 3

like this:

(8.9)

Now proceed to the efficient tabular implementation which we consider

only for the case of a 32-bit computer. Denote the state of the block by U .

The sequence of Steps 3-6 of encryption algorithm converts the data block

from the state U to a new state Y . Taking into account the transformations

performed at Steps 3-6, we can write the computation of each j t h word

(i.e. each column) in Y :

(the rightmost column in the expression is the j t h word of Wi). Uncovering

Modern Secret Key Ciphers 155

the matrix multiplication we obtain

Define the four tables

Each table is built for b running from 0 to 255 and consists of 256 4-

byte words. The multiplication operation in the computations is binary

polynomial multiplication modulo rn(z). Tables Ti do not depend on either

the key or the data and can be computed in advance. Using these tables

we can build the j t h word of the block as follows:

Now we are ready to write the algorithm in the tabular form (Algo-

rithm 8.10). Note that many S-boxes are contained in tables Ti. For

instance, for the S-box at Step 8, one can use low-order bytes of table Tz.

To construct a tabular version for the inverse cipher we must review the

observations given above with respect to the inverse transformations. This

Basics of Contemporary Cryptography for IT Practitioners

156

Algorithm 8.10 RIJNDAEL: ENCRYPTION (FAST VERSION).

Block X, round key W .

INPUT:

OUTPUT: Block Y .

UtXa3Wo;

1.

F O R i = 1 , 2 , ..., ˜ - 1 D 0

2.

F O R j = 0,1,2,3 DO

3.

4. + To[Uo,j] CBTi[ui,j-i] CB Tz[U2,j-2]

wzj;

3 U , -@

@T [ 3 j 3]

u +- Y ;

5.

FOR i = 0,1,2,3 DO

6.

FOR j = 0,1,2,3 DO

7.

K,j

8. S[Ui,j-i];

+-

Y+Y@Wy;

9.

RETURN Y .

10.

results in obtaining the inverse tables T i ' :

Given these inverse tables we can write down the decrypting algorithm

(Algorithm 8.11).

Note once again that all the tables in a ready-to-use form may be found

in [Daemen and Rijmen (2002)l.

The last thing to consider is the formation of the round key. In the

direct and inverse ciphers, it is convenient to divide the round key W into

4-word blocks. However, the formation of the key must be done in a word

mode, so let's denote by the letter w with a subscript a distinct word in

W starting numbering from zero. As it follows from the encryption and

+

decryption algorithms, the round key W must consist of T 1 blocks where

+

T is the number of rounds. So the number of words in W equals 4(r 1).

In its turn, the number of words in the secret key K , which we shall denote

Modern Secret Key Czphers 157

Algorithm 8.11 RIJNDAEL: DECRYPTION (FAST VERSION).

Block Y , round key W .

INPUT:

OUTPUT: Decrypted block X.

Ut-Y@Wo;

1.

F O R i = ˜ - - 1 , ˜ - 2 ..., 1 D O

2. ,

3. FOR j = 0,1,2,3 DO

4. Xj T,'[Uo,j] â‚¬3 TT1[U1,j+1]@ Ti1[Uz,j+z]

+-

@TT1

[u3,j+3] Wi,j;

â‚¬3

UtX;

5.

6. FOR i = O,1,2,3 DO

F O R j = 0 , 1 , 2 , 3 DO

7.

S-'[ui,j+i];

8. Xi,j +

9. X+X@W,;

10. RETURNX.

by c, may be 4, 6, or 8. First we describe the algorithm for constructing

W and then discuss some issues.

ñòð. 29 |