FR3015076A1 - Generation de cles cryptographiques - Google Patents

Abstract

Procédé de génération de paire de clés cryptographiques publique et privée dans le groupe additif des entiers modulo n, avec n étant le produit de deux nombres premiers p et q, le procédé comportant les étapes suivantes : - de calcul d'un exposant public e pour ladite clé publique, et - de calcul d'un exposant privé d pour ladite clé privée à partir dudit exposant public et dudit module publique, avec d.e = 1 mod λ(n), λ(n) étant le plus petit commun multiple entre p-1 et q-1, caractérisé en ce que le procédé comporte en outre, une étape : - de vérification pour vérifier que λ(n) = 0 mod (p-1) et λ(n) = 0 mod (q-1).

Description

La présente invention concerne le domaine de la sécurité informatique. Elle concerne plus particulièrement la sécurisation des procédés cryptographiques mettant en oeuvre des paires de clés publiques et privées. Certains systèmes cryptographiques mettant en oeuvre des procédés comme par exemple la signature numérique d'un message ou son chiffrement, nécessitent la génération de paires de clés cryptographiques. La clé publique est partagée en clair par le système cryptographique avec les systèmes destinataires du message traité alors que la clé privée est gardée secrète. La génération des paires de clés publiques et privées étant une 10 opération sensible, des mécanismes de test sont usuellement prévus pour vérifier leur intégrité. Par exemple, la norme américaine FIPS 140-2 publiée par le NIST (sigle de « National lnstitute of Standards and Technology ») prévoit un tel test (intitulé « pair-wise consistency test »). 15 Dans le cas de procédés cryptographiques de type RSA (sigle de « Rivest Shamir Adelman »), la paire de clés est obtenue de la manière suivante. Pour obtenir p et q, deux grands nombres premiers, on répète les deux étapes suivantes : 20 - obtention de deux nombres p et q candidats à partir de nombres tirés au hasard dans l'ensemble Z, du groupe additif des entiers modulo n, et - test de la primalité des p et q candidats ( par exemple selon un test de primalité probabiliste, par exemple de type Miller-Rabin, par exemple conformément à la norme FIPS 140-2, 25 jusqu'à obtenir un nombre premier. Le produit des nombres p et q forme ainsi un nombre n (n=p.q). Ensuite, le nombre 1(n) = (p-1).(q-1) est calculé (I) étant la fonction indicatrice d'Euler, ou « totient » en terminologie anglo-saxonne).

