permuted randomly. The content of the tables forms an extra secret pa
rameter that may be common for a large group of users. Note that in DES
the similar Sboxes are fixed and publicly known.
The following operations are used in the cipher:
+ addition modulo 232;
* cyclic shift left the specified number of bits;
bitwise “exclusive or” of two words, i.e. bitwise addition modulo 2.
@
Modern Secret Key Ciphers 143
Algorithm 8.1 BASIC CYCLE GOST 2814789.
OF
Block L, R, round key W .
INPUT:
OUTPUT: Transformed block L, R.
FOR i = 0, 1,. . . ,31 DO
1.
k + R+ Wi, k = ( k 7  ” k 0 ) 1 6 ;
2.
FOR j = 0,1,. . . ,7 DO
3.
4.

kj + Sj[kj];
L 6 L 6 ( k + 11);
5. 3
R;
L
6.
RETURN L, R.
7.
(At Step 4 of the algorithm distinct 4bit elements of variable k are used.)
The described LLbasic cycle” is used for encryption and decryption. To
encrypt a block X, construct the round key
put X and W to the input and obtain the encrypted block Y as the output.
To decrypt a block, construct the round key
i.e. (8.5) in the reverse order, input W , Y and obtain X as output.
A program implementation usually requires to rework the loop begin
ning at Step 3 of Algorithm 8.1 since operating with halfbytes is inefficient.
It is clear that the same transformation can be performed with the use of
4 tables, 256 bytes each, or two tables, 65536 halfwords each. For in
stance, when working with bytes, we have k = (ks.. . k0)256 and Steps 34
o Algorithm 8.1 are rewritten as follows:
f
FOR j = 0,1,2,3 DO
3.
kj t T 3 [ k j ] .
4.
The tables Tj, j = 0,1,2,3, are computed beforehand from Sboxes:
FOR i = 0,1,. . . ,255 DO
+
Tj[i]+ Szj[i mod 161 16S˜j+l[i 161.
div
Basics of Contemporary Cryptography for IT Practitioners
144
The standard says nothing about the rules of generating the keying
information except the claim that each Sbox should contain a permutation
of different numbers. Yet, it can be seen that, for example, zero key or
trivially defined Sboxes (mapping k to itself) do not provide the security
of the cipher.
The RC5 and RC6 Ciphers
8.2.2
The RC5 and RC6 are modern block ciphers designed by Ron Rivest in 1995
and 1998, respectively. The cipher RC5 (see [Menezes et al. (1996)l) has
been a touchstone for many new cryptanalytic methods. We shall describe
one of the attacks involving RC5 in Sec. 9.5. It must be said that RC5 was
not completely broken by either of the attacks but some of its “weak spots”
were demonstrated followed by increasing demands for parameter values.
As a response to these attacks, the cipher RC6 [Rivest et al. (1998)] was
suggested which may be viewed as an enhanced version of RC5. RC6 took
part in the competition for the new US block cipher standard carried out
in years 19992001, had passed to the finals but lost the first place to
another cipher (Rijndael). Nevertheless, intensive investigations of RC6 in
the course of competition do not reveal in it any weakness and this cipher
is highly esteemed by the specialists. For the sake of completeness and for
further references, we shall describe both ciphers but discuss the design
rationale only for RC6.
In RC5, the user specifies the word size w (16, 32, or 64 bits), the
number of rounds r, and the key length 1 in bytes. A particular variant of
the cipher is denoted by the template RC5w/r/Z, e.g. RC532/20/16. The
block always contains two words. The same round key W of 2 r + 2 words
is used in encryption and decryption.
The cipher uses the following operations (all on wbit words):
+,  addition and subtraction modulo 2”;
@ bitwise “exclusive or” of two words (the sum modulo 2);
*, ˜f cyclic left and right shifts by a specified number of bits (note that
given the word size of w bits the number of shift positions is re
duced modulo w, such a reduction being usually done automati
cally at machine level  the processor uses only loworder logw
bits of the number defining the shift amount).
The encryption algorithm is as follows.
145
Modern Secret K e y Ciphers
Algorithm 8.2 RC5: ENCRYPTION.
Twoword block ( a ,b ) , round key W .
INPUT:
OUTPUT: Encrypted block ( a ,b).
1. ata+Wo,btb+Wl;
FOR i = 1,2,. . . ,T DO
2.
+
a + ( ( a 63 b) * b) WZi,
3.
+
b + ( ( b ‚¬9 a ) * a ) w2i+1;
4.
RETURN ( a , b ) .
5.
To decrypt, undone the process in reverse order.
Algorithm 8.3 RC5: DECRYPTION.
Twoword block ( a ,b), round key W
INPUT:
OUTPUT: Decrypted block ( a ,b).
FOR i = T , T  1,.. . ,1 DO
1.
2. ( ( b  WZi+l) Ct a ) 63 a,
b +
u t ( ( u  Wzi) 6) 63 6;
3.
w,;
b c b  WI, a + a 
4.
RETURN (a,b).
5.
The process of round key formation (round key schedule) is more com
plicated in RC5 and RC6 than in GOST 2814789, which is typical for most
of modern ciphers. In fact, the secret key K is expanded to a longer pseudo
random sequence W in order to harden the cryptanalysis of a cipher.
Denote by c the number of words in the key, c = 81/w. With the round
key schedule algorithm the secret key K is expanded to the round key W :
The following “magic” numbers are used in the algorithm: P,, the first w
bits of the binary expansion for e  2 where e = 2.718281828.. . is the base
of natural logarithm, and Q,, the first w bits of the binary expansion for
 1 where C#J = (  1)/2 is the golden section. In Table 8.1 the values
6
of P, and Qw are given in hexadecimal system for various word lengths.
With all this in mind, the algorithm of round key formation for RC5 is
written down as follows.
Basics of Contemporary Cryptography for IT Practitioners
146
Algorithm 8.4 RC5: ROUND KEY SCHEDULE.
Secret key K .
INPUT:
OUTPUT: Round key W .
w Pw;
o
1. +
F O R i = 1 , 2 ,..., 2 r + 1 DOWi+Wil+Q,;
2.
a + 0, b t 0, i + 0, j + 0;
3.
+
k + 3max(c, 2r 2);
4.
DO k times
5.
++
Wi + (Wi u b) Q 3, a + Wi,
6.
Kj + ( K j + a + b ) ˜ ( ˜ + b ) b + K j ,
,
7.
+
i t i + 1mod 2r 2, j + j + 1mod c;
8.
RETURN W .
9.
Now we describe the cipher RC6. It is quite close to RC5. In RC6, the
user also specifies the word size w (16, 32, or 64 bits), the number of rounds
r, and the key length 1 in bytes (from 0 to 255). But, in contrast to RC5, the
block consists of 4 words and the round key W of 2r+4 words. A particular
variant of the cipher is denoted similarly by the template RCGw/r/l. For
example, RC632/20/16 is the variant with the blocksize and key length
128 bits, 20 rounds (this variant had been proposed a a candidate for the
s
US standard).
The cipher uses the same operations as RC5 but one new operation is
added:
* multiplication modulo 2"
Algorithm 8.5 RC6: ENCRYPTION.
Fourword block ( a ,b, c, d ) , round key W .
INPUT:
OUTPUT: Encrypted block (a,b, c, d).
b+b+Wl, d + d + W 1 ;
1.
FOR i = 1 , 2 , . . . , r DO
2.
+
t + ( b * (2b 1))c ' logw,
3. 
4. u t ( d * ( 2 d + 1 ) ) c'logw,
+
a + ( ( a C t ) u) WZi,
5. B Q
C+ ( ( a 4 t ) + W 2 i + l ,
6. *
( a ,b, c, 4 ( 4 c, d , a ) ;
7. +
+ +
8. a a W2rf27 c c W2rf3;
RETURN (a,b,c,d).
9.
Modern Secret Key Ciphers 147
To decrypt, as in RC5, undo the process in reverse order.
Algorithm 8.6 RC6: DECRYPTION.
Fourword block (a,b, c, d ) , round key W .
INPUT:
OUTPUT: Decrypted block ( a ,b, c, d ) .
c c  W 2 r f 3 , a +a  Wzr+2;
1. +