Brevet FR3015080A1 — 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 Selon des modes de réalisation, lors de ladite étape de vérification, il est vérifié si le produit de l'exposant public e par ledit exposant privé d est congru à 1 modulo le produit (p'-1).(q'-1). Par exemple, ladite étape de vérification porte sur le plus petit 5 commun multiple À(n) entre (p-1) et (q-1). Par exemple encore, lors de ladite étape de vérification, le plus petit commun multiple À(n) entre (p-1) et (q-1) est comparé au plus petit commun multiple À'(n) entre (p'-1) et (q'-1). Selon des modes de réalisation, lors de ladite étape de vérification, il Io est vérifié si : - le plus petit commun multiple À(n) entre (p-1) et (q-1) est congru à 0 modulo (p'-1), et - le plus petit commun multiple À(n) entre (p-1) et (q-1) est congru à 0 modulo (q'-1). 15 Lesdits facteurs candidats peuvent par exemple être calculés par un algorithme de factorisation probabiliste. Par exemple, le procédé est mise 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 20 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 25 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, ).(q-1), et 5 - 1 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 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 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é zo 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 zo 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, 25 - 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 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 10 peut ainsi retrouver l'un des facteurs secrets (p et q) du nombre n tel que n = P.a. En effet, supposons que l'entier a divise le nombre (q-1) sans pour 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)' 15 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 : (md)e = m mod n, mais on a aussi 20 (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 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 suit, Â(n) = 1).(c1 avec gcd(p-1, q-1) étant le plus grand commun diviseur gcep-1,q-1) 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 5 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. Un attaquant peut provoquer des erreurs dans le calcul de l'exposant 10 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 de celui-ci. 15 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 20 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 mod À(n)/a est l'exposant erroné, l'exposant correct étant d = e-1 mod À(n), si d' 25 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 d = . 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 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é 5 de paire de clés cryptographiques qui peut être mis en oeuvre lorsque les nombres premiers p et q à partir desquels les clés sont générés ne sont pas connus. Lors d'une première étape 200, un compteur i est initialisé à la valeur 1. Ensuite, un algorithme de factorisation probabiliste est mis en oeuvre lors d'une étape 201. Cet algorithme permet, à partir de n (n = p.q), de l'exposant publique e de la clé publique et de d' l'exposant privée de la clé privée dont on cherche à savoir si elle est erronée ou non, de retrouver les facteurs premiers p' et q' de n. Une fois l'étape 201 exécutée, il est déterminé lors d'une étape 202 15 si elle a permis de retrouver les nombres p et q. Si l'exécution de l'étape 201 n'a pas permis de déterminer ces nombres (NOK), il est vérifié si le compteur i a atteint la valeur M lors de l'étape 203. La valeur M est un nombre maximum de fois que l'algorithme de l'étape 201 doit être exécuté. Si le nombre M est atteint (OK), il est déterminé lors 20 d'une étape 204 que la paire de clés n'est pas intègre. Si au contraire (NOK), la valeur M n'est pas encore atteinte, l'étape 201 est exécutée une nouvelle fois. De retour à l'étape 202, si à l'étape 201, il a été possible de déterminer les nombres p et q (OK), une étape 205 est mise en oeuvre lors de laquelle le plus petit commun multiple À'(n) des nombres p'-1 et q'-1 est calculé 25 (À'(n) = (p'-1).(q'-1)). Ensuite, il est testé lors d'une étape 206, si le produit e.d' est congru à 1 modulo À'(n) (e.d' = 1 mod À'(n)). Si tel est le cas (OK), il est déterminé lors de l'étape 207 que la paire de clés est intègre. Sinon (NOK), le processus repasse à l'étape 204. Alternativement, ou en combinaison, il peut être procédé à la comparaison entre À'(n) et À(n) pour vérifier que À'(n) = À (n). Alternativement, ou en combinaison, il peut par ailleurs être vérifié si À(n) mod p'-1 et À(n) mod q'-1 sont tous les deux égaux à 0. Dans ces alternatives, la valeur À(n), calculée à partir de p et q est gardée en mémoire puis lue pour les vérifications. Encore alternativement, ou en combinaison, les valeurs p' et q' peuvent être utilisées pour vérifier que e.d' = 1 mod (p' -1).(q'-1). La recherche des facteurs p et q de n peut avoir un coût de calcul de l'ordre de O(u.log3(n)), typiquement pour un algorithme de factorisation probabiliste. La probabilité de trouver un facteur de n après u essais est supérieure ou égale à 1- 2-u. Ainsi, après dix essais, la probabilité de factorisation est supérieure ou égale à 99,9%. Une fois la factorisation effectuée, le coût du test de l'étape 406 est 15 dominé par le coût du calcul du plus grand commun diviseur mis en oeuvre pour calculer le plus petit commun multiple (on rappelle que lcm(p'-1 ; q'-1) = (p'- 1).(q'-1)/gcd(p'-1, q'-1)). Ainsi, le coût total du procédé est de l'ordre de O(log3(n)) + O(log3(n)) = O(log3(n)) pour une probabilité de détection supérieure ou égale à 20 99,9%. Un procédé de vérification classique est quant à lui d'un coût de l'ordre de O(log3(n)) pour une probabilité de détection de l'ordre de 50% (données expérimentales). La figure 3 illustre schématiquement un dispositif selon des modes de réalisation. 25 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é 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 (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 15 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 20 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. 25 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 dans le groupe additif des entiers modulo 5 n, avec n étant le produit de deux nombres premiers p et q, le procédé comportant les étapes suivantes : - de calcul (201), à partir dudit nombre n, d'un exposant public e de ladite clé publique, et d'un exposant privé d de ladite clé privée, de deux facteurs candidats p' et q' correspondant respectivement 10 aux nombres p et q, - de vérification (206) pour vérifier la cohérence dudit exposant privé par rapport audit exposant public et audit nombre n, ladite étape de vérification faisant intervenir lesdits facteurs candidats. 2. Procédé selon la revendication 1, dans lequel ladite étape de 15 vérification porte sur le produit de l'exposant public e par ledit exposant privé d. 3. Procédé selon la revendication 2, dans lequel lors de ladite étape de vérification, il est vérifié si le produit de l'exposant public e par ledit exposant privé d est congru à 1 modulo À'(n), le plus petit commun multiple entre (p'-1) et (q'-1). 20 4. Procédé selon la revendication 2, dans lequel lors de ladite étape de vérification, il est vérifié si le produit de l'exposant public e par ledit exposant privé d est congru à 1 modulo le produit (p'-1).(q'-1). 5. Procédé selon la revendication 1, dans lequel ladite étape de vérification porte sur le plus petit commun multiple À(n) entre (p-1) et (q-1). 25 6. Procédé selon la revendication 5, dans lequel lors de ladite étape de vérification, le plus petit commun multiple À(n) entre (p-1) et (q-1) est comparé au plus petit commun multiple À'(n) entre (p'-1) et (q'-1). 7. Procédé selon la revendication 5, dans lequel lors de ladite étape de vérification, il est vérifié si : - le plus petit commun multiple À(n) entre (p-1) et (q-1) est congru à 0 modulo (p'-1), et - le plus petit commun multiple À(n) entre (p-1) et (q-1) est congru à 0 modulo (q'-1). 8. Procédé selon l'une des revendications 1 à 7, dans lequel lesdits facteurs candidats sont calculés par un algorithme de factorisation probabiliste. 9. Procédé de test de sécurité d'un dispositif électronique vis-à-vis 10 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 10. Programme d'ordinateur comportant des instructions pour la mise en oeuvre d'un procédé selon l'une quelconque des revendications 1 à 9 lorsqu'il est chargé et exécuté par un processeur d'un dispositif de 25 cryptographie. 11. Dispositif cryptographique comportant une unité de traitement configurée pour mettre en oeuvre un procédé selon l'une des revendications 1 à 9. 12. Entité électronique portable comprenant un dispositif selon 5 la revendication 11.