<<

. 15
( 16)



>>




Table A-2: Wang's AM0 Differential (Part 1) [157]

Output Wj AWj AOutyut VOutput
j -
x, . . . . . . . . .-++++++ ++++++++ ++......

4
+B -
231
+
3 1 2 3 6 + . . . . . . . + . . . . . . . . . . . . . . . .- . . .. ..
0
5 Q5 X5
- +--
2 7 2 3 6 0 ++++++-- -. . . . . . . . . ..-+++ ++-+++++
6 0
X6
Q6
- _ -+
2 3 1 7 1 5 0 . . . . . . . . -..-+++- + . . . . . . . . . . . . . .+
Q7 X7 0
7
+ -+
- ++ . . . .+-
- ......................
Xg
8 Qs 3160
0
$i c2 +.. . . . . . . . . . . . . . . .+-. . . . . . . . . . . .
Xg
Q9
9 0
++. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Xl0
Qlo 0 &3$0
10
+ --
1'5 31 1 3 7 +.. . . . . . . . . . -+++ +++. . . . - + . . . . . . .
Xll
Qll
11
+.. . . .+- . . . . . . . . . . . . . . . . . . . . . . . .
QI2 XI2
12 &$I
0
+
+...............................
+. . . . . . . . . . . . . . . - . . . . . . . ....+...
+.-..... ........................
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
+ . . . . . . . . . . . . . +. . . . . . . . . . . . . . . . .
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
................................
................................
................................
0
24 Q24 x9

3'; ................................
0
25 x4
1
Q25
APPENDIX
364




Table A-3: Wang's A M , Differential (Part 2 ) [157]

Wj AWj AOlltput VOutput
Output
j


1'5 3 t l i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
XII
34 Q34

*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Qs:,
35 XI* $
1 21
*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36 0 $
1
x1
6236

*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
$
1
37 $
1
X4
Q37
t
*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38 Qs 0 31
X7


