Courbes elliptiques, Cryptographie à clés publiques et Protocoles d’échange de clés

Courbes elliptiques, Cryptographie à clés publiques et Protocoles d’échange de clés

Courbes elliptiques 

 Généralités sur les courbes elliptiques

 Introduites par Miller et Koblitz [25, 32] en 1987, les courbes elliptiques connaissent un essor considérable depuis leur utilisation dans la cryptographie. Reposant sur le problème du logarithme discret, la cryptographie sur les courbes elliptiques appliquées requiert, à niveau de sécurité équivalent, des clés bien plus petites que RSA (une clé de 160 bits est aussi robuste qu’une clé RSA de 1024 bits), celui-là étant donc plus adapté à des environnements à puissance réduite (tels que les cartes à puce). Pour de plus amples informations voir les livres et les articles suivants : – Silverman [42] – Hand book hyper elliptic curves[3] – Courbes d’Edwards (Edwards curves) [16, 5] – Huff curves 

 Notions de base Espace affine

Soit K un corps et K sa clôture algébrique. L’espace affine de dimension n est l’ensemble des points A n (K) = {P = (a1, · · ·, an), ai ∈ K}. L’ensemble des points rationnels est A n (K) = {P = (a1, · · ·, an), ai ∈ K}. Ensemble algébrique affine On note K[X1, · · ·, Xn] l’anneau des polynômes à n variables à coefficients dans K. – Si I est un idéal de K[X1, · · ·, Xn], alors le sous-ensemble de A n (K) donné par CI = {P ∈ A n /f(P) = 0, ∀f ∈ I} est appelé ensemble algébrique défini par I. 11 – Si C ⊆ A n (K) est un ensemble algébrique affine, son idéal est I(C) = {f ∈ K(X1, · · ·, Xn) /f(P) = 0, ∀P ∈ C}. – On dit qu’un ensemble algébrique C est défini sur K si son idéal est engendré par des polynômes de K[X]. – Un ensemble algébrique C est une variété si son idéal I(C) est premier. – Si C est une variété alors l’anneau des coordonnées de C est K[C] = K[X1,···,Xn] I(C) – L’anneau des coordonnées K[C] est intègre et son corps des fractions, noté K(C), est appelé le corps des fractions de C. – La dimension d’une variété C, est le degré de transcendance de l’extension de corps de K(C) sur K. – En particulier si C est donné par H(X1, · · ·, Xn) = 0 avec H(X1, · · ·, Xn) un polynôme irréductible dans K (c’est-à-dire absolument irréductible dans K), alors C est une variété affine de dimension n − 1. NB : Dans la suite on considère des variétés affines de dimension 1 en définissant une variété C par C : H(x, y) = 0 où H(x, y) est polynôme irréductible dans K. Espace projectif Un espace projectif sur K, noté P n ou P n (K), est l’ensemble des points (n + 1)−uplets (X0, · · ·, Xn) ∈ A n+1 tel qu’au moins un Xi est non nul, modulo la relation d’équivalence donnée par (X0, · · ·, Xn) ∼ (Y0, · · ·, Yn) s’il existe un λ ∈ K ∗ avec Xi = λYi pour tout i. Une classe d’équivalence {(λX0, · · ·, λXn), λ ∈ K ∗ } est notée [X0, · · ·, Xn] et X0, · · ·, Xn sont appelés coordonnées homogènes pour les points correspondants dans P n . L’ensemble des points K−rationnels dans P n est l’ensemble P n (K) = {[X0, · · ·, Xn] ∈ P n : pour tout Xi ∈ K} Ensemble algébrique projectif – Soit P = [X0, · · ·, Xn] ∈ P n (K). Le corps minimal de définition pour P (sur K), noté K(P), est le corps K(P) = K(X0/Xi , · · ·, Xn/Xi) pour tout Xi 6= 0. c’est-à-dire la plus petite extension de corps contenant K et les valeurs Xj/Xi , 0 ≤ j ≤ n, Xi 6= 0. 12 – Un polynôme f ∈ K[X] = K[X0, · · ·, Xn] est de degré homogène d si f(λX0, · · ·, λXn) = λ d f(X0, · · ·, Xn) pour tout λ ∈ K. Un idéal I ⊂ K[X] est homogène s’il est généré par des polynômes homogènes. Pour chaque idéal homogène I, on associe un sous-ensemble de P n , VI = {P ∈ P n : f(P) = 0 pour tout f ∈ I}, I homogène. – Un ensemble algébrique (projectif) est tout ensemble de la forme VI . Si V est un ensemble algébrique projectif, l’idéal (homogène) de V , noté I(V ), est l’idéal dans K[X] donné par I(V ) = {f ∈ K[X] : f est homogène et f(P) = 0 pour tout P ∈ V }. Points infinis A toute variété affine W, on peut associer une et une seule variété projective V . Les points infinis de W sont les points de V qui ne sont pas sur W. Exemples – Si on a une variété affine donnée par H(x, y) = 0, on peut avoir la version projective en faisant le changement : x = X Z , y = Y Z puis réduire en supprimant les dénominateurs. – Si on a une variété projective H(X, Y, Z) = 0, on peut avoir la version affine en posant Z = 1. – Pour trouver les points infinis, il suffit de résoudre H(X, Y, Z) = 0 en posant Z = 0 Singularité Une courbe C de dimension 1 sur K admet une partie affine qui peut être représentée comme un polynôme H(x, y) sur K[x, y] et alors, la partie affine de la courbe devient H(x, y) = 0. Si la courbe « affine » est définie par H(x, y) = 0, alors : la courbe  C est non singulière ou lisse signifie que le système :   H(x, y) = 0, (1) ; ∂H(x, y) ∂x = 0, (2) ; ∂H(x, y) ∂y = 0, (3). n’a pas de solutions dans K. Le résultat se généralise aisément à n variables. Genre Soit C une courbe non-singulière sur un corps K, une équation de Weierstrass de C est un modèle affine donné par la forme : H(x, y) = y 2 + yh(x) − f(x) = 0 13 où f, h sont des polynômes dans K[x], f est unitaire et deg(h) ≤ ⌊(deg(f) − 1)/2⌋ où ⌊a⌋ = partie entière de a. Notez que si deg(f) = 2g + 1 ou deg(f) = 2g + 2, alors deg(h) ≤ g, g est un entier naturel non nul. L’entier g est unique et est un invariant de la courbe C. Dans le cas général, il est donnée par le théorème de Riemann-Roch et est appelé genre de la courbe (voir Silvermann [42], Hank Book [3]). Pour une courbe elliptique en forme de Weierstrass, on a h(x) = a1x + a3 et f(x) = x 3 + a2x 2 + a4x + a6 et donc le genre est g = 1. Points rationnels L’ensemble des points K−rationnels de la courbe C est défini par l’ensemble des points : C(K) = {(x, y) ∈ K × K, /H(x, y) = 0} ∪ S∞ où S∞ est l’ensemble des points infinis. Equivalence birationnelle Pour étudier les isomorphismes entre les courbes et plus généralement entre les variétés, nous avons besoin d’une fonction birationnelle que nous utiliserons. Avant de la définir, nous rappelons qu’un morphisme entre deux variétés est une fonction qui est compatible avec la structure de variété. Soient A et B deux variétés sur un corps K, un morphisme birationnel de A à B est un morphisme ψ : A −→ B avec un sous ensemble ouvert U dense dans B tel que ψ −1 (U) −→ U est un isomorphisme (voir Silverman [42]). 