La clé publique est ensuite formée par les nombres n et e, avec e, l'exposant public », étant un entier tel que : - 1 < e < (1)(n), et - e et 1 (n) sont premiers entre eux (gcd(e, (1)(n))=1, « gcd » étant le sigle de « greatest common divisor », c'est-à-dire le plus grand commun diviseur). La clé privée est quant à elle formée par les nombres n et d, avec d, « l'exposant privé », étant un entier tel que : - d.e = 1 mod À(n), avec - À(n) étant le plus petit commun multiple entre p-1 et q-1 (À(n)=lcm(p-1, q-1), « lcm » étant le sigle de « least common multiplier » c'est-à-dire plus petit commun multiple en anglais). Lorsque le procédé cryptographique est un chiffrement d'un message m (m appartenant à Zn), le test d'intégrité prévu par la norme FIPS 15 140-2 peut se résumer comme suit : 1) le message m est chiffré avec la clé publique en sorte à obtenir un message chiffré c = me mod n, 2) le message chiffré c est déchiffré avec la clé privée en sorte à obtenir un message déchiffré m' = cd mod n, et 20 3) il est vérifié que le message initial m et le message déchiffré sont les mêmes (m' = m). Lorsque le procédé cryptographique est une signature d'un message m (m appartenant à 4), le test d'intégrité prévu par la norme FIPS 140-2 peut se résumer comme suit 25 1) le message m est signé avec la clé privée en sorte à obtenir une signature s = (m)d mod n, (ou éventuellement s = (H(m))d, H étant une fonction de hashage, 2) une valeur h' est calculée comme h' = se mod n, et 3) il est vérifié que la valeur h' ainsi calculée et le message m sont les mêmes (ou éventuellement que le la valeur h' et le condensât du message par la fonction de hashage sont les mêmes (h' = H(m)). Les inventeurs ont toutefois remarqué que les tests d'intégrité actuellement utilisés pouvaient ne pas détecter certaines erreurs de génération de paires de clés. Ils ont ainsi mis à jour un besoin pour améliorer la fiabilité de la génération de paires de clés dans les systèmes cryptographiques.

La présente invention s'inscrit dans ce cadre. Un premier aspect de l'invention concerne un procédé de génération de paire de clés cryptographiques publique et privée dans le groupe additif des entiers modulo n, avec n étant le produit de deux nombres premiers p et q, le procédé comportant les étapes suivantes : - de calcul d'un exposant public e pour ladite clé publique, et - de calcul d'un exposant privé d pour ladite clé privée à partir dudit exposant public et dudit module publique, avec d.e = 1 mod À(n), À(n) étant le plus petit commun multiple entre p-1 et q-1, caractérisé en ce que le procédé comporte en outre, une étape : - de vérification pour vérifier que À(n) = 0 mod (p-1) et À(n) = 0 mod (q-1). Un procédé selon le premier aspect permet de résister à la corruption des clés lors de leur génération, notamment nors du calcul du plus petit commun multiple.

Un procédé selon le premier aspect permet notamment de résister à des attaques malveillantes visant des procédés cryptographiques mettant en oeuvre les clés générées.

Des modes de réalisation visent un procédé de test d'intégrité de génération de clés cryptographiques comportant les étapes suivantes : - de génération d'une paire de clés cryptographiques selon le premier aspect, - de chiffrement d'un message m avec l'exposant public e en sorte à obtenir un message chiffré c, - de déchiffrement dudit message chiffré c avec ladite clé privée d en sorte à obtenir un message déchiffré m', et - de comparaison du message m avec le message déchiffré m'.

Le procédé peut en outre comporter les étapes suivantes : - de chiffrement (105) du message déchiffré m' avec l'exposant public e en sorte à obtenir un message chiffré c', - de comparaison du message chiffré c' avec le message chiffré c. Par exemple, le procédé est mis en oeuvre dans un dispositif électronique vis-à-vis d'une combinaison d'attaque par canal auxiliaire et d'une attaque par injection de faute, ladite combinaison étant mise en oeuvre lors de l'exécution d'un procédé cryptographique mettant en oeuvre une paire de clés cryptographiques. Un deuxième aspect de l'invention concerne un procédé de test de sécurité d'un dispositif électronique vis-à-vis d'une attaque, le dit dispositif mettant en oeuvre une génération d'une clé cryptographique publique e et une clé cryptographique privée d dans le groupe additif des entiers modulo n, telles que : - n = p.q, avec p et q étant des nombres premiers, - 1 < e < (I)(n), avec e et (I) (n) étant premiers entre eux et 1(n) = (p- 1).(q-1), et - d.e = 1 mod À(n), À(n) étant le plus petit commun multiple entre p- 1 et q-1, le procédé comprenant une étape de perturbation du calcul de la valeur À(n), en sorte à obtenir, en lieu et place de la valeur À(n), une valeur À'(n) 5 = À(n)/a, avec a divisant À(n), ladite perturbation amenant à calculer une clé privée d', en lieu et place de la clé privée d telle que d'.e = 1 mod À(n)/a. Un procédé selon le deuxième aspect permet de tester des dispositifs électroniques mettant en oeuvre une génération de paires de clés, en vérifiant leur réaction vis-à-vis de la perturbation du calcul du plus petit commun multiple. Un procédé selon le deuxième aspect peut être mise en oeuvre dans le processus industriel de test des dispositifs électroniques mettant en oeuvre une génération de clé cryptographiques, par exemple en laboratoire de test. Ladite étape de perturbation peut permettre de mettre à jour une vulnérabilité 15 dans la résistance à un calcul erroné de la valeur À(n). Un troisième aspect de l'invention concerne un programme d'ordinateur ainsi qu'un produit programme d'ordinateur et un support de stockage pour de tels programme et produit, permettant la mise en oeuvre d'un procédé selon le premier ou le deuxième aspect lorsque le programme est 20 chargé et exécuté par un processeur d'un dispositif électronique, par exemple un dispositif cryptographique. Un quatrième aspect concerne un dispositif électronique, par exemple un dispositif cryptographique, configuré pour la mise en oeuvre d'un procédé selon le premier aspect ou le deuxième aspect. 25 Par exemple, un dispositif selon le troisième aspect est une entité électronique portable. Le dispositif selon le troisième aspect peut être une carte à puce.

D'autres types de dispositifs peuvent être envisagés, notamment les documents de sécurité (passeport électronique, cartes d'identité électronique ou autre), les clés USB, les téléphones mobiles ou « smartphones ». D'autres avantages, buts et caractéristiques de la présente invention 5 ressortent de la description détaillée qui suit, faite à titre d'exemple non limitatif, au regard des dessins annexés dans lesquels: - la figure 1 illustre un procédé de test d'intégrité de génération de clés ; - la figure 2 illustre un procédé de génération de paire de clés; 10 - la figure 3 illustre schématiquement un dispositif selon des modes de réalisation. Dans la suite, des modes de réalisation sont décrits. Cependant, de manière liminaire, il est décrit un procédé de test d'intégrité de génération de paires de clés cryptographiques. Ce procédé de test peut être utilisé pour des 15 clés cryptographiques utilisées dans des mécanismes de chiffrement et/ou de signature numérique. Ainsi, ce procédé peut être utilisé avant même de connaître l'usage ultérieur de la paire de clés générée. On suppose qu'une clé cryptographique publique (e, n) et une clé cryptographique privée (d, n) sont générées telles que : 20 - n=p.q, avec p et q étant des nombres premiers, - 1 < e < 1(n) et e et (I) (n) sont premiers entre eux (gcd(e, 1(n))=1), avec 1(n) = (p-1).(q-1) (I) étant la fonction indicatrice d'Euler, ou « totient » en terminologie anglo-saxonne), et - d.e = 1 mod À(n), À(n) étant le plus petit commun multiple entre p- 25 1 et q-1 (À(n)=lcm(p-1, q-1)). Ensuite, comme illustré par la figure 1, lors d'une première étape 100 un message m (m appartenant à Zn, le groupe additif des entiers modulo n), est chiffré avec l'exposant publique e en sorte à obtenir un premier message chiffré c = me mod n. Ensuite, lors de l'étape 102, le message chiffré c est déchiffré avec la clé privée d en sorte à obtenir un message déchiffré m' = Cd mod n.

