for γ1 = log2 (C1 ) and γ2 = log2 (C2 ) is a solution of the linear system of

equations:

d2 c1 + d1 c2 = log2 (N ) and (15.35)

(d1 + 1)c1 + (d2 + 1)c2 = log2 (N ). (15.36)

We can remark that for d1 = d2 , this system of equation does not have a

solution and the two linear constraints cannot be optimized simultaneously.

Otherwise, we ¬nd a solution and in particular, we have:

2 log2 N

(c1 + c2 ) = . (15.37)

d1 + d2 + 1

Looking at Equations (15.33) and (15.34), we see that when a and b are up-

per bounded by a common bound B, the product of the norms is (ignoring

small factors) C1 C2 B d1 +d2 = 2c1 +c2 B d1 +d2 . It is interesting to note that this

expression only involves d1 + d2 and c1 + c2 . Moreover Equation (15.37) above

relates these two parameters. As a consequence, when presenting construc-

tions of polynomials for the number ¬eld sieve, it is very useful to compare

the value of c1 + c2 that can be achieved by a given construction to the limit

given by Equation (15.37).

15.4.3.1.1 The special number ¬eld sieve Note that the bound given

by Equation (15.37) only holds for numbers N of a general form. Special

numbers with a short description may correspond to better polynomials, i.e.,

polynomials with smaller coe¬cients. The number ¬eld sieve when applied

to such numbers is called the special number ¬eld sieve or SNFS. In this

special case, Equation (15.35) remains true, but Equation (15.36) no longer

holds. Thus, to determine the best polynomials we can achieve, we need to

minimize c1 +c2 under the constraints that c1 ≥ 0 and c2 ≥ 0, while respecting

Equation (15.35). Assuming that d1 ¤ d2 , the best choice is c1 = log2 (N )/d2

and c2 = 0. Clearly, with such a choice, for a ¬xed value D of d1 + d2 the

overall optimum is achieved by choosing d1 = 1 and d2 = D ’ 1. For example,

see Exercise 6.

© 2009 by Taylor and Francis Group, LLC

Index calculus algorithms 463

15.4.3.2 Base m construction

The simpler of all known constructions that can be used for the number

¬eld sieve is the base-m construction. With this construction, one of the two

polynomials is linear, say d1 = 1 and the other can be chosen with arbitrary

degree d2 . The construction works as follows:

√

• Choose an integer m by rounding d2 +1 N up.

• Write N in basis m as:

d2

Mi mi ,

N= (15.38)

i=0

with 0 ¤ Mi < m for all i.

• Let f1 (X) = X ’ m.

d2

Mi x i .

• Let f2 (X) = i=0

Clearly, m is a root of both f1 and f2 modulo N and the resultant of f1 and

f2 is N . The sizes of the coe¬cients that are achieved are:

log2 (N )

c1 = c2 = . (15.39)

d2 + 1

2 log2 (N )

Thus, c1 + c2 is equal to and slightly above the theoretical minimum

d1 +d2

2 log2 (N )

d1 +d2 +1 .

For an asymptotic point-of-view, this small di¬erence does not a¬ect

the overall complexity that can be achieved. However, in practice, its e¬ect

might be non-negligible.

15.5 Smoothness probabilities

15.5.1 Computing smoothness probabilities for polynomials

In order to precisely evaluate the behavior of index calculus algorithms

based on the function ¬eld sieve, it is essential to give ¬ne predictions for the

probability for a polynomial of degree D to split into factors of maximum

degree m. In practice, there exists a simple combinatorial algorithm that

allows us to compute these probabilities exactly. In order to describe this

algorithm, we introduce a few notations:

m

SD = {f ∈ Fp [x]| deg f = D, any irreducible g|f has deg g ¤ m} ,

˜m m

SD = {f ∈ SD | deg f = D, at least one g of f has deg g = m} ,

˜m ˜m

m m

ND = SD and ND = SD . (15.40)

© 2009 by Taylor and Francis Group, LLC

464 Algorithmic Cryptanalysis

Remember that since Fp is a ¬eld, all irreducible polynomials can be chosen

to be unitary polynomials. In addition to the above notations, it is convenient

˜0 ˜0

0 0

to extend the de¬nitions and let N0 = N0 = 1 and ND = ND = 0 for D > 0.

Indeed, no non-constant polynomial can be written as a product of constants.

˜ ˜

The di¬erence between S or N and S or N is that in the second case we

insist on having at least one factor of exact degree m. From these de¬nitions,

a few properties can immediately be deduced:

m

˜j

m D m

= p , whenever m ≥ D, and

ND ND = ND . (15.41)

j=1

Indeed, the ¬rst property follows from the remark that any polynomial of

degree D can be decomposed in factors of degree at most D. The second

property is that the factor of largest degree in this decomposition necessarily

˜D

has a degree between 1 and D. Another noteworthy property is that ND is

equal to the number of irreducible polynomials of degree D.

With these notations in mind, we can now proceed to compute the various

˜m

m

values of ND and ND . Any polynomial f of degree N is either irreducible or

reducible. When f is reducible and m is the degree of its largest irreducible

factor, f can be decomposed as:

t

Fi — g,

f= (15.42)

i=1

where each Fi has degree m and where g is a product of polynomials of degree

at most m ’ 1. Moreover, this decomposition is unique up to a renumbering

of the polynomials Fi . When m and t are ¬xed, the number of polynomials

f which can be written as in Equation (15.42), is simply the product of the

number of possible t-uples (F1 , . . . , Ft ) by the number of possible polynomials

m’1

g. The number of possible polynomials g is simply ND’tm , since g is a poly-

nomial of degree D ’ tm with no irreducible factor of degree m or more. We

now need to determine the number of unordered t-uples (F1 , . . . , Ft ). Since

each Fi is an irreducible polynomial of degree m, it su¬ces to choose t such

polynomials. However, we should be careful that even though the t-uples are

unordered, repetitions are allowed. A very classical combinatorial result is

˜m

that an unordered choice with repetitions allowed of t elements in a set of Nm

elements is:

˜m

˜m (Nm + t ’ 1)!

Nm + t ’ 1

= . (15.43)

˜m

t t!(Nm ’ 1)!

One easy way to prove this result is to remark that if (n1 , n2 , . . . , nt ) is a

unordered t-uples of t integers in [1 · · · M ] with possible repetitions sorted in

increasing order, then (n1 + 1, n2 + 2, . . . , nt + t) is an unordered t-uples of

t integers in [2 · · · M + t] without repetitions. Moreover the correspondence

works both ways.

© 2009 by Taylor and Francis Group, LLC

Index calculus algorithms 465

It is now very easy to sum up the contribution of the various values of t

and obtain:

D/t

˜m

Nm + t ’ 1

˜D = m’1

m

N ND’tm . (15.44)

t

t=1

˜m m’1 m

Thanks to Equation (15.41), it su¬ces to add ND and ND to obtain ND .

As a side bonus, the computation also yields the number of irreducible poly-

nomials of degree D, thanks to the relation:

˜D D’1

ND = p D ’ ND . (15.45)

Note that, by theoretical analysis we already know an exact formula for

˜D

ND . Indeed, by taking any element g of FpD that does not belong to any

proper sub¬eld, we can construct an irreducible polynomial by contructing

the product:

D’1

i

X ’ gp .

i=0

Thus, the number of irreducible is equal to the number of such elements

divided by D. For example, when D is prime, we ¬nd:

D

˜D = p ’ p .

D

N (15.46)

D

When D is not prime, we need to remove each element which belongs to a

sub¬eld and we ¬nd:

«

pD ’ pD/2

1

˜D µ(D/d)pd ≥

ND = , (15.47)

D D

d|D

where µ is the Moebius function de¬ned on a number from its decomposition

into primes as follows:

±

0 if x is not square free,

1 if x has an even number of distinct prime factors,

µ(x) =

’1 if x has an odd number of distinct prime factors.

˜D

So, in all cases, ND is close to pD /D.

The above equations can directly be translated into Algorithm 15.1. For

simplicity, the variable V in this algorithm is assumed to be a rational. In

order to work with integers only, one should slightly reorder the computations

to avoid non-exact divisions. Note that in all cases, the numbers involved in

this algorithm can become very large. As a consequence, one should preferably

work with a multi-precision integer library. A much less preferable alternative

is to perform the computations using ¬‚oating point numbers. Indeed, once

we exceed the accuracy limit, the results become completely meaningless.

© 2009 by Taylor and Francis Group, LLC

466 Algorithmic Cryptanalysis

Algorithm 15.1 Compute number of smooth polynomials

Require: Input: characteristic p, maximum degree D

Create a two-dimensional D — D array N

Create a vector of D elements I

Let I[1] ←’ p

for i from 1 to D do

for j from i to D do

Let N [i, j] ←’ pi

end for

end for

for i from 2 to D do

Let V ←’ 1

Let C ←’ I[1] + i

for k from 1 to i do

Let V ←’ (C ’ k)V /k

end for

Let N [i, 1] ←’ V

for m from 2 to i ’ 1 do

Let N [i, m] ←’ N [i, m ’ 1]

Let V ←’ 1

for t from 1 to T do

Let C ←’ I[m] + t

Let V ←’ N [i ’ tm, m ’ 1]

for k from 1 to t do

Let V ←’ (C ’ k)V /k

end for

Let N [i, m] ←’ N [i, m] + V

end for

end for

Let I[i] ←’ N [i, i] ’ N [i, i ’ 1]

end for

© 2009 by Taylor and Francis Group, LLC

Index calculus algorithms 467

15.5.2 Asymptotic lower bound on the smoothness proba-

bility

Here, using the same notations as above, we prove the lower bound of the

