Bard Algebraic Cryptanalysis

1. Auflage 2009
ISBN: 978-0-387-88757-9
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 356 Seiten

Algebraic Cryptanalysis bridges the gap between a course in cryptography, and being able to read the cryptanalytic literature. This book is divided into three parts: Part One covers the process of turning a cipher into a system of equations; Part Two covers finite field linear algebra; Part Three covers the solution of Polynomial Systems of Equations, with a survey of the methods used in practice, including SAT-solvers and the methods of Nicolas Courtois. Topics include: Analytic Combinatorics, and its application to cryptanalysis The equicomplexity of linear algebra operations Graph coloring Factoring integers via the quadratic sieve, with its applications to the cryptanalysis of RSA Algebraic Cryptanalysis is designed for advanced-level students in computer science and mathematics as a secondary text or reference book for self-guided study. This book is suitable for researchers in Applied Abstract Algebra or Algebraic Geometry who wish to find more applied topics or practitioners working for security and communications companies.

Autoren/Hrsg.

Bard, Gregory

Inhaltsverzeichnis

1;EAE lgebraic Cryptanalysis;2
1.1;Preface;5
1.1.1;Why this Book was Written;6
1.1.2;Advice for Graduate Students;7
1.2;Dedication;8
1.3;Acknowledgements;9
1.3.1;If you Find Any Errors. . .;13
1.4;Contents;14
1.5;List of Tables;24
1.6;List of Figures;25
1.7;List of Algorithms;26
1.8;List of Abrreviations;27
1.9;Introduction: How to Use this Book;28
1.9.1;Part One;28
1.9.2;Part Two;29
1.9.3;Part Three;31
1.9.3.1;Appendices;32
1.9.3.2;Suggested Chapter Ordering;33
1.9.3.3;Theorem Numbering;33
1.10;Cryptanalysis;34
1.11;The Block Cipher Keeloq and Algebraic Attacks;35
1.11.1;Notational Convention;35
1.11.2;2.1 What is Algebraic Cryptanalysis?;36
1.11.2.1;2.1.1 The CSP Model;36
1.11.3;2.2 The Keeloq Specification;36
1.11.4;2.3 Modeling the Non-linear Function;37
1.11.4.1;2.3.1 I/O Relations and the NLF;38
1.11.5;2.4 Describing the Shift-Registers;38
1.11.5.1;2.4.1 Disposing of the Secret Key Shift-Register;39
1.11.5.2;2.4.2 Disposing of the Plaintext Shift-Register;39
1.11.5.2.1;Change of Indexing;39
1.11.6;2.5 The Polynomial System of Equations;39
1.11.7;2.6 Variable and Equation Count;40
1.11.8;2.7 Dropping the Degree to Quadratic;40
1.11.9;2.8 Fixing or Guessing Bits in Advance;41
1.11.10;2.9 The Failure of a Frontal Assault;42
1.12;The Fixed-Point Attack;43
1.12.1;3.1 Overview;43
1.12.1.1;3.1.1 Notational Conventions;43
1.12.1.2;3.1.2 The Two-Function Representation;43
1.12.1.3;3.1.3 Acquiring an f (8)k -oracle;44
1.12.2;3.2 The Consequences of Fixed Points;44
1.12.3;3.3 How to Find Fixed Points;45
1.12.4;3.4 How far must we search?;46
1.12.4.1;3.4.1 With Analytic Combinatorics;47
1.12.4.2;3.4.2 Without Analytic Combinatorics;49
1.12.5;3.5 Comparison to Brute Force;49
1.12.6;3.6 Summary;50
1.12.7;3.7 Other Notes;51
1.12.7.1;3.7.1 A Note about Keeloq’s Utilization;51
1.12.7.2;3.7.2 RPA vs KPA vs CPA;52
1.12.8;3.8 Wagner’s Attack;52
1.12.8.1;3.8.1 Later Work on Keeloq;53
1.13;Iterated Permutations;55
1.13.1;4.1 Applications to Cryptography;55
1.13.2;4.2 Background;56
1.13.2.1;4.2.1 Combinatorial Classes;56
1.13.2.2;4.2.2 Ordinary and Exponential Generating Functions;56
1.13.2.3;4.2.3 Operations on OGFs;57
1.13.2.3.1;4.2.3.1 Simple Sum;57
1.13.2.3.2;4.2.3.2 Cartesian Product;57
1.13.2.3.3;4.2.3.3 Sum with Non-Empty Intersection;58
1.13.2.3.4;4.2.3.4 Semiring of Combinatorial Classes;58
1.13.2.3.5;4.2.3.5 Sequences of Objects;59
1.13.2.3.6;4.2.3.6 Other Operations;60
1.13.2.4;4.2.4 Examples;60
1.13.2.4.1;4.2.4.1 Permutations in General;60
1.13.2.4.2;4.2.4.2 The Non-Negative Integers;60
1.13.2.4.3;4.2.4.3 Partitions into Boxes;61
1.13.2.4.4;4.2.4.4 Cycles;61
1.13.2.4.5;4.2.4.5 Morse Code;62
1.13.2.4.6;4.2.4.6 Zig-Zag Arrangement;62
1.13.2.5;4.2.5 Operations on EGFs;62
1.13.2.5.1;4.2.5.1 The Labelled Product;62
1.13.2.5.2;4.2.5.2 Random Permutations;64
1.13.2.5.3;4.2.5.3 Asymptotic Probabilities;64
1.13.2.6;4.2.6 Notation and Definitions;65
1.13.3;4.3 Strong and Weak Cycle Structure Theorems;66
1.13.3.1;4.3.1 Expected Values;67
1.13.4;4.4 Corollaries;69
1.13.4.1;4.4.1 On Cycles in Iterated Permutations;71
1.13.4.1.1;4.4.1.1 An Example;71
1.13.4.2;4.4.2 Limited Cycle Counts;72
1.13.4.3;4.4.3 Monomial Counting;73
1.13.5;4.5 Of Pure Mathematical Interest;73
1.13.5.1;4.5.1 The Sigma Divisor Function;74
1.13.5.2;4.5.2 The Zeta Function and Ap´ery’s Constant;74
1.13.5.3;4.5.3 Greatest Common Divisors and Cycle Length;75
1.13.6;4.6 Highly Iterated Ciphers;75
1.13.6.1;4.6.1 Distinguishing Iterated Ciphers;76
1.13.6.1.1;4.6.1.1 Repeating the Attack;77
1.13.6.1.2;4.6.1.2 A General Maxim:;78
1.13.6.2;4.6.2 A Key Recovery Attack;78
1.14;Stream Ciphers;81
1.14.1;5.1 The Stream Ciphers Bivium and Trivium;81
1.14.1.1;5.1.1 Background;81
1.14.1.1.1;5.1.1.1 What is a Stream Cipher?;81
1.14.1.1.2;5.1.1.2 What was eSTREAM?;82
1.14.1.1.3;5.1.1.3 What is Trivium?;84
1.14.1.1.4;5.1.1.4 Secret Key versus Initial State;85
1.14.1.1.5;5.1.1.5 Initialization Stage in Trivium;86
1.14.1.1.6;5.1.1.6 Two Types of Attack;86
1.14.1.1.7;5.1.1.7 What is Bivium?;87
1.14.1.2;5.1.2 Bivium as Equations;87
1.14.1.2.1;5.1.2.1 Features of these Equations;90
1.14.1.3;5.1.3 An Excellent Trick;90
1.14.1.4;5.1.4 Bivium-A;91
1.14.1.5;5.1.5 A Notational Issue;91
1.14.1.6;5.1.6 For Further Reading;91
1.14.2;5.2 The Stream Cipher QUAD;92
1.14.2.1;5.2.1 How QUAD Works;92
1.14.2.2;5.2.2 Proof of Security;93
1.14.2.2.1;5.2.2.1 Computationally Indistinguishable;93
1.14.2.2.2;5.2.2.2 The Objective;94
1.14.2.2.3;5.2.2.3 The Underlying Hard Problem: A Pre-Image Finder;94
1.14.2.2.4;5.2.2.4 Outline of a Proof;95
1.14.2.2.5;5.2.2.5 Exploratory Example;96
1.14.2.3;5.2.3 The Yang-Chen-Bernstein-Chen Attack against QUAD;98
1.14.2.3.1;5.2.3.1 The Combination of Wiedemann and XL-II;98
1.14.2.3.2;5.2.3.2 The Attack Itself;100
1.14.2.4;5.2.4 Extending to GF(16);101
1.14.2.4.1;5.2.4.1 An Exercise;101
1.14.2.4.2;5.2.4.2 The Solution: Direct Version;101
1.14.2.4.3;5.2.4.3 Another look at Fix-XL;102
1.14.2.5;5.2.5 For Further Reading;103
1.14.3;5.3 Conclusions for QUAD;104
1.15;Linear Systems Mod 2;105
1.16;Some Basic Facts about Linear Algebra overGF(2);106
1.16.1;6.1 Sources;106
1.16.2;6.2 Boolean Matrices vs GF(2) Matrices;106
1.16.2.1;6.2.1 Implementing with the Integers;107
1.16.3;6.3 Why is GF(2) Different?;107
1.16.3.1;6.3.1 There are Self-Orthogonal Vectors;107
1.16.3.2;6.3.2 Something that Fails;108
1.16.3.3;6.3.3 The Probability a Random Square Matrix Singular orInvertible;109
1.16.4;6.4 Null Space from the RREF;110
1.16.5;6.5 The Number of Solutions to a Linear System;111
1.17;The Complexity of GF(2)-Matrix Operations;114
1.17.1;7.1 The Cost Model;114
1.17.1.1;7.1.1 A Word on Architecture and Cross-Over;115
1.17.1.2;7.1.2 Is the Model Trivial?;116
1.17.1.3;7.1.3 Counting Field Operations;116
1.17.1.4;7.1.4 Success and Failure;117
1.17.2;7.2 Notational Conventions;117
1.17.3;7.3 To Invert or to Solve?;118
1.17.4;7.4 Data Structure Choices;119
1.17.4.1;7.4.1 Dense Form: An Array with Swaps;119
1.17.4.2;7.4.2 Permutation Matrices;119
1.17.5;7.5 Analysis of Classical Techniques with our Model;121
1.17.5.1;7.5.1 Na¨ ve Matrix Multiplication;121
1.17.5.2;7.5.2 Matrix Addition;121
1.17.5.3;7.5.3 Dense Gaussian Elimination;121
1.17.5.4;7.5.4 Back-Solving a Triangulated Linear System;123
1.17.6;7.6 Strassen’s Algorithms;124
1.17.6.1;7.6.1 Strassen’s Algorithm for Matrix Multiplication;125
1.17.6.2;7.6.2 Misunderstanding Strassen’s Matrix Inversion Formula;126
1.17.7;7.7 The Unsuitability of Strassen’s Algorithm for Inversion;126
1.17.7.1;7.7.1 Strassen’s Approach to Matrix Inversion;127
1.17.7.2;7.7.2 Bunch and Hopcroft’s Solution;128
1.17.7.3;7.7.3 Ibara, Moran, and Hui’s Solution;128
1.18;On the Exponent of Certain Matrix Operations;131
1.18.1;8.1 Very Low Exponents;131
1.18.2;8.2 The Equicomplexity Theorems;132
1.18.2.1;8.2.1 Starting Point;133
1.18.2.2;8.2.2 Proofs;133
1.18.3;8.3 Determinants and Matrix Inverses;142
1.18.3.1;8.3.1 Background;142
1.18.3.2;8.3.2 The Baur-Strassen-Morgenstern Theorem;144
1.18.3.2.1;8.3.2.1 The Computational Model;145
1.18.3.2.2;8.3.2.2 Theorem and Proof;145
1.18.3.2.2.1;Superfluous Operations:;146
1.18.3.2.2.2;Useful Operations:;146
1.18.3.2.2.3;Notation;147
1.18.3.2.2.4;Case 1: Sum of Two Distinct Variables;147
1.18.3.2.2.5;Case 2: Sum of a Variable with Itself;147
1.18.3.2.2.6;Case 3: Sum of a Variable and a Constant;148
1.18.3.2.2.7;Case 4: Sum of a Constant and a Variable;148
1.18.3.2.2.8;Case 5: Difference of Two Distinct Variables;148
1.18.3.2.2.9;Case 6: Deducting a Constant from a Variable;149
1.18.3.2.2.10;Case 7: Deducting a Variable from a Constant;149
1.18.3.2.2.11;Case 8: Product of Two Distinct Variables;149
1.18.3.2.2.12;Case 9: Product of a Variable with Itself;150
1.18.3.2.2.13;Case 10: Product of a Constant and a Variable;150
1.18.3.2.2.14;Case 11: Product of a Variable and a Constant;151
1.18.3.2.2.15;Case 12: Quotient of Two Distinct Variables;151
1.18.3.2.2.16;Case 13: A Constant Divided by a Variable;151
1.18.3.2.2.17;Case 14: A Variable Divided by a Constant;152
1.18.3.2.2.18;The Base Case;152
1.18.3.2.2.19;Considering s and h also;153
1.18.3.2.3;8.3.2.3 A Running Example;153
1.18.3.2.4;8.3.2.4 Dividing by Zero;155
1.18.3.2.5;8.3.2.5 Impossibility of the Hessian;155
1.18.3.3;8.3.3 Consequences for the Determinant and Inverse;156
1.19;The Method of Four Russians;157
1.19.1;9.0.4 The Fair Coin Assumption;158
1.19.2;9.1 Origins and PreviousWork;158
1.19.2.1;9.1.1 Strassen’s Algorithm;159
1.19.3;9.2 Rapid Subspace Enumeration;159
1.19.4;9.3 The Four Russians Matrix Multiplication Algorithm;161
1.19.4.1;9.3.1 Role of the Gray Code;161
1.19.4.2;9.3.2 Transposing the Matrix Product;162
1.19.4.3;9.3.3 Improvements;162
1.19.4.4;9.3.4 A Quick Computation;163
1.19.4.5;9.3.5 M4RM Experiments Performed by SAGE Staff;163
1.19.4.6;9.3.6 Multiple Gray-Code Tables and Cache Management;165
1.19.5;9.4 The Four Russians Matrix Inversion Algorithm;165
1.19.5.1;9.4.1 Stage 1:;165
1.19.5.2;9.4.2 Stage 2:;166
1.19.5.3;9.4.3 Stage 3:;166
1.19.5.4;9.4.4 A Curious Note on Stage 1 of M4RI;167
1.19.5.5;9.4.5 Triangulation or Inversion?;169
1.19.6;9.5 Exact Analysis of Complexity;169
1.19.6.1;9.5.1 An Alternative Computation;170
1.19.6.2;9.5.2 Full Elimination, not Triangular;171
1.19.6.3;9.5.3 The Rank of 3k Rows, or Why k+e is not Enough;172
1.19.6.4;9.5.4 Using Bulk Logical Operations;173
1.19.7;9.6 Experimental and Numerical Results;173
1.19.8;9.7 M4RI Experiments Performed by SAGE Staff;175
1.19.8.1;9.7.1 Determination of k;175
1.19.8.2;9.7.2 The Transpose Experiment;175
1.19.9;9.8 PairingWith Strassen’s Algorithm for Matrix Multiplication;175
1.19.9.1;9.8.1 Pairing M4RI with Strassen;176
1.19.10;9.9 Higher Values of q;176
1.19.10.1;9.9.1 Building the Gray Code over GF(q);176
1.19.10.2;9.9.2 Other Modifications;177
1.19.10.3;9.9.3 Running Time;177
1.19.10.4;9.9.4 Implementation;178
1.20;The Quadratic Sieve;183
1.20.1;10.1 Motivation;183
1.20.1.1;10.1.1 A View of RSA from 60,000 feet;184
1.20.1.2;10.1.2 Two Facts from Number Theory;185
1.20.1.3;10.1.3 Reconstructing the Private Key from the Public Key;185
1.20.2;10.2 Trial Division;187
1.20.2.1;10.2.1 Other Ideas;189
1.20.2.1.1;10.2.1.1 Classification by Difficulty;189
1.20.2.1.2;10.2.1.2 Easy Factorization;190
1.20.2.1.3;10.2.1.3 Testing Divisibility with GCDs;190
1.20.2.2;10.2.2 Sieve of Eratosthenes;191
1.20.2.2.1;10.2.2.1 Smooth Version;192
1.20.2.2.1.1;An Interesting Trick;192
1.20.3;10.3 Theoretical Foundations;193
1.20.4;10.4 The Na ve Sieve;194
1.20.4.1;10.4.1 An Extended Example;195
1.20.5;10.5 The Gödel Vectors;195
1.20.5.1;10.5.1 Benefits of the Notation;196
1.20.5.2;10.5.2 Unlimited-Dimension Vectors;197
1.20.5.3;10.5.3 The Master Stratagem;197
1.20.5.4;10.5.4 Historical Interlude;197
1.20.5.5;10.5.5 Review of Null Spaces;198
1.20.5.6;10.5.6 Constructing a Vector in the Even-Space;199
1.20.6;10.6 The Linear Sieve Algorithm;200
1.20.6.1;10.6.1 Matrix Dimensions in the Linear & Quadratic Sieve;200
1.20.6.2;10.6.2 The Running Time;202
1.20.7;10.7 The Example, Revisited;202
1.20.8;10.8 Rapidly Generating Smooth Squares;204
1.20.8.1;Quadratic Residues;205
1.20.8.1.1;10.8.1 New Strategy;205
1.20.9;10.9 Further Reading;207
1.20.10;10.10 Historical Notes;207
1.21;Polynomial Systems and Satisfiability;208
1.22;Strategies for Polynomial Systems;209
1.22.1;11.1 Why Solve Polynomial Systems of Equations over FiniteFields?;209
1.22.2;11.2 Universal Maps;211
1.22.3;11.3 Polynomials over GF(2);213
1.22.3.1;11.3.1 Exponents: x2 = x;213
1.22.3.2;11.3.2 Equivalent versus Identical Polynomials;213
1.22.3.3;11.3.3 Coefficients;214
1.22.3.4;11.3.4 Linear Combinations;214
1.22.4;11.4 Degree Reduction Techniques;214
1.22.4.1;11.4.1 An Easy but Hard-to-State Condition;215
1.22.4.2;11.4.2 An Algorithm that meets this Condition;216
1.22.4.3;11.4.3 Interpretation;217
1.22.4.4;11.4.4 Summary;218
1.22.4.5;11.4.5 Detour: Asymptotics of the “Choose” Function;218
1.22.4.6;11.4.6 Complexity Calculation;219
1.22.4.7;11.4.7 Efficiency Note;220
1.22.4.8;11.4.8 The Greedy Degree-Dropper Algorithm;220
1.22.4.9;11.4.9 Counter-Example for Linear Systems;221
1.22.5;11.5 NP-Completeness of MP;221
1.22.5.1;One Last Interesting Thought;224
1.22.6;11.6 Measures of Difficulty in MQ;225
1.22.6.1;11.6.1 The Role of Over-Definition;225
1.22.6.2;11.6.2 Ultra-Sparse Quadratic Systems;225
1.22.6.2.1;An Interesting Observation;226
1.22.6.3;11.6.3 Other Views of Sparsity;227
1.22.6.3.1;Connection To Linear Sparsity;227
1.22.6.3.2;Memory Usage;227
1.22.6.3.3;SAT Solvers;227
1.22.6.4;11.6.4 Structure;227
1.22.7;11.7 The Role of Guessing a Few Variables;228
1.22.7.1;11.7.1 Measuring Infeasible Running Times;228
1.22.7.2;11.7.2 Fix-XL;229
1.23;Algorithms for Solving Polynomial Systems;230
1.23.1;12.1 A Philosophical Point on Complexity Theory;230
1.23.2;12.2 Gröbner Bases Algorithms;231
1.23.2.1;12.2.1 Double-Exponential Running Time;231
1.23.2.2;12.2.2 Remarks about Gröbner Bases;231
1.23.3;12.3 Linearization;232
1.23.4;12.4 The XL Algorithm;234
1.23.4.1;12.4.1 Complexity Analysis;236
1.23.4.2;12.4.2 Sufficiently Many Equations;237
1.23.4.3;12.4.3 Jumping Two Degrees;237
1.23.4.4;12.4.4 Fix-XL;238
1.23.5;12.5 ElimLin;240
1.23.5.1;12.5.1 Why is this useful?;241
1.23.5.2;12.5.2 How to use ElimLin;242
1.23.5.3;12.5.3 On the Sub-Space of Linear Equations in the Span of aQuadratic System of Equations;244
1.23.5.4;12.5.4 The Weight of the Basis;245
1.23.5.5;12.5.5 One Last Trick for GF(2)-only;246
1.23.5.6;12.5.6 Notes on the Sufficient Rank Condition;247
1.23.5.6.1;Amplification;247
1.23.5.6.2;A View from the Point-of-View of Randomness;248
1.23.6;12.6 Comparisons between XL and F4;248
1.23.7;12.7 SAT-Solvers;249
1.23.8;12.8 System Fragmentation;249
1.23.8.1;12.8.1 Separability;250
1.23.8.2;12.8.2 Gaussian Elimination is Not Enough;251
1.23.8.3;12.8.3 Depth First Search;251
1.23.8.4;12.8.4 Nearly Separable Systems;252
1.23.8.5;12.8.5 Removing Multiple vertices;253
1.23.8.6;12.8.6 Relation to Menger’s Theorem;253
1.23.8.7;12.8.7 Balance in Vertex Cuts;254
1.23.8.7.1;12.8.7.1 Infinite Fields and Large Finite Fields;254
1.23.8.8;12.8.8 Applicability;254
1.23.9;12.9 Resultants;255
1.23.9.1;12.9.1 The Univariate Case;255
1.23.9.2;12.9.2 The Bivariate Case;256
1.23.9.3;12.9.3 Multivariate Case;257
1.23.9.3.1;12.9.3.1 Variables versus Parameters;257
1.23.9.3.2;12.9.3.2 Solving the System;258
1.23.9.4;12.9.4 Further Reading;259
1.23.10;12.10 The Raddum-Semaev Method;259
1.23.10.1;12.10.1 Building the Graph;259
1.23.10.2;12.10.2 Agreeing;260
1.23.10.3;12.10.3 Propigation;261
1.23.10.4;12.10.4 Termination;261
1.23.10.5;12.10.5 Gluing;261
1.23.10.6;12.10.6 Splitting;263
1.23.10.7;12.10.7 Summary;263
1.23.11;12.11 The Zhuang-Zi Algorithm;264
1.23.12;12.12 Homotopy Approach;264
1.23.12.1;Applicability;265
1.24;Converting MQ to CNF-SAT;266
1.24.1;13.1 Summary;266
1.24.2;13.2 Introduction;267
1.24.2.1;13.2.1 Application to Cryptanalysis;268
1.24.3;13.3 Notation and Definitions;268
1.24.4;13.4 Converting MQ to SAT;269
1.24.4.1;13.4.1 The Conversion;269
1.24.4.1.1;13.4.1.1 Minor Technicality;269
1.24.4.1.1.1;Step One: From a Polynomial System to a Linear System;270
1.24.4.1.1.2;Step Two: From a Linear System to aConjunctive Normal Form Expression;270
1.24.4.2;13.4.2 Measures of Difficulty;271
1.24.4.2.1;13.4.2.1 Bounds on SAT;272
1.24.4.3;13.4.3 Preprocessing;273
1.24.4.3.1;The Reverse Massage;274
1.24.4.4;13.4.4 Fixing Variables in Advance;274
1.24.4.4.1;13.4.4.1 Parallelization of SAT;275
1.24.4.5;13.4.5 SAT-Solver Used;275
1.24.4.5.1;13.4.5.1 Note About Randomness;275
1.24.4.5.1.1;Error in Dissertation;276
1.24.5;13.5 Experimental Results;276
1.24.5.1;13.5.1 The Source of the Equations;276
1.24.5.2;13.5.2 Note About the Variance;276
1.24.5.3;13.5.3 The Log-Normal Distribution of Running Times;277
1.24.5.4;13.5.4 The Optimal Cutting Number;278
1.24.6;13.6 Cubic Systems;279
1.24.6.1;13.6.1 Do All Possible Monomials Appear?;279
1.24.6.2;13.6.2 Measures of Efficiency;281
1.24.7;13.7 Further Reading;281
1.24.7.1;13.7.1 Previous Work;281
1.24.7.2;13.7.2 Further Work;282
1.24.8;13.8 Conclusions;283
1.25;How do SAT-Solvers Operate?;284
1.25.1;14.1 The Problem Itself;284
1.25.1.1;14.1.1 Conjunctive Normal Form;285
1.25.2;14.2 Solvers like Walk-SAT;285
1.25.2.1;14.2.1 The Search Space;286
1.25.2.2;14.2.2 Papadimitriou’s Algorithm;286
1.25.2.3;14.2.3 Greedy SAT or G-SAT;287
1.25.2.4;14.2.4 Walk-SAT;288
1.25.2.5;14.2.5 Walk-SAT versus Papadimitriou;289
1.25.2.6;14.2.6 Where Heuristic Methods Fail;289
1.25.2.7;14.2.7 Closing Thoughts on Heuristic Methods;290
1.25.3;14.3 Back-Tracking;290
1.25.4;14.4 Chaff and its Descendants;293
1.25.4.1;14.4.1 Variable Management;293
1.25.4.2;14.4.2 Unit Propagation;294
1.25.4.3;14.4.3 The Method of Watched Literals;294
1.25.4.4;14.4.4 Absent Literals;295
1.25.4.5;14.4.5 Summary;295
1.25.5;14.5 Enhancements to Chaff;296
1.25.5.1;14.5.1 Learned Clauses;296
1.25.5.2;14.5.2 The Alarm Clock;296
1.25.5.3;14.5.3 The Third Finger;297
1.25.6;14.6 Economic Motivations;297
1.25.7;14.7 Further Reading;298
1.26;Applying SAT-Solvers to Extension Fields ofLow Degree;299
1.26.1;15.1 Introduction;299
1.26.2;15.2 Solving GF(2) Systems via SAT-Solvers;300
1.26.2.1;15.2.1 Sparsity;300
1.26.3;15.3 Overview;301
1.26.4;15.4 Polynomial Systems over Extension Fields of GF(2);301
1.26.4.1;15.4.1 Extensions of the Coefficient Field;302
1.26.4.2;15.4.2 Difficulty in Bits;302
1.26.5;15.5 Finding Efficient Arithmetic Representations via Matrices;302
1.26.6;15.6 Using the Algebraic Normal Forms;306
1.26.6.1;15.6.1 Remarks on the Special Forms;307
1.26.6.2;15.6.2 Remarks on Degree;307
1.26.6.3;15.6.3 Remarks on Coefficients;308
1.26.6.4;15.6.4 Solving with Gr¨obner Bases;308
1.26.7;15.7 Experimental Results;309
1.26.7.1;Special Symbols in Results Table:;309
1.26.7.2;Underdefined Systems of Equations;310
1.26.7.3;On the Efficacy of the Translation;310
1.26.7.4;Larger Fields;311
1.26.7.5;15.7.1 Computers Used;311
1.26.7.6;15.7.2 Polynomial Systems Used;311
1.26.8;15.8 Inverses and Determinants;312
1.26.8.1;15.8.1 Determinants;312
1.26.8.2;15.8.2 Inverses;312
1.26.8.3;15.8.3 Rijndael and the Para-Inverse Operation;313
1.26.9;15.9 Conclusions;314
1.26.10;15.10 Review of Extension Fields;315
1.26.10.1;15.10.1 Constructing the Field;315
1.26.10.2;15.10.2 Regular Representation;317
1.26.11;15.11 Reversing the Isomorphism: The Existence of DeadGive-Aways;318
1.27;Appendix A;321
1.27.1;On the Philosophy of Block CiphersWith SmallBlocks;321
1.27.1.1;A.1 Definitions;321
1.27.1.2;A.2 Brute-Force Generic Attacks on Ciphers with Small Blocks;322
1.27.1.2.1;Point of View 1: Theoretical;322
1.27.1.2.2;Point of View 2: Practical;323
1.27.1.2.3;Summary;323
1.27.1.3;A.3 Key Recovery vs. Applications of Ciphers with Small Blocks;323
1.27.1.3.1;Scenario One: LORI-KPA/LORI-CPA;323
1.27.1.3.2;Scenario Two: Manufacturer Sub-Keys;324
1.27.1.3.3;Scenario Three: Short but Private Data;325
1.27.1.3.4;Scenario Four: Assigning Account Numbers;325
1.27.1.3.5;Scenario Five: Scratch Cards and Software Serial Numbers;325
1.27.1.3.6;Scenario Six: Random Number Generation;326
1.27.1.3.7;Scenario Seven: Fast Shuffling and Anonymity;326
1.27.1.4;A.4 The Keeloq Code-book—Practical Considerations;326
1.27.1.5;A.5 Conclusions;327
1.28;Appendix B;328
1.28.1;Formulas for the Field Multiplication law forLow-Degree Extensions of GF(2);328
1.28.1.1;B.1 For GF(4);328
1.28.1.2;B.2 For GF(8);328
1.28.1.3;B.3 For GF(16);329
1.28.1.4;B.4 For GF(32);330
1.28.1.5;B.5 For GF(64);331
1.29;Appendix C;333
1.29.1;Polynomials and Graph Coloring, with OtherApplications;333
1.29.1.1;C.1 A Very Useful Lemma;333
1.29.1.2;C.2 Graph Coloring;334
1.29.1.2.1;C.2.1 The c 6= pn Case;334
1.29.1.2.2;C.2.2 Application to GF(2) Polynomials;334
1.29.1.3;C.3 Related Applications;335
1.29.1.3.1;C.3.1 Radio Channel Assignments;335
1.29.1.3.2;C.3.2 Register Allocation;336
1.29.1.4;C.4 Interval Graphs;336
1.29.1.4.1;C.4.1 Scheduling an Interval Graph Scheduling Problem;337
1.29.1.4.2;C.4.2 Comparison to Other Problems;338
1.29.1.4.3;C.4.3 Moral of the Story;339
1.30;Appendix D;340
1.30.1;Options for Very Sparse Matrices;340
1.30.1.1;D.1 Preliminary Points;340
1.30.1.1.1;D.1.1 Accidental Cancellations;340
1.30.1.1.2;D.1.2 Solving Equations by Finding a Null Space;341
1.30.1.1.3;D.1.3 Data Structures and Storage;341
1.30.1.1.3.1;D.1.3.1 An Interesting Variation;342
1.30.1.2;D.2 Na¨ ve Sparse Gaussian Elimination;342
1.30.1.2.1;D.2.1 Sparse Matrices can have Dense Inverses;343
1.30.1.3;D.3 Markowitz’s Algorithm;343
1.30.1.4;D.4 The BlockWiedemann Algorithm;343
1.30.1.5;D.5 The Block Lanczos Algorithm;344
1.30.1.6;D.6 The Pomerance-Smith Algorithm;344
1.30.1.6.1;D.6.1 Overview;345
1.30.1.6.1.1;D.6.1.1 Objective;345
1.30.1.6.1.2;D.6.1.2 The Method;346
1.30.1.6.2;D.6.2 Inactive and Active Columns;346
1.30.1.6.3;D.6.3 The Operations;346
1.30.1.6.4;D.6.4 The Actual Algorithm;348
1.30.1.6.5;D.6.5 Fill-in and Memory Management;349
1.30.1.6.6;D.6.6 Technicalities;350
1.30.1.6.6.1;D.6.6.1 Why not Do Operation 0 only Once?;350
1.30.1.6.6.2;D.6.6.2 Random Matrices;350
1.30.1.6.6.3;D.6.6.3 Only Getting Part of the Null Space;351
1.30.1.6.7;D.6.7 Cremona’s Implementation;351
1.30.1.6.8;D.6.8 Further Reading;352
1.31;Appendix E;353
1.31.1;Inspirational Thoughts, Poetry and Philosophy;353
1.32;References;355
1.33;Index;367