Brevet FR2881300A1 — publié le 20060728

PROCEDE DE GENERATION D'UNE COURBE ELLIPTIQUE, APPLICATION A UN PROCEDE CRYPTOGRAPHIQUE, ET PROCEDE CRYPTOGRAPHIQUE UTILISANT UNE TELLE COURBE. L'invention concerne, de façon générale, les techniques récentes de cryptographie et les procédés qui y sont employés. Plus précisément, l'invention concerne, selon un premier aspect, un procédé cryptographique utilisant une courbe elliptique représentée dans un plan par une équation contenant des premier et deuxième paramètres (a, b), un couplage bilinéaire, et des calculs dans un groupe fini de nombres entiers construit sur au moins une première règle de réduction réduisant chaque entier à son reste dans une division entière par un premier nombre premier (p) constituant un troisième paramètre, les éléments du groupe fini étant en bijection avec des points choisis sur la courbe elliptique et dont le nombre est lié à un quatrième paramètre (q), et ce procédé mettant en oeuvre des clefs publiques et privées dont chacune est représentée par un point déterminé de la courbe elliptique ou par un facteur multiplicatif entre deux points de cette courbe. De tels procédés forment la base des plus récentes techniques cryptographiques fondées sur un couplage 30 bilinéaire, par exemple un couplage de Weil. Un exemple illustre d'un tel procédé est donné dans l'article intitulé "Identity-Based Encryption from the Weil Pairing", et publié en 2003 dans SIAM Journal of Computing, Volume 32, N 3, pages 586 à 615 par Dan Boneh et Matthew Franklin. Les procédés actuels de ce type reposent sur l'utilisation de courbes elliptiques super-singulières. Or, le recours à de telles courbes implique des calculs complexes, qui peuvent être un obstacle à l'utilisation de ces procédés dans tous les cas où les capacités de calcul disponibles sont limitées. Dans ce contexte, l'invention a pour but de proposer une solution alternative, permettant la construction de courbes elliptiques non supersingulières et conduisant à un procédé cryptographique de mise en oeuvre simplifiée, bien que lui aussi fondé sur un couplage bilinéaire, par exemple un couplage de Weil. A cette fin, le procédé de l'invention, par ailleurs conforme à la définition générique qu'en donne le préambule ci-dessus, est essentiellement caractérisé en que ladite première règle de réduction est l'unique règle de réduction mise en oeuvre, et en ce que la courbe elliptique est obtenue par un processus de construction pas à pas attribuant directement audit groupe fini q * q points d'ordre q sur la courbe elliptique. Dans le cas où ce procédé cryptographique met au moins en oeuvre l'algorithme "SetUp" du protocole "Identity Based Encryption" tel que défini dans l'article précité et bien connu de l'homme du métier, le processus de construction pas à pas de ladite courbe elliptique est intégré à cet algorithme "SetUp". L'invention concerne également un procédé de génération d'une courbe elliptique représentée dans un plan par une équation contenant des premier et deuxième paramètres (a, b), comprenant des calculs dans un groupe fini de nombres entiers construit sur au moins une première règle de réduction réduisant chaque entier à son reste dans une division entière par un premier nombre premier (p) constituant un troisième paramètre, les éléments du groupe fini étant en bijection avec des points choisis sur la courbe elliptique et dont le nombre est lié à un quatrième paramètre (q), ce procédé étant caractérisé en ce qu'il comprend les opérations consistant à : - générer au hasard un nombre premier en tant que quatrième paramètre (q); - choisir, en tant que cinquième paramètre, un nombre entier (d) répondant aux contraintes inhérentes à la multiplication complexe par des nombres de la forme [u + v*racine(-d)] où u et v sont des entiers relatifs; - générer au hasard deux nombres entiers auxiliaires (n, m) ; - calculer le nombre entier représenté par la somme: 1 + 2.n.q + q^2.(n^2 + d.m^2); - vérifier que le nombre entier calculé précédemment est premier; dans l'affirmative, adopter le nombre entier calculé en tant que troisième paramètre (p); dans la négative, retourner à l'opération consistant à générer au hasard deux nombres entiers auxiliaires (n, m) en changeant la valeur de l'un au moins de ces deux entiers auxiliaires; et construire les premier et deuxième paramètres (a, b) en appliquant au troisième paramètre (p) la technique de multiplication complexe par [u + v*racine(-d)] où u et v sont des entiers relatifs, ce dont il résulte que la courbe elliptique répond à l'équation y^2 = x^3 + a. x + b, que le groupe fini comprend q*q points d'ordre q sur la courbe elliptique, et que la première règle de réduction est l'unique règle de réduction pour construire le groupe fini, les calculs étant ainsi simplifiés. De préférence, le quatrième paramètre (q) est un nombre premier d'au moins 160 bits. Il peut également être avantageux de prévoir que le cinquième paramètre (d) soit un nombre entier au plus 30 égal à 1000. Dans un mode de réalisation préféré de l'invention, le cinquième paramètre (d) est égal à 3, ce dont il résulte que le premier paramètre (a) est nul. Le procédé de génération de courbe elliptique tel que précédemment défini est idéalement applicable à la réalisation du processus de construction pas à pas du procédé cryptographique évoqué en premier lieu. D'autres caractéristiques et avantages de l'invention ressortiront clairement de la description qui en est faite ci-après, à titre indicatif et nullement limitatif, en référence à son application particulière au protocole "Identity Based Encryption", également connu de l'homme du métier sous l'acronyme "IBE" et défini dans l'article précité de Dan Boneh et Matthew Franklin. Le protocole IBE comprend tout d'abord un algorithme dit "SetUp" (c'est-àdire "installation" ou "lancement"), qui permet à un organisme de confiance de générer des paramètres globaux du système de cryptographie et une clef maître. Le protocole IBE comprend d'autre part un algorithme dit "Extract" (c'està-dire "extraction"), qui permet, à partir de la clef maître et d'une clef publique tout à fait quelconque, de générer une clef privée. Le caractère tout à fait quelconque de la clef publique permet à chaque utilisateur d'utiliser, en tant que clef publique, une chaîne de caractères qui lui est tout à fait spécifique et néanmoins facile à mémoriser, par exemple son adresse Internet. Le protocole IBE comprend enfin deux algorithmes complémentaires l'un de l'autre, notés "Encrypt" et "Decrypt", (c'est-à-dire respectivement "chiffrement" et "déchiffrement"). L'algorithme "Encrypt" permet d'obtenir un message crypté à partir d'un message en clair par application de la clef publique, et l'algorithme "Decrypt" permet de retrouver le message en clair à partir du message crypté par application de la clef privée. Parmi les paramètres globaux du système figurent: - une courbe elliptique d'équation y^2 = x^3 + a. x + b, où a et b constituent des premier et deuxième paramètres, - un nombre premier (p) constituant un troisième paramètre, et - un autre nombre premier (q) constituant un quatrième 25 paramètre. En fait, chacune des clefs publiques et privées est représentée par un point déterminé de la courbe elliptique ou par un facteur multiplicatif entre deux points de cette courbe, ces points étant en bijection avec des éléments d'un groupe fini de nombres entiers, dont le nombre est lié au quatrième paramètre (q). Le but premier de l'invention est de construire les paramètres a, b, p, et q de manière que les calculs devant être effectués aussi bien par l'autorité de confiance que par les utilisateurs soient les plus simples possibles. Dans l'art antérieur connu, le groupe fini de nombres entiers dans lequel sont effectués les calculs de l'algorithme "SetUp" est construit sur une première règle de réduction réduisant chaque entier à son reste dans une division entière par le premier nombre premier (p) et sur une deuxième règle de réduction faisant intervenir un polynôme. Dans sa définition la plus générique, l'invention consiste à prévoir que la première règle de réduction soit l'unique règle de réduction mise en oeuvre, et à obtenir la courbe elliptique par un processus de construction pas à pas attribuant directement au groupe fini q * q points d'ordre q de cette courbe elliptique. Dans le cas d'utilisation du protocole "Identity Based Encryption", le processus de construction pas à pas de la courbe elliptique est donc intégré à l'algorithme "SetUp". La courbe elliptique est par exemple obtenue par la mise en oeuvre des opérations suivantes: 1 - générer au hasard un nombre premier, ce nombre étant destiné à constituer le quatrième paramètre (q); 2 - choisir, en tant que cinquième paramètre, un nombre entier (d) répondant aux contraintes inhérentes à la multiplication complexe par des nombres de la forme [u + v*racine(-d)] où u et v sont des entiers relatifs; 3 - générer au hasard deux nombres entiers auxiliaires (n, m) ; 4 - calculer le nombre entier (p0) représenté par la somme: 1 + 2.n.q + q^2.(n^2 + d.m^2); 5 vérifier que le nombre entier (p0) calculé précédemment est premier; dans l'affirmative, adopter le nombre entier calculé (p0) en tant que troisième paramètre (p); dans la negative, retourner à l'opération (3) consistant à générer au hasard deux nombres entiers auxiliaires (n, m) en changeant la valeur de l'un au moins de ces deux entiers auxiliaires; et 6 - construire les premier et deuxième paramètres (a, b) en appliquant au troisième paramètre (p) la technique de multiplication complexe par [u + v*racine(-d)] où u et v sont des entiers relatifs. La mise en oeuvre de ces opérations a pour effet que la courbe elliptique répond effectivement à l'équation y^2 = x^3 + a. x + b, que le groupe fini comprend q*q points d'ordre q sur la courbe elliptique, et que la première règle de réduction est l'unique règle de réduction pour construire le groupe fini. La technique de multiplication complexe, qui ne doit pas être confondue avec la multiplication de deux nombres complexes, est bien connue de l'homme du métier et notamment décrite dans l'ouvrage: "Blake, I.F., Seroussi, G., and Smart, N.P., Elliptic Curves in Cryptography, London Mathematical Society Lecture Notes Series 265, Cambridge University Press, 1999". Le quatrième paramètre (q) est par exemple un nombre premier de 160 bits ou plus, le cinquième paramètre (d) 15 pouvant être un nombre entier égal ou inférieur à 1000. Dans le cas où le cinquième paramètre (d) est égal à 3, les calculs sont particulièrement simplifiés puisque le premier paramètre (a) est alors nul, l'équation de la courbe elliptique se réduisant à : y^2 = x^3 + b. Dans ce cas, la courbe elliptique peut être obtenue par 25 la mise en oeuvre des opérations suivantes: 1 - générer au hasard un nombre premier, par exemple de 160 bits, ce nombre étant destiné à constituer le quatrième paramètre (q); 2 - générer au hasard deux nombres entiers auxiliaires (n, m), par exemple de 352 bits chacun; 3 - calculer le nombre entier (p0) représenté par la somme: 1 + 2.n.q + q^2.(n^2 + 3.m^2); 4 - vérifier que le nombre entier (p0) calculé précédemment est premier; dans l'affirmative, adopter le nombre entier calculé (p0) en tant que troisième paramètre (p); dans la négative, retourner à l'opération (2) consistant à générer au hasard deux nombres entiers auxiliaires (n, m) en changeant la valeur de l'un au moins de ces deux entiers auxiliaires; - choisir au hasard un nombre entier b jusqu'à ce que l'ordre de la courbe elliptique d'équation y^2 = x^3 + b soit égal à q^2.(n^2 + 3.m^2), et 6 - choisir au hasard un point sur cette courbe et opérer une multiplication scalaire par l'entier (n^2 + 3.m^2). Le résultat est un point de la courbe, d'ordre q. 25 La mise en oeuvre du procédé précédemment décrit donne par exemple les valeurs particulières suivantes. q = 4297242806128994185033021941702087560370368619631. 7057491073750168475624047105694932863429081910233925327 1529893442070457891195274735458620625415190633449567948 5740755687689682603079627276015128159703948632280242718 7040926033208055563751891758532222532293275449078013248 088539370376808014228321266803863367. La courbe a alors l'équation y^2 = x^3 + 8. Grâce à la simplification des calculs à laquelle elle conduit, l'invention facilite la mise en oeuvre d'un procédé cryptographique utilisant un couplage bilinéaire sur une carte à puce équipée seulement d'un crypto-coprocesseur conçu pour effectuer des calculs rapides modulo un grand nombre. 12 REVENDICATIONS. 1. Procédé cryptographique utilisant une courbe elliptique représentée dans un plan par une équation contenant des premier et deuxième paramètres (a, b), un couplage bilinéaire, et des calculs dans un groupe fini de nombres entiers construit sur au moins une première règle de réduction réduisant chaque entier à son reste dans une division entière par un premier nombre premier (p) constituant un troisième paramètre, les éléments du groupe fini étant en bijection avec des points choisis sur la courbe elliptique et dont le nombre est lié à un quatrième paramètre (q), et ce procédé mettant en oeuvre des clefs publiques et privées dont chacune est représentée par un point déterminé de la courbe elliptique ou par un facteur multiplicatif entre deux points de cette courbe, caractérisé en que ladite première règle de réduction est l'unique règle de réduction mise en oeuvre, et en ce que la courbe elliptique est obtenue par un processus de construction pas à pas attribuant directement audit groupe fini q * q points d'ordre q sur la courbe elliptique. 2. Procédé cryptographique selon la revendication 1, mettant au moins en oeuvre l'algorithme "SetUp" du protocole "Identity Based Encryption", caractérisé en ce que le processus de construction pas à pas de ladite courbe elliptique est intégré à cet algorithme. 3. Procédé de génération d'une courbe elliptique représentée dans un plan par une équation contenant des premier et deuxième paramètres (a, b), comprenant des calculs dans un groupe fini de nombres entiers construit sur au moins une première règle de réduction réduisant chaque entier à son reste dans une division entière par un premier nombre premier (p) constituant un troisième paramètre, les éléments du groupe fini étant en bijection avec des points choisis sur la courbe elliptique et dont le nombre est lié à un quatrième paramètre (q), caractérisé en ce qu'il comprend les opérations consistant à : - générer au hasard un nombre premier en tant que quatrième paramètre (q); - choisir, en tant que cinquième paramètre, un nombre entier (d) répondant aux contraintes inhérentes à la multiplication complexe par des nombres de la forme [u + v*racine(-d)] où u et v sont des entiers relatifs; - générer au hasard deux nombres entiers auxiliaires (n, m); - calculer le nombre entier représenté par la somme: 25 1 + 2.n.q + q^2.(n^2 + d.m^2); - vérifier que le nombre entier calculé précédemment est premier; dans l'affirmative, adopter le nombre entier calculé en tant que troisième paramètre (p); dans la négative, retourner à l'opération consistant à générer au hasard deux nombres entiers auxiliaires (n, m) en changeant la valeur de l'un au moins de ces deux entiers auxiliaires; et - construire les premier et deuxième paramètres (a, b) en appliquant au troisième paramètre (p) la technique de multiplication complexe par [u + v*racine(-d)] où u et v sont des entiers relatifs, ce dont il résulte que la courbe elliptique répond à l'équation y^2 = x^3 + a. x + b, que le groupe fini comprend q*q points d'ordre q sur la courbe elliptique, et que la première règle de réduction est l'unique règle de réduction pour construire le groupe fini, les calculs étant ainsi simplifiés. 4. Procédé de génération d'une courbe elliptique suivant la revendication 3, caractérisé en ce que le quatrième paramètre (q) est un nombre premier d'au moins 160 bits. 5. Procédé de génération d'une courbe elliptique suivant la revendication 3 ou 4, caractérisé en ce que le cinquième paramètre (d) est égal à 3, ce dont il résulte que le premier paramètre (a) est nul. 6. Application du procédé de génération selon l'une quelconque des revendications 3 à 5 à la réalisation du processus de construction pas à pas du procédé cryptographique suivant l'une quelconque des revendications 1 et 2.