probability of smoothness of polynomials of degree D over the basis of monic

irreducible polynomials of degree at most m. Thus, our goal is to give an

m

asymptotic lower bound on ND .

We ¬rst assume that D is a multiple of m, D = m. In that case, the number

of smooth polynomials is greater than the number of possible products of

distinct irreducible polynomials of degree m. This number is:

’1

1 ˜m

(Nm ’ i).

! i=0

˜m

Remembering that Nm is close to pm /m, letting and m grow and dividing

1

by pD to get a probability, we obtain a lower bound of: !(m+ ) for any value

of > 0. Taking the logarithm we ¬nd (log + m + ) which is asymptotically

equivalent to log as expected.

In the general case, we write D = m + r with r < m and proceed similarly

with a product of a single irreducible of degree r and distinct irreducibles of

degree m. The lower bounds immediately follows.

15.5.3 Smoothness probabilities for integers

To compute the probability of smoothness for integers, let us introduce the

quantity Ψ(x, y) to denote the number of positive integers up to x which are

y-smooth. Then, we have the following theorem from [CEP83].

THEOREM 15.2 Can¬eld, Erd¨s, Pomerance

o

For every > 0, there exists a constant C such that for all x ≥ 1 and

3 ¤ u ¤ (1 ’ ) log(x)/ log log(x) we have:

log log(u)’1

Ψ(x, x1/u ) ≥ x · e’u(log(u)+log log(u)’1+ ),

+E(x,u)

log(u)

where

2

log log(u)

|E(x, u)| ¤ C .

log(u)2

As a consequence, to express Ψ(x, y), we let u = log(x)/ log(y) and substi-

tute u in the above theorem. After dividing by x to obtain a probability of

smoothness and ignoring low order terms we ¬nd that:

log(x) log(x)

log(Ψ(x, y)/x) ≈ ’ log .

log(y) log(y)

To understand the relation between this smoothness probability and the

functions LN (±, c), see Exercise 9.

© 2009 by Taylor and Francis Group, LLC

468 Algorithmic Cryptanalysis

Exercises

1h . Draw the graphs of LN (±, c) as a function of N for several values of ±

and c. In particular, focus on the values of ± and c that arise in the

complexity analysis we have seen. In each case, what is the maximum

value of N that can be reached if we want to ensure that LN (±, c) ¤ 280 ?

This gives an upper bound on the size of N that can be reached in the

near future.

2. Repeat the complexity analysis of the function ¬eld sieve variation of

Section 15.3 when D is a ¬xed integer. For D = 1, you should recover

the results of Section 15.2. For each D, what is the range for p where

this value of D is the best choice? Draw the corresponding asymptotic

complexities on a graph.

3h . For the case of Fpn with p = 65537 and n = 49, construct two polyno-

mials f1 and f2 allowing to apply the basic algorithm of Section 15.2.

Write a program to generate equations from xy + ax + by + c. How

long would it take to ¬nd enough equations? How long to solve the lin-

ear algebra problem and obtain discrete logarithms for the smoothness

basis?

Turn to the descent problem and write code, possibly in a computer

algebra system, to perform the descent step down to degree 2. Can you

descend from degree 2 to degree 1?

√

4. Consider the nine ¬elds Q[ ’d] whose rings of integers are unique fac-

√

torization domains. For each, list the primes of the form (a +b ’d)/2.

Remark that division by 2 is not always required. When is it needed?

√

Write a program to explicitly factor any a + b ’d. Assuming that a

and b are coprime, is there any integer prime appearing in these decom-

positions?

√

5h . Consider the ¬eld Q[ ’5]. Characterize all the prime ideals in the ring

√

of numbers of the form a + b ’5. Write a program to compute the

decomposition into prime ideals of all numbers of this form when |a|

and |b| are smaller than 1000.

p

6. Consider the p-th Fermat number Fp = 22 + 1. Construct two polyno-

mials with a common root modulo Fp which beat the bound of Equa-

tion (15.37). Explain why the special number ¬eld sieve outperforms

the number ¬eld sieve in this case.

7h . Let N be a ¬xed integer and let f1 (X) = ±X ’ β for two integers ± and

β. How can we use lattice reduction to construct a second polynomial f2

of degree d which also has β/± (mod N ) as a root modulo N ? Given N

© 2009 by Taylor and Francis Group, LLC

Index calculus algorithms 469

and d, which size can be achieved for ± and β. Compare with the base

m construction. Assume that the sieving step considers elements of the

form a + bX with unbalanced bounds on |a| and |b|. Show that in that

case, using unbalanced (skewed) coe¬cients in f1 and f2 is important.

Adapt the construction to the skewed case.

8. This exercise considers a contruction, due to Montgomery, of two quadratic

polynomials usable for the number ¬eld sieve modulo N . Let p be a

√

prime near N such that N is a quadratic residue modulo p. Let c be a

square root of N modulo p. Show that the numbers p, c and (c2 ’ N )/p)

form a geometry progression of ratio c/p (mod N ). Consider the lattice

formed of all vectors whose scalar product with (p, c, (c2 ’ N )/p) mod-

ulo N is 0. What is the rank of this lattice? What is the size of the

short vectors it contains? Show that each short vector in this lattice can

be transformed into a polynomial with root c/p modulo N . Conclude

how we obtain two quadratic polynomials f1 and f2 for the number ¬eld

sieve. Compare with the bound of Equation (15.37).

9h . This exercise studies the relation between functions LN (±, c) and the

smoothness probabilities given in Section 15.5.3. Assume that x =

LN (±, c) and y = LN (β, d) and compute Ψ(x, y)/x. For which values of

±, β, c and d is this formula valid?

A natural implementation project for this topic is to implement one of the

possible index calculus algorithms described in this chapter. Note that this

is a long project, because it is necessary to implement at least three separate

parts, sieving, linear algebra and ¬nal phase (individual logarithm or factor

extraction). This can possibly be split into separate but well-coordinated

subprojects.

© 2009 by Taylor and Francis Group, LLC

References

Numbers within brackets after each reference indicate the citing pages.

[AB04] A. O. L. Atkin and Daniel J. Bernstein. Prime sieves using binary

quadratic forms. Mathematics of Computation, 73(246):1023“

1030, 2004. [123, 133, 134, 135]

[ABW03] Mart´ Abadi, Michael Burrows, and Ted Wobber. Moderately

±n

hard and memory-bound functions. In NDSS 2003, San Diego,

California, USA, February 5“7, 2003. The Internet Society. [164]

[ADKF70] V. L. Arlazarov, E. A. Dinic, M. A. Kronod, and I. A. Faradzev.

On economical construction of the transitive closure of an ori-

ented graph. Soviet Math. Dokl., 11:1209“1210, 1970. [85]

[Adl94] Leonard M. Adleman. The function ¬eld sieve. In First Algorith-

mic Number Theory Symposium (ANTS), volume 877 of LNCS,

pages 108“121. Springer-Verlag, Berlin, Germany, 1994. [453]

[ADR02] Jee Hea An, Yevgeniy Dodis, and Tal Rabin. On the security

of joint signature and encryption. In Lars R. Knudsen, editor,

EUROCRYPT 2002, volume 2332 of LNCS, pages 83“107, Ams-

terdam, The Netherlands, April 28“May 2, 2002. Springer-Verlag,

Berlin, Germany. [20]

[AFK+ 07] Kazumaro Aoki, Jens Franke, Thorsten Kleinjung, Arjen K.

Lenstra, and Dag Arne Osvik. A kilobit special number ¬eld sieve

factorization. In Kaoru Kurosawa, editor, ASIACRYPT 2007,

volume 4833 of LNCS, pages 1“12, Kuching, Malaysia, Decem-

ber 2“6, 2007. Springer-Verlag, Berlin, Germany. [113]

[AKS01] Mikl´s Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm

o

for the shortest lattice vector problem. In 33rd ACM STOC,

pages 601“610, Crete, Greece, July 6“8, 2001. ACM Press. [328]

[AKS02] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is

in P. Ann. of Math, 2:781“793, 2002. [38]

[AS08] Onur Acii¸mez and Werner Schindler. A vulnerability in RSA

c

implementations due to instruction cache analysis and its demon-

stration on OpenSSL. In Tal Malkin, editor, CT-RSA 2008,

LNCS, pages 256“273, San Francisco, CA, USA, April 7“11, 2008.

Springer-Verlag, Berlin, Germany. [92]

[AScKK07] Onur Acii¸mez, Werner Schindler, and Cetin Kaya Ko¸. Cache

c ¸ c

based remote timing attack on the AES. In Masayuki Abe, ed-

itor, CT-RSA 2007, volume 4377 of LNCS, pages 271“286, San

471

© 2009 by Taylor and Francis Group, LLC

472 Algorithmic Cryptanalysis

Francisco, CA, USA, February 5“9, 2007. Springer-Verlag, Berlin,

Germany. [92]

´

[Bar04] Magali Turrel Bardet. Etude des syst`mes alg´briques

e e

surd´termin´s. Applications aux codes correcteurs et ` la cryp-

e e a

tographie. PhD thesis, Universit´ de Paris VI, 2004. [367]

e

[BBD07] Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, ed-

itors. Post Quantum Cryptography. Springer-Verlag, Berlin, Ger-

many, 2007. [363]

[BC04] Eli Biham and Ra¬ Chen. Near-collisions of SHA-0. In

Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS,

pages 290“305, Santa Barbara, CA, USA, August 15“19, 2004.

Springer-Verlag, Berlin, Germany. [179]

[BCJ+ 05] Eli Biham, Ra¬ Chen, Antoine Joux, Patrick Carribault,

Christophe Lemuet, and William Jalby. Collisions of SHA-0 and

