Brevet FR3015079A1 — publié le 20150619

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é probabilistique, par exemple de type Miller-Rabin, par exemple conformement à 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 Un procédé selon le premier aspect permet d'améliorer significativement la fiabilité des tests d'intégrité, avec un coût de calcul 5 supplémentaire optimal.. Par exemple, ledit nombre M est compris entre 2 et 7. Ledit nombre M est avantageusement égal à 7. Par exemple, ladite première étape est le chiffrement de ladite donnée initiale avec la clé publique et ladite deuxième étape est le déchiffrement du premier résultat avec la clé privée. Selon des modes de réalisation, ledit test d'intégrité comporte en outre, en cas de comparaison positive entre ledit deuxième résultat et de ladite donnée de test initiale : - une troisième étape de chiffrement dudit deuxième résultat, ladite 15 troisième étape permettant de générer un troisième résultat, - une comparaison dudit troisième résultat et dudit premier résultat. Par exemple, ladite première étape est la signature de ladite donnée initiale avec la clé privée et ladite deuxième étape est la vérification du premier résultat avec la clé publique. 20 Ledit test d'intégrité comporte par exemple en outre, en cas de comparaison positive entre ledit deuxième résultat et de ladite donnée de test initiale : - une quatrième étape de déchiffrement dudit deuxième résultat, ladite quatrième étape permettant de générer un quatrième résultat, 25 - une comparaison dudit quatrième résultat et dudit premier résultat. Par exemple, des messages aléatoires sont mis en oeuvre à chaque réexécution. Par exemple, des messages différents de 0 et différents de 1 sont mise en oeuvre à chaque réexécution. 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 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é 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 chargé et exécuté par un processeur d'un dispositif électronique, par exemple un dispositif cryptographique. Un troisième aspect concerne un dispositif électronique, par exemple un dispositif cryptographique, configuré pour la mise en oeuvre d'un procédé selon le premier ou le deuxième aspect. 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 20 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 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 25 Clés ; - la figure 2 illustre un procédé de vérification d'intégrité de clés; - 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 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 : - n=p.q, avec p et q étant des nombres premiers, - 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 5 antérieur. Par exemple, si, au lieu de générer l'exposant privé d, il est généré un nombre d' tel que : - d'.e = 1 mod À(n)/a, - 1 a, 10 - a divise À(n), il peut arriver que pour des messages, la paire de clés avec les nombres d' et e 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 15 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. 20 À(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.a. 25 En effet, supposons que l'entier a divise le nombre (a-1) sans pour (p-1) autant diviser le nombre 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_ 1 au lieu de l'anneau ZÀ(i). Pour un message aléatoire m, on a alors : (1-1r1d)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. Un attaquant peut ainsi perturber la génération de clés et demander la 10 signature de messages aléatoires. Pour certains messages m, la signature s obtenu 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é comme (p-1).(q-1) suit, .1(n) = gccl(p-1,q-1) avec gcd(p-1, q-1) étant le plus grand commun diviseur de p-1 et q-1. Si le calcul de ce plus grand commun diviseur donne a. gcd(p-1, 15 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 clés, notamment lors d'attaques telle qu'évoquées ci-dessus. 20 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 lasers pour perturber le dispositif ou encore perturber l'alimentation électrique 25 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 + 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 qu'il 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. En effet, soient e, p et q des paramètres RSA avec n = p.q. si d' = e-1 10 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' # m mod n. Par ailleurs, si Vm E Zn on a (me)d' = m mod n alors cl = . La démonstration de ceci est possible mais n'est pas présentée ici dans un souci de concision. Ci-après, il est décrit un procédé permettant de rendre les tests 15 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 test d'intégrité de paire de clés cryptographiques. Le procédé consiste à répéter un certain nombre de fois M, un test 20 d'intégrité, tel que par exemple celui décrit en référence à la figure 1 à partir de messages différents. Par exemple il s'agit de messages aléatoires. Ces messages doivent être différents de 0 et de 1. Les inventeurs ont déterminé que, par exemple, pour un nombre M = 7 répétitions avec des messages différents, moins de 1`)/0 des paires de clé 25 corrompues passaient le test. Il y a ainsi une probabilité de plus de 99% de détecter la non intégrité d'une paire de clés, et ce sans forcément utiliser de nouveaux tests. La multiplication du coût de calcul par M est acceptable au vu du niveau de fiabilité du test (99%). Lors d'une étape 200, un compteur i est initialisé à la valeur 1. Ensuite, lors d'une étape 201, un message m différent de 0 et de 1, est tiré aléatoirement dans l'ensemble Zn. Un test d'intégrité, par exemple tel que décrit en référence à la figure 5 1, est ensuite mis en oeuvre lors d'une étape 202. Si le test n'est pas satisfait (NOK), il est déterminé lors d'une étape 203 que la paire de clés n'est pas intègre. Si par contre le test est satisfait (OK), il est testé lors d'une étape 204, si le compteur est égal à la valeur M. Si tel est le cas (OK), le test de l'étape 202 a été exécuté le nombre M de fois et il est déterminé lors de l'étape 205 que la paire de clés est intègre. Si par contre le compteur i n'a pas atteint la valeur M (NOK), le compteur est incrémenté lors de l'étape 206 et le processus retourne à l'étape 201. Les inventeurs ont obtenu les résultats suivants: Nombre de clés réellement erronées sur 10 000 générations de clé perturbées Taux de détection avec 1 message Taux de détection avec 2 massages a = 2 5 057 58.4% 81.3% a = 3 6 683 70.3% 90.5% a = 4 7 506 72.7% 90.0% a = 5 7 976 81.6% 96.4% a = 6 8 206 75.0% 91.8% a = 7 8 597 86.5% 98.1% a = 8 8 705 82.4% 94.7% 15 Lorsque l'erreur a (évoquée ci-avant) est de 2 (a = 2), les inventeurs ont obtenu les résultats suivants : Nombre de messages 1 2 3 4 5 6 7 Taux de détection 58.4% 81.3% 91.1% 95.7% 97.9% 98.9% 99.5% Un nombre de 7 répétitions avec des messages différents est ainsi avantageux. Cependant, il est possible de retenir un nombre de répétions de 2 à 6 (c'est-à-dire 2, 3, 4, 5 ou 6). La figure 3 illustre schématiquement un dispositif selon des modes 5 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é 10 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 15 (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 20 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 25 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 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 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. REVENDICATIONS1. Procédé de vérification d'intégrité de paire de clés cryptographiques publique et privée, le procédé comportant l'exécution d'un test 5 d'intégrité (202), dans lequel le test d'intégrité comporte: - au moins une première étape (100) mettant en oeuvre l'une des clés privée et publique et une donnée de test initiale, ladite première étape permettant de générer un premier résultat, - au moins une deuxième étape (102) mettant en oeuvre au moins 10 ledit premier résultat et la clé non utilisée lors de la au moins une première étape, ladite deuxième étape permettant de générer un deuxième résultat, et - une comparaison (103) dudit deuxième résultat et de ladite donnée de test initiale, 15 caractérisé en ce que le test est réexécuté à chaque comparaison positive, et en ce que le test est exécuté au moins un nombre M de fois, M étant supérieur ou égal à 2. 2. Procédé selon la revendication 1, dans lequel ledit nombre M est compris entre 2 et 7. 20 3. Procédé selon la revendication 1, dans lequel ledit nombre M est égal à 7. 4. Procédé selon l'une des revendications 1 à 3, dans lequel ladite première étape est le chiffrement de ladite donnée initiale avec la clé publique et ladite deuxième étape est le déchiffrement du premier résultat avec la clé 25 privée. 5. Procédé selon la revendication 4, dans lequel ledit test d'intégrité comporte en outre, en cas de comparaison positive entre ledit deuxième résultat et de ladite donnée de test initiale : - une troisième étape (105) de chiffrement dudit deuxième résultat, ladite troisième étape permettant de générer un troisième résultat, - une comparaison (106) dudit troisième résultat et dudit premier résultat. 6. Procédé selon la revendication 1, dans lequel ladite première étape est la signature de ladite donnée initiale avec la clé privée et ladite deuxième étape est la vérification du premier résultat avec la clé publique. 7. Procédé selon la revendication 6, dans lequel ledit test d'intégrité comporte en outre, en cas de comparaison positive entre ledit deuxième résultat et de ladite donnée de test initiale : 15 - une quatrième étape de déchiffrement dudit deuxième résultat, ladite quatrième étape permettant de générer un quatrième résultat, - une comparaison dudit quatrième résultat et dudit premier résultat. 20 8. Procédé selon l'une des revendications 1 à 7, mettant en oeuvre des messages aléatoires à chaque réexécution. 9. Procédé selon l'une des revendications 1 à 8, mettant en oeuvre des messages différents de 0 et différents de 1 à chaque réexécution. 10. Procédé selon l'une des revendications 1 à 9, mis en oeuvre 25 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. 11. 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 12. Programme d'ordinateur comportant des instructions pour 15 la mise en oeuvre d'un procédé selon l'une quelconque des revendications 1 à 11 lorsqu'il est chargé et exécuté par un processeur d'un dispositif de cryptographie. 13. Dispositif cryptographique comportant une unité de traitement configurée pour mettre en oeuvre un procédé selon l'une des zo revendications 1 à 11. 14. Entité électronique portable comprenant un dispositif selon la revendication 13.