Algorithmic
cryptAnAlysis

© 2009 by Taylor and Francis Group, LLC


CHAPMAN & HALL/CRC
CRYPTOGRAPHY AND NETWORK SECURITY

Series Editor

Douglas R. Stinson
Published Titles
Jonathan Katz and Yehuda Lindell, Introduction to Modern
Cryptography
Antoine Joux, Algorithmic Cryptanalysis

Forthcoming Titles
Burton Rosenberg, Handbook of Financial Cryptography
Maria Isabel Vasco, Spyros Magliveras, and Rainer Steinwandt,
Group Theoretic Cryptography
Shiu-Kai Chin and Susan Beth Older, Access Control, Security and
Trust: A Logical Approach

© 2009 by Taylor and Francis Group, LLC


Chapman & Hall/CRC
CRYPTOGRAPHY AND NETWORK SECURITY


registration for a variety of users. For organizations that have been granted a photocopy license by the CCC,
a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used
only for identification and explanation without intent to infringe.
Library of Congress Cataloging‑in‑Publication Data
Joux, Antoine.
Algorithmic cryptanalysis / Antoine Joux.
p. cm. -- (Chapman & Hall/CRC cryptography and network security)
Includes bibliographical references and index.
ISBN 978-1-4200-7002-6 (hardcover : alk. paper)
1. Computer algorithms. 2. Cryptography. I. Title. III. Series.
QA76.9.A43J693 2009
005.8’2--dc22
Visit the Taylor & Francis Web site at

and the CRC Press Web site at


© 2009 by Taylor and Francis Group, LLC

2009016989