reduced SHA-1. In Ronald Cramer, editor, EUROCRYPT 2005,

volume 3494 of LNCS, pages 36“57, Aarhus, Denmark, May 22“

26, 2005. Springer-Verlag, Berlin, Germany. [179, 181]

[BCRL79] Dario Bini, Milvio Capovani, Francesco Romani, and Grazia

Lotti. o(n2.7799 ) complexity for n — n approximate matrix mul-

tiplication. Information processing letters, 8(5):234“235, 1979.

[89]

[BD99] Dan Boneh and Glenn Durfee. Cryptanalysis of RSA with pri-

vate key d less than n0.292 . In Jacques Stern, editor, EURO-

CRYPT™99, volume 1592 of LNCS, pages 1“11, Prague, Czech

Republic, May 2“6, 1999. Springer-Verlag, Berlin, Germany. [414]

[BDJR97] Mihir Bellare, Anand Desai, Eric Jokipii, and Phillip Rogaway.

A concrete security treatment of symmetric encryption. In 38th

FOCS, pages 394“403, Miami Beach, Florida, October 19“22,

1997. IEEE Computer Society Press. [15]

[Ber00] Daniel J. Bernstein. How to ¬nd small factors of integers. Avail-

able on cr.yp.to, 2000. [152]

[Ber07] Cˆme Berbain. Analyse et conception d™algorithmes de chi¬re-

o

ment ` ¬‚ot. PhD thesis, Universit´ Paris Diderot, 2007. [289]

a e

[BGP06] Cˆme Berbain, Henri Gilbert, and Jacques Patarin. QUAD: A

o

practical stream cipher with provable security. In Serge Vaude-

nay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages

109“128, St. Petersburg, Russia, May 28“June 1, 2006. Springer-

Verlag, Berlin, Germany. [289]

[Bih97] Eli Biham. A fast new DES implementation in software. In

Eli Biham, editor, FSE™97, volume 1267 of LNCS, pages 260“

© 2009 by Taylor and Francis Group, LLC

References 473

272, Haifa, Israel, January 20“22, 1997. Springer-Verlag, Berlin,

Germany. [162]

[BJ07] Aur´lie Bauer and Antoine Joux. Toward a rigorous variation

e

of Coppersmith™s algorithm on three variables. In Moni Naor,

editor, EUROCRYPT 2007, volume 4515 of LNCS, pages 361“

378, Barcelona, Spain, May 20“24, 2007. Springer-Verlag, Berlin,

Germany. [413]

[BJN00] Dan Boneh, Antoine Joux, and Phong Q. Nguyen. Why textbook

ElGamal and RSA encryption are insecure. In Tatsuaki Okamoto,

editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 30“43,

Kyoto, Japan, December 3“7, 2000. Springer-Verlag, Berlin, Ger-

many. [269]

[BK03] Mihir Bellare and Tadayoshi Kohno. A theoretical treatment of

related-key attacks: RKA-PRPs, RKA-PRFs, and applications.

In Eli Biham, editor, EUROCRYPT 2003, volume 2656 of LNCS,

pages 491“506, Warsaw, Poland, May 4“8, 2003. Springer-Verlag,

Berlin, Germany. [21]

[BK04] Mihir Bellare and Tadayoshi Kohno. Hash function balance and

its impact on birthday attacks. In Christian Cachin and Jan

Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS,

pages 401“418, Interlaken, Switzerland, May 2“6, 2004. Springer-

Verlag, Berlin, Germany. [192]

[BKN04] Mihir Bellare, Tadayoshi Kohno, and Chanathip Namprempre.

Authenticated encryption in SSH: provably ¬xing the SSH bi-

nary packet protocol. ACM transactions on information and

system security, 7(2):206“241, May 2004. Full paper avail-

able at http://www.cse.ucsd.edu/users/mihir/papers/ssh.

html. Earlier version appeared in ACM CCS 02. [238, 239]

[BKR00] Mihir Bellare, Joe Kilian, and Phillip Rogaway. The security of

the cipher block chaining message authentication code. Journal

of Computer and System Sciences, 61(3):362“399, 2000. [5]

[BM97] Mihir Bellare and Daniele Micciancio. A new paradigm for

collision-free hashing: Incrementality at reduced cost. In Wal-

ter Fumy, editor, EUROCRYPT™97, volume 1233 of LNCS, pages

163“192, Konstanz, Germany, May 11“15, 1997. Springer-Verlag,

Berlin, Germany. [266]

[BM05] Johannes Bl¨mer and Alexander May. A tool kit for ¬nding

o

small roots of bivariate polynomials over the integers. In Ronald

Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS,

pages 251“267, Aarhus, Denmark, May 22“26, 2005. Springer-

Verlag, Berlin, Germany. [412]

© 2009 by Taylor and Francis Group, LLC

474 Algorithmic Cryptanalysis

[BN00] Mihir Bellare and Chanathip Namprempre. Authenticated en-

cryption: Relations among notions and analysis of the generic

composition paradigm. In Tatsuaki Okamoto, editor, ASI-

ACRYPT 2000, volume 1976 of LNCS, pages 531“545, Kyoto,

Japan, December 3“7, 2000. Springer-Verlag, Berlin, Germany.

[17, 18]

[BR94] Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryp-

tion. In Alfredo De Santis, editor, EUROCRYPT™94, volume 950

of LNCS, pages 92“111, Perugia, Italy, May 9“12, 1994. Springer-

Verlag, Berlin, Germany. [64]

[BR96] Mihir Bellare and Phillip Rogaway. The exact security of digital

signatures: How to sign with RSA and Rabin. In Ueli M. Maurer,

editor, EUROCRYPT™96, volume 1070 of LNCS, pages 399“416,

Saragossa, Spain, May 12“16, 1996. Springer-Verlag, Berlin, Ger-

many. [10, 64]

[BR06] Mihir Bellare and Phillip Rogaway. The security of triple en-

cryption and a framework for code-based game-playing proofs.

In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of

LNCS, pages 409“426, St. Petersburg, Russia, May 28“June 1,

2006. Springer-Verlag, Berlin, Germany. [186]

[BS91a] Eli Biham and Adi Shamir. Di¬erential cryptanalysis of DES-

like cryptosystems. In Alfred J. Menezes and Scott A. Vanstone,

editors, CRYPTO™90, volume 537 of LNCS, pages 2“21, Santa

Barbara, CA, USA, August 11“15, 1991. Springer-Verlag, Berlin,

Germany. [273]

[BS91b] Eli Biham and Adi Shamir. Di¬erential cryptoanalysis of Feal

and N-hash. In Donald W. Davies, editor, EUROCRYPT™91,

volume 547 of LNCS, pages 1“16, Brighton, UK, April 8“11, 1991.

Springer-Verlag, Berlin, Germany. [273]

[BS92] Eli Biham and Adi Shamir. Di¬erential cryptanalysis of Snefru,

Khafre, REDOC-II, LOKI and Lucifer. In Joan Feigenbaum,

editor, CRYPTO™91, volume 576 of LNCS, pages 156“171, Santa

Barbara, CA, USA, August 11“15, 1992. Springer-Verlag, Berlin,

Germany. [273]

[BS93] Eli Biham and Adi Shamir. Di¬erential cryptanalysis of the full

16-round DES. In Ernest F. Brickell, editor, CRYPTO™92, vol-

ume 740 of LNCS, pages 487“496, Santa Barbara, CA, USA,

August 16“20, 1993. Springer-Verlag, Berlin, Germany. [273]

[BS00] Alex Biryukov and Adi Shamir. Cryptanalytic

time/memory/data tradeo¬s for stream ciphers. In Tatsuaki

Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS,

© 2009 by Taylor and Francis Group, LLC

References 475

pages 1“13, Kyoto, Japan, December 3“7, 2000. Springer-Verlag,

Berlin, Germany. [394]

[BSS05] Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors. Ad-

vances in Elliptic Curve Cryptography, volume 317 of London

Mathematical Society Lecture Note Series. Cambridge University

Press, New York, 2005. [425]

[BSV07] Thomas Baign`res, Jacques Stern, and Serge Vaudenay. Linear

e

cryptanalysis of non binary ciphers. In Carlisle M. Adams, Ali

Miri, and Michael J. Wiener, editors, SAC 2007, volume 4876

of LNCS, pages 184“211, Ottawa, Canada, August 16“17, 2007.

Springer-Verlag, Berlin, Germany. [289]

[BT04] Alexandra Boldyreva and Nut Taesombut. Online encryption

schemes: New security notions and constructions. In Tatsuaki

Okamoto, editor, CT-RSA 2004, volume 2964 of LNCS, pages

1“14, San Francisco, CA, USA, February 23“27, 2004. Springer-

Verlag, Berlin, Germany. [238]

[Buc04] Johannes Buchmann. Introduction to Cryptography (Second edi-

tion). Undergraduate texts in Mathematics. Springer, New York,

2004. [3]

[BV07] Johannes Buchmann and Ulrich Vollmer. Binary Quadratic

Forms “ An Algorithmic Approach, volume 20 of Algorithms and

Computation in Mathematics. Springer-Verlag, Berlin, Germany,

2007. [311]

[Cav00] Stefania Cavallar. Strategies in ¬ltering in the number ¬eld sieve.

In Fourth Algorithmic Number Theory Symposium (ANTS), vol-

ume 1838 of LNCS, pages 209“232. Springer-Verlag, Berlin, Ger-

many, 2000. [118]

[CEP83] E. R. Can¬eld, Paul Erd¨s, and Carl Pomerance. On a problem

o

of Oppenheim concerning factorisatio numerorum. Journal of

Number Theory, 17:1“28, 1983. [467]

