of encryption to the input sequence, denoting the result by P I , P 2 , . . . , Pm:
h).
= El(Q1,h ) , = &(am,
*. * 7
P1 Pm
P
We claim that the sequence is more random than the sequence a,
Random Numbers in Cryptography 181
r(P)< $0).After the second step of encryption, the sequence
i.e.
EZ(P1,k 2 ) , E2(P2, k2) 7 E2(Pm, k2)
*** 7
is more random than P, and so on. Each step of encryption increases the
degree of randomness.
Notice the obvious consequence: in decryption according to (9.5),the
randomness of the data decreases from step to step. For example, the
sequence
which is a, is less random than P. But what is important: this is true only
if the decryption is done with the valid key. If the key is not valid, denote
it by ki, then the sequence
a,. , a:,
Q; = DI(Pm, k:)
= Dl(P1, *'
will be more random than P, ˜ ( a '< y(P). This is because decrypting with
)
a different key corresponds to further encrypting with that key, which is
the wellknown multiple encryption principle [Menezes e t al. (1996)l. So,
generally, decryption with an invalid round key increases randomness, while
decryption with the valid round key decreases randomness. This difference
can be detected by a statistical test.
The suggested gradient statistical attack is mounted as follows. First
encrypt the sequence a l , a2, . . . , am, defined above. Denote the output
sequence by w ,
. .. , .
w, = E(am,K )
= E(a1,K),
w1
(Recall that the cipher involves t rounds or steps, and the length of subkey
at each step is Ikl.)
Now begin the main procedure of key search. For all u E {O,l}lkl
compute a sequence
and estimate its randomness, i.e. compute y ( r t ( u ) ) . Find such u*for which
y(rt(u*)) maximal. Assume that unknown subkey kt = u*.Note that
is
the number of operations at this stage is proportional to rn21'l.
After that, based upon the sequence rt(kt), repeat the similar compu
tations t o find subkey Ictl. Using r t  1 ( k t  1 ) find kt2, and so on down to
Basics of Contemporary Cryptography foT I T Practitioners
182
kl. The total number of operations t o recover all subkeys is proportional
to mt21kl.
We have described the idea of the attack in a pure form. Now let™s
discuss some implementation variants.
(1) The measure of randomness y is a parameter. One may apply differ
ent measures not only for different ciphers, but also for different rounds of
the same cipher. As stated above, any statistical test applicable to checking
the main hypothesis Ho that the binary sequence is truly random versus
the opposite hypothesis HI that the sequence is not, may be used for that
purpose.
( 2 ) The sequence length m was chosen to be constant for simplicity of
description. In fact, this length may vary in each round. More lengthy
sequences are needed when cipher™s output becomes more random, i.e. in
the last rounds. The value of m depends on the power of statistical test
and the cipher and can usually be determined experimentally.
(3) Some division of encryption process into simple steps may result in
a situation where, at a particular step, only part of the block is affected.
This may reduce the effective length of the sequence to be tested. Thus the
division of RC5 into steps as shown in Example 9.4, assumes that at the
odd steps (1, 3, . . . , t  1) only the left half of the block, a, changes, and
at the even steps ( 2 , 4, . . . , t ) the right half, b. Therefore only one half of
the sequence, virtually m/2 blocks, is to be subjected to statistical tests.
(3) When searching for a relevant subkey, it is reasonable to keep not a
single but several candidate subkeys, say, s different values of u E (0,l}lkl
for which y(rj(u)) is maximal. Besides, when searching for simple se
quences and subkeys, the sequential methods, analogous to sequential cri
teria in statistics, are appropriate.
(4) The initial nonrandom sequence a1, a2, . . . , a, may be constructed
in different ways. For example, it seems to make sense to choose the se
quence in which consecutive words (ai,ai+l) not only contain many equal
bits but differ in at most one bit (socalled Grey code). Other choices may
reflect the peculiarities of a particular cipher.
(5) The last modification may be connected with the fact that many
modern ciphers with great number of rounds convert even absolutely non
random input sequence into something “quite random” (at least not dis
tinguishable from a truly random sequence by known tests in acceptable
time). Let, for instance, the cipher has T rounds and for some simple initial
Random Numbers in Cryptography 183
sequence a:, a;, . . . , a: the sequences
...
are not random under all subkeys k l , . . . , k d , d < r. Then the suggested
attack may be modified in the following manner. For each set of subkeys
k d + l , . . . , k, of rounds d + 1, . . . ', r apply the main procedure described
above and find unknown subkeys k l , . . . , k d . In other words, find subkeys
.
k d + l , . . , k, by exhaustive search, and k l , . . . , kd by the gradient statistical
test. To maintain this combined attack O(m2('d)lkld21kl) operations are
required, which, depending on certain parameters, can be smaller than
O(2lKI)for exhaustive key search.
Let's describe briefly a concrete application of the described attack to
one of the most popular ciphers, RC5. The experiments were planned
as follows. First, the degree of randomness of encrypted sequences as a
function of the number of steps of encryption was analysed. The goal
was to find the maximal number of steps at which the tests can tell the
encrypted sequence from truly random. Second, the claim the attack is
based upon was examined, namely, whether decrypting with a wrong subkey
increases randomness in comparison with decrypting using a valid subkey,
more exactly, whether these are distinguishable by the tests. Finally, based
on the results obtained, the suggested attack started. The experiments
were carried out on a multiprocessor system containing 10 1GHz Alpha
processors with 1G bytes of memory per device.
The experiments confirm the assumptions as to principal possibility of
the suggested gradient statistical attack. First, the encrypted sequence gets
more random as the number of rounds increases. And second, a sequence
decrypted with invalid subkey is more random than one decrypted with
valid subkey, and the test can detect this. Some additional tricks dependent
on the structure of RC5 are used whose description goes beyond the scope
of the book. To the date, RC5 with 8 rounds can be broken with 233 chosen
plaintextciphertext pairs.
This page intentionally left blank
Answers to Problems and Exercises
1.1, a. k = 17. b. k = 23.
b. MANGO ( I c = 20).
a PINEAPPLE (k = 5).
12
.. 2.1. a.
.
5 = 5, 16 = 6, 27 = 7, 4 = 6, 13 = 3 = 7, 3 f 8 = 1, 3  8 = 5,
3 . 8 = 4 , 3  8 . 5 = 4 , 5 = 0 (mod 10). b. 5 = 5 , 1 6 = 5 , 2 7 = 5 ,  4 = 7 ,
13 = 2 = 9 , 3 + 8 = 0 , 3  8 = 6 , 3 . 8 = 2,343.5 = 2.5 = 10 (mod 11).
2.2. 28 mod 10 = 6, 3' mod 10 = 7, 719 mod 100 = 43, 757 mod 100 = 7.
2.3. 108 = 2 * 2 * 3 . 3 * 3, 77 = 7.11, 65 = 5 * 13, 30 = 3 . 3 . 5 , 159 = 3 * 53.
2.4. Pairs (25,12) and (40,27) are coprime, the others are not (numbers
(25,15) are divisible by 5, (13,39) divisible by 13).
2 5 (˜(14) 6,(˜(20) 8.
=
.. =
2.6. 4 5 3 ) = 52, (˜(21) ( ˜ ( 7*)( ˜ ( 3 = 6 2 = 12, (˜(159) 2 * 52 = 104.
)
= =
9

2.7. 313 mod 13 = 3 312 mod 13 = 3, 522mod 11 = 5 2 . 51° . 51° mod 11 =
25 mod 11 = 3, 317 mod 5 = 3.
2.8. 39 mod 20 = 3 . 38 mod 20 = 3, 214 mod 21 = 22 . 212 mod 21 = 4,
21°7 mod 159 = 23 . 21°4 mod 159 = 8.
gcd(21,12) = 3, gcd(30,12) = 6, gcd(24,40) = gcd(40,24) = 8,
2.9.
gcd(33,16) = 1.
2.10. a. a : =  l , y = 2 . b a:=l,y=2. c. s = 2 , y =  1 .
.
d. 2 l , =˜2.
2.11. 31 mod 7 = 5, 5l mod 8 = 5, 31 = 18, lo' = 16 (mod 53).
2.12. The primes less than 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 73, 79, 83, 89, 97. Among them, the numbers
185
Basics of Contemporary Cryptography for IT Practitioners
186
+ 1.
5, 7, 11, 23, 47, 59, and 83 correspond to the form p = 2q
2.13. If p = 11 then generator g may be either 2, 6, 7, or 8.
2.14. a. YA = 20, YB = 17, ZAB = 21. b. YA = 13, YB = 14,
ZAB = 10. C. YA = 21, YB = 9, ZAB = 16. d. YA = 8, YB = 5,
ZAB = 9. e. YA= 6, YB = 17, ZAB = 16.
2.15. a . d A = 1 1 , d B = 1 3 , r c l = 1 7 , z 2 = 5 , 2 3 = 6 , x 4 = 4 . b.dA=3,
d B = 19, 21 = 8, 2 2 = 12, 2 3 = 3, ˜4 = 6. C . d˜ = 5, dB = 11, X I = 14,
10, 2 3 = 3, 2 4 = 10. d. d A = 5, dB = 15, 2 1 = 7, 2 2 = 21, 2 3 = 14,
22 =
x4=17. e. d ˜ = l l , d ˜ = 5 , ˜ 1 = 1 5 , ˜ 2 = 2 , ˜ 3 = 8 , ˜ 4 = 9 .
2.16. a. d g = 1 3 , ˜ = 1 4 , e = 1 2 , m ' = 5 . b. d g = 1 6 , r = 9 , e = 1 5 ,
m' = 10. c. d B = 15, r = 16, e = 14, m' = 10. d. dB = 21, r = 14,
e = 1 2 , m ' = 5 . e. d g = 8 , r = 5 , e = 5 , m 1 = 1 0 .
2.17. a. N A = 55, ( ˜ ( N A ) 40, C A = 27, e = 23, m' = 12. b. N A = 65,
=
( ˜ ( N A ) 48, C A = 29, e = 50, m' = 20. C. N A = 77, ˜ ( N A= 60,
= )
C A = 43, e = 52, m' = 17. d. N A = 91, ( ˜ ( N A ) 72, C A = 29, e = 88,
=
m' = 30. e. N A = 33, ˜ ( N A ) 20, C A = 7, e = 9, m' = 15.
=
2.18.m=lll. 31 a.x=17. b.x=10. c.x=28. d.z=14.
..
e. x = 30.
3.2. a . x = 2 0 . b.x=45. c.x=34. d.x=53. e.x=25.
3.3. a. x = 10000. = 20000. c. x = 1000. 12345.
b. d. =
2 IC
e. x=25000.
4.1. a . s = 2 8 . b.s=30. c.s=26. d.s=71. e.s=18.
a. (7,28) is authentic, (22,15) is not, (16,36) is authentic.
4.2.
b. (6,42) no, (10,30) yes, (6,41) yes. c. (13,41) yes, (11,28) no, (5,26)
yes. d. (15,71) yes, (11,46) no, (16,74) yes. e. (10,14) no, (24,18) yes,
(17,8) yes.
4.3. a. y = 2 2 , r = 1 0 , ˜ = 1 5 , I c  ˜ = 1 5 , ˜ = 5 . y = 9 , r = 1 9 ,
b.
U = 13, k' = 3, s = 17. C. y = 10, T = 21, u = 11, k' = 17, S = 11.
d. y = 6 , r = 1 7 , ˜ = 7 , I c  ˜ = l 9 , s = l . e. y = l l , r = 7 , ˜ = 1 8 ,
kl = 7, s = 16.
1, T' = 19, g h = 19), (15; 10,5) yes (y' = 1,
4.4. a. (15; 20,3) yes (y' =
rs = 19, g h = 19), (15;19,3) no (y' = 22, rs = 5, g h = 19 # 18).
b. (5; 19,17) yes (y' = 13, rs = 21, g h = 20), (7; 17,8) no (' = 3, rs = 18,
y
Answers to Problems and Exercises 187
gh = 17 # 8), (6;17,8) yes (y' = 3, rs = 18, gh = 8). c. (3;17,12) yes
(y' = 17, rs = 6, gh = lo), (2; 17,12) no (y' = 17, rs = 6, g h = 2 # lo),
(8;21,11) yes (y' = 7, rs = 22, g h = 16). d. (5;17,1) yes (y' = 12,
rs = 17, g h = 20), (5;11,3) yes (y' = 1, rs = 20, g h = 20), (5;17,10)
no (y' = 12, rs = 4, g h = 20 # 2). e . (15;7,1) no (y' = 7, rs = 7,
g h = 19 # 3), (10; 15,3) yes (y' = 10, rs = 17, g h = 9), (15; 7,16) yes
(y' = 7, rs = 6, g h = 19).
4.5. a. y = 1 4 , r = 3 , s = 8 . b. y = 2 4 , r = 3 , s = l . c . y = 4 0 ,
r = 9 , s = 8 . d. y = 2 2 , r = 9 , s = 5 . e . y = 6 4 , r = 7 , s = 3 .
4.6. a. (10;4,5) no (sl = 9, u1 = 2, u2 = 3, a"] = 40, yu2 = 64,
21 = 3 # 4), (10;7,4) yes (sl = 3, u1 = 8, u2 = 10, a"' = 24, yU2= 24,
w = 7), (10;3,8) yes (sl = 7, u = 4, up= 10, a"' = 15, y"2 = 24, w = 3).
1
b. (1;3,1) yes 1, u1 = 1, u2 = 3, a"' = 25, yU2= 22, = 3),
(s' =
1, u1 = 1, u2 = 9, a"' = 25, yU2 = 62, w = 9), (1;4,5)
(1;9,1) yes (sl =
no (s' = 9, u = 9, up= 3, a"' = 64, y"2 = 22, w = 1 # 4). C. (7;7,4)
1
yes (s' = 3, u1 = 10, 212 = 10, a"' = 59, yU2 = 62, w = 7), (7; 9,2) no
(s' = 6, u1 = 9, u = 10, a"' = 64, y"2 = 62, w = 4 # 9), (5; 9,8) yes