<<

. 18
( 18)



5.1 Propagation of di¬erences in a local collision of SHA . . . . . . 170

7.1 Rho shape while iterating a random function . . . . . . . . . 224

10.1 A 2-dimensional lattice with a basis . . . . . . . . . . . . . . 312
10.2 A reduced basis of the same lattice . . . . . . . . . . . . . . . 313
10.3 Applying Gauss™s algorithm . . . . . . . . . . . . . . . . . . . 314
10.4 Typical cases of short vectors in 2-dimensional lattices . . . . 316
10.5 Computing b— from b3 . . . . . . . . . . . . . . . . . . . . . . 321
3
10.6 An elementary reduction step of L3 in dimension 3 . . . . . . 323

11.1 A sample algebraic system in two unknowns . . . . . . . . . . 342

12.1 Noisy LFSR (Binary Symmetric Channel) model . . . . . . . 376


List of Programs
2.1 Representation of F232 with a Galois LFSR . . . . . . . . . . 51
3.1 Basic C code for matrix multiplication over F2 . . . . . . . . 73
3.2 Matrix multiplication over F2 with compact encoding .... 74
3.3 Matrix multiplication using fast scalar product . . . . . . . . 76
Fast transposition of 32 — 32 matrices over F2 . . . . . . . . .
3.4 78
Faster scalar product for multiplying of 32 — 32 matrices . . .
3.5 79
C code for elementary 32n — 32n matrix multiplication over F2
3.6 86
3.7 C code for elementary matrix multiplication over Fp . . . . . 88
3.8 C code for matrix mult. over Fp with fewer modular reductions 90
Inversion of 32 — 32 matrix over F2 . . . . . . . . . . . . . . .
3.9 100
4.1 Basic C code for Eratosthenes™s sieve . . . . . . . . . . . . . . 126
4.2 Small memory code for Eratosthenes™s sieve . . . . . . . . . . 129
4.2 Small memory code for Eratosthenes™s sieve (continued) . . . 130




© 2009 by Taylor and Francis Group, LLC
Lists 495

4.3 Line sieving with two levels of cache . . . . . . . . . . . . . . 151
9.1 C code for Walsh transform . . . . . . . . . . . . . . . . . . . 278
9.2 C code for Moebius transform . . . . . . . . . . . . . . . . . . 287


List of Tables

32 — 32 Boolean matmul. on Intel Core 2 Duo at 2.4 GHz . .
3.1 80
Times for (32n) — (32n) Boolean matrix multiplication . . . .
3.2 86

5.1 DES initial permutation . . . . . . . . . . . . . . . . . . . . . 158
5.2 DES ¬nal permutation . . . . . . . . . . . . . . . . . . . . . . 158
5.3 Permutation of the round function . . . . . . . . . . . . . . . 159
5.4 Expansion of the round function . . . . . . . . . . . . . . . . 160
5.5 S-box S1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.6 S-box S2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.7 S-box S3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.8 S-box S4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.9 S-box S5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.10 S-box S6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.11 S-box S7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.12 S-box S8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.13 Permutation PC-1 of the key bits . . . . . . . . . . . . . . . . 162
5.14 Table PC-2 to extract Ki from Ci and Di . . . . . . . . . . . 162
5.15 De¬nition of the round functions and constants . . . . . . . . 167
5.16 Possible expanded bit sequences for local collisions . . . . . . 172
5.17 Case by case behavior of MAJ(x, y, z) . . . . . . . . . . . . . 175
5.18 Case by case behavior of XOR(x, y, z) . . . . . . . . . . . . . 175
5.19 Case by case behavior of IF(x, y, z) . . . . . . . . . . . . . . . 175
5.20 Case by case behavior of ADD(x, y, z) (carry bit on left) . . . 176
5.21 Interferences of overlapping local collisions . . . . . . . . . . . 178

9.1 Timings on Intel Core 2 Duo at 2.4 GHz using gcc 4.3.2 . . . 278

12.1 Typical probabilities with binomial distributions . . . . . . . 379

15.1 Equations (x + u) = (y + v1 ) · (y + v2 ) as triples (u, v1 , v2 ) . . 450
15.2 Equations (x + u1 ) · (x + u2 ) = (y + v) as triples (u1 , u2 , v) . 450




© 2009 by Taylor and Francis Group, LLC
496 Algorithmic Cryptanalysis

15.3 Equations a(x + u1 ) · (x + u2 ) = (y + v1 ) · (y + v2 ) from x + ay + b
represented by (a, b) (u1 , u2 , v1 , v2 ) . . . . . . . . . . . . . . 451




© 2009 by Taylor and Francis Group, LLC

<<

. 18
( 18)