Brevet FR3071081A1 — publié le 20190315

MÉTHODE CRYPTOGRAPHIQUE SUR COURBES ELLIPTIQUES BINAIRES D'EDWARDS DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne de manière générale le domaine de la cryptographie et plus particulièrement de la cryptographie sur courbes elliptiques. Elle trouve notamment application dans le domaine de l'Internet des Objets ou loT (Internet of Things). ÉTAT DE LA TECHNIQUE ANTÉRIEURE La cryptographie sur courbes elliptiques ou ECC (Elliptic Curve Cryptography) est une technique de chiffrement économe en termes de longueur de clé et de temps de calcul, ce qui rend son utilisation particulièrement attractive dans les noeuds de l'Internet des Objets, pauvres en ressources par nature. La cryptographie sur courbes elliptiques exploite la difficulté de résoudre le problème du logarithme discret ou DLP (Discrete Logarithm Problem) sur un groupe cyclique fini. Si l'on considère par exemple le groupe multiplicatif d'un corps fini Fq (on notera dans la suite Fq ou GF( q ) un corps fini à q=pni éléments où p est un nombre premier et m est un entier non nul), ce groupe est cyclique et le problème du logarithme discret de z dans la base x peut être défini comme la recherche du plus petit entier k tel que xi' = z où x,z E F: . De manière générale, une courbe elliptique E sur un corps k est définie à partir d'une cubique à deux variables x, y prenant leurs valeurs dans ce 2 corps, à savoir l'ensemble des points (couples d'éléments de k ) vérifiant l'équation de Weierstrass: y2 ± aixy+ a3y = x3 ± a2 x2 ± a4x + a6 (1) 5 où ai,...,a4,a6 E k. L'ensemble de ces points, complété par un point Q, dit point à l'infini, définit une courbe elliptique sur le corps k , notée E(k). On construit une opération d'addition affine sur E(k) telle que E(k) munie de cette opération forme un groupe additif. Pour un point G appartenant à E(k), 10 l'ensemble des éléments £G avec £ entier est alors un sous-groupe cyclique de E(k). En pratique, la multiplication d'un point de E(k) par un scalaire (par exemple L), encore dénommée exponentiation par analogie avec un groupe multiplicatif, est décomposée en des opérations élémentaires de doublement (calcul de 2G) et d'addition, plus simples à effectuer. 15 Si l'on considère le cas d'un corps fini k = Fq , un cryptosystème sur courbe elliptique sur Fq est caractérisé par un ensemble de paramètres, (q,a1...,d4,a6,G,n,h), encore dénommés paramètres de domaine, où q, a1,...,a4,a6, sont des paramètres précédemment définis, G est un point ) 11 générateur, n est l'ordre de G dans le groupe additif E(Fq), h= E(Fq) le n 2 0 cofacteur de G dans ce groupe, E(Fq) estest l'ordre du groupe E(Fq) . Une clé privée d peut alors être choisie parmi les entiers [1,n-1], la clé publique correspondante étant donnée par les coordonnées Q=dG. La recherche de la clé privée à partir de la clé publique et du point générateur G, ou problème ECLDP (Elliptic Curve Discrete Logarithm Problem), est plus ardue que le 3 problème DLP sur les corps finis et, dans l'état actuel, impossible à résoudre dans un temps polynomial. On pourra trouver une présentation de la cryptographie sur courbes elliptiques dans l'ouvrage de D. Hankerson, A. Menezes et S. Vanstone intitulé 5 « Guide to Elliptic Curve Cryptography » publié en 2004 aux éditions Springer. En pratique, les courbes actuellement utilisées en cryptographie sur courbes elliptiques appartiennent à la famille des courbes de Weierstrass données par (1) où k est un corps fini Fp et p est un grand nombre premier, ou bien où k est un corps d'extension de F2, soit Fr, . Dans ce dernier cas, 10 l'équation de Weierstrass se réduit à : y2 ± xy = x3 +ax2+b (2) avec a,b E k . Pour des questions de commodité d'implémentation, on opte 15 généralement pour le corps d'extension binaire Fr (une division par 2 étant alors implémentée par un simple décalage). L'élément neutre de Ew(F p) ou de Ew(F2,') est un point à l'infini Q . La cryptographie sur courbes elliptiques est notamment utilisée dans la méthode de signature numérique ECDSA (Elliptic Curve Digital Signature 20 Algorithm), normalisée par le NIST (National Institute of Standards and Technology). Plus récemment, une nouvelle famille de courbes elliptiques, dites courbes d'Edwards a été introduite, ces courbes étant définies sur un corps Fp où p est un grand nombre premier : 25 x2 + y2 1 + dx2y2 (3) 4 avec d e F. . L'ensemble des points P appartenant à une courbe d'Edwards peut être muni d'une loi d'addition affine lui conférant une structure de groupe additif. Toutefois, les calculs dans Fp sont complexes à implémenter et leur protection contre les attaques par canaux auxiliaires s'avère délicate. Il convient de noter 5 que les courbes définies par (3) ne sont pas elliptiques sur un corps de caractéristique 2, autrement dit ne sont pas applicables à un corps d'extension binaire F2', . Pour remédier à ces inconvénients, une famille de courbes elliptiques sur un corps d'extension binaire Fr a été proposée dans l'article de D.J. Bernstein et 10 a/. intitulé « Binary Edwards Curves », Lecture Notes in Computer Science, vol. 514 LNCS, pp. 244-265, 2008, définie par : d 1(x + y) + d 2(x2 + y2 ) = xy + xy (x + y) + x2 y2 (4) 15 où d1, d2 eF2- avec d1 0 et d2 d12 + dl " Ces courbes sont encore connues sous leur acronyme « BEC ». L'addition affine de deux points Pi et P2 de coordonnées respectives (xl,y1) et (x2,y2) d'une BEC est un point P, de coordonnées (x3,y3), définies par : 20 x3 = di (xi + x2)+d2 (xi +y1)(x2 +y2)+(xl +x12)(x2(yi +y2 +1)-Fyiy2) di +(xl +x12)(x2 ±Y2) (5-1) y3 = di (y1 +y2)+d2 (xi -Fyi)(x2 +y2)+(yi + y12)(y2 (xi +x2 +0+ xix2) (5-2) di ± (YI ± Y12) ( x2 -F.Y2) 5 Le point P3 appartient à la courbe en question, les dénominateurs figurant en (5-1) et (5-2) ne pouvant être nuls en raison des conditions sur d1 et d2. L'opération d'addition affine confère à l'ensemble des points de la BEC, dont les coordonnées appartiennent à Fr , une structure de groupe additif, noté dans 5 la suite EBEC (F 2m) . On notera en outre le caractère symétrique en x et y de l'équation (4) et le fait que les expressions (5-1) et (5-2) se déduisent l'une de l'autre par cette symétrie. Ceci a pour conséquence que si un point P(x,y) appartient à EBEC (F 2m ), son symétrique PI (y,x) lui appartient également. On peut d'ailleurs 10 montrer à partir des expressions (4),(5-1) et (5-2) que P'+ P = 0, autrement dit que P' est l'inverse de P dans le groupe additif EBEC (F 2m) et que l'élément neutre de ce groupe n'est autre que le point neutre O de coordonnées (0,0). On peut en outre montrer que la courbe binaire d'Edwards est isomorphe (ou birationnellement équivalente) à une courbe de Weierstrass, le point neutre O de 15 la première correspondant au point infini Q de la seconde. On pourra trouver une introduction aux courbes binaires d'Edwards dans la thèse de B. Koziel initulée « Low-resource and fast elliptic curve implementations over Binary Edwards Curves », Rochester lnstitute of Technology, 2016. 20 Un cas particulier de courbe BEC permet de simplifier la multiplication d'un point par un scalaire. En effet, les expressions (5-1) et (5-2) nécessitent de nombreuses opérations (calculs de carrés, multiplications, et inversions notamment) dans le corps Fr . Lorsque d1 =d2 =d, la courbe BEC, alors notée E d se simplifie comme suit: 25 d (x + x2 + y+ y2) = xy+xy(x+ y)+ x2y2 = (x+ x2)(y+ y2) (6) 6 où d est tel que ,Zrt G Fr tel que d = t2 +t. On notera dans la suite Ed (F2m) le groupe additif E BEc (F 2m) lorsque la BEC est sous la forme (6). Dans ce cas, il est possible d'effectuer une addition différentielle, c'est à dire de calculer la somme 5 Q+P de deux points P,Q de Ed(F2m) à partir des coordonnées des points Q,P et de leur différence P-Q, comme décrit par exemple dans l'article de D.J. Bernstein précité. Toutes les courbes BEC ne présentent pas le même degré de sécurité vis- 10 à-vis d'attaques potentielles ni se prêtent à une implémentation de manière équivalente. L'article de D.J. Bernstein intitulé « Batch binary Edwards » publié dans Lecture Notes in Computer Science, vol. 5677 LNCS, pp. 317-336, 2009 énumère une liste de conditions à remplir pour qu'une méthode cryptographique sur une 15 courbe BEC simplifiée (c'est-à-dire définie par l'expression (6)) offre un niveau élevé de sécurité. Il est notamment préconisé de choisir un degré d'extension m égal à un nombre premier pour se prémunir contre les attaques dites GHS (Galbraith, Hess et Smart) et de choisir une courbe telle que l'ordre du groupe Ed (F2m) ainsi que l'ordre du groupe additif sur la tordue quadratique(quadratic 20 twist of the curve), Edi ' 4 ' , associée à la courbe Ed, soient chacun proches d'un nombre premier à un faible facteur multiplicatif près. De manière générale, on rappelle que la tordue quadratique d'une courbe elliptique E sur un corps k est une courbe elliptique isomorphe à E sur une clôture algébrique de k , c'est-à-dire une extension algébrique de k algébriquement close. 25 Toutefois, la courbe BEC sur le corps F22' proposée dans l'article « Batch binary Edwards » ne permet pas d'atteindre le niveau de sécurité de 128 bits préconisé par le NIST et n'est pas non plus optimisée en termes de rapidité de 7 calcul. On rappelle que le niveau de sécurité d'un chiffrement sur courbe 1 elliptique E(Fq) est défini comme ilo,g2 (E(Fq)) (taille de la courbe divisée par 2). L'objet de la présente demande est par conséquent de proposer une 5 méthode cryptographique sur courbe BEC qui présente un niveau de sécurité élevé, une rapidité de calcul supérieure à celle de l'état de la technique et qui se prête bien à une implémentation sur une architecture matérielle à 32 bits ou 64 bits. 10 EXPOSÉ DE L'INVENTION La présente invention est définie par une méthode cryptographique sur une courbe binaire d'Edwards définie par d(x+ x2 +y+y2)=(x + x2)(y+y2) dans le plan affine par un corps d'extension binaire F2,, =F2 [X] / (H(X)) où F2 [X] est l'anneau des polynôme à coefficients dans F2 et H(X) est un 15 polynôme irréductible de F2 [X] de degré m , le paramètre d de la courbe étant un élément de F2,, [t], l'ensemble des points de la courbe étant muni d'une loi lui conférant une structure de groupe additif, Ed(F2m), ladite méthode faisant appel à au moins une primitive cryptographique dans laquelle un entier k est transformé en kG où G est un point de Ed(F2,,), dit point générateur, dans 20 laquelle: pour une implémentation de ladite méthode au moyen d'une architecture matérielle 32 bits ou 64 bits, le corps d'extension binaire est l'un des corps suivants : F22' [t] = F2 [X]/(X257 ± X65 ± 1) ; 25 F2431 [t] = F2 [X]/(X431 + x303 ± x239 ± x111 ± ; 8 F248, [t] = F2 [X]e"' + X295 + Xl" + X" +1) ; F2569 [t]= F2 [X]/(X569 + x441 + x313 + x121 + ; et pour une implémentation au moyen d'une architecture matérielle 32 bits, le corps d'extension binaire pouvant être également choisi parmi : 5 F2223 [t] = F2 [X]/(X223 + X159 + 1) ; F247, [t] = F2 [X]/(X479 + X255 + 1) F2521 [t] = F2 [X]/(X521 + X489 + 1) ; le paramètre d de la courbe binaire d'Edwards sur chacun de ces corps d'extension binaire étant donné dans l'annexe. 10 Avantageusement, le paramètre d de la courbe binaire d'Edwards est donné par : pou r F2223 [t] : d_ t64 + t36 + t5 + 1 ; pour F2257 [t] . d_ t65 + t31 + t14 +1 . F2313 [t] . d-t"+t"+ `,28 , ' 1 I . pour 15 pour F243, [t] : d - t83 + t66 + t17 + 1- 1 I . F247, [t] : d = t73 + t29 + t3 + 1 . pour F2487 [t] : d_ t69 + t33 + t15 + 1 . pour F2,21 H : d-t66+t29+`,28 +1 . pour pour F2569 [t] : d_ t56 + t45 + t41 + 1 20 Ledit point générateur G, de coordonnées affines G Gy), est avantageusement choisi de manière à ce que sa coordonnée différentielle il; (G) = G' +Gy vérifie: - 9 pour F2223 [t] :142(G) t32 +1 ; 1 t192 F 257 [t] if (- G) pour 2 1 = t64 + 1 F 313 [t]w (G) pour 2 : t 64 + 1 pour F2' [t] : le(G) 5 F ', [t] 142(1 = t64 +1 G) pour 2 : F ', [t] 142(1 = t64 +1 G) pour 2 : 1 = t32 + 1 F 521 [t] if (- G) pour 2 : t 64 +1 F 569 [t] }V (- G) pour 2 : 10 De préférence, les coordonnées affines (Gx,Gy) du point générateur sont données, en notation hexadécimale, par : pour F222, [t] : 15 pour F22' [t] : pour F231, [t] : 1 1 1 o OT BRÈVE DESCRIPTION DES DESSINS D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture d'un mode de réalisation préférentiel de l'invention, fait en référence à la 5 Figure unique représentant de manière schématique un processus de sélection des paramètres d'une méthode cryptographique sur une courbe binaire d'Edwards selon un mode de réalisation de l'invention. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS 10 Nous considérons dans la suite une méthode cryptographique sur une courbe elliptique, la courbe elliptique étant une courbe binaire d'Edwards simplifiée Ed, c'est-à-dire dont les points vérifient la relation (6). L'ensemble des points de la courbe, dont les coordonnées appartiennent à Fr,, muni de la relation d'addition affine définie par (5-1) et (5-2), avec d1 =d2 =d, possède une 15 structure de groupe additif,Ed(F2m). Par méthode cryptographique sur courbe elliptique on entend notamment une méthode de chiffrement, une méthode de déchiffrement, une méthode de génération d'un couple (clé privée, clé publique), une méthode d'échange de clés selon un protocole Diffie-Hellmann, une méthode de signature 20 électronique etc., faisant appel à au moins une primitive cryptographique dans laquelle un entier k est transformé en un point kP où P est un point de ladite courbe elliptique. Autrement dit, ladite méthode cryptographique fait appel à au moins une opération d'exponentiation dans le groupe Ed(F2m). L'idée à la base de l'invention est de sélectionner les paramètres de la 25 méthode cryptographique sur courbe BEC en fonction d'un certain nombre de critères de sécurité, de facilité d'implémentation, et de rapidité de calcul. 11 12 Dans une première étape, on recherche les corps d'extension binaire Fr et les polynômes irréductibles associés, se prêtant bien à des calculs arithmétiques au moyen d'une architecture matérielle 32 ou 64 bits. Par architecture matérielle à 32 ou 64 bits, on entend que la taille des registres et/ou 5 des bus de données est de 32 ou 64 bits. Par exemple, une telle architecture matérielle sera présente dans un cryptoprocesseur 32 ou 64 bits. Pour chaque nombre premier a compris dans un intervalle [a.'a.] où amie est une valeur minimale prédéterminée correspondant au niveau de sécurité minimal souhaité et an est une valeur maximale prédéterminée, on 10 recherche les polynômes irréductibles dans F2 [X] de degré a et de forme trinomiale : H(X)= X' + Xb +1 (7-1) 15 dans laquelle les degrés des monômes vérifient : a -b =O[wordsize] (7-2) où wordsize est la taille en nombre de bits des registres dans l'architecture 20 matérielle de l'implémentation souhaitée. Par exemple wordsize =32 ou 64 selon que l'on recherche une implémentation sur 32 ou 64 bits. On choisira avantageusement an.= 256 de manière à pouvoir atteindre le niveau de sécurité minimal de 128 bits préconisé par le NIST. On pourra toutefois déroger à ce principe lorsque les ressources du noeud loT sont faibles et 25 que l'on peut accepter un niveau de sécurité inférieur. Dans ce dernier cas, on pourra choisir an.= 160 si l'on accepte un niveau de sécurité minimal de 80 bits. 13 On notera que si la condition (7-2) est remplie sur 64 bits, elle est a fortiori sur 32 bits. Si, pour une valeur de a donnée, un tel trinôme n'existe pas, autrement dit s'il n'existe pas d'entier b vérifiant a -b =O[wordsize] tel que H(X) soit un polynôme irréductible de Fr , on recherche alors les polynômes 5 de forme pentanomiale : H(X)= Xa + Xb +X° + Xd +1 (8-1) tels que : 10 a -b =O[wordsize] , a - c = O[wordsize] et a - d =O[wordsize] (8-2) On peut montrer que pour tout degré d'extension binaire m, on peut trouver un polynôme de forme trinomiale ou pentanomiale de degré a=m, 15 irréductible sur F2 et primitif sur Fr,, c'est-à-dire tel que l'anneau quotient F2 [X]/ (H(X)) soit isomorphe à l'extension binaire Fr, où F2 [X] est l'anneau des polynômes à coefficients dans F2. H(X) étant irréductible sur F2, F2 [X]/ (H(X)) a une structure de corps comme Fr, . On notera t la classe de X dans F2 [X1/ (H(X)), t est donc une racine de H(X). Fr, étant identique à 20 un isomorphisme près à F2,, [t]= F2[X]/(H(X)), les deux notations seront considérées équivalentes et utilisées indifféremment dans la suite. Au terme de cette première étape, on obtient ainsi une liste de corps candidats Fr avec m premier, chaque corps candidat Fr étant associé à un polynôme irréductible H(X) de degré m à coefficients dans F2, de forme 25 trinomiale ou pentanomiale, vérifiant respectivement la condition (7-2) ou (8-2). 14 Ainsi pour l'intervalle [160,571], on peut notamment retenir les corps 5 candidats suivants : (9-1) F2223 [t] = F2 [X]/(X223 + X159 + 1) F225, [t] = F2 [X]/(X257 + X65 +1) (9-2) F2,1, [t] = F2 [X]/(X3" + x121 + 1) (9-3) [t] = F2 [X1/(X431 +X303 +X239 +X111 (9-4) F2479 [t] = F2 [X]/(X479 + X255 +1) (9-5) F248, [t] = F2 [X ]/I + X295 + X167 + X39 +1) (9-6) 10 F252, [t] = F2 [X ]/(X521 + X489 +1) (9-7) F25' [t] = F2 [x]/(x569 +X441 +X313 +X121 + (9-8) Tous les corps ci-dessus se prêtent bien à des calculs arithmétiques (notamment des réductions) au moyen d'une architecture 64 ou 32 bits, à 15 l'exception des corps F2'9[t] et F2521 [t] qui ne se prêtent bien qu'à des calculs sur une architecture 32 bits. Dans une seconde étape, on recherche pour chacun des corps F2,, [t] ci-dessus, une courbe BEC simplifiée (cf. expression (6)), autrement dit un élément 2 0 d de Fr, , tel que l'ordre du groupe E d (F 2m) noté Ed (F 2,,), soit de la forme 2s n où n est un nombre premier et s e {1,2,3}, et tel que Ed (Fr), l'ordre du groupe associé à la courbe BEC quadratiquement tordue, E soit également de la forme 2s' n' où n' est un nombre premier et sic {1,2,3}. Cette contrainte sur Ed (F2',) (resp. sur E',/1"' (F2,' )), autrement dit sur le nombre de points de la 15 courbe Ed (resp. dont on rappelle que les coordonnées sont des éléments du corps Fr,, permet de réduire la sensibilité aux attaques usuelles de résolution de ECDLP sur la courbe BEC (resp. des attaques par fautes s'effectuant sur la tordue quadratique). 5 En pratique, on recherche un élément d avec un poids de Hamming faible en commençant par une expression binomiale en t (poids de Hamming égal à 2), puis une expression trinomiale (poids de Hamming égal à 3), quadrinomiale (poids de Hamming égal à 4) et enfin pentanomiale (poids de Hamming égal à 5), autrement dit dans ce dernier cas : 10 d =ta +t° +t8 +t' +1 (10) où m>a>p>6>y>0 sont des entiers, d étant tel que lEd(F)=2sn et Ed (F2,,, = 2s' n' avec les conventions précitées. 15 D'autres critères de sécurité, d'importance moindre par rapport au critère mentionné plus haut, peuvent également être pris en compte, tels que : - le j -invariant de la courbe BEC, à savoir 1/d8 doit être un élément générateur de Fr [t] ; - le discriminant de la multiplication complexe de la courbe BEC, à 20 savoir Ad = Tr(Ed )2 -4pm , doit être divisible par un grand nombre premier (par exemple supérieur à 2100) exactement une fois ; - l'ordre multiplicatif de r, modulo n , dans F2,, [t] est élevé (par à 00-1 exemple supérieur a ). De même, l'ordre multiplicatif de r, modulo n', dans F2', [t] est élevé (par exemple supérieur à m-1 100 16 Ces critères de sécurité permettent d'éviter dans certains cas une accélération des attaques ECDLP. Il convient de noter que relativement peu de valeurs de d vérifient l'ensemble de ces conditions. 5 L'Annexe donne pour chacun des corps candidats, les plus faibles valeurs du paramètre d ainsi que l'ordre des groupes Ed (F2,' ) et Edi'' (Fr, ). Pour simplifier les notations, on a adopté dans l'annexe les notations 1E1 et E1 en lieu et place de Ed et ), respectivement. 10 Dans une troisième étape, on recherche pour chacune des courbes BEC sélectionnées à la deuxième étape, un point générateur G optimal pour effectuer les opérations arithmétiques sur la courbe BEC et plus exactement dans le groupe additif Ed(F2m). Etant donné que l'ordre de G (autrement dit l'ordre du sous-groupe 15 cyclique engendré par G) divise l'ordre Ed (F )= 2'n, on choisira avantageusement un point G d'ordre n , le cofacteur de G étant alors 2s. Le fait de choisir un point générateur d'ordre premier (élevé) renforce sensiblement la sécurité des calculs vis-à-vis d'éventuelles attaques. Un avantage important de l'invention est que le point générateur est en 20 outre choisi pour simplifier les calculs sur la courbe BEC. On rappelle que les opérations arithmétiques (addition et doublement notamment) sur les points de la courbe font généralement appel à une technique d'addition différentielle (cf. article précité « Binary Edwards Curves » de Bernstein et al.). Selon cette technique, chaque point de la courbe P(x,y) est 25 représenté par une coordonnée w(P) = x+ y qui est un élément de F2,, N. Il est alors possible de calculer w(2P) et w(Q+P) (où Q est un autre point de la 17 courbe BEC) à partir de li(P), w(Q) et w(Q-P). Plus précisément, si l'on suppose que W en adoptant une w(P)_ z2 ' 112(Q) = Z3 ' w (Q - P) = w 1 5 représentation mixte (affine et projective), on a : 142 C2 (2P) = 2 d(4) + C2 le (ID ± Q, ) V +Z51121 (11-2) V ± d(Z2Z3 )2 avec C =W2 (Z2 ± W2) et V =CW3(Z3 + W3). 10 Ce calcul peut être encore simplifié (économie d'une opération d'élévation au carré au dénominateur de (11-1) et (11-2)) en adoptant un dénominateur commun pour w(P) et w(Q), comme décrit dans la thèse de B. Koziel précitée (paragraphe 3.2.5.1). Cette simplification est connue dans la 15 littérature sous le nom de « Co-Z trick ». Dans ce cas, w(P) et w(Q) sont représentés sous la forme w(P) = W Z et w(Q) = , et les expressions (11-1), (11-2) deviennent: (12-1) (w2 (w2 + z))2 w (2P) = clZ 4 + (W 2(W 2 + Z))2 20 18 (w2 ±w3V ± w1 (w2 ±w3)2 (12-2) W(P+Q) - f 1 Z2 1 ± (W2 + W3 )2 11;1 Il est ensuite possible de revenir aux coordonnées (x, y) à partir des coordonnées différentielles w, comme décrit par exemple dans la thèse de B. 5 Koziel précitée (algorithme 3.3). On remarque que l'expression (12-2) fait appel à -1 avec w1= w(Q-P) if 1 . Or, lorsque l'on souhaite calculer w(P+Q) par itérations successives sur une échelle de Montgomery, l'écart entre deux points au sein d'une itération est de 1 de Q -P = G . Il en résulte que toutes les itérations utilisent l'élément 142(G) 10 Fr [t] . Afin de réduire le nombre de multiplications dans F2', [il, il est 1G) intéressant d'opter pour un point générateur tel que 142( ait un faible poids de Hamming. Autrement dit, idéalement 142( 21G) , doit être un monôme ou un binôme en t : 15 1 (13-1) w(G) =t OU 2, (13-2) 142 (G) = t +1 20 avec 1 REVENDICATIONS1. Méthode cryptographique sur une courbe binaire d'Edwards définie par d(x+ x2 + y+ y2) = (x + x2)(y+ y2) dans le plan affine par un corps d'extension binaire Fr, [t] = F2 [X] / (H(X)) où F2 [X] est l'anneau des polynôme à coefficients dans F2 et H(X) est un polynôme irréductible de F2 [X] de degré m , le paramètre d de la courbe étant un élément de F2,, [t], l'ensemble des points de la courbe étant muni d'une loi lui conférant une structure de groupe additif, Ed (F2m ), ladite méthode faisant appel à au moins une primitive cryptographique dans laquelle un entier k est transformé en kG où G est un point de Ed (Fr, ), dit point générateur, ladite méthode étant caractérisée en ce que: pour une implémentation de ladite méthode au moyen d'une architecture matérielle 32 bits ou 64 bits, le corps d'extension binaire est l'un des corps suivants : F22' [t] = F2 [X]/(X257 ± X65 +1) ; F2431 [t] = F2 [X]/(x431 )(303 ± X239 ± x111 +1) ; F2487 [t] = F2 [X]/(X487 + X295 + X167 + X39 + 1) ; F2569 [t] = F2 [X]/(X569 + x441 + X313 + x121 1) ; et pour une implémentation au moyen d'une architecture matérielle 32 bits, le corps d'extension binaire pouvant être également choisi parmi : F2223 [t] = F2 [X]/(X223 + X159 + 1) ; F2479 [t] = F2 [X]/(X479 + X255 + 1) F2521 [t] = F2 [X]/(X521 + X489 + 1) ; 35 - le paramètre d de la courbe binaire d'Edwards sur chacun de ces corps d'extension binaire étant donné dans l'annexe. 2. Méthode cryptographique sur une courbe binaire d'Edwards selon la 5 revendication 1, caractérisée en ce que le paramètre d de la courbe binaire d'Edwards est donné par : pour F2223 [t] : d = t64 + t36 + t5 + 1 ; pour F2257 [t] : d = t65 + t31 + t14 + 1 ; pour F2313 [t] : d - t" + t" t28 + ; 10 pour F2431 [t] : d = t83 t66 + t17 + 1 ; pour F2479 [t] : d = t73 + t29 + t2 +1 ; pour 15 F2487 [t] : d - t69 + + t +1 ; pour F2521 [t] : d t66 + t29 + t28 + 1 ; pour F2569 [t] : d = t56 + t45 + t41 + 1 15 3. Méthode cryptographique sur une courbe binaire d'Edwards selon la revendication 2, caractérisée en ce que ledit point générateur G, de coordonnées affines (Gy, Gy , possède une coordonnée différentielle 1G) w (G) = G ' + Gy dont l'inverse w(G) vérifie: 20 - pour F222, [t] : - pour F2257 [t] : - pour F231, [t] : 1 t32 + 1 ; 1 t192 142 (G) 1 t64 + 1 ; 142 (G) 142 (G) 36 pour F243, [t] : pour F2'9 [t] : pour F2487 [t] : pour F2521 [t] : 5 pour F2569 [t] t64 + ; if (G) 1t32 +1 ; 1,12 (G) t64 + . W (G) 4. Méthode cryptographique sur une courbe binaire d'Edwards selon la revendication 3, caractérisée en ce les coordonnées affines (Gx,Gy) du point générateur sont données, en notation hexadécimale, par : 10 - pour F222, [t] - pour F2_, [t] : 15 - pour F23' [t] : - pour F2431 [t] 0I [] 69 nod -