. 28
( 36 .)


FOR i = T , T - 1,.. . ,1 DO
( 4a , b, 4 ,
3. ( a ,b, c, d )

t f- ( b * (2b 1))p logw,
u t ( d * (2d 1))* logw,
a + ( ( a - W Z ) u ) CB t ,
6. ˜f

c t ( ( c- W2i+l)4t ) CB u;
d t d - Wl, b +- b - Wo;
9. RETURN (a,b,c,d).

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

Algorithm 8.7 RC6: ROUND KEY SCHEDULE.
Secret key K.
OUTPUT: Round key W .
Wo t P w ;
FOR i = 1,2,. . . ,2r 3 DO W +- WGI+ Q,;
2. i
a +- 0 , b t 0, i +- 0, j +- 0;
k c 3max(c, 27- 4);
DO k times
W i (Wi a b) t-' 3, a + Wi,
6. t
Kj t ( K j + a + b ) + ( a + b ) , b t K j ,
+ +
i f- i + 1 mod 2r 4, j +- j 1 mod c;

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

“Magic” numbers for RC5 and RC6.
Table 8.1

16 64

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
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
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,
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 =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


Block X , round key W .
OUTPUT: Block Y.
FOR2 = 1 , 2 , ..., ˜ - 1 D 0
Y c SubBytes(Y),
Y t ShiftRows(Y),
5. Y c MixColumns(Y),
7. Y c SubBytes(Y),
Y +- ShiftRows(Y),
9. YtYeW,;

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:


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


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) +
+ + 5 = 11000010,

+ 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)

= (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

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


. 28
( 36 .)