Wiki du cours

Rédacteur: Léo MORINO

A traiter [edit]

• Motivation [1]
• Coordonnées projectives [1], [2]
• Le modèle de Jacobi [1], [2]
• Multiplication par des entiers par doublements successifs [3].

Motivation [edit]

Maintenant que nous venons de définir une loi de groupe pour trouver des points sur une courbe elliptique donnée, on souhaiterait calculer ces points très rapidement ( car des applications en cryptographie requièrent fréquemment de calculer des points dont les coordonnées sont des entiers très grands.)

Pour rappel, si on prend E une courbe elliptique définie par une équation de Weierstrass avec \(P_1=(x_1,y_1)\) et \(P_2=(x_2,y_2)\) deux points différents de l'infini. Alors, on définit \((x_3,y_3)=P_3=P_1+P_2\) par :

• \( x_3 = m^2 - x_1 - x_2\), \(y_3 = m(x_1-x_3) - y_1\) où \(m = \frac{y_2-y_1}{x_2-x_1}\) si \(x_1 \ne x_2 \)
• \(x_3 = m^2 -2 x_1\), \(y_3 = m(x_1-x_3) - y_1\) ou \(m = \frac{3x_1^2 + A}{2y_1}\) si \(P_1=P_2\) et \(y_1 \ne 0\)

On voit que pour calculer \(P_3\), cela nous coûte 1 "carré" (noté S par la suite), 2 multiplications (noté M) et \(1\) inversion (noté I) pour le premier cas et 2S + 2M + I pour le deuxième cas. Malheureusement, l'inversion qui semble simple demande 9 à 40 fois plus de temps de calcul qu'une multiplication(I >> 20M) (l'addition, la soustraction et la multiplication par une constante sont négligeables et le carré est du même ordre que la multiplication). Ainsi, lorsqu'on travaillera avec de grands nombres, nous aurons une perte de temps significative. Nous allons donc dans les prochaines parties proposer des méthodes pour contourner le problème lié a l'inversion.

Coordonnées projectives [edit]

Une méthode naturelle est de travailler avec l'espace projectif. En effet, si un triplet \((x:y:z)\) est solution de \( y^2z = x^3 + Axz^2 + Bz^3\) alors en divisant par \(z \ne 0\), \((\frac{x}{z}:\frac{y}{z}:1)\) lui est équivalent et \((\frac{x}{z},\frac{y}{z})\) est un point de notre courbe elliptique. Maintenant, on aimerait obtenir une expression de la loi de groupe pour les coordonnées projectives.

Proposition: Soit \(P_i = (x_i:y_i:z_i)\) pour tout \(i \in {1,2}\) des points de notre courbe elliptique d'équation \(y^2 =x^3 + Axz^2 + Bz^3\). Alors,

\((x_3:y_3:z_3)=P_3=P_1+P_2\)

où \(x_3, y_3\) et \(z_3\) sont définis comme il suit:

Si \(P_1 \ne \pm P_2\) alors

• \(u = y_2z_1 - y_1z_2\), \(v = x_2z_1- x_1z_2\), \(w= u^2z_1z_2 - v^3 - 2v^2x_1z_2\)
• \(x_3 = vw\), \(y_3 = u(v^2x_1z_2 - w) - v^3y_1z_2\), et \(z_3=v^3z_1z_2\)

Si \(P_1 = P_2\) alors

• \(t = Az_1^2 + 3x_1^2\), \(u =y_1z_1\), \(v = ux_1y_1\), \(w = t^2 - 8v\)
• \(x_3 = 2uw\), \(y_3 = t(4v - w) - 8y_1^2u^2\), et \(z_3=8u^3\)

Si \(P_1 = -P_2\) alors \(P_1 +P_2 = \infty \)

Maintenant, nous allons compter les opérations nécessaires pour obtenir nos points projectifs. nous allons regarder de plus près le cas \(P_1 \ne \pm P_2\) (Nous ne détaillerons pas pour le cas point double mais nous donnerons le résultat à la fin du paragraphe). Pour u et v, on compte 2M pour chacun. Pour w, ça demande un plus de détails. Pour le premier membre, on a 1S et 2M. Ensuite pour \(v^3\), nous allons le décomposer en \(v^2v\) ce qui demande 1S et 1M. Pour le dernier, nous venons tout juste de calculer \(v^2\) et \(x_1z_2\) a été calculé dans v. Donc, on a seulement besoin de 1M. Ainsi, w demande 2S et 4M. Nous en sommes à 8M et 2S mais il nous reste encore les opérations pour calculer les coordonnées \(x_3\), \(y_3\), et \(z_3\). Pour \(x_3\), on a seulement 1M. Pour \(z_3\), on a 1M car nous avons déjà calculer \(z_1z_2\) et \(v^3\)dans w donc il n'y a pas besoin de les recalculer et seul la multiplication entre ces deux membres est nécessaire. Et pour finir, \(y_3\) demande à être regardé de plus près. A première vue, son premier membre demande 2M mais en réalité si on calcule \(v^2x_1z_2 - w\) explicitement, on obtient \(-u^2z_1z_2 + v^3 + 3v^2x_1z_2\). Chaque terme a été calculé ( à constante près) dans w. Ainsi, on a seulement 1M. Pour le deuxième terme de \(y_3\), on 1M par les mêmes arguments que précédemment. On obtient donc 12M et 2S contre 1I, 2M et 1S. Même si le nombre de M a fortement augmenté, nous avons pu éviter de faire une inversion!! De plus, avec I>>20M, cette méthode est donc plus rapide. Pour le cas point double, on peut compter 7M et 5S.

Le modèle de Jacobi [edit]

Cette fois, au lieu de considérer le plan affine \((\frac{x}{z},\frac{y}{z})\), nous allons nous intéresser au plan affine \((\frac{x}{z^2}\frac{y}{z^3})\). La courbe elliptique devient \(y^2 = x^3 + Axz^4 + Bz^6\). Le point infini a pour coordonnées \((1:1:0)\). On définit notre addition entre deux points projectifs comme suit:

Proposition: Soit \(P_i = (x_i:y_i:z_i)\) pour tout \(i \in {1,2}\) des poins de notre courbe elliptique d'équation \(y^2z =x^3 + Axz^4 + Bz^6\). Alors,

\((x_3:y_3:z_3)=P_3=P_1+P_2\)

où \(x_3, y_3\) et \(z_3\) sont définis comme il suit:

Si \(P_1 \ne \pm P_2\) alors

• \(r=x_1z_2^2\), \(s=x_2z_1^2\), \(t=y_1z_2^3\), \(u = y_2z_1^3\), \(v =s-r\), \(w =u-t\)
• \(x_3 = -v^3 - 2rv^2 +w^2\), \(y_3 =-tv^3 + (rv^2 - x_3)w\), et \(z_3=vz_1z_2\)

Si \(P_1 = P_2\) alors

• \(v = 4x_1y_1^2\), \(w =3x_1^2 + Az_1^4\)
• \(x_3 = -2v +w^2\), \(y_3 = -8y_1^4 + (v-x_3)w\), et \(z_3=2y_1z_1\)

Si \(P_1 = -P_2\) alors \(P_1 +P_2 = \infty \)

On peut compter qu'il y a 12M et 4S pour le cas \(P_1 \ne \pm P_2\), ce qui est 2S de plus que la méthode précédente. Cependant, là où cette méthode devient intéressante, c'est pour le cas point double. On compte 3M et 6S. C'est 3 opérations de moins.

Remarque: De plus, si \(A=-3\) alors on peut factoriser w et on obtient \(w =3(x_1^2 -z_1^4)=3(x_1 +z_1^2)(x1 -z_1^2)\). Ainsi, on a 1S et 1M au lieu de 3S.

Multiplication par des entiers par doublements successifs. [edit]

Maintenant, on va s'intéresser au cas où on souhaite additionner plusieurs fois le même point. C'est-à-dire si on prend un point P de notre courbe elliptique et k un entier positif alors on souhaite calculer \(kP= P+P+...+P\), k fois. Si \(k<0\) alors \(kP = (-P)+(-P)+...+(-P)\), \(|k|\) fois. La méthode utilisé pour calculer ces points de façon judicieuse est expliqué par les étapes ci-dessus:

• Méthodes des doublements successifs

Soit k un entier positif et P un point de la courbe elliptique donnée. Les étapes suivantes permettent de calculer kP.

• 1. On commence par poser: \(a=k\), \(B=\infty\) et \(C = P\).
• 2. Si a est pair alors on pose \(a=\frac{a}{2}\), \(B=B\) et \(C=2C\).
• 3. Si a est impair alors on pose \(a=a-1\), \(B=B+C\) et \(C=C\).
• 4. Si \(a=0\) alors renvoyer B

Voici un exemple pour mieux comprendre les différentes étapes. Nous souhaitons calculer 23P, voici les étapes a suivre:

• Tout d'abord, nous identifions nos variables: \(a=23\), \(B=\infty\) et \(C=P\)
• Nous avons a impair donc \(a=22\), \(B=\infty+C=\infty+P=P\), et \(C=C=P\)
• Nous avons a pair donc \(a=11\), \(B=B=P\), et \(C=2C=C+C=P + P=2P\)
• Nous avons a impair donc \(a=10\), \(B=B +C=P +2P\), et \(C=C=2P\)
• Nous avons a pair donc \(a=5\), \(B=B=P+2P\), et \(C=2C=2P +2P=4P\)
• Nous avons a impair donc \(a=4\), \(B=B+C=P+2P+4P\), et \(C=C=4P\)
• Nous avons a pair donc \(a=2\), \(B=B=P+2P+4P\), et \(C=2C=4P+4P=8P\)
• Nous avons a pair donc \(a=1\), \(B=P+2P+4P\), et \(C=2C= 8P+8P=16P\)
• Nous avons a impair donc \(a=0\), \(B=B+C=P+2P+4P+16P\), et \(C=P\)
• Nous avons \(a=0\) donc on renvoie \(B=P+2P+4P+16P=23P\)

Nous remarquons qu'au lieu d'effectuer "bêtement" 22 opérations, il nous suffit de 7 opérations.

Références [edit]

[1] Craig Costello, Pairings for beginners, Section 2.1.4.
[2] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 2.6.
[3] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 2.2.