[CF05] Henri Cohen and Gerhard Frey, editors. Handbook of Elliptic and

Hyperelliptic Curve Cryptography, volume 34 of Discrete Mathe-

matics and its Applications. Chapman & Hall, CRC, 2005. [417,

424, 432]

[CJ98] Florent Chabaud and Antoine Joux. Di¬erential collisions in

SHA-0. In Hugo Krawczyk, editor, CRYPTO™98, volume 1462

of LNCS, pages 56“71, Santa Barbara, CA, USA, August 23“27,

1998. Springer-Verlag, Berlin, Germany. [179]

[CJL+ 92] Matthijs J. Costerr, Antoine Joux, Brian A. LaMacchia, An-

drew M. Odlyzko, Clauss-Peter Schnorr, and Jacques Stern. Im-

© 2009 by Taylor and Francis Group, LLC

476 Algorithmic Cryptanalysis

proved low-density subset sum algorithms. Computational Com-

plexity, 2:111“128, 1992. [402]

[CJM02] Philippe Chose, Antoine Joux, and Michel Mitton. Fast corre-

lation attacks: An algorithmic point of view. In Lars R. Knud-

sen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages

209“221, Amsterdam, The Netherlands, April 28“May 2, 2002.

Springer-Verlag, Berlin, Germany. [257, 385, 387]

[CKM97] St´phane Collart, Michael Kalkbrener, and Daniel Mall. Con-

e

verting bases with the Gro¨bner walk. J. Symbolic Computation,

o

24(3“4):465“469, 1997. [361]

[CKSU05] Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Christopher

Umans. Group-theoretic algorithms for matrix multiplication.

In Proceedings of the 46th Annual IEEE Symposium on Foun-

dations of Computer Science, pages 379“388, Washington, DC,

USA, 2005. IEEE Computer Society. [93]

[CL09] Jean-Marc Couveignes and Reynald Lercier. Elliptic periods for

¬nite ¬elds. Finite ¬elds and their applications, 15:1“22, 2009.

[49]

[CLO07] David Cox, John Little, and Donal O™Shea. Ideals, Varieties and

Algorithms (Third edition). Undergraduate texts in Mathematics.

Springer, New York, 2007. [345, 348, 350, 353, 354]

[Cop94] Don Coppersmith. Solving homogeneous linear equations over

gf (2) via block wiedemann algorithm. Mathematics of Compu-

tation, 62(205):333“350, 1994. [113]

[Cop96a] Don Coppersmith. Finding a small root of a bivariate integer

equation; factoring with high bits known. In Ueli M. Maurer,

editor, EUROCRYPT™96, volume 1070 of LNCS, pages 178“189,

Saragossa, Spain, May 12“16, 1996. Springer-Verlag, Berlin, Ger-

many. [412]

[Cop96b] Don Coppersmith. Finding a small root of a univariate modu-

lar equation. In Ueli M. Maurer, editor, EUROCRYPT™96, vol-

ume 1070 of LNCS, pages 155“165, Saragossa, Spain, May 12“16,

1996. Springer-Verlag, Berlin, Germany. [410]

[Cor04] Jean-S´bastien Coron. Finding small roots of bivariate integer

e

polynomial equations revisited. In Christian Cachin and Jan Ca-

menisch, editors, EUROCRYPT 2004, volume 3027 of LNCS,

pages 492“505, Interlaken, Switzerland, May 2“6, 2004. Springer-

Verlag, Berlin, Germany. [412]

[Cor07] Jean-S´bastien Coron. Finding small roots of bivariate integer

e

polynomial equations: A direct approach. In Alfred Menezes,

© 2009 by Taylor and Francis Group, LLC

References 477

editor, CRYPTO 2007, volume 4622 of LNCS, pages 379“394,

Santa Barbara, CA, USA, August 19“23, 2007. Springer-Verlag,

Berlin, Germany. [412]

[CP91] Paul Camion and Jacques Patarin. The Knapsack hash function

proposed at Crypto™89 can be broken. In Donald W. Davies,

editor, EUROCRYPT™91, volume 547 of LNCS, pages 39“53,

Brighton, UK, April 8“11, 1991. Springer-Verlag, Berlin, Ger-

many. [264, 405]

[CPS08] Jean-S´bastien Coron, Jacques Patarin, and Yannick Seurin. The

e

random oracle model and the ideal cipher model are equiva-

lent. In David Wagner, editor, CRYPTO 2008, volume 5157

of LNCS, pages 1“20, Santa Barbara, CA, USA, August 17“21,

2008. Springer-Verlag, Berlin, Germany. [22]

[CT65] James W. Cooley and John W. Tukey. An algorithm for the

machine calculation of complex Fourier series. Mathematics of

Computation, 19:297“301, 1965. [296]

[CV94] Florent Chabaud and Serge Vaudenay. Links between di¬erential

and linear cryptoanalysis. In Alfredo De Santis, editor, EURO-

CRYPT™94, volume 950 of LNCS, pages 356“365, Perugia, Italy,

May 9“12, 1994. Springer-Verlag, Berlin, Germany. [279, 281]

[CW90] Don Coppersmith and Shmuel Winograd. Matrix multiplica-

tion via arithmetic progressions. J. of Symbolic Computation,

9(3):251“280, 1990. [93]

[Dam90] Ivan Damg˚ ard. A design principle for hash functions. In Gilles

Brassard, editor, CRYPTO™89, volume 435 of LNCS, pages 416“

427, Santa Barbara, CA, USA, August 20“24, 1990. Springer-

Verlag, Berlin, Germany. [405, 406]

[DES77] Data encryption standard. National Bureau of Standards, NBS

FIPS PUB 46, U.S. Department of Commerce, January 1977.

[157]

[DFV97] Herv´ Daud´, Philippe Flajolet, and Brigitte Vall´e. An average-

e e e

case analysis of the gaussian algorithm for lattice reduction. Com-

binatorics, Probability & Computing, 6(4):397“433, 1997. [318]

[DGV94] Joan Daemen, Ren´ Govaerts, and Joos Vandewalle. Correla-

e

tion matrices. In Bart Preneel, editor, FSE™94, volume 1008 of

LNCS, pages 275“285, Leuven, Belgium, December 14“16, 1994.

Springer-Verlag, Berlin, Germany. [279]

[DH76] Whit¬eld Di¬e and Martin E. Hellman. New directions in cryp-

tography. IEEE Transactions on Information Theory, 22(6):644“

654, 1976. [5, 9]

© 2009 by Taylor and Francis Group, LLC

478 Algorithmic Cryptanalysis

[DLC07] Fr´d´ric Didier and Yann Laigle-Chapuy. Finding low-weight

ee

polynomial multiples using discrete logarithm. Computing Re-

search Repository (CoRR), abs/cs/0701069, 2007. [386]

[DN93] Cynthia Dwork and Moni Naor. Pricing via processing or com-

batting junk mail. In Ernest F. Brickell, editor, CRYPTO™92,

volume 740 of LNCS, pages 139“147, Santa Barbara, CA, USA,

August 16“20, 1993. Springer-Verlag, Berlin, Germany. [164]

[DS09] Itai Dinur and Adi Shamir. Cube attacks on tweakable black

box polynomials. In Antoine Joux, editor, EUROCRYPT 2009,

volume 5479 of LNCS, pages 278“299. Springer-Verlag, Berlin,

Germany, 2009. [390, 391, 392, 396]

[Eis95] David Eisenbud. Commutative Algebra with a View Towards Al-

gebraic Geometry, volume 150 of Graduate Texts in Mathematics.

Springer, New York, 1995. [342]

[ElG85] Taher ElGamal. A public key cryptosystem and a signature

scheme based on discrete logarithms. In G. R. Blakley and David

Chaum, editors, CRYPTO™84, volume 196 of LNCS, pages 10“18,

Santa Barbara, CA, USA, August 19“23, 1985. Springer-Verlag,

Berlin, Germany. [66, 67]

[Fau99] Jean-Charles Faug`re. A new e¬cient algorithm for computing

e

Gr¨bner bases (F4). J. Pure Appl. Algebra, 139(1-3):61“88, 1999.

o

E¬ective methods in algebraic geometry (Saint-Malo, 1998). [356,

357]

[Fau02] Jean-Charles Faug`re. A new e¬cient algorithm for computing

e

Gr¨bner bases without reduction to zero (F5). In T. Mora, editor,

o

ISSAC 2002, pages 75“83, 2002. [356, 359]

[FGLM93] Jean-Charles Faug`re, Patricia Gianni, Daniel Lazard, and Teo

e

Mora. E¬cient computation of zero-dimensional Gro¨bner bases

o

by change of ordering. J. Symbolic Computation, 16(4):329“344,

1993. [361, 362]

[FJ03] Jean-Charles Faug`re and Antoine Joux. Algebraic cryptanaly-

e

sis of hidden ¬eld equation (HFE) cryptosystems using gr¨bner

o

bases. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of

LNCS, pages 44“60, Santa Barbara, CA, USA, August 17“21,

2003. Springer-Verlag, Berlin, Germany. [365]

[FJMV04] Pierre-Alain Fouque, Antoine Joux, Gwena¨lle Martinet, and

e

Fr´d´ric Valette. Authenticated on-line encryption. In Mitsuru

ee

Matsui and Robert J. Zuccherato, editors, SAC 2003, volume

3006 of LNCS, pages 145“159, Ottawa, Ontario, Canada, Au-

gust 14“15, 2004. Springer-Verlag, Berlin, Germany. [238]

© 2009 by Taylor and Francis Group, LLC

References 479

[FJP04] Pierre-Alain Fouque, Antoine Joux, and Guillaume Poupard.

