Algebraic Cryptanalysis

This book gives an overview of algebraic cryptanalysis. It is a further development of the author's Ph.D. thesis [Algorithms for solving linear and polynomial systems of equations over finite fields with applications to cryptanalysis, Univ. Maryland, College Park, MD, 2007]. As such, the book still has some rough edges, not only in the form of many typos but also in terms of the presentation of the material, which could be improved at times. Moreover, it is not as comprehensive as the title suggests. Nonetheless, the book seems to be the only broad treatise on the subject available. The book is divided into three parts, which cover cryptanalysis, linear systems modulo 22, and polynomial systems and satisfiability. The first part covers the main topic, while the other two parts cover useful and necessary tools. Part one describes attack strategies against some stream ciphers. The author introduces the subject by presenting attacks on Keeloq and shows the intricacies of such attacks. Following this, some general attack strategies are presented; the final chapter of the first part discusses the stream ciphers bivium, trivium and QUAD as well as attack strategies. The second part presents tools related to linear algebra over GF(2)\Bbb{GF}(2) and discusses the complexity of some algorithms. Most of the material presented is needed to perform some cryptanalysis or to estimate the complexity of an attack. However, there is also material that does not aid cryptanalysis as introduced in the first part—this is where the book seems to be a mere collection of materials that the author thinks are useful. The final part presents tools related to polynomial systems and SAT-solvers. Although the book gives a broad overview of various issues of algebraic cryptanalysis, it covers only a few topics in depth. That is, the book is not a tutorial on algebraic cryptanalysis. Therefore, as an introduction to the topic it can show a graduate student where to look further, but it is not self-contained enough to allow one to enter the field without further material. Reviewed by [Safuat Hamdy](https://mathscinet.ams.org/mathscinet/search/author.html?mrauthid=685719) * * * 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. * * * This is the first work in which I heard about [SAGE](http://sagemath.org/), the open-source alternative to Mathematica, Matlab, etc. 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. The cipher Keeloq, used in nearly all automobiles with remote key-less entry, is described as a running example, including the manipulation of the equations to enable their solution. The stream cipher Trivium, along with its variants Bivium-A and Bivium-B, and the stream cipher family QUAD are also analyzed as extensive examples, including summaries of several published attacks. Additional 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 particularly suitable for researchers in Applied Abstract Algebra or Algebraic Geometry who wish to find more applied topics, practitioners working for security and communications companies, or intelligence agencies EAE lgebraic Cryptanalysis 2 Preface 5 Dedication 8 Acknowledgements 9 Contents 14 List of Tables 24 List of Figures 25 List of Algorithms 26 List of Abrreviations 27 Introduction: How to Use this Book 28 Cryptanalysis 34 The Block Cipher Keeloq and Algebraic Attacks 35 The Fixed-Point Attack 43 Iterated Permutations 55 Stream Ciphers 81 Linear Systems Mod 2 105 Some Basic Facts about Linear Algebra overGF(2) 106 The Complexity of GF(2)-Matrix Operations 114 On the Exponent of Certain Matrix Operations 131 The Method of Four Russians 157 The Quadratic Sieve 183 Polynomial Systems and Satisfiability 208 Strategies for Polynomial Systems 209 Algorithms for Solving Polynomial Systems 230 Converting MQ to CNF-SAT 266 How do SAT-Solvers Operate? 284 Applying SAT-Solvers to Extension Fields ofLow Degree 299 Appendix A 321 Appendix B 328 Appendix C 333 Appendix D 340 Appendix E 353 References 355 Index 367 Gregory V. Bard. Includes Bibliographical References (p. 339-350) And Index.