Factorisation par courbes elliptiques
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 :
On suppose qu'on a un entier n à factoriser, dont un facteur premier p est tel que p-1 est puissance de petits nombres premiers. On choisit K un entier assez petit, et a un autre entier. Avec de bonnes chances, (p-1) divise K! (factorielle K). D'après le petit théorème de Fermat, aK!=1 mod p. On a donc aK!-1=rp, et le pgcd de n et aK!-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 4a3+27b2 soit premier avec n. Si en les prenant au hasard ce n'est pas le cas, c'est encore mieux car pgcd(4a3+27b2,n) donne un diviseur strict de n. Remarquons que, puisque 4a3+27b2 est premier avec n, il est premier avec p et est inversible dans Z/pZ. L'équation y2=x3+ax+b définit une une courbe elliptique sur Z/pZ, 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 y2=x3+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=210385674...
- 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, 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=0 (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.