Blockwise adversarial model for on-line ciphers and symmetric

encryption schemes. In Helena Handschuh and Anwar Hasan,

editors, SAC 2004, volume 3357 of LNCS, pages 212“226, Wa-

terloo, Ontario, Canada, August 9“10, 2004. Springer-Verlag,

Berlin, Germany. [238]

[FLPR99] Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Srid-

har Ramachandran. Cache-oblivious algorithms. In 40th FOCS,

pages 285“298, New York, New York, USA, October 17“19, 1999.

IEEE Computer Society Press. [92]

[FM03] Joanne Fuller and William Millan. Linear redundancy in S-boxes.

In Thomas Johansson, editor, FSE 2003, volume 2887 of LNCS,

pages 74“86, Lund, Sweden, February 24“26, 2003. Springer-

Verlag, Berlin, Germany. [282]

[FMP03] Pierre-Alain Fouque, Gwena¨lle Martinet, and Guillaume

e

Poupard. Practical symmetric on-line encryption. In Thomas Jo-

hansson, editor, FSE 2003, volume 2887 of LNCS, pages 362“375,

Lund, Sweden, February 24“26, 2003. Springer-Verlag, Berlin,

Germany. [239]

[FO90] Philippe Flajolet and Andrew M. Odlyzko. Random mapping

statistics. In Jean-Jacques Quisquater and Joos Vandewalle, ed-

itors, EUROCRYPT™89, volume 434 of LNCS, pages 329“354,

Houthalen, Belgium, April 10“13, 1990. Springer-Verlag, Berlin,

Germany. [231, 233, 234]

[FP85] U. Fincke and Michael E. Pohst. Improved methods for calcu-

lating vectors of short length in a lattice, including a complexity

analysis. Mathematics of Computation, 44(170):463“471, 1985.

[328]

[FS87] Amos Fiat and Adi Shamir. How to prove yourself: Practical

solutions to identi¬cation and signature problems. In Andrew M.

Odlyzko, editor, CRYPTO™86, volume 263 of LNCS, pages 186“

194, Santa Barbara, CA, USA, August 1987. Springer-Verlag,

Berlin, Germany. [10]

[Gal04] William F. Galway. Ph. D. in mathematics. PhD thesis, Univer-

sity of Illinois at Urbana-Champaign, 2004. [135]

[GC91] Henri Gilbert and Guy Chass´. A statistical attack of the FEAL-

e

8 cryptosystem. In Alfred J. Menezes and Scott A. Vanstone,

editors, CRYPTO™90, volume 537 of LNCS, pages 22“33, Santa

Barbara, CA, USA, August 11“15, 1991. Springer-Verlag, Berlin,

Germany. [273]

© 2009 by Taylor and Francis Group, LLC

480 Algorithmic Cryptanalysis

[GH05] Jovan Dj. Golic and Philip Hawkes. Vectorial approach to fast

correlation attacks. Des. Codes Cryptography, 35(1):5“19, 2005.

[380]

[GJS06] Louis Granboulan, Antoine Joux, and Jacques Stern. In-

verting HFE is quasipolynomial. In Cynthia Dwork, editor,

CRYPTO 2006, volume 4117 of LNCS, pages 345“356, Santa

Barbara, CA, USA, August 20“24, 2006. Springer-Verlag, Berlin,

Germany. [366]

[GL96] Gene H. Golub and Charles F. Van Loan. Matrix Computations

(third edition). The Johns Hopkins University Press, London,

1996. [71]

[GL03] Rosario Gennaro and Yehuda Lindell. A framework for password-

based authenticated key exchange. In Eli Biham, editor, EU-

ROCRYPT 2003, volume 2656 of LNCS, pages 524“543, War-

saw, Poland, May 4“8, 2003. Springer-Verlag, Berlin, Germany.

http://eprint.iacr.org/2003/032.ps.gz. [156]

[GMR89] Sha¬ Goldwasser, Silvio Micali, and Charles Racko¬. The knowl-

edge complexity of interactive proof systems. SIAM Journal on

Computing, 18(1):186“208, 1989. [66]

[GN08] Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduc-

tion. In Nigel P. Smart, editor, EUROCRYPT 2008, LNCS, pages

31“51, Istanbul, Turkey, April 13“17, 2008. Springer-Verlag,

Berlin, Germany. [405]

[HG97] Nick Howgrave-Graham. Finding small roots of univariate mod-

ular equations revisited. In Michael Darnell, editor, Cryptog-

raphy and Coding, 6th IA International Conference, volume

1355 of LNCS, pages 131“142, Cirencester, UK, December 1997.

Springer-Verlag, Berlin, Germany. [407, 410]

[HG07] Nick Howgrave-Graham. A hybrid lattice-reduction and meet-

in-the-middle attack against NTRU. In Alfred Menezes, editor,

CRYPTO 2007, volume 4622 of LNCS, pages 150“169, Santa

Barbara, CA, USA, August 19“23, 2007. Springer-Verlag, Berlin,

Germany. [405]

[HILL99] Johan H˚

astad, Russell Impagliazzo, Leonid A. Levin, and Michael

Luby. A Pseudorandom Generator from any One-way Function.

SIAM J. Comput., 28(4):1364“1396, 1999. [286]

[HS07] Guillaume Hanrot and Damien Stehl´. Improved analysis of kan-

e

nan™s shortest lattice vector algorithm. In Alfred Menezes, edi-

tor, CRYPTO 2007, volume 4622 of LNCS, pages 170“186, Santa

Barbara, CA, USA, August 19“23, 2007. Springer-Verlag, Berlin,

Germany. [331]

© 2009 by Taylor and Francis Group, LLC

References 481

[JG94] Antoine Joux and Louis Granboulan. A practical attack against

Knapsack based hash functions (extended abstract). In Al-

fredo De Santis, editor, EUROCRYPT™94, volume 950 of LNCS,

pages 58“66, Perugia, Italy, May 9“12, 1994. Springer-Verlag,

Berlin, Germany. [406]

[JL01] Antoine Joux and Reynald Lercier. “Chinese & Match,” an al-

ternative to Atkin™s “Match and Sort” method used in the SEA

algorithm. Mathematics of Computation, 70:827“836, 2001. [267,

268, 269]

[JLSV06] Antoine Joux, Reynald Lercier, Nigel Smart, and Frederik Ver-

cauteren. The number ¬eld sieve in the medium prime case. In

Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS,

pages 326“344, Santa Barbara, CA, USA, August 20“24, 2006.

Springer-Verlag, Berlin, Germany. [452, 456, 461]

[JMV02] Antoine Joux, Gwena¨lle Martinet, and Fr´d´ric Valette.

e ee

Blockwise-adaptive attackers: Revisiting the (in)security of some

provably secure encryption models: CBC, GEM, IACBC. In Moti

Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 17“30,

Santa Barbara, CA, USA, August 18“22, 2002. Springer-Verlag,

Berlin, Germany. [238, 239]

[JN08] Marc Joye and Gregory Neven, editors. Identity-based Cryptog-

raphy, volume 2 of Cryptology and Information Security Series.

IOS Press, Amsterdam, 2008. [417]

[JNT07] Antoine Joux, David Naccache, and Emmanuel Thom´. When

e

e-th roots become easier than factoring. In Kaoru Kurosawa,

editor, ASIACRYPT 2007, volume 4833 of LNCS, pages 13“28,

Kuching, Malaysia, December 2“6, 2007. Springer-Verlag, Berlin,

Germany. [439]

[JP07] Antoine Joux and Thomas Peyrin. Hash functions and the

(ampli¬ed) boomerang attack. In Alfred Menezes, editor,

CRYPTO 2007, volume 4622 of LNCS, pages 244“263, Santa

Barbara, CA, USA, August 19“23, 2007. Springer-Verlag, Berlin,

Germany. [182]

[Jut01] Charanjit S. Jutla. Encryption modes with almost free message

integrity. In Birgit P¬tzmann, editor, EUROCRYPT 2001, vol-

ume 2045 of LNCS, pages 529“544, Innsbruck, Austria, May 6“10,

2001. Springer-Verlag, Berlin, Germany. [17]

[Kah67] David Kahn. The Codebreakers: The Comprehensive History

of Secret Communication from Ancient Times to the Internet.

Scribner, 1967. [11]

© 2009 by Taylor and Francis Group, LLC

482 Algorithmic Cryptanalysis

[Kan83] Ravi Kannan. Improved algorithms for integer programming and

related lattice problems. In Proc. 15th Symp. Theory of Comp.,

pages 193“206, 1983. [327, 328, 330]

[Ker83] Auguste Kerckho¬s. La cryptographie militaire. Journal des

sciences militaire, IX, 1883. Article in two parts: Jan. and Feb.

issues. [4]

[Knu94] Lars R. Knudsen. Truncated and higher order di¬erentials. In

Bart Preneel, editor, FSE™94, volume 1008 of LNCS, pages 196“

211, Leuven, Belgium, December 14“16, 1994. Springer-Verlag,

Berlin, Germany. [282, 392]

[KPT96] Jyrki Katajainen, Tomi Pasanen, and Jukka Teuhola. Practical

in-place mergesort. Nordic J. of Computing, 3(1):27“40, 1996.

[201]

[Kra01] Hugo Krawczyk. The order of encryption and authentication

for protecting communications (or: How secure is SSL?). In Joe

Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 310“

331, Santa Barbara, CA, USA, August 19“23, 2001. Springer-

Verlag, Berlin, Germany. [18]

[KS99] Aviad Kipnis and Adi Shamir. Cryptanalysis of the HFE public

key cryptosystem by relinearization. In Michael J. Wiener, editor,

CRYPTO™99, volume 1666 of LNCS, pages 19“30, Santa Barbara,

