<<

. 15
( 18)



>>

NTRU lattices is given in [GN08].
It is also worth mentioning that combined attacks mixing lattice reduction
and birthday paradox methods can be devised for NTRU (see [HG07]).

13.1.2.4 Cryptanalysis of Damg˚
ard™s hash function
In [Dam90], among other options, Damg˚ proposed to base a hash func-
ard
tion on a knapsack compression function using 256 (non-modular) numbers ai
of size 120 bits. His idea was to divide the message to be hashed into blocks
of 128 bits, and to apply the following process:
• Start with a ¬xed initial value on 128 bits. Appending the ¬rst 128-bit
block of the message, one gets a block B of 256 bits.
• (Compression phase.) Compute the knapsack transform of these 256
bits, i.e., starting from zero, add up all ai s whose index corresponds to
the position of a one bit of B. The resulting number can be encoded
using 128 bits.
• Append the next block to get 256 bits and iterate the compression phase.
In order to ¬nd a collision for this hash function, it is clearly enough to
¬nd two di¬erent 128-bit blocks that, when appended to the initial value,
yield the same hash value. This clearly corresponds to ¬nding a collision in
a knapsack transform based on 128 numbers of 120 bits. In the sequel, we
study how collisions in such a knapsack transform can be found using lattice
reduction, and we show that it is feasible to build collisions for Damg˚ ard™s
hash function. A completely di¬erent kind of attack against this construction
has already appeared in the work of P. Camion and J. Patarin ([CP91]). Still,
it has never been implemented, and besides, it could only ¬nd collisions for
the compression function rather than for the hash function itself. In contrast
to this approach, our attack runs on a computer and actually outputs collision
for the size of the parameters suggested by Damg˚ ard.
Unfortunately, our attack cannot be proven, even in the lattice oracle setting
described in Section 13.1.2.1. Nevertheless, for a slightly weaker notion of
a collision, which we call pseudo-collision, a correct mathematical analysis
can be carried through. A pseudo-collision for Damg˚ ard™s hash function
consists of two messages whose hash values coincide except for the 8 leading
bits. The practical signi¬cance of pseudo-collisions is obvious since pseudo-
collisions have a non-negligible chance of being actual collisions.

13.1.2.4.1 The basic strategy In this section, we associate a lattice to
any given knapsack-based compression-function in such a way that collisions




© 2009 by Taylor and Francis Group, LLC
406 Algorithmic Cryptanalysis

correspond to short vectors. Before describing the reduction, we make our
de¬nitions and notations a bit more precise: we ¬x a sequence of integers,
a = a1 , . . . , an . The knapsack-compression function Sa , which we simply
denote by S, takes as input any vector x in {0, 1}n and computes
n
S(x) = a i xi
i=1

A collision for this function consists of two values x and x such that S(x) =
S(x ).
In order to search collisions, we reduce the lattice given by the columns of
the following matrix:
« 
Ka1 Ka2 · · · Kan
0 ··· 0 ·
¬1
¬ ·
1 ··· 0 ·.
¬0
B=¬ ·
¬. . .. .·
. . ..
. . .
0 ··· 1
0
Note that this lattice is exactly the lattice used in the original Lagarias-
Odlyzko attack for solving knapsack problems (see [LO85]). Let us consider
the possible output of lattice reduction. Since K is large, it is clear that the
¬rst coordinate of a short vector is 0. As for the other coordinates, we expect
them to be all 0, 1 or ’1. Indeed, if this happens we clearly get a collision:
from an element of the lattice
···
e = (0 n ).
1 2

with all coordinates 0, 1 or ’1, we ¬nd that
n
i ai =0
i=1

and thus obtain a collision:
ai = ai .
i =1 i =’1



Analysis of the attack With the attack as was stated above, ¬nding a
ard™s hash function can be done in practice, using L3 to
collision for Damg˚
compute collisions for a knapsack compression function based on 128 numbers
with 120 bits each. This was described in [JG94].
Surprisingly, despite these practical results, a theoretical analysis shows
that asymptotically, the attack as presented does not work. However, it is
possible to slightly modify the attack and obtain an exponential attack with
complexity around 2n/1000 . This explains why the attack works for the values
of n suggested in [Dam90].




© 2009 by Taylor and Francis Group, LLC
Lattice-based cryptanalysis 407




13.2 Coppersmith™s small roots attacks
13.2.1 Univariate modular polynomials
In general, the problem of ¬nding a root of a univariate polynomial f (x)
modulo an integer N of unknown factorization is a di¬cult problem. Indeed,
it is well known that ¬nding a root of x2 ’ r2 (mod N ) for a random value
r, usually yields a (partial) factorization of N ; see Section 2.3.3.1. On the
contrary, when the factorization of N is known, it is easy to ¬nd roots of f
modulo each prime factor and paste them together with the Chinese remainder
theorem, using a Hensel lifting step to deal with multiple factors of N . On
the other hand, when f has roots over the integers, it is easy to ¬nd them and
use them as roots modulo N . For example, ¬nding a root of x2 ’ 4 modulo a
large integer N is easy. This example can be generalized to any polynomial
d
f with small enough coe¬cients. Write f (x) = i=0 f (i) xi and denote by
d (i) i
|f | the polynomial de¬ned by |f |(x) = i=0 |f |x whose coe¬cients are
the absolute values of the coe¬cients of f . If B is a positive integer such
that |f |(B) < N , then for all integers x such that ’B ¤ x ¤ B, we have
’N < f (x) < N . As a consequence, any root x of f modulo N that lies the
interval [’B, B] is also a root of f over the ring of integers. As a consequence,
it can be easily found.
The ¬rst small root algorithm of Coppersmith extends this idea beyond its
initial range. It plays on the two sides of the inequality |f |(B) < N in order
to allow larger values for B. On the right-hand side, N is replaced by some
power of N ; on the left-hand side, f is replaced by another polynomial F with
smaller coe¬cients. One basic remark behind Coppersmith™s construction is
that if we denote by Fi,j,k the polynomial Fi,j,k (x) = xi f (x)j N k , then any
root r of f modulo N is also a root of Fi,j,k modulo N j+k . Let us choose a
parameter t and look at polynomials of the form Fi,j,t’j ; they all share the
root r modulo N t . In addition, the degree of Fi,j,t’j is i + j · deg(f ). It is
convenient to choose a bound D on the allowed degree and consider a set of
polynomials Fi,j,t’j of degree at most D.

13.2.1.1 Howgrave-Graham™s variation

In fact, it is easier to ¬rst describe a variation of Coppersmith™s ¬rst small
root algorithm, as presented in [HG97]. In this version, we use the fact that
since all polynomials, in the set of polynomials Fi,j,t’j of bounded degree, have
the common root r modulo N t , any linear combination of these polynomials
also has the same root modulo N t . Our goal is now to ¬nd such a linear
combination F that maximizes the possible bound B satisfying the constraint
|F |(B) < N t . Invoking our early remarks, we can then ¬nd the root r under
D
the condition |r| < B. Once again writing, F (x) = i=0 F (i) xi , we can see




© 2009 by Taylor and Francis Group, LLC
408 Algorithmic Cryptanalysis

that |F |(B) is the · of the row vector:
1


VF = (F (0) , BF (1) , B 2 F (2) , · · · , B D F (D) ). (13.13)

Thus, the best possible polynomial that can be obtained from a family of
polynomials Fi,j,t’j corresponds to the shortest non-zero vector in norm · 1
in the lattice generated by the row vectors VFi,j,t’j .
Finding this best possible polynomial is not possible for two reasons: ¬rst
available lattice reduction algorithms work on the Euclidean norm and not the
· 1 norm; second, even considering the Euclidean norm, we do not generally
obtain the shortest non-zero vector in the lattice. However, the good news
is that the shortest vector that can be found using existing lattice reduction
algorithms su¬ces to obtain a polynomial F with |F |(B) < N t for a large
value of B. We now analyze this lattice in order to establish the relationship
between the bound B, the parameters t and D, the size of the coe¬cients of
f and of the modulus N .

