Brevet FR2903258A1 — publié le 20080104

Titre de l'invention Système et procédé cryptographique à clé publique pour l'authentification d'une première entité par une seconde entité. Domaine technique de l'invention L'invention se rapporte au domaine de la cryptographie. Plus particulièrement, celui de la cryptographie à clé publique pour l'authentification d'une première entité possédant une clé secrète associée à une clé publique par une seconde entité possédant la clé publique. A titre d'exemple, l'invention peut être utilisée pour la protection contre la fraude d'une puce électronique dans des transactions entre une application et la puce. Arrière-plan de l'invention Actuellement, les cartes à puce sont susceptibles de subir différents types de fraude. Un premier type de fraude consiste à dupliquer sans autorisation la carte, le terme clonage étant souvent utilisé pour caractériser cette opération. Un deuxième type de fraude consiste à modifier les données attachées à une carte, en particulier le montant du crédit inscrit dans la carte. Pour lutter contre ces fraudes, il est fait appel à la cryptographie, d'une part pour assurer l'authentification de la carte au moyen d'une authentification et/ou pour assurer l'authentification des données au moyen d'une signature numérique, et d'autre part pour assurer le cas échéant la confidentialité des données au moyen d'un chiffrement. De manière générale, la cryptographie met en jeu deux entités, qui sont dans le cas de l'authentification un vérificateur et un objet à vérifier, et elle peut être soit symétrique, soit asymétrique. Lorsqu'elle est symétrique (ou "à clé secrète", les deux termes étant synonymes), les deux entités partagent exactement la même information, en particulier 2903258 2 une clé secrète. Lorsqu'elle est asymétrique (ou "à clé publique", les deux termes étant synonymes) une des deux entités possède une paire de clés dont l'une est secrète et l'autre est publique; il n'y a pas de clé secrète partagée. 5 Les premiers mécanismes d'authentification développés en cryptographie symétrique consistent à calculer une fois pour toutes une valeur d'authentification, différente pour chaque carte, à la stocker dans la mémoire de la carte, à la lire à chaque transaction et à la vérifier en interrogeant une application du réseau apte à mettre en oeuvre la 10 transaction, où les valeurs d'authentification déjà attribuées sont soit stockées soit recalculées. Ces mécanismes assurent une protection insuffisante parce que la valeur d'authentification peut être espionnée, reproduite et rejouée frauduleusement étant donné qu'elle est toujours la même pour une carte donnée ; un fraudeur peut ainsi réaliser un clone de 15 cette carte. Pour lutter contre les clones, les mécanismes d'authentification passifs de cartes sont remplacés par des mécanismes d'authentification actifs qui peuvent en outre assurer l'intégrité des données. Le principe général des mécanismes d'authentification actifs 20 symétriques est le suivant : lors d'une authentification, la puce électronique et l'application calculent une valeur d'authentification qui est le résultat d'une fonction appliquée à une liste d'arguments déterminée à chaque authentification ; la liste d'arguments peut comprendre un aléa (l'aléa étant une donnée déterminée par l'application à chaque 25 authentification), une donnée contenue dans la puce électronique et une clé secrète connue de la puce électronique et de l'application. Lorsque la valeur d'authentification calculée par la puce électronique est identique à la valeur d'authentification calculée par l'application, la puce électronique est jugée authentique et la transaction entre la puce électronique et 30 l'application est autorisée. 2903258 3 Cependant, les mécanismes à clé secrète imposent que le dispositif de vérification, en charge de l'authentification de la puce, tel que ceux présents dans un téléphone public, un terminal de paiement électronique, ou encore un portillon de transport en commun, connaisse la 5 clé secrète détenue par ladite puce. Il en découle un inconvénient majeur, à savoir que, si l'on souhaite que ledit dispositif puisse authentifier n'importe quelle puce émise en relation avec l'application, soit il doit stocker les clés secrètes de toutes les puces, soit il doit stocker une clé de base, appelée aussi clé-mère ou clé-maître, permettant de retrouver la clé 10 secrète de n'importe quelle puce. Dans les deux cas, chacun de ces dispositifs stocke suffisamment d'information pour pouvoir retrouver les clés secrètes de toutes les puces émises, et stocke donc suffisamment d'information pour pouvoir fabriquer des clones de n'importe laquelle d'entre elles. Il s'ensuit qu'une intrusion réussie contre n'importe lequel 15 des dispositifs de vérification anéantirait la sécurité de l'application dans son ensemble. Ainsi, des solutions à base de cryptographie à clé publique peuvent être préférées aux mécanismes à clé secrète. Le principe de fonctionnement de mécanismes d'authentification à clés publiques est 20 alors le suivant : la puce cherchant à s'authentifier calcule des valeurs dépendant de sa clé privée (qui est associée à sa clé publique) et d'éventuels paramètres aléatoires ; l'application vérifie ensuite la cohérence des valeurs calculées par la puce sans nécessiter la connaissance de la clé privée de la puce; seule l'utilisation de la clé 25 publique de la carte à puce est nécessaire ainsi que d'éventuels autres paramètres non secrets. Il est alors aussi envisageable que la puce s'authentifie auprès de l'application mais aussi que la puce authentifie l'application avec laquelle elle communique. Dans ce cas, le terme "authentification 30 mutuelle" est utilisé. Ce type d'authentification mutuelle se fait en 2903258 4 exécutant simultanément deux procédés d'authentification classiques où la puce et l'application intervertissent les rôles dans les deux protocoles. Les solutions les plus connues permettant de réaliser de tels mécanismes d'authentification reposent généralement sur des problèmes 5 mathématiques difficiles tels que la factorisation ou le logarithme discret, ces deux problèmes engendrent dans leur réalisation des calculs d'exponentiations modulaires, c'est à dire des calculs du type xe modn où "mod" correspond à la fonction mathématique de réduction modulaire. Ce type de calculs est à priori l'opération la plus complexe pouvant être 10 réalisée en temps raisonnable (sans hypothèse particulière sur la puissance de calcul) par une carte à puce. Cependant, au cas où l'on trouverait des algorithmes efficaces pour résoudre ces problèmes, alors ces derniers deviendraient inutilisables en cryptographie. C'est pourquoi il est indispensable de partir à la 15 recherche de problèmes mathématiques d'une autre nature et de mécanismes d'authentification utilisant ces nouveaux problèmes. Depuis quelques années, les applications bilinéaires, bien connues des mathématiciens, ont fait leur apparition dans le domaine de la cryptographie. Considérons par exemple une application f définie sur 20 l'ensemble G, xG2 dans G où G,,G, et G sont des groupes (notion mathématique). Supposons g, et g, des générateurs (ou primitifs) respectivement de G, et G2, la fonction f est dite bilinéaire de G, xG2 dans G si f(g, ,g = f(gäg,)ah. Le problème actuel lié à ces applications bilinéaires est que 25 leurs évaluations engendrent d'énormes calculs, bien plus complexes que le calcul d'une (simple) exponentiation modulaire. D'où la difficulté dans un cadre classique, de réaliser de tels calculs. De plus, les solutions existantes semblent très peu efficaces pour permettre de les utiliser pour l'authentification mutuelle. 2903258 5 Actuellement, il existe deux schémas d'authentification utilisant les applications bilinéaires. Le premier protocole est décrit dans l'article de G. Yao, G. Wang, et Y. Wang intitulé "An Improved Identification Scheme", Progress in Computer Science and Applied Logic, Berkhauser- 5 Verlag, novembre 2003. Le second protocole est décrit dans l'article de M. Kim et K. Kim intitulé "A New Identification Scheme Based on the Bilinear Diffie-Hellman Problem", 7th Australian Conference on Information Security and Privacy, ACISP '02, pages 362 à 378, Springer-Verlag, 2002. La figure 4 illustre un tableau détaillant les caractéristiques du 10 protocole de Wang et Wang (référencé Ml) et celui de Kim et Kim (référencé M2). Chaque protocole M1 ou M2 peut être caractérisé par le nombre d'opérations mathématiques nécessaire pour réaliser une itération entre une puce électronique E101 et une application E102. Ces opérations 15 comportent le nombre de phases (référencé NP) de transfert de données, le nombre d'exponentiations (référencé NE) par un exposant de même taille que celle de l'ordre du primitif g et le nombre d'évaluations (référencé NB) d'une application bilinéaire. En effet, la première colonne du tableau indique le type de 20 protocole M1 ou M2, la deuxième colonne indique l'entité EN (c'est-à-dire, la puce E101 ou l'application E102), la troisième colonne indique le nombre d'évaluations NB d'une application bilinéaire, la quatrième colonne indique le nombre d'exponentiations NE par un exposant de même taille que celle de l'ordre de g et la cinquième colonne indique le nombre de 25 phases NP de transfert de données. On notera que les valeurs données sont des valeurs moyennes. De plus, ces valeurs sont données pour des méthodes ne réalisant pas des précalculs, qui restent une possibilité très contextuelle. Ceci permet de rendre objective et de faciliter la comparaison entre les différentes 30 méthodes. 2903258 6 Ces protocoles présentent des propriétés de sécurité fort intéressantes mais nécessitent en pratique beaucoup de calculs. Ceci présente un très grand frein à leur développement. 5 Objet et résumé de l'invention La présente invention concerne un procédé cryptographique à clé publique pour l'authentification d'une première entité possédant une clé secrète S associée à une clé publique P par une seconde entité possédant ladite clé publique P, ladite clé secrète S appartenant à un 10 premier ou à un deuxième groupes (G,,G,) respectivement engendrés par des premier et deuxième primitifs g, et g, d'ordre premier q, ledit procédé comprenant les étapes suivantes : - envoi d'un défi par la seconde entité à la première entité, - calcul par la première entité d'une réponse prenant en compte ledit défi 15 et ladite clé secrète S , - envoi par la première entité de ladite réponse à la seconde entité, et - vérification de la réponse par la seconde entité à l'aide dudit défi et de la clé publique P. Ledit procédé est remarquable en ce que ladite clé publique P 20 comporte, d'une part, une valeur publique v = e(g, , S) ou v = e(S, g,) égale à l'image par une application bilinéaire e définie sur lesdits premier et deuxième groupes (G,,G,) d'un couple d'éléments formé par la clé secrète S et le primitif appartenant à l'autre des premier et deuxième groupes (G,,G,) que celui auquel appartient la clé secrète S, et d'autre 25 part ce primitif. Ainsi, le protocole d'authentification de la présente invention permet l'utilisation d'une application bilinéaire avec un coût de calcul inférieur aux schémas existants, ce qui permet une authentification sécurisée et efficace entre les deux entités. Ce protocole trouve une 2903258 7 application très avantageuse dans l'utilisation de nouveaux procédés à l'heure actuelle jugés trop coûteux en temps de calcul. La présente invention a donc pour but de proposer une nouvelle solution afin de diminuer efficacement ce temps de calcul. 5 Avantageusement, ladite clé publique P comporte en outre des paramètres publics identiques pour toute première entité, lesdits paramètres publics comprenant un premier paramètre égal au premier primitif gä un deuxième paramètre égal au deuxième primitif g2, et un troisième paramètre v = e(g,,g2) égal à l'image par ladite application 10 bilinéaire e desdits premier et deuxième primitifs g, et g2 . Le fait de fixer ces paramètres de manière universelle et de les publier permet de simplifier les calculs. Selon un mode de réalisation, le procédé selon l'invention comprend les étapes suivantes : 15 -choix par la première entité d'un premier nombre naturel r, -envoi par la première entité à la seconde entité d'une première valeur W =e(g,,g,)' égale à l'image par l'application bilinéaire e du couple (g,,g_) formé par lesdits premier et deuxième primitifs portée à la puissance dudit premier nombre naturel r, 20 -choix par la seconde entité d'un second nombre naturel c définissant ledit défi, - envoi dudit second nombre naturel c à la première entité, -calcul par la première entité d'une seconde valeur Y = g,rS` ou Y = g, S` définissant ladite réponse, ladite seconde valeur étant égale au produit 25 entre un premier terme g' ou g,r, et un second terme S`, ledit premier terme g; ou g; étant égal au primitif appartenant au même groupe que celui de la clé secrète porté à la puissance dudit premier nombre naturel r, et ledit second terme S` étant égal à la clé secrète S portée à la puissance dudit second nombre naturel c, 2903258 8 -envoi de ladite seconde valeur Y à la seconde entité, et -vérification par la seconde entité si l'image e(g,,Y) ou e(Y,g,) par l'application bilinéaire e du couple formé par ledit primitif appartenant à l'autre des premier et deuxième groupes (G,,G,) et ladite seconde valeur 5 Y est égale au produit Wv` entre ladite première valeur W et ladite clé publique v portée à la puissance dudit second nombre naturel c . Ainsi, la validation ou la non-validation de l'étape de vérification permet de considérer que l'authentification est réussie ou non réussie respectivement. Dans l'un ou l'autre des cas, les opérations de calcul entre 10 les première et seconde entités peuvent être réalisées avec seulement une évaluation d'application linéaire, quatre exponentiations et trois phases de transfert, ce qui représente un coût de calcul global inférieur aux schémas actuels d'authentification. Avantageusement, ladite première valeur W = e(g,,g, )r et/ou 15 ledit premier terme gz ou g; sont précalculés. Ceci permet de rendre plus rapide l'exécution en ligne du protocole, puisque les premières valeurs ont déjà pu être calculées hors ligne. Selon une particularité de l'invention, lesdites étapes sont 20 réitérées un nombre prédéterminé de fois de manière parallèle ou séquentielle. Ainsi, la sécurité de l'authentification est augmentée. Selon une variante, les premier et deuxième groupes (G,,G,) sont égaux et comportent un primitif commun g les primitifs g, et g, étant alors tout deux égaux à g . Ceci permet de réduire le nombre de 25 données à publier. L'invention vise aussi un système cryptographique à clé publique comportant une première entité possédant une clé secrète S associée à une clé publique P et une seconde entité possédant ladite clé 2903258 9 publique P, ledit système étant adapté pour la mise en oeuvre du procédé cryptographique selon au moins l'une des caractéristiques ci-dessus. L'invention vise également une carte à puce électronique adaptée pour la mise en oeuvre du procédé cryptographique selon au 5 moins l'une des caractéristiques ci-dessus. L'invention vise aussi un programme informatique téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par une puce électronique, comprenant des instructions de codes pour l'exécution des étapes du 10 procédé cryptographique selon au moins l'une des caractéristiques ci- dessus, lorsqu'il est exécuté sur un ordinateur ou une puce électronique. Brève description des dessins D'autres particularités et avantages de l'invention ressortiront à 15 la lecture de la description faite, ci-après, à titre indicatif mais non limitatif, en référence aux dessins annexés, sur lesquels : -la figure 1 illustre schématiquement un système cryptographique à clé publique comportant une première entité et une seconde entité, selon l'invention ; 20 -la figure 2 illustre un tableau détaillant les caractéristiques du procédé cryptographique selon l'invention ; -la figure 3 est un exemple illustrant de manière schématique les principales étapes de l'authentification de la première entité par la seconde entité ; et 25 la figure 4 illustre un tableau détaillant les caractéristiques des procédés cryptographiques selon l'art antérieur. Description détaillée de modes de réalisation 2903258 10 Conformément à l'invention, la figure 1 illustre de manière schématique un système cryptographique à clé publique comportant une première entité El et une seconde entité E2. La première entité El et la seconde entité E2 peuvent être 5 reliés entre elles par l'intermédiaire d'une ligne de communication 3 par contact ou à distance ou via un réseau de communication. La première entité El peut être un objet à vérifier tel qu'une puce électronique d'une carte de téléphone, carte de crédit ou titre de transport. La seconde entité E2 peut être une application ou un dispositif 10 de vérification, en charge de l'authentification de la première entité El, tel que ceux présents dans un téléphone public, un terminal de paiement électronique ou un portillon de transport en commun. La première entité El possède une clé publique P ainsi qu'une clé secrète S associée à cette clé publique P, et la seconde entité E2 15 possède la clé publique P. La clé secrète S appartient à un premier ou à un deuxième groupes (G,,G,) respectivement engendrés par des premier et deuxième générateurs ou primitifs g, et g2 d'ordre y, où y est un nombre premier de préférence grand (par exemple q > 2160 ) 20 En effet, on suppose l'existence d'une application bilinéaire e définie sur G1 xG2 et à valeur dans un troisième groupe G, de sorte que les groupes G, et G, sont respectivement engendrés par les éléments g, et g2 d'ordre q (c'est-à- dire e(g;,g;)=e(g1,g,Y) pour tout a et tout b). Conformément à l'invention, la clé publique P comporte d'une 25 part une valeur publique v égale à l'image par l'application bilinéaire e définie sur les premier et deuxième groupes (G1,G2) d'un couple d'éléments formé par la clé secrète S et le primitif appartenant à l'autre des premier et deuxième groupes (G,,G,) que celui auquel appartient la 2903258 11 clé secrète 5(c'est-à-dire v = e(g,, S) ou v = e(S, g2) et d'autre part, ce primitif (c'est-à-dire g, ou g, respectivement). Plus particulièrement, la clé publique peut correspondre à un quadruplet comportant trois paramètres en plus de la valeur publique 5 v = e(g, , S) ou v = e(S, g,) . A titre d'exemple, le premier paramètre est égal au premier primitif g, , le deuxième paramètre est égal au deuxième primitif g2 et le troisième paramètre v = e(g,, g,) est égal à l'image par l'application bilinéaire e des premier et deuxième primitifs g, et g2. Autrement dit, la clé publique P peut être constituée d'un quadruplet de 10 la forme (g1,g2,e(g,,g2), v=e(g,,S)) ou (g,,g,,e(gl,g2), v=e(S,g2)) Avantageusement, les premier g!, deuxième g2, et troisième v = e(gä g,) paramètres publics sont identiques pour toute première entité El. Ainsi, les variables ou paramètres g, , g, et e(g,, g,) peuvent 15 être fixées "universellement", c'est-à-dire qu'elles sont fixées égales pour tous les acteurs du protocole et publiées comme paramètres universels du protocole. Dans ce cas la clé publique, propre à chaque entité, est alors réduite à v = e(g, ,S' ) ou v = e(S, g, ) On notera que la figure 1 est également une illustration des 20 principales étapes du procédé cryptographique selon l'invention pour l'authentification de la première entité El (entité à vérifier) par la seconde entité E2 (entité vérificatrice). En effet, afin de vérifier l'authenticité de la première entité El, la seconde entité E2 envoie (étape N4) un défi à cette dernière. En 25 recevant ce défi, la première entité El calcule (étape N5) une réponse qui prend en compte le défi et la clé secrète S. A l'étape N6, la première entité El envoi cette réponse à la seconde entité E2. 2903258 12 A la réception de la réponse, la seconde entité E2 vérifie (étape N7) cette réponse à l'aide du défi et de la clé publique P. La figure 2 illustre un tableau détaillant les caractéristiques du protocole selon le schéma d'authentification de la présente invention. 5 Ce tableau indique que pour la première entité El le nombre d'évaluations NB d'une application bilinéaire est égal à zéro , le nombre d'exponentiations NE par un exposant de même taille que celle de l'ordre du primitif g est égal à trois . En outre, ce tableau indique que pour la seconde entité E2 le nombre d'évaluations NB d'une application bilinéaire 10 est égal à un , le nombre d'exponentiations NE par un exposant de même taille que celle de l'ordre de g est égal à un . Le tableau indique également que le nombre de phases NP de transfert de données entre la première entité El et la seconde entité E2 est égal à trois . Ainsi, ce tableau montre que le nombre moyen d'opérations 15 pour une itération entre la première entité El et la seconde entité E2 peut être réalisé avec seulement une évaluation d'application linéaire, quatre exponentiations et trois phases de transfert, ce qui représente un coût de calcul global inférieur aux schémas d'authentification de l'art antérieur (voir figure 4). En particulier, on notera que le nombre global 20 d'exponentiations (qui nécessitent beaucoup de temps de calcul) est petit par rapport à cet art antérieur. La figure 3 est un exemple illustrant les principales étapes de l'authentification de la première entité El par la seconde entité E2. A l'étape N11, la première entité El choisit un premier nombre 25 naturel r . Ce nombre naturel r est avantageusement choisi de manière aléatoire parmi les entiers strictement inférieurs à l'ordre premier q du primitif g, ou g, (c'est-à-dire 0 REVENDICATIONS 1. Procédé cryptographique à clé publique pour l'authentification d'une première entité (El) possédant une clé secrète S associée à une clé publique P par une seconde entité (E2) possédant ladite clé publique P, ladite clé secrète S appartenant à un premier ou à un deuxième groupes (G,, G2) respectivement engendrés par des premier et deuxième primitifs g, et g2 d'ordre premier q, ledit procédé comprenant les étapes suivantes: -envoi d'un défi par la seconde entité (E2) à la première entité (El), -calcul par la première entité (El) d'une réponse prenant en compte ledit défi et ladite clé secrète s, - envoi par la première entité (El) de ladite réponse à la seconde entité, et - vérification de la réponse par la seconde entité (E2) à l'aide dudit défi et de la clé publique P, ledit procédé étant caractérisé en ce que ladite clé publique P comporte, d'une part, une valeur publique v= e(g,, S) ou v = e(S, g,) égale à l'image par une application bilinéaire e définie sur lesdits premier et deuxième groupes (G,, G,) d'un couple d'éléments formé par la clé secrète S et le primitif appartenant à l'autre des premier et deuxième groupes (G,, G2) que celui auquel appartient la clé secrète S, et d'autre part ce primitif. 2. Procédé selon la revendication 1, caractérisé en ce que ladite clé publique P comporte en outre des paramètres publics identiques pour toute première entité, lesdits paramètres publics comprenant un premier paramètre égal au premier primitif g, , un deuxième paramètre égal au deuxième primitif g,, et un troisième paramètre v=e(g,,g,) égal à 2903258 18 l'image par ladite application bilinéaire e desdits premier et deuxième primitifs g, , g2. 3. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce 5 qu'il comprend les étapes suivantes : -choix par la première entité (El) d'un premier nombre naturel r, -envoi par la première entité (E1) à la seconde entité (E2) d'une première valeur W = e(g,, g2) égale à l'image par l'application bilinéaire e du couple (g, , g2) formé par lesdits premier et deuxième primitifs portée à la 10 puissance dudit premier nombre naturel r, -choix par la seconde entité (E2) d'un second nombre naturel c définissant ledit défi, -envoi dudit second nombre naturel c à la première entité (El), -calcul par la première entité (El) d'une seconde valeur Y = g;S` ou 15 Y = g; S' définissant ladite réponse, ladite seconde valeur étant égale au produit entre un premier terme g2 ou g; , et un second terme S`, ledit premier terme g; ou g; étant égal au primitif appartenant au même groupe que celui de la clé secrète porté à la puissance dudit premier nombre naturel r, et ledit second terme S` étant égal à la clé secrète S 20 portée à la puissance dudit second nombre naturel c, - envoi de ladite seconde valeur Y à la seconde entité (E2), et - vérification par la seconde entité (E2) si l'image e(gi, Y) ou e(Y, g2) par l'application bilinéaire e du couple formé par ledit primitif appartenant à l'autre des premier et deuxième groupes (G1, G2) et ladite seconde valeur 25 Y est égale au produit WV` entre ladite première valeur W et ladite clé publique v portée à la puissance dudit second nombre naturel c. 2903258 19 4. Procédé selon la revendication 3, caractérisé en ce que ladite première valeur W = e(g, ,g, ) et/ou ledit premier terme g, ou g; sont précalculés. 5. Procédé selon la revendication 3 ou 4, caractérisé en ce que lesdites 5 étapes sont réitérées un nombre prédéterminé de fois de manière parallèle ou séquentielle. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que les premier et deuxième groupes (G,, G2) sont égaux et 10 comportent un primitif commun g, les primitifs g, et g, étant alors tout deux égaux à g. 7. Système cryptographique à clé publique comportant une première entité possédant une clé secrète S associée à une clé publique Pet une 15 seconde entité possédant ladite clé publique P, ledit système étant adapté pour la mise en oeuvre du procédé cryptographique selon au moins l'une des revendications 1 à 6. 8. Carte à puce électronique adaptée pour la mise en oeuvre du procédé 20 cryptographique selon au moins l'une des revendications 1 à 6. 9. Programme informatique téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par une puce électronique, caractérisé en ce qu'il comprend 25 des instructions de codes pour l'exécution des étapes du procédé cryptographique selon au moins l'une des revendications 1 à 6, lorsqu'il est exécuté sur un ordinateur ou une puce électronique.