CA, USA, August 15“19, 1999. Springer-Verlag, Berlin, Germany.

[357]

[KVW04] Tadayoshi Kohno, John Viega, and Doug Whiting. CWC: A

high-performance conventional authenticated encryption mode.

In Bimal K. Roy and Willi Meier, editors, FSE 2004, volume

3017 of LNCS, pages 408“426, New Delhi, India, February 5“7,

2004. Springer-Verlag, Berlin, Germany. [17]

[Kwa00] Matthew Kwan. Reducing the gate count of bitslice DES. IACR

eprint archive, 2000. Report 2000/051. [163, 183]

[Lai94] Xuejia Lai. Higher order derivatives and di¬erential cryptanal-

ysis. In Communication and Cryptography “ Two Sides of One

Tapestry, pages 227“233. Kluwer Academic Publisher, 1994. [392]

[Lan05] Serge Lang. Algebra, volume 211 of Graduate Texts in Mathe-

matics. Springer, New York, 2005. Revised third edition. [37, 47,

48, 62, 110, 343]

[Laz83] Daniel Lazard. Gr¨bner bases, gaussian elimination and reso-

o

lution of systems of algebraic equations. In Computer algebra

(London, 1983), volume 162 of LNCS, pages 146“156. Springer-

Verlag, Berlin, Germany, 1983. [355]

© 2009 by Taylor and Francis Group, LLC

References 483

[LG89] Leonid A. Levin and Oded Goldreich. A Hard-core Predicate

for all One-way Functions. In D. S. Johnson, editor, 21th ACM

Symposium on Theory of Computing - STOC ™89, pages 25“32.

ACM Press, 1989. [286]

[LL93] Arjen K. Lenstra and Hendrick W. Lenstra, Jr., editors. The

development of the number ¬eld sieve, volume 1554 of Lecture

Notes in Mathematics. Springer-Verlag, Berlin, Germany, 1993.

[456, 461]

[LLL82] Arjen K. Lenstra, Hendrick W. Lenstra, Jr., and L´szl´ Lov´sz.

ao a

Factoring polynomials with rational coe¬cients. Math. Ann.,

261:515“534, 1982. [319]

[LMV05] Yi Lu, Willi Meier, and Serge Vaudenay. The conditional cor-

relation attack: A practical attack on bluetooth encryption. In

Victor Shoup, editor, CRYPTO 2005, volume 3621 of LNCS,

pages 97“117, Santa Barbara, CA, USA, August 14“18, 2005.

Springer-Verlag, Berlin, Germany. [380]

[LO85] Je¬rey C. Lagarias and Andrew M. Odlyzko. Solving low-density

subset sum problems. Journal of the ACM, 32(1):229“246, 1985.

[402, 406]

[LO91] Brian A. LaMacchia and Andrew M. Odlyzko. Solving large

sparse linear systems over ¬nite ¬elds. In Alfred J. Menezes and

Scott A. Vanstone, editors, CRYPTO™90, volume 537 of LNCS,

pages 109“133, Santa Barbara, CA, USA, August 11“15, 1991.

Springer-Verlag, Berlin, Germany. [113, 115]

[Luc05] Stefan Lucks. Two-pass authenticated encryption faster than

generic composition. In Henri Gilbert and Helena Handschuh,

editors, FSE 2005, volume 3557 of LNCS, pages 284“298, Paris,

France, February 21“23, 2005. Springer-Verlag, Berlin, Germany.

[17]

[Mar57] Harry M. Markowitz. The elimination form of the inverse and

its application to linear programming. Management Science,

3(3):255“269, 1957. [116]

[Mat93] Mitsuru Matsui. Linear cryptoanalysis method for DES cipher.

In Tor Helleseth, editor, EUROCRYPT™93, volume 765 of LNCS,

pages 386“397, Lofthus, Norway, May 23“27, 1993. Springer-

Verlag, Berlin, Germany. [273]

[Mat94a] Mitsuru Matsui. The ¬rst experimental cryptanalysis of the data

encryption standard. In Yvo Desmedt, editor, CRYPTO™94, vol-

ume 839 of LNCS, pages 1“11, Santa Barbara, CA, USA, Au-

gust 21“25, 1994. Springer-Verlag, Berlin, Germany. [273]

© 2009 by Taylor and Francis Group, LLC

484 Algorithmic Cryptanalysis

[Mat94b] Mitsuru Matsui. On correlation between the order of S-boxes

and the strength of DES. In Alfredo De Santis, editor, EURO-

CRYPT™94, volume 950 of LNCS, pages 366“375, Perugia, Italy,

May 9“12, 1994. Springer-Verlag, Berlin, Germany. [273]

[MG90] Miodrag J. Mihaljevic and Jovan Dj. Golic. A fast iterative al-

gorithm for a shift register initial state reconstruction given the

noisy output sequence. In Jennifer Seberry and Josef Pieprzyk,

editors, AUSCRYPT™90, volume 453 of LNCS, pages 165“175,

Sydney, Australia, January 8“11, 1990. Springer-Verlag, Berlin,

Germany. [380]

[MG02] Daniele Micciancio and Sha¬ Goldwasser. Complexity of Lat-

tice Problems: A Cryptographic Perspective, volume 671 of The

Kluwer International Series in Engineering and Computer Sci-

ence. Kluwer Academic Publishers, 2002. [311]

[Mil04] Victor S. Miller. The Weil pairing, and its e¬cient calculation.

Journal of Cryptology, 17(4):235“261, September 2004. [431]

[Mon92] Peter L. Montgomery. A FFT Extension of the Elliptic Curve

Method of Factorization. PhD thesis, University of California,

Los Angeles, 1992. [236, 435]

[Mon95] Peter L. Montgomery. A block Lanczos algorithm for ¬nding de-

pendencies over GF(2). In Louis C. Guillou and Jean-Jacques

Quisquater, editors, EUROCRYPT™95, volume 921 of LNCS,

pages 106“120, Saint-Malo, France, May 21“25, 1995. Springer-

Verlag, Berlin, Germany. [112]

[MP08] St´phane Manuel and Thomas Peyrin. Collisions on SHA“0 in

e

one hour. In Kaisa Nyberg, editor, FSE 2008, volume 5086

of LNCS, pages 16“35, Lausanne, Switzerland, February 10“13,

2008. Springer-Verlag, Berlin, Germany. [182]

[MS89] Willi Meier and Othmar Sta¬elbach. Fast correlation attacks

on certain stream ciphers. Journal of Cryptology, 1(3):159“176,

1989. [380]

[MSK98] Shiho Moriai, Takeshi Shimoyama, and Toshinobu Kaneko.

Higher order di¬erential attak of CAST cipher. In Serge Vau-

denay, editor, FSE™98, volume 1372 of LNCS, pages 17“31, Paris,

France, March 23“25, 1998. Springer-Verlag, Berlin, Germany.

[392]

[MT09] Ravi Montenegro and Prasad Tetali. How long does it take to

catch a wild kangaroo? In Michael Mitzenmacher, editor, 41st

ACM STOC, pages 1“10, Bethesda, Maryland, USA, May 31“

June 2 2009. ACM Press. [238]

© 2009 by Taylor and Francis Group, LLC

References 485

[MvOV97] Aldred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone,

editors. Handbook of Applied Cryptography. CRC Press LLC,

Boca Raton, Florida, 1997. [3]

[MY92] Mitsuru Matsui and Atsuhiro Yamagishi. A new method for

known plaintext attack of FEAL cipher. In Rainer A. Ruep-

pel, editor, EUROCRYPT™92, volume 658 of LNCS, pages 81“

91, Balatonf¨red, Hungary, May 24“28, 1992. Springer-Verlag,

u

Berlin, Germany. [273]

[Niv04] G. Nivasch. Cycle detection using a stack. Information Processing

Letter, 90(3):135“140, 2004. [229, 242]

[NP99] Wim Nevelsteen and Bart Preneel. Software performance of

universal hash functions. In Jacques Stern, editor, EURO-

CRYPT™99, volume 1592 of LNCS, pages 24“41, Prague, Czech

Republic, May 2“6, 1999. Springer-Verlag, Berlin, Germany. [8]

[NS05] Phong Q. Nguyen and Damien Stehl´. Floating-point LLL re-

e

visited. In Ronald Cramer, editor, EUROCRYPT 2005, volume

3494 of LNCS, pages 215“233, Aarhus, Denmark, May 22“26,

2005. Springer-Verlag, Berlin, Germany. [326]

[Odl85] Andrew M. Odlyzko. Discrete logarithms in ¬nite ¬elds and their

cryptographic signi¬cance. In Thomas Beth, Norbert Cot, and

Ingemar Ingemarsson, editors, EUROCRYPT™84, volume 209 of

LNCS, pages 224“314, Paris, France, April 9“11, 1985. Springer-

Verlag, Berlin, Germany. [113]

[OST06] Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks

and countermeasures: The case of AES. In David Pointcheval,

editor, CT-RSA 2006, volume 3860 of LNCS, pages 1“20, San

Jose, CA, USA, February 13“17, 2006. Springer-Verlag, Berlin,

Germany. [92]

[Pai99] Pascal Paillier. Public-key cryptosystems based on composite

degree residuosity classes. In Jacques Stern, editor, EURO-

CRYPT™99, volume 1592 of LNCS, pages 223“238, Prague, Czech

Republic, May 2“6, 1999. Springer-Verlag, Berlin, Germany. [64]

[Pan84] Victor Pan. How to multiply matrix faster, volume 179 of LNCS.

Springer-Verlag, Berlin, Germany, 1984. [89]

[Pat96] Jacques Patarin. Hidden ¬elds equations (HFE) and isomor-

