Thierry Mefenza
email: thierrymefenza@yahoo.fr

Damien Vergnaud
email: damien.vergnaud@lip6.fr

Inferring Sequences Produced by Elliptic Curve Generators using Coppersmith's Methods

Keywords: Pseudo-random generator, Elliptic curve linear congruential generator, Elliptic curve power generator, Coppersmith's methods, Elliptic curves

We analyze the security of two number-theoretic pseudo-random generators based on elliptic curves: the elliptic curve linear congruential generator and the elliptic curve power generator. We show that these recursive generators are insecure if sufficiently many bits are output at each iteration (improving notably the prior cryptanalysis of Gutierrez and Ibeas from 2007). We present several theoretical attacks based on Coppersmith's techniques for finding small roots on polynomial equations. Our results confirm that these generators are not appropriate for cryptographic purposes.

Introduction

In cryptography, a pseudo-random number generator is a polynomial-time deterministic algorithm which takes as input a short random seed and outputs a long sequence which is indistinguishable in polynomial time from a truly random sequence. Pseudo-random numbers have found numerous applications in the literature. For instance they are useful in cryptography for key generation, encryption and digital signature. Number-theoretic pseudorandom generators work by iterating an algebraic map F (public or private) over a residue ring Z N (where N is usually a prime number or an RSA modulus) on a secret random initial seed value s 0 ∈ Z N to compute the intermediate state values s i+1 = F (s i ) mod N for i ∈ N and outputting (some consecutive bits of) the state value s i at each iteration. The input s 0 of the generator (and possibly the description of F ) is called the seed and the output is called the pseudorandom sequence. The case where F is an affine function is known as the linear congruential generator. This generator is efficient and has good statistical properties. Unfortunately, it is cryptographically insecure: Boyar [START_REF] Boyar | Inferring sequences produced by a linear congruential generator missing low-order bits[END_REF] proved that -with a sufficiently long run of the pseudorandom sequence -one can recover the seed in time polynomial in the bit-size of N . It was suggested to use a non-linear algebraic map F in order to avoid these attacks. The provably secure classical power-generator from [START_REF] Blum | A simple unpredictable pseudo-random number generator[END_REF] uses the algebraic map is F : x -→ x e mod N for some integer e ∈ N and outputs asymptotically only at most O((log log N )/(log e)) bits per multiply modulo an RSA modulus N , and hence are too slow to be used in many practical applications. Even if one wants to use this generator with no proven security guarantees, it outputs at most O(log N/ log e) bits per multiply modulo N and for this reason, this generator is used only with a very small integer e (typically e ∈ {2, 3}).

In 1994, Hallgren [START_REF] Hallgren | Linear congruential generators over elliptic curves[END_REF] proposed a pseudo-random number generator based on a subgroup of points of an elliptic curve defined over a prime finite field. This generator is known as the Linear Congruential Generator on Elliptic Curves (EC-LCG). Let p be a prime number (with p 5) and let E be an elliptic curve defined over a prime finite field F p , that is a rational curve given by the following Weierstrass equation E : y 2 = x 3 + ax + b for some a, b ∈ F p with 4a 3 + 27b 2 = 0. It is well known that the set E(F p ) of F p -rational points (including the special point O at infinity) forms an Abelian group with an appropriate composition rule (denoted ⊕) where O is the neutral element. For a given point G ∈ E(F p ), the EC-LCG generates a sequence U n of points defined by the relation:

U n = U n-1 ⊕ G = [n]G ⊕ U 0 , n ∈ N
where U 0 ∈ E(F p ) is the initial value or seed. We refer to G as the composer of the EC-LCG. For a positive integer e > 1 and a point G ∈ E(F p ) of order with gcd(e, ) = 1, the Elliptic Curve Power Generator (EC-PG), introduced by Lange and Shparlinksi in [START_REF] Lange | Certain exponential sums and random walks on elliptic curves[END_REF], generates a sequence of points V n defined by the relation:

V n = [e]V n-1 = [e n ]G, n ∈ N
where V 0 ∈ E(F p ) is the initial value or seed.

The EC-LCG and the EC-PG provide a very attractive alternative to linear congruential generators and power generators and they have been extensively studied in the literature (see [GBS00, GL01, MS02, BD02, LS05, Shp05, HS02, IS09, Mer17] and the references therein). In cryptography, one may want to use the output of these generators as a keystream for encryption. One can notice that if two consecutive values U n , U n+1 of the EC-LCG generator are revealed, it is easy to find U 0 and G (see also [START_REF] Merai | Predicting the elliptic curve congruential generator[END_REF] for the EC-PG). In order to use the produced sequences for cryptography, one should therefore output only some bits (e.g. the most significant ones) of each coordinate of U n or V n , n ∈ N in the hope that this makes the resulting output sequence difficult to predict. As for the classical power generator [START_REF] Blum | A simple unpredictable pseudo-random number generator[END_REF][START_REF] Bauer | Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith's methods[END_REF], in cryptographic uses of the EC-PG, e is always assumed to be "small" (and does not grow with the security parameter). Indeed, the computation of V n from V n-1 requires Ω(log(e)) multiplications modulo p and the generator outputs at most O(log(p)) bits. The EC-PG is used only with a very small integer e (typically e ∈ {2, 3}) and it is therefore assumed to be known to the adversary (it this is not the case, the adversary can perform an exhaustive search on all possible e and this adds only a constant factor overhead to its computational complexity).

In this paper, we show that the EC-LCG and the EC-PG are insecure if sufficiently many bits are output at each stage. Therefore a secure use of these generators requires to output fewer bits at each iteration and the efficiency of the schemes is thus degraded. Our attacks used the well-known Coppersmith's methods for finding small roots on polynomial equations. These methods have been introduced in 1996 by Coppersmith for polynomial of one or two variables [START_REF] Coppersmith | Finding a small root of a univariate modular equation[END_REF][START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF] and have been generalized to many variables. These methods have been used to infer many pseudo-random generators and to cryptanalyze many schemes in cryptography (see [START_REF] Benhamouda | Easing coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness[END_REF][START_REF] Bauer | Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith's methods[END_REF] and the references therein). In this paper we notably used such techniques to improve the previous bounds known on the security of the EC-LCG in the literature. Our improvements are theoretical since in practice, the cost of Coppersmith's method in our case is prohibitive because of large dimension of the lattice. However, they confirm that these generators are not appropriate for cryptographic purposes.

Prior work. In the cryptography setting, the initial value U 0 and the constants G, a and b may be kept secret. Gutierrez and Ibeas [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF] consider two settings: the case where the composer G is known to the attacker and a, b are kept secret and the case where the composer G is unknown and a, b are kept secret. In the first case, they showed that the EC-LCG is insecure if a proportion of at most 1/6 of the least significant bits of two consecutive values of the sequence is hidden. When the composer is unknown, they showed heuristically that the EC-LCG is insecure if a proportion of at most 1/46 of the least significant bits of three consecutive values of the sequence is hidden. Their result is based on a lattice basis reduction attack, using a certain linearization technique. In some sense, their technique can be seen as a special case of the problem of finding small solutions of multivariate polynomial congruences. The Coppersmith's methods also tackle the problem of finding small solutions of multivariate polynomial congruences. Gutierrez and Ibeas due to the special structure of the polynomials involved claimed that "the Coppersmith's methods does not seem to provide any advantages", and that "it may be very hard to give any precise rigorous or even convincing heuristic analysis of this approach". Our purpose in this paper is to tackle this issue.

Contributions of the paper. We predict the EC-LCG sequence and the EC-PG sequence using Coppersmith's method for calculating the small roots of multivariate polynomials modulo an integer. The method for multivariate polynomials is heuristic since it is not proven and may fail (but in practice it works most of the time). At the end of the Coppersmith's methods we use the methods from [START_REF] Benhamouda | Easing coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness[END_REF] to analyze the success condition.

In the case where the composer is known, we showed that the EC-LCG is insecure if a proportion of at most 1/5 of the least significant bits of two consecutive values U 0 and U 1 of the sequence is hidden. This improves the previous bound of 1/6 of Gutierrez and Ibeas. We further improve this result by considering several consecutive values of the sequence. We showed that the EC-LCG is insecure if a proportion of at most 3/11 of the least significant bits of these values is hidden.

We also consider the case where some most significant bits of the abscissa of several points U kn are given, with n ∈ N for some fixed integer k. In this case, the addition law on the elliptic curve gives us a system of polynomials of high degree whose roots are the hidden bits. We use summation polynomials [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF] on elliptic curves to obtain a system of polynomials of low degree. We then showed that the EC-LCG is insecure if a proportion of at most 1/8 of the least significant bits of two values X(U 0 ) and X(U k ) is hidden, where X(P ) denotes the abscissa of the point P on the curve. This attack is the first cryptanalytic result on the EC-LCG when the attacker knows some most significant bits of non-consecutive values of the generator. We further improve this result by considering several values U kn , n ∈ N of the sequence. We also show that the EC-LCG is insecure if a proportion of at most 1/4 of the least significant bits of the abscissa of these values is hidden.

In the case where the composer is unknown, we showed that the EC-LCG is insecure if a proportion of at most 1/24 of the least significant bits of two consecutive values U 0 and U 1 of the sequence is hidden. This improves significantly the (heuristic) previous bound 1/46 of Gutierrez and Ibeas. We further improve this result by considering sufficiently many consecutive values of the sequence. We showed that the EC-LCG is insecure if a proportion of at most 1/8 of the least significant bits of these values is hidden.

Finally, we also showed that the EC-PG is insecure if a proportion of at most 1/2e 2 of the least significant bits of the abscissa of two consecutive values V 0 and V 1 of the sequence is hidden. We improve this bound by considering several consecutive values of the sequence and we showed that the EC-PG is insecure if a proportion of at most 1/e 2 of the least significant bits of the abscissa of these values is hidden. To our knowledge no such results are known in the literature for the EC-PG.

The table below gives a comparison between our results and those known in the literature. It gives the bound of the proportion of least significant bits hidden from each value necessary to break the EC-LCG in (heuristic) polynomial time. The basic proportion corresponds to the case where the adversary knows bits coming from the minimum number of intermediate values leading to a feasible attack; while the asymptotic proportion corresponds to the case when the bits known by the adversary knows bits coming from arbitrary number of values.

Preliminaries

In this section, we collect some statements about elliptic curves, Coppersmith's methods and analytic combinatorics.

Elliptic curves

Throughout this paper, let p be a prime number (with p 5). We first recall the arithmetic of the group law ⊕ on elliptic curves defined by the Weierstrass equation (for more details on elliptic curves, we refer to [START_REF] Blake | Elliptic curves in cryptography[END_REF][START_REF] Washington | Elliptic curves. Number theory and cryptography[END_REF]). Let E : y 2 = x 3 + ax + b be an elliptic curve over F p . For two points P = (x P , y P ) ∈ E(F p ) and Q = (x Q , y Q ) ∈ E(F p ), with P, Q = O, the addition law ⊕ is defined as R = (x R , y R ) = P ⊕ Q where:

• If x P = x Q , then x R = m 2 -x P -x Q mod p, y R = m(x P -x R ) -y P mod p, where, m = y Q -y P x Q -x P mod p (1)
• If x P = x Q but y P = y Q , then R = O • If P = Q and y P = 0, then x R = m 2 -2x P mod p, y R = m(x P -x R ) -y P mod p, where, m = 3x 2 Q + a 2y P mod p • If P = Q and y P = 0, then R = O.

Division polynomials of elliptic curves

With the notation from the previous paragraph, we recall some basic facts on division polynomials of elliptic curves (see again [START_REF] Washington | Elliptic curves. Number theory and cryptography[END_REF] and [START_REF] Blake | Elliptic curves in cryptography[END_REF] for details). They provide a way to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. The division polynomials ψ m (X, Y ) ∈ F p [X, Y ]/(Y 2 -X 3 -AX -B), m 0, are recursively defined by:

ψ 0 = 0 ψ 1 = 1 ψ 2 = 2Y ψ 3 = 3X 4 + 6AX 2 + 12BX -A 2 ψ 4 = 4Y (X 6 + 5AX 4 + 20BX 3 -5A 2 X 2 -4ABX -8B 2 -A 3 ) ψ 2m+1 = ψ m + 2ψ 3 m -ψ m-1 ψ 3 m+1 , m 2 ψ 2m = ψ m (ψ m+2 ψ 2 m-1 -ψ m-2 ψ 2 m+1 )/ψ 2 , m 3, where ψ m is an abbreviation for ψ m (X, Y ). If m is odd, then ψ m (X, Y ) ∈ F p [X] is univariate and if m is even then ψ m (X, Y ) ∈ ψ 2 (X, Y )F p [X] so ψ m (X, Y ) ∈ 2Y F p [X]. Therefore, as ψ 2 2 (X, Y ) = 4(X 3 +AX+B), we have ψ 2 m (X, Y ) ∈ F p [X] and ψ m-1 (X, Y )ψ m+1 (X, Y ) ∈ F p [X]
. In particular, we may write ψ 2m+1 (X) and ψ 2 m (X). As mentioned above, the division polynomials can be used to calculate multiples of a point on the elliptic curve E. Let P = (x, y) ∈ E with P = O, then the abscissa of [m]P is given by

θ m (x) ψ 2 m (x)
, where θ m (X) = Xψ 2 m -ψ m-1 ψ m+1 .

The zeros of the denominator ψ 2 m (X) are exactly the abscissa of the non-trivial m-torsion points, i.e, the points Q = (x, y) ∈ F p 2 \ {O} on E with [m]Q = O. Note, that these points occur in pairs Q = (x, y) and

-Q = (x, -y), which coincide only if 2Q = O, i.e, if
x is a zero of ψ 2 2 (X). We recall that the group of m-torsion points E[m], for an elliptic curve E defined over a field of characteristic p, is isomorphic to (Z/mZ) 2 if p m and to a proper subgroup of (Z/mZ) 2 if p | m. If m is a power of p then E[m] is either isomorphic to (Z/mZ) or to {O}. Accordingly, the degree of ψ 2 m (X) is m 2 -1 if p m and strictly less than m 2 -1 otherwise. In particular, for p = 2 and m a power of 2 we have deg(ψ 2 m ) = m -1 if E is not supersingular and deg(ψ 2 m ) = 0 otherwise. By induction one can show that θ m (X) ∈ F p [X] is monic of degree m 2 .

Summation polynomials

With the same notation as above, for n ∈ N, n 2, we define introduce n-th summation polynomial