Il est ensuite vérifié, lors d'une étape 103, si le message initial m et le message déchiffré sont les mêmes (m' = m). Si ce n'est pas le cas (NOK), il est déterminé lors de l'étape 104 que la paire de clé générée n'est pas intègre. Si par contre le message initial m et le message déchiffré sont les mêmes (OK), le message déchiffré m' est chiffré, lors d'une étape 105, avec l'exposant public e en sorte à obtenir un deuxième message chiffré c' = (m')e mod n. Il est ensuite vérifié, lors d'une étape 106, si le premier message chiffré c et le deuxième message chiffré c' sont les mêmes (c' = c). Si tel est le cas (OK), il est déterminé lors de l'étape 107 que le test d'intégrité est réussi. Sinon (NOK), il est déterminé, lors de l'étape 108, que la paire de clé générée n'est pas intègre. Certaines paires de clés non intègres peuvent passer avec succès les tests d'intégrités comme celui décrit ci-dessus ou d'autres tests de l'art antérieur. Par exemple, si, au lieu de générer l'exposant privé d, il est généré 20 un nombre d' tel que : - d'.e = 1 mod À(n)/a, - 1 a, - a divise À(n), il peut arriver que pour des messages, la paire de clés avec les nombres d' et e 25 passe le test avec succès alors qu'une erreur s'est produite sur l'exposant privé d. En plus d'être une source d'erreurs pour un système cryptographique utilisant les clés, cela peut être une source d'attaques par des tiers malveillants.

Par exemple, le nombre d' peut être généré par erreur si le calcul du plus petit commun multiple de p-1 et q-1 (qui doit normalement donner À(n)) est entaché d'une erreur. Le nombre d' peut être calculé par mise en oeuvre de l'algorithme d'Euclide. Les entiers a et b sont calculé en sorte que e.a + b. À(n)/a = 1 (relation de Bezout). Le nombre d' est alors obtenu comme d' = a mod À(n)/a. Dans ces conditions, on a bien d'.e = 1 mod À(n)/a. En provoquant la détermination du nombre d' au lieu du nombre d, un attaquant peut ainsi retrouver l'un des facteurs secrets (p et q) du nombre n tel que n = p.q.

En effet, supposons que l'entier a divise le nombre (a-1) sanspour autant diviser le nombre (p-1)gcd(p-1,q-1)' alors en notant t le nombre tel que t = (q-1) a.gcd(p-1,q-1)' on obtient d = e-1 mod t.(p-1). Ainsi, l'exposant privé est l'inverse de l'exposant public dans l'anneau Zp_ 15 1 au lieu de l'anneau ZÀ(i). Pour un message aléatoire m, on a alors : (md)e = m mod n, mais on a aussi (md)e = m mod p. Un multiple du facteur p peut ainsi être obtenu comme (md)e - m mod n. 20 Un attaquant peut ainsi perturber la génération de clés et demander la signature de messages aléatoires. Pour certains messages m, la signature s obtenue est telle que gcd(se - m,n) donne un facteur de n. Supposons que le plus petit commun multiple de p-1 et q-1 est calculé (p-1).(q-1) comme suit, .1(n) = gcd(p-1,q-1)' avec gcd(p-1, q-1) étant le plus grand commun 25 diviseur de p-1 et q-1. Si le calcul de ce plus grand commun diviseur donne a. gcd(p-1, q-1) (le produit de a par gcd(p-1, q-1)) au lieu de gcd(p-1, q-1), on calcule d' au lieu de calculer d. Les inventeurs ont remarqué que les tests d'intégrité actuellement utilisés pouvaient ne pas détecter certaines erreurs de génération de paires de 5 clés, notamment lors d'attaques telle qu'évoquées ci-dessus. Un attaquant peut provoquer des erreurs dans le calcul de l'exposant privé par observation par canal auxiliaire du fonctionnement du dispositif mettant en oeuvre la génération de clé puis par attaque physique du dispositif pour perturber ce fonctionnement. L'attaquant peut par exemple utiliser des 10 lasers pour perturber le dispositif ou encore perturber l'alimentation électrique de celui-ci. A titre d'illustration, si une erreur a (telle qu'évoquée ci-dessus) est introduite de sorte que le nombre a divise la valeur k.À(n)/a (k étant un entier), et que le nombre d' est déterminé à la place du nombre d tel que d'.e = 1 + 15 k.À(n)/a alors un test d'intégrité tel que par exemple défini dans la norme FIPS 140-2 exécuté sur un message m d'ordre s ne permet pas de détecter l'erreur si s divise k.À(n)/a alors que le test d'intégrité permet de la détecter si s ne divise pas k.À(n)/a. On rappelle que l'ordre s du message m dans le groupe additif est le nombre de fois qu'il faut additionner le message m pour obtenir 1. 20 En effet, soient e, p et q des paramètres RSA avec n = p.q. si d' = e-1 mod À(n)/a est l'exposant erroné, l'exposant correct étant d = e-1 mod À(n), si d' est différent de d alors 3m E Zn tel que (me)d' # mmod n. Par ailleurs, si Vm E Zn on a (me)d' = m mod n alors cl = d'. La démonstration de ceci est possible mais n'est pas présentée ici dans un souci de concision. 25 Ci-après, sont décrits des procédés permettant de rendre les tests d'intégrité sensibles à ce type d'erreurs. Les tests d'intégrité peuvent être mis en oeuvre lors de la génération des clés ou après.