phisms of polynomials (IP): Two new families of asymmetric al-

gorithms. In Ueli M. Maurer, editor, EUROCRYPT™96, volume

1070 of LNCS, pages 33“48, Saragossa, Spain, May 12“16, 1996.

Springer-Verlag, Berlin, Germany. [362, 363]

© 2009 by Taylor and Francis Group, LLC

486 Algorithmic Cryptanalysis

[PGF98] Daniel Panario, Xavier Gourdon, and Philippe Flajolet. An ana-

lytic approach to smooth polynomials over ¬nite ¬elds. In Third

Algorithmic Number Theory Symposium (ANTS), volume 1423 of

LNCS, pages 226“236. Springer-Verlag, Berlin, Germany, 1998.

[444]

[PK95] Walter T. Penzhorn and G. J. Kuhn. Computation of low-

weight parity checks for correlation attacks on stream ciphers.

In Cryptography and Coding “ 5th IMA Conference, volume 1025

of LNCS, pages 74“83. Springer-Verlag, Berlin, Germany, 1995.

[386]

[Pol75] John M. Pollard. A Monte Carlo method for factorization. BIT

Numerical Mathematics, 15(3):331“334, 1975. [233]

[Pom82] Carl Pomerance. Analysis and comparison of some integer fac-

toring methods. In Jr. Hendrik W. Lenstra and Robert Tijde-

man, editors, Computational methods in number theory “ Part I,

volume 154 of Mathematical centre tracts, pages 8“139. Mathe-

matisch Centrum, Amsterdam, 1982. [141]

[Pri81] Paul Pritchard. A sublinear additive sieve for ¬nding prime num-

bers. Communications of the ACM, 24(1):18“23, 1981. [128, 133]

[Pri83] Paul Pritchard. Fast compact prime number sieves (among oth-

ers). Journal of algorithms, 4:332“344, 1983. [133]

[QD90] Jean-Jacques Quisquater and Jean-Paul Delescaille. How easy is

collision search. New results and applications to DES. In Gilles

Brassard, editor, CRYPTO™89, volume 435 of LNCS, pages 408“

413, Santa Barbara, CA, USA, August 20“24, 1990. Springer-

Verlag, Berlin, Germany. [229, 244]

[RBBK01] Phillip Rogaway, Mihir Bellare, John Black, and Ted Krovetz.

OCB: A block-cipher mode of operation for e¬cient authenti-

cated encryption. In ACM CCS 01, pages 196“205, Philadelphia,

PA, USA, November 5“8, 2001. ACM Press. [15, 17]

[RH07] Sondre Rønjom and Tor Helleseth. A new attack on the ¬lter gen-

erator. IEEE Transactions on Information Theory, 53(5):1752“

1758, 2007. [388, 389]

[Sch87] Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis

reduction algorithms. Theoretical Computer Science, 53:201“224,

1987. [331]

[Sch90] Claus-Peter Schnorr. E¬cient identi¬cation and signatures for

smart cards. In Gilles Brassard, editor, CRYPTO™89, volume 435

of LNCS, pages 239“252, Santa Barbara, CA, USA, August 20“

24, 1990. Springer-Verlag, Berlin, Germany. [67]

© 2009 by Taylor and Francis Group, LLC

References 487

[Sch91] Claus-Peter Schnorr. E¬cient signature generation by smart

cards. Journal of Cryptology, 4(3):161“174, 1991. [10]

[Sch93] Oliver Schirokauer. Discrete logarithms and local units. Phil.

Trans. R. Soc. Lond. A 345, pages 409“423, 1993. [461]

[Sch96] Bruce Schneier. Applied Cryptography (Second Edition). John

Wiley & Sons, 1996. [3]

[SE94] Claus-Peter Schnorr and M. Euchner. Lattice basis reduction:

Improved practical algorithms and solving subset sum problems.

Math. Program., 66:181“199, 1994. [326, 328]

[Sha49] Claude E. Shannon. Communication theory of secrecy systems.

Bell System Technical Journal, 28:656“715, 1949. [4, 337]

[Sie84] T. Siegenthaler. Correlation-immunity of nonlinear combining

functions for cryptographic applications. IEEE Trans. on Infor-

mation Theory, IT-30:776“780, 1984. [378]

[Sie85] T. Siegenthaler. Decrypting a class of stream ciphers using ci-

phertext only. IEEE Trans. Comput., C-34:81“85, 1985. [378]

[Sil86] Joseph H. Silverman. The Arithmetic of Elliptic Curves, volume

106 of Graduate Texts in Mathematics. Springer, New York, 1986.

[417, 424, 431]

[Sim82] Gustavus J. Simmons. A system for point-of-sale or access

user authentication and identi¬cation. In Allen Gersho, editor,

CRYPTO™81, volume ECE Report 82-04, pages 31“37, Santa

Barbara, CA, USA, 1982. U.C. Santa Barbara, Dept. of Elec.

and Computer Eng. [8]

[Sim85] Gustavus J. Simmons. Authentication theory/coding theory. In

G. R. Blakley and David Chaum, editors, CRYPTO™84, volume

196 of LNCS, pages 411“431, Santa Barbara, CA, USA, Au-

gust 19“23, 1985. Springer-Verlag, Berlin, Germany. [8]

[Sim86] Gustavus J. Simmons. The practice of authentication. In Franz

Pichler, editor, EUROCRYPT™85, volume 219 of LNCS, pages

261“272, Linz, Austria, April 1986. Springer-Verlag, Berlin, Ger-

many. [8]

[Sor98] Jonathan P. Sorenson. Trading time for space in prime number

sieves. In Third Algorithmic Number Theory Symposium (ANTS),

volume 1423 of LNCS, pages 179“195. Springer-Verlag, Berlin,

Germany, 1998. [133]

[SS81] Richard Schroeppel and Adi Shamir. A T = O(2n/2 ), S =

O(2n/4 ) algorithm for certain NP-complete problems. SIAM

Journal on Computing, 10(3):456“464, 1981. [251]

© 2009 by Taylor and Francis Group, LLC

488 Algorithmic Cryptanalysis

[Sti02] Douglas Stinson. Cryptography: Theory and Practice (Third Edi-

tion). CRC Press LLC, Boca Raton, Florida, 2002. [3]

[Str69] Volker Strassen. Gaussian elimination is not optimal. Numer.

Math., 13:354“356, 1969. [80]

[TCG92] Anne Tardy-Corfdir and Henri Gilbert. A known plaintext at-

tack of FEAL-4 and FEAL-6. In Joan Feigenbaum, editor,

CRYPTO™91, volume 576 of LNCS, pages 172“181, Santa Bar-

bara, CA, USA, August 11“15, 1992. Springer-Verlag, Berlin,

Germany. [273]

[TSM94] Toshio Tokita, Tohru Sorimachi, and Mitsuru Matsui. Lin-

ear cryptanalysis of LOKI and s2DES. In Josef Pieprzyk and

Reihaneh Safavi-Naini, editors, ASIACRYPT™94, volume 917 of

LNCS, pages 293“303, Wollongong, Australia, November 28 “

December 1, 1994. Springer-Verlag, Berlin, Germany. [273]

[Val91] Brigitte Vall´e. Gauss™ algorithm revisited. J. Algorithms, 12(4),

e

1991. [318]

[vW96] Paul C. van Oorschot and Michael J. Wiener. Improving im-

plementable meet-in-the-middle attacks by orders of magnitude.

In Neal Koblitz, editor, CRYPTO™96, volume 1109 of LNCS,

pages 229“236, Santa Barbara, CA, USA, August 18“22, 1996.

Springer-Verlag, Berlin, Germany. [244]

[Wag99] David Wagner. The boomerang attack. In Lars R. Knudsen,

editor, FSE™99, volume 1636 of LNCS, pages 156“170, Rome,

Italy, March 24“26, 1999. Springer-Verlag, Berlin, Germany. [182]

[Wag02] David Wagner. A generalized birthday problem. In Moti Yung,

editor, CRYPTO 2002, volume 2442 of LNCS, pages 288“303,

Santa Barbara, CA, USA, August 18“22, 2002. Springer-Verlag,

Berlin, Germany. [264, 265]

[Was03] Lawrence C. Washington. Elliptic curves: number theory and

cryptography. CRC Press LLC, Boca Raton, Florida, 2003. [422]

[WC81] Mark N. Wegman and Larry Carter. New hash functions and their

use in authentication and set equality. Journal of Computer and

System Sciences, 22:265“279, 1981. [8]

[Wie90] Michael J. Wiener. Cryptanalysis of short RSA secret expo-

nents (abstract). In Jean-Jacques Quisquater and Joos Vande-

walle, editors, EUROCRYPT™89, volume 434 of LNCS, page 372,

Houthalen, Belgium, April 10“13, 1990. Springer-Verlag, Berlin,

Germany. [414]

[Wie04] Michael J. Wiener. The full cost of cryptanalytic attacks. Journal

of Cryptology, 17(2):105“124, March 2004. [5]

© 2009 by Taylor and Francis Group, LLC

References 489

[WYY05a] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. E¬cient

collision search attacks on SHA-0. In Victor Shoup, editor,

CRYPTO 2005, volume 3621 of LNCS, pages 1“16, Santa Bar-

bara, CA, USA, August 14“18, 2005. Springer-Verlag, Berlin,

Germany. [179, 182]

[WYY05b] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding colli-

sions in the full SHA-1. In Victor Shoup, editor, CRYPTO 2005,

volume 3621 of LNCS, pages 17“36, Santa Barbara, CA, USA,

August 14“18, 2005. Springer-Verlag, Berlin, Germany. [179, 182]