f n = f n (X 1 , X 2 , . . . , X n ) introduced by Semaev in [Sem04] such that f n (x 1 , . . . , x n ) = 0
for x i ∈ F p (the algebraic closure of F p if and only if there exist y 1 , . . . , y n ∈ F p such that (x 1 , y 1 ), . . . , (x n , y n ) ∈ E(F p ) and

(x 1 , y 1 ) ⊕ • • • ⊕ (x n , y n ) = O.
These polynomials have found interesting applications in cryptography (in particular for solving the discrete logarithm problem on elliptic curves defined finite fields, see [START_REF] Diem | On the discrete logarithm problem in elliptic curves Compos[END_REF] and references therein).

The following lemma gives a simple way for calculating them:

Lemma 1. The n-th Semaev summation polynomial f n may be defined by:

f 2 (X 1 , X 2 ) = X 1 -X 2 f 3 (X 1 , X 2 , X 3 ) = (X 1 -X 2 ) 2 X 2 3 -2 ((X 1 + X 2 )(X 1 X 2 + a) + 2a) X 3 + (X 1 X 2 -a) 2 -4b(X 1 + X 2 ) f n (X 1 , . . . , X n ) = Res X (f n-k (X 1 , . . . , X n-k-1 , X), f k+2 (X n-k , . . . , X n , X)), n 4 and 1 k n -1 .
The polynomial f n is symmetric and of degree 2 n-2 in each variable X i for any n 3. The polynomial f n is absolutely irreducible and we have

f n (X 1 , . . . , X n ) = f 2 n-1 (X 1 , . . . , X n-1 )X 2 n-2 n + . . .

Coppersmith's methods

In this section, we give a short description of Coppersmith's method for solving a multivariate modular polynomial system of equations modulo an integer N . We refer the reader to [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF] for details and proofs.

Problem definition.

Let f 1 (y 1 , . . . , y n ), . . . , f s (y 1 , . . . , y n ) be irreducible multivariate polynomials defined over Z, having a root (x 1 , . . . , x n ) modulo a known integer N , namely f i (x 1 , . . . , x n ) ≡ 0 mod N . We want this root to be small in the sense that each of its components is bounded by a known value X i . We also need to bound the sizes of X i allowing to recover the desired root in polynomial time.

Polynomials collection.

In a first step, one generates a collection P of polynomials { f1 , . . . , fr } linearly independent having (x 1 , . . . , x n ) as a root modulo N . Usually, multiples and powers of products of f i for i ∈ {1, . . . , s} are chosen, namely f = y

α 1, 1 • • • y α n, n f k 1, 1 • • • f k s, s
for some integers α 1, , . . . , α n, , k 1, , k s, . Such polynomials satisfy the relation f (x 1 , . . . , x n ) ≡ 0 mod N s i=1 k i, , i.e., there exists an integer c i such that fi (x 1 , . . . ,

x n ) = c i N s j=1 k j, .

Matrix construction.

We denote as M the set of monomials appearing in collection of polynomials P. Then each polynomial fi can be expressed as a vector with respect to a chosen order on M. We hence construct a matrix M as follows and we define as L the lattice generated by its rows:

f1 • • • fr ↓ • • • ↓                         1 1 X -1 1 y 1 . . . . . . X -a1 1 . . . X -an n y a1 1 . . . y an n 0 N s i=1 ki,1 . . . N s i=1 ki,r
On that figure, every row of the upper part is related to one monomial of M (we assume in the figure that M contains 1, y 1 , and y a1 1 . . . y an n among other monomials). The left-hand side contains the bounds on these monomials (e.g., the coefficient

X -1 1 X -2 2
is put in the row related to the monomial y 1 y 2 2 ). The right-hand side is formed by all vectors coming from P.

A short vector in a sublattice.

Let us now consider the row vector

r 0 = (1, x 1 , . . . , x a1 1 . . . x an n , -c 1 , . . . , -c r ) .
By multiplying this vector by the matrix M, one obtains:

s 0 = 1, x 1 X 1 , . . . , x 1 X 1 a1 • • • x n X n an , 0, . . . , 0 .
The knowledge of s 0 ∈ L is sufficient to recover the root we are searching for and its norm is very small since s 0 2 √ M. Thus, the recovery of a small vector in L, will likely lead to the recovery of the desired root (x 1 , . . . , x n ). To this end, we first restrict ourselves in a more appropriated subspace. Indeed, noticing that the last coefficients of s 0 are all null, we know that this vector belongs to a sublattice L whose last coordinates are composed by zero coefficients. By doing elementary operations on the rows of M, one can construct that sublattice and its determinant is the same as the one of L.

Method conclusion.

From that point, one computes an LLL-reduction on the lattice L and computes the Gram-Schmidt's orthogonalized basis (b 1 , . . . , b t ) of the LLL output basis (b 1 , . . . , b t ). Since s 0 belongs to L , this vector can be expressed as a linear combination of the b i 's. Consequently, if its norm is smaller than those of b t , then s 0 is orthogonal to b t . Extracting the coefficients appearing in b t , one can construct a polynomial p 1 defined over Z such that p 1 (x 1 , . . . , x n ) = 0. Repeating the same process with the vectors b t-1 , . . . , b t-n+1 leads to the system {p 1 (x 1 , . . . , x n ) = 0, . . . , p n (x 1 , . . . , x n ) = 0}. Under the (heuristic) assumption that all created polynomials define an algebraic variety of dimension 0, the previous system can be solved (e.g., using elimination techniques such as Groebner basis) and the desired root recovered in polynomial time.

The conditions on the bounds X i that make this method work are given by the following (simplified) inequation (see [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF] for details):

y k 1 1 ...y kn n ∈M X k1 1 • • • X kn n < N r =1 s i=1 k i, . (2)
For such techniques, the most complicated part is the choice of the collection of polynomials, what could be a really intricate task when working with multiple polynomials.

Remark 1. As noted above, the inequality 2 is simplified. In [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF], there is an additionnal multiplicative term in the right-hand side that depends only on the dimension of the lattice and does not depend on N (and therefore only contributes to an error term as N grows with the security parameter). The non-simplified equation is

y k 1 1 ...y kn n ∈M X k1 1 • • • X kn n < 2 -ω(ω-1)/4 ω -ω/2 N r =1 s i=1 k i, . (3)
where ω = #M denotes the number of monomials.

Analytic combinatorics

In the following, we recall the analytic combinatorics methods from [START_REF] Flajolet | Analytic Combinatorics[END_REF] to estimate the exponents of the bounds X 1 , . . . , X n and of the modulo N on the monomials and polynomials appearing in the inequality (2) in Coppersmith's methods. Those methods can be used to compute the cardinalities of the sets P and M. We used the same notations as in [START_REF] Benhamouda | Easing coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness[END_REF] and for more details of the methods the reader is referred to that paper.

To make things clear, we will explain the method with one simple example. Suppose we want to solve the equation: f (y 1 , . . . , y n ) = 0 mod N , with |y i | X i . We consider the set of polynomials

P = {f k = y k1 1 . . . y kn n f k mod N k : 1 k < t and deg(f k ) = k 1 + • • • + k n + k e < te} ,
The set of monomials appearing in the collection P will usually look like

M = {y k = y k1 1 . . . y kn n : 0 deg(y k ) = k 1 + • • • + k n < te} .
These considerations imply that for the final condition in Coppersmith's method (see Equation (2)), one needs to compute the values

ψ = f k ∈P k and ∀i ∈ {1, . . . , n}, α i = y k ∈M k i .
These values correspond to the exponent of N and X i (for i ∈ {1, . . . , n}) in Equation (2) respectively. We show how to compute these sums ψ and α i for polynomials in P or M of a certain degree.

We see P (respectively M) as a combinatorial class with size function S(f k ) = deg(f k )(respectively S(y k ) = deg(y k )). We recall that a combinatorial class is a finite or countable set on which a size function is defined, satisfying the following conditions: (i) the size of an element is a non-negative integer and (ii) the number of elements of any given size is finite. We define another function χ, called a parameter function, such that χ(f k ) = k (respectively χ(y k ) = k i ). This allows us to compute ψ (respectively α i ) as: We proceed as follows:

ψ = χ <te (P) = a∈P:S(a)<te
1. We give another description of A with respect to S and χ. This description associates to the combinatorial class an ordinary generating function (OGF) F (z, u) (using Table 1, see [START_REF] Benhamouda | Easing coppersmith methods using analytic combinatorics: Applications to public-key cryptography with weak pseudorandomness[END_REF] for details).

When the class contains elements of different sizes (such as variables of degree 1 and polynomials of degree e), the variables in the OGF are represented by the atomic element Z and the polynomials by the element Z e , in order to take into account the degree of these polynomials. Then we "mark" the element useful for the parameter, with a new variable u. At this level we only know how to compute a∈A:S(a)=p χ(a). An easier way to compute χ p (A) is to force all elements a of size less than or equal to p to be of size exactly p by adding enough times a dummy element y 0 such that χ(y 0 ) = 0. In our context of polynomials, the aim of the dummy variable y 0 is to homogenize the polynomial.

Construction OGF Atomic class Z Z(z) = z Neutral class ε E(z) = 1 Disjoint union A = B + C (when B ∩ C = ∅) A(z) = B(z) + C(z) Complement A = B \ C (when C ⊆ B) A(z) = B(z) -C(z) Cartesian product A = B × C A(z) = B(z) • C(z) Cartesian exponentiation A = B k = B × • • • × B A(z) = B(z) k Sequence A = Seq(B) = ε + B + B 2 + . . . A(z) = 1 1-B(z)
2. We have:

χ (A)(z) = +∞ p=0 χ p (A)z p = ∂F (z, u) ∂u u=1 ,
3. Since Coppersmith's method is usually used in an asymptotic way, singularity analysis enables us to find the asymptotic value of the coefficients in an simple way by using the following theorem (see [START_REF] Flajolet | Analytic Combinatorics[END_REF], page 392):

Theorem 2 (Transfer Theorem). Let A be a combinatorial class with an ordinary generating function F regular enough such that there exists a value c verifying

F (z) = +∞ n=0 F n z n ∼ z→1 c (1 -z) α
for a non-negative integer α. The asymptotic value of the coefficient F n is

F n ∼ n→∞ (cn α-1 )/(α -1)! .

Predicting EC-LCG Sequences for Known Composer

Following [START_REF] Gutierrez | Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits[END_REF], our results involve a parameter ∆ which measures how well some values approximate the sequence elements. More precisely, we say that

W = (x W , y W ) ∈ F 2 p is a ∆-approximation to U = (x U , y U ) ∈ F 2 p if there exist integers e, f satisfying: |e|, |f | ∆, x W + e = x U and y W + f = y U .
For a given point G ∈ E(F p ), the EC-LCG generates a sequence U n of points defined by the relation:

U n = U n-1 ⊕ G = [n]G ⊕ U 0 , n ∈ N
where U 0 ∈ E(F p ) is the initial value or seed. We refer to G as the composer of the EC-LCG. In the cryptographic setting, the initial value U 0 = (x 0 , y 0 ) and the constants G, a and b are supposed to be the secret key. In the following we infer the sequence output by the EC-LCG in the case where the composer G is known and the curve is kept secret.

We consider two settings: the case where the most significant bits of consecutive values U n of the sequence is output and the case where the most significant bits of the abscissa of consecutive multiple values U kn (for some fixed integer k) of the sequence is output. In the first case, we show that the generator is insecure if at least a proportion of 4/5 of the most significant bits of two consecutive values U 0 and U 1 of the sequence is output. In the second case, We show that the generator is insecure if at least a proportion of 7/8 of the most significant bits of two values X(U 0 ) and X(U k ) is output, X(P ) denoting the abscissa of the point P .

3.1. Information on consecutive inputs Theorem 3. (two consecutive outputs) Given ∆-approximations W 0 , W 1 to two consecutive affine value U 0 , U 1 produced by the EC-LCG, and given the value of the composer G = (x G , y G ). Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in heuristic polynomial time in log p as soon as ∆ < p 1/5

Proof. We suppose U 0 / ∈ {-G, G}. Then, clearing denominators in (1), we can translate

U 1 = U 0 ⊕ G
into the following identities in the field F p :

L 1 = L 1 (x 0 , y 0 , x 1 ) = 0 mod p, L 2 = L 2 (x 0 , y 0 , x 1 , y 1 ) = 0 mod p
where U 0 = (x 0 , y 0 ), U 1 = (x 1 , y 1 ) and

L 1 = x 3 G + x 1 x 2 G -x 0 x 2 G -2x 1 x G x 0 -x G x 2 0 + x 3 0 + 2y G y 0 + x 1 x 2 0 -y 2 G -y 2 0 , L 2 = y 1 x G -y 1 x 0 -y G x 0 + y G x 1 -y 0 x 1 + y 0 x G .
Set W 0 = (α 0 , β 0 ) and W 1 = (α 1 , β 1 ). Then using the equalities x j = α j + e j and y j = β j + f j , for j ∈ {0, 1}, where |e j |, |f j | < ∆ leads to the following polynomial system:

f (e 0 , e 1 , f 0 ) = 0 mod p g(e 0 , e 1 , f 0 , f 1 ) = 0 mod p .

where f (z 1 , z 2 , z 3 ) = A 1 z 1 + A 2 z 2 + A 3 z 3 + A 4 z 2 1 + A 5 z 1 z 2 + z 3 1 + z 2 1 z 2 -z 2 3 + A 6 and g(z 1 , z 2 , z 3 , z 4 ) = B 1 z 1 + B 2 z 2 + B 3 z 3 + B 4 z 4 + z 1 z 4 + z 2 z 3 + B 5
are polynomials whose coefficients A i and B i are functions of x G , and the approximations values

α 0 , α 1 , β 0 , β 1 . If we fix u = z 3 1 + z 2 1 z 2 -z 2 3 and v = z 1 z 4 + z 2 z 3 , then the polynomial f becomes f 1 (z 1 , z 2 , z 3 , u) = A 1 z 1 + A 2 z 2 +A 3 z 3 +A 4 z 2 1 +A 5 z 1 z 2 +u+A 6 and g becomes g 1 (z 1 , z 2 , z 3 , z 4 , v) = B 1 z 1 +B 2 z 2 +B 3 z 3 +B 4 z 4 +v +B 5 .
Description of the attack. The adversary is therefore looking for the small solutions of the following modular multivariate polynomial system:

f 1 (z 1 , z 2 , z 3 , u) = 0 mod p g 1 (z 1 , z 2 , z 3 , z 4 , v) = 0 mod p . With |z j | < ∆, |u| < X = ∆ 3 and |v| < Y = ∆ 2 .
The attack consists in applying Coppersmith's methods for multivariate polynomials. From now, we use the following collection of polynomials (parameterized by some integer t ∈ N):

P = z j1 1 . . . z j4 4 f i1 1 g i2 1 mod p i1+i2 : i 1 + i 2 > 0 and j 1 + • • • + j 4 + 2i 1 + i 2 < 2t 9
The list of monomials appearing within this collection can be described as:

M = z i1 1 z i2 2 z i3 3 z i4 4 u i5 v i6 mod ∆ i1+i2+i3+i4 X i5 Y i6 : i 1 + • • • + i 4 + 2i 5 + i 6 < 2t .
If we use for instance the monomial order lex (with z i < u < v) on the set of monomials, then the leading monomial of f 1 is LM (f 1 ) = u and LM (g 1 ) = v. Then the polynomials in P are linearly independent since we have prohibited the multiplication by u and v.

Bounds for the polynomials modulo p. We consider the set P as a combinatorial class, with the size function S(z j1 1 . . .

z j4 4 f i1 1 g i2 1 ) = j 1 + • • • + j 4 + 2i 1 + i 2 and the parameter function χ(z j1 1 . . . z j4 4 f i1 1 g i2 1 ) = i 1 + i 2 .
The degree of each variable z i , u, v is 1, whereas the degree of f 1 is 2 and the degree of g 1 is 1. For the sake of simplicity, we can consider 0 i 1 + i 2 , since the parameter function equals 0 for elements z j1 1 . . . z j4 4 f i1 1 g i2

1 with i 1 + i 2 = 0.
We can describe P as:

4 i=1 Seq(Z) × Seq(uZ 2 ) × Seq(uZ) × Seq(Z),
where the last one is for the dummy value z 0 . This leads to the generating function:

F (z, u) = 1 1 -z 5 × 1 1 -uz 2 × 1 1 -uz .
We have

∂F ∂u (u, z) u=1 = z 2 (1 -z) + z(1 -z 2 ) (1 -z) 7 (1 -z 2 ) 2 , as z → 1 , 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 3(1 -z) 4(1 -z) 9 ∼ 3 4(1 -z) 8 ,
since 2t ∼ 2t -1, this leads to:

χ <2t (P) ∼ 3 4 × (2t) 7 7!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function

S(z i1 1 . . . z i4 4 u i5 v i6 ) = i 1 + • • • + i 4 + 2i 5 + i 6 and the parameter function χ(z i1 1 . . . z i4 4 u i5 v i6 ) = i 1 + • • • + i 4 .
As z 1 , z 2 , z 3 , z 4 , u, v "count for" 1, 1, 1, 1, 2 and 1 respectively in the condition of the set, we can describe M as:

Seq(Z 2 ) × Seq(Z) × 4 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dummy value z 0 . Which leads to the generating function:

F (z, u) = 1 (1 -z 2 )(1 -z) 2 × 1 1 -uz 4 . We have ∂F ∂u (u, z) u=1 = 4z (1 -z) 7 (1 -z 2 ) , as z → 1, 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 2 (1 -z) 8 , since 2t ∼ 2t -1, this leads to: χ <2t,∆ (M) ∼ 2(2t) 7

7! 10

Bounds for the monomials modulo X. We consider the set M as a combinatorial class, with the size function S(z i1 1 . . . z i4 4 u i5 v i6 ) = i 1 + • • • + i 4 + 2i 5 + i 6 and the parameter function χ(z i1 1 . . . z i4 4 u i5 v i6 ) = i 5 . As z 1 , z 2 , z 3 , z 4 , u, v "count for" 1, 1, 1, 1, 2 and 1 respectively in the condition of the set, we can describe M as:

5 i=1 Seq(Z) × Seq(uZ 2 ) × Seq(Z),
where the last one is for the dummy value z 0 . Which leads to the generating function:

F (z, u) = 1 (1 -z) 6 × 1 1 -uz 2 .
This leads to:

χ <2t,X (M) ∼ (2t) 7 4 × 7!
Bounds for the monomials modulo Y . We consider again the set M as a combinatorial class, with the size function

S(z i1 1 . . . z i4 4 u i5 v i6 ) = i 1 + • • • + i 4 + 2i 5 + i 6 and the parameter function χ(z i1 1 . . . z i4 4 u i5 v i6 ) = i 6 .
As z 1 , z 2 , z 3 , z 4 , u, v "count for" 1, 1, 1, 1, 2 and 1 respectively in the condition of the set, we can describe M as:

4 i=1 Seq(Z) × Seq(Z 2 ) × Seq(uZ) × Seq(Z),
where the last one is for the dummy value z 0 . Which leads to the generating function:

F (z, u) = 1 (1 -z) 5 (1 -z 2 ) × 1 1 -uz .
This leads to:

χ <2t,Y (M) ∼ (2t) 7 2 × 7!
Condition. If we denote by ν 1 = χ <2t,∆ (M), ν 2 = χ <2t,X (M), ν 3 = χ <2t,Y (M) and ε = χ <2t (P), the condition for Coppersmith's method is p ε > ∆ ν1 X ν2 Y ν3 , ie ∆ < p ε ν 1 +3ν 2 +2ν 3 , where:

ε ν 1 + 3ν 2 + 2ν 3 ∼ χ <2t (P) χ <2t,∆ (M) + 3χ <2t,X (M) + 2χ <2t,Y (M) ∼ 1 5 ,
this leads to the bound:

∆ < p 1 5 .
Complexity of the attack. The dimensions of the matrix used in Coppersmith methods depend on the cardinalities of the set of polynomials and monomials. To compute the cardinalities of the sets P and M, we make use of the parameters functions χ(z j1 1 . . . z j4 4 f i1 1 g i2 1 ) = 1 and χ(z i1 1 . . . z i4 4 u i5 v i6 ) = 1. This leads to the generating functions:

F 1 (z) = 1 1 -z 5 × 1 1 -z 2 × 1 1 -z -1
and

F 2 (z) = 1 1 -z 5 × 1 1 -z 2 × 1 1 -z ,
for P and M respectively.

We have:

F 1 (z), F 2 (z) ∼ z→1 1 2(1 -z) 7 ,
which leads when t goes to infinity to the asymptotic bound:

1 2 × (2t) 6 6!
From the inequality (2), one can see that the attack works if

p ε > ∆ ν1 X ν2 Y ν3 , with I 1 = {i = (i 1 , . . . , i 6 )|0 i 1 + • • • + i 4 + 2i 5 + i 6 < 2t}, I 2 = {i = (j 1 , . . . , j 4 , i 1 , i 2 )| i 1 + i 2 > 0 and 0 j 1 + • • • + j 4 + 2i 1 + i 2 < 2t}, ν 1 = i∈I1 i 1 + • • • + i 4 , ν 2 = i∈I1 i 5 , ν 3 = i∈I1 i 6 and ε = i∈I2 i 1 + i 2
. Putting X = ∆ 3 and Y = ∆ 2 , we then have the following theoretical bound

∆ < p δ theo ,
where δ theo = ε ν1+3ν2+2ν3 . If one uses the non-simplified inequality (3), we only obtain ∆ < 2 -ω(ω-1)/4 ω -ω/2 p δ theo where ω = #M denotes the number of monomials. The "error term" is thus independent of p but so small that we can only conclude theoretically that the attack works only for very large p (several hundreds of bits even for only t = 2). However, our experiments show that the attack works for practical values of p (and even sometimes for ∆ < p δexp , where δ exp > δ theo . We give in the table below the cardinalities of the sets P, M and the theoretical bound δ theo for smaller t. Unfortunately, even if t is small, the constructed matrix is of huge dimension (since the number of monomials is quite large) and the computation which is theoretically polynomial-time becomes in practice prohibitive. These attacks are nethertheless good evidence of a weakness in this pseudo-random generator.

Experimental Results. We have implemented the attack in Sage 7.6 on a MacBook Air laptop computer (2,2 GHz Intel Core i7, 4 Gb RAM 1600 MHz DDR3, Mac OSX 10.10.5). Table 2 lists the dimension d of the lattice (d = P + m), the theoretical bound δ theo and an experimental bound δ exp for a m-bit prime p. We consider the family of polynomials P with t = 2 (since for t > 2, the dimension of the lattice is huge). We ran several experiments for all parameters and Table 2 gives the average running time (in seconds) of the LLL algorithm, the Gram-Schmidt's orthogonalization algorithm and the Gröbner basis computation. This bound improves the known bound ∆ < p 1/6 . Next we further improve the previous bound and we show that the generator is insecure if at least a proportion of 8/11 of the most significant bits of a large number of consecutive values U i of the sequence is output. Proof. Let us assume, for instance that the adversary has access to n + 1 ∆-approximations W 0 , W 1 ,. . . ,W n of U 0 , U 1 ,. . . ,U n produced by the EC-LCG. Then using the equalities x j = α j + e j and y j = β j + f j , for j ∈ {0, . . . , n}, where |e j |, |f j | < ∆ and W j = (α j , β j ) and U j = (x j , y j ) leads to the following polynomial system:

                 f 1 (e 0 , e 1 , f 0 ) = 0 mod p g 1 (e 0 , e 1 , f 0 , f 1 ) = 0 mod p . . . f n (e n-1 , e n , f n-1 ) = 0 mod p g n (e n-1 , e n , f n-1 , f n ) = 0 mod p .
Where for i ∈ {1, . . . , n},

f i (z i-1 , z i , z n+i ) = A 1 z i-1 + A 2 z i + A 3 z n+i + A 4 z 2 i-1 + A 5 z i-1 z i + z 3 i-1 + z 2 i-1 z i -z 2 n+i + A 6 and g i (z i-1 , z i , z n+i , z n+i+1 ) = B 1 z i-1 + B 2 z i + B 3 z n+i + B 4 z n+i+1 + z i-1 z n+i+1 + z i z n+i + B 5
are polynomials whose coefficients A i and B i are functions of x G , and the approximations values

α k , β k , (k ∈ {i -1, i}). If we fix u i = z 3 i-1 + z 2 i-1 z i -z 2 n+i and v i = z i-1 z n+i+1 + z i z n+i , then the polynomial f i becomes f i (z i-1 , z i , z n+i , u i ) = A 1 z i-1 + A 2 z i + A 3 z n+i + A 4 z 2 i-1 + A 5 z i-1 z i + u i + A 6 and g i becomes g i (z i-1 , z i , z n+i , z n+i+1 , v i ) = B 1 z i-1 + B 2 z i + B 3 z n+i + B 4 z n+i+1 + v i + B 5 .
The adversary is then looking for the solutions of the modular multivariate polynomial system:

                 f 1 (z 0 , z 1 , z n+1 ) = 0 mod p g 1 (z 0 , z 1 , z n+1 , z n+2 ) = 0 mod p . . . f n (z n-1 , z n , z 2n ) = 0 mod p g n (z n-1 , z n , z 2n , z 2n+1 ) = 0 mod p . With |z j | < ∆, j ∈ {0, . . . , 2n + 1}, |u i | < X = ∆ 3 and |v i | < Y = ∆ 2 , i = 1, . . . , n.
We consider the following collection of polynomials: P = fj0,...,j2n+1,i1,...,in,l1,...,ln = z j0 0 . . . z

j2n+1 2n+1 f i1 1 . . . f in n g l1 1 . . . g ln n mod p i1+l1•••+in+ln s.t. i 1 + l 1 + • • • + i n + l n > 0 and j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n < 2t .
The list of monomials appearing within this collection can be described as:

M = z j0 0 . . . z j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n mod ∆ j0+•••+j2n+1 X i0+•••+in Y l0+•••+ln s.t. j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n < 2t .
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj0,...,j2n+1,i1,...,in,l1,...,ln

) = j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n
and the parameter function χ( fj0,...,j2n+1,i1,...,in,l1,...,ln

) = i 1 + l 1 + • • • + i n + l n .
We can describe P as:

2n+1 i=0 Seq(Z) × n j=1 Seq(uZ 2 ) × n k=1 Seq(uZ) × Seq(Z),
where the last one is for the dummy variable. This leads to the generating function:

F (z, u) = 1 (1 -z) 2n+3 × 1 (1 -uz 2 ) n × 1 (1 -uz) n .
We have

∂F ∂u (u, z) u=1 ∼ z→1 3n 2 n+1 (1 -z) 4n+4 , since 2t ∼ 2t -1, we get: χ <2t (P) ∼ 3n 2 n+1 × (2t) 4n+3 (4n + 3)!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j0 0 . . . z

j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n ) = j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n and the parameter function χ(z j0 0 . . . z j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n ) = j 0 + • • • + j 2n+1 .
We can describe M as:

n i=1 Seq(Z 2 ) × n i=1 Seq(Z) × 2n+1 i=0 Seq(uZ) × Seq(Z),
where the last one is for the dummy value y 0 . Which leads to the generating function:

F (z, u) = 1 (1 -z 2 ) n (1 -z) n+1 × 1 (1 -uz) 2n+2 . As z → 1, 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 2n + 2 2 n (1 -z) 4n+4 , since 2t ∼ 2t -1, this leads to: χ <2t,∆ (M) ∼ 2n + 2 2 n × (2t) 4n+3 (4n + 3)!
Bounds for the monomials modulo X.. We consider the set M as a combinatorial class, with the size function S(z j0 0 . . . z

j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n ) = j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n and the parameter function χ(z j0 0 . . . z j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n ) = i 1 + • • • + i n .
We can describe M as:

2n+1 i=0 Seq(Z) × n i=1 Seq(Z) × n i= Seq(uZ 2 ) × Seq(Z),
where the last one is for the dummy value y 0 . Which leads to the generating function:

F (z, u) = 1 (1 -z) 3n+3 × 1 (1 -uz 2 ) n .
This leads to:

χ <2t,X (M) ∼ n 2 n+1 × (2t) 4n+3 (4n + 3)!
Bounds for the monomials modulo Y . We consider the set M as a combinatorial class, with the size function S(z j0 0 . . . z

j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n ) = j 0 + • • • + j 2n+1 + 2(i 1 + • • • + i n ) + l 1 + • • • + l n and the parameter function χ(z j0 0 . . . z j2n+1 2n+1 u i1 1 v l1 1 . . . u in n v ln n ) = l 1 + • • • + l n .
We can describe M as:

2n+1 i=0 Seq(Z) × n i=1 Seq(Z 2 ) × n i= Seq(uZ) × Seq(Z),
where the last one is for the dummy value y 0 . Which leads to the generating function:

F (z, u) = 1 (1 -z) 2n+3 (1 -z 2 ) n × 1 (1 -uz) n .
This leads to:

χ <2t,Y (M) ∼ n 2 n × (2t) 4n+3 (4n + 3)! Condition. If we denote by ν 1 = χ <2t,∆ (M), ν 2 = χ <2t,X (M), ν 3 = χ <2t,Y (
M) and ε = χ <2t (P), the condition for Coppersmith's method is p ε > ∆ ν1 X ν2 Y ν3 , ie ∆ < p ε ν 1 +3ν 2 +2ν 3 , where:

ε ν 1 + 3ν 2 + 2ν 3 ∼ χ <2t (P) χ <2t,∆ (M) + 3χ <2t,X (M) + 2χ <2t,Y (M) ∼ 3n 11n + 4 ,
this leads to the expecting bound:

∆ < p 3n 11n+4 → n→∞ ∆ < p 3/11 .

Information on non-consecutive inputs

In this section, we consider an attacker with information on non-consecutive inputs. Our attacks only make use of the abscissa of the points generated by the EC-LCG. Given as above parameter ∆ which measures how well some values approximate the sequence elements, we say that w ∈ F p is a ∆-approximation to x ∈ F p if there exist an integer e satisfying: |e| ∆ and w + e = x.

Theorem 5. (two outputs) Given ∆-approximations w 0 , w k to two values X(U 0 ), X(U k ) produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in polynomial time in log p as soon as ∆ < p 1/8 . Proof. We set U 0 = (x 0 , y 0 ), U k = (x k , y k ) and G = (x G , y G ). We then have the equalities:

x i = w i + e i where |e i | < ∆, i ∈ {0, k}. We have U 0 -U k = -kG, thus U 0 -U k + kG = O. Hence: f 3 (x 0 , x k , X(kG)) = 0,
where f 3 is the polynomial defined in section 2. Using the equalities x i = w i + e i , i ∈ {0, k} we obtain the polynomial equation:

f (e 0 , e k ) = 0, where f (y 1 , y 2 ) = f 3 (w 0 + y 1 , w 0 + y 2 , X(kG)). If we consider monomials with respect to lexicography ordering, we have LM (f ) = y 2 1 y 2 2 . f is a polynomial of degree 4. We consider the following collection of polynomials:

P = { fj1,j2,i = y j1 1 y j6 6 f i mod p i : i > 0 and j 1 + j 2 + 4i < 4t and (j 1 < 2 ∨ j 2 < 2)} ,
One can check that the polynomials fj1,j2,i are linearly independent since LM (f ) = y j1 1 y j2 2 for each fj1,j2,i from P. The list of monomials appearing within this collection can be described as:

M = z j1 1 z j2 2 mod ∆ j1+j2 : j 1 + j 2 < 4t ,
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj1,j2,i ) = j 1 + j 2 + 4i and the parameter function χ( fj1,j2,i ) = i. Since the degree of each variable z i is 1 and the degree of f is 4, we can describe P as:

Seq(uZ 4 ) × (ε + Z)(Seq(Z) + Z 2 Seq(Z)) × Seq(Z),
where the last one is for the dumming value y 0 . This leads to the generating function:

F (z, u) = (1 + z)(1 + z 2 ) (1 -z) 2 × z 4 1 -uz 4 . We have ∂F ∂u (u, z) u=1 = z 4 (1 + z)(1 + z 2 ) (1 -z) 2 (1 -z 4 ) 2 as z → 1, 1 -z 4 ∼ 4(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 1 4(1 -z) 4 , since 4t ∼ 4t -1, this leads to: χ <4t (P) ∼ 1 4 × (4t) 3 3!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(y j1 1 y j2 2 ) = j 1 + j 2 and the parameter function χ(y j1 1 y j2 2 ) = j 1 + j 2 . Since the degree of each z i is 1, we can then described M as:

2 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dumming value y 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz 2 × 1 1 -z .
We have ∂F ∂u (u, z)

u=1 = 2z (1 -z) 4 , as z → 1, 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 2 (1 -z) 4 , since 4t ∼ 4t -1, this leads to: χ <4t (M) ∼ 2(3t) 3 3!
Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is

p ν > ∆ ε , ie ∆ < p ν ε , where: ν ε ∼ χ <4t (P) χ <4t (M) ∼ 1 8 ,
this leads to the expecting bound:

∆ < p 1 8 .
We can further improve the previous bound and we show that the generator is insecure if at least a proportion of 1/4 of the most significant bits of a large number of abscissa of the values U ki of the sequence is output. Theorem 6. (more outputs) Given ∆-approximations w 0 , w k ,. . . ,w kn to n + 1 values X(U 0 ), X(U k ),. . . , X(U kn ) produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in polynomial time in log p as soon as ∆ < p n 4(n+1) .

Proof. We set U kt = (x kt , y kt ), for t = 0, . . . , n and G = (x G , y G ). We then have the equalities:

x i = w i + e i where |e i | < ∆, i ∈ {0, k, . . . , nk}.
We have U kt -U k(t+1) = -kG, for t = 0, . . . , n -1. Thus U kt -U k(t+1) + kG = O. Hence:

f 3 (x tk , x k(t+1) , X(kG)) = 0,
where f 3 is the polynomial defined in section 2. Using the equalities x i = w i + e i , i ∈ {0, k, . . . , kn} we obtain the polynomial system: f j (e (j-1)k , e jk ) = 0, j ∈ {1, . . . , n} where f j (y j-1 , y j ) = f 3 (w (j-1)k + y j-1 , w jk + y j , X(kG)). If we consider monomials with respect to lexicography ordering, we have LM (f k ) = y 2 j-1 y 2 j . f j is a polynomial of degree 4. We consider the following collection of polynomials:

P = { fj0,...,jn,i k = y j0 0 . . . y jn n f i k k mod p i k : k ∈ {1, . . . , n}; (j k-1 < 2 ∨ j k < 2) (i k > 0) and (j 0 + • • • + j n + 4i k ) < 4t} ,
One can check that the polynomials fj0,...,jn,i k are linearly independent. The list of monomials appearing within this collection can be described as:

M = z j0 0 . . . z jn n mod ∆ j0+•••+jn : j 0 + • • • + j n < 4t
, Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj0,...,jn,i k ) = j 0 + • • • + j n + 4i k and the parameter function χ( fj0,...,jn,i k ) = i k . Since the degree of each variable z i is 1 and the degree of f is 4, we can describe P as:

n k=1 Seq(uZ 4 ) × (ε + Z)(Seq(Z) + Z 2 Seq(Z)) × n j=0,j =k-1,k Seq(Z) × Seq(Z),
where the last one is for the dumming value z 0 . This leads to the generating function:

F (z, u) = n k=1 (1 + z)(1 + z 2 ) (1 -z) n+1 × 1 1 -uz 4 . We have ∂F ∂u (u, z) u=1 = nz 4 (1 + z)(1 + z 2 ) (1 -z) n+1 (1 -z 4 ) 2 as z → 1, 1 -z 4 ∼ 4(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 n 4(1 -z) n+3 , since 4t ∼ 4t -1, this leads to: χ <4t (P) ∼ n 4 × (4t) n+2 (n + 2)!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(y j1 1 y j2 2 ) = j 0 + • • • + j n and the parameter function χ(y j0 0 . . . y jn n ) = j 0 + • • • + j n . Since the degree of each z i is 1, we can then described M as:

n i=0 Seq(uZ) × Seq(Z),
where the last one is for the dumming value z 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz n+1 × 1 1 -z .
We have ∂F ∂u (u, z)

u=1 = 2z (1 -z) n+3 ,
Description of the attack. The adversary is therefore looking for the solutions smaller than ∆ of the following modular multivariate polynomial equation: f (z 1 , . . . , z 6 ) = 0 mod p The attack consists in applying Coppersmith's methods as in the former subsection. If we consider monomials with respect to lexicographic order, then the leading monomial of f is z 3 1 z 2 . From now on, we use the following collection of polynomials:

P = { fj1,...,j6,i = z j1 1 . . . z j6 6 f i mod p i : i > 0 and j 1 + • • • + j 6 + 4i < 4t and (0 j 1 < 3 ∨ j 2 = 0)} ,
One can check that the polynomials fj1,...,j6,i are linearly independent since LM (f ) = z j1 1 . . . z j6 6 for each fj1,...,j6,i from P. The list of monomials appearing within this collection can be described as:

M = z j1 1 . . . z j6 6 mod ∆ j1+•••+j6 : j 1 + • • • + j 6 < 4t .
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj1,...,j6,i ) = j 1 + • • • + j 6 + 4i and the parameter function χ( fj1,...,j6,i ) = i. Since the degree of each variable z i is 1 and the degree of f is 4, we can describe P as:

4 i=1 Seq(Z) × Seq(uZ 4 ) ×   (ε + Z + Z 2 z1 )(ε + ZSeq(Z) z2 ) + Z 3 Seq(Z) z1    × Seq(Z),
where the last one is for the dummy value z 0 . This leads to the generating function:

F (z, u) = 1 1 -z 5 × 1 1 -uz 4 × (1 + z + z 2 )(1 + z/(1 -z)) + z 3 1 -z .
We have ∂F ∂u (u, z)

u=1 = 1 + z + z 2 + z 3 (1 -z) 6 × z 4 (1 -z 4 ) 2 as z → 1, 1 -z 4 ∼ 4(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 1 4(1 -z) 8 , since 4t ∼ 4t -1, this leads to: χ <4t (P) ∼ 1 4 × (4t) 7 7!
Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j1 1 . . . z j6 6 ) = j 1 + • • • + j 6 and the parameter function χ(z j1 1 . . . z j6 6 ) = j 1 + • • • + j 6 . Since the degree of each z i is 1, we can then described M as:

6 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dummy value z 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz 6 × 1 1 -z .
We have

∂F ∂u (u, z) u=1 = 6z (1 -z) 8 , as z → 1, 1 -z n ∼ n(1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 6 (1 -z) 8 ,
since 4t ∼ 4t -1, this leads to:

χ <4t (M) ∼ 6(3t) 7 7!
Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is

p ν > ∆ ε , ie ∆ < p ν ε
, where:

ν ε ∼ χ <4t (P) χ <4t (M) ∼ 1 24 ,
this leads to the expecting bound: ∆ < p 1 24 .

Complexity of the attack. To compute the cardinalities of the sets P and M, we make used of the parameters functions χ( fj1,...,j6,i ) = 1 and χ(z j1 1 . . . z j6 6 ) = 1. This leads to the generating functions:

F 1 (z) = 1 1 -z 5 × z 4 1 -z 4 × 1 + z + z 2 + z 3 1 -z and F 2 (z) = 1 (1 -z) 7 ,
for P and M respectively. Asymptotic bounds. We have: This bound improves the known bound ∆ < p 1/46 . Next, we further improve the previous bound and we show that the generator is insecure if at least a proportion of 7/8 of the most significant bits of an infinite consecutive values U i of the sequence is output.

F 1 (z), F 2 (z) ∼ z→1 1 (1 -z)
Theorem 8. (more consecutive outputs) Given ∆-approximations W 0 , W 1 ,. . . ,W n+1 (for some integer n > 1) to n + 2 consecutive affine values U 0 , U 1 ,. . . ,U n+1 produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 and the composer G in polynomial time in log p as soon as ∆ < p n/4(2n+4) .

Proof. Let us assume, for instance that the adversary has access to n+1 ∆-approximations W 0 , W 1 ,. . . ,W n+1 of U 0 , U 1 ,. . . ,U n+1 produced by the EC-LCG. Then using the equalities x j = α j + e j and y j = β j + f j , for j ∈ {0, . . . , n}, where |e j |, |f j | < ∆ and W j = (α j , β j ) and U j = (x j , y j ) and the fact that y 2 j = x 3 j + ax j + b, j ∈ {0, . . . , n + 1} and eliminating the curve parameters from three consecutive points U j , U j+1 , U j+2 ,j ∈ {0, . . . , n -1} leads to the following polynomial system:

       f 1 (e 0 , e 1 , e 2 , f 0 , f 1 , f 2 ) = 0 mod p . . . f n (e n-1 , n , e n+1 , f n-1 , f n , f n+1 ) = 0 mod p .
Where f j are polynomials of degrees 4 and LM (f i ) = z 3 i-1 z i . The adversary is then looking for the solutions of the modular multivariate polynomial system:

       f 1 (z 0 , z 1 , z 2 , z n+2 , z n+3 , z n+4 ) = 0 mod p . . . f n (z n-1 , z n , z n+1 , z 2n+1 , z 2n+2 , z 2n+3 ) = 0 mod p .
We consider the following collection of polynomials:

P =    fj0,...,j2n+3,αi = z j0 0 . . . z j2n+3 2n+3 f αi i mod p αi s.t. i ∈ {1, . . . , n}; (j i-1 < 3 ∨ j i = 0) (α i > 0) and (j 0 + • • • + j 2n+3 + 4α i ) < 4t    .
The list of monomials appearing within this collection can be described as:

M = z j0 0 . . . z j2n+3 2n+3 mod ∆ j0+•••+j2n+3 : j 0 + • • • + j 2n+3 < 4t ,
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj0,...,j2n+3,αi ) = j 0 + • • • + j 2n+3 + 4α i and the parameter function χ( fj0,...,j2n+3,αi ) = α i . We can describe P as:

n i=1 2n+3 j=0 j∈{i-1,i} Seq(Z) × Seq(uZ 4 ) × (ε + Z + Z 2 )(ε + ZSeq(Z)) + Z 3 Seq(Z) × ε × Seq(Z),
where the last one is for the dummy variable. This leads to the generating function:

F (z, u) = 1 (1 -z) 2n+3 × 1 1 -uz 4 × n (1 + z + z 2 )(1 + z/(1 -z)) + z 3 1 -z .
We have where the last one is for the dummy variable. This leads to the generating function:

∂F ∂u (u, z) u=1 ∼ z→1 n 4(1 -z) 2n+6 , since 4t ∼ 4t -1, this leads to: χ <4t (P) ∼ n 4 × (
F (z, u) = 1 1 -uz 2n+4 × 1 1 -z .
We get

∂F ∂u (u, z) u=1 ∼ 2n + 4 (1 -z) 2n+6 , since 4t ∼ 4t -1, this leads to: χ <4t (M) ∼ (2n + 4) × (4t) 2n+5 (2n + 5)!
Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is

p ν > ∆ ε , ie ∆ < p ν ε , where: ν ε ∼ χ <4t (P) χ <4t (M) ∼ n 4(2n + 4) ,
This leads to the expecting bound:

∆ < p n 4(2n+4) → n→∞ ∆ < p 1/8 .

Predicting the Elliptic curve power generator

We show that one can predict the sequences generated by the EC-PG in the case where the constants a, b and e are known. We show that the generator is insecure if at least a proportion of 1 -1 2e 2 of the most significant bits of two consecutive values X(V 0 ) and X(V 1 ) is output.

Theorem 9. (two consecutive outputs) Given ∆-approximations w 0 , w 1 to two consecutive values X(V 0 ), X(V 0 ) produced by the EC-PG and under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed V 0 in heuristic polynomial time in log p as soon as ∆ < p

1 2e 2 Proof. We put V 0 = (x 0 , y 0 ), V 1 = (x 1 , y 1 ). We have x 1 = θe(x0) ψ 2 e (x0) since V 1 = eV 0 . Using the equalities x 0 = w 0 + α 0 and x 1 = w 1 + α 1 with α i < ∆, we have f (α 1 , α 0 ) = 0, where f (y 1 , y 2 ) = (y 1 + w 1 )ψ 2
e (y 2 + w 0 )-θ e (y 2 +w 0 ). We are looking for small modular modulo p. If we monomials with respect to lexicography ordering, then the leading monomial of f is y 1 y e 2 -1 2 . f is a polynomial of degree e 2 . We consider the following collection of polynomials (parameterized by some integer t ∈ N): P = f j1,j2,i = y j1 1 y j2 2 f i mod p i : i > 0 and j 1 + j 2 + e 2 i < e 2 t and (j 1 = 0 ∨ 0 j 2 e 2 -2) .

One can check that the polynomials f j1,j2,i are linearly independent since LM ( f j1,j2,i ) = y j1 1 y j2 2 for each f j1,j2,i . The list of monomials appearing within this collection can be described as:

M = y j1 1 y j2 2 mod ∆ j1+j2 : j 1 + j 2 < e 2 t .
Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj1,j2,i ) = j 1 + j 2 + e 2 i and the parameter function χ( fj1,j2,i ) = i. Since the degree of each variable z i is 1 and the degree of f is e 2 , we can describe P as:

Seq(uZ e 2 ) ×   (ε + Z + • • • + Z e 2 -2 y2 )(ε + ZSeq(Z) y1 ) + Z e 2 -1 Seq(Z) y2    × Seq(Z),
where the last one is for the value y 0 . This leads to the generating function:

F (z, u) = 1 1 -z 2 × 1 1 -uz e 2 × 1 + z + • • • + z e 2 -1 . We have ∂F ∂u (u, z) u=1 = z e 2 (1 + z + • • • + +z e 2 -1 ) (1 -z) 2 (1 -z e 2 ) 2 as z → 1, 1 -z e 2 ∼ e 2 (1 -z) leads to: ∂F ∂u (u, z) u=1 ∼ z→1 1 e 2 (1 -z) 4
, since e 2 t ∼ e 2 t -1, this leads to:

χ <e 2 t (P) ∼ 1 e 2 ×
(e 2 t) 3 3! Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j1 1 . . . z j6 6 ) = j 1 + • • • + j 6 and the parameter function χ(y j1 1 y j2 2 ) = j 1 + j 2 . Since the degree of each z i is 1, we can then described M as:

2 i=1 Seq(uZ) × Seq(Z),
where the last one is for the dumming value y 0 . Which leads to the generating function: Theorem 10. (more consecutive outputs) Given ∆-approximations w 0 , w 1 ,. . . ,w n (for some integer n > 1) to n + 1 consecutive values X(V 0 ), X(V 1 ),. . . , X(V 1 ) produced by the EC-PG and under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed V 0 in heuristic polynomial time in log p as soon as ∆ < p n (n+1)e 2 Proof. We put V i = (x i , y i ), i ∈ {0, . . . , n}. We have x j+1 = θe(xj ) ψ 2 e (xj ) since V j+1 = eV j for j ∈ {0, . . . , n -1}. Using the equalities x i = w i + α i , i ∈ {0, . . . , n} with α i < ∆, we have f j (α j , α j-1 ) = 0, for j ∈ {1, . . . , n} where f j (y j-1 , y j ) = (y j-1 + w j )ψ 2 e (y j + w j-1 ) -θ e (y j + w j-1 ). We are then looking for small modular modulo p. We use the Coppersmith's methods to recover the desired solution in polynomial time. If we monomials with respect to lexicography ordering, then the leading monomial of each f j is y j-1 y e 2 -1 j . f j is a polynomial of degree e 2 . We consider the following collection of polynomials (parameterized by some integer t ∈ N): P = f j1,...,jn,i k = y j1 1 . . . y jn n f i k k mod p i k : i k > 0, k ∈ {1, . . . , n}, and j 1 + • • • + j n + e 2 i k < e 2 t and (j k-1 = 0 ∨ 0 j k e 2 -2) .

F (z, u) = 1 1 -uz 2 × 1 1 -z . We have ∂F ∂u (u, z) u=1 = 2z (1 -z) 4 , which leads to: ∂F ∂u (u, z) u=1 ∼ z→1 2 (1 -z) 4 , since e 2 t ∼ e 2 t -
One can check that the polynomials f j1,...,jn,i k are linearly independent since LM ( f j1,...,jn,i k ) = y j1 1 . . . y jn n for each f j1,...,jn,i k . The list of monomials appearing within this collection can be described as: M = y j0 0 . . . y jn n mod ∆ j0+•••+jn : j 0 + • • • + j n < e 2 t .

Bounds for the Polynomials modulo p. We consider the set P as a combinatorial class, with the size function S( fj1,...,jn,i k ) = j 1 + • • • + j 2 + e 2 i k and the parameter function χ( fj1,...,jn,i k ) = i k . Since the degree of each variable z i is 1 and the degree of f k is e 2 , we can describe P as: where the last one is for the dumming value z 0 . This leads to the generating function:

F (z, u) = n k=1 1 1 -z n+1 × 1 + z + • • • + z e 2 -1 1 -uz e 2 .
We have ∂F ∂u (u, z) Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j1 1 . . . z j6 6 ) = j 1 + • • • + j 6 and the parameter function χ(y j0 0 . . . y j2 n ) = j 1 + • • • + j n . Since the degree of each y i is 1, we can then described M as:

n i=0 Seq(uZ) × Seq(Z),
where the last one is for the dumming value z 0 . Which leads to the generating function:

F (z, u) = 1 1 -uz (n+1) × 1 1 -z .
We

Conclusion

We analyzed the security of the Elliptic Curve Linear Congruential Generator (EC-LCG) and of the Elliptic Curve Power Generator (EC-PG). In the case where the composer is known, we showed that the EC-LCG is insecure if at least a proportion of 8/11 of the most significant bits of an arbitrary large number of consecutive values U i of the sequence is output. We also tackle the case where the most significant bits of an arbitrary large number of non consecutive values (namely the most significant bits of the abscissa of values U ki for some fixed integer k) of the sequence is output and we showed that the EC-LCG is insecure if at least a proportion of 3/4 of the most significant bits is output. Furthermore, we consider the cryptographic setting where the composer is unknown and we showed that this generator is insecure if at least a proportion of 7/8 of the most significant bits of an arbitrary large number of consecutive values U i of the sequence is output. Finally, we showed that the EC-PG is insecure if a proportion of at least 1 -1/e 2 of the most significant bits of the abscissa of an arbitrary large number of consecutive values V i of the sequence is output. However, our results are theoretical since in practice, the performance of Coppersmith's method in our attacks is prohibitive because of large dimension of the constructed lattice but they are good evidences of the weaknesses of these generators.

  χ(a) (respectively α i = χ <te (M) = a∈P:S(a)<te χ(a) ). To do so we should be able to compute given a combinatorial class A (A = P or A = M) with size function S and the parameter function χ, χ p (A) = a∈A:S(a) p χ(a) .

  4t) 2n+5 (2n + 5)! Bounds for the monomials modulo ∆. We consider the set M as a combinatorial class, with the size function S(z j0 0 . . . z j2n+3 2n+3 ) = j 0 + • • • + j 2n+3 and the parameter function χ(z j0 0 . . . z j2n+3 2n+3 ) = j 0 + • • • + j 2n+3 . We can describe M as: 2n+4 i=1 Seq(uZ) × Seq(Z),

nk=1

  Seq(uZ e 2 )×   (ε + Z + • • • + Z e 2 -2 y k )(ε + ZSeq(Z) y k-1 ) + Z e 2 -1 Seq(Z) =k,k-1 Seq(Z)×Seq(Z),

u=1 = nz e 2

 2 (1 + z + • • • + +z e 2 -1 ) (1 -z) n+1 (1 -z e 2 ) 2 as z → 1, 1 -z e 2 ∼ e 2 (1 -z) leads to: 1 -z) n+3, since e 2 t ∼ e 2 t -1, this leads to:χ <e 2 t (P) ∼ n e 2 ×(e 2 t) n+2 (n + 2)!

Table 1 :

 1 Combinatorics constructions and their OGF

Table 2 :

 2 Predicting EC-LCG Sequences for Known Composer Theorem 4. (more consecutive outputs) Given ∆-approximations W 0 , W 1 ,. . . ,W n (for some integer n > 1) to n + 1 consecutive affine values U 0 , U 1 ,. . . ,U n produced by the EC-LCG, and given the value of the composer G = (x G , y G ). Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 in polynomial time in log p as soon as ∆ < p

	m	t	δ theo	δ exp	d LLL time(s) Gram-Schmidt's time(s)	Gröbner basis time(s)
	128 2 0.182	0.20	89	2.908	20.910	0.567
	256 2 0.182	0.12	89	2.957	46.157	6.474
			3n
			11n+4

  Concrete bounds. We give in the table below the cardinalities of the sets P and M for smaller t.

				7 ,
	which leads when t goes to infinity to the asymptotic bound:
		(4t) 6
		6!
	t	1	2	3	4	5
	number of polynomials 0	84	1716 12376 54264
	number of monomials 84 1716 12376 54264 177100

  1, this leads to:Condition. If we denote by ν = χ <e 2 t (P), and ε = χ <e 2 t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p

	ν ε , where:
	ν ε	∼	χ <e 2 t (P) χ <e 2 t (M)	∼	1 2e 2 ,
	this leads to the expecting bound:
			∆ < p	1 2e 2 .
	χ <e 2 t (M) ∼	2(e 2 t) 3 3!

  If we denote by ν = χ <e 2 t (P), and ε = χ <e 2 t (M), the condition for Coppersmith's method is p ν > ∆ ε , ie ∆ < p

	have		∂F ∂u	(u, z)	u=1	=	(n + 1)z (1 -z) n+3 ,
	which leads to:	∂F ∂u (1 -z) ν (u, z) u=1 n + 1 ∼ z→1 ε , where:
			ν ε	∼	χ <e 2 t (P) χ <e 2 t (M)	∼	n (n + 1)e 2 ,
	this leads to the expecting bound:	∆ < p	n (n+1)e 2	→ n→∞	∆ < p	1 e 2 .

( n + 3) , since e 2 t ∼ e 2 t -1, this leads to:

χ <e 2 t (M) ∼ (n + 1)(e 2 t) ( n + 2) (n + 2)!

Condition.

as z → 1, 1 -z n ∼ n(1 -z) leads to: n+3 , since 4t ∼ 4t -1, this leads to:

Condition. If we denote by ν = χ <4t (P), and ε = χ <4t (M), the condition for Coppersmith's method is

, where:

this leads to the expecting bound:

Predicting EC-LCG Sequences for Unknown Composer

In this section, we infer the EC-LCG in the case where the composer G is unknown and the curve is kept secret. In the following, We show that the generator is insecure if at least a proportion of 23/24 of the most significant bits of three consecutive values U 0 and U 1 and U 2 of the sequence is output. Theorem 7. (three consecutive outputs) Given ∆-approximations W 0 , W 1 , W 2 to three consecutive affine values U 0 , U 1 , U 2 produced by the EC-LCG. Under the heuristic assumption that all created polynomials we get by applying Coppersmith's method with the polynomial set P below define an algebraic variety of dimension 0, one can recover the seed U 0 and the composer G in polynomial time in log p as soon as ∆ < p 1/24 . Proof. We set U 0 = (x 0 , y 0 ), U 1 = (x 1 , y 1 ), U 2 = (x 2 , y 2 ), W 0 = (α 0 , β 0 ), W 1 = (α 1 , β 1 ) and W 2 = (α 2 , β 2 ). We then have the equalities:

We also have:

Eliminating the curve parameters a, b and assuming that U 2 = ±U 1 (that is, x 2 = x 1 ), we obtain the following equation:

Using the equalities (3), leads to the equation:

f (e 0 , e 1 , e 2 , f 0 , f 1 , f 2 ) = 0 mod p where f is a polynomial of degree 4 whose coefficients are functions of α 0 , α 1 , α 2 , β 0 , β 2 , and β 2 .


J E Arlot
email: arlot@imcce.fr

G Dourneau
email: dourneau@obs.u-bordeaux1.fr

J F Le Campion

An analysis of Bordeaux meridian transit circle observations of planets and satellites (1997-2007)

Keywords:

Context. Meridian transit circle observations of the planets and their satellites are regularly performed for ephemerides improvement. Some have been made in Bordeaux observatory during the period 1997-2007. Aims. This paper presents these observations and makes an analysis of the data in order to determine the accuracy of the observations, their interest for dynamical purpose and a comparison with the dynamical models of the observed objects. Methods. For the determination of the positions of the planets, the observations of their satellites have been used, providing pseudo observations of the planet. The method is tested. Results. The results show the interest of continuing this type of observations. Residuals show what ephemerides have to be improved using the present data.

Introduction

Bordeaux observatory continues to perform meridian transit circle observations and has included in its program of observations some solar system objects. Since it appears that more solar system objects observations are needed and that the observations performed with other transit circle instruments are very useful, we wondered if it was worth to continue our observations. The analysis of the reduction and of the comparison of observational data with ephemerides and with other observations made during the same period of time will answer this question.

The observations

The instrument

The Bordeaux meridian transit circle is a 20cm diameter refractor with a 2.37m focal length. The derived scale of the instrument is 87 arcsec/mm. The Bordeaux observatory is located at the following geodetic coordinates: Longitude = 0 deg 31 min 39 sec W, Latitude = 44 deg 50 min 7 sec N and Elevation = Send offprint requests to: J.E. Arlot 73m. The Bordeaux meridian circle was fully automated from 1984 (Requieme and Mazurier, 1991). It was equipped with a photometric micrometer until 1994 when it received a CCD camera (512x512 pixels) for tests and from 1996 the definitive camera (1024x1024).

A two-stage thermoelectric Peltier unit is used to cool the Thomson 7896M CCD detector below -40 • C in order to limit the resulting dark noise to about 65e-/s. The size of the pixels is 19 µm x 19 µm, corresponding to 1.65 arcsec x 1.65 arcsec in the sky. In declination, the field of the CCD chip is 28 arcmin. In right ascension, the transit time is 112s/cosδ for stars with a declination of δ. This time corresponds to the exposure time of the instrument when used in the drift scan mode.

Drift scan mode was used instead of classical stare mode. The scan mode appeared necessary in view of the characteristics of the transit observations and it allows to observe every night a greater number of stars. Also, the rather long exposure time (about 112s) improves the limiting magnitude up to 16. As stars with a magnitude of 8.5 can be observed without significant pixel saturation, the dynamical range of the CCD unit appears to be about 7.5 mag. The strips observed in scan mode with the CCD detector are narrow in declination (28 arcmin) and can be much wider in right ascension, up to several hours. Oppositely, the scan mode presents some drawbacks, as the distortion of star images which can reach a critical level at high declinations. Stars are rejected when their images present an elongation in right ascension six times higher than in declination. As a result, no observation can be done for declinations above 78 degrees. This is not a real problem for the observation of solar system objects orbiting near the equator.

Both GG495 and BG38 filters are used to select a reduced bandwidth of 5200-6800 Å, with a central wavelength of 6050 Å, so as to limit the chromatic refraction to about 0.04 arcsec tanz. Today, the Bordeaux observatory meridian circle remains one of the last instruments of this type in regular operation with the FASTT in Flagstaff (Stone, 1996), the CMASF in San Fernando, Argentina (Muinos et al. 2006) and the Valinhos meridian circle in Brazil (Viateau et al. 1999). For more detailed information about the Bordeaux meridian circle, refer to Viateau et al. (1996).

The program of observations

The regular observations of solar system objects as Uranus and Neptune have begun in 1982 with a photoelectric micrometer (Rapaport et al. 1987). In 1996, with the automated CCD camera, we have continued this program in observing new objects as Pluto and the main satellites of Uranus as Ariel, Umbriel, Titania and Oberon, as well as Triton, the satellite of Neptune. Moreover, some of the major satellites of Saturn: Titan, Hyperion and Iapetus were observed from 1998. The planet Saturn was not observed, because of its too high brightness. Also, the image processing appeared not to be efficient enough to derive an accurate position of the planet Saturn from its irregular shape, due to the vicinity of the rings. Some results of the first observations of Pluto and Saturn s satellites were obtained by Rapaport et al. (2002).

Further the regular observations of planets and satellites, the Bordeaux meridian circle is currently involved in several other observing programs. In the recent years, the main of these programs was Meridien 2000, planning a systematic observation of the Bordeaux zone of the Astrographic Catalogue (11 deg ≤ δ ≤ 18 deg) for more than 3 years. A very consistent catalogue of positions and proper motions of all stars up to magnitude 15 has been derived (Rapaport et al., 2001;Ducourant et al., 2006;Rapaport et al., 2006). Other observing programs concern the asteroids, either to improve their masses (Viateau and Rapaport, 1996) or the accuracy of the prediction of star occultations from last minute observations. More recently, another program involving some extragalactic radiosources as blazars, was developed in order to contribute to improve the ICRF system [START_REF] Le Campion | Highlights 2004[END_REF].

The reduction

Image processing

The first step of the image processing is the extraction of the sky background. Two methods may be used. The first one consists in fitting the background to a polynomial of degree from 0 to 3. This is a fast method but it can only be used for moderate gradients. In the case of planetary satellites, located in fields with stronger gradients, the median filter method is preferred. This method consists in searching the median value M of a square of 15 x 15 pixels centered on each pixel and to subtract M to the value of the central pixel.

After the extraction of sky background, the identification of objects is processed from the comparison of each pixel to the standard deviation σ of the residuals of the pixels for each column. An object is identified when 2 consecutive pixels present residuals greater than 3 σ. Two objects can be separated if their distance is greater than 5 arcsec. Then, the photo centre of the images is computed from a two-dimensional Gaussian fit. Bright objects with magnitudes lower than 8.5, as some of the solar system objects involved in our observing program, present images with pixels which may be saturated. Then, such saturated pixels are rejected in the Gaussian fit, so as to limit possible consequent bias in the determination of the photo centre.

Astrometric reduction

For each star of each individual strip observed each night, the following system of equations below is used to rely the catalogued right ascension α R , declination δ R , and magnitude V R of reference stars to their rectangular measured coordinates (x, y) expressed in pixels and to the measured flux Φ in encoder step units so as:

α R = α 0 + a 1 x + a 2 (y -y 0 ) δ R = δ 0 + b 1 (y -y 0 ) + b 2 x + b 3 Φ V R = V 0 2.5 log Φ + cx α R
and δ R are the catalogued positions of stars, reduced to the epoch of observation from their proper motions. α 0 represents the local sidereal time at the instant of the beginning of the strip, and δ 0 the declination of the centre of the strip y 0 . The flux term in declination b 3 Φ is used to recover the excessive shift of charge in the CCD for the images of bright objects. As this effect appears to be negligible in right ascension, no flux term is used in this coordinate. The constants a 1 , a 2 , b 1 , b 2 , b 3 , V 0 and c, in equations above, are determined by the least-squares method, as well as α 0 and δ 0 , also adjusted to observations. Then, the constants are used to determine the new positions and magnitude of the reference stars and of the other non-catalogued objects as secondary stars, planets and satellites. A preliminary catalogue is obtained from the mean positions of all the stars common to the different strips, including secondary stars. The positions of this preliminary catalogue are reintroduced in equations above for a second astrometric reduction. The convergence of the constants generally occurs after 5 successive iterations of this procedure. In order to limit atmospheric effects which can affect the observed positions, a curve is fitted on the residuals of each night of observations by the B-spline method (Viateau et al.1999). The used reference catalogue is Tycho 2 providing data with an accuracy better than 60 mas for positions and 2.5 mas/year for proper motions (Hog et al.2000). So, the positions of solar system objects observed by the Bordeaux meridian circle have a mean accuracy of about 60 mas. They are topocentric and given in the ICRF system and no chromatic correction has been made.

We made several attempts to evaluate the chromatic effects. The first one was derived from the previous work (Rapaport et al.2001) made in the range of declination between 11 and 18 degrees of the M2000 catalog. Fig. 1 visualizes the derived chromatic departure versus (B-V) index. For this range of declination, Fig. 1 shows that chromatic departure is unsignificant, as always under 20 mas, for objects with (B-V) index between 0.5 and 1, as most of solar system objects. In the recent years, Saturn s satellites were located at a declination close to the M2000 zone. So, their positions presented in this paper must be unsignificantly affected by chromatic effect and do not need any correction. But Uranus, Neptune and Pluto were located at a negative declination from -10 degrees to -15 degrees during the recent period of observations. As chromatic effect is increasing with the zenital distance, the positions of these objects and their satellites can be affected with an higher departure. Due to their low (B-V) index, we have shown, by extrapolating the curve given in Fig. 1 to lower declinations, that the planets Uranus and Neptune remain only affected with very slight chromatic effect under 20 mas. Only their satellites Titania, Oberon and Triton, as well as the dwarf planet Pluto, due to their higher (B-V) index, can be affected with a significant higher chromatic effect which remains lower than positional errors. A second recent evaluation of chromatic effect involving much more stars, including low declination ones, has shown that this effect should be lower than 10 mas, whatever the declination and the (B-V) index of solar system objects. This last evaluation, obtained from real observations, appears to be more realistic than the first one which was derived from an extrapolation of observational effects. Finally, no chromatic correction has been made. Anyway, this point still remains under consideration for the future.

The data obtained

The observations were carried out through the program of observations of the Bordeaux transit circle. Planets and their satel-lites were included in the program when possible. We did not include all the objects for several reasons. For some planets, it was unnecessary to make such observations because of the large sets of modern data (radar or from space probes) available, sufficient for dynamics purpose (Mercury, Venus, Mars). For some planets such as Jupiter and Saturn, and some satellites, such as the Galilean satellites, the magnitude did not allow the observation. Anyway, the accuracy of the transit circle observations of the planets Jupiter and Saturn themselves will not be sufficient for dynamics purpose. We were not able to observe the Galilean, but we observed the Saturnian satellites. The good results obtained will lead us to solve the technical problems in order to observe the Galilean satellites. We will see further that the positions of the satellites may be used in order to propose pseudo-observed positions of their primary that is very useful for Saturn: we observe a satellite, then we calculate the theoretical positions of the center of mass of the system and get a pseudo-positions of the planet. The error on such a position is the one of the dynamical model of the satellite which is much smaller than the error on the measurement of the position of the center of mass of the planet itself. We provide in Table 1, the main characteristics of the observed objects, in Table 2, the number of observations made, and in Table 3 the rms of each series of data calculated as follows:

rms = Σ(r -rm) 2 (N -1) (1)
where r is the O-C on one observation and rm the mean (O-C) for the series. N is the number of observations. The used ephemerides are DE405 for the planets, TASS for the Saturnian satellites (Vienne and Duriez, 1995;[START_REF] Duriez | [END_REF], LA06 by Lainey and Arlot (2007) for the Uranian satellites and Jacobson (1991) for Triton. It is clear that the quality of the observations depends on the magnitude of the object as shown in Fig. 2. For magnitude larger than 14, the accuracy decreases rapidly as it is obvious in Table 3 for Hyperion and the Uranian satellites. Note that differences appear in right ascension and declination. These differences did not come from chromatic effects but confirm only that a meridian transit circle is more accurate in right ascension than in declination.

All the observational data have been published extensively in the Note Scientifique et Technique de l IMCCE n • S089 [START_REF] Dourneau | Note scientifique et technique de l IMCCE n • S089[END_REF]. They are available at the Web address: http://www.imcce.fr/page.php?nav=fr/publications/nst -C) of all the observations. Note that the ephemerides are DE405 for the planets, TASS or Do93 by [START_REF] Dourneau | [END_REF] for the Saturnian satellites and LJ86 (Laskar and Jacobson 1987) or LA06 for the Uranian satellites (Arlot et al. 2007). Table 4 gives the values of the mean (O-C)s for each object and for each opposition. We have to notice that the motions of the planets are slow enough to have a very small variation of the (O-C) over one opposition (a few months) that is not true for the satellites which have a fast motion and then, a variation of the (O-C)s with time over the same period. However, the mean (O-C) for the satellite over one opposition should be very close to the mean (O-C) for the planet. For the Saturnian system, only three satellites were observed showing similar (O-C)s which should correspond to the one of the planet. Hyperion, the magnitude of which is 14.2, has a worse accuracy due to a bad S/N ratio. For the Uranian system, we find the same status. Contrarily to the Saturnian system, the planet itself has been observed that confirms that the satellites show similar (O-C) than the planet. Ariel should be excluded because its poor observation history and Umbriel because the bad astrometric results as consequence of its magnitude. For the Neptunian system, Triton s (O-C)s discrepancy is larger than the one of Neptune and we do not find similar values. For Pluto, systematic negative (O-C)s seem to appear, as well as for Uranus and Neptune.

In conclusion, assuming that the objects have a magnitude brighter than 15, the observations have an accuracy making them useful for dynamical purpose.

Positions of planets derived from observed positions of satellites

The accuracy of the observations of some bright satellites of the planets and the fact that their (O-C)s are mainly coming from the position of the planet, may allow us to make pseudoobservations of the planets through the observation of their satellites. The dynamical models of the motion of the satellites may allow this, since the satellites are orbiting around the centre of mass of the system planet-satellites which is of interest. Note that the direct observation of the planet provides a position of an unknown point, needing a model to go to this centre of mass. The question is: what theoretical model should be the best for that purpose? the motion of the satellite on the making of the pseudo observations of the planet. Contrarily, the impact of the chosen satellite used for the making of the pseudo observation of the planet is very large. Fig. 5c shows what happens when using Hyperion instead of Titan. The discrepancy is very large and the observation of Saturn deduced from the one of Hyperion badly accurate. This was obvious when looking at Table 3: the rms of the residuals reach 0.22/0.30 arcsec for Hyperion and 0.08/0.11 for Titan for all the series of data. In the case of Iapetus, the accuracy of the measurement seems to be better than for Hyperion but the theoretical model is worse than the one of Titan that encourages us to use Titan for determining pseudo-positions of the planet at the present time.

Comparison of the observations with other sets of data made at the same time -comparison of the (O-C)s from DE403 and DE405

Since similar series of observations are made in other observatories, it is interesting to compare the results obtained. From 1997 to 2005, observations were performed at Flagstaff using FASTT transit circle facilities. Since Uranus is moving slowly, we may compare the (O-C)s issued from Flagstaff and Bordeaux. Table 5 provides the mean (O-C)s calculated using the LJ86 ephemeris for the satellites and DE 405 for the planet. For Titania and Oberon, both series of observations are in agreement, but for the planet Uranus, the results disagree. It is puzzling that the observations from Bordeaux for Uranus are in agreement with the observations of the satellites, and that is not the case for Flagstaff. Table 6 provides a comparison of the (O-C)s obtained for the opposition of 1998, with also, observations made at Itajuba, Brazil, with a classical CCD target on a 1.6m-telescope (Veiga and Vieira-Martins 1999). The results are much more in agreement except for Uranus itself, probably because of the brightness of the planet which decreases the observational accuracy. Mean residuals in Table 7 are displayed in Fig. 3 visualizing residuals in declination versus residuals in right ascension. Fig. 3 shows that the DE405 ephemeris presents no real improvement to the DE403, excepted for Saturn. For the planet Saturn, this result showing the improvement of DE405 with respect to DE403 is in good agreement with Rapaport et al.(2002). For Uranus and Neptune, we confirm the very small discrepancies between both ephemerides, previously mentioned by Rapaport et al.(2002). Fig. 3 shows that such discrepancies are less than 20 mas. We can observe they are rather favourable to DE403 but this is not really significant as we are under the observational accuracy. For Pluto, Fig. 3 also confirms the improvement of DE405 in right ascension and the theoretical difference DE405-DE403 of about 100mas in declination presented by Rapaport et al.(2002). But in this case, we can see in Fig. 3 that this significative difference in Pluto declination does not appear to be in favour of DE405. Finally, the most important improvement of DE405 with respect to DE403 is obtained for Saturn. This can be due to the fact that only new accurate observations of Saturn derived from spacecraft data were used in the DE405 in order to improve the DE403 ephemeris.

Comparison of the theories of motion of

Saturn's satellites.

Table 8 shows that most of the lowest standard errors are derived from TASS theory by Vienne and Duriez (1995) and by [START_REF] Duriez | [END_REF]. However, the lowest absolute mean residuals are generally obtained for the other theories Do93 [START_REF] Dourneau | These de Doctorat d'Etat[END_REF][START_REF] Dourneau | [END_REF] for Titan in right ascension and HT93 (Harper and Taylor 1993;Taylor 1992) for Titan in declination as well as for Iapetus in right ascension. For Hyperion, TASS theory presents all the lowest mean and standard residuals. This means that TASS has really improved HT93 Taylor s theory (1992) which had previously improved Do93 Dourneau s theory (1987). The latest theory appears to need, for this satellite, a real improvement so as to include a series of perturbation terms that have not been introduced in comparison to Taylor and TASS theories.

This analysis shows that TASS theory, presenting most of the lowest standard errors, certainly proposes the best model for representing the real orbits of Saturnian satellites. However, this theory appears to need an improvement so as a new fit to observations in order to reduce the significant shift that we have observed in right ascension and in declination.

As a conclusion about the comparison of Saturnian satellites theories, TASS appears to give the best model of orbits as it considers additional terms not included in other theories. But both of the other theories Do93 and HT93 present a better fit to observations than TASS theory for Iapetus in right ascension and for Titan in right ascension and in declination.

Conclusion

In conclusion, it appears that transit circle observations are still useful either for the observations of the planetary satellites and for the planets. The pseudo positions of the planets deduced from the observation of the satellites are valuable, mainly for Jupiter and Saturn the centers of mass of which are not easy to measure directly and also for Uranus, increasing the amount of data since Uranus itself is measurable. These observations have an accuracy similar to the one of the direct observations. These observations have allowed us to obtain some results concerning the consistency of planetary and satellite theoretical models. For the planets we have shown that the DE405 ephemeris presents no real improvement to the DE403 ephemeris, except for Saturn. For the satellites of Saturn, the TASS theory has appeared to give the best model of their orbits, but we have shown that the other models Do93 and HT93 can present a better fit to the observations for some satellites such as Titan and Iapetus. So, we encourage the continuation of such regular automatic observations allowing to keep a sample of observations well distributed in time.

Fig. 1 .

 1 Fig. 1. Chromatic departure in declination vs (B-V) index, expressed in mas (δ between 11 and 18 degrees).

Fig. 2 .

 2 Fig. 2. Dispersion of the residuals (in mas) as a function of the V-magnitude.

  We calculated the (O-C) between the observations and the ephemerides in order to see the interest of the observations for the improvement of the dynamics of the observed objects. The figures show the (O-C). Figs. 4 and 6 show the (O-C) in right ascension and declination depending on time and Figs. 5 and 7 the (O

  Fig. 4 shows the (O-C) of the planet Saturn deduced from the observations of Titan, and Fig. 5, the (O-C)s in right ascension versus declination for all the observations. It appears clearly that the ephemerides DE405 of Saturn shows a systematic offset. Fig. 5 a shows the (O-C)s when using the TASS ephemeris for Titan, Fig. 5b when using Do93 Dourneau ephemeris for Titan. The offset to DE405 is quite similar, showing the weak impact of the theoretical model of

Fig. 3 .

 3 Fig. 3. Comparison of mean residuals (O-C) in mas derived from DE403 and from DE405.

Table 8 .Fig. 4 .

 84 Fig. 4. Residuals (O-C) vs time on the positions of Saturn deduced from the observed positions of Titan.

Fig. 5 .

 5 Fig. 5. Residuals (O-C) in α vs δ on the positions of Saturn deduced from the observed positions of the satellites (a: from Titan TASS theory; b: from Titan Do93 theory; c: from Hyperion TASS theory).

Fig. 6 .

 6 Fig. 6. Residuals (O-C) vs time on the positions of Uranus directly observed and deduced from the observed positions of the satellites.

Fig. 7 .

 7 Fig. 7. Residuals (O-C) in α vs δ on the positions of Uranus directly observed and deduced from the observed positions of the satellites.

Table 1 .

 1 Main characteristics of the observed objects

	Object	mag radius radius	phase	phase orbital	max
		at			angle	defect period elong
		opp.	km	arcsec degrees	mas	days	arcsec
	Titan	8.3	2440	0.35	6	13.8	15.9	209
	Hyperion 14.2	200	0.03	6	1.3	21.3	254
	Iapetus	11.9	720	0.10	6	3.5	79.3	610
	Uranus	5.5	24500	1.75	3	34.4	-	-
	Ariel	14.4	580	0.04	3	8.1	2.5	15
	Umbriel	15.3	585	0.04	3	8.1	4.1	21
	Titania	13.9	800	0.06	3	12.3	8.7	35
	Oberon	14.2	760	0.05	3	11.8	13.5	47
	Neptune	7.8	25100	1.15	2	15.0	-	-
	Triton	13.7	1350	0.06	2	0.8	5.9	17
	Pluto	15.0	1200	0.05	2	0.7	-	-

Table 2 .

 2 Number of observations

	Object	1997 1998 1999 2000 2001 2002 2003 2004-05 2006 2007	all
	Titan	-	-	14	-	13	-	4	7	12	12	62
	Hyperion	-	-	15	-	11	-	7	8	18	11	70
	Iapetus	-	-	15	-	16	-	9	9	21	14	84
	Uranus	18	10	2	-	50	9	26	22	28	-	165
	Ariel	-	-	-	-	-	-	2	-	-	-	2
	Umbriel	2	2	-	-	1	-	6	2	7	-	20
	Titania	14	5	1	-	29	5	14	12	16	-	96
	Oberon	13	6	1	-	38	9	20	12	18	-	117
	Neptune	-	-	4	-	-	-	50	19	29	-	102
	Triton	-	-	3	-	-	-	48	18	26	-	95
	Pluto	-	-	-	-	-	23	-	-	33	-	56

Table 3 .

 3 Rms of the residuals for each series of data in mas

Table 5 .

 5 Mean residuals (O-C) in α and δ in mas for the period 1997-2005

	Object	Bordeaux	Flagstaff
		α	δ	α	δ
	Uranus	-120 -130	-10	-20
	Umbriel -120	-40	-	-
	Titania	-120 -140 -100	-80
	Oberon -150 -140 -130 -100

Table 6 .

 6 Mean residuals (O-C) in α and δ in mas for the 1998 opposition

	Object	Bordeaux	Flagstaff	Itajuba
		α	δ	α	δ	α	δ
	Uranus	-110 -130 -160 +40 -330 -10
	Ariel	-	-	-	-	-140 +40
	Umbriel	-90	+210	-	-	-160 +50
	Titania	-80	-100 -140 -20 -130 +90
	Oberon	-120	-70	-140 -70 -150 +50

Table 7 .

 7 Comparison of DE403 and DE405 ephemerides derived from mean residuals (O-C) in α and in δ of Bordeaux meridian circle 1997-2006 observations (in mas unit)

				Mean residuals (O-C)
	Object	Period	N	DE403	DE405
				α	δ	α	δ
	Titan	1999-2006	50	111	-47	71	-26
	Hyperion 1999-2006	59	89	20	54	40
	Iapetus	1999-2006	70	84	-86	51	-66
	Uranus	1997-2005 165	-70	-113	-101	-129
	Ariel	1998-2003	2	-1775	561 -1797 546
	Umbriel	1997-2005	20	-88	-22	-125	-39
	Titania	1997-2005	96	-92	-138	-122	-154
	Oberon	1997-2005 113	-108	-134	-138	-150
	Neptune	1999-2005 102	-13	-128	-26	-142
	Triton	1999-2005	89	-26	-156	-40	-170
	Pluto	2002-2005	54	170	40	-39	-91

Acknowledgements. This paper has been made possible thanks to the staff of the meridian circle of Bordeaux Observatory.