Brevet FR2892251A1 — publié le 20070420

PROCEDE CRYPTOGRAPHIQUE METTANT EN îUVRE UN SYSTEME DE CHIFFREMENT BASE SUR L'IDENTITE La présente invention concerne un procédé de génération de clés destinées à un algorithme cryptographique à clé publique mis en oeuvre dans le cadre d'un système cryptographique basé sur l'identité, dit IBE (de l'acronyme anglais Identity-Based Encryption ). L'invention est notamment intéressante pour la mise en oeuvre d'algorithmes cryptographiques pour le chiffrement et le déchiffrement ou la signature et la vérification de signature dans un objet électronique portable de type carte à puce. Parmi les schémas de sécurité à clé publique, la technologie IBE présente un certain nombre d'avantages. Ainsi, dans les schémas d'infrastructure à clé publique classique, la clé publique est souvent un nombre calculé de façon aléatoire, devant être liée à l'identité de l'utilisateur par un certificat. Avec l'IBE, la clé publique peut être choisie en toute liberté et est directement égale à l'identité de l'utilisateur, sans l'échange de certificats ni la coûteuse infrastructure correspondante. Le schéma d'IBE proposé par la présente invention est mis en oeuvre au moyen de fonctions de couplage sur des courbes elliptiques. Un tel schéma d'IBE utilise le couplage bilinéaire sur des courbes elliptiques pour obtenir un algorithme permettant de transformer une simple identité en une paire de clés publique/privée. Pour rappel, une courbe elliptique est un ensemble de points ayant des caractéristiques communes et dont les coordonnées peuvent notamment être calculées à partir des coordonnées de certains points de la courbe, dits points générateurs, par des opérations simples telles qu'une multiplication par un scalaire. Le lecteur pourra se reporter au document Identity based encryption from the Weil pairing d. Boneh et M. Frankin, dans proceedings of crypto '01, Springer-Verlag, 2001 pour plus de détails sur les systèmes de chiffrement basés sur l'identité qui utilisent de telles techniques cryptographiques. D'une manière générale, la sécurité de tout protocole cryptographique repose sur la difficulté d'un problème algorithmique donné. La présente invention consiste plus précisément en une amélioration du système cryptographique basé sur l'identité proposé par Waters, qu'on appellera dans la suite de la description schéma de Waters, dont la preuve de sécurité ne fait pas appel à des oracles aléatoires mais est basée sur le problème DBDH (acronyme anglais pour Decisional Bilinear Diffie-Hellman ). Le lecteur pourra utilement se reporter pour plus de détails sur ce schéma d'IBE dit complètement sécurisé dans le modèle standard, à la publication Efficient Identity-Based Encryption Without Random Oracles par Brent Waters, dans Proceedings of Eurocrypt 2005, Springer-Verlag, 2005 . L'inconvénient du schéma d'IBE de Waters est qu'il nécessite d'employer une clé publique dont la taille, typiquement de l'ordre de 165 Ko, est incompatible avec les environnements contraints tels que les cartes à puce. Aussi, si ce protocole a montré son efficacité tout en faisant preuve de sa sécurité, il a cependant l'inconvénient d'être particulièrement coûteux, en termes de ressources matérielles de calcul nécessaires à sa mise en œuvre. Notamment, certaines opérations élémentaires utilisées dans ce protocole sont particulièrement coûteuses, comme par exemple les opérations de couplage ( pairing en anglais ) sur courbes elliptiques, d'autant plus si la clé publique possède une taille importante. Parce que certaines opérations sont coûteuses du fait de la longueur de la clé publique, le schéma d'IBE de Waters est particulièrement difficile à implémenter dans une carte à puce, car les temps de calcul deviennent prohibitifs, les ressources matérielles de la carte étant nécessairement limitées. L'invention a donc pour but de remédier à cet inconvénient en permettant la mise en oeuvre d'algorithmes de chiffrement à clé publique basés sur l'identité, qui présentent un fort niveau de sécurité tout en se servant d'une clé publique dont la taille est fortement réduite par rapport aux schémas d'IBE précédemment décrits, rendant ainsi plus aisée leur incorporation dans des environnements contraints en ressources de calcul. Avec cet objectif en vue, l'invention a notamment pour objet un procédé de génération de clés destinées à un algorithme cryptographique à clé publique mis en oeuvre dans le cadre d'un système cryptographique basé sur l'identité d'un utilisateur dudit système et comprenant des étapes de : obtention d'un ensemble de paramètres publics et privés associés audit système cryptographique basé sur l'identité ; - sélection d'un identifiant public comprenant une information d'identité dudit utilisateur et de détermination d'un vecteur identité représentatif dudit identifiant propre audit utilisateur; - génération d'un couple clé publique/clé privé associé à l'identité dudit utilisateur, à partir desdits paramètres publics et privés et dudit vecteur identité. Ce procédé est caractérisé en ce que les éléments dudit vecteur identité sont codés chacun sur k bits, avec k>l. Avantageusement, l'algorithme cryptographique mis en oeuvre est un algorithme de chiffrement d'un message pour l'émission du message chiffré d'un émetteur vers l'utilisateur destinataire, ledit procédé comprenant une étape de calcul du message chiffré à partir du message en clair, des paramètres publics et du vecteur identité. De préférence, l'étape de calcul du message 25 chiffré comprend l'utilisation de la clé publique associée au destinataire, définie par le produit n u' fl uiv' , u' et ul faisant partie des paramètres publics i=1 du système et les vi étant les éléments du vecteur identité. Avantageusement, le déchiffrement du message chiffré comprend une étape de calcul du message en clair à partir dudit message chiffré en utilisant ladite clé privée dudit utilisateur destinataire. L'algorithme cryptographique mis en oeuvre peut être un algorithme de signature à clé publique. Le procédé peut être mis en oeuvre dans le cadre du système cryptographique de Waters, dans lequel lesdits paramètres publics et privé sont issus d'un groupe algébrique dérivé d'une courbe elliptique. L'identifiant public dudit utilisateur peut comprendre le nom dudit utilisateur ou son adresse électronique. D'autres caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture de la description suivante donnée à titre d'exemple illustratif et non limitatif et faite en référence aux figures annexées dans lesquelles : -la figure 1 illustre de façon schématique un système cryptographique basé sur l'identité dans lequel la présente invention est mise en oeuvre ; -la figure 2 illustre schématiquement la suite d'étapes mises en oeuvre pour chiffrer un message selon la présente invention, et -la figure 3 illustre schématiquement la suite d'étapes mises en oeuvre pour déchiffrer ledit message selon la présente invention. Selon l'exemple de réalisation, l'invention est mise en oeuvre dans un système cryptographique basé sur l'identité (IBE), permettant à un utilisateur de chiffrer un message devant être émis en se servant de données personnelles du destinataire comme clé publique. Ainsi, de manière générale, dans un tel système cryptographique représenté à la figure 1, lorsqu'un émetteur A souhaite envoyer un message m sous forme chiffrée à un destinataire B, le message est chiffré en utilisant une clé publique reliée directement à un identifiant public ID comprenant une information d'identité du destinataire B. Cette information d'identité du destinataire est par exemple constituée du nom du destinataire, ou encore de son adresse électronique, ou de toute autre information permettant d'identifier le destinataire. Lorsque le destinataire B reçoit le message c ainsi chiffré, il s'adresse à une autorité PKG, dont le rôle est de fournir au destinataire sa clé privée d,ä qui est calculée comme une fonction de l'identité du destinataire. Le destinataire B peut alors déchiffrer le message chiffré c qu'il a reçu, à l'aide de la clé privée ainsi obtenue auprès de l'autorité PKG. Le principe de fonctionnement va maintenant être décrit plus en détail en référence au schéma d'IBE de Waters, auquel la présente invention propose une amélioration significative. Un schéma d'IBE est décrit typiquement par quatre algorithmes, dénommés Setup , extract , encrypt et decrypt dans la littérature anglaise. La première phase, mise en œuvre par l'algorithme Setup , est une phase de génération de paramètres du système. Pour ce faire, l'algorithme travaille sur un groupe G d'ordre premier, constitué des points d'une courbe elliptique. Un générateur g pour le groupe G est défini ainsi qu'une application e bilinéaire admissible sur G, bénéficiant donc des propriétés de bilinéarité, qui sont connues en elle mêmes. Tout d'abord, un nombre secret a est choisi de manière aléatoire dans l'ensemble prédéfini Zp, avec p un nombre premier, puis on définit g1, tel que g1=ga. Un élément g2 est également choisi de manière aléatoire dans le groupe G. Puis, on choisit une valeur aléatoire u' appartenant au groupe G, ainsi qu'un vecteur U=(ui) de longueur n, dont les éléments ui sont choisis de manière aléatoire dans le groupe G. Dans ce cas, des identités de longueur binaire n pourront être supportées par ce schéma d'IBE. Les paramètres publics du système sont alors constitués par les éléments précédemment définis g, g1, g2, u' et U. Ces paramètres sont encore appelés clé publique maître PKmaître : PKmaître = ( g, g1, g2, u', U). Par ailleurs, on définit un paramètre privé, dit clé privée maître SK maître SKmaître ù g2a La phase suivante consiste, à partir des paramètres du système ainsi obtenus, en la génération du couple clé publique et clé privée, associé à l'identité de l'utilisateur. On détermine tout d'abord un vecteur identité v représentatif d'un identifiant propre à l'utilisateur, en l'occurrence le destinataire du message. Comme on l'a vu, cet identifiant comprend une information d'identité du destinataire, par exemple son nom. Selon la variante améliorée du schéma de Waters proposé par l'invention, l'identité est représentée par un vecteur identité de longueur n, v = (vl,. . .,vn), où chaque élément vi est un entier codé sur k bits, avec k>l. On prendra par exemple k = 32 bits. Dans le schéma de Waters classique, le vecteur identité est une chaîne de bits où chaque élément du vecteur identité est au contraire codé sur un seul bit. Comme illustré à la figure 2, après avoir obtenu les paramètres publics du système (étape 10) et déterminé le vecteur identité v selon les principes exposés ci-dessus (étape 20), une clé publique PKID du destinataire est générée (étape 30), à partir du vecteur public U et du vecteur identité v. Pour ce faire, le calcul suivant est mis en œ uvre : PKun = u' 11 u, '[' La nouvelle construction du vecteur identité v permet alors avantageusement de réduire la taille du vecteur public U d'un facteur k. Ainsi, si on définit par n' la taille du vecteur U dans le schéma de Waters classique, avec le vecteur identité constitué alors classiquement de n' éléments chacun codé sur un bit, la taille du vecteur U est maintenant ramenée à n=n'/k, en prenant la configuration particulière selon l'invention du vecteur identité v. Selon l'exemple avec k = 32, on passe alors d'une taille de vecteur public égale à 160Ko dans le schéma de Waters classique à une taille égale à 5Ko selon l'invention. Une fois la clé publique PKID du destinataire calculée pour l'identité v déterminée, le message m peut être chiffré (étape 40) côté émetteur pour être transmis sous forme chiffrée c au destinataire. Pour ce faire, l'algorithme encrypt de chiffrement prend en entrées les paramètres publics, la clé publique du destinataire, le message en clair m, ainsi qu'un nombre t, choisi de manière aléatoire dans l'ensemble Zp. Le message chiffré c fourni par l'algorithme pour être transmis au destinataire est construit de la façon suivante sous forme d'un triplet: c = (cl, c2, c3), avec cl = e (gl , g2) L .m, e étant l'opération de couplage mis en œuvre entre les deux paramètres publics g1 et g2 ; c2 = gt ; c3=(u'~u'r Les trois éléments cl, c2 et c3 sont donc envoyés en tant que message chiffré. Pour pouvoir mettre en oeuvre le déchiffrement côté destinataire, l'algorithme decrypt doit prendre en entrées le triplet chiffré reçu c = (cl, c2, c3) et la clé privée du destinataire, calculée comme une fonction de l'identifiant ID du destinataire. La réalisation de ce calcul nécessite tout d'abord d'obtenir la clé privé d, correspondant au vecteur 20 identité v représentatif de l'identité du destinataire. La clef privée dv est construite (étape 60) par l'autorité en utilisant l'algorithme "extract" et en connaissant la clef secrète maitre, de la façon suivante : n dv = (g2a (u'n ui ['1)r i gr) r=t n On définit dl = g2a (u'nu;v1'1 )Y ; et d2 = gr r étant un nombre aléatoire choisi dans l'ensemble Zp. L'étape de déchiffrement proprement dite (étape 70) peut alors être mise en oeuvre. Soient donc c = (cl,c2,c3), le triplet représentant la forme chiffrée du message m en utilisant l'identité du destinataire représentée par le vecteur identité v, et dv = (dl,d2), la clé privée du destinataire correspondant à son identité, l'algorithme decrypt fournit alors le message m déchiffré en appliquant les calculs suivants . e(d ,c ) elgr,(u'llu.vi )t) 2 3 t c1 e(c2 d1) = e(gl,g2 ) m e(gt ~ga (ut~ u.vi )r ) 2 e(g,(u'nu.vl )rt) = e(gl , g2 )t . m. = m Il ressort donc de ce qui précède, que la nouvelle amélioration du schéma de Waters selon la présente invention, consistant à écrire l'identité de e(g1'g2)te(g,(ulIIulvl )rt) l'utilisateur comme un vecteur v à n éléments v = (v1, vn) où chaque vi est un entier codé sur k bits avec k > 1, tel que n.k = n', où n' serait la taille du vecteur public U dans le schéma antérieur classique de n v Waters, et à calculer le produit modifié UT-Pi ' , l=1 conduit à considérer un vecteur public U possédant dorénavant une longueur n, sa taille ayant donc été réduite d'un facteur n'/n = k. En effet, selon l'invention, chaque élément ui du vecteur U peut maintenant supporter k bits, au lieu d'un seul bit dans le schéma antérieur. Pour une taille d'identité identique, la taille du vecteur U est donc divisée par un facteur k. Bien que la taille du paramètre public U puisse être réduite de façon conséquente, par un facteur k, le schéma d'IBE selon la présente invention bénéficie toujours d'une sécurité prouvée dans le modèle de sécurité le plus strict, appelé modèle standard. Les calculs illustrant la preuve de cette sécurité étant accessibles à l'homme de l'art, ils ne seront pas développés dans le cadre de la présente demande.25 REVENDICATIONS 1. Procédé de génération de clés destinées à un algorithme cryptographique à clé publique mis en oeuvre dans le cadre d'un système cryptographique basé sur l'identité d'un utilisateur dudit système et comprenant des étapes de : - obtention (10, 50) d'un ensemble de paramètres publics (g, g1, g2, u', U) et privés (g2a ) associés audit système cryptographique basé sur l'identité ; - sélection d'un identifiant public (ID) comprenant une information d'identité dudit utilisateur et de détermination (20) d'un vecteur identité (v) représentatif dudit identifiant propre audit utilisateur; - génération (30, 60) d'un couple clé publique 15 (PKID)/clé privé (dv) associé à l'identité dudit utilisateur, à partir desdits paramètres publics et privés et dudit vecteur identité (v) ; ledit procédé étant caractérisé en ce que les éléments (vi) dudit vecteur identité (v) sont codés 20 chacun sur k bits, avec k>1. 2. Procédé selon la revendication 1, caractérisé en ce que l'algorithme cryptographique mis en oeuvre est un algorithme de chiffrement d'un message (m) pour 25 l'émission du message chiffré (c) d'un émetteur (A) vers l'utilisateur destinataire (B), ledit procédé comprenant une étape de calcul (40) du message chiffréà partir du message en clair, des paramètres publics et du vecteur identité (v). 3 Procédé selon la revendication 2, caractérisé en ce que l'étape de calcul du message chiffré (c) comprend l'utilisation de la clé publique (PKID) associée au destinataire, définie par le produit n u~fluiv' , u' et ui faisant partie des paramètres publics i=1 du système et les vi étant les éléments du vecteur 10 identité. 4. Procédé selon la revendication 2 ou 3, caractérisé en ce que le déchiffrement du message chiffré (c) comprend une étape de calcul (70) du 15 message en clair (m) à partir dudit message chiffré (c) en utilisant ladite clé privée dudit utilisateur destinataire. 5. Procédé selon la revendication 1, caractérisé 20 en ce que l'algorithme cryptographique mis en oeuvre est un algorithme de signature à clé publique. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il est 25 mis en oeuvre dans le cadre du système cryptographique de Waters, dans lequel lesdits paramètres publics et privé sont issus d'un groupe algébrique dérivé d'une courbe elliptique.7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'identifiant public (ID) dudit utilisateur comprend le nom dudit utilisateur ou son adresse électronique.5