Joux Algorithmic Cryptanalysis

Erscheinungsjahr 2009
ISBN: 978-1-4200-7003-3
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 520 Seiten

Reihe: Chapman & Hall/CRC Cryptography and Network Security Series

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.

Zielgruppe

Mathematicians and computer scientists in cryptography, discrete mathematics, and algorithms.

Autoren/Hrsg.

Joux, Antoine

Fachgebiete

• Mathematik | Informatik EDV | Informatik Technische Informatik Computersicherheit

Inhaltsverzeichnis

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 F2

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 Fp

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 Computations

General framework

Bivariate systems of equations

Definitions: multivariate ideals, monomial orderings, and Gröbner bases

Buchberger algorithm

Macaulay’s matrices

Faugère’s algorithms
Algebraic attacks on multivariate cryptography

On the complexity of Gröbner bases computation
APPLICATIONS
Attacks on Stream Ciphers

LFSR-based keystream generators

Correlation attacks

Algebraic attacks

Extension to some nonlinear shift registers

The cube attack

Time memory data tradeoffs
Lattice-Based Cryptanalysis

Direct attacks using lattice reduction

Coppersmith’s small roots attacks
Elliptic Curves and Pairings

Introduction to elliptic curves
The Weil pairing
The elliptic curve factoring method
Index Calculus Algorithms

Introduction to index calculus

A simple finite field example

Generalization to finite fields with small enough characteristics

Introduction to the number field sieve

Smoothness probabilities
References

Über Autor(innen)

Antoine Joux is associate professor at Université de Versailles Saint-Quentin-en-Yvelines.