Courbes elliptiques

Loi de groupe

Une courbe elliptique est définie par une équation du type y2 + (a1 x + a3) y = x3 + a2 x2 + a4 x+ a6 ; on peut la munir d'une loi de groupe comme indiquée sur la figure ci-dessus, où M3 est la somme de M1 et M2. L'utilisation des courbes elliptiques en théorie algorithmique des nombres remonte à 1987, date à laquelle Lenstra a mis au point une méthode de factorisation utilisant ces objets [Lenstra87]. De nombreuses autres applications ont suivi: primalité d'entiers [GoKi86], [AtMo93b]; systèmes cryptographiques (voir par exemple [Menezes93], [Enge99]).

Pour en savoir plus:
[Menezes93]
Alfred J. Menezes. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.
[Enge99]
Andreas Enge. Elliptic Curves and Their Applications to Cryptography. Kluwer Academic Publishers, 1999.
[BlSeSm99]
I. Blake and G. Seroussi and N. Smart. Elliptic Curves in Cryptography. Cambridge University Press, 1999.
[GoKi86]
S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. In Proc. 18th STOC, pages 316-329. ACM, 1986. May 28-30, Berkeley.
[Lenstra87]
Hendrik W. Lenstra, Jr. Factoring integers with elliptic curves. Annals of Math., 126:649-673, 1987.

Cardinal

Un paramètre important d'une courbe elliptique sur un corps fini est son cardinal, c'est-à-dire le nombre de points (x,y) à coordonnées dans le corps fini qui satisfont l'équation de la courbe. La connaissance du cardinal permet, par exemple, de donner une preuve de primalité ou d'écarter une courbe non sûre en cryptographie. Il existe désormais une pléiade d'algorithmes rapides pour faire cela. Le premier algorithme polynomial, dû à Schoof [Schoof85] (avec de nombreuses améliorations par Atkin, Elkies, Couveignes, Lercier, Dewaghe, Mueller, etc.), est encore d'actualité pour le calcul en grande caractéristique. Sa complexité est de O (n4 + epsilon), en supposant l'utilisation de la multiplication rapide et en admettant les heuristiques à la base des améliorations.
Records de calcul du cardinal d'une courbe elliptique sur Fp
Taille en chiffres décimaux Qui Quand
65 Atkin 24/02/1991
75 Atkin 14/02/1992
100 Atkin 24/02/1992
120 Atkin 24/07/1992
130 Atkin 24/07/1992
150 Atkin 29/03/1992
200 Atkin 24/07/1992
225 Atkin ??/07/1993
250 FM 07/02/1994
276 Atkin 29/03/1994
350 RL-FM ??/04/1994
376 Müller ??/04/1994
400 RL-FM 03/10/1994
425 Müller ??/10/1994
500 RL-FM 27/01/1995

En 1999, Satoh a introduit les méthodes p-adiques dans le calcul de la cardinalité en se servant du relèvement canonique d'une courbe elliptique. Dans un corps de pn éléments pour un p fixé, son algorithme déterministe a une complexité de O (n3 + epsilon). Le coup d'envoi de la mise en pratique de cet algorithme a été donné par Fouquet, Gaudry et Harley qui ont proposé une extension au cas de p=2. Ce cas n'était pas traité dans l'article de Satoh bien qu'ayant le plus d'intérêt pratique (cette extension a été effectuée indépendamment par Skjernaa). Des expériences pratiques ont permis d'une part de pulvériser les précédents records (passant de 2000 à 8000 bits) et d'autre part de gagner un ordre de grandeur sur les temps de calcul pour les tailles utiles en cryptographie.

Des améliorations se sont succédées et les différentes alternatives sur le marché actuellement incluent l'algorithme de Vercauteren et al. qui réduit la complexité spatiale à O (n2), la méthode AGM inventée par Mestre et développée par Gaudry et Harley qui présente les mêmes avantages tout en améliorant les constantes, et dernièrement la méthode de Satoh-Skjernaa-Taguchi (SST) qui améliore la complexité théorique au prix de quelques précalculs. De nouveaux progrès sont encore en cours ou à venir (voir le récent record de Harley à 32000 bits).

Records du calcul du cardinal d'une courbe elliptique dans F2n
taille Qui Quand Méthode
300 RL-FM ??/09/94 SEA
400 RL-FM 28/09/94 SEA
500 RL-FM 18/10/94 SEA
601 RL-FM 27/12/94 SEA
701 RL-FM 10/03/95 SEA
1009 RL-FM 31/07/95 SEA
1301 RL-FM ??/04/96 SEA
1663 RL-Joux 19/06/98 SEA
1999 Vercauteren 17/10/99 SEA
3001 Fouquet-Gaudry-Harley 10/05/2000 Satoh-FGH
8009 Fouquet-Gaudry-Harley 05/10/2000 Satoh-FGH
16001 Harley ??/??/2001 AGM
32003 Harley 20/08/02 p-adique
Pour en savoir plus:
[Schoof85]
R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44:483-494, 1985.

Courbes elliptiques à multiplication complexe

La théorie de la multiplication complexe fournit une alternative aux algorithmes de calcul du cardinal, car elle permet de construire sur mesure des courbes dont le cardinal est connu d'avance. Les algorithmes qui en ressortent sont au cœur des preuves de primalité d'ECPP. Il servent également à la construction de cryptosystèmes elliptiques. Notre équipe a fait de nombreuses contributions dans ce domaine.

Pour en savoir plus:
voir les publications de l'équipe