Premières propriétés et lois de groupe

 Une courbe projective définie sur un corps K qui est non singulière et irréductible sur la clôture algébrique K de K, de genre 1 et qui a au moins un point K−rationnel, est appelée courbe elliptique sur K. Définition 1.1.2. . Une courbe elliptique E sur un corps K notée par E/K est donnée par l’équation de Weierstrass E : y 2 + a1xy + a3y = x 3 + a2x 2 + a4x + a6 (1) où les coefficients a1, a2, a3, a4, a6 ∈ K sont tels que pour tout point (x1, y1) avec des coordonnées dans K satisfaisant (1), les dérivées partielles 2y1+a1x1+a3 et 3x 2 1+2a2x1+a4−a1y1 ne s’annulent pas simultanément. La dernière condition indique qu’une courbe elliptique est non-singulière (c’est-à-dire lisse). Un point, sur une courbe, est dit singulier si les deux dérivés partielles s’annulent. Pour une représentation plus courte, nous regroupons les coefficients dans (1) sous la forme suivante : E : y 2+h(x)y = f(x), et les données h(x) et f(x) ∈ K[x], deg(h) ≤ 1, deg(f) = 3 avec f unitaire. 14 La régularité de la condition peut aussi être exprimée plus intrinsèquement. En effet, soit b2 = a 2 1 + 4a2, b4 = a1a3 + 2a4, b6 = a 2 3 + 4a6, b8 = a 2 1 a6 − a1a3a4 + 4a2a6 + a2a 2 3 − a 2 4 En caractéristique impaire, la transformation y 7→ y − (a1x + a3)/2 mène à une courbe isomorphique donnée par y 2 = x 3 + b2 4 x 2 + b4 2 x + b6 4 (2). Exemple d’un schéma d’une courbe elliptique sur R : y 2 = x 3 − 6x 1 2 3 4 −1 −2 −3 −4 −4 −3 −2 −1 1 2 3 4 5 6 Le polynôme cubique précédent admet seulement des racines simples sur la clôture algébrique K si et seulement si son déterminant est non nul. L’équation du déterminant est par conséquent utile pour déterminer si (2) est une courbe elliptique ou non. En plus, il est également approprié pour les corps de caractéristique 2. Définition 1.1.3. Soit E une courbe définie sur K par (1) et soient les coefficients b2, b4, b6 et b8 définis comme précédemment. Le discriminant de la courbe E noté par ∆ satisfait ∆ = −b 2 2 b8 − 8b 3 4 − 27b 2 6 + 9b2b4b6. La courbe E est non-singulière , et ainsi est une courbe elliptique, si et seulement si ∆ est non nul. Dans ce cas, nous définissons le j − invariant de E par j(E) = (b 2 2 − 24b4) 3/∆. Le j − invariant permet de classer les courbes par classe d’isomorphismes. Pour additionner deux points P = (x1, y1) et Q = (x2, y2), en général on trace une droite les reliant. Il existe un troisième point d’intersection. Le symétrique de ce point par rapport à l’axe des abscisses donne la somme de P et Q notée P ⊕ Q. La même construction peut être appliquée 15 à un point double où la droite qui relie les points est remplacée par la tangente à P. On appelle le conjugué d’un point P, son symétrique par rapport à l’axe des abscisses. Soient P = (x1, y1) et Q = (x2, y2) deux points d’une courbe elliptique E, alors : – si P = (x1, y1) et Q = (x2, y2) sont distincts et non conjugués (c’est à dire P 6= Q et P 6= Q) alors la droite (P Q) coupe la courbe E en un unique troisième point R = (x3, y3) et la somme de P = (x1, y1) et Q = (x2, y2) est le conjugué de R = (x3, y3) : P ⊕ Q = R. – Si P = Q, on considère la droite tangente en P à la courbe E au lieu de la droite (P Q). Supposons P 6= Q avec (x1 6= x2) comme précédemment et calculons les coordonnées de R = P ⊕ Q = (x3, y3). La droite d’intersection admet comme pente λ = y1 − y2 x1 − x2 et passe à travers P. Son équation est ainsi donnée par : y = λx + x1y2 − x2y1 x1 − x2 . Nous appelons le terme constant par µ et remarquons que µ = y1 − λx1. Les points d’intersection avec la courbe sont obtenus en égalisant la droite et la courbe : (λx + µ) 2 + (a1x + a3)(λx + µ) = x 3 + a2x 2 + a4x + a6. Ceci conduit à l’équation r(x) = 0 où r(x) = x 3 + (a2 − λ 2 − a1λ)x 2 + (a4 − 2λµ − a3λ − a1µ)x + a6 − µ 2 − a3µ. Nous connaissons déjà deux racines de r(x), correspondant aux abscisses des deux autres points. Puisque r(x) = (x − x1)(x − x2)(x − x3) on a λ 2 + a1λ − a2 = x1 + x2 + x3. Comme x1, x2 sont définis sur K alors il existe de même x3 et y3 = λx3 + µ. L’inflexion à l’axe des abscisses peut être traduite à la condition que le second point ait les mêmes coordonnées et ainsi satisfait à l’équation de la courbe. Nous observons que si P = (x1, y1) est sur la courbe alors il en est de même que (x1, −y1 − a1x1 − a3), qui correspond à −P, puisque le point à l’infini est l’élément neutre pour cette loi. Par conséquent, nous obtenons y3 = −λx3 − µ − a1x3 − a3. Le dédoublement de P = (x1, y1) fonctionne aussi de même avec la pente obtenue par une dérivation implicite. D’où nous avons P ⊕ Q = (x3, y3) et −P = (x1, −y1 − a1x1 − a3), P ⊕ Q = (λ 2 + a1λ − a2 − x1 − x2, λ(x1 − x3) − y1 − a1x3 − a3), où λ =    y1 − y2 x1 − x2 si P 6= ±Q 3x 2 1 + 2a2x1 + a4 − a1y1 2y1 + a1x1 + a3 si P = Q 16 Il découle immédiatement de cette description illustrée que cette loi est commutative, admet le point à l’infini comme élément neutre et que l’inverse de (x1, y1) est donné par (x1, −y1 −a1x1 −a3). L’associativité beaucoup plus délicate peut être montrée en appliquant seulement la loi de groupe (voir Silverman [42]). 

 Courbes elliptiques sur F2m

 Nous rappelons des cas particuliers des courbes elliptiques binaires qui nous intéresserons par la suite. Définition 1.1.4. Soit K = F2m un corps, une courbe elliptique binaire est une équation de Weierstrass de la forme E/F2m : y 2 + xy = x 3 + a2x 2 + a6, (avec a6 6= 0) où O = (0 : 1 : 0) est le point à l’infini et l’inverse d’un point P0 = (x0, y0) ∈ E\{O} est −P0 = (x0, y0 + x0). Lois de groupe (formules pour le doublement et l’addition) : Soient P1 = (x1, y1) et P2 = (x2, y2), l’addition de P1 + P2 = P3 = (x3, y3) avec    x3 = λ 2 + λ + x1 + x2 + a2, y3 = (x1 + x3)λ + x3 + y1. où    λ = y1 + y2 x1 + x2 si P1 6= P2, λ = y1 x1 + x1 si P1 = P2. 1.

 Multiplication scalaire

 Supposons n ∈ N\{0} et notons la multiplication scalaire par n sur E par [n], ou [n]E pour éviter la confusion. C’est-à-dire, [n] : E → E P 7→ [n]P = P ⊕ P ⊕ · · · ⊕ P | {z } n fois Cette définition est prolongée trivialement à tout n ∈ Z, en prenant [0]P = P∞ et [n]P = [−n](−P) pour n < 0. 1.1.5 Points rationnels sur une courbe elliptique Soit E une courbe elliptique définie sur K. Les points de E à coordonnées dans K forment l’ensemble des points K − rationnels de E notés E(K). Nous avons E(K) = {(x1, y1) ∈ K2 |y 2 1 + a1x1y1 + a3y1 = x 3 1 + a2x 2 1 + a4x1 + a6} ∪ {P∞}. 

