<<

. 17
( 18)



>>

As a consequence, given d1 and d2 , the minimum we can hope to achieve
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

<<

. 17
( 18)



>>