FOR i = T , T - 1,.. . ,1 DO

2.

( 4a , b, 4 ,

3. ( a ,b, c, d )

+-

+

t f- ( b * (2b 1))p logw,

4.

+

u t ( d * (2d 1))* logw,

5.

a + ( ( a - W Z ) u ) CB t ,

6. ˜f

c t ( ( c- W2i+l)4t ) CB u;

7.

d t d - Wl, b +- b - Wo;

8.

9. RETURN (a,b,c,d).

To describe the round key formation we use the same notation as for

RC5.

Algorithm 8.7 RC6: ROUND KEY SCHEDULE.

Secret key K.

INPUT:

OUTPUT: Round key W .

Wo t P w ;

1.

+

FOR i = 1,2,. . . ,2r 3 DO W +- WGI+ Q,;

2. i

a +- 0 , b t 0, i +- 0, j +- 0;

3.

+

k c 3max(c, 27- 4);

4.

DO k times

5.

++

W i (Wi a b) t-' 3, a + Wi,

6. t

Kj t ( K j + a + b ) + ( a + b ) , b t K j ,

7.

+ +

i f- i + 1 mod 2r 4, j +- j 1 mod c;

8.

RETURN W .

9.

Discuss briefly the main ideas of RC6 construction. First of all, note

that similarly to DES and GOST 28147-89, in each round of RC6, one half

of block is used for encrypting the other. Indeed, the values of variables t

and u (Lines 3-4 of Algorithm 8.5) are determined only by the words b and

d , respectively. Then these variables are used to modify the words a and c

prior to summation with the elements of the key (Lines 5-6). Therefore, a

Basics of Contemporary Cryptography for IT Practitioners

148

“Magic” numbers for RC5 and RC6.

Table 8.1

16 64

32

W

pw b7el b7e15163 b7e15162 8aed2a6b

Qw 9e37 9e3779b9 9e3779b9 7f4a7c15

dependence upon b and d is introduced in a and c. In the next round, the

pairs a, c and b, d exchange the roles, b and d transposed (Line 7). Owing

to such structure the number of rounds has to be even.

The function f(z) = (2z2+ z) mod 2” chosen for computation of t and

u is known to manifest a strong dependence of high-order bits of its value

upon all the bits of the argument. There are the high-order bits o f f that

must determine the shift amount in Lines 5-6 of the algorithm. So these

bits are put in the low-order bits of t and u by means of rotation v log w.

The use of “exclusive or7, for modification of a and c is quite traditional

but the use of data-dependent rotations is a characteristic feature of RC6

(and RC5).

Lines 1 and 8 are intended to hide the words unmodified in the first and

last rounds.

The recommended number of rounds T = 20 is connected with the results

of investigating the cipher™s security with respect to differential and linear

cryptanalysis.

In the course of studying the security of RC6 no weak keys were found,

i.e. any key, even all zero, ensures the declared security of the cipher. It is

believed that for RC6-32/20/16 there exist no attacks more efficient than

the brute force attack.

The Rijndael (AES) Cipher

8.2.3

This cipher is designed by Belgian specialists Vincent Rijmen and Joan

Daemen and has won in the competition AES as was mentioned before.

In 2001, Rijndael was adopted a the new US standard (AES). Perhaps,

s

it will play as important role in practical cryptography as was played by

DES for decades. Rijndael is noticeably more complicated than RC6 and

GOST 28147-89 although its computer implementation occurs to be very

fast. We shall describe only the main ideas behind the construction of the

cipher. Details and implementation examples may be found in [Daemen

and Rijmen (2002); FIPS 197 (2001)l.

The Rijndael/AES cipher is characterised by the block size 128 bits, the

Modern Secret Key Ciphers 149

key length 128, 192, or 256 bits, and the number of rounds 10, 12, or 14

depending on the key length.

Let™s agree on notation. The word (32 bits) is the sequence of 4 bytes.

The bytes in a word are numbered from 0 (least significant byte) to 3 (most

significant byte). The data block consists of 4 words that are also numbered

from 0 to 3. For ease of designation, we shall assume that the ordinal

numbers of bytes in a word and words in a block are always reduced modulo

4, without explicit indication. A data block is considered as a matrix 4 x 4

bytes, the words corresponding not to the rows (as usually) but to the

columns. For instance, X2,3 denotes the 2nd byte of the 3rd word of block

X.Nevertheless, the item with only one subscript denotes the word, e.g. X3

is the 3rd word of the block. We shall follow this agreement in order not

to change the connected terminology of Rijndael.

For making transformations in a block, the round key W is used, derived

from the secret key K . The length of the secret key 1 implicates the number

of rounds r:

1 = 128 + r = 1 0 ,

1=192+r=12,

1 =256 + r = 1 4 .

The round key consists of blocks (per 128 bits), the number of blocks being

equal to the number of rounds plus 1,

w = wo, . . . ,w,

w,, .

Three criteria formed the basis for the design of Rijndael: security with

respect to all known attacks, speed and compactness of code, simplicity

and clearness of design. As distinct from the previous ciphers considered,

Rijndael does not use any analogue of the Feistel structure. Each round

consists of three different invertible transformations called layers:

(1) the linear mixing layer guarantees high diffusion between bytes over

multiple rounds for masking statistical relations;

(2) the non-linear layer implemented with S-boxes having optimum non-

linearity properties precludes the application of the linear, differential,

and other methods of cryptanalysis;

(3) the key addition layer performs the encryption.

Encryption begins and ends with the operation of adding the key. This

allows to conceal the input of the first round in the known-plaintext attack

and to make cryptographically meaningful the result of the last round.

Basics of Contemporary Cryptography for IT Practitioners

150

Algorithm 8.8 RIJNDAEL: ENCRYPTION.

Block X , round key W .

INPUT:

OUTPUT: Block Y.

YcXCBWo;

1.

FOR2 = 1 , 2 , ..., ˜ - 1 D 0

2.

Y c SubBytes(Y),

3.

Y t ShiftRows(Y),

4.

5. Y c MixColumns(Y),

YcYeWi;

6.

7. Y c SubBytes(Y),

Y +- ShiftRows(Y),

8.

9. YtYeW,;

10. RETURN Y.

The SubBytes procedure (byte substitution) implements the non-linear

layer. The other procedures, ShiftRows and MixColumns, present the lin-

ear mixing layer. The key addition layer is realised by means of bitwise

“exclusive or™™ $.

Notice that there is no MixColumns transformation in the last round.

It seems at first sight worsening the structure of cipher. But it is not so.

Denote the Steps 3-6 of the algorithm by B, R, C, and K, respectively, and

write the sequence of operations in the form of linear chain:

BRCKBRK .

KBRCKBRCK (8.6)

**

To decrypt a block one has to perform all operations in the reverse order

using the inverse functions. As will be shown below, the transformations B

and R can be swapped without affecting the result. The transformations C

and K can also be swapped provided some changes are made in the round

key. Under such alteration the sequence (8.6) is rewritten as

KRBKCRBKC . . . RBKCRBK . (8.7)

The sequence (8.7), read from right to left, matches exactly to (8.6). This

means that we can decrypt the block using the same sequence of operations

as in encryption. It is important that the sequence of operations BRCK

(as will be shown below) can be efficiently implemented by table lookups,

the tables being constantly defined, i.e. independent of either the key or

the data.

Modern Secret K e y Ciphers 151

Now we proceed immediately to the description of transformations BRC.

In order to understand the Rijndael transformations one have to learn poly-

nomial arithmetic (see, e.g. [Knuth (1981)l). However, if the reader is inter-

ested mainly in computer implementation of the cipher, he/she may jump

immediately t o p. 156 where efficient tabular algorithms are presented.

Each data byte in Rijndael is considered as a polynomial with binary

coefficients 0 and 1 and all operations with coefficients are performed mod-

ulo 2. For example,

+ z4 + z + 1 ,

10010011 = x7

( 2+ x4 + 1)

+ 01010001 = ( z 7 + z4 + z + 1) +

10010011

+ + 5 = 11000010,

=27

+ z4+ 2 + 1) . z

10010011 * 00000010 = (z7

+ z5 + z2 + 2 = 100100110.

=

In many of Rijndael™s operations, byte-polynomials are multiplied modulo

+ x4 + z3 + 2 + 1. For example,

the polynomial m ( z )= z8

10010011 ˜00000010

mod m ( s )

+ x4 + z + 1) . z mod (z8+ z4+ x 3 + z + 1)

(x7

=

= (z8 + x5 + x 2 + z) mod (z8+ z4+ x 3 + + 1) 2

= ( ˜ ˜ + 2 ˜ + 2 ˜ + ˜ ˜ + 2 ˜ + 2 ˜ + =+ I )

-(z) x z5+z4+23+˜2+100111101

=

(subtraction and addition modulo 2 are the same operation).

The selected polynomial m(z) has the following important property:

it cannot be represented as the product of other polynomials with binary

coefficients (this is an analogue of a prime number in binary polynomial

arithmetic). As a result, any polynomial a(.) # 0 has the inverse, i.e. the

polynomial u - l ( z ) such that a(.) . mod m ( z ) = 1 (the inverse is

computed by the extended Euclidean algorithm in which all numbers are

replaced by polynomials). In terms of the theory of groups, one says that

byte-polynomials constitute a field F2s .

Each word of data, i.e. a sequence of 4 bytes, in Rijndael is represented

as a polynomial with coefficients in IF28 , i.e. each byte-coefficient is consid-

ered as binary polynomial reduced modulo m(z). For example, the word

Basics of Contemporary Cryptography f o r IT Practitioners

152

7500a302, written in hexadecimal system, consists of 4 bytes (from most to

least significant): 75, 00, a3, and 02, and can be represented as polynomial