Brevet FR2807898A1 — publié le 20011019

PROCEDE DE CRYPTOGRAPHIE COURBES ELLIPTIQUES La présente invention concerne un procédé de cryptographie sur courbe elliptique. Un tel procédé est basé sur l'utilisation d'un algorithme à clé publique, et peut s'appliquer à la génération de signatures numériques probabilistes d' message et/ou à un protocole d'échange de clé et/ou à un algorithme de chiffrement d'un message. Un algorithme de génération et de vérification de signatures numériques consiste à calculer un ou plusieurs entiers, en général une paire, appelés la signature et associés à message donné afin de certifier l'identité du signataire et l'intégrité du message signé. La signature est dite probabiliste lorsque l'algorithme fait appel à un aléa dans la génération de la signature, aléa étant secret et régénéré à chaque nouvelle signature. Ainsi, un même message transmis par un même utilisateur peut avoir plusieurs signatures distinctes. Les algorithmes de protocole d'échange de clé et de chiffrement utilisent également un aléa k secret et régénéré à chaque nouvelle application de l'algorithme. Les algorithmes de cryptographie à clé publique sur courbes elliptiques sont de plus en plus utilisés. Un tel algorithme est basé utilisation de points P(x,y) d'une courbe E vérifiant la relation y2 + xy = x' + ax` + b avec a et b, deux éléments d'un corps fini. Des opérations d'addition ou de soustraction sont effectuées sur les points P la courbe E. L'opération consistant à additionner k fois le même point P est appelée la multiplication scalaire de P par k, et correspond à un point C de la courbe elliptique défini par C(x',y' )= k#P(x,y). Un exemple d'un tel algorithme peut être illustré par ECDSA (de l'anglais Elliptic Curve Digital Standard Algorithm) qui est un algorithme de génération et vérification de signatures numériques probabilistes. paramètres du ECDSA sont - E, une courbe elliptique définie sur ensemble ZP, le nombre de points de la courbe E étant divisible par un grand premier N, en général N>2160 P(x,y), un point donné de la courbe elliptique E, clé secrète d est un nombre aléatoirement fixé entre 0 et N-1, et la clé publique Q est liée à d par la relation de multiplication scalaire Q(xl,yl)=d-P(x,y) . Soit m, le message à envoyer. La signature ECDSA de m est la paire d'entiers (r, s) compris dans l'intervalle [1, N-1] et définis comme suit soit k, un nombre aléatoire choisi dans l'intervalle [1, N-1], k étant un aléa régénéré à chaque signature ; Calcul du point C obtenu par la multiplication scalaire C (x' , y') =k - P (x, y) ; - r = x' mod N ; - s = k-1 ( h (m) + d- r) mod N ; avec h(m) le résultat de l'application d'une fonction de hachage h, qui est une fonction cryptographique pseudo aléatoire, au message initial m. La vérification de la signature s'effectue, à l'aide des paramètres publics (E, P, N, Q), comme suit réalise des calculs intermédiaires w = s-1 mod N ; - u1 = h (m) - w mod N ; - u2 = r-w mod N ; - on réalise une opération d'addition et de multiplication scalaire en calculant le point de la courbe E correspondant à u1P + u2Q = (xo, yo) ; on verifie si v = xo mod N ' r. Si cette égalité est vrai, la signature est authentique. La genération de la signature (r, s) a éte réalisée avec la clé secrète d et un nombre aléatoire k secret et différent pour chaque signature, et sa vérification avec paramètres de la clé publique. Ainsi, n'importe qui peut authentifier une carte et son porteur sans détenir sa clé secrète. coût d'exécution d'un tel algorithme de signature sur courbe elliptique est directement lié à la complexité et la rapidité de l'opération de multiplication scalaire pour définir la point -k-P. Des améliorations au procédé de cryptographie sur courbes elliptiques ont été mises au point pour faciliter et accélérer cette opération de multiplication scalaire. En particulier, l'article de J.A. Solinas An Improved Algorithm for Arithmetic on a Family of Elliptic Curves paru dans Proceedings of Crypto'97, Springer Verlag, décrit une amelioration possible. Afin d'accélérer le procédé de calcul d'une multiplication scalaire dans le cadre d'un algorithme sur courbe elliptique E, il a ainsi été envisagé de travailler sur une famille particulière courbes elliptiques, dites courbes elliptiques binaires anormales ou courbes de Koblitz, sur lesquelles un opérateur particulier est disponible, appele opérateur de Frobenius, permettant de calculer plus rapidement les opérations de multiplication scalaire. Les courbes de Koblitz sont définit sur l'ensemble mathématique GF(2") par la relation y2 + xy - x3 + axe + 1 avec aE (0, 1 } L'opérateur de Frobenius T est définit comme T [P (x, y) = (x2, y2) avec la relation i2+2 = (-1) 1-a T Appliquer l'opérateur T à un point donné P de la courbe E constitue une opération rapide car on travaille dans l'ensemble mathématique GF(2"), n étant la taille du corps fini, par exemple n=163. Afin de faciliter le calcul de la multiplication scalaire C y,)= k- P (x, y) , on décompose l'entier k de manière à revenir à des opérations d'addition et de soustraction. On définit ainsi la forme non adjacente de l'entier par le NAF (de l'anglais Non Adjacent Form) qui consiste à écrire un entier k sous la forme d'une somme k = E(i= à 1-1) ei2' avec eiE (-1, 0, 1 } et 1-n. Dans le cas d'une courbe elliptique de Koblitz, le NAF peut être exprimé à l'aide de l'opérateur de Frobenius : = E (i=0 à 1) eili Ainsi, l'opération de multiplication scalaire de P par k revient à appliquer l'opérateur de Frobenius au point P, ce qui est facile et rapide. En outre, le calcul de la multiplication scalaire k#P peut être encore accéléré par le précalcul et la mémorisation de quelques couples (ki, Pi= ki - P) , ces couples pouvant avantageusement être stockés dans la mémoire du dispositif mettant en #uvre l'algorithme de signature. On rappelle en effet que P fait parti des paramètres publics de la clé de l'algorithme de signature. Pour un aléa k de 163 bits, on peut ainsi, en stockant 42 couples de multiplication scalaire (ki,Pi), réduire le nombre d'opérations d'addition/ soustraction à 19 au lieu de 52 sans aucun précalcul. La présente invention a pour objet un procédé de cryptographie sur courbe elliptique qui permet de réduire davantage le nombre d'additions de la multiplication scalaire. L'invention concerne plus particulièrement un procédé de cryptographie pour la génération de signatures numériques probabilistes et/ou pour un protocole d'échange de clé et/ou pour un algorithme de chiffrement, ledit procédé étant basé sur l'utilisation d'un algorithme à clé publique sur courbe elliptique (E) binaire anormale (Courbe de Koblitz) sur laquelle un point P (x, y) est sélectionné, des couples (ki, Pi) étant mémorisés avec Pi le point correspondant à la multiplication scalaire du point P par ki, ledit procédé comprenant des étapes consistant à générer un aléa k et à calculer un point C correspondant à la multiplication scalaire de P par k (C=k#P), caractérisé en ce que la génération dudit aléa k et le calcul du point C sont effectués simultanément. Selon une application, l'algorithme cryptographique de génération d'une signature numérique probabiliste est le ECDSA (de l'anglais Elliptic Curve Digital Standard Algorithm). Selon une autre application, l'algorithme cryptographique de protocole d'échange de clé est le ECDH (de l'anglais Elliptic Curve Diffie-Hellmann). Selon une caractéristique, le procédé est basé sur l'utilisation d'une courbe de Koblitz définie sur l'ensemble mathématique GF(2") sur laquelle un opérateur dit de Frobenius T [P (x, y) ] _ (x2, y2) est disponible, le procédé étant caractérisé en ce qu'il comporte les étapes suivantes - initialiser l'aléa k=0 et le point C=0, - réaliser une boucle pour j allant de 1 a niter, ladite boucle consistant à - genérer les aléas suivants à chaque nouvelle itération - a, compris entre 0 et n, avec n la taille du corps fini sur lequel la courbe est définie, - u (-l, 1}, - i compris entre O et t, avec t le nombre de couples (ki, Pi) mémorisés, - calculer le point CI =Cj_1+ u * Ta # Pi - genérer l'aléa kj = kj_1 + u # ki , Ta - convertir k en entier en fin de boucle, - présenter simultanément l'aléa k et le point C=k Selon une caractéristique, le nombre t de couples (ki,Pi) mémorisés est compris entre 35 et 45. Selon une autre caractéristique, le nombre d'itérations de la boucle (niter) est fixé entre 10 et 12. Selon une autre caractéristique, la taille du corps mathématique n sur lequel 1a courbe de Koblitz est définie est égale à 163. L'invention concerne également un dispositif sécurisé, de type carte à puce, ou un dispositif de calcul, de type ordinateur muni d'un logiciel de chiffrement, comportant un composant électronique apte à mettre #uvre le procédé de signature selon l'invention Le procédé selon l'invention présente l'avantage de réduire le temps de calcul du produit scalaire de P par k, constitue une étape essentielle dans la mise en oeuvre d'un procédé de cryptographie sur courbe elliptique, d'une part en générant l'aléa k simultanément au calcul du produit scalaire k#P et d'autre part en réduisant le nombre d'opérations d'additions par le précalcul de couples ki, Pi=ki # P. particularités et avantages de l'invention apparaîtront plus clairement à la lecture de la description qui suit faite en référence à l'algorithme ECDSA et donnée à titre d'exemple illustratif et non limitatif. Le procédé selon l'invention peut en effet être également appliqué à un protocole d'échange de clé ou ' un algorithme de chiffrement par exemple. Soit E, une courbe elliptique de Koblitz définie sur l'ensemble GF(2") avec n=163, la taille du corps mathématique sur lequel on travail, et soit P(x,y) un point donné de cette courbe. L'opérateur de Frobenius z [P (x, y) ] _ (x2, y2) est alors disponible et constitue une opération rapide etant donné le corps GF(2") sur lequel on travaille. On calcul dans un premier temps un certain nombre de couples (ki, Pi=k-P) qui sont mémorisés dans le composant mettant en #uvre le procédé de signature (un micro contrôleur de carte à puce par exemple). On fixe le nombre de couples à t compris entre 35 et qui constitue un compromis entre la place mémoire occupée et accélération souhaitée du procédé de calcul de génération de la signature. procédé selon la présente invention consiste à accélérer le procédé de génération d'une signature probabiliste en utilisant des couples Pi) précalculés et mémorisés en en générant l'aléa en même temps que le calcul du point C=k-P. Dans un premier temps les valeurs de C et k sont initialisés à 0. On réalise alors une boucle sur j de nïter iterations qui effectue les opérations suivantes - génération des aléas suivants à chaque nouvelle itération de j - r, compris entre 0 et n, - u 1-1,1}, - i compris entre 0 et t, - calcul de Cj = Cj_1 + u--c'-P, - calcul de kj = kj_1 + u - k; - z` On obtient alors en sortie de la boucle, l'aléa k l'on convertit en entier, et le point C correspondant à la multiplication scalaire de P k. La signature (r,s) est ensuite générée selon la procédure classique du ECDSA, ou d'un autre algorithme exploitant des courbes elliptiques de Koblitz, avec les valeurs de k et C définis selon le procède de l'invention. La génération de k simultanément au calcul du point C permet d'accélérer le procédé de génération de signature, en particulier en réduisant le nombre d'additions nécessaire au calcul de la multiplication scalaire de P par k. Le nombre d'additions pour le calcul du point C est en effet de niter -1. Selon le degré de sécurité et les performances souhaitées, on fixe nit,, compris entre 10 12 itérations. Ainsi, avec k un entier de 163 bits et en mémorisant environ 40 couples (ki,Pi), on peut calculer la multiplication scalaire k-P en effectuant seulement 9 à 11 opérations d'additions. REVENDICATIONS 1. Procédé de cryptographie pour la génération de signatures numériques probabilistes et/ou pour un protocole d'échange de clé et/ou pour un algorithme de chiffrement, ledit procédé étant basé sur l'utilisation d'un algorithme à clé publique sur courbe elliptique (E) binaire anormale (Courbe de Koblitz) sur laquelle un point P y) est sélectionné, des couples (ki, Pi) étant mémorisés avec Pi le point correspondant à la multiplication scalaire du point P par ki, ledit procédé comprenant étapes consistant à générer un aléa (k) et à calculer un point C correspondant à la multiplication scalaire de P par k (C=k-P), caractérisé en ce que génération dudit aléa (k) et le calcul du point C sont effectués simultanément. 2. Procédé selon la revendication 1, caractérisé en ce que l'algorithme cryptographique pour la génération d'une signature numérique probabiliste est le ECDSA (de l'anglais Elliptic Curve Digital Standard Algorithm). 3. Procédé selon la revendication 1, caractérisé en ce que l'algorithme de cryptographie de protocole d'échange clé est le ECDH (de l'anglais Elliptic Curve Diffie Hellmann). 4. Procédé selon l'une quelconques des revendications précédentes, le procédé étant basé sur l'utilisation d'une courbe de Koblitz (E) définie sur l'ensemble mathématique GF(2") sur laquelle un opérateur dit de Frobenius i [P (x, y) ]=(X-;', y2) est disponible, caractérisé en ce qu'il comporte les étapes suivantes - initialiser l'aléa k=0 et le point =0, réaliser une boucle pour j allant de 1 à niter.- ladite boucle consistant à - générer les aléas suivants à chaque nouvelle itération de j . - a, compris entre 0 et n, avec n la taille du corps fini sur lequel courbe (E) est définie, - u {-1,1}, - i compris entre 0 et t, avec t le nombre de couples (ki, Pi) mémorisés, - calculer le point Cj =Cj_i+ u ' T`" Pi - générer l'aléa k, = kj_1 + u # ki * T@ convertir k en entier en fin de boucle, - présenter simultanément l'aléa k et le point C=k-P. 5. Procédé selon la revendication 4, caractérisé en ce le nombre (t) de couples (ki,Pi) mémorisés est compris entre 35 et 45. . Procédé selon la revendication 4, caractérisé en ce que le nombre d'itérations de la boucle (niter) est fixé entre 10 et 12. 7. Procédé selon la revendication 4, caractérisé en ce que la taille du corps mathématique n sur lequel la courbe de Koblitz (E) est définie est égale à 163. 8. Dispositif sécurisé, de type carte à puce, caractérisé en ce qu'il comporte un composant électronique apte à mettre en #uvre le procédé de signature selon les revendications 1 à 7. 9. Dispositif calcul, de type ordinateur muni d'un logiciel de chiffrement, caractérisé en ce qu'il comporte un composant électronique apte à mettre en oeuvre le procédé signature selon les revendications 1 à 7.