Points de torsion 

Définition 1.1.5. . Soient E/K une courbe elliptique, n ∈ Z. Le noyau de [n], noté par E[n], satisfait E[n] = {P ∈ E(K)|[n]P = P∞}. Un élément P ∈ E[n] est appelé point n − torsion. Théorème 1.1.1. . Soit E une courbe elliptique définie sur K. Si la caractéristique de K est nulle ou premier à n alors E[n] ≃ Z/nZ × Z/nZ. Sinon, lorsque char(K) = p et n = p r , alors E[p r ] = {P∞}, pour tout r > 1 ou E[p r ] ≃ Z/prZ, pour tout r > 1. 1.1.7 Isogénies Définition 1.1.6. . Deux courbes E/K et E′/K sont isogènes sur K s’il existe un morphisme ψ : E → E′ (avec les coefficients dans K) envoyant l’élément neutre de E sur l’élément neutre de E′ . De cette propriété simple, il est possible de montrer que ψ est un homomorphisme de groupe de E(K) dans E′ (K). Proposition 1.1.1. . Soit Fq, un corps fini à q éléments. Deux courbes elliptiques E et E′ définies sur Fq sont isogènes sur Fq si et seulement si |E(Fq)| = |E′ (Fq)| (même cardinal). 

 Endomorphismes

 La multiplication par n est un endomorphisme de la courbe E pour tout n ∈ Z. L’ensemble de tous les endomorphismes de E définis sur K sera noté par EndK(E) ou plus simplement par End(E). Soit Fq, un corps fini à q éléments, q = p r avec p premier. Soit E une courbe elliptique sur Fq. L’automorphisme de Frobenius de Fq s’étend à tous les points de la courbe en renvoyant P∞ à lui-même et P = (x1, y1) à φq(P) = (x q 1 , y q 1 ). On peut facilement vérifier que le point φq(P) est aussi un point sur la courbe sans tenir compte du corps de définition de P. D’où, φq est un endomorphisme de E, appelé endomorphisme de Frobenius de E/Fq. Il est différent de [n] pour tout n ∈ Z. 

 Cardinalité 

Soit Fq, un corps fini à q éléments. La cardinalité d’une courbe elliptique E sur Fq, i.e., le nombre de points Fq − rationnels, est un aspect important pour la sécurité des cryptosystèmes construits sur E(Fq). 18 Théorème 1.1.2. (Hasse, Weil). Soit E une courbe elliptique définie sur Fq. Alors, il existe t tel que |E(Fq)| = q + 1 − t avec |t| ≤ 2 √ q. Définition 1.1.7. (trace d’un endomorphisme). La trace d’un endomorphisme est la trace de la matrice associée à cet endomorphisme dans une base quelconque. Remarque 1.1.1. . (i) L’entier t est la trace de l’endomorphisme de Frobenius. (ii) Pour tout entier t ∈ [−2 √p, 2 √p], il existe au moins une courbe elliptique E définie sur Fp de cardinalité p + 1 − t. Théorème 1.1.3. . Soit q = p r . Il existe une courbe elliptique E définie sur Fq avec |E(Fq)| = q + 1 − t si et seulement si une des conditions suivantes est vérifiée : 1. t 6≡ 0 mod p et t 2 ≤ 4q. 2. r est impair soit (i) t = 0 ou (ii) p = 2 et t 2 = 2q ou (iii) p = 3 et t 2 = 3q. 3. r est pair et soit (i) t 2 = 4q ou (ii) p 6≡ 1( mod 3) et t 2 = q ou (iii) p 6≡ 1( mod 4) et t = 0.