[XM88] Guo-Zhen Xiao and James L. Massey. A spectral characterization

of correlation-immune combining functions. IEEE Transactions

on Information Theory, 34(3):569“571, 1988. [275]

[Yuv79] Gideon Yuval. How to swindle Rabin. Cryptologia, 3:187“189,

1979. [243]

[ZF06] Bin Zhang and Dengguo Feng. Multi-pass fast correlation at-

tack on stream ciphers. In Eli Biham and Amr M. Youssef, edi-

tors, SAC 2006, volume 4356 of LNCS, pages 234“248, Montreal,

Canada, August 17“18, 2006. Springer-Verlag, Berlin, Germany.

[380]

[Zha05] Fuzhen Zhang, editor. The Schur Complement and Its Applica-

tions (Numerical Methods and Algorithms). Springer, New York,

2005. [94]

[Zhe97] Yuliang Zheng. Digital signcryption or how to achieve

cost(signature & encryption) < cost(signature) + cost(en-

cryption). In Burton S. Kaliski Jr., editor, CRYPTO™97, vol-

ume 1294 of LNCS, pages 165“179, Santa Barbara, CA, USA,

August 17“21, 1997. Springer-Verlag, Berlin, Germany. [20]

© 2009 by Taylor and Francis Group, LLC

Lists

List of Algorithms

2.1 Euclid™s greatest common divisor algorithm . . . . . . . . . . 28

2.2 Euclid™s extended algorithm . . . . . . . . . . . . . . . . . . . 29

2.3 GCD of a list of numbers . . . . . . . . . . . . . . . . . . . . 30

2.4 Stein™s binary greatest common divisor algorithm . . . . . . . 32

2.5 Addition modulo N ....................... 35

2.6 Subtraction modulo N . . . . . . . . . . . . . . . . . . . . . . 35

2.7 Multiplication modulo N .................... 36

2.8 Multiplicative inverse modulo N . . . . . . . . . . . . . . . . 36

2.9 Exponentiation in Z/N Z, left-to-right version . . . . . . . . . 36

2.10 Exponentiation in Z/N Z, right-to-left version . . . . . . . . . 37

2.11 Shanks-Tonelli algorithm for square roots in Fp . . . . . . . . 40

2.12 Computation of Jacobi symbols . . . . . . . . . . . . . . . . . 42

2.13 Stein™s greatest common divisor algorithm for polynomials . . 46

2.14 Berlekamp-Massey algorithm . . . . . . . . . . . . . . . . . . 56

2.15 Squarefree factorization of polynomials . . . . . . . . . . . . . 58

2.16 Distinct degree factorization of a squarefree polynomial . . . 58

2.17 Final splitting of polynomials . . . . . . . . . . . . . . . . . . 60

3.1 Elementary square matrix multiplication . . . . . . . . . . . . 72

3.2 Strassen matrix multiplication (rounding up) . . . . . . . . . 82

3.3 Strassen matrix multiplication (rounding down) . . . . . . . . 83

3.4 Triangularization of a linear system (simpli¬ed, incorrect) . 95

3.5 Backtracking to solve a triangular system . . . . . . . . . . . 95

3.6 Triangularization of a linear system . . . . . . . . . . . . . . . 97

3.7 Matrix inversion . . . . . . . . . . . . . . . . . . . . . . . . . 99

3.8 Triangularization of a possibly non-invertible system . . . . . 101

3.9 Backtracking of a possibly non-invertible triangular system . 102

3.10 Hermite normal forms . . . . . . . . . . . . . . . . . . . . . . 104

3.11 Lanczos™s algorithm over ¬nite ¬elds . . . . . . . . . . . . . . 109

491

© 2009 by Taylor and Francis Group, LLC

492 Algorithmic Cryptanalysis

4.1 Eratosthenes™s sieve . . . . . . . . . . . . . . . . . . . . . . . 124

Sieve of Atkin and Bernstein for primes ≡ 1 (mod 4) . . . . .

4.2 134

4.3 Two-dimensional sieving for smooth numbers . . . . . . . . . 139

4.4 Walking the multiples with polynomials . . . . . . . . . . . . 145

4.5 Walking the multiples with numbers . . . . . . . . . . . . . . 146

4.6 Basic line sieve . . . . . . . . . . . . . . . . . . . . . . . . . . 149

6.1 Generating all collisions in a sorted list . . . . . . . . . . . . . 193

6.2 Dichotomy search . . . . . . . . . . . . . . . . . . . . . . . . . 195

6.3 Bubble sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

6.4 Find minimal element . . . . . . . . . . . . . . . . . . . . . . 197

6.5 Selection sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

6.6 Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

6.7 Merge sort main procedure . . . . . . . . . . . . . . . . . . . 200

6.8 Merge sort wrapper . . . . . . . . . . . . . . . . . . . . . . . . 201

6.9 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

6.10 Radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

6.11 Heap sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

6.12 Insertion in heap procedure . . . . . . . . . . . . . . . . . . . 205

6.13 Count sort: Beating the sort lower bound . . . . . . . . . . . 206

6.14 Collision search using hash tables . . . . . . . . . . . . . . . . 209

6.15 Avoiding cache misses with hash tables . . . . . . . . . . . . . 211

6.16 Insertion in a binary search tree . . . . . . . . . . . . . . . . . 214

6.17 Deletion in a binary search tree . . . . . . . . . . . . . . . . . 215

6.18 Pohlig-Hellman discrete logarithm algorithm . . . . . . . . . . 218

6.19 Baby-step, giant-step discrete logarithm algorithm . . . . . . 219

7.1 Floyd™s cycle detection algorithm . . . . . . . . . . . . . . . . 225

7.2 Brent™s cycle detection algorithm . . . . . . . . . . . . . . . . 226

7.3 Algorithm for recovering a cycle™s start . . . . . . . . . . . . . 228

7.4 Nivasch™s cycle detection algorithm . . . . . . . . . . . . . . . 230

7.5 Pollard™s Rho factoring algorithm . . . . . . . . . . . . . . . . 235

8.1 Initialization of Shamir and Schroeppel algorithm . . . . . . . 255

8.2 Get next knapsack sum with Shamir and Schroeppel algorithm 255

8.3 Generating all solutions to Equation (8.10) . . . . . . . . . . 259

8.4 Alternative option to Algorithm 8.3 . . . . . . . . . . . . . . 260

9.1 Algorithm for computing di¬erential characteristics . . . . . . 274

9.2 Algorithm for computing linear characteristics . . . . . . . . . 275

© 2009 by Taylor and Francis Group, LLC

Lists 493

9.3 Walsh transform algorithm . . . . . . . . . . . . . . . . . . . 276

9.4 Inverse Walsh transform algorithm . . . . . . . . . . . . . . . 277

9.5 Algorithm for truncated di¬erential characteristics . . . . . . 283

9.6 Moebius transform algorithm . . . . . . . . . . . . . . . . . . 286

9.7 Pre-Walsh transform encoding over Fp . . . . . . . . . . . . . 291

9.8 Walsh transform algorithm over Fp . . . . . . . . . . . . . . . 292

9.9 Moebius transform algorithm over Fp . . . . . . . . . . . . . . 295

9.10 Fast Fourier transform algorithm on N = 2n values . . . . . . 298

9.11 Core transform of extended Walsh over Fp . . . . . . . . . . . 301

10.1 Gauss™s reduction algorithm . . . . . . . . . . . . . . . . . . . 312

10.2 t-Gauss reduction algorithm . . . . . . . . . . . . . . . . . . . 317

10.3 Gram-Schmidt algorithm .................... 320

10.4 LLL algorithm using rationals . . . . . . . . . . . . . . . . . . 322

10.5 Length reduction subalgorithm RED(i, j) . . . . . . . . . . . . 323

10.6 A basic short vector enumeration algorithm . . . . . . . . . . 329

10.7 Kannan™s HKZ reduction algorithm . . . . . . . . . . . . . . . 331

11.1 Computation of normal form . . . . . . . . . . . . . . . . . . 349

11.2 Basic version of Buchberger™s algorithm . . . . . . . . . . . . 353

11.3 Reduction of a Gr¨bner basis . . . . . . . . . . . . . . . . . .

o 355

11.4 A basic linear algebra based Gr¨bner basis algorithm . . . . .

o 358

12.1 Computing formal expression of LFSR outputs . . . . . . . . 384

14.1 Miller™s algorithm with double and add ............ 432

14.2 Pollard™s p ’ 1 factoring algorithm . . . . . . . . . . . . . . . 433

15.1 Compute number of smooth polynomials . . . . . . . . . . . . 466

List of Figures

1.1 Some classical encryption modes . . . . . . . . . . . . . . . . 7

2.1 Ordinary LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.2 Galois LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.1 MMX and SSE instructions . . . . . . . . . . . . . . . . . . . 75

3.2 Winograd™s formulas for matrix multiplication . . . . . . . . . 84

3.3 Performance of Strassen™s multiplication over F2 . . . . . . . 87

3.4 Performance of Strassen™s multiplication over Fp . . . . . . . 91

3.5 Principles of cached memory in processors . . . . . . . . . . . 92

© 2009 by Taylor and Francis Group, LLC

494 Algorithmic Cryptanalysis

3.6 E¬ect of a pivoting step . . . . . . . . . . . . . . . . . . . . . 96

4.1 Schematic picture of wheel factorization . . . . . . . . . . . . 127

4.2 Multiples of 7 in a wheel of perimeter 30 . . . . . . . . . . . . 131

4.3 Set of points a + b± divisible by (11, 5) . . . . . . . . . . . . . 137

4.4 Gray codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.5 Illustration of Algorithm 4.5 . . . . . . . . . . . . . . . . . . . 147