En référence à la figure 2, il est décrit un procédé de génération de paire de clés cryptographiques évitant que la clé cryptographique privée soit corrompue par le calcul du plus petit commun multiple. Lors d'une étape 200, un nombre p est généré aléatoirement dans 5 Zn. Il est ensuite vérifié lors de l'étape 201 que le nombre p est premier. Si ce n'est pas le cas (NOK), l'étape 200 est répétée. Si p est bien premier (OK), il est généré aléatoirement lors de l'étape 202 un nombre q dans Zn. Il est ensuite vérifié lors de l'étape 203 que le nombre q est premier. Si ce n'est pas le cas (NOK), l'étape 203 est répétée. Si q est bien premier (OK), il est calculé lors de 10 l'étape 204 le produit n des nombres p et q (n = p.q). Les nombres suivants sont ensuite calculés : - le nombre 1(n), lors de l'étape 205, avec 1(n) = (p-1).(q-1) étant la fonction indicatrice d'Euler, ou « totient » en terminologie anglo-saxonne), et 15 - le nombre y, lors de l'étape 206, y étant le plus petit commun multiple de p-1 et q-1 uniquement dans le cas où il n'est pas erroné (y = lcm(p-1, q-1)). Il est ensuite procédé au test de l'étape 207 lors duquel il est vérifié que y est congru à 0 modulo p-1 (y = 0 mod p-1) et que y est congru à 0 20 modulo q-1(y = 0 mod q-1). Si le test n'est pas satisfait (NOK), l'étape 206 est répétée. Sinon (OK), un message peut être retourné lors d'une étape 208. Ce message peut informer un utilisateur qu'une mauvaise clé a été générée. La clé publique est générée lors de l'étape 209 avec le calcul de l'exposant public e tel que : 25 - 1 < e < (I)(n) et - e et (I) (n) sont premiers entre eux (gcd(e, (I)(n))=1), avec 1(n) = (p-1).(q-1) (I) étant la fonction indicatrice d'Euler, ou « totient » en terminologie anglo-saxonne).

La clé privée est générée lors de l'étape 210 avec le calcul du nombre d tel que d.e = 1 mod À(n). Un procédé tel que décrit en référence à la figure 2 offre une sécurité accrue avec un cout de calcul supplémentaire faible.

En effet, les erreurs éventuelles lors du calcul du plus petit commun multiple (lcm) sont détectées car (on le démontre par l'absurde) si g = gcd(p1,q-1) alors À(n) = (p-1).(q-1)/g. En outre on suppose qu'il existe un nombre À'(n) tel que À'(n) = À(n)/a = (p-1).(q-1)/(a.g), avec a tel que y = 0 mod p-1 et y = 0 mod q-1. On a ainsi À'(n) mod p - 1 = 0 À'(n) mod q - 1 = 0. Cela implique que (p-1)/(a.g) est un entier et que (q-1)/(a.g) aussi. Cependant, par définition du plus grand commun diviseur, il n'existe pas d'entier R plus grand que g tel que (p-1)/6 et (q-1)/6 soient entiers. La seule valeur possible pour a est donc 1, ce qui contredit l'hypothèse initiale. La figure 3 illustre schématiquement un dispositif selon des modes 15 de réalisation. Le dispositif 30 de la figure 3 comporte une unité de mémoire 31 (MEM). Cette unité de mémoire comporte une mémoire vive pour stocker de manière non durable des données de calcul utilisées lors de la mise en oeuvre d'un procédé conforme à l'invention, selon divers modes de réalisation. L'unité 20 de mémoire comporte par ailleurs une mémoire non volatile (par exemple du type EEPROM) pour stocker par exemple un programme d'ordinateur, selon un mode de réalisation, pour son exécution par un processeur (non représenté) d'une unité de traitement 31 (PROC) du dispositif. Le dispositif comporte par ailleurs une unité de communication 33 25 (COM), par exemple pour échanger des données avec un autre dispositif conformément à des modes de réalisation. Les échanges de données entre dispositifs peuvent se faire selon le protocole APDU, sigle de « Application Protocol Data Unit », tels que définis dans la norme ISO 7816 partie 4.

L'unité de communication peut ainsi comporter une interface entrée/sortie apte à échanger selon ce protocole. Les données échangées peuvent se faire par des commandes APDU et des réponses à ce type de commandes.

Un dispositif selon des modes de réalisation peut être conforme à la norme IS07816. Il peut par exemple s'agir d'une carte à puce ou d'un élément sécurisé. Un dispositif selon des modes de réalisation est par exemple un circuit intégré. La présente invention a été décrite et illustrée dans la présente description détaillée en référence aux figures jointes. Toutefois la présente invention ne se limite pas aux formes de réalisation présentées. D'autres variantes, modes de réalisation et combinaisons de caractéristiques peuvent être déduits et mis en oeuvre par la personne du métier à la lecture de la 15 présente description et des figures annexées. Dans les revendications, le terme "comporter" n'exclut pas d'autres éléments ou d'autres étapes. L'article indéfini « un » n'exclut pas le pluriel. Un seul processeur ou plusieurs autres unités peuvent être utilisées pour mettre en oeuvre l'invention. Les différentes caractéristiques présentées et/ou 20 revendiquées peuvent être avantageusement combinées. Leur présence dans la description ou dans des revendications dépendantes différentes, n'exclut pas en effet la possibilité de les combiner. Les signes de référence ne sauraient être compris comme limitant la portée de l'invention.

Claims (4)

1. REVENDICATIONS1. Procédé de génération de paire de clés cryptographiqueS publique et privée dans le groupe additif des entiers modulo n, avec n étant le produit de 5 deux nombres premiers p et q, le procédé comportant les étapes suivantes : de calcul (209) d'un exposant public e pour ladite clé publique, et de calcul (210) d'un exposant privé d pour ladite clé privée à partir dudit exposant public et dudit module publique, avec d.e = 1 mod À(n), À(n) étant le plus petit commun multiple entre p-1 et q- 10 1, caractérisé en ce que le procédé comporte en outre, une étape : - de vérification (207) pour vérifier que À(n) = 0 mod (p-1) et À(n) = 0 mod (q-1). 15
2. 2. Programme d'ordinateur comportant des instructions pour la mise en oeuvre d'un procédé selon la revendication 1 lorsqu'il est chargé et exécuté par un processeur d'un dispositif de cryptographie.
3. 3. Dispositif cryptographique comportant une unité de traitement 20 configurée pour mettre en oeuvre un procédé selon la revendication 1.
4. 4. Entité électronique portable comprenant un dispositif selon la revendication 3. 25