ńņš. 15 |

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 |