Cryptographie!

Factorisation des entiers par les courbes elliptiques


Avant d'aborder cette lecture, il faut avoir lu cette page.

  Les courbes elliptiques permettent l'adoption de nouveaux cryptosystèmes. Mais elles mettent aussi en danger des cryptosystèmes existants, comme le RSA. Elles sont en effet à l'origine d'une méthode élégante de factorisation, due à H.W.Lenstra. Nous commençons par expliquer un algorithme qui n'a rien à voir avec les courbes elliptiques, mais qui est une bonne introduction à notre sujet...
Méthode $p-1$ de Pollard :

  La méthode $p-1$ de Pollard est une méthode efficace pour factoriser des entiers $n$ admettant un facteur premier $p$ tel que la décomposition en facteurs premiers de $p-1$ ne fait apparaitre que de petits nombres premiers. Supposons qu'on a un tel entier $n$, et que tous les facteurs premiers de $p-1$ sont inférieurs ou égaux à $K$. On choisit également $a$ un autre entier. Alors, $p-1$ divise $K!$ (on suppose aussi que tous les facteurs premiers de $p-1$ sont simples). D'après le petit théorème de Fermat, $a^{K!}\equiv 1[p]$. En particulier, $p$ divise $a^{K!}-1$ et $n$, et donc le pgcd de $n$ et de $a^{K!}-1$ donne un diviseur strict de $n$.

  Bien sûr, cet algorithme a peu de chances de fonctionner, car il n'est pas fréquent que $p-1$ soit puissance de petits nombres premiers, d'autant que, dans les cryptosystèmes comme RSA, on fabrique l'entier $n$, et on peut s'arranger pour que n ne vérifie pas cette condition.

Factorisation par courbes elliptiques :

  L'idée de cet algorithme est dû à Lenstra. On suppose que l'on doit factoriser un entier $n$ (donné). On note $p$ un diviseur premier de n (que l'on ne connait pas!).

  • Etape 1 : choix d'une courbe elliptique. On choisit $a$ et $b$ tel que $4a^3+27b^2$ soit premier avec $n$. Si en les prenant au hasard ce n'est pas le cas, c'est encore mieux car $\textrm{pgcd}(4a^3+27b^2,n)$ donne un diviseur strict de $n$. Remarquons que, puisque $4a^3+27b^2$ est premier avec $n$, il est premier avec $p$ et est inversible dans $\mathbb Z/p\mathbb Z$. L'équation $y^2=x^3+ax=b$ définit une une courbe elliptique sur $\mathbb Z/p\mathbb Z$, que nous noterons $E(a,b,p)$ (signalons que, puisqu'on ne connait pas p, on ne connait pas cette courbe elliptique).
  • Etape 2 : choix d'un point sur la courbe elliptique. On trouve deux entiers $x$ et $y$ tels que $y^2=x^3+ax+b$. En particulier, $P(x,y)$ est un point de la courbe elliptique $E(a,b,p)$.
  • Etape 3 : choix d'un entier auxiliaire. On choisit $k$ un entier pas très grand, mais qui est produit de petits facteurs premiers à des exposants déjà élevés. Par exemple, $k=2^{10}3^85^67^4$.
  • Etape 4 : calcul sur les courbes elliptiques. On calcule les coordonnées du point $kP$, en utilisant les formules classiques, les calculs s'effectuant modulo $n$. Ces calculs font intervenir des divisions, et ceci n'est pas toujours possible modulo $n$ : il faut que le dénominateur $d$ soit premier avec n. Mais ce qu'on espère, c'est que ce n'est pas le cas! En effet, si $d$ n'est pas premier avec $n$, $\textrm{pgcd}(d,n)$ donne un diviseur premier de $n$. Si on a pu mener les calculs jusqu'au bout, on recommence à l'étape 1, en changeant de courbe elliptique.
Pourquoi ça marche?

  Si une courbe elliptique $E(a,b,p)$ ($p$ diviseur de $n$) comporte $m$ points, tel que $m$ est produit de petits facteurs premiers, alors $m|k$. $k$ est donc un multiple du cardinal du groupe de la courbe elliptique, et d'après le théorème de Lagrange, $kP=O$ (point à l'infini). Dans ce cas, dans le calcul de $kP$, une erreur (=division par 0) va se produire, et on va trouver un diviseur de $n$.

  Dans la méthode de Pollard, il fallait supposer qu'un diviseur $p$ soit tel que $p-1$ soit puissance de petits nombres premiers. Désormais, il suffit que ce soit le cas pour le cardinal d'une courbe elliptique $E(a,b,p)$. Comme on peut choisir librement $a$ et $b$, il est bien possible que cela se produise. D'ailleurs, un théorème mathématique garantit que cela arrive forcément pour un bon choix de $a$ et $b$.

  Dans la pratique, pour factoriser les entiers qui interviennent dans le RSA, l'algorithme est un peu moins performant que le crible quadratique, mais il est très efficace quand il s'agit de factoriser un entier qui a un facteur premier relativement petit.
Consulter aussi