13.2.1.1.1 Properties of the lattice of Howgrave-Graham Through-
out the analysis, we assume that the bound B is a ¬xed parameter. We assess
the largest value of B that can be obtained at the very end of the analysis.
We start from a set of integer pairs S and we construct a lattice LS (f )
generated by the family of vectors VFi,j,t’j de¬ned as in Equation (13.13)
from the polynomials Fi,j,t’j , for (i, j) ∈ S. When choosing S, it is useful to
make sure that this generating family is in fact a basis of LS (f ), thus avoiding
trivial dependencies between the vectors. For example, if S contains (0, 2) and
(0, 1), (1, 1), . . . (d, 1) such a trivial dependency occurs. Indeed, assuming that
t = 2, these pairs correspond to the polynomials, f 2 , N f , N xf , . . . , N xd f
which are related by:
d
2
f (i) (N xi f ).
N ·f = (13.14)
i=0

Thus, it is a good strategy to keep the parameter i below the degree d of the
starting polynomial f . With this in mind, a natural choice for the set S is
the direct product [0 . . . d ’ 1] — [0 . . . t]. With this choice, we have d(t + 1)
polynomials of degree at most D = d(t + 1) ’ 1 and the generating family
of LS is a square matrix of dimension D + 1 = d(t + 1). The next step to
obtain information about the lattice is to compute the determinant of the
square matrix. To do this, remark that since the lattice is generated by using
the encoding described in Equation (13.13) we can factor B out of the second
column of the matrix, B 2 out of the third and so on. All in all, this implies
that B D(D+1)/2 can be be factored out of the determinant. Similarly, we can
factor N t out of each polynomial Fi,0,t , N t’1 out of Fi,1,t’1 and so on. The
total contribution to the determinant is N dt(t+1)/2 = N (D+1)t/2 . After this,
there remains a triangular matrix whose diagonal entries are powers of the
highest degree coe¬cient of f .




© 2009 by Taylor and Francis Group, LLC
Lattice-based cryptanalysis 409

At that point, we need to mention that multiplying f by the modular inverse
of its high degree coe¬cient, we can always assume that f is unitary. The only
way this could fail is by revealing of factor of N ; in that case, we can work
modulo each of the revealed factors1 . When f is unitary, the determinant
of the lattice LS as above is N (D+1)t/2 B D(D+1)/2 . Using Equation (10.24)
from Section 10.3.2, we see that we can thus ¬nd a short vector V in LS of
Euclidean norm satisfying:

¤ 2D/4 N t/2 B D/2 .
V (13.15)

¤
Since V D+1 V we associate to V a polynomial F such that:
1

|F |(B) ¤ D + 1 · 2D/4 N t/2 B D/2 . (13.16)

In order to make sure that |F |(B) < N t we need to choose t and D that
satisfy: √

D + 1( 2 · B)D/2 < N t/2 . (13.17)

Ignoring the D + 1 factor and taking logarithms, the largest value of B that
can be achieved satis¬es: √
( 2 · B)D ≈ N t . (13.18)

Letting t grow, we ¬nd that asymptotically, we can achieve B ≈ N 1/d / 2.
It is nice to note that in this context of Coppersmith™s attack, the 2D/4

approximation factor only changes the bound B by a factor 2 compared to
an ideal lattice reduction oracle. Since a constant factor on B can be gained
by exhaustively trying a small number of bits of the root we seek, we see that
where Coppersmith™s attack is concerned, the L3 algorithm is essentially as
satisfactory as a lattice reduction oracle.

13.2.1.2 Coppersmith™s original method
Starting from the same set of polynomials Fi,j,t’j of degree at most D,
Coppermith proceeds di¬erently. He remarks that, since r is a common root
of all these polynomials, the vector:

W (r) = (1, r, r2 , . . . , rD )

is orthogonal to the vectors representing each of these polynomials. As in
Chapter 11, we map vectors to polynomials and vice versa using a monomial
ordering. Moreover, with univariate monomials, it is clear that monomials
are simply sorted by degree.
Thus, instead of looking for a short vector in the lattice generated by
the vectors corresponding to the polynomials Fi,j,t’j , Coppersmith™s method

1 Infact, in many cases, if the factorization is revealed, the attacker succeeds and can abort
his attack.




© 2009 by Taylor and Francis Group, LLC
410 Algorithmic Cryptanalysis

looks for the vector W (r) which belongs to the orthogonal of this lattice.
As with Howgrave-Graham™s variation, ad-hoc multipliers should appear in
each coordinate to guarantee that we look for a short vector. To choose the
multipliers, recalling that |r| < B it su¬ces to remark that:

1
· (1, r/B, (r/B)2 , . . . , (r/B)D )
W (r) = √
D+1
is a short vector of norm less than 1, since all of its D + 1 coordinates are

smaller than 1/ D + 1 in absolute value.√
More precisely, Coppersmith let δ = 1/ D + 1 and considers the lattice L
generated by the rows of the following matrix:

[x0 ]F0,0,t [x0 ]F1,0,t · · · [x0 ]Fd’1,t,0
« 
···
δ 0 0 0
¬ 0 δ · B ’1 [x1 ]F0,0,t [x1 ]F1,0,t · · · [x1 ]Fd’1,t,0 ·
···
0 0
δ · B ’2 · · · [x2 ]F0,0,t [x2 ]F1,0,t · · · [x2 ]Fd’1,t,0 ·
¬ ·
¬0 0 0
¬ ·
¬. . . . . . .
.. ..
¬. . . . . . . ·
. .
. . . . . . . ·,
·
¬
· · · δ · B ’D [xD ]F0,0,t [xD ]F1,0,t · · · [xD ]Fd’1,t,0 ·
¬0 0 0
¬ ·
Nt
··· ···
¬0 0 0 0 0 0 ·
¬ ·
Nt
··· ···
0 0 0 0 0 0 
Nt
··· ···
0 0 0 0 0 0

where [xi ]F denotes the coe¬cient of xi in F . Clearly W (r) is a short vector
in the sublattice of L with zeros everywhere on the right coordinates. In fact,
the matrix given in [Cop96b] is obtained by factoring out extra powers of N
in the right-hand part of the matrix. Indeed, it is possible to factor N t’j out
the coe¬cients of Fi,j,t’j .
One important feature of Coppersmith™s attack is that instead of looking
at the ¬rst vector of the L3 reduced basis in order to ¬nd W (r), it focuses on
the last vector of the lattice. If the norm of the Gram-Schmidt orthogonalized
of this last vector is large enough, then it cannot appear in the decomposi-
tion of W (r). As a consequence, W (r) is orthogonal to this orthogonalized
vector. In other words, the orthogonalized vector can be transformed into a
polynomial with r as a root over Z.
In [HG97], it is shown that the original approach of Coppersmith and
Howgrave-Graham™s method are related through lattice duality. Following
Section 10.5, this relationship explains why we need to consider the ¬rst vec-
tor with one lattice and the last one with the other.


13.2.2 Bivariate polynomials
Another di¬cult problem is to ¬nd integral solutions of polynomial equa-
tions in two unknowns. For example, if we could ¬nd the roots of xy ’ N , we
could clearly factor N . The second small root algorithm of Coppersmith pre-
cisely addresses this case. Assume that we are given an irreducible polynomial




© 2009 by Taylor and Francis Group, LLC
Lattice-based cryptanalysis 411

f (x, y) with integer (or rational) coe¬cients and an integral root (x0 , y0 ) such
that |x0 | ¤ Bx and |y0 | ¤ By for some bounds Bx and By . We would like to
determine a method that recovers (x0 , y0 ) assuming that Bx and By are small
enough. Note that this notion of “smallness” can no longer be related to the
modulus; instead, we need to relate Bx and By with the size of coe¬cients
d d
occuring in f . More precisely, writing f (x, y) = i=0 j=0 fi,j xi y j , the rele-
ij
vant parameter is M (f ) = maxi,j Bx By |fi,j |. Let Fi,j denote the polynomial
xi y j f (x, y). Of course, (x0 , y0 ) is a common root of all polynomials in this
family. Let us choose a set S of pairs of non-negative integers. We say that a
polynomial g(x, y) has its support in S if and only if all monomials xi y j that
appear with non-zero coe¬cients in g are such that (i, j) ∈ S. When g has
its support in S, we can write:

g (i,j) xi y j ,
g= (13.19)
(i,j)∈S

in this case, we let |g| denote the polynomial:

|g (i,j) |xi y j ,
|g| = (13.20)
(i,j)∈S

We can now encode g into a vector, following a graded monomial ordering:

Vg(S) = (g (0,0) , Bx g (1,0) , By g (0,1) , · · · , Bx By g (i,j) , · · · ).
ij
(13.21)

In fact, the order of coe¬cients of g in this vector is unessential, as long as we
make the same choice for all polynomials that we encode. However, following
a monomial ordering makes things easier to write down. When S is clear from
the context, we omit it and write Vg .
In parallel, based on the same order, we may encode the (unknown) root
(x0 , y0 ) into an (unknown) vector:
1
(S)
· (1, x0 /Bx , y0 /By , · · · , (x0 /Bx )i (y0 /By )j , · · · ).
W(x0 ,y0 ) = (13.22)
|S|
When g has its support in S and when (x0 , y0 ) is a root of g, we see that:
(S)
(Vg(S) | |S| · W(x0 ,y0 ) ) = g (i,j) Bx By (x0 /Bx )i (y0 /By )j
ij

(i,j)∈S
j
g (i,j) xi y0 = g(x0 , y0 ) = 0.
= (13.23)
0
(i,j)∈S

(S) (S)
Thus, the vector W(x0 ,y0 ) is orthogonal to Vg .
Now, given a set S, we construct a lattice LS (f ) as follows:
• Consider all polynomials Fi,j with support in S and construct the cor-
S
responding vector VFi,j .




© 2009 by Taylor and Francis Group, LLC
412 Algorithmic Cryptanalysis

• Let LS (f ) be the lattice spanned by the above vectors.

S
If (x0 , y0 ) is a root of f , it is also a root of each Fi,j , thus W(x0 ,y0 ) is orthogonal
to the lattice LS (f ). In addition, if |x0 | ¤ Bx and |y0 | ¤ By , we see that
S S
W(x0 ,y0 ) ¤ 1. As a consequence, W(x0 ,y0 ) is a short vector in the orthogonal
of the lattice LS (f ).
S
Of course, (x0 , y0 ) can be recovered from W(x0 ,y0 ) , thus a natural approach
to solve the equation f (x, y) = 0 is to use lattice reduction to ¬nd a short
vector in the orthogonal lattice. However, as with Coppersmith™s ¬rst algo-
rithm, to provably obtain the solution (x0 , y0 ), we need to make sure that no
other short vector can hide the solution. To avoid this di¬culty, Coppersmith
S
instead proves that, under some conditions, W(x0 ,y0 ) belongs to the sublattice
obtained by removing the ¬nal vector in a L3 reduced basis. As a conse-
quence, the Gram-Schmidt vector corresponding to this ¬nal basis element is
S
orthogonal to W(x0 ,y0 ) ; thus, it encodes a bivariate polynomial h(x, y) that
vanishes at (x0 , y0 ). Since f is irreducible, it su¬ces to prove that h is not a
multiple of f in order to make sure that the system of equation f (x, y) = 0,
h(x, y) = 0 has a ¬nite number of solution over the complex ¬eld C and thus
to guarantee that (x0 , y0 ) can be recovered from the knowledge of f and h.
In [Cop96a], Coppersmith studied the case of polynomials of degree d in
each variable. In that case, (x0 , y0 ) can be recovered as long as Bx By <
M (f )2/(3d) . He also considered the case of bivariate polynomials of total
degree d. In this other case, the corresponding bound is Bx By < M (f )1/d .
The method can be generalized to many di¬erent shapes of polynomials, for
a survey, refer to [BM05].
In [Cor04] and [Cor07], Coron proposed a variation of Coppersmith™s algo-
rithm for bivariate polynomials using a modular approach similar to Howgrave-
Graham™s method.

13.2.2.1 Coppersmith™s algorithm with more variables
Coppersmith™s second algorithm can be extended to polynomials with more
variables. It su¬ces to choose an appropriate set of monomials S. With this
adaptation, we easily obtain a second polynomial h from the initial polynomial
f . However, using the results of Chapter 11, we know that with more than
two unknowns, two polynomials do not su¬ce to determine a zero-dimensional
ideal. So, the key question in this context is to obtain extra polynomials with
the same root. A simple heuristic method consists of taking several vectors in
Coppersmith™s reduced lattice instead of one and to construct a polynomial
from each of these vectors. The same heuristic idea also works with modular
polynomials with more than a single variable. The problem with this method
is that it does not guarantee algebraic independence of polynomials. However,
many cryptographic attacks, such as the one presented in Section 13.2.4 are
based on this heuristic method and work extremely well in practice.




© 2009 by Taylor and Francis Group, LLC
Lattice-based cryptanalysis 413

In some cases, it is possible to replace this heuristic method by a di¬erent
approach which mixes lattice reduction and Gr¨bner basis techniques [BJ07].
o


13.2.3 Extension to rational roots
A natural question concerning Coppersmith™s algorithm is to ask whether
it can also discover “small” rational roots. Of course, we need to de¬ne the
meaning of the word “small” in this context. The easiest is to de¬ne the size
of a fraction p/q in irreducible form as max(|p|, |q|). With this de¬nition of
size, ¬nding a small rational root of a polynomial f (x1 , . . . , xk ) is equivalent
to ¬nding a small integer root of F (X1 , Y1 , X2 , Y2 , . . . , Xk , Yk ), where F is
derived from f by independently homogenizing each of the k variables in f .
The algorithms of Coppersmith can then easily be adapted. We now detail
the case of Coppersmith™s ¬rst algorithm, using Howgrave-Graham™s method,
to show how this a¬ects the bound on the size of the root. Let f be a
univariate polynomial of degree d, with a rational root r = x0 /y0 modulo
N satisfying |x0 | < B and |y0 | < B. After homogenization, we obtain an
homogeneous polynomial in two variables, x and y, namely y d f (x/y). Given
a ¬xed degree bound D, we can de¬ne the family of polynomials Fi,j,k (x, y) =
y D’i xi f (x/y)j N k . Each polynomial in the family is homogeneous of degree
D in x and y. Then, we construct a lattice as in Section 13.2.1.1 but instead
of using the encoding of Equation (13.13) we instead use:

VF = (F (0) , F (1) , F (2) , · · · , F (D) ). (13.24)

The only di¬erence with Equation (13.13) is that we omit the factor B used to
balance the size of di¬erent power of x when searching integer roots. Indeed,
with a homogeneous polynomial and the same bound on x and y, this is no
longer needed.
With this change, the determinant of the lattice adapted from Howgrave-
Graham™s is N (D+1)t/2 . We can guarantee that the shortest vector in the
adapted lattice corresponds to a polynomial with the exact rational root r
if the sum of the absolute values of its coe¬cients are smaller than √ t /B D .
N
3
Thanks to the L bound, the sum of coe¬cients can be bounded by D + 1 ·

2D/4 · N t/2 . Ignoring the factor D + 1, we ¬nd that the largest value of B
we can obtain satis¬es: √
( 2 · B)D ≈ N t/2 .
4
(13.25)
Asymptotically, we can achieve:

N 1/d / 2.
B≈

In other words, in this case, the bound on the numerator and denominator x0
and y0 of the rational root is the square root of the original bound for integer
roots.




© 2009 by Taylor and Francis Group, LLC
414 Algorithmic Cryptanalysis

13.2.4 Security of RSA with small decryption exponent
One typical application of Coppersmith™s method in cryptography is the
Boneh-Durfee attack for recovering the secret key of an RSA instance, when
the decryption exponent is small. Let N = pq be an RSA modulus and
φ(N ) = (p ’ 1) · (q ’ 1). We know that the encryption exponent e and the
decryption exponent d are related by the following equation:

ed = 1 + kφ(N ). (13.26)

In the sequel, we assume that d is normalized in the interval [’φ(N )/2, φ(N )/2)]
and we say that d is ±-small when |d| ¤ φ(N )± . We also assume that e is
in the interval [0, φ(N )]. Clearly, in this setting, if d is ±-small then so is k.
Moreover, since φ(N ) = N ’ (p + q) + 1, it is possible to write φ(N ) = N ’ z,