` Katia, Anne et Louis
A

© 2009 by Taylor and Francis Group, LLC


Contents


11

1.2.2

Integrity and signatures . . . . . . . . . . . . . . . . .

16

1.2.3

Authenticated encryption . . . . . . . . . . . . . . . .

17

1.2.4

Abstracting cryptographic primitives . . . . . . . . . .

21

2 Elementary number theory and algebra background

23

2.1

Integers and rational numbers

. . . . . . . . . . . . . . . . .


. . . . . . . . . . . . . . . . . . . . . . .

33

2.3.1

Basic algorithms for modular arithmetic . . . . . . . .

34

2.3.2

Primality testing . . . . . . . . . . . . . . . . . . . . .

38

2.3.3

Specific aspects of the composite case . . . . . . . . .

41

Univariate polynomials and rational fractions . . . . . . . . .

44

2.4.1

Greatest common divisors and modular arithmetic . .


55

2.6

Vector spaces and linear maps

. . . . . . . . . . . . . . . . .

61

2.7

The RSA and Diffie-Hellman cryptosystems . . . . . . . . . .

63

2.7.1

RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

2.7.2

Diffie-Hellman key exchange . . . . . . . . . . . . . . .

65

© 2009 by Taylor and Francis Group, LLC

3.2.2

Asymptotically fast matrix multiplication . . . . . . .

89

3.2.3

Relation to other linear algebra problems . . . . . . .

93

Gaussian elimination algorithms . . . . . . . . . . . . . . . .

94

3.3.1

Matrix inversion . . . . . . . . . . . . . . . . . . . . .

98

3.3.2

Non-invertible matrices . . . . . . . . . . . . . . . . .

98

3.3.3



123

Introductory example: Eratosthenes’s sieve . . . . . . . . . .

123

4.1.1

Overview of Eratosthenes’s sieve . . . . . . . . . . . .

123

4.1.2

Improvements to Eratosthenes’s sieve . . . . . . . . .

125

4.1.3

Finding primes faster: Atkin and Bernstein’s sieve . .

133

Sieving for smooth composites

. . . . . . . . . . . . . . . . .

135


Brute force and the DES algorithm

. . . . . . . . . . . . . .

157

5.2.1

The DES algorithm . . . . . . . . . . . . . . . . . . .

157

5.2.2

Brute force on DES . . . . . . . . . . . . . . . . . . .

161

5.3

Brute force as a security mechanism . . . . . . . . . . . . . .

163

5.4

Brute force steps in advanced cryptanalysis . . . . . . . . . .

164

Brute force and parallel computers . . . . . . . . . . . . . . .

6 The birthday paradox: Sorting or not?

182
185

6.1

Introductory example: Birthday attacks on modes of operation 186

6.2

Analysis of birthday paradox bounds

6.1.1
6.2.1
6.3

6.4

Security of CBC encryption and CBC-MAC . . . . . .

189

Generalizations . . . . . . . . . . . . . . . . . . . . . .

190

Finding collisions


216

6.4.2

Baby-step, giant-step algorithm . . . . . . . . . . . . .

218

7 Birthday-based algorithms for functions
7.1

7.2

7.3

7.4

7.5

186

. . . . . . . . . . . . .

223

Algorithmic aspects . . . . . . . . . . . . . . . . . . . . . . .

224


Global properties . . . . . . . . . . . . . . . . . . . . .

231

7.2.2

Local properties . . . . . . . . . . . . . . . . . . . . .

232

7.2.3

Extremal properties . . . . . . . . . . . . . . . . . . .

232

Number-theoretic applications

. . . . . . . . . . . . . . . . .

233

7.3.1

Pollard’s Rho factoring algorithm . . . . . . . . . . . .

233

7.3.2



Delayed CBC beyond the birthday bound . . . . . . .

240

Collisions in hash functions . . . . . . . . . . . . . . . . . . .

242

7.5.1

Collisions between meaningful messages . . . . . . . .

243

7.5.2

Parallelizable collision search . . . . . . . . . . . . . .

244

© 2009 by Taylor and Francis Group, LLC


7.6

Hellman’s time memory tradeoff . . . . . . . . . . . . . . . .

246



Preliminaries . . . . . . . . . . . . . . . . . . . . . . .

252

8.1.2

The algorithm of Shamir and Schroeppel

253

. . . . . . .

General setting for reduced memory birthday attacks

. . . .

256

8.2.1

Xoring bit strings . . . . . . . . . . . . . . . . . . . . .

257

8.2.2

Generalization to different groups . . . . . . . . . . . .

258


. . . . . . . . . . . . . . . . . . . .

267

8.4.1

Noisy Chinese remainder reconstruction . . . . . . . .

267

8.4.2

Plain RSA and plain ElGamal encryptions

. . . . . .

269

8.4.3

Birthday attack on plain RSA . . . . . . . . . . . . . .

269

8.4.4

Birthday attack on plain ElGamal . . . . . . . . . . .

270


282

9.2

Algebraic normal forms of Boolean functions . . . . . . . . .

9.1.4

285

9.3

Goldreich-Levin theorem

286

9.4

Generalization of the Walsh transform to Fp

9.5

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . .

288

9.4.1



Arbitrary finite abelian groups . . . . . . . . . . . . .

303

10 Lattice reduction

309

10.1 Definitions

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

309

10.2 Introductory example: Gauss reduction . . . . . . . . . . . .

311

10.2.1 Complexity analysis . . . . . . . . . . . . . . . . . . .

315

10.3 Higher dimensions . . . . . . . . . . . . . . . . . . . . . . . .

318

10.3.1 Gram-Schmidt orthogonalization . . . . . . . . . . . .

319


10.5.2 Orthogonal of a lattice . . . . . . . . . . . . . . . . . .

333

11 Polynomial systems and Gr¨
obner base computations
11.1 General framework

. . . . . . . . . . . . . . . . . . . . . . .

11.2 Bivariate systems of equations

337
338

. . . . . . . . . . . . . . . . .

340

11.2.1 Resultants of univariate polynomials . . . . . . . . . .

341

11.2.2 Application of resultants to bivariate systems . . . . .

343

11.3 Definitions: Multivariate ideals, monomial orderings and Gr¨obner
bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

356

11.6.2 The F5 approach . . . . . . . . . . . . . . . . . . . . .

359

11.6.3 The specific case of F2 . . . . . . . . . . . . . . . . . .

360

11.6.4 Choosing and changing monomial ordering for Gr¨obner
bases . . . . . . . . . . . . . . . . . . . . . . . . . . . .

361

11.7 Algebraic attacks on multivariate cryptography . . . . . . . .

362

11.7.1 The HFE cryptosystem . . . . . . . . . . . . . . . . .

363

© 2009 by Taylor and Francis Group, LLC


11.7.2 Experimental Gr¨obner basis attack . . . . . . . . . . .

364


376

12.2.1 Noisy LFSR model . . . . . . . . . . . . . . . . . . . .

376

12.2.2 Maximum likelihood decoding . . . . . . . . . . . . . .

377

12.2.3 Fast correlation attacks . . . . . . . . . . . . . . . . .

380

12.2.4 Algorithmic aspects of fast correlation attacks . . . . .

383

12.3 Algebraic attacks

. . . . . . . . . . . . . . . . . . . . . . . .

387

12.3.1 Predicting an annihilator polynomial . . . . . . . . . .

388

12.4 Extension to some non-linear shift registers . . . . . . . . . .



. . .

402

13.2 Coppersmith’s small roots attacks . . . . . . . . . . . . . . .

407

13.2.1 Univariate modular polynomials . . . . . . . . . . . .

407

13.2.2 Bivariate polynomials . . . . . . . . . . . . . . . . . .

410

13.2.3 Extension to rational roots . . . . . . . . . . . . . . .

413

13.2.4 Security of RSA with small decryption exponent . . .

414

14 Elliptic curves and pairings
14.1 Introduction to elliptic curves

417
. . . . . . . . . . . . . . . . .


. . . . . . . . . . . . . .

432

14.3.1 Pollard’s p − 1 factoring . . . . . . . . . . . . . . . . .

432

14.3.2 Elliptic curve factoring . . . . . . . . . . . . . . . . . .

433

15 Index calculus algorithms

439

15.1 Introduction to index calculus
15.2 A simple finite field example

. . . . . . . . . . . . . . . . .

439

. . . . . . . . . . . . . . . . . .

441

15.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . .


. . . . . . . . . . . . . . . . . . . .

463

15.5.1 Computing smoothness probabilities for polynomials .

463

15.5.2 Asymptotic lower bound on the smoothness probability 467
15.5.3 Smoothness probabilities for integers . . . . . . . . . .

467

References

471

Lists

491

© 2009 by Taylor and Francis Group, LLC


Preface
The idea of this book stemmed from a master’s degree course given at the
University of Versailles. Since most students in this course come from a mathematical background, its goal is both to prime them on algorithmic methods
and to motivate these algorithmic methods by cryptographically relevant examples. Discussing this course with colleagues, I realized that its content
could be of interest to a much larger audience. Then, at Eurocrypt 2007 in
Barcelona, I had the opportunity to speak to Sunil Nair from Taylor & Francis. This discussion encouraged me to turn my course into a book, which you


end projects.
Throughout this book, we discuss many algorithms. Depending on the specific aspect that needs to be emphasized, this is done using either a textual
description, an algorithm in pseudo-code or a C code program. The idea is
to use pseudo-code to emphasize high-level description of algorithms and C
code to focus on lower-level implementation details. Despite some drawbacks,
the C programming language is well suited for programming cryptanalytic
applications. One essential advantage is that it is a relatively low-level programming language that allows to tightly control the behavior of the code
that is executed by the target processor. Of course, assembly language would
give an even tighter control. However, it would be much harder to read and
would only be usable on a single microprocessor or family of microprocessors.
Note that for lack of space, it was not possible to present here C programs
for all algorithms that are discussed in this book. Several additional codes
are available for downloading on the book’s website. All these codes were
developed and tested using the widely available Gnu GCC compiler. Note
that these codes are not optimally tuned, indeed, fine tuning C code is usually
specific to a single compiler version and often hurt the code’s legibility. Where
timings are given, they were measured on an Intel Core 2 Duo at 2.4 Ghz.
Writing this book was a long and challenging undertaking. It would not
have been possible without the help of many people. First, I would like to
thank my Ph.D. advisor, Jacques Stern, without his guidance, I would not
have taken the path of research and cryptography. I also wish to thank all
my colleagues and co-authors, for discussing fascinating research problems. It
was a great source of inspiration while writing this book. All my students and
former students deserve special thanks, especially for forcing me to reconsider
previous knowledge again and again. Through sheer coincidence, I happened
to be the program chair of Eurocrypt 2009 while writing this book, it was a
very nice experience and I am extremely grateful to the wonderful people who
accepted to serve on my committee. During the finalization of the manuscript,
I attended a seminar on “Symmetric Cryptography” at the “Leibniz-Zentrum


Stand-alone tools
• GAP This computer algebra system is developed by the GAP group, its
home page is It includes many features
and offers very useful group theoretic algorithms. In particular, it is able
to manipulate group characters and group representation.
• MAGMA Magma is a computer algebra system that can be bought
online at An online calculator,
with limited computing power, is also available. The Magma language
is mathematically oriented and every object belongs to a rigourously
defined structure. Magma includes a large number of features. In particular, it offers algebraic geometry tools and knows how to compute
with elliptic curves and divisors. Magma also contains a fast implementation of F4 Gr¨
obner basis algorithm and lattice reduction tools.
• Maple Maple computer algebra is a very well-known and versatile system, used in a large variety of applications. The current version contains
a very efficient implementation of the F5 Gr¨obner basis algorithm.
• PARI/GP This computer algebra system was initiated by Henri Cohen
and is currently maintained by Karim Belabas under the GPL license.
It offers both a stand-alone tool and a C library. In addition to classical
features such as modular computation, linear algebra, polynomials, it
offers some specific functionalities to compute information about general
number fields and elliptic curves over the complex field. For more information, look up the webpage at />
© 2009 by Taylor and Francis Group, LLC


• SAGE Sage is an open-source mathematics software system http:
//www.sagemath.org/ based on the Python language. It incorporates
many efficient implementations of algorithms for algebra. One specificity of Sage is that it offers the option of interfacing with other computer algebra systems and of incorporating functionalities from existing
libraries.

Libraries

certainly to give a complete description of modern cryptography. The reader
may wish to consult a reference book on cryptography. There are many such
books, a few examples are [Buc04, MvOV97, Sch96, Sti02].

1.1

Preliminaries

Cryptography is a ubiquitous tool in the world of information security. It
is required when trying to keep the secrecy of communications over open
channels or to prove the authenticity of an incoming message. It can be used
to create many multiparty protocols in a way that makes cheating difficult
and expensive. In fact, its range of applicability is very wide and it would
not be possible to give a complete list of functionalities that can be achieved
through the use of cryptography. Instead, we are going to focus on a small set
of fundamental goals and see how they can be formalized into precise security
notions. From an historical perspective, the oldest and foremost cryptographic
goal is confidentiality.
Confidentiality appeared quite early in human history. At that time, messengers were regularly sent between troops or traders to carry important messages. They were also regularly captured by enemies and they sometimes

3
© 2009 by Taylor and Francis Group, LLC


4

Algorithmic Cryptanalysis

turned out to be spies or traitors. In this context, the basic idea was to be
able to write messages in a way that would preserve the secrecy of the message meaning against these events. Later, with the invention of postal services,

simple encryption algorithm called the One Time Pad. The bad news is that
the One Time Pad is impractical for most applications and that according
to information theory nothing more practical can be secure. Indeed, the
One Time Pad views messages as sequences of symbols (bits or characters)
and encrypts them by a simple mixing of each symbol with a corresponding
symbol extracted from the key. However, it is crucial for the security of this
scheme to use a random key of the same length as the message to encrypt.
With any shorter key, the One Time Pad degenerates into a variation of the

© 2009 by Taylor and Francis Group, LLC


A bird’s-eye view of modern cryptography

5

Vigenere cipher and becomes very weak. Of course, transmitting very long
keys securely is rarely easier than directly transmitting messages securely.
Moreover, this system is error prone and any key reuse dooms the security
of the corresponding messages. In practice, a user would expect to use a
relatively short key for the transmission of long messages. Using information
theory, Shannon showed that this not possible. Indeed, a powerful enough
cryptanalyst can always try to decrypt the transmitted message using all
possible keys. The only key that yields a meaningful message is the correct
one.
In order to bypass this impossibility result, modern cryptography takes into
account the amount of work required from the cryptanalyst and assumes that,
even for relatively short key lengths, trying all keys costs too much and is not
an option. This idea is at the core of computationally based cryptography. An
asymptotically oriented approach to this idea can be obtained by using complexity theory. In this approach, easy tasks such as encryption or decryption



6

1.1.1

Algorithmic Cryptanalysis

Typical cryptographic needs

These two basic functionalities, confidentiality and integrity, give a first
criteria to classify cryptographic algorithms. Another essential criterion is
the distinction between secret key and public key algorithms. Secret key
algorithms use the same key, or sometimes distinct but equivalent keys, to
encrypt and decrypt, to authenticate or verify authentication. Public key
algorithms use different keys, the public key to encrypt or verify signatures,
the private key to decrypt or sign.
Using these two criteria, we obtain four classes of cryptographic systems.
1.1.1.1

Secret key encryption

Typical secret key algorithms encrypt messages using a short secret key
common to the sender and the recipient of the secret message. Typically,
secret keys of recent algorithm are often between 128 and 256 bits. Secret key
encryption algorithms are further divided into two main categories: stream
ciphers based and block ciphers based.
Stream ciphers combine a pseudo-random generator of cryptographic quality, also called a keystream generator, together with One Time Pad encryption.
Block ciphers are keyed permutations which act on blocks of bits; blocks of
128 bits are a frequent choice. In order to encrypt messages, they are combined

P2

7

P

−1

P

C

−1

C

P

−1

P

C

−1

C

···


P1

P

P2
C1

C2

P

−1

C

−1

C

(c) CTR encryption

Figure 1.1: Some classical encryption modes

© 2009 by Taylor and Francis Group, LLC


8

Algorithmic Cryptanalysis


In [Sim82, Sim85, Sim86], Simmons developed a theory for perfect authentication systems, which can be seen as an equivalent of Shannon’s perfect
encryption. The secret key authentication algorithms used in practice are
known as Message Authentication Codes (MACs). There are two main categories of MACs, MAC based on a block cipher and MAC based on a universal
hash function. To construct a MAC based on a block cipher, it suffices to
devise a specific mode of operation. MAC based on universal hash functions
work on a very different principle; they were initially proposed by Wegman
and Carter in [WC81]. The idea is to compute the universal hash of the
message to authenticate and then to encrypt this value. This method yields
very fast MAC algorithms. Indeed, there exist some very fast universal hashing algorithms that only cost a few processor operations per message block,
see [NP99].

© 2009 by Taylor and Francis Group, LLC


A bird’s-eye view of modern cryptography

9

To illustrate MACs based on a block cipher, let us consider the CBC encryption mode once more. Another interesting feature of this mode is that a
very simlar variation can be used as a Message Authentication Code (MAC).
In this alternative mode called CBC-MAC, we very closely follow the CBC
encryption process with a couple of simple changes. The first change is that
CBC-MAC does not need an IV . Moreover, adding an IV would make CBCMAC insecure if the IV is processed as a ciphertext block. The second change
is that in CBC-MAC, we do not output any intermediate block encryption
but only the value of the last block. The third and final change concerns the
output of the final block. If this block is directly given as MAC value, then the
resulting authentication mode is only secure for messages of fixed length. In
practice, it is usually required to have the ability to process messages of arbitrary length. In that case, the last encrypted block should be post-processed
before being used as a MAC. The most common post-processing simply reencrypts this value with the block cipher keyed with another independent key.
1.1.1.3