<<

. 29
( 36 .)



>>


+ +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
( 36 .)



>>