with a value of z below a small multiple of N . Thus, Equation (13.26) can
be rewritten as:
ed ’ kN ’ kz ’ 1 = 0. (13.27)
In this equation, the term kz is smaller than the terms ed and kN . This
remark was used by Wiener in [Wie90]. It means that the equation can be
rewritten as e/N ≈ k/d. As a consequence, if d and k are small enough, the
fraction k/d naturally arises as an approximation of e/N using the techniques
presented in Section 2.2.2. Using a continued fraction algorithms, Wiener
showed in [Wie90] that this allows recovery of the decryption exponent d
under the condition d < N 1/4 .
In [BD99], in order to increase the bound to N ± with ± > 1/4, Boneh and
Durfee rewrite Equation (13.27) as a bivariate modular equation kN +kz+1 =
0 (mod e). In this equation, we search a solution with z of the order of N 1/2
and k of the order of N ± . Using the heuristic extension of Coppersmith
univariate modular algorithm to the bivariate modular case adapted to the
shape of this polynomial, they ¬rst obtain a new bound ± ≈ 0.285. With a
speci¬c improvement, involving rectangular matrices, they derive an improved
bound ± ≈ 0.292.




© 2009 by Taylor and Francis Group, LLC
Lattice-based cryptanalysis 415



Exercises
1. Consider the ¬‚oating point number:

x = ’8.44311610583794550393138517.

Show that x is a close approximation of a real root of a polynomial of
degree 3, with coe¬cient bounded by 20 (in absolute value).
2h . Let p be a large prime such that the polynomial f1 (x) = x3 + 2 has a
root X0 modulo p. Find a polynomial f2 (X) of degree 2 with coe¬cients
of the order of p1/3 and such that f2 (X0 ) = 0 (mod N ). What can you
say about the resultant of f1 and f2 .
3h . Generalize the above method for a polynomial f1 of degree d with small
coe¬cients.
4h . Show that the polynomials f1 and f2 from the two previous exercises
can serve as a basis for a number ¬eld sieve computation modulo p (see
Chapter 15). Compare with the bound given in Section 15.4.3.
5. Assume that a positive integer x has been encrypted under 3 di¬erent
RSA keys, N1 , N2 and N3 (x is smaller than these three values to allow
decryption), under the public exponent 3. Show that x can be recovered
from the three encrypted values c1 , c2 and c3 .
√ √
6h . Consider an RSA number N = pq, with N /2 ¤ p ¤ N . Assume
that a fraction of the high order bits of p are known. In that case, we
can write p = p0 + x.

• Give an upper bound on x.
• Show that the high order bits of q are also known.
• When can Coppersmith™s method be used to solve N = (p0 + x) ·
(q0 + y)?

7. Consider Equation (13.26). Check that by using the methods for ap-
proximating fractions given in Chapter 2, it is possible to recover the
RSA secret key as long as it remains below N 1/4 .
8. Consider a variation of Equation (13.26), namely:

ed = r + kφ(N ).

Assuming that d and r are both small, under which condition can these
numbers be recovered?




© 2009 by Taylor and Francis Group, LLC
Chapter 14
Elliptic curves and pairings


Elliptic curves are an essential tool in today™s cryptography. They are often
used to construct cryptosystems but there are also some cryptanalytic appli-
cations where the use of elliptic curves is necessary. In this chapter, we give
a self-contained introduction to elliptic curves, together with a description of
the Weil pairing. This pairing was initially introduced in cryptography as a
cryptanalytic tool to attack the discrete logarithm problem on some special
elliptic curves. It is interesting to note that the Weil pairing1 has now become
an essential tool for constructing new cryptosystems.
The constructions and proofs given in this chapter are often ad-hoc short-
cuts which hide deeper and nicer theory. In particular, we only consider
elliptic curves over ¬nite ¬elds of characteristic p ≥ 5. In order to learn more
about elliptic curves and their cryptographic applications, interested readers
should refer to more speci¬c textbooks such as [CF05, JN08, Sil86].




14.1 Introduction to elliptic curves
Over a ¬nite ¬eld Fq = Fpn , with p ≥ 5, an elliptic curve is described by a
Weierstrass equation:
y 2 = x3 + ax + b, (14.1)

where a and b are elements of Fq . For this equation, it is essential to be able
to de¬ne the tangent line to the curve at every point on the curve. If it is not
the case, we say that the curve is singular and not really an elliptic curve. The
tangent line at a point P of coordinates (xP , yP ) is given by the equation:

2yP (y ’ yP ) = (3x2 + a)(x ’ xP ). (14.2)
P


It is well de¬ned unless 2yP = 3x2 + a = 0. Since we also have yP =
2
P
x3 + axP + b, the tangent is well de¬ned unless both 3x2 + a = 0 and
P P



1 Together with a few cousins which can be computed faster, such as the Tate, Ate or Eta
pairings.



417
© 2009 by Taylor and Francis Group, LLC
418 Algorithmic Cryptanalysis

x3 + axP + b = 0. Put together, these two conditions imply:
P

(6ax2 ’ 9bxP + 4a2 ) · (3x2 + a) + (’18axP + 27b) · (x3 + axP + b) = 0. (14.3)
P P P

The reader can easily check that the above quantity is equal to ∆(a, b) =
4a3 + 27b3 , it is called the discriminant of the curve. The above discussion
shows that the curve is non-singular (or smooth) if and only if ∆(a, b) = 0.
Given an elliptic curve E in Weierstrass equation, we can clearly de¬ne the
set of points on this curve:

E(Fq ) = P = (xP , yP ) | (xP , yP ) ∈ F2 , yP = x3 + axP + b
2
{O}. (14.4)
q P

The additional point O is called the point at in¬nity on the elliptic curve.
Similarly, for any extension of the ¬nite ¬eld, we can de¬ne E(Fqe ), by taking
points with coordinates in the extension ¬eld.


14.1.1 The group structure of elliptic curves
The fundamental property of elliptic curves is that we can add a group
structure to these sets of points. This group structure is denoted additively
and the point at in¬nity is the zero element in the group. This group structure
can be introduced in several ways. Here, we give an algebraic construction in
order to de¬ne other mathematical objects that are needed for the introduc-
tion of the Weil pairing.

14.1.1.1 Divisors
The ¬rst step of the construction is to de¬ne the divisor group of the elliptic
curve. This divisor group Div is the group of maps from the curve to the
set of integers Z which are equal to zero except on a ¬nite2 set of points.
Clearly, if we de¬ne the sum of two maps D1 and D2 as the map D1 + D2
whose value at a point P is D1 (P ) + D2 (P ), we obtain an additive group.
The zero element is the zero mapping and the opposite of a map D is ’D,
with value ’D(P ) at P . Furthermore, this group is abelian, since addition of
integers is commutative. To represent these maps in the divisor group, it is
traditional to write them as formal sums D(P ) (P ). For example, the map
D with value 3 at P , ’3 at O and equal to zero elsewhere is represented as
3(P ) ’ 3(O). From now on, an element from the divisor group will simply be
called a divisor.
Given any divisor D, we de¬ne its degree as the (¬nite) sum of the values of
D at all points. For example, deg(2(P ) + 2(Q) ’ 3(O)) = 1. Since deg(D1 +
D2 ) = deg(D1 ) + deg(D2 ), deg is a group morphism from the divisor group
Div to Z. As a consequence, its kernel is a subgroup, called the subgroup of
degree 0 divisors and denoted by Div0 .

2 Of course, since E(Fq ) is already a ¬nite set, this restriction is irrelevant in our case.




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 419

14.1.1.2 Functions
The second step of the construction is to de¬ne functions on the elliptic
curve. We start from an arbitrary polynomial F (x, y). Clearly, for any point
P = (xP , yP ) other than O on the elliptic curve E(Fq ), we can de¬ne F (P ) =
F (xP , yP ). Note that F (P ) is an element of Fq . If F (P ) = 0, we say that P is
a zero of F . Unless F is multiple of y 2 ’x3 ’ax’b, the set of zeros of F is ¬nite.
In fact, adding any multiple of y 2 ’ x3 ’ ax ’ b to a polynomial F preserves
the values F (P ) and the set of zeros. As a consequence, if we so wish, we can
replace y 2 by x3 + ax + b in F and write F (x, y) as F0 (x) + yF1 (x). When P
is a zero of F , we can de¬ne its order or multiplicity denoted by ordP (F ). It
is the largest integer o such that some multiple F H of F , with H(P ) = 0 can
be written as a product (modulo y 2 ’ x3 ’ ax ’ b) of o polynomials, each with
value 0 at P . When P is not a zero of F we say that ordP (F ) = 0. With this
de¬nition, we have the nice property that P is a zero of a product GH if and
only if it is a zero of either G or H, in addition:

ordP (GH) = ordP (G) + ordP (H). (14.5)

To make this notion of order of a function at P more precise, let us analyze
in detail the zeros of F (x, y) = F0 (x) + yF1 (x). Let P = (xP , yP ) be a zero
of F . If yP = 0, it is always possible to factor y out of F (after potentially
multiplying by a polynomial H(x, y) with H(P ) = 0). If F0 (x) = 0 this is
clear. Otherwise, since xP is a root of x3 + ax + b, x ’ xP divides x3 + ax + b,
e.g., there exists a polynomial H(x) such that x3 + ax + b = H(x)(x ’ xP ).
Moreover, xP is a root of F0 (x) and (x’xP ) divides F0 (x). As a consequence,
x3 + ax + b divides H(x)F0 (x). Thus, replacing x3 + ax + b by y 2 we can factor
y out of H(x)F (x, y).
Similarly, if yP = 0, it is always possible to factor x ’ xP out of F after
potential multiplication by H. First, remark that x ’ xP divides either both
F0 (x) and F1 (x) or none of them. If x ’ xP divides both, the conclusion
follows. If x ’ xP divides none, then letting H(x, y) = F0 (x) ’ yF1 (x), we
see that H(P ) = 0. Moreover, H(x, y) · F (x, y) = F0 (x)2 ’ y 2 F1 (x)2 can be
written as a polynomial in the single unknown x by replacing y 2 by x3 +ax+b.
Since xP is a root of this polynomial, we can factor x ’ xP .
The two polynomials y or x ’ xP that occur in the above discussion are
called uniformizers at P . With this notion in mind, the order of F at P can
be equivalently de¬ned as the maximal power of the uniformizer at P that
can be factored out of F . Using uniformizers, we can more easily analyze the
zeros of F (x, y) = F0 (x) + yF1 (x) and their orders. When F1 (x) = 0, this
reduces to ¬nding the points P such that F0 (xP ) = 0 and their multiplicity.
Clearly, we need to factor F0 as a univariate polynomial. If xP is a root of
F0 with multiplicity o, two cases arise. In the ¬rst case, x3 + axP + b = 0
P
and we ¬nd two zeros of F : P = (xP , yP ) and P = (xP , ’yP ), each of these
two zeros has order o. Indeed, in that case x ’ xP is a uniformizer both at
P and at P . In the second case, x3 + axP + b = 0 and we ¬nd a single zero
P




© 2009 by Taylor and Francis Group, LLC
420 Algorithmic Cryptanalysis

P = (xP , 0), with order 2o. To understand why the order is doubled, let us
again write x3 + ax + b = H(x)(x ’ xP ). Thus, modulo the curve equation,
y 2o divides H(x)o F0 (x). Since y is the uniformizer at P in this case, the
conclusion follows.
Continuing the analysis, we now turn to the case F0 (x) = 0 and are left
with yF1 (x). Clearly, we already know how to ¬nd the zeros of F1 (x) and
simply need to look at the zeros of y. In fact, y has three zeros, one for each
root of x3 + ax + b. Note that, since the curve has a non-zero discriminant,
the three roots are distinct. Moreover, since y is a uniformizer at these three
points, the order of y at each point is 1.
Finally, let us look at F (x, y) = F0 (x) + yF1 (x) when neither F0 nor F1
is zero. Factoring out the greatest common divisor of F0 and F1 , we see
that it su¬ces to deal with the case where F0 and F1 are coprime. Assume
that P = (xP , yP ) is a root of F . If yP = 0, then ordP (F ) = 1 indeed we
know that P is a root of order at least 2 of F0 . Thus, if we had ordP (F ) >
1, we could write yF1 (x) = F0 (x) ’ F (x, y) with F1 (P ) = 0 and conclude
that ordP (y) > 1, this would contradict the above analysis which says that
ordP (y) = 1. Finally, if P is a root of F with yP = 0, we see that neither
F0 (xP ) nor F1 (xP ) can be 0, otherwise both would be and F0 and F1 would
not be coprime. Thus, multiplying F by H(x, y) = F0 (x) ’ yF1 (x), we ¬nd
that the order of P at F is equal to the multiplicity of x ’ xP in the univariate
polynomial F0 (x)2 ’ (x3 + ax + b)F1 (x)2 .
When looking at the zeros of a polynomial F , it is important to remember
that the zeros are not necessarily points with coordinates in Fq . In many cases,
the zeros have their coordinates in some extension ¬eld. If we construct all
the zeros of a non-zero polynomial F (x, y) = F0 (x) + yF1 (x) including zeros
over extension ¬elds, it is possible to prove that the sum of their orders is
max(2 deg(F0 ), 3 + 2 deg(F1 )), using the usual convention that deg(0) = ’∞.
It is useful to de¬ne the order of F at the point at in¬nity O as ordO (F ) =
’ max(2 deg(F0 ), 3 + 2 deg(F1 )). With this convention, we now de¬ne the
divisor of a non-zero polynomial F as:

div(F ) = ordP (F )(P ), (14.6)
P

where the sum includes points over extension ¬elds and the point at in¬nity.
We see that div(F ) is a divisor of degree 0.
The above de¬nitions can easily be extended to quotients F/G letting:

ordP (F/G) = ordP (F ) ’ ordP (G) and
div(F/G) = div(F ) ’ div(G). (14.7)

When ordP (F/G) > 0 we say that P is a zero of F/G and when ordP (F/G) <
0 we say that P is a pole of F/G. Any fraction F/G is called a function on the
elliptic curve. Note that functions are determined modulo the curve equation
y 2 ’ x3 ’ ax ’ b and can thus be represented by several possible fractions. Any




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 421

divisor which can be written as the divisor of a function is called a principal
divisor.

14.1.1.3 Principal divisors and the group structure
Looking at the set of principal divisors, we may easily see that it is a sub-
group of the group Div0 of degree 0 divisors. Indeed, each principal divisor
has degree 0; the empty3 divisor is principal and equal to div(1) since the
constant function 1 has neither zeros nor poles; the opposite of a principal
divisor is principal since div(F/G) = ’div(G/F ); and the sum of two prin-
cipal divisors is principal, div(F1 /G1 · F2 /G2 ) = div(F1 /G1 ) + div(F2 /G2 ).
It is thus possible to form a quotient group by considering degree 0 divisors
modulo principal divisors. It is usual to say that two divisors which di¬er by
a principal divisor are linearly equivalent. We are now going to see that
this quotient group and this notion of linear equivalence can be used to give
a group structure to the elliptic curve itself.
The key ingredient is to show that any degree zero divisor D can be writ-
ten as D = (P ) ’ (O) + div(f ) for some point P on the elliptic curve and
some function f . In fact, this can be done in a completely e¬ective and
computationally e¬cient manner. Clearly, since any divisor is a ¬nite sum
of points, it su¬ces to show how to compute the sum and the di¬erence of
D1 = (P1 ) ’ (O) and D2 = (P2 ) ’ (O) in the above form. To compute the
sum, we write P1 = (xP1 , yP1 ), P2 = (xP2 , yP2 ) and we consider the following
cases:
1. If P1 = O, then D1 is the empty divisor and D1 + D2 = D2 already is
of the correct form. If P2 = O this remark also applies.
2. If xP1 = xP2 and yP1 = ’yP2 then:

div(x ’ xP1 ) = (P1 ) + (P2 ) ’ 2(O) = D1 + D2 , (14.8)

thus D1 + D2 is linearly equivalent to the empty divisor (O) ’ (O). Note
that this also covers the special case where P1 = P2 and yP1 = 0.
3. If P1 = P2 and yP1 = 0 then let L(x, y) be the equation of the tangent
to the elliptic curve at P1 . More precisely:

L(x, y) = (y ’ yP1 ) ’ »(x ’ xP1 ),
3x2 +a
P1
with » = 2yP1 .

From our general analysis, we know that the sum of the orders of the
zeros of L(x, y) is 3 and thus that:

div(L(x, y)) = 2(P1 ) + (P3 ) ’ 3(O), (14.9)

3 Remember that the empty divisor is the group neutral element.




© 2009 by Taylor and Francis Group, LLC
422 Algorithmic Cryptanalysis

for some point P3 . Moreover, the coordinates of P3 are in the same ¬eld
as the coordinates of P1 . We can explicitly write:

xP3 = »2 ’ xP1 ’ xP2 and (14.10)
yP3 = yP1 + »(xP3 ’ xP1 ). (14.11)

This shows that D1 + D2 is linearly equivalent to (O) ’ (P3 ). However,
we are not done because this divisor does not have the expected form.
We now write:

div(x ’ xP3 ) = (P3 ) + (P4 ) ’ 2(O), (14.12)

with P4 = (xP3 , ’yP3 ). As a consequence,

L(x, y)
D1 + D2 = (P4 ) ’ (O) + div . (14.13)
x ’ xP3

4. If xP1 = xP2 , let L(x, y) be the equation of the line passing though P1
and P2 . More precisely:

L(x, y) = (y ’ yP1 ) ’ »(x ’ xP1 ),
yP2 ’yP1
with » = . The very same reasoning as above apply and once
xP2 ’xP1
again:
L(x, y)
D1 + D2 = (P4 ) ’ (O) + div ,
x ’ xP3
where P3 is the third point on the line of equation L(x, y) with coordi-
nates as in Equations 14.10 and 14.11, and where P4 is its symmetric
with coordinates (xP3 , ’yP3 ).

To compute di¬erences, it su¬ces to use the above formula that transform
(O) ’ (P3 ) into a linearly equivalent divisor (P4 ) ’ (O) repeatedly. As a
consequence, iterating these formulas we are able to reduce any divisor D to
a linearly equivalent divisor (P ) ’ (O). In fact, we even recover an expression
for a function f such that:

D = (P ) ’ (O) + div(f ). (14.14)

In order to turn the elliptic curve itself into a group, it now su¬ces to interpret
any point P as the divisor (P ) ’ (O) and vice versa. To make sure that this
interpretation is unequivocal, we need to check that two di¬erent points P1
and P2 yield two di¬erent group elements. Thus, we need to verify that
D = (P1 ) ’ (P2 ) is not a principal divisor when P1 = P2 ; see Exercise 3
or refer to [Was03, Lemma 11.3]. Using this interpretation, we obtain the
following properties for the group structure:




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 423

• The point at in¬nity O is the neutral element in the group. Indeed,
(O) ’ (O) is the empty divisor.
• The opposite of a point P = (xP , yP ) is its symmetric ’P = (xP , ’yP ).
Indeed, (P ) ’ (O) + (’P ) ’ (O) = div(x ’ xP ) is principal.
• The sum of P1 and P2 is the symmetric of the third point of intersection
P3 of the line through P1 and P2 and the elliptic curve. When P1 = P2 ,
we take the tangent at P1 as the line through P1 and P2 .


14.1.2 Double and add method on elliptic curves
With the above addition law, it is possible to compute xP for any point
P on the elliptic curve E and any integer x. When x is zero, the result is
the point at in¬nity O. When x < 0, we replace the computation of xP
by the computation of (’x)P where P is the symmetric, i.e., opposite, of
P . By de¬nition, xP with x > 0 is obtained by adding together x copies of
the point P . However, for large values of x this is not e¬cient. To speed
up the computation of xP , it su¬ces to generalize the square and multiply
algorithms used for exponentiation of modular integers to the case of elliptic
curve. Adapted to this speci¬c case, the basic idea is simply to remark that
the sequence P , 2P , 4P , . . . 2t P can be e¬ciently computed by writing each
term as the sum of the previous term in the sequence with itself, i.e., as the
double of the previous term. Moreover, from the binary decomposition of x,
we can rewrite xP as the sum of the terms 2i P such that 2i appear in the
decomposition of x. Thus, xP can be computed using log2 (x) doublings and
at most log2 (x) additions. We leave the adaptation of Algorithms 2.9 and 2.10
as an exercise to the reader.


14.1.3 Number of points on elliptic curves
In order to use an elliptic curve over a ¬nite ¬eld as the basis for a discrete
logarithm based cryptographic problem, it is useful to know the cardinality
of this elliptic curve. This is not mandatory and there are systems that work
with groups of unknown cardinality. However, the most frequent cryptosys-
tems over elliptic curves require knowledge of the cardinality. In addition, it
is useful to describe the group structure, i.e., to ¬nd an isomorphic group,
written as a product of cyclic groups of the form Z/rZ. With elliptic curves
over a ¬nite ¬eld Fp , a lot of information is known about the cardinality and
the group structure. In particular, we have the following theorem:


THEOREM 14.1
Let E be an elliptic curve over Fp and let CE be the number of points of E
with both coordinates in Fp , including the point at in¬nity O. Then we have:
√ √
p + 1 ’ 2 p ¤ CE ¤ p + 1 + 2 p. (14.15)




© 2009 by Taylor and Francis Group, LLC
424 Algorithmic Cryptanalysis

Moreover, there exist two positive integers r1 and r2 such that:

1. r2 divides r1 .

2. The number of points CE is equal to r1 r2 .

3. The group structure of the elliptic curve E is Z/r1 Z — Z/r2 Z.


PROOF See [Sil86, Chapter III], Corollary 6.4 and [Sil86, Chapter V],
Theorem 1.1.

We do not develop point counting algorithms here and refer the reader
to [CF05, Part IV]. For the Schoof-Elkies-Atkin point counting method, the
noisy Chinese remainder reconstruction algorithm discussed in Section 8.4.1
can be used to speed up the ¬nal phase.




14.2 The Weil pairing
14.2.1 Weil™s reciprocity law
Since we have already de¬ned divisors and functions, we are almost ready to
go forward and de¬ne pairings. Before that, we need to learn how to evaluate
a function on a divisor. Let f = F/G be a function on an elliptic curve E and
let D be an arbitrary divisor. We de¬ne the support of D to be the ¬nite set of
points of E that appear with non-zero coe¬cients in D. When the support D
contains none of the zeros or poles of f , writing once again D = D(P )(P )
we can de¬ne:
f (P )D(P ) .
f (D) = (14.16)

Note that we have already de¬ned f (P ) as F (P )/G(P ) for all points P not
equal to the point at in¬nity (O). If the support of D does not contain O,
nor any zero or pole of f , f (D) is a well-de¬ned and non-zero value. We shall
determine, later on, the precise ¬nite ¬eld where this value is de¬ned. For
now, let us simply say that it clearly belongs to some extension of Fp . To
de¬ne f (D) in all cases, we need to de¬ne f (O) when O is neither a zero nor
a pole of f . In fact, this can be done by looking only at high order terms.
More precisely, if we de¬ne the degree of a monomial y dy xdx in the function
¬eld as 3dy + 2dx and the degree of a polynomial F as the maximum of the
degrees of the monomials in F , looking back at Section 14.1.1.2 we see that
the order of f at O is then equal to the degree of F . Thus, saying that O is
neither a zero nor a pole of f means that the degrees of F and G are equal.
In that case, we de¬ne f (O) as the quotient of the coe¬cients in front of the
highest degree monomials in F and G.




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 425

With this de¬nition of f (D), we easily remark that when D is of degree
0, f (D) is equal to (»f )(D) for any constant ». This is extremely interest-
ing because if we only consider f up to a multiplicative constant, we are in
fact looking at an object which is determined by the divisor div(f ). This
connection is emphasized by the following theorem:


THEOREM 14.2 Weil™s reciprocity
Let f and g be two functions in the function ¬eld of an elliptic curve E. If
div(f ) and div(g) have disjoint support, or equivalently if the zeros and poles
of f and g do not intersect, then:

f (div(g)) = g(div(f )). (14.17)

We give here an elementary proof using resultants; for a shorter proof, the
reader may refer to [BSS05, pages 212“213].


