• Introduces cryptography from a cryptanalytic perspective
• Covers linear algebra, sieving, brute force, algorithms based on the birthday paradox, Hadamard–Fourier–Walsh transforms, lattice reduction, and Gröbner bases
• Presents advanced applications, such as LFSR-based stream ciphers, lattice methods for cryptanalysis, elliptic curves, and index calculus methods
• Includes exercises, with some hints and solutions offered on http://www.joux.biz/algcrypt/
• Provides several C codes for download on http://www.joux.biz/algcrypt/

Illustrating the power of algorithms, Algorithmic Cryptanalysis describes algorithmic methods with cryptographically relevant examples. Focusing on both private- and public-key cryptographic algorithms, it presents each algorithm either as a textual description, in pseudo-code, or in a C code program.

Divided into three parts, the book begins with a short introduction to cryptography and a background chapter on elementary number theory and algebra. It then moves on to algorithms, with each chapter in this section dedicated to a single topic and often illustrated with simple cryptographic applications. The final part addresses more sophisticated cryptographic applications, including LFSR-based stream ciphers and index calculus methods.

Accounting for the impact of current computer architectures, this book explores the algorithmic and implementation aspects of cryptanalysis methods. It can serve as a handbook of algorithmic methods for cryptographers as well as a textbook for undergraduate and graduate courses on cryptanalysis and cryptography.

BACKGROUND

A Bird’s-Eye View of Modern Cryptography

Preliminaries

Defining security in cryptography

Elementary Number Theory and Algebra Background

Integers and rational numbers

Greatest common divisors in Z

Modular arithmetic

Univariate polynomials and rational fractions

Finite fields

Vectors spaces and linear maps

The RSA and Diffie–Hellman cryptosystems

ALGORITHMS

Linear Algebra

Introductory example: multiplication of small matrices over F₂

Dense matrix multiplication

Gaussian elimination algorithms

Sparse linear algebra

Sieve Algorithms

Introductory example: Eratosthenes’s sieve

Sieving for smooth composites

Brute Force Cryptanalysis

Introductory example: dictionary attacks

Brute force and the DES algorithm

Brute force as a security mechanism

Brute force steps in advanced cryptanalysis

Brute force and parallel computers

The Birthday Paradox: Sorting or Not?

Introductory example: birthday attacks on modes of operation

Analysis of birthday paradox bounds

Finding collisions

Application to discrete logarithms in generic groups

Birthday-Based Algorithms for Functions

Algorithmic aspects

Analysis of random functions

Number theoretic applications

A direct cryptographic application in the context of blockwise security

Collisions in hash functions

Hellman’s time memory tradeoff

Birthday Attacks through Quadrisection

Introductory example: subset sum problems

General setting for reduced memory birthday attacks

Extensions of the technique

Some direct applications

Fourier and Hadamard–Walsh Transforms

Introductory example: studying S-boxes

Algebraic normal forms of boolean functions

Goldreich–Levin theorem

Generalization of the Walsh transform to F_p

Fast Fourier transforms

Lattice Reduction

Definitions

Introductory example: Gauss reduction

Higher dimensions

Shortest vectors and improved lattice reduction

Dual and orthogonal lattices

Polynomial Systems and Gröbner Bases Computatio