Brevet FR2852470A1 — publié le 20040917

PROCEDE CRYPTOGRAPHIQUE METTANT EN EUVRE DES COURBES HYPERELLIPTIQUES DE GENRE 2 L'invention se rapporte à un procédé de cryptage de données dans une entité électronique et met en oeuvre des courbes hyperelliptiques de genre 2. L'invention s'applique en particulier avantageusement, mais de façon nullement limitative, aux cartes à microcircuit. On rappelle tout d'abord la définition d'une courbe hyperelliptique. Soit K un corps fini. L'ensemble des points (x,y) c KxK vérifiant l'équation y2+ h(x)y = f(x) (1) o h est un polynôme de degré au plus g sur K, g étant un entier strictement positif, et f est un polynôme unitaire de degré 2g+l sur K, forment, avec le point à l'infini O, une courbe hyperelliptique de genre g. Toute courbe hyperelliptique sur un corps peut s'exprimer sous cette 15 forme. On sait aussi que dans un corps fini, le nombre d'éléments du corps s'exprime toujours sous la forme pn, o p est un nombre premier. Le nombre p est la caractéristique du corps. L'invention se rapporte plus particulièrement au cas des applications 20 cryptographiques o l'exposant n est impair. Les algorithmiques à clé publique sur des courbes hyperelliptiques permettent des applications cryptographiques de type chiffrement, vérification de signature, authentification, etc. Il est récemment apparu un intérêt croissant pour les courbes 25 hyperelliptiques. La communauté scientifique espère ainsi obtenir des temps de calcul réduits pour une sécurité équivalente aux autres systèmes cryptographiques, tels que les algorithmes du type RSA ou fondés sur des courbes elliptiques (ECC, en anglais "Elliptic Curve Cryptosystems"), d'autant que le corps de base sur lequel on travaille est petit dans le cas des courbes 30 hyperelliptiques, ce qui est déterminant, en termes de vitesse de calcul, dans le domaine des cartes à microcircuit. Deux classes de courbes hyperelliptiques sont plus particulièrement utilisées dans les systèmes cryptographiques: celles définies sur un corps fini K de caractéristique p différente de 2 et de 2g+1, et celles définies sur un corps de caractéristique égale à 2. L'invention s'intéresse aux courbes hyperelliptiques sur un corps de caractéristique égale à 2 car elles permettent des réalisations électroniques plus 5 rapides. Par ailleurs, I'invention s'intéresse aux courbes de genre 2 (c'est-à-dire au cas g = 2), car il a déjà été montré que la sécurité est affaiblie pour g > 4, et lorsque g = 1, on est en présence de courbes elliptiques. L'équation d'une courbe hyperelliptique (1) de genre 2 s'écrit ainsi y2 + (h2x2 + h1X + ho)y = x5 + f4x4 + f3x3 + f2x2 + f1x + f0, o fi ï K, hi E K (2) 10 Il est bien connu de l'homme du métier que la Jacobienne d'une courbe hyperelliptique forme un groupe abélien additif. Les éléments de cette Jacobienne sont des diviseurs de degré 0 modulo les diviseurs principaux. Un diviseur est la somme formelle de points (x,y) de la courbe hyperelliptique. En pratique, on utilise la représentation de Mumford, o un diviseur D est 15 représenté par une paire de polynômes u et v sur le corps fini K, soit D = (u,v), o u est un polynôme unitaire de degré 2, le degré de v est strictement inférieur au degré de u, et u divise le polynôme f-hv-v2. Pour les courbes hyperelliptiques, I'algorithme de G. Cantor définit l'addition de diviseurs D = (u,v) dans la Jacobienne. L'addition ainsi définie sur 20 les diviseurs éléments de la Jacobienne est à la base des algorithmes de multiplication scalaire utilisant les courbes hyperelliptiques. Etant donné un diviseur D de la courbe hyperelliptique et un entier m fixé, le résultat de la multiplication scalaire du diviseur D par le scalaire m est le diviseur D' de la courbe hyperelliptique et s'écrit D' = m.D = D + D + ... + D (m fois). Le calcul de la multiplication scalaire D' = m.D est réalisé par une série d'opérations d'addition et doublement (D+D) de diviseurs, par exemple selon un algorithme bien connu sous la terminologie anglaise "double and add". On réalise autant d'opérations d'addition de diviseurs qu'il y a de bits de valeur 1 dans la représentation de m en binaire et on réalise autant d'opérations de 30 doublement de diviseurs qu'il y a de bits dans la représentation de m en binaire. Typiquement, m est représenté sur environ 90 bits (par exemple 89 bits). Les algorithmes cryptographiques à clé publique ou symétrique sur une courbe hyperelliptique sont ainsi fondés sur la multiplication scalaire d'un diviseur D de la courbe hyperelliptique par un scalaire m prédéterminé, qui est la clé (secrète ou publique). Le résultat de cette multiplication scalaire m.D est un diviseur D' de la courbe hyperelliptique. Dans un exemple d'application au chiffrement, le diviseur D' obtenu représente le résultat du chiffrement d'un message représenté par D en utilisant la clé secrète m. Cependant, l'algorithme de G. Cantor présente l'inconvénient d'être trop lent, essentiellement en raison de l'utilisation répétée de l'algorithme de calcul du pgcd (algorithme d'Euclide pour le calcul du plus grand commun diviseur). Il utilise surtout une mémoire de calcul excessive, ce qui est prohibitif pour 10 l'implantation dans des cartes à microcircuit. Récemment, l'utilisation de formules explicites pour l'addition de deux diviseurs et le doublement d'un diviseur pour les courbes hyperelliptiques de genre 2 a permis d'accélérer considérablement les calculs et surtout de réduire l'espace mémoire utilisé, ce qui a conduit à un regain d'intérêt pour les courbes 15 hyperelliptiques. On a par exemple obtenu des temps de calcul avec les courbes hyperelliptiques comparables à ceux obtenus jusqu'à présent avec les courbes elliptiques. On peut retrouver les formules explicites pour la caractéristique 2 dans les articles de Tanja LANGE intitulés "Efficient Arithmetic on Genus 2 Hyperelliptic 20 Curves over Finite Fields via Explicit Formulae", Cryptology ePrint Archive, Report 2002/121, 2002, "Inversion-Free Arithmetic on Genus 2 Hyperelliptic Curves", Cryptology ePrint Archive, Report 2002/147, 2002, et "Weighted Coordinates on Genus 2 Hyperelliptic Curves", Cryptology ePrint Archive, Report 2002/153, disponibles sur Internet à l'adresse "http://eprint.iacr.org". Ces formules explicites décrivent une série d'étapes de calcul, combinant les coefficients des polynômes h et f de la courbe hyperelliptique et les coordonnées u et v des diviseurs, par des multiplications et des additions sur K. Le résultat final de cette série d'étapes de calcul consiste en les coordonnées du diviseur résultant de l'addition de deux diviseurs ou du diviseur résultant du 30 doublement d'un diviseur. Ces formules explicites sont données en coordonnées affines, c'est-à-dire sous la forme D = (u,v), et projectives, c'est-à-dire sous la forme D = (U:V:Z), o Z représente une ou plusieurs variables (il s'agit en fait d'un tableau). Deux types de représentations projectives sont utilisés: projective simple et projective pondérée. Il apparaîtra clairement à l'homme du métier que l'invention s'applique à tout type de représentation des coordonnées d'un diviseur. L'invention cherche à simplifier ces formules explicites. Or s'il est aisé de 5 trouver une courbe hyperelliptique plus simple, il est beaucoup plus difficile de trouver une telle courbe qui soit également sûre d'un point de vue cryptographique. A titre d'exemple, l'homme du métier constatera aisément que les courbes hyperelliptiques suivantes ne sont pas sûres: y2+y=X5+ 1 y2 + xy = x5 + x3 + x2 + f0 avec f0 E K (K corps fini de cardinalité pn) et n = 89 L'article de F. ZHANG, S. LIU et K. KIM intitulé "Compact representation of domain parameters of hyperelliptic curve cryptosystems", Proceedings de la conférence ACISP 2002, Lecture Notes in Computer Science 2384, Springer 15 Verlag, divulgue la simplification de courbes hyperelliptiques par changement de variable et propose l'étude d'un cas particulier, permettant de supprimer certains coefficients. Il s'agit des courbes définies par l'équation suivante: y2+ xy = x5 + f4x + f3x3 + f2X2 + f1x + f0 avec f1: 0 (3) c'est-à-dire l'ensemble des courbes hyperelliptiques données par l'équation (2) 20 restreint à celles o h2 = 0, hl = 1, ho = 0 et f1 0. Pour simplifier cette courbe hyperelliptique, on pose le changement de variable y = f4l/2x2 + fo2 + Bx o Best une solution de x2 + x = f2 ou x2 + x = f2 + 1. On obtient alors: y2+ xy = x5 + f3x3 + f2x2 + fix avec f2 E {0,1} et fi: 0 (4) 25 Néanmoins, la simplification proposée par ZHANG et al. a l'inconvénient de ne concerner qu'une infime partie des courbes hyperelliptiques. Si on pose q = p" comme étant la cardinalité du corps K, le nombre total de courbes hyperelliptiques est q8, alors que la simplification de ZHANG et al. ne concerne que q5 courbes environ, soit une courbe sur q3 courbes. Or, typiquement, n est 30 proche de 90 (par exemple, n = 89) pour obtenir avec des courbes hyperelliptiques une sécurité équivalente au système RSA actuel. Dans ce cas, la simplification proposée par ZHANG et al. ne concerne, en caractéristique 2, qu'une courbe sur 2240, soit environ une courbe sur 1072 courbes. A la lecture de l'article de ZHANG et ai., l'homme du métier comprend que ces simplifications ne sont pas possibles pour l'ensemble des courbes hyperelliptiques. Ces simplifications ne sont possibles qu'en raison de la nature des courbes étudiées. La présente invention a pour but de remédier à cet inconvénient. Elle cherche à simplifier les formules explicites mentionnées plus haut, afin d'obtenir des algorithmes plus performants pour l'addition et le doublement sur des courbes hyperelliptiques. Elle propose en outre une simplification s'appliquant à tout type de courbe hyperelliptique. L'idée de base de l'invention est de choisir de travailler uniquement sur des courbes hyperelliptiques simplifiées o certains des coefficients des polynômes h et f sont supprimés ou restreints à {0,1}, afin de simplifier les formules explicites et donc d'accélérer l'addition et le doublement, et cela sans perte de généralité. En effet, à partir d'une courbe hyperelliptique quelconque, on 15 peut toujours se ramener, par un isomorphisme sur K, à une de ces courbes hyperelliptiques simplifiées. L'isomorphisme sur K en question est un changement de variable sur la courbe hyperelliptique. On sait qu'un sousensemble de courbes ainsi isomorphes entre elles définit une classe d'isomorphisme. En cryptographie, il est bien connu de l'homme du métier que lorsque deux courbes hyperelliptiques sont isomorphes, deux systèmes cryptographiques utilisant ces deux courbes sont théoriquement équivalents du point de vue de leur sécurité. Typiquement, les mêmes attaques seront identiquement efficaces ou inefficaces sur les deux systèmes cryptographiques. 25 C'est pourquoi l'utilisation de courbes simplifiées par isomorphisme est considéré comme étant réalisé sans réduire la sécurité. Dans le but mentionné ci-dessus, l'invention propose un procédé de cryptage de données dans une entité électronique, ce procédé utilisant des courbes hyperelliptiques de genre 2 sur un corps de caractéristique 2, de la 30 forme y2 + (h2x2 + h1x + ho)y = x5 + f4x4 + f3x3 + f2x2 + f1x + f0, o pour tout entier i = 0, 1, 2 et tout entier j = 0, ..., 4, hi et fi sont des éléments de la réunion du corps précité et de l'ensemble {0,1}, ce procédé étant remarquable en ce que - h2, f4, f2 appartiennent à {0,1}, et - au moins une des conditions suivantes est remplie: h2 ó 0, h1 X 1, ho ó 0, f1 = 0. Ainsi, I'invention permet d'utiliser des courbes hyperelliptiques plus simples et d'obtenir des temps de calcul réduits pour les algorithmes 5 cryptographiques, sans pour autant diminuer la sécurité du système cryptographique. Selon une caractéristique particulière, le procédé conforme à l'invention est utilisé pour effectuer des opérations de doublement ou d'addition de diviseurs, dans lesquelles l'invention permet d'augmenter la vitesse de calcul. Une typologie des courbes hyperelliptiques de genre 2 est donnée dans l'article de Y. CHOIE et D. YUN intitulé "lsomorphism classes of hyperelliptic curves of genus 2 over F', Proceedings de la conférence ACISP 2002, Lecture Notes in Computer Science 2384, Springer Verlag, qui définit trois types de courbes hyperelliptiques suivant les coefficients dominants du polynôme h de la 15 courbe hyperelliptique: - type l: h2 0; type ll:h2=0, h 0; - type lI: h2= hl = 0, ho 0. Dans un mode particulier de réalisation, le procédé conforme à l'invention 20 utilise des courbes hyperelliptiques de type I de la forme y2 + (x2 + h1x + ho)y = x5 + f4x4 + fx + f0, avec h0 = 0 ou h0 = h12, et f4 e {0,1}. Ce mode de réalisation permet une simplification optimale des courbes hyperelliptiques, c'est-à-dire une simplification permettant d'obtenir un nombre minimal de coefficients sans toutefois réduire la sécurité du système 25 cryptographique et s'appliquant à toutes les courbes. Dans un autre mode particulier de réalisation, le procédé conforme à l'invention utilise des courbes hyperelliptiques de type Il de la forme y2 + (x + ho)y = x5 + f2x2 + f0 avec f2 e {0,1}. Dans encore un autre mode particulier de réalisation, il utilise des courbes 30 hyperelliptiques de type Il de la forme y2 + xy = X5 + f3x3 + f2x2 + f0 avec f2 {0,1}. Ces deux derniers modes de réalisation permettent également une simplification optimale des courbes hyperelliptiques, au sens de la minimisation du nombre de coefficients obtenus, et s'appliquant à toutes les courbes. Cette simplification est d'autant plus avantageuse que le type Il comporte, en proportion, plus de courbes hyperelliptiques sûres d'un point de vue cryptographique, que les autres types (I et 1II). Dans le dernier mode de réalisation mentionné ci-dessus, avantageusement, f2 = 1. En effet, ce choix de coefficient permet d'obtenir une proportion plus élevée de courbes offrant une plus grande sécurité du point de vue cryptographique. Dans une application privilégiée de la présente invention, l'entité 10 électronique est une carte à microcircuit. Dans le même but que celui indiqué plus haut, la présente invention propose également une entité électronique mémorisant une courbe hyperelliptique de genre 2 sur un corps de caractéristique 2, de la forme y2 + (h2X2 + h1x + ho)y = x5 + f4x4 + f3x3 + f2x2 + f1x + fo, o pour tout entier i = 0, 1, 2 et 15 tout entier j = 0, ..., 4, hi et fj sont des éléments de la réunion du corps précité et de l'ensemble {0,1}, l'entité électronique étant remarquable en ce que: - h2, f4, f2 appartiennent à {0,1}, et - au moins une des conditions suivantes est remplie: h2 É 0, h1 t 1, ho X 0, f1 = 0. Les caractéristiques particulières et les avantages de l'entité électronique étant similaires à ceux du procédé de cryptage conforme à l'invention, ils ne sont pas rappelés ici. D'autres aspects et avantages de l'invention apparaîtront à la lecture de la description détaillée qui suit de modes particuliers de réalisation, donnés à titre 25 d'exemples non limitatifs. La description est faite en référence aux dessins qui l'accompagnent, dans lesquels: - la figure 1 est un organigramme illustrant les différentes étapes correspondant aux formules explicites obtenues dans le cas de coordonnées affines pour un exemple non limitatif d'opération d'addition de deux diviseurs, en 30 utilisant une première courbe hyperelliptique du type mis en oeuvre dans la présente invention; - la figure 2 est un organigramme illustrant les différentes étapes correspondant aux formules explicites obtenues dans le cas de coordonnées affines pour un exemple non limitatif d'opération de doublement d'un diviseur, en utilisant une deuxième courbe hyperelliptique du type mis en oeuvre dans la présente invention; et - la figure 3 est un organigramme illustrant les différentes étapes 5 correspondant aux formules explicites obtenues dans le cas de coordonnées affines pour un exemple non limitatif d'opération de doublement d'un diviseur, en utilisant une troisième courbe hyperelliptique du type mis en oeuvre dans la présente invention. On cherche à crypter des données dans une entité électronique, telle 10 qu'une carte à microcircuit. On utilise à cette fin des courbes hyperelliptiques de genre 2 sur un corps K de caractéristique 2, de la forme y2 + (h2x2 + h1x + ho)y = x5 + f4x4 + f3x3 + f2x2 + f1x + fo, o pour tout entier i = 0, 1, 2 et tout entier j = 0, ..., 4, hi et fj sont des éléments du corps considéré. Conformément à la présente invention 15 - h2, f4, f2 appartiennent à {0,1}, et - au moins une des conditions suivantes est remplie: h2 É 0, hl É 1, ho É 0, f1 = 0. Les formules explicites obtenues à partir des courbes hyperelliptiques ainsi simplifiées conduisent à des temps de calcul inférieurs à ceux donnés par 20 T. LANGE dans les articles précités. Le tableau 1 cidessous compare les formules explicites données par T. LANGE et celles résultant de l'invention, du point de vue du nombre de multiplications (ou de mises au carré, également comptées comme étant des multiplications) et d'inversions sur le corps K, qui engendrent l'essentiel du temps de calcul pour l'addition et le doublement de 25 diviseurs. Lorsque les calculs cryptographiques sont réalisés par une carte à microcircuit, une multiplication ou un doublement sur un corps K à 2" éléments nécessite typiquement environ 100 fois plus de temps qu'une addition sur K, et 150 fois plus de temps qu'une multiplication par un scalaire appartenant à {0,1} 30 ou qu'une addition d'un élément du corps K. Une inversion sur K exécutée par une carte à microcircuit peut nécessiter au moins 20 fois plus de temps qu'une multiplication. Par comparaison, exécuter une inversion sur un ordinateur personnel peut nécessiter trois fois plus de temps qu'une multiplication. Il est à noter que, dans le cas d'une représentation projective, il n'y a pas d'inversion dans les formules explicites, d'o l'intérêt de ce type de représentation pour les applications aux cartes à microcircuit. Représentation Opération T. Lange Invention Gain en temps apporté par l'invention Affine Addition 25 multiplications 25 multiplications 0% 1 inversion 1 inversion Doublement 29 multiplications 27 multiplications 2% 1 inversion 1 inversion Projective Addition 43 multiplications 42 multiplications 2,5% pondérée Doublement 48 multiplications 47 multiplications 2% Projective Addition 43 multiplications 42 multiplications 2,5% simple Doublement 52 multiplications 48 multiplications 7,5% Tableau 1 Le gain en temps de calcul n'apparaît comme substantiel que dans le cas de l'opération de doublement en représentation par coordonnées projectives 10 simples. Cependant, on montrera par la suite que la simplification des formules explicites proposée par l'invention peut être affinée de façon à obtenir des gains beaucoup plus importants et pour tout type de représentation (affine, projective) et d'opération (addition, doublement). L'organigramme de la figure 1 illustre les différentes étapes 15 correspondant aux formules explicites obtenues dans le cas de coordonnées affines pour un exemple non limitatif d'opération d'addition de deux diviseurs: D1 = (Uî, V1) = [uîî,ulo,vîî,vîo], o u11 et u10 sont les coefficients du polynôme U, et v11 et v10 sont les coefficients du polynôme V1, et D2 = (U2, V2) = [u21,u20,v21,v20], o u21 et u20 sont les coefficients du 20 polynôme U2 et v21 et v20 sont les coefficients du polynôme V2. On cherche donc à obtenir D1 + D2 = [uî,uO,vl,vO]. On utilise à cet effet la courbe hyperelliptique définie par l'équation: y2 + (h2x2 + hlx + ho)y = x5 + f4x4 + f3x3 + f2x2 + f1x + f0, avec h2, f4, f2 E {0,1}. Les étapes 10 à 16, dont le détail est illustré sur la figure 1 et n'est donc 25 pas répété ici, sont une succession de calculs intermédiaires aboutissant à l'obtention de D1 + D2. A l'étape 11, la notation inv1 désigne le quasi-inverse de v1 (et invo le quasi-inverse de vo) (en anglais "almost inverse"). On donne cidessous le coût de calcul associé à chaque étape, en termes de multiplications, de mises au carré et d'inversions sur le corps K (les opérations de multiplication 5 et d'addition pour lesquelles un des opérandes est un coefficient d'un polynôme de la courbe hyperelliptique qui est, selon l'invention, dans {0, 1}, ne sont pas décomptées dans le calcul du coût): - étape 10: 1 mise au carré, 3 multiplications; - étape 11: coût nul; - étape 12:5 multiplications; - étape 13: 1 inversion, 1 mise au carré, 5 multiplications; - étape 14:2 multiplications; - étape 15: 1 mise au carré, 3 multiplications; - étape 16: 4 multiplications. Le coût global est donc de 1 inversion, 3 mises au carré et 22 multiplications. L'homme du métier pourra déduire, à partir des articles de T. LANGE précités, pour toutes les autres combinaisons de représentations (affine, projective) et d'opérations (addition, doublement), des formules explicites 20 permettant de réduire le nombre de multiplications pour les courbes hyperelliptiques de la forme (2) ainsi simplifiées en posant h2, f4, f2 E {0,1}. Ainsi, l'invention se rapporte à un procédé de cryptage de données dans une entité électronique, qui utilise des courbes hyperelliptiques de genre 2, sur un corps de caractéristique 2, s'écrivant: y2 + (h2x2 + h1x + ho)y = x5 + f4x4 + f3x3 + f2x2 + f1x + f0, avec h2, f4, f2 E {0,1} et qui satisfont au moins une des conditions suivantes: h2 É 0, h1 É 1, ho # 0 ou f1 = 0. Préférentiellement, ce procédé cryptographique est utilisé pour effectuer des opérations de doublement ou d'addition de diviseurs, car il permet 30 d'accélérer les calculs, comme indiqué plus haut. Cependant, l'intérêt de l'invention ne se restreint pas à ces deux types d'opération ou même au calcul de la multiplication d'un diviseur par un scalaire m, soit D' = m.D. Quel que soit le type d'opération réalisé dans le calcul cryptographique, I'invention permet de limiter la mémoire nécessaire à la mémorisation et à l'utilisation de la courbe hyperelliptique. Cela est particulièrement avantageux pour les applications aux cartes à microcircuit, qui possèdent une mémoire très limitée. Typiquement, la RAM ne 5 dispose que de 4 Koctets, dont environ 512 octets dédiés aux algorithmes cryptographiques, alors qu'une courbe hyperelliptique nécessite 100 octets uniquement pour sa mémorisation. L'utilisation de courbes hyperelliptiques simplifiées permet au moins un gain de 30 % de l'espace mémoire utilisé par une courbe hyperelliptique. Conformément à la présente invention, cette simplification des courbes hyperelliptiques est possible grâce à des changements de variable bien plus complexes que ceux proposés par ZHANG et al. Ainsi, I'invention propose trois changements de variable dans un corps K de caractéristique 2, en s'appuyant sur la typologie pour le genre 2 donnée dans l'article de Y. CHOIE et al. précité. 15 Dans cet article, il est notamment montré que l'ensemble des courbes hyperelliptiques de type I peut être partitionné en asymptotiquement entre 2q3 et 4q3 classes d'isomorphismes, et que l'ensemble des courbes hyperelliptiques de type Il peut être partitionné en asymptotiquement 2q2 classes d'isomorphismes. Parmi les trois types 1, 11, 111, les courbes de type II1 ne sont pas utilisées 20 en cryptographie. Elles sont dites supersingulières et l'homme du métier sait qu'elles présentent une sécurité faible. C'est pourquoi on ne détaille pas ici le cas des courbes hyperelliptiques de type III, même si le procédé cryptographique proposé par l'invention s'applique également aux courbes de ce type. Dans un premier mode particulier de réalisation de l'invention, o on considère les courbes hyperelliptiques de type 1, on montre que le changement de variable suivant est particulièrement intéressant: X =h22x + X y= h25y + h22x + h24(Xx2 + h24pX2 + Y o: X2 2) n-1 2i X est racine de h2x2 + h1x + h0 si Tr(ho h2 h-2) = 0, avec Tr(x) = Ex2 i=O X est racine de h2x2 + h1x + ho + h12h2-1 si Tr(ho h2 hi-2) = 1, ca est racine de x2 + h2x + f4 + ? + sh22 avec ú = Tr((f4 + I)h22) = 1, À= (f3 + hx0h2 y= (32hp + h1 + (h212 + h; + ho)f3X + f2)h2-. En effet, par application de ce changement de variable, à partir d'une 5 courbe hyperelliptique telle que définie par l'équation (2), quelconque de type 1, on se ramène alors à une courbe hyperelliptique simplifiée, également de type 1, de la forme (5): y2 + (x2 + h1x + ho)y = x5 + sx4+ f1x + fo, avec ho = 0 ou h0 = h12, E {0,1}(5) (hi, f1, fo restent dans le corps K) Ainsi, le procédé de cryptage conforme à l'invention utilise avantageusement une courbe hyperelliptique de type I de la forme (5): y2 + (x2 + h1x + ho)y = x5 + f4x4 + f1x + fo, avec ho = 0 ou ho = h12 (et f4 E {0,1}) (5) Conformément à l'invention, I'utilisation de ces courbes hyperelliptiques 15 simplifiées de type I conduit à une simplification des formules explicites de T. LANGE et, comme on peut le voir dans le tableau 2 donné plus loin, à une accélération des opérations d'addition et de doublement de diviseurs. A titre d'exemple, la figure 2 illustre les différentes étapes correspondant aux formules explicites ainsi obtenues dans le cas de coordonnées affines pour 20 un exemple non limitatif d'opération de doublement d'un diviseur D = (Uî,V1) = [uî,uo,vî,vo], o u1 et u0 sont les coefficients du polynôme U1 et v1 et v0 sont les coefficients du polynôme V1. On cherche donc à obtenir 2D = [u'I,u'0,v'l,v'0]. On utilise à cet effet la courbe hyperelliptique définie par l'équation y2 + (x2 + h1x + ho)y = x5 + sx4 + fix + fo, avec s c {0,1} et h0 = 0 (courbes de type lb) ou h0 = h12 (courbes de type la). Les étapes 20 à 28, dont le détail est illustré sur la figure 2 et n'est donc pas répété ici, sont une succession de calculs intermédiaires aboutissant à l'obtention de 2D. On donne ci-dessous le coût de calcul associé à chaque 30 étape, en termes de multiplications, de mises au carré et d'inversions sur le corps K: - étape 20 (effectuée uniquement dans le cas des courbes de type la): 1 mise au carré, 3 multiplications; - étape 21 (effectuée uniquement dans le cas des courbes de type lb): 1 mise au carré, 2 multiplications - étape 22: coût nul; - étape 23: 2 multiplications; - étape 24: 5 multiplications; - étape 25: 1 inversion, 1 mise au carré, 5 multiplications; - étape 26:2 multiplications; - étape 27: 2 mises au carré, 1 multiplication; - étape 28:4 multiplications. Le coût global est donc de 1 inversion, 4 mises au carré et 22 multiplications dans le cas des courbes de type la, et de 1 inversion, 4 mises au carré et 21 multiplications dans le cas des courbes de type lb. L'homme du métier pourra déduire, à partir des articles de T. LANGE précités, pour toutes les autres combinaisons de représentations (affine, 15 projective) et d'opérations (addition, doublement), des formules explicites permettant de réduire le nombre de multiplications pour les courbes hyperelliptiques simplifiées de la forme (5). Ce mode de réalisation est remarquable dans la mesure o il propose une simplification optimale des courbes hyperelliptiques, c'est-à-dire une 20 simplification permettant d'obtenir un nombre minimal de coefficients sans toutefois réduire la sécurité du système cryptographique et s'appliquant à toutes les courbes. En effet, la courbe hyperelliptique simplifiée obtenue n'a que quatre coefficients (ho dépend de hl ou est nul) dont trois coefficients dans K (hi, f1, fo) et un coefficient dans {0,1} (f4), ce qui définit au plus 2q3 classes 25 d'isomorphismes et, d'après le résultatdonné dans l'article de CHOIE et al. précité, il existe asymptotiquement au moins 2q3 classes d'isomorphismes. Dans un deuxième et un troisième modes particuliers de réalisation, o on considère des courbes de type 11, on montre que le changement de variable suivant est particulièrement intéressant: 30 x= 2x+? y= pt5y + h22X + 14ax2 + i4IX2 + Y o: u est tel que,U3 = hl, X = hoh1 -, c= 'f4 3 est racine de x2 + h1x + f2 + Eh12, Y = ((ho + hiL)P3 + X2f3 + X4 + f1) h1-. En effet, par application de ce changement de variable, à partir d'une courbe hyperelliptique telle que définie par l'équation (2), quelconque de type 11, on se ramène à une courbe hyperelliptique simplifiée, également de type 11, de la forme (6): y2 + xy = x5 + f3x3 + EX2 + f0 avec s c {0,1} (6) (f3, f0 restent dans le corps K) Ainsi, le procédé de cryptage conforme à l'invention utilise avantageusement une courbe hyperelliptique de type 11 de la forme (6): y2 + xy = x5 + f3x3 + f2x2 + f0 avec f2 e {0,1} (6) Dans ce changement de variable, on peut choisir de supprimer le 15 coefficient f3 au lieu de ho, en choisissant X avant a, et obtenir ainsi la courbe hyperelliptique de type 11 de la forme (7): y2 + (x + h0)y = x5+ EX2 + f0, avec E e {0,1} (7) (ho, f0 restent dans le corps K) Conformément à l'invention, I'utilisation de ces courbes hyperelliptiques 20 simplifiées de type Il selon les formules (6) et (7) conduisent à une simplification des formules explicites de T. LANGE et, comme on peut le voir dans le tableau 2 donné plus loin, à une accélération des opérations d'addition et de doublement de diviseurs. A titre d'exemple, la figure 3 illustre les différentes étapes correspondant 25 aux formules explicites ainsi obtenues dans le cas de coordonnées affines pour un exemple non limitatif d'opération de doublement d'un diviseur D = (U1,V1) = [u1,uo,v1,vo], o u1 et u0 sont les coefficients du polynôme U1 et v1 et v0 sont les coefficients du polynôme V1. On cherche donc à obtenir 2D = [u'1,u'0,v'î,v'0]. On utilise à cet effet la courbe hyperelliptique définie par l'équation: y2 + xy = x5 + f3x3 + Ex2 + f0, avec s E {0,1}. Les étapes 30 à 37, dont le détail est illustré sur la figure 3 et n'est donc pas répété ici, sont une succession de calculs intermédiaires aboutissant à l'obtention de 2D. On donne ci-dessous le coût de calcul associé à chaque étape, en termes de multiplications, de mises au carré et d'inversions sur le corps K: - étapes 30 et 31: coût nul; - étape 32: 2 mises au carré, 1 multiplication; - étape 33: 1 multiplication; - étape 34: 1 inversion, 1 mise au carré, 5 multiplications; 10 - étape 35: 2 multiplications; - étape 36: 2 mises au carré; - étape 37:4 multiplications. Le coût global est donc de 1 inversion, 5 mises au carré et 13 multiplications. L'homme du métier pourra déduire, à partir des articles de T. LANGE précités, pour les deux formes de courbes hyperelliptiques simplifiées de type Il ((6) et (7)), et pour toutes les autres combinaisons de représentations (affine, projective) et d'opérations (addition, doublement), des formules explicites permettant de réduire le nombre de multiplications. Les deuxième et troisième mode de réalisation décrits ci-dessus sont remarquables dans la mesure o ils proposent une simplification optimale des courbes hyperelliptiques au sens de la minimisation du nombre de coefficients obtenus, et s'appliquant à toutes les courbes. En effet, la courbe hyperelliptique de type Il simplifiée ainsi obtenue n'a que deux coefficients (f3, fo ou f3, ho) dans 25 K et un coefficient dans {0,1} (f2), ce qui définit au plus 2q2 classes d'isomorphismes et, d'après le résultat donné dans l'article de CHOIE et al. précité, il existe asymptotiquement 2q2 classes d'isomorphismes. Cette simplification est d'autant plus intéressante que le type Il comporte, en proportion, plus de courbes hyperelliptiques sûres d'un point de vue 30 cryptographique, que les autres types (I et 1il). Le tableau 2 suivant donne le nombre de multiplications (ou de mises au carré) et d'inversions sur K obtenu pour les opérations d'addition et de doublement de diviseurs pour trois types de représentations (affine, projective pondérée et projective simple), pour les courbes hyperelliptiques générales de genre 2 (courbes hyperelliptiques de la forme (2)), et selon les trois modes de réalisation décrits précédemment (courbes hyperelliptiques de la forme (5), (6) et (7)). On constate que l'amélioration maximale en termes de réduction du temps de calcul est apportée par les courbes de type Il simplifiées de la forme (6): y2 + xy = x5 + f3x3 + f2x2 + f0 avec f2 E {0,1} Représentation Opération T. Lange Type I Type II Type II (1) simplifiées simplifiées simplifiées forme (5) forme (6) forme (7) Affine Addition 25 mult. 25 mult. 24 mult. 24 mult. 1 inversion 1 inversion 1 inversion 1 inversion Doublement 29 mult. 25 (h0=0) 18 mult. 21 mult. 1 inversion ou 1 inversion 1 inversion 26 (ho=h12) mult. 1 inversion Projective Addition 43 mult. 41 (h0=0) 40 mult. 41 mult. pondérée ou 42 (h0=h12) mult. Doublement 48 mult. 43 (ho=0) 31 mult. 37 mult. ou (ho=h12) mult. Projective Addition 46 mult. 44 (ho=0) 42 mult. 43 mult. simple ou (ho=h12) mult. Doublement 52 mult. 42 (ho=0) 31 mult. 42 mult. ou (ho=h12) mult. Tableau 2 Conformément à l'invention, la simplification générale des courbes de genre 2 en caractéristique 2, de la forme (2), consistant à poser h2, f4, f2 E {0,1}, s'obtient en prenant l'intersection des coefficients simplifiés proposés par l'invention pour les courbes hyperelliptiques de types I et Il (formes (5), (6) et 15 (7)). L'invention s'applique avantageusement aux cartes à microcircuit. En effet, les ressources de calcul d'une carte à microcircuit sont très limitées et nécessitent donc d'accorder une attention particulière au coût en temps de calcul et à la mémoire utilisée. La sécurité des courbes selon l'invention a été analysée lors d'une étude réalisée par les inventeurs en prenant n = 89 pour le corps de base K (la 5 cardinalité de corps de base K (pn) est égale à 289). Cette étude a consisté à sélectionner aléatoirement, en choisissant au hasard les coefficients des courbes dans K, au moins 10 000 courbes pour chaque forme (5) ou (6). On a ensuite appliqué, à chaque courbe hyperelliptique, l'attaque présentée par G. FREY et H. RUCK dans un article intitulé "A remark 10 concerning m-divisibility and the discrete logarithm in the divisor class group of curves", Math. Comp., vol. 62, pp. 865-874, 1994. Toutes les courbes selon l'invention testées ont résisté à cette attaque. La cardinalité de la Jacobienne de chaque courbe a été ensuite calculée en utilisant l'algorithme de Kedlaya comme cela est décrit dans un article de F. 15 VERCAUTEREN intitulé " Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2 ", Advances in Cryptology CRYPTO'02, LNCS, vol. 2248, pp. 369-384, Springer-Verlag, 2002. On a ensuite vérifié pour chaque courbe: - si le cardinal de sa Jacobienne possède un diviseur plus grand que 20 2160; on dira dans la suite que, dans ce cas, la courbe est une bonne courbe. Pour être d'une sécurité au moins minimale pour être utilisable en cryptographie, une courbe hyperelliptique doit être une bonne courbe; - si le cofacteur du cardinal de la Jacobienne est égal au cofacteur minimal; on dira dans la suite que, dans ce cas, la courbe est parfaite. D'un 25 point de vue cryptographique, une courbe parfaite offre théoriquement le maximum de sécurité pour un corps de base d'une taille donnée (par exemple n = 89). Lorsque cela est possible, on préfère, en cryptographie, utiliser ce type de courbe. On a ensuite calculé, pour chaque type de courbe hyperelliptique selon 30 I'invention, le pourcentage de courbes bonnes et parfaites, parmi les courbes aléatoires testées. Le résultat de ce calcul est donné dans le tableau 3 ci-après. Ce calcul est réalisé dans le cas o f2 = 0 et dans le cas o f2 = 1, les inventeurs ayant montré que la valeur de ce coefficient pouvait influencer le pourcentage de courbes bonnes ou parfaites. En effet, on montre, selon l'invention, pour les courbes hyperelliptiques de la forme (6), que la valeur du cofacteur minimal est dépendante de la valeur de f2, plus précisément que la valeur du cofacteur minimal est égale à 4 si f2= 0 et à 2 si f2 = 1. Type Valeur Bonnes Courbes Cofacteur Nombres de f2 courbes parfaites minimal de (%) (%) courbes testées Type I simplifiées f2=0 10,4 0,56 2 10000 forme (5) f2=1 10 0,53 2 11446 ho=hl2 Type I simplifiées f2=0 8,9 0,33 4 10000 forme (5) f2=1 9,6 0,6 4 11445 ho=0O Type II simplifiées f2=0 9,6 0,6 4 20917 forme (6) f2=1 10,9 1,23 2 16724 Tableau 3 Le tableau 3 montre qu'il y a davantage de bonnes courbes ou de courbes 10 parfaites dans le cas des courbes simplifiées de la forme (6) lorsque f2 = 1. Pour vérifier si une courbe est bonne et/ou parfaite, il faut aujourd'hui plusieurs minutes de calcul sur un ordinateur avancé. Il faudrait donc plusieurs heures, voire plusieurs jours de calcul, si on souhaitait engendrer une courbe hyperelliptique bonne et/ou parfaite de façon aléatoire, ce qui est nécessaire ou 15 utile dans certaines applications cryptographiques. Avec les courbes de la forme (6) avec f2 = 1, on peut donc obtenir une bonne courbe sensiblement plus rapidement que dans le cas des autres courbes, et une courbe parfaite deux fois plus rapidement que dans le cas des autres courbes. Ainsi, le procédé de cryptage conforme à la présente invention utilise 20 avantageusement une courbe de la forme: y2 + xy = x5+ f3x3+ x2 + fo. REVENDICATIONS 1. Procédé de cryptage de données dans une entité électronique, ledit procédé utilisant des courbes hyperelliptiques de genre 2 sur un corps de 5 caractéristique 2, de la forme y2 + (h2x2 + h1x + ho)y = x5 + f4x4 + f3x3 + f2x2 + fix + fo, o pour tout entier i = 0, 1, 2 et tout entier j = 0, ..., 4, hi et fj sont des éléments de la réunion dudit corps et de l'ensemble {0,1}, ledit procédé étant caractérisé en ce que: - h2, f4, f2 appartiennent à {0,1}, et - au moins une des conditions suivantes est remplie: h2: 0, h1 ó 1, h0 o 0, f1 = 0. 2. Procédé selon la revendication 1, caractérisé en ce qu'il est utilisé pour effectuer des opérations de doublement ou d'addition de diviseurs. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il utilise 15 des courbes hyperelliptiques de type I de la forme y2 + (x2 + h1x + ho) y = x5 + f4x4 + f1x + fo, avec ho = 0 ou ho = h12. 4. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il utilise des courbes hyperelliptiques de type Il de la forme y2 + (x + ho)y = x5 + f2x2 + f0. 5. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il utilise 20 des courbes hyperelliptiques de type Il de la forme y2 + xy = X5 + f3x3 + f2x2 + fo. 6. Procédé selon la revendication précédente, caractérisé en ce que f2 = 1. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que ladite entité électronique est une carte à microcircuit. 8. Entité électronique mémorisant une courbe hyperelliptique de genre 2 sur un corps de caractéristique 2, de la forme y2 + (h2x2 + h1x + ho)y = x5 + f4x4 + f3x3 + f2x2 + flx + fo, o pour tout entier i = 0, 1, 2 et tout entier j = 0, ..., 4, hi et fj sont des éléments de la réunion dudit corps et de l'ensemble {0,1}, ladite entité électronique étant caractérisée en ce que: 30 - h2, f4, f2 appartiennent à {0,1}, et - au moins une des conditions suivantes est remplie: h2 - 0, h1 É 1, ho 0, f1 = 0. 9. Entité électronique selon la revendication précédente, caractérisée en ce que ladite courbe est utilisée pour effectuer des opérations de doublement ou d'addition de diviseurs. 10. Entité électronique selon la revendication 8 ou 9, caractérisée en ce 5 qu'elle mémorise une courbe hyperelliptique de type I de la forme y2 + (X2 + h1X + ho)y = x5+ f4x4 + f1x + f0, avec ho = 0 ou ho= h12. 11. Entité électronique selon la revendication 8 ou 9, caractérisée en ce qu'elle mémorise une courbe hyperelliptique de type Il de la forme y2 + (X + ho)y =x5 + f2x2 + f0. 12. Entité électronique selon la revendication 8 ou 9, caractérisée en ce qu'elle mémorise une courbe hyperelliptique de type Il de la forme y2 + xy = X5 + f3x3 + f2x2 + fo. 13. Entité électronique selon la revendication précédente, caractérisée en ce que f2 = 1. 14. Entité électronique selon l'une quelconque des revendications 8 à 13, caractérisée en ce qu'il s'agit d'une carte à microcircuit.