Brevet FR2879384A1 — publié le 20060616

p -p+l l ' p6 -1 1m E, r.P ePublic Génération r x=C(r.ID, s.P) E=chiffr, (msg) ID K.(s.1D, r.P) msg déchiff,, (E) L'invention concerne un procédé de traitement de données utilisant une fonction de couplage et un dispositif associé. Les algorithmes cryptographiques utilisent couramment des clés dans les procédés de chiffrement ou de déchiffrement des messages et lors de l'apposition ou de la vérification d'une signature électronique. Dans les systèmes à clé privée et clé publique, un utilisateur quelconque peut chiffrer un message ou vérifier une signature avec une clé publique correspondant à une clé privée détenue par un seul utilisateur et qui lui permet de déchiffrer le message ou d'apposer sa signature. Un tel système cryptographique est basé sur le fait que la 15 connaissance de la clé publique ne permet pas la connaissance de la clé privée associée. La clé publique est ainsi distribuée par le détenteur de la clé privée aux utilisateurs qui veulent communiquer avec lui. Il peut arriver toutefois qu'un usurpateur arrive à convaincre les utilisateurs d'utiliser une fausse clé publique dont cet usurpateur connaît la clé privée associée. Dans ce cas, l'utilisateur chiffre son message avec la fausse clé publique et le message est ainsi déchiffrable par l'usurpateur. Afin d'éviter ces problèmes, on doit avoir recours à une autorité centrale de certification (parfois dénommée CA de l'anglais "Certification Authority') qui est contactée par l'utilisateur qui souhaite vérifier l'authenticité d'une clé publique. Un tel système est donc relativement complexe à mettre en oeuvre si l'on veut atteindre un bon niveau de sécurité. On a de ce fait envisagé une approche qui évite toute ambiguïté sur l'authenticité de la clé publique en utilisant, pour chiffrer un message ou vérifier une signature, une information relative à l'identité du destinataire du message ou du signataire. Cette approche, dénommée en général "cryptographie basée sur l'identité" (ou IBC de l'anglais "Identity based cryptography') a été proposée dans l'article "Identitybased cryptosystems and signature schemes", de A. Shamir, in Advances in Cryptology CRYPTO'84, LNCS196, pp. 47-53 (Springer-Verlag Berlin Heidelberg 1985). La mise en oeuvre pratique d'une telle approche n'a été introduite que plus récemment, par exemple dans l'article "Identity-based Encryption from the Weil Pairing" de D. Boneh et M. Franklin in Advances in Cryptology-CRYPTO'2001, Lecture Notes in Computer Science, Vol. 2139, pp. 213-229 (Springer-Verlag 2001). Ces réalisations pratiques utilisent des fonctions dénommées couplages définies sur un corps fini à p éléments (où p est un nombre premier généralement grand) au moyen d'une courbe elliptique sur le corps fini. Ces fonctions sont bilinéaires, ce qui permet d'obtenir un résultat identique que le calcul soit fait par l'émetteur du message (qui utilise par exemple pour paramètres l'identité du destinataire multipliée par un nombre aléatoire r et un paramètre public s.P) ou par le destinataire du message (qui utilise par exemple sa clé privée, égale à s multiplié par son identité, et le produit reçu également de l'émetteur du nombre aléatoire r et du paramètre public P). Il est possible d'utiliser cette technique pour chiffrer et déchiffrer des données en utilisant une même clé. Une telle approche est également utilisable pour signer et authentifier un message. Un couplage utilisé dans ce cadre est le couplage de Tate, défini lorsqu'il est appliqué aux paramètres P, Q par une formule du type: f' pA I (P,Q)=fp(AQ) r où 1 est un entier premier avec p qui divise le cardinal des points de 25 la courbe elliptique, k le plus petit entier tel que 1 divise (pk-1), fp une fonction définie sur la courbe elliptique et AQ le diviseur associé au point Q. Pour plus de détails sur cette définition, on peut consulter l'article "Efficient Algorithms for Pairing-Based Cryptosystems" de P. Barreto et al. in Advances in Cryptology, CRYPTO'2002, Lecture Notes in Computer Science, Vol. 2442, pp. 354-368, 2002. Lors de la mise en oeuvre du calcul d'une telle fonction dans un algorithme cryptographique, on souhaite réduire au minimum possible le coût calculatoire de l'exponentiation à la puissance (pk-lyl. L'invention propose ainsi un procédé de traitement de données 5 utilisant une fonction de couplage appliquée à au moins un élément d'un corps fini à p6 éléments et impliquant une exponentiation à une puissance entière de la forme p6 -1, où p et 1 sont des nombres entiers, 1 caractérisé en ce qu'il comprend les étapes de: exponentiation à un entier m que divise p2 - p+1 - - exponentiation à la puissance plm 1 en utilisant l'endomorphisme de Frobenius (p. Grâce à la constatation que Pz p +1 est un entier et que P6 -1 l lm peut donc s'écrire sous forme d'un polynôme en p, on profite au mieux de la technique consistant à utiliser l'endomorphisme de Frobenius, malgré la présentation sous forme de fraction de l'exposant pG -1 l Le coût calculatoire de l'ensemble, dominé par le coût de l'exponentiation à la puissance m (par exemple par des méthodes classiques), reste ainsi limité. On peut par exemple représenter l'élément du corps fini F p, par les 20 coefficients d'un polynôme de l'ensemble -Fp [X, où a est un nombre entier, ce XG+a qui simplifie notamment le calcul de l'endomorphisme de Frobenius. On peut prendre par exemple m = pz - p +1 Dans ce cas, si on note x l'élément à élever à la puissance pli 1 l'exponentiation à la puissance peut être réalisée de façon particulièrement simple par les étapes suivantes: - calcul de /3 = xço[xço(x)] ; - calcul de ço[o(fi)] 33 En variante, on peut prendre m = (p2 -p+l)(p- 1) L'exponentiation à la puissance p6 -1 peut alors être réalisée de lm manière pratique par les étapes suivantes: - calcul de l3 = xço[xço(x)] ; 10 - calcul de f3rp(/3). L'invention propose également un programme d'ordinateur apte à être chargé dans un appareil programmable, caractérisé en ce qu'il contient des instructions pour mettre en oeuvre le procédé précédemment évoqué. L'invention propose en outre un dispositif de traitement de données avec des moyens aptes à utiliser une fonction de couplage appliquée à au moins un élément d'un corps fini à p6 éléments FI), et impliquant une exponentiation à une puissance entière de la forme p6l, où p et l sont des nombres entiers, caractérisé en ce qu'il comprend: - des moyens pour effectuer une exponentiation à un entier m que divise p2 p+l 1 ' - des moyens pour effectuer une exponentiation à la puissance b P -1 en utilisant l'endomorphisme de Frobenius (p. lm Les caractéristiques possibles du procédé et les avantages qui en découlent s'appliquent également à ce dispositif. L'invention est d'ailleurs particulièrement adaptée à un dispositif du type carte à microcircuit, mais peut naturellement être appliquée à d'autres dispositifs. D'autres caractéristiques et avantages de l'invention apparaîtront à la lumière de la description qui suit, faites en référence aux dessins annexés dans lesquels: - la figure 1 représente l'architecture générale d'un système de cryptographie basé sur l'identité ; - la figure 2 représente schématiquement une communication sécurisée au moyen du système de cryptographie présenté à la figure 1. On décrit à présent des exemples de réalisation de l'invention dans le cadre de la cryptographie basée sur l'identité. Une solution pour la mise en oeuvre d'un tel système est de s'appuyer sur un corps fini K à p éléments, généralement noté Fp, (où p est par exemple de la forme q" avec q un nombre premier dénommé "caractéristique de K" et n un entier positif dénommé "degré d'extension de K" on peut prendre n=1) et sur une courbe elliptique E(K) définie sur ce corps K, par exemple par l'équation y2=x3+ax+y et de manière analogue sur F, pour k>0. On utilisera ici k=6. On notera ID l'identité d'un utilisateur ou sa représentation dans E(K), les deux étant directement liés selon les principes de la cryptographie basés sur l'identité. Afin de permettre une communication sécurisée entre l'utilisateur ID (représenté par la référence 6 sur les figures) et tout autre utilisateur 2 (représenté par la référence 5) du public (représenté par la référence 4), un centre de génération de clé 2 (ou KGC de l'anglais "Key Generation Center") publie une clé publique P, ainsi que son produit s.P par un secret s (c'est-à-dire P+P+...+P s fois), comme schématiquement représenté à la figure 1 par la flèche 8. P est un point de la courbe E(F k) et il n'est pas possible d'obtenir le secret s lorsque l'on connaît P et s.P, d'où la sécurité du système. Le centre de génération de clé 2 met également à la disposition du public 4 les données nécessaires à la connaissance du corps K et de la courbe E(F) utilisés. Le centre de génération de clé 2 communique à l'utilisateur ID par une liaison sécurisée 10 le produit s.lD. Une telle communication sécurisée est par exemple réalisée par établissement d'une communication électronique sécurisée ou par la transmission à l'utilisateur ID d'une carte à microcircuit dans laquelle est mémorisée la valeur s.lD. Les étapes essentielles de la transmission d'un message avec chiffrement d'un utilisateur à l'utilisateur ID sont représentées à la figure 2. L'utilisateur a, génère une valeur pseudo-aléatoire r au moyen d'un procédé de génération de valeur aléatoire. Il détermine ensuite une clé K au moyen d'une fonction de couplage C selon la formule: K =C(r.ID, s.P). La valeur ID correspond à l'identité de l'utilisateur auquel le message doit être adressé et est donc connue de l'utilisateur a,, qui peut dès lors facilement calculer le produit r.ID. La valeur du produit s. P est quant à elle publique comme déjà mentionné. L'utilisateur a, procède alors au chiffrement d'un message à envoyer msg au moyen d'un algorithme de chiffrement à clé symétrique chiffra en utilisant comme clé la clé K précédemment déterminée. Le message chiffré à envoyer E peut donc s'exprimer par: E=chiffra (msg). L'utilisateur k peut alors envoyer le message chiffré E à l'utilisateur ID en joignant le produit r.P qui sera utilisé par l'utilisateur ID comme décrit dans la suite. On peut noter à ce sujet que le produit r.P est facilement calculable par l'utilisateur a, qui connaît la valeur aléatoire r et la clé publique P, mais que la connaissance du produit r.P par d'éventuels utilisateurs malveillants ne permet pas d'en déduire la valeur r ni par conséquent de calculer la valeur de la clé K selon le procédé utilisé par l'utilisateur pour ce faire. L'utilisateur ID reçoit donc le message chiffré E et le produit r. P. Il procède alors au calcul de la valeur C(s.ID, r.P), ce qui est possible pour lui (et pour lui seul) puisqu'il est le seul utilisateur à connaître le produit s.ID (comme expliqué ci-dessus) et qu'il a reçu le produit r.P. Selon les propriétés bilinéaires des couplages, la valeur calculée par l'utilisateur ID est égale à C(r.ID, s.P), c'est-à-dire à K: l'utilisateur ID a pu ainsi calculer par une manière alternative la clé K en utilisant la propriété de bilinéarité du couplage C et sa connaissance du produit s.lD. Le déchiffrement du message E est alors possible en utilisant la clé K: msg=déchiffrK (E). (On rappelle à cet égard que l'algorithme de chiffrement utilisé est à clé symétrique.) La solution qui vient d'être présentée pour le chiffrement, puis le déchiffrement, d'un message peut également être appliquée à la signature d'un message et à l'authentification de cette signature, par exemple au moyen d'un algorithme à clé symétrique K comme déjà présenté, au moyen d'une clé asymétrique ou directement, par exemple en utilisant le résultat du couplage comme moyen de vérification. Dans ces diverses solutions, on utilise donc une fonction de couplage C, tel que par exemple le couplage de Tate défini par une formule du type: Px 1 C(P,Q) _ fP (AQ) Le calcul du couplage utilisé en diverses occasions dans l'algorithme cryptographique comme expliqué ci- dessus implique donc une exponentiation à la puissance (pk-1)/l. On rappelle qu'il s'agit d'un exposant entier puisque par définition 1 divise (pk-1). On va à présent décrire une première solution pour le calcul d'une telle exponentiation dans le cas où k=6. On utilise le fait que l'ensemble F6 peut s'assimiler par isomorphisme à l'ensemble-quotient F [X] des polynômes à coefficients dans R(x) Fp pris modulo un polynôme de degré 6 R(X), pour représenter les éléments de F 6 comme des éléments de F[X] . Dans l'exemple détaillé ici, on prend p R(X) R(X) = X6+a ce qui est possible lorsque p == lmod3. Le calcul du couplage précédemment mentionné revient donc à élever à la puissance (p6-1)/1 un élément de cet ensemble, à savoir un polynôme de F[x] R(X) On propose d'utiliser le fait que: p61 1 = PZ 1P+1(pz -1)(P2 +P+1)= [p2_ Ip+l (P-1)](p +1)(p2 +p+1) et que (p6-1)/l peut donc s'écrire m.(P+1)(P2+P+1) avec m = P2 P +l (P -1) 1 pour réaliser l'exponentiation par les deux étapes suivantes, dans un ordre quelconque: - exponentiation à la puissance m par une méthode classique (par 15 exemple par la méthode dite "square-and-multiply" dont le coût calculatoire est de l'ordre du logarithme de l'exposant) ; - exponentiation à la puissance (p+1)(p2+p+1) en utilisant l'endomorphisme de Frobenius cp défini cornme suit: On a en effet constaté que m est un entier malgré son expression sous forme d'une fraction. Par ailleurs, on sait utiliser l'endomorphisme de Frobenius cp pour réaliser une exponentiation à une puissance s'exprimant sous forme d'un 25 polynôme en p, comme décrit par exemple dans l'article "Medium Galois Fields, their Bases and Arithmetic", de Preda Mihâilescu in Submissions to IEEE P1363a, février 2000. L'endomorphisme de Frobenius étant très peu consommateur en temps de calcul par rapport à une méthode d'exponentiation classique, l'exponentiation en deux étapes proposée nécessite un coût calculatoire de l'ordre de 2.log p (correspondant au coût cl'exponentiation à la puissance m par une méthode classique), au lieu de 5.log p si une méthode d'exponentiation classique avait été utilisée pour l'ensemble de l'exposant (p6-1)/l. Plus précisément, si on note x le nombre à élever à la puissance 10 (p+1)(p2+p+1), on propose de réaliser l'exponentiation à la puissance (p+1)(p2+p+1) comme suit: - on calcule fi = x6p[x1p(x)], /3 valant donc fi = x. x.x" P = xP2+p+1; - calcul de f6p(f) qui vaut donc f.BP = xP2+p+I+ p(p2+p+I) soit x 1'3+2p2+2p+1 = x(P+1)(P2+p+l) On remarque en outre que, lorsque l'on utilise la représentation de F 6 précédemment mentionnée, l'image,d'un élément x = x,X' de F 6 par =o s l'endomorphisme de Frobenius s'écrit simplement p(x) = Ix;b'X' mod p avec h i=o (P-1) une constante qui vaut b = ( a) 6 mod p. L'utilisation du polynôme R(X) = X6+ a comme polynôme irréductible pour représenter F6 sous la forme RP permet donc d'appliquer R(X) l'endomorphisme de Frobenius de manière simple en ne mémorisant par exemple que la valeur de b, alors que la mémorisation de 6x6=36 éléments est nécessaire dans le cas général pour représenter cp sous forme matricielle. Une telle solution est donc particulièrement adaptée aux environnements à ressource mémoire limitée, tels que les cartes à microcircuit. On va à présent décrire une variante pour le calcul de l'exponentiation à la puissance (p6-1)/l d'un élément de Fi), représenté comme un élément de ' x6 +a' D'après la factorisation de l'exposant (p6-1) /l donnée plus haut, celui- ci eut également s'écrire m'. +1 2+ +1 1 où m' est égal à p2 p + 1 p (P)(p p)(P-) l On a constaté que, du fait que par définition 1 divise (p6-1) mais ne divise pas (p-1) pour i compris entre 1 et 5, m' est un entier malgré son expression sous forme d'une fraction. L'exponentiation à la puissance (p6-1)/l peut ainsi être réalisée 10 comme suit: - exponentiation à la puissance m' par une méthode classique; exponentiation à la puissance (p+1)(p2+p+1)(p-1) en utilisant l'endomorphisme de Frobenius cp, ces deux étapes pouvant être réalisées dans un ordre quelconque. L'utilisation du polynôme R(X) = X6+a comme polynôme irréductible permet de simplifier le calcul de l'endomorphisme de Frobenius comme déjà expliqué. Par ailleurs, si on note x le nombre à élever à la puissance (p+1) (p2+p+1)(p-1) au moyen de l'endomorphisme de Frobenius, on propose de réaliser l'exponentiation à la puissance (p+1)(p2+p+1)(p-1) comme suit: on calcule 8 = xçp[xçp(x)], fi valant donc fi = x.l x.x" ]P = xP2+P+' ; calcul de Ç'49(fi)] qui vaut ainsi x(P2+P+'>(P2-1) i3 Bien que ce dernier calcul implique une division, son coût calculatoire (équivalent à environ 10 multiplications) est négligeable par rapport à l'ensemble de l'exponentiation. Les exemples qui viennent: d'être décrits ne représentent naturellement que des modes possibles de mise en oeuvre de l'invention. REVENDICATIONS 1. Procédé de traitement de données utilisant une fonction de couplage appliquée à au moins un élément d'un corps fini à p6 éléments (F6) 61 et impliquant une exponentiation à une puissance entière de la forme pl 1, où p et 1 sont des nombres entiers, caractérisé en ce qu'il comprencl les étapes de: - exponentiation à un entier m que divise p2 p + 1 l exponentiation à la puissance pG -1 en utilisant l'endomorphisme lm de Frobenius (p. 2. Procédé selon la revendication 1, caractérisé en ce que l'élément du corps fini F6 est représenté par les coefficients d'un polynôme de l'ensemble X 6[Xa, où a est un nombre entier. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que m = 2 p p+1 l 4. Procédé selon la revendication 3, caractérisé en ce, que 20 l'élément à élever à la puissance PG -1 étant noté x, l'exponentiation à la lm puissance pG -1 est réalisée par les étapes suivantes: lm -calcul de /3 = xço[xço(x)] ; calcul de Ç9[ç0(fl)] 5. Procédé selon la revendication 1 ou 2, caractérisé en ce que m = (p 2 P +1)(P -1) 1 6. Procédé selon la revendlication 5, caractérisé en ce que, l'élément à élever à la puissance Plm 1 étant noté x, l'exponentiation à la puissance p6 -1 est réalisée par les étapes suivantes: lm - calcul de /6 = xçp[xçp(x)] ; - calcul de /3çp(/3). 7. Programme d'ordinateur apte à être chargé dans un appareil programmable, caractérisé en ce qu'il contient des instructions pour mettre en oeuvre le procédé selon l'une des revendications 1 à 6. 8. Dispositif de traitement de données avec des moyens aptes à utiliser une fonction de couplage appliquée à au moins un élément d'un corps fini à p6 éléments (F6) et impliquant une exponentiation à une puissance G entière de la forme Pl 1, où p et 1 sont des nombres entiers, caractérisé en ce qu'il comprend: - des moyens pour effectuer une exponentiation à un entier m que divise p p+l 1 - des moyens pour effectuer une exponentiation à la puissance G p -1 en utilisant l'endomorphisme de Frobenius (p. lm 9. Dispositif selon la revendication 8, caractérisé en ce qu'il comprend des moyens aptes à représenter l'élément du corps fini F 6 par les coefficients d'un polynôme de l'ensemble -F[X] , où a est un nombre entier. y6 +a 10. Dispositif selon la revendication 8 ou 9, caractérisé en ce que m p2_p+l 1 11. Dispositif selon la revendication 10, caractérisé en ce que, l'élément à élever à la puissance plm 1 étant noté x, les moyens pour effectuer une exponentiation à la puissance plm 1 comprennent: des moyens de calcul de /3 = xçp[xv(x)] ; des moyens de calcul de (0k(fi)] 12. Dispositif selon la revendication 8 ou 9, caractérisé en ce que m=(p2 -p +1)(p -1) 13. Dispositif selon la revendication 12, caractérisé en ce que; l'élément à élever à la puissance p -1 étant noté x, les moyens pour effectuer lm G une exponentiation à la puissance p -1 comprennent: lm - des moyens de calcul de /.3 = xv[xçp(x)] ; des moyens de calcul de /3çp(/3). 14. Carte à microcircuit comprenant un dispositif selon l'une des revendications 8 à 13. l3