PROOF Since f and g need only be de¬ned up to multiplicative constants,
we may assume the polynomials at the numerators and denominators of f
and g are normalized, i.e., that the coe¬cients in front of the highest degree
monomials are everywhere 1s.
Under this hypothesis, all evaluations at O yield 1. As a consequence,
we can consider a simpli¬ed variation of Weil™s reciprocity that ignores the
point at in¬nity. For this variation, let us take two polynomials on the curve
F (x, y) = F0 (x) + yF1 (x) and G(x, y) = G0 (x) + yG1 (x), with no common
zeros. We know that div(F ) can be written as DF ’ ordO (F )(O), where
DF describes the zeros of F . Similarly, div(G) can be written as DG ’
ordO (G)(O). We now claim, that:

F (DG ) = ±G(DF ). (14.18)

Moreover, the ± sign in the above equation is uniquely determined by the
degrees of F and G.
Weil™s reciprocity law easily follows from Equation (14.18). Indeed, thanks
to the normalization we chose, if we write f = F/H and g = G/K then we
see that:
F (DG )H(DG )
f (div(g)) = = g(div(f )), (14.19)
F (DK )H(DK )
since all evaluations at O are equal to 1. The only tricky part is to verify that
the signs really cancel out. We leave the veri¬cation to the reader. Anyway,
since we only intend to de¬ne the Weil pairing on -torsion points where is
an odd prime, this veri¬cation is not even required here.
In order to prove Equation (14.18), we need to consider three elementary
possibilities for F and G. For F , the options are F (x, y) = F0 (x), F (x, y) = y
and F (x, y) = F0 (x) + yF1 (x) with F0 and F1 coprime. Indeed, any other




© 2009 by Taylor and Francis Group, LLC
426 Algorithmic Cryptanalysis

case can be obtained by multiplication of these elementary cases and of course
Equation (14.18) is preserved by multiplication, since clearly for F = F (1) F (2) ,
if Weil™s reciprocity is satis¬ed by (F (1) , G) and (F (2) , G) we have:

F (DG ) = F (1) (DG ) · F (2) (DG ) = G(DF (1) )G(DF (2) ) = G(DF ), (14.20)

since the divisor of a product is the sum of the divisors of each term.
Combining all possibilities for F and G, there is a total of 9 cases to consider.
Taking into account the symmetry betwen F and G, this is reduced to 6 cases.
In addition, since F and G have no common zero, we can ignore4 the case
F (x, y) = G(x, y) = y. As a consequence, there are ¬ve remaining cases to
consider. It is important to remember that all highest degree coe¬cients are
1s. This allows us to replace some expressions by resultants as de¬ned in
Chapter 11. This makes these expressions easier to manipulate and greatly
simpli¬es the proof. The ¬ve cases are:

1. When F (x, y) = F0 (x) and G(x, y) = G0 (x), for each root ± of F0 in
the algebraic closure of the ¬eld of de¬nition of E, there are either two
corresponding points (±, y± ) and (±, ’y± ) or a point (±, 0). In the ¬rst
case, the order at each point is equal to the multiplicity of ± in F0 . In
the second case, the order is equal to twice the multiplicity. Thus:

G0 (±)2 = Res(F0 , G2 ) = Res(F0 , G0 )2 .
G(DF ) = 0
± root of F0
(with multiplicity)

Clearly, by symmetry, we also have:

F (DG ) = Res(G0 , F0 )2 .

Moreover, since Res(F0 , G0 ) = ±Res(G0 , F0 ), both expressions are
equal.

2. When F (x, y) = F0 (x) and G(x, y) = y, once again we can look at the
roots ± of F0 . If there is a corresponding point of the form (±, 0), then
F and G have this point as a common zero and DF (G) = DG (F ) = 0.
Otherwise, we see that:
2
’y±
G(DF ) =
± root of F0
(with multiplicity)
±3 + a± + b = ’Res(F0 , x3 + ax + b)
=’
±


4 Anyway, it is clear in that case that DF (G) = DG (F ) = 0.




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 427

Letting (β1 , 0), (β2 , 0) and (β3 , 0) denote the three distinct points with
y coordinate 0, i.e., letting β1 , β2 and β3 be the roots of x3 + ax + b, we
also have:

F (DG ) = F0 (β1 )F0 (β2 )F0 (β3 ) = Res(x3 + ax + b, F0 ).

As a consequence, we conclude that DF (G) = ±DG (F ).


3. When F (x, y) = F0 (x) and G(x, y) = G0 (x) + yG1 (x), with G0 and G1
coprime, once more, we start by looking at the roots ± of F0 . If a point
of the form (±, ±y± ) is a zero of G, then F and G have this point as a
common zero and DF (G) = DG (F ) = 0. Otherwise, we ¬rst compute
G(DF ) as:


(G0 (±) + y± G1 (±))(G0 (±) ’ y± G1 (±))
G(DF ) =
± root of F0
(with multiplicity)
= Res(F0 , G),

where G denotes the polynomial G(x) = G0 (x)2 ’ (x3 + ax + b)G1 (x)2 .
Indeed, we can group the zeros of F in pairs (±, y± ) and (±, ’y± ). Note
that this also holds when y± = 0, since in that case the order of the
point is twice the multiplicity of ± in F0 .

To evaluate the second term F (DG ), we remark that each zero (β, yβ )
of G with order e corresponds to a root β of G of multiplicity e. Also
note that from β, we can obtain yβ as ’G0 (β)/G1 (β). Since F does not
depend on y, we do not need this expression of yβ for this case, but it
will be useful for the next cases. Thanks to this remark, we can write:


F (DG ) = F0 (β) = Res(G, F0 ).
β root of G
(with multiplicity)



Clearly, the two expressions we obtain for G(DF ) and F (DG ) are equal,
up to sign. This concludes the third case.


4. When F (x, y) = y and G(x, y) = G0 (x) + yG1 (x), with G0 and G1
coprime, let us denote G(x) = G2 (x) ’ (x3 + ax + b)G2 (x) as above, we
0 1




© 2009 by Taylor and Francis Group, LLC
428 Algorithmic Cryptanalysis

¬nd:

’G0 (β) Res(G, ’G0 )
F (DG ) = yβ = =
G1 (β) Res(G, G1 )
β
β root of G
(with multiplicity)
Res(’(x3 + ax + b)G2 (x), ’G0 )
1
= 2 (x), G )
Res(G0 1
Res(’G2 (x), ’G0 )
1
3
= Res((x + ax + b), ’G0 ) · 2 (x), G )
Res(G0 1
= ±Res((x3 + ax + b), G0 ).


For the other expression, recalling that the zeros of y correspond to the
roots of x3 + ax + b, we write:

G(DF ) = G0 (±)
± root of x3 + ax + b
= Res((x3 + ax + b), G0 ).

This concludes the fourth case.

5. Finally, we need to address the most complicated case where F (x, y) =
F0 (x) + yF1 (x) and G(x, y) = G0 (x) + yG1 (x), with F0 , F1 coprime and
G0 , G1 coprime. For this case, it is useful to de¬ne G as above, F in the
same way and to write the rational fraction F1 /G1 in irreducible form
as f1 /g1 . We then write:

G(DF ) = (G0 (±) + y± G1 (±))
(±, y± ) zero of F
(with order)
G0 (±) ’ F0 (±)G1 (±)/F1 (±)
=
(±,y± )

Res(F, ∆)
= .
Res(F, f1 )

where ∆ = f1 G0 ’ F0 g1 .

By symmetry:
Res(G, ’∆)
F (DG ) = .
Res(G, g1 )




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 429

We can now prove that:
Res(F, ∆) = ±Res(∆, F) = ±Res(∆, F0 (x)2 + (x3 + ax + b)F1 (x)2 )
2
f1
2 3 2
= ±Res(∆, F0 (x) + (x + ax + b)G1 (x) )
g1
2
Res(∆, f1 )
= ±Res(G, ∆) · .
Res(∆, g1 )

We also have:
Res(F, f1 ) = ±Res(f1 , F) = ±Res(f1 , F0 (x)2 + (x3 + ax + b)F1 (x)2 )
2
f1
2 3 2
= ±Res(f1 , F0 (x) + (x + ax + b)G1 (x) )
g1
2 2
Res(f1 , g1 F0 ) Res(f1 , ∆)
=± =± .
Res(f1 , g1 ) Res(f1 , g1 )

And by symmetry:
2
Res(g1 , ∆)
Res(G, g1 ) = ± .
Res(g1 , f1 )

Putting everything together concludes the ¬nal case.



14.2.2 The Weil pairing on -torsion points
Using Weil™s reciprocity, it is now possible to de¬ne the Weil pairing of two
-torsion points P and Q on an elliptic curve E. Remember that a point P is
said to be an -torsion point when P = O on the elliptic curve. In that case,
(P ) ’ (O) is a principal divisor and we can express it as div(fP ). More
generally, for any divisor DP which sums to P , DP is principal. To de¬ne
e (P, Q) the Weil pairing of P and Q, we choose two arbitrary divisors DP and
DQ with respective sums P and Q and with distinct supports. Then, we de¬ne
the two functions fP and fQ such that div(fP ) = DP and div(fQ ) = DQ .
Finally, we de¬ne:
fP (DQ )
e (P, Q) = . (14.21)
fQ (DP )

THEOREM 14.3
The Weil pairing is a well-de¬ned function of P and Q, i.e., it is independent
of the choice of DP and DQ . It satis¬es the following properties:
1. For all -torsion points P and Q, e (P, Q) is an -th root of unity, i.e.,
e (P, Q) = 1.




© 2009 by Taylor and Francis Group, LLC
430 Algorithmic Cryptanalysis

2. For all -torsion points P and Q: e (P, Q) = e (Q, P )’1 .
3. In particular, for all -torsion point P : e (P, P ) = 1.
4. For all -torsion points P, P and Q: e (P +P , Q) = e (P, Q)·e (P , Q).
5. For all -torsion points P, Q and Q : e (P, Q+Q ) = e (P, Q)·e (P, Q ).
6. For all -torsion points P, Q and all integers a, b: e (aP, bQ) = e (P, Q)ab .
7. The pairing e is non-degenerate, i.e., there exists -torsion points P
and Q, such that e (P, Q) = 1.


PROOF To show that e is well de¬ned, let us see that for two di¬erent
choices of divisor summing to P , say DP and DP we obtain the same value
for e (P, Q). Since, DP and DP both sum to P , their di¬erence is principal
and we can write DP = DP + div(h) for some function h. Thus:
fQ (DP ) = fQ (DP ) · fQ (div(h)).
If we let fP and fP be the functions corresponding to DP and DP , we see
that fP = h fP . Evaluating at DQ , we ¬nd:
fP (DQ ) = fP (DQ ) · h(DQ )
= fP (DQ ) · h( DQ )
= fP (DQ ) · h(div(fQ )).


Thanks to Weil™s reciprocity, we know that h(div(fQ )) = fQ (div(h)). Thus,
after dividing the numerator by the denominator, we ¬nd equality for our two
expressions of e (P, Q). Clearly, the same reasoning also applies for DQ and
Weil pairing does not depend on the chosen divisors, only on the points P
and Q. A frequently encountered choice is to take:
DP = (P ) ’ (O) and
DQ = (Q + X) ’ (X) for an arbitrary point X = P, ’Q. (14.22)
In order to verify that e (P, Q) is an -th root of unity, let us look at the
value of the numerator raised to the power :
fP (DQ ) = fP ( DQ ) = fP (div(fQ )).
Thanks to Weil™s reciprocity, we see that this is equal to the denominator
fQ (DP ) , as a consequence e (P, Q) = 1.
To check that e (P + P , Q) = e (P, Q)e (P , Q), we ¬rst remark that DP +
DP is a possible choice for the divisor DP +P . With this choice, we clearly
have:
fQ (DP +P ) = fQ (DP )fQ (DP ) and
fP +P = fP fP . (14.23)




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 431

Thus the property follows. The same argument also implies e (P, Q + Q ) =
e (P, Q)e (P, Q ).
The bilinearity e (aP, bQ) = e (P, Q)ab follows by induction for positive
values of a and b. For a = 0, it su¬ces to check that e (O, Q) = 1. Similarly,
for b = 0. For negative a and b, we ¬rst remark that e (’P, Q) = e (P, ’Q) =
e (PQ )’1 and conclude by induction.
For the proof of non-degeneracy, we refer the reader to [Sil86, Proposi-
tion 8.1].

In [Mil04], it is shown that by choosing normalized functions fP and fQ
with highest degree coe¬cients equal to one, such that div(fP ) = (P ) ’ (O)
and div(fQ ) = (Q)’ (O), then the computation of the Weil pairing e (P, Q)
can be simpli¬ed to fP (Q)/fQ (P ).

14.2.2.1 Miller™s algorithm for the Weil pairing
In [Mil04], Miller describes a very useful algorithm generally known as
Miller™s algorithm for computing pairing or more precisely to evaluate a func-
tion fP at a point Q. Note that using this algorithm is essential for con-
structive application of pairings. Trying to compute fP itself rather than
evaluating it on the ¬‚y is doomed because, even in factored form, storing this
function is very costly.
(i)
Miller™s algorithm considers intermediate functions, fP speci¬ed by:
(i)
div(fP ) = (i)(P ) ’ (iP ) ’ (i ’ 1)(P ).
(0)
Note that the divisor on the right-hand side is principal. Remark that div(fP )
(1) (0) (1)
and div(fP ) are both empty. Thus, we can choose fP = fP = 1. Moreover,
()
fP = fP .
(i+j) (i) (j)
We now remark that it is easy to compute fP from fP and fP . Indeed:
(i+j) (i) (j)
) = div(fP ) + div(fP ) + (iP ) + (jP ) ’ ((i + j)P ) ’ (O).
div(fP

Moreover, following Section 14.1.1.3, we know that there exists a linear poly-
nomial L(x, y) such that:

div(L(x, y)) = (iP ) + (jP ) + (’(i + j)P ) ’ 3(O).

Moreover, if x0 is the x coordinate of (i + j)P , we have:

div(x ’ x0 ) = ((i + j)P ) + (’(i + j)P ) ’ 2(O).

It follows that:
(i+j) (i) (j)
) = div(fP ) + div(fP ) + div(L(x, y)) ’ div(x ’ x0 ). (14.24)
div(fP




© 2009 by Taylor and Francis Group, LLC
432 Algorithmic Cryptanalysis

As a consequence, we can choose:
L(x, y)
(i+j) (i) (j)
= fP · fP ·
fP . (14.25)
x ’ x0
Miller™s method can be incorporated into any e¬cient algorithm for comput-
ing P , such as the double and add method, see Algorithm 14.1. To optimize
the e¬ciency of this algorithm, the reader should refer to [CF05].


Algorithm 14.1 Miller™s algorithm with double and add
Require: Input integer > 0, points P and Q of -torsion
Require: Finite ¬eld Fq
k’1
Write in binary n = i=0 i 2i
Let R ←’ P
Let y ←’ 1
for i from k ’ 1 down to 0 do
Let L be the tangent line at R
Let R ←’ 2R
Let y ←’ y 2 · L(Q)/(xQ ’ xR ) in Fq
if ni = 1 then
Let L be the line through P and R
Let R ←’ R + P
Let y ←’ y · L(Q)/(xQ ’ xR ) in Fq
end if
end for
Output y {Value of fP (Q)}




14.3 The elliptic curve factoring method
Another interesting use of elliptic curves in cryptography is the elliptic curve
factoring method (ECM) which can be used to detect small enough factors
of large integers. This method is closely related to Pollard™s p ’ 1 factoring
algorithm. Thus, for simplicity, we start by describing this method.


14.3.1 Pollard™s p ’ 1 factoring
Pollard™s p ’ 1 factoring algorithm can e¬ciently ¬nd factors of a special
form in composite numbers. Its name comes from the fact that a factor p can
be e¬ciently found with this method when p ’ 1 is a product of small enough




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 433

primes. Here, small enough means that all prime factors of p ’ 1 are smaller
than some bound B speci¬ed in advance. Alternatively, we say that p ’ 1 is
B-smooth. Given p and B, let us de¬ne:
log(p)
P (p, B) = q . (14.26)
log(q)


prime,
q q¤B

This product is constructed in a way that guarantees that p ’ 1 is B-smooth
if and only if p ’ 1 divides P (p, B).
As a consequence, when p ’ 1 is B-smooth, for any invertible element x
modulo p, we have xP (p,B) = 1 (mod p). Thus, if a composite N has a factor

<<

. 15
( 18)



>>