Algebraic Cryptanalysis

Description

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

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, the open-source alternative to Mathematica, Matlab, etc.