3+ + 1 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44 0
x9
(2 4 4

+...............................
31
45 0
Qu Xi2
+
+...............................
31
46 0
(246 x15
+
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
47 0
(2.17 x
2
+
+...............................
48 Xo 0 31
(248

-...............................
$
1
49 0
x7
+
Q49

+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31 $
1
50 (25" x4
1
+
-...............................
x:, 31
51 0
(251


+
...............................
31
57 0 -
Q57 x5
1
+
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58 X6 0 31
Q:,8
+
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0 31
59 x3
1
Q59
+ +
+...............................
60 Q f j o + A X4 31 31
+ ++
+ . . . . .+. . . . . . . . . . . . . . . . . . . . . . . . .
+ D Xi1 31 25
15
61 Q6,
++
+ . . . .+-. . . . . . . . . . . . . . . . . . . . . . . . .
+C 3125
0
62 X2
++
Q(jz


-. . . . .+. . . . . . . . . . . . . . . . . . . . . . . . .
+ B X!, 0 3125
63 Q63
APPENDIX 365




Output Wj AWj AOutput VOutput
j
3™;k - . . . . .+. ........................
0 Xo
Qo 0




-..-+. . . . . . . . . . . . . . . . .-+ ++. . . . . .
31276
6 0
Q6
+--+
x
6
31231715 -....-++ + . . . . . -+ - . . . . . . . . . . . . . . .
0
X7
7 Q7

2166 +- -- . . . .+-
-.....................
xi?
8 0
Q8
&I3 - . . . . . . . . . . . . . . . . . . + . . . . . . . . . . . .
Xg 0
9 Q9
3i -...............................
10 0
6210 Xl0

-. . . . . . . ....-+++ +++..... . . . . . . . .
11
........................
++------
12
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
+. . . . . . . . . . . . . . . +. . . . . . . . . . . + . . .
14
+.-..... ........................
15
+...............................
16
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
+ . . . . . . . . . . . . . +. . . . . . . . . . . . . . . . .
18
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
+...............................
7


31
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3l
+
3i +. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3fi +...............................
................................
24 0
0
Qzs x
9

................................
0
$
1
25 &a5 x4
1
APPENDIX
366




Table A-5: Wang™s AM, Differential (Part 2) [157]
__
-
W , AW, AOiitput VOutput
Output
j
-



*. . . . . . . . . . . . . . . . . . . . . . . ........
˜




15 $
1
34 Q34
........
i.. . . . . . . . . . . . . . . . . . . . . .
$
1 $
1
35 Q35
L
....................... ........
0 3˜1
36 f
QSti

3i 2
1 i. . . . . . . . . . . . . . . . . . . . . . . ........
37 Q37
ii f. . . . . . . . . . . . . . . . . . . . . . . ........
38 0
Q3X



3™i ........
+.......................
0
48 (24 8

........
.......................
$l
0 -
49 Q49
3i
ii +....................... ........
50 Q50
L
........
-.......................
0 31
QT,1
51


........
+.......................
$
1
0
58 Q58
+....................... ........
0 $
1
59 Qm
-

........
........................
60
........................ ........
61
........................ ........
62
........
........................
63
-
APPENDIX 367




Deterministic Sufficient Conditions [ 1441
Table A-6: A40
˜




I Number
˜




Conditions on
. . . . . . . . . . . .o... . . . .o . . . . o . . . . . . ˜
˜




3
Q2
. . . . . . . o---l--- --^^l^^^ -011... . 21
Q3
27
1000100. 01..0000 00000000 0010.1.1
Q4
32
0000001- 01111111 10111100 0100-0-1
Q5
32
Qs 00000011 11111110 11111000 00100000
28
00000001 1..10001 0.0.0101 01000000
Q7
Qs 11111011 . . . 10000 0.1-1111 00111101 28
0111 . . . . 0..11111 1101 . . .0 01 . . . .00 19
Q9
29
00100000 1 . . . 0 0 0 1 11000000 11000010
Qio
Q i i 000 . . . 00 . . . . 1000 0001 . . . 1 0 . . . . . . . 15
Q12 01 .... 01 . . . . 1111 111 .... 0 O...l... 14
Q13 0 . 0 . . . 00 . . . . 1011 111 .... 1 1...1... 14
Q14 0.1 . . . 01 . . . . . . .0 1 . . . . . . . . . . .o . . . 7
Q15 0!1. . . . . . . . . . . ! . . . . . . . . . . . . . . . . . 4
- ....... ....-...
O ! . . . . . . . . . . . .0 . 5
QlS
. . . . . . 1. ................ 3
Q17 0 . - . . . . .
Qis 0 . . . . . . . . . . . . . 0 . ................ 2
................
Qi9 0 . . . . . . . . . . . .! . . 2
&ao ................
0....... ......-. 2
Subtotal 287
˜
˜
APPENDIX
368




Table A-7: n/r, Probabilistic Sufficient Conditions [ 1441

Number
Coritlitions 011 A40
0....... ........ ................ 1
Qai
0....... ........ ................ 1
Q22
1....... ........ . . . . . . . . . . . . . . . . 1
Q23
........ ................
........ 0
Q24 Q44
I. . . . . . .
˜




........ ................ 0
Q45
........ . . . . . . . . . . . . . . . .
J....... 0
Q4fi
I. . . . . . . ........ ................ 1
Q47
J....... ........ ................ 1
Q48
........ ................
K....... 1
Q49
J....... ........ ................ 1
Q50
........ . . . . . . . . . . . . . . . .
K....... 1
Q5i
........ ................
J....... 1
Q52
........ . . . . . . . . . . . . . . . .
K....... 1
&5:3
........ ................
J....... 1
Q54
........ ................
K....... 1
Q55
........ ................
....... 1
J
Q5O
K....... ........ ................ 1
Q57
........ ................
J....... 1
Q5S
........ ................
I....... 1
QSI
........ ................
J....... 1
QbO
........ ................
I. . . . . . . 1
(261
........ ................
J....... 1
Q62
........ ........ ................ 0
Qfxi
Subtotal 19
2
8
316
APPENDIX 369




Table A-8: M I Deterministic Sufficient Conditions [144]
˜




Conditions from Mn
˜




Number
__
. . . . . .0 . . . . . . . . . . . . . . . . . . . . . . . . . (1)
Q-3
- . . . .01 . . . . . . . . . . . . . . . . . . . . . . . . . (3)
&-a
&-1 - . . . .00 . . . . . . . . . . . . . . . . . . . 0 . . . . . (4)
Coiiditions on MI Subtotal: (8)
Qo ! . . .010. . . 1 . . . .0 . . . .0. . . .10. . . . .
˜

˜




9
-- 110. ..o---- 0 1 . . -l... -10. . o 0. 21
Qi
-011111. . .011111 0..Ol..1 011--11. 24
Q2
-011101. . .000100 . . . 00-- 0001000- 26
0
Q3
!loo10. . . . 101111 . . .01110 01010000 25
Q4
- ..0010. 1.10. . 10 11.01100 01010110 25
Q5
! ..lo11- 1.00. .01 10.11110 00. . . . . 1 21
-
Q6
. .00100 0.11 . . 10 1 . . . . . 11 111 . . . -0 19
Q7
Qs - . . 11100 0. . . . .01 0. . - . . 01 110 . . .01 18
- . . . . 111 1 . . .1011 11001.11 11. . . .00 20
Q9
Qio - . .00. . . . . . . 1101 11000.11 110 . . . 11 19
. . . . 1000 0001 . . . . 1 . . . . . . .
Q i i ---oo--- 17
!0111111 0. . . 1111 111 . . . . . 0. . . l... 18
&in
-1000000 1 . . . 1011 111 . . . . . 1 . . .l... 18
Q13
01111101 . . . . . . . . 00. . . . . . . . . . 0 . . . 11
Q14
0.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I

. . . . . . . . . . . .0 . - . . . . . . . . . . . - . . .
Q15
5
O!
Q16
Q17 0.- . . . . . . . . . . 1 . . . . . . . . . . . . . . . . .
. 3
0 . . . . . . . . . . . . .0 . . . . . . . . . . . . . . . . . 2
Qi8
Qi9 0 . . . . . . . . . . . .! . . . . . . . . . . . . . . . . . . 2
Q20 0 . . . . . . . . . . . . . - . . . . . . . . . . . . . . . . . 2
Subtotal 309
.
˜
APPENDIX
370




Table A-9: M I Probabilistic Sufficient Conditions [144]

Conditions on MI Number
.
........
0. . . . . . . . . . . . . . . ........ 1
Q21
........
0............... ........ 1
Q22
1. . . . . . . . . . . . . . . . . . . . . . . ........ 1
Q23
................ ........
........ 0
Q24-Q44
........
I. . . . . . . . . . . . . . . ........ 0
Q45
........
J............... ........ 0
Q46
1. . . . . . . . . . . . . . . ........ ........ 1
I

Q47
........
J . . . . . . . . . . . . . . . ........ 1
Q48
K............... ........ ........ 1
Q49
J............... ........ ........ 1
Q50
K............... ........
........ 1
&51
............... ........
........ 1
J
Q52
K............... ........
........ 1
Q53
........
J............... ........ 1
Q64
........
K............... ........ 1
Q55
........ ........
J............... 1
Q56
........
K............... ........ 1
Q57
........
............... ........ 1
J
Q59
........
1. . . . . . . . . . . . . . . ........ 1
Q59
J............... ........ ........ 1
Q6O
........
1. . . . . . . . . . . . . . . . . . . . . . . 1
1
dZ(j
J............... ........ ........ 1
Q62
................ ........ ........ 0
963
Subtotal 19
TJ restrictions 2
330
Total conditions
APPENDIX 371


Math
A-2
Number Theory
A-2.1
For a positive integer n, the Euler phi function (or totient function), de-
noted $ ( n ) ,
gives the number of positive integers less than n that are relatively
prime to n.
It is not difficult to show that if n = py'p;' . . .pEk is the prime factorization
of the positive integer n, then

i) );
;). . . (1
$(n)= n (1 (1
- - -



Another important fact is that the element x E { 0 , 1 , 2 , .. . , n l} has a
-

multiplicative inverse modulo n if and only if gcd(x, n ) = 1.

Fermat's Little Theorem. If p is a prime number and p does not divide a ,
then c2-l = 1 (mod p ) .

Euler's Theorem. If' gcd(a, n ) = 1, then a@(n) 1 (mod n).
=

Chinese Remainder Theorem. Let mo,ml , . . . , m k - 1 be positive inte-
gers such that for i # j , we have gcd(mi,mj) = 1. Then given inte-
gers ao, a l , . . . , a k - 1 , there is a unique solution x (mod moml... m k - i ) to
the system of simultaneous congruences

...,
x = a o (mod mo), x = a l (mod (mod
x=ak-l mk-1).
ml),



Example. Find x that satisfies the system of congruences

x = 1 (mod 3), x 5), z = 3 (mod 7).
= 2 (mod

We first set M = 3 . 5 . 7 = 105, MO = 105/3 = 35, M1 = 105/5 = 21
and M2 = 105/7= 15. Then we need to solve the congruences
(mod 3)
35yo =1
21y1 = 1 (mod 5)
15y2 = 1 (mod 7).
Easy calculations yield yo = 2 (mod 3 ) , gl = 1 (mod 5) and y2 = 1 (mod 7).
Then the desired solution to the system of congruences is given by

x = 1 . 3 5 . 2 + 2 . 2 1 . 1 + 3 . 1 5 . 1 = 1 5 7 = 5 2 (mod 105)

Euclidean Algorithm. Let TO = a and T I = b be non-negative integers
with b # 0. Suppose that the division algorithm is successively applied to
APPENDIX
372


+
r,+2 with 0 < r,+2 < rJ+l, for j = 0 , 1 , . . . , n - 2,
obtain T, = r,+lq,+l
wherc T, = 0. Then gcd(a, b ) = r,-1, the last non-zero remainder.

Example. Find the greatest common divisor of 27 and 48. Express this gcd
as a linear combination of 27 and 48.
From the Euclidean Algorithm, we have

+ 21
48 = 2 7 . 1
21 . 1 + 6
27
21 = 6 . 3 + 3
6 =3.2+O

which implies gcd(27,48) = 3 . Using back-substitution, we obtain

3 21 - 6 . 3
=
= 21 - (27 21 . 1) ' 3
˜




(48 - 2 7 . 1) - (27 - (48 - 27)) . 3
=
+
= 48 - 27 - (27) . 3 (48) . 3 (27) ' 3
˜




= (48) . 4 - (27) . 7.


A-2.2 Group Theory
* on G,
*)
A group (G. is a non-empty set G, together with a binary operation
such that the following axioms are satisfied:

* is associative.
The binary operation
0



There is an element e E G such that e * I(: = .?: * e for all z E G.
= z,
0


* a = a * a'
For each a G, there is an element a' G such that a' e.
E E =
0



* b = b * a , for all a , b E G.
A group (G, *) is abelian (or commutative) if a

A-2.3 Ring Theory
+
A r m g ( R ,+, .) is a non-empty set R , together with two binary operations
arid . (called addition and multiplication, respectively) defined on R such that
the following axioms are satisfied:

( R ,+, .) is an abelian group.
0


LIiiltiplication is associativc.
0


+ b)c = ac + bc
+ c ) = ab + ac
For all a , b, c E R, we have a(6 and ( a
0

hold.
APPENDIX 373


Linear Algebra
A-2.4
Matrix Operations

Addition of matrices is performed elementwise. For example,


[:211 [4 I:; [; 111
=
+




+
If the matrices A and B do not have the same dimensions, then A B is
undefined.
Suppose A is an m x r matrix, denoted A,,,, and B is an r x n matrix,
Then the product C = AB is an m x n matrix, that is,
denoted B,,,.
C,,, = AmX,BTXn. entry in row i and column j of C is given by the
The
formula
+ ++
+
aioboj ailblj ai2bzj . . . ai,r-lbT-l,j,
where aij is the element in row i and column j of A, and similarly for bij.

[' "1 ["
For example,
-11 = [ 13 -11 '
9 -3
20
3-1
A set of vectors z o , z 1 , . . . , xn_l is linearly independent if
n- 1


i=O

implies that a0 = a1 = . .. = an-l = 0. If the vectors z are not linearly
i
independent, then we say that they are linearly dependent.

Example. Consider the set of vectors




These are linearly dependent, since


I™;[ [:] [8]
[I] =
-
+




However, the set



is linearly independent, since
APPENDIX
3 74


0.
implies that a0 = a1 =




1
Inverse Matrix




-;; : I::
In, .
rf =

'.. 1
0
-0 0
Annotated Bibliography

[l] 3GPP home page, at www . ˜ g p .org/
p
Cited on page 94

[2] E. Aboufadel, Work by the Poles to break the Enigma codes, at
www.gvsu.edu/math/enigma/polish.htm
Cited on page 34

A brief description of the work by the Polish cryptanalysts.
0



[3] G. Alvarez, D. de la Guia, and F. M. y Albert0 Peinado, Akelarre: a
new block cipher algorithm Proceedings of the SAC™96 Workshop, 1996,
pp. 1-14
Cited on pages 160, 163, and 169

[4] R. Anderson, ˜Trusted computing™ frequently asked questions, at
www.cl.cam.ac.uk/-rjal4/tcpa-faq.html
Cited on pages 316 and 380

An entertaining a.nd enlightening discussion of trusted computing,
0

but very one-sided. For a more balanced treatment, see [48].

[5] I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-
key cryptography, Mathematical Research Letters, Vol. 6, 1999, pp. 287-
291
Cited on pages 279 and 284

[6] Barbie, at en.wikipedia.org/wiki/Barbie
Cited on page xiii

Talking Barbie™s infamous “math class is tough” quote, which is
often misquoted as, “math is hard.”

[7] T. Barr, Invitation to Cryptology, First edition, Prentice Hall, 2002
Cited on page 1

A nice introduction to cryptology for the general reader.
0




375
ANNOTATEDBIBLIOGR,APHY
376


[8] F. L. Bauer, Decrypted Secrets: Methods and Maxims of Cryptology,
third edition, Springer, 2002
Cited on pages 1 and 5
[9] Nl. Bellare, S. Goldwasser, and D. Micciaricio "Pseudo-random"
number generation within cryptographic algorithms: the DDS case,
Advances in Cryptology, Proceedings of Crypto 1997, LNCS 1294,
B. S. Kaliski, Jr., Ed., Springer-Verlag, 1997, pp. 277-291, at
theory.lcs.mit.edu/"cis/pubs/shafi/l997-lncs-bgm.pdf
Cited on page 80
[lo] nl. Bellare and P. Rogaway, Optimal asymmetric encryption-how to
encrypt with RSA, at www. cse .ucsd.edu/users/mihir/papers/oae. pdf
Cited on page 291
[ll] S. M. Bellovin and M. Merritt, Encrypted key exchange: password-
based protocols secure against dictionary attacks, at
www.windowsecurity.com/uplarticle/4/neke.p˜
Cited on page 278
[ l a ] D. J. Bernstein, Cache-timing attacks on AES, at
cr.yp.to/antiforgery/cachetiming-20050414.pdf
Cited on pages 342 and 353
[13] E. Biham and P. Kocher, A known plaintext attack on the PKZIP
stream cipher, Fast Software Encryption '94, LNCS 1008, pp. 144-153,
B. Preneel, Ed., Springer-Verlag, 1994
Cited on pages 111, 115, 118, and 378
The ideas are undeniably there, but the details arc incredibly dif-
0

ficult to pull out of this cryptic paper; see the implementation
in [30] for help.

[14] E. Biham and A. Shamir, Differential cryptanalysis of Feal and N-hash,
Advances in C;ryptolog?j, Proceedings of Eurocrypt 1991, LNCS 547,
D. W. Davies, Ed., Springer-Verlag, 1991, pp. 1-16
Cited on pages 170 and 171
[15] J . Birman, K. KO, and S. Lec, A new approach to the word and conju-
Racy problems in the braid groups, Advances in Mathematics, No. 139,
1998, pp. 322-353
Cited on page 283
[I61 J. Black, M. Cochran, and T. Highland, A study of the MD5 attacks:
insights and improvements, at
www.cs.colorado.edu/"jrblack/papers/md5e-full.pdf
Cited on pages 230, 237, and 250
ANNOTATEDBIBLIOGRAPHY 377


[17] I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography,
London Mathematical Society Lecture Notes 265, Cambridge University
Press, 2002
Cited on page 284

[18] M. Blaze, Quantize wrapper library, at
islab.oregonstate.edu/documents/People/blaze
Cited on page 352

[19] D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices of
the AMS, February 1999, at www. ams. org/notices/199902/boneh.pdf
Cited on pages 285, 287, 288, and 354

[20] J. Borst, B. Preneel, and J. Vandewalle, On the time-memory tradeoff
between exhaustive key search and table precomputation, at
www.esat.kuleuven.ac.be/-borst/downloadable/tm.ps.gz
Cited on page 142

An extension of Hellman's original TMTO work. This approach
0

allows for an efficient distributed attack.

[all D. M. Bressoud, Factorization and Primality Testing, Springer-Verlag,
New York, 1989
Cited on page 287

[22] D. Brumley and D. Boneh, Remote timing attacks are practical, at
crypto.stanford.edu/"dabo/papers/ssl-timing.pdf
Cited on pages 335, 349, 350, 351, and 352

A timing attack on the RSA implementation in OpenSSL.
0


[23] S. Budiansky, Battle of Wits, The Free Press, 2000
Cited on pages 26, 37, 38, 48, and 52
[241 D. A. Buell, Montgomery multiplication, at
www.cse.sc.edu/˜buell/csce557/Dlecturenotes/montgomery.pdf
Cited on pages 338 and 339

[25] D. M. Burton, Elementary Number Theory, second edition,
Wm. C. Brown Publishers, 1989
Cited on pages 323 and 332

[26] A. Carlson, Simulating the Enigma cypher machine, at
homepages.tesco.net/-andycarlson/enigma/simulating-enigma.html
Cited on page 28

Describes the double stepping well.
ANNOTATED BIBLIOGRAPHY
378


[27] F. Chabaud and A. Joux, Differential collisions in SHA-0, Advances
in Cryptology, Proceedings of Crypto 1998, LNCS 1462, H. Krawczyk,
Ed., Springer-Verlag, 1998
Citctl on page 237

[28] W. 0. Chan, Sigaba, Master's Thesis, Department of Computer Sci-
ence, San Jose State University, 2006
Cited on pages 64. 67, and 68

[29] R. Churchhouse, Codes and Czphers, Cambridge University Press, 2002
Cited on page 26

This contains a nice overview of some classical crypto. In partic-
0

ular, a few chapters are devoted to some of the World War I1
crypto--machine systems.

[30] P. Conrad, pkcrack, at
www.unix-ag.uni-kl.de/"conrad/krypto/pkcrack.html
Cited on pages 111 and 376

Without this software-which implements Biham and Kocher's
0

PKZIP attack- -or something comparable, deciphering Biham and
Kocher's paper [13] would be well-nigh impossible. Conrad even
includes some valuable comments for the most confusing parts.

[31] D. Coppersmith, Small solutions to polynomial equations, and low
exponent RSA vulnerabilities, Journal of Cryptology, Vol. 10, 1997,
pp. 233--260
Cited on pages 343 and 350

[32] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction
to Algorithms, second edition, MIT Press, 2001
Cited on pages 327 and 333

[33] ill. Dashu, Xorguinas y Celestinas, excerpt from Secret History of the
Watches, at
www.suppressedhistories.net/secret_history/xorguinas.html
Cited on page 160

[34] M. Daum, Cryptanalysis of hash functions of the MD4-family, Disser-
tation zur Erlangurig des Grades eines Doktor der Naturwissenschaften
der Ruhr-Universit at Bochum am Fachbereich Mathematik, at
www.cits.ruhr-uni-bochum.de/imperia/md/content/magnus/
dissmd4.pdf
Cited on pages 194, 208: 212, 230, 233, 235, 237, 238, 250, and 392
ANNOTATEDBIBLIOGRAPHY 379


An excellent source for background information on MD4 and MD5
0

collision attacks. This dissertation is readable and provides a
wealth of relevant information on hash function cryptanalysis.
Daum™s work was supervised by the late Hans Dobbertin.

[35] M. Daum and S. Lucks, Attacking hash functions by poisoned
messages--˜the story of Alice and her boss™, at
www.cits.rub.de/MD5Collisions/
Cited on page 253

[36] H. Delfs and H. Knebl, Introduction to Cryptography: Principles and
Applications, Springer-Verlag, 2002
Cited on page 291

[37] Y. Desmedt, What happened with knapsack cryptographic schemes?,
Performance Limits in Communication, Theory and Practice,
J. K. Skwirzynski, ed., Kluwer, pp. 113-134, 1988
Cited on page 275

[38] W. Diffie and M. E. Hellman, New directions in cryptography, IEEE
Transactions on Information Theory, Vol. IT-22, No. 6, 1976, pp. 644-
654
Cited on page 276

[39] W. Diffie, P. C. van Oorschot, and M. Wiener, Authentication and
authenticated key exchanges, Designs, Codes and Cryptography, Vol. 2,
1992, pp. 107-125
Cited on page 278

[40] J. D. Dixon, Asymptotically fast factorization of integers, Mathematics
of Computation, Vol. 36, 1981, pp. 255-260
Cited on page 317

[41] H. Dobbertin, Cryptanalysis of MD4, Proceedings of the Third Inter-
national Workshop on Fast Software Encryption, LNCS 1039, D. Goll-
mann, Ed., Springer-Verlag, 1996, pp. 53-69
Cited on page 208

[42] H. Dobbertin, Cryptanalysis of MD4, Journal of Cryptology, Vol. 11,
NO. 4, 1998, pp. 253-271
Cited on pages 199, 208, 210, 216, 219, 224, 225, 231, and 260

A somewhat difficult attack, but a very well-written article-an
0

exception t o the rule in the cryptanalysis literature.
ANNOTATED BIBLIOGRAPHY
380


[43] J. R. Durbin, Modern Algebra: An Introduction, fifth edition, John
Wiley & Sons, Inc., 2004
Cited on page 86

[44]T. ElGanial, A public key cryptosystein and a signature scheme
based on discrete logarithms. Advances in Cryptology, Proceedings of
Crypto 1984, LNCS 196, Springer-Verlag, 1985, pp. 10-18
Cited on page 307
[45] J. H. Ellis, The possibility of secure nori-secret digital encryption, CESG
Report, January 1970
Cited on page 265
Ellis was the first to suggest the possibility of public key cryptog-
0

raphy.
[46] Enigma, at www .nsa.gov/public/publi00007. cfm
Cited on page 27
[47] Enigma Machine, Wikipetlia, the free encyclopedia, at
en.wikipedia.org/wiki/Enigma-machine
Cited on page 26
[48] P. Ericson, TCPA/TCG and NGSCB: benefits and risks for users,
School of Humanities and Informatics University of Skovde, Sweden,
2004, at
pericson.com/writings/tcpa-tcg-ngscb/tcpa-tcg_and_ngscb.pdf
Cited on pages 316 and 375
A balanced and highly readable discussion of trusted computing
0

(TC). See [4] for the anti-trusted computing viewpoint.
[49] W. Feller, An Introduction t o Probability Theory and Its Applications,
third edition, Wiley, 1968
Cited on pages 185 arid 141
A classic source for information on discrete probability.
0


[50] N. Ferguson and B. Schneier, Cryptanalysis of Akelarre, Proceedings of
th,e SAC'S7 workshop, 1997, pp. 201-212
Cited on page 160
[51] S. Fluhrer, I. Mantin, and A. Shaniir, Weaknesses in the key scheduling
algorithm of ltC4, at www .drizzle.com/"aboba/IEEE/rc4˜ksaproc.pdf
Cited on pages 105, 110, 122, and 385
Several attacks on RC4 are discussed. Mantin's thesis [96] is much
0

clearer and easier t'o rcad.
ANNOTATEDBIBLIOGRAPHY 381


[52] W. Freeman, G. Sullivan, and F. Weierud, Purple revealed: simula-
tion and computer-aided cryptanalysis of Angooki Taipu B, Cryptolo-
gia, Vol. XXVII, No. 1, January 2003, pp. 1-43
Cited on pages 39, 46, and 49

The most detailed source of information on the Purple cipher.
0


[53] F. Fugate, Frank Rowlett, and David Kahn, at
cryptome.org/rowlett-kahn.htm
Cited on page 383

Fugate, who claims to be Rowlett's nephew, describes an attempt
0

by Kahn to coerce Rowlett into divulging classified information.

[54] E. Fujisaki and T. Okamoto, Secure integration of asymmetric and
symmetric encryption schemes, Advances in Cryptology, Proceedings
of Crypto 1999, LNCS 1666, M. Wiener, Ed., Springer-Verlag, 1999,
pp. 537-554
Cited on page 304

[55] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide
to the Theory of N P - Completeness, W. H. Freeman & Company, 1979
Cited on page 267

[56] B. Gates, The Road Ahead, Penguin, 1995
Cited on page 316

[57] I. Goldberg and D. Wagner, Architectural considerations for cryptana-
lytic hardware, at
www.comms.scitech.susx.ac.uk/fft/crypto/paper.pdf
Cited on page 82

[58] J. GoliC, Correlation via linear sequential circuit approximation of com-
biners with memory, Advances in Cryptology, Proceedings of EURO-
CRYPT '92, LNCS 658, 1993, pp. 113-123
Cited on page 93

[59] S. W. Golornb, Shift Register Sequences, Aegean Park Press, 1981 (re-
vised edition)
Cited on page 86

[60] B. Goren, RSA: practical public-key cryptography, at
www.trumpetpower.com/Papers/Crypto/RSA
Cited on page 284

[61] M. Goresky and A. M. Klapper, Fibonacci and Galois representations of
feedback-with-carry shift registers, IEEE Transactions o n Information
ANNOTATED BIBLIOGRAPHY
382


Theory, Vol. 48, No. 11, November 2002, pp. 2826-2836
Cited on page 83

[62] F. G. Gustavson, Analysis of the Berlekamp-Massey linear feedback
shift-register synthesis algorithm, IBM Journal of Research and Devel-
opment, Vol. 20, May 1976, pp. 204-212
Cited on page 85

[63] D. Hamer, Enigma: actions involved in the 'double-stepping' of the
middle rotor, Cr:yptologia, Vol. 21, No. 1, January 1997, pp. 47-50, at
www.eclipse.net/"dhamer/downloads/rotorpdf.zip
Cited on page 28

[64] P. Hawkes, M. Paddon, arid G. G. Rose, Musings on the Wang et al.
MD5 collision, at eprint . iacr .org/2004/264 .pdf
Cited on pages 229, 238, 239, 240, 241, 242, 243, 244, 245, 247, and 392

A remarkable paper arid an absolute necessity for understanding
0

the intricate details of Wang's attack.

[65] M. Hellman, A cryptanalytic time-memory tradeoff, IEEE Transactions
on Information Theory, vol. 26, pp. 401-406, 1980
Cited on page 133

[66] T. Henderson, ARC shikreware license, at
www.esva.net/-thom/arclicense.html
Cited on page 110

[67] L. S. Hill, Cryptography in an algebraic alphabet, Arnerican Mathe-
m,atical Month,ly, No. 36, 1929, pp. 306 -312
Cited on page 16

[68] J. Hoffstein, J. Pipher, and J . H. Silverman, NTRU: A ring based public
key cryptosystem, Algorithmic Number Theory: Third International
Sy7nposiu7n Proceedings of ANTS-111, LNCS 1423, J. P. Buhler, Ed.,
Springer-Verlag, 1998, pp. 267-288
Cited on pages 293 arid 299

[69] J . Hughes and A. Tannenbaum, Length-based attacks for certain group
based encryption rewriting systems, preprint, 2000
Cited on page 283

[70] IBM Rescarch, Horst Feistel, at
domino.watson.ibm.com/comm/pr.nsf/pages/bio.feistel.html
Citcd on page 131
ANNOTATEDBIBLIOGRAPHY 383


[71] Investigation of the Pearl Harbor attack, Report of the Joint Committee
on the Investigation of the Pearl Harbor Attack, Part I. Diplomatic
Background, at www.ibiblio.org/pha/pha/congress/part-l.htm1
Cited on page 39

[72] Japanese “Fourteen Part” message of December 7, 1941, at
www.ibiblio.org/hyperwar/PTO/Dip/Fourteen.html
Cited on page 38

[73] E. Jaulmes and A. Joux, A chosen-ciphertext attack against NTRU,
Advances in Cryptology, Proceedings of Crypto 2000, LNCS 1880,
M. Blaze, Ed., Springer-Verlag, 2000, pp. 20-35
Cited on pages 302 and 304

[74] D. Kahn, T h e Codebreakers: T h e Story of Secret Writing, Macmillan,
1967
Cited on pages 1 and 5

The most complete source for crypto history prior to its original
0

publication date of 1967. But it is important to remember that
most of the World War I1 crypto history was still classified in 1967
and it shows. In particular, Kahn slights Rowlett and, disturbingly,
it appears that he knew better at the time [53].

[75] S. A. Kallis, Jr., Codes and cipher, at www. otr.com/ciphers .shtml
Cited on page 38

[76] A. Karatsuba and Y. Ofman. Multiplication of many-digital numbers
by automatic computers, Doklady Akad. Nauk SSSR,Vol. 145, pp. 293-
294, 1962 (translation in Physics-Doklady, Vol. 7, pp. 595-596, 1963)
Cited on page 341

[77] E. Kasper, Linear cryptanalysis of stream ciphers, at
www.tcs.hut.fi/Studies/T-79.514/slides/S4.Kasper.lc-stream.pdf
Cited on page 93

A misleading title since it has nothing to do with linear crypt-
0

analysis. Nevertheless, these notes provide an excellent overview
of correlation attacks in general, with some details regarding such
attacks on A5/1 (used in GSM) and EO (used in Bluetooth).

[78] P. Katz, appnote.txt, at
search.cpan.org/src/NEDKONZ/Archive-Zip-l.14/docs/Appnote.txt
Cited on page 111
ANNOTATEDBIBLIOGRAPHY
384


[79] C. Kaufman, R. Perlman, and M. Speciner, Network Security, second
edition, Prentice Hall, 2002
Cited on page 194

[80] J. Kelsey and T. Kohno, Herding hash functions and the Nostradamus
attack, at eprint.iacr.org/2005/28l.pdf
Cited on pages 203, 204, 206, and 207

[81] V. Klima, Finding MD5 collisions on a notebook PC using multi-
message modifications, at eprint . iacr .org/2005/102 .pdf
Cited on pages 229. 230. 248. and 253

[82] L. R. Knudsen and V. Rijmen, Two rights sometimes make a wrong,
Proceedings of the SAC™97 workshop, 1997, pp. 213-223
Cited on pages 132, 160, 166, and 169

A clever title, but the details are sketchy.
0



[83] N. Koblitz, A Course in Number Theory und Cryptography, second edi-
tion, Springer-Verlag, 1994
Cited on page 308

[84] N. Koblitz, A. J. Menezes, Y. H. Wu, and R. 3 . Zuccherato, Algebraic
Aspects of Cryptography, Algorithms and Computation in Mathematics,
Springer-Verlag, 2004
Cited on page 284

[85] P. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA,
DSS, and other systems, at

<<

. 15
( 16)



>>