- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Chapman & Hall/CRC

Publication Date:

2009

Number of Pages:

501

Format:

Hardcover

Series:

Chapman & Hall/CRC Cryptography and Network Security

Price:

89.95

ISBN:

9781420070026

Category:

Monograph

[Reviewed by , on ]

Tom Schulte

04/29/2010

This is a work suitable for first-year graduate students or advanced undergraduates. Obviously designed as a textbook, the addition of the online materials makes this book usable by independent readers or industry algorithm implementers in need of a reference work.

Focused on the implementation of algorithms, *Algorithmic Cryptanalysis* is a work in three parts. A preliminary section gives a brief, historical introduction to cryptography along with relevant topics from elementary number theory and algebra. The meat of the book is the central portion, on algorithms, including examples in pseudocode or C. Concluding the work is a part detailing cryptographic applications. Each chapter ends with exercises, usually about ten of them. Roughly a third of these have hints or solutions residing at the text’s web site. This site also has the C programs available for download and various auxiliary materials.

The first part, entitled “Background,” includes elementary number theory with a focus on the finite fields relevant to cryptography: modular arithmetic, primality tests, univariate polynomials, vector spaces, and linear maps. The RSA and Diffie-Hellman cryptosystems are analyzed in this portion.

The strength of the algorithm part is the rich bevy of algorithms presented in the coherent context of teaching cryptography as a science. I would wager that the pseudocode, the more prevalent form for algorithms in this book, is enough for the C programmer to get going. I wish the author, when going as far as far to show the syntax-specific programs for the Walsh transform or even Eratosthenes’s sieve, had picked a more widely used, higher-level language, such as Java or C#. If not wanting to commit to one of those divisive camps, even *MATLAB* would be nice. In the book’s defense, it may be more natural to show the effects of more current computer architecture, such as L1 and L2 cache usage in line sieving, when using a more low-level language such as C.

Entitled “Applications,” the final part of the book offers details on stream cipher attacks, lattice-based cryptanalysis, elliptic curves, and applications of index calculus. These chapters employ the work’s key elements: recognition of the impact of computer architecture such as LFSR-based keystream generators, the explanation of relevant theory such as the group structure of elliptic curves, and explicitly practical algorithms such as the pseudocode on computing the number of smooth polynomials presented in the index calculus chapter. The index calculus chapter features a very illustrative and complete toy example on computing discrete logs in **F**_{101}.

Combining practical algorithms and supported by explanation of the relevant theory, this is a good introduction to cryptanalysis that improves on that good recipe by including key details on current computer architecture. This makes this work succeed as both handbook and textbook.

Tom Schulte is a lead systems engineer at Plex Systems in Michigan with a focus on application security.

*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_{2}

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 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**

- Log in to post comments