Brevet FR2985126A1 — publié le 20130628

Procédé de détermination du cofacteur d'une courbe elliptique, composant électronique, et produit programme d'ordinateur correspondants. 1. DOMAINE DE L'INVENTION Le domaine de l'invention est celui de la cryptographie. Plus précisément, l'invention concerne une technique de détermination du cofacteur d'une courbe elliptique donnée. L'invention a de nombreuses applications, notamment dans le cadre des passeports électroniques. Plus généralement, elle peut s'appliquer à tous les protocoles et algorithmes cryptographiques basés sur l'utilisation des courbes elliptiques. 2. ARRIÈRE-PLAN TECHNOLOGIQUE Soit E une courbe elliptique définie sur un corps fini Fg, correspondant au corps fini à q éléments, où q = pm , avec p un nombre premier et m un entier supérieur ou égal à un. On considère qu'un point de base P appartenant à cette courbe (i.e le point de base point P E E(Fq)), possède un ordre égal à n. Avant d'utiliser une telle courbe elliptique dans des applications cryptographiques, il convient de vérifier plusieurs paramètres (cf. §4.2 du document Al intitulé : « Guide to elliptic curve cryptography » de D. Hankerson et al.) permettant de garantir la sécurité d'une telle courbe. Parmi ces paramètres, le cofacteur h d'une telle courbe elliptique vérifiant l'équation suivante : h = #E(Fq )In (où #E(Fq) correspond au cardinal de la courbe elliptique) doit être déterminé afin notamment d'empêcher la réalisation d'attaques du type « Small subgroup attacks » (cf. §4.3 du document Al). En effet, lorsque le cofacteur h d'une courbe elliptique est grand, celle-ci présente potentiellement une faiblesse de par la possibilité de réaliser une attaque du type « Small subgroup attacks ». De plus, le cofacteur h d'une courbe elliptique est de plus en plus utilisé afin de spécifier de nouveaux protocoles cryptographiques (comme par exemple le protocole ECC CDH (pour « Elliptic Curve Cryptography Cofactor DiffieHellman »). D'autres exemples d'applications sont décrits dans le document inititulé « Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarihtm Cryptography » (la référence de ce document est : NIST SP800-56A), et dans le document intitulé « Supplemental Access Control for Machine Readable Travel Documents (v. 1.01)» publié par l'ICAO (pour « Organisation de l'aviation civile internationale »). Cependant, déterminer le cofacteur d'une courbe elliptique au sein d'un composant électronique tel qu'un microcontrôleur d'une carte à puce n'est pas évident car les techniques de détermination du cardinal d'une courbe elliptique sont coûteuses (d'un point de vue de la complexité des opérations calculatoires à mettre en oeuvre), comme cela est mentionné au §4.2.3 du document Al, via l'utilisation par exemple d'une technique développée par Satoh, ainsi que des variantes telles que l'algorithme dit SST (pour « Satoh-Skjernaa-Taguchi ») ou l'algorithme AGM (pour « Arithmetic Geometric Mean »). On connaît de ce document de l'état de la technique une solution utilisant l'inégalité du théorème de Hasse, qui, lorsque n >4-'Iq, propose une technique plus précise, à savoir on a : h = floor((\lq+1)21n) où la fonction floor(.) correspond à la fonction dite partie entière. Ainsi, la détermination du cofacteur dans ce cas de figure nécessite la détermination de la racine carrée de q. Pour déterminer la racine carrée de q, l'homme du métier aurait utilisé une des techniques décrites dans les documents US-639443, US-625632 et US-2006/0059216, qui proposent des techniques de détermination d'une racine carrée, pour déterminer la valeur du cofacteur. Cependant, un inconvénient de ces méthodes de détermination de racines carrées est qu'elles sont coûteuses à mettre en oeuvre et de plus elles nécessitent d'apporter des modifications sur un composant électronique tel qu'un microcontrôleur d'une carte à puce, devant mettre en oeuvre la détermination d'un cofacteur. 3. EXPOSÉ DE L'INVENTION Dans un mode de réalisation particulier de l'invention, il est proposé un procédé de calculs cryptographiques mis en oeuvre dans un composant électronique, comprenant une étape de détermination du cofacteur d'une courbe elliptique E définie sur un corps fini Fg à q éléments, ladite courbe elliptique comprenant un point de base P possédant un ordre égal à n. Un tel procédé est remarquable en ce que ladite étape de détermination comprend une étape de détermination d'une valeur de floor((q+2C "2)+1 +1)/n) lorsque que n>6-^Iq, où la fonction ceil correspond à la fonction dite partie fractionnaire, floor correspond à la fonction dite partie entière, et b correspond à la taille q en nombre de bits de q. Le principe général de l'invention consiste donc à déterminer la valeur du cofacteur en utilisant des opérations simples à mettre en oeuvre. L'invention, dans au moins un mode de réalisation, a notamment pour objectif de pallier ces différents inconvénients de l'état de la technique. Plus précisément, dans au moins un mode de réalisation de l'invention, un objectif est de fournir une technique de détermination du cofacteur d'une courbe elliptique qui soit facile à mettre en oeuvre notamment sur le nombre et la complexité des opérations calculatoires utilisées. Ainsi, ce mode de réalisation particulier de l'invention permet de déterminer la valeur du cofacteur vérifiant une condition particulière qui est, de par le choix des paramètres n et q souvent vérifiée. Dans un mode de réalisation préférentiel, il n'est pas nécessaire de vérifier le critère n > 6N1q car celui-ci est vérifié de par la méthode de construction des courbes elliptiques (cf. par exemple les courbes standardisées par le NIST). Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques pour lequel q = 2"' où m est un entier supérieur ou égal à un. Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques pour lequel q = p où p est un nombre premier supérieur ou égal à trois. Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques comprenant en outre une étape de comparaison entre n et 611q. Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques qui est remarquable en ce que l'étape de comparaison comprend : - une étape de détermination de A := 36q ; - une étape de détermination de B := n2 ; - une étape de comparaison de A et B. Ainsi, l'étape de comparaison de n avec 6^Iq ne nécessite pas la détermination d'une racine carrée. Elle ne nécessite que trois opérations : une élévation au carré, une multiplication et une soustraction, comme dans les techniques antérieures.. Dans un autre mode de réalisation de l'invention, il est proposé un produit programme d'ordinateur qui comprend des instructions de code de programme pour la mise en oeuvre du procédé précité (dans l'un quelconque de ses différents modes de réalisation), lorsque ledit programme est exécuté sur un ordinateur. Dans un autre mode de réalisation de l'invention, il est proposé un médium de stockage lisible par ordinateur et non transitoire, stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur pour mettre en oeuvre le procédé précité (dans l'un quelconque de ses différents modes de réalisation) Dans un autre mode de réalisation de l'invention, il est proposé un composant électronique comprenant des moyens de calculs cryptographiques comprenant des moyens de détermination du cofacteur d'une courbe elliptique E définie sur un corps fini Fq à q éléments, ladite courbe elliptique comprenant un point de base P possédant un ordre égal à n. Lesdits moyens de détermination sont remarquables en ce que qu'ils comprennent des moyens de détermination d'une valeur de floor((q+2ceil(b/2)+1 n) lorsque n>6^Iq, où la fonction ceil correspond à la fonction dite partie fractionnaire, floor correspond à la fonction dite partie entière, et b correspond à la taille de q en nombre de bits. Selon un aspect particulier de l'invention, il est proposé un composant électronique qui est remarquable en ce que les moyens de comparaison comprennent des moyens de comparaison entre n et 6^Iq. Selon un aspect particulier de l'invention, il est proposé un module sécurisé comprenant un tel composant électronique. Selon une implémentation préférée, les différentes étapes du procédé selon l'invention sont mises en oeuvre par un logiciel ou programme d'ordinateur, ce logiciel comprenant des instructions logicielles destinées à être exécutées par un processeur de données d'un module relais selon l'invention et étant conçu pour commander l'exécution des différentes étapes de ce procédé. En conséquence, l'invention vise aussi un programme, susceptible d'être exécuté par un ordinateur ou par un processeur de données, ce programme comportant des instructions pour commander l'exécution des étapes d'un procédé tel que mentionné ci-dessus. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un processeur de données, et comportant des instructions d'un programme tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. Selon un mode de réalisation, l'invention est mise en oeuvre au moyen de composants logiciels et/ou matériels. Dans cette optique, le terme "module" peut correspondre dans ce document aussi bien à un composant logiciel, qu'à un composant matériel ou à un ensemble de composants matériels et logiciels. Un composant logiciel correspond à un ou plusieurs programmes d'ordinateur, un ou plusieurs sous-programmes d'un programme, ou de manière plus générale à tout élément d'un programme ou d'un logiciel apte à mettre en oeuvre une fonction ou un ensemble de fonctions, selon ce qui est décrit ci-dessous pour le module concerné. Un tel composant logiciel est exécuté par un processeur de données d'une entité physique (terminal, serveur, etc) et est susceptible d'accéder aux ressources matérielles de cette entité physique (mémoires, supports d'enregistrement, bus de communication, cartes électroniques d'entrées/sorties, interfaces utilisateur, etc). De la même manière, un composant matériel correspond à tout élément d'un ensemble matériel (ou hardware) apte à mettre en oeuvre une fonction ou un ensemble de fonctions, selon ce qui est décrit ci-dessous pour le module concerné. Il peut s'agir d'un composant matériel programmable ou avec processeur intégré pour l'exécution de logiciel, par exemple un circuit intégré, une carte à puce, une carte à mémoire, une carte électronique pour l'exécution d'un micrologiciel (firmware), etc. 4. LISTE DES FIGURES D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante, donnée à titre d'exemple indicatif et non limitatif, et des dessins annexés, dans lesquels : - la figure 1 présente un organigramme d'un mode de réalisation particulier du procédé selon l'invention ; - la figure 2 présente la structure d'un composant électronique selon un mode de réalisation particulier de l'invention. 5. DESCRIPTION DÉTAILLÉE Sur toutes les figures du présent document, les éléments et étapes identiques sont désignés par une même référence numérique. Comme préalablement exposé, dans un mode de réalisation, l'invention se rapporte à un procédé de calculs cryptographique mis en oeuvre dans un composant électronique. La figure 1 présente un organigramme d'un mode de réalisation particulier du procédé selon l'invention. Plus précisément, la figure 1 présente une étape de détermination 100 d'un cofacteur d'une courbe elliptique qui est mise en oeuvre lors de l'exécution d'un protocole ou un algorithme cryptographique (tel par exemple le protocole ECC CDH, ou dans un protocole de validation des paramètres du domaine d'une courbe elliptique). Une telle étape de détermination 100 nécessite l'obtention de l'élément q (correspondant à une puissance entière d'un nombre premier) qui définit le corps fini à q éléments, ainsi que l'ordre du groupe générateur engendré par un point de base P, égal à n. La présente étape de détermination comprend : - une étape 101 de comparaison des nombres n et 6^Iq (consistant dans un mode de réalisation à comparer les valeurs de n2 et 36q); et - une étape 102 de détermination de la valeur de floor((q+2ceil(b/2)+1 +1)/n) si la condition suivante est vérifiée n>6^Iq (qui est validée ou non lors de la réalisation de l'étape 101), où la fonction ceil correspond à la fonction partie fractionnaire, floor correspond à la fonction partie entière, et b correspond à la taille q en nombre de bits de q. Cette valeur ainsi déterminée correspond à la valeur du cofacteur de la courbe elliptique considérée. En effet, en partant de l'inégalité suivante : (q+2((b "2)+1 1)In Or on a (q+2ceii(w2)'+/) - hn 6^Iq, on a bien h = floor((q+2 ceil(b/2)+1 +1)/n). Ainsi, cette technique de détermination d'un cofacteur d'une courbe elliptique est moins coûteuse que les techniques de l'art antérieur, puisque les techniques décrites dans les documents US-639443, US-625632 et US-2006/0059216 nécessitent un nombre de calculs plus important. La figure 2 présente la structure d'un composant électronique selon un mode de réalisation particulier de l'invention. Le composant électronique 200 comprend une mémoire vive 202 (ou RAM, pour « Random Access Memory » en anglais), qui fonctionne comme une mémoire principale d'une unité de calcul 201 (ou CPU, pour « Central Processing Unit » en anglais). La capacité de cette mémoire vive 202 peut être étendue par une mémoire vive optionnelle, connectée à un port d'expansion (non illustré sur la figure 2). Le composant électronique 200 comprend également une mémoire morte 203 (ou ROM, pour « Read Only Memory » en anglais). Après la mise sous tension, l'unité de calcul 201 est capable d'exécuter des instructions contenues dans la mémoire vive 202 et relatives à un programme d'ordinateur, une fois ces instructions chargées à partir de la mémoire morte 203 ou d'une mémoire externe (non illustrée sur la présente figure). Un tel programme d'ordinateur, s'il est exécuté par l'unité de calcul 201, permet l'exécution d'une partie ou la totalité des étapes mentionnées en figure 1, dans le cas où le dispositif 200 représente par exemple un composant électronique. Dans une variante de réalisation, les étapes mentionnées en figure 1, peuvent être implémentées sous forme de matériel dans un composant programmable de type FPGA (« Field Programmable Gate Array » en anglais) ou de type ASIC (« ApplicationSpecific Integrated Circuit » en anglais). Ainsi, le composant électronique peut, dans un mode de réalisation comprendre des moyens de comparaison entre n et 6^Iq, ainsi que des moyens de détermination d'une valeur de floor((q+2ceil(b/2)+1 +1)In) permettant de déterminer la valeur du cofacteur d'une courbe elliptique définie sur F g. REVENDICATIONS1. Procédé de calculs cryptographiques mis en oeuvre dans un composant électronique, comprenant une étape de détermination (100) du cofacteur d'une courbe elliptique E définie sur un corps fini Fq à q éléments, ladite courbe elliptique comprenant un point de base P possédant un ordre égal à n, ledit procédé étant caractérisé en ce que ladite étape de détermination comprend une étape de détermination (102) d'une valeur de floor((q+ 2ceil(b/2)+1 1) ) lorsque que n>6^Iq, où la fonction ceil correspond à la fonction dite partie fractionnaire, floor correspond à la fonction dite partie entière, et b correspond à la taille q en nombre de bits de q. 2. Procédé de calculs cryptographiques selon la revendication 1 caractérisé en ce que q = 2m où in est un entier supérieur ou égal à un. 3. Procédé de calculs cryptographiques selon la revendication 1 caractérisé en ce que q = p où p est un nombre premier supérieur ou égal à trois. 4. Procédé de calculs cryptographiques selon l'une quelconque des revendications 1 à 3 caractérisé en ce qu'il comprend une étape de comparaison (101) entre n et 6^Iq. 5. Procédé de calculs cryptographiques selon la revendication 4 caractérisé en ce que l'étape de comparaison (101) comprend : - une étape de détermination de A := 36q ; - une étape de détermination de B := n2 ; - une étape de comparaison de A et B. 6. Produit programme d'ordinateur, comprenant des instructions de code de programme pour la mise en oeuvre du procédé selon au moins une des revendications 1 à 5 lorsque ledit programme est exécuté sur un ordinateur. 7. Médium de stockage lisible par ordinateur et non transitoire, stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur ou un processeur pour mettre en oeuvre le procédé selon au moins une des revendications 1 à 5. 8. Composant électronique comprenant des moyens de calculs cryptographiques comprenant des moyens de détermination du cofacteur d'une courbe elliptique E définie sur un corps fini Fq à q éléments, ladite courbe elliptique comprenant un point de base P possédant un ordre égal à n, lesdits moyens de détermination étant caractérisés en ce quequ'ils comprennent des moyens de détermination d'une valeur de floor((q+2ceil(b/2)+1 +1)1n) lorsque n>6^1q, où la fonction ceil correspond à la fonction dite partie fractionnaire, floor correspond à la fonction dite partie entière, et b correspond à la taille de q en nombre de bits. 9. Composant électronique selon la revendication 8 caractérisé en ce que les moyens de comparaison comprennent des moyens de comparaison entre n et 6^Iq. 10. Module sécurisé comprenant un composant électronique selon l'une quelconque des revendications 8 et 9.