Brevet FR2830146A1 — publié le 20030328

PROCEDE DE MISE EN OEUVRE, DANS UN COMPOSANT ELECTRONIQUE, D'UN ALGORITHME DE CRYPTOGRAPHIE ET COMPOSANT CORRESPONDANT L'invention concerne un procédé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie. L'invention se rapporte également au composant électronique correspondant. De tels composants sont utilisés dans des applications où l'accès à des services ou à des données est sévèrement contrôlé. Ils ont une architecture formée autour d'un microprocesseur et de mémoires, dont une mémoire programme de type ROM ("Read Only Memory" en anglais) qui contient le (s) nombre (s) secret (s) d. Ces composants sont utilisés dans des systèmes informatiques, embarqués ou non ; ils sont notamment utilisés dans les cartes à puce, pour certaines applications de celles-ci. Ce sont par exemple des applications d'accès à certaines banques de données, des applications bancaires, des applications de télépéage, par exemple pour la télévision, la distribution d'essence ou encore le passage de péages d'autoroutes. Ces composants ou ces cartes mettent donc en oeuvre un algorithme de cryptographie pour assurer le chiffrement de données émises et/ou le déchiffrement de données reçues lorsque celles-ci doivent demeurer confidentielles. De manière générale et succincte, ces algorithmes cryptographiques ont notamment pour fonction le chiffrement ou la signature numérique d'un message. A partir de ce message appliqué en entrée à la carte par un système hôte (serveur, distributeur bancaire...) et de nombreux secrets contenus dans la carte, la carte fournit en retour au système hôte le message chiffré ou signé, ce qui permet par exemple au système hôte d'authentifier le composant ou la carte, d'échanger des données,.... Les caractéristiques des algorithmes de cryptographie sont connues : calculs effectués, paramètres utilisés. La seule inconnue est le ou les nombres secrets contenus en mémoire programme. Toute la sécurité de ces algorithmes de cryptographie tient dans ce (s) nombre (s) secret (s) contenu (s) dans la carte et inconnu (s) du monde extérieur à cette carte. Ce nombre secret ne peut être déduit de la seule connaissance du message appliqué en entrée et du message chiffré fourni en retour. Or il est apparu que des attaques externes permettent à des tiers mal intentionnés de trouver le (s) nombre (s) secret (s) contenu (s) dans cette carte. Dans le domaine de la carte à puce, entre autres, il existe plusieurs attaques possibles, dont une dite "attaque par faute". Dans ce type d'attaque, l'attaquant injecte une faute quelconque pendant le calcul d'un algorithme cryptographique, dans le but d'exploiter la présence de cette faute pour extraire une information secrète. La faute peut aussi provenir d'une erreur de calcul due au matériel mettant en oeuvre l'algorithme cryptographique ; on considère néanmoins, dans un cas comme dans l'autre, qu'il s'agit d'une attaque par faute. Ce type d'attaque est notamment envisageable avec l'algorithme RSA (du nom de ses auteurs Rivert, Shamir, Adleman), qui est celui le plus utilisé en cryptographie dans ce domaine d'application. La sécurité de l'algorithme RSA est basée sur la difficulté de factoriser de grands nombres. Ces algorithmes utilisent notamment des calculs d'exponentiation à la puissance d, d étant un nombre secret. On rappelle brièvement les principales étapes de l'algorithme RSA. On établit un nombre N qui est le produit de deux nombres premiers p et q (N=p. q), ainsi qu'un exposant public ou clé publique e et un exposant privé ou clé privée ou secrète d, satisfaisant la relation : e. d = 1 (modulo Â (N) ), (1) Â (. ) étant la fonction de Carmichael. Selon un premier mode de fonctionnement de l'algorithme RSA dit standard, les paramètres publics sont (N, e) et les paramètres privés sont (N, d). Etant donné x compris dans l'intervalle 0, N [, l'opération publique sur x qui peut être par exemple le chiffrement du message x ou encore la vérification de la signature x, consiste à calculer : y = xe modulo N (2) L'opération privée correspondante qui peut être par exemple le déchiffrement du message chiffré y ou la génération d'une signature x, consiste à calculer : yd modulo N (3) avec x= yd modulo N puisque e. d = l (modulo Â. (N) ). On va présenter un autre mode de fonctionnement dit mode CRT car basé sur le théorème des restes chinois ("Chinese Remainder Theorem"ou CRT en anglais) et quatre fois plus rapide que celui de l'algorithme RSA standard. Selon ce RSA mode CRT, on n'effectue pas directement les calculs modulo N mais on effectue d'abord les calculs modulo p et modulo q. Les paramètres publics sont (N, e) mais les paramètres privés sont (p, q, d) ou (p, q, dp, dq, iq) avec dp = d modulo (p-1), dq = d modulo (q-1) et iq= q-l modulo p. Par la relation (1), on obtient : edp=l modulo (p-1) et edq=l modulo (q-1) (4) L'opération publique s'effectue de la même façon que pour le mode de fonctionnement standard ; par contre pour l'opération privée, on calcule d'abord : xp = y Pmodp et -y"modq Ensuite, par application du théorème des restes chinois, on obtient x = yd mod N par : x = CRT (xp, xq) =Xq+q [iq (Xp-Xq) modulo p] (5) L'algorithme RSA a été présenté avec deux facteurs premiers p et q, pour simplifier l'exposé. On peut le généraliser au cas où N est le produit de deux entiers p et q tels que pgcd (p, q) =l. Dans ce cas, dp = d (modulo Â, (p) ), dq = d (modulo # (q) ), iq reste inchangé par rapport au cas précédent, edp=l (modulo Â. (p) ) et edq=l (modulo Â (q) ), et les calculs de xp, Xq et x sont inchangés. Cette généralisation s'applique au mode standard comme au mode CRT. On va à présent décrire un exemple d'attaque par faute basée sur l'obtention de deux signatures du même message, l'une correcte x et l'autre incorrecte notée x. La signature incorrecte a par exemple été obtenue de la manière suivante. L'attaquant, par une méthode quelconque, injecte une erreur durant le calcul de xp, mais pas durant celui de Xq. La valeur de xp est alors incorrecte et notée Axp. Par contre, la valeur de Xq est correcte. De ce fait, lorsque l'on recombine les valeurs axe et Xq en appliquant le théorème des restes chinois, la signature résultante ^x est incorrecte. Il suffit alors à l'attaquant qui connaît bien sûr par ailleurs les paramètres publics (N, e), de calculer le plus grand commun diviseur (pgcd) avec N, soit : pgdc (x-x, N). Or, pgdc (x-x, N) = q. Il obtient alors le facteur secret q et donc p et dp et dq. De ce fait, le code RSA est effectivement cassé. Autrement dit, si quelqu'un est capable d'injecter une erreur quelconque durant un calcul modulo p alors que le calcul modulo q est correct ou réciproquement, il peut casser complètement le code RSA. Il est également possible de casser le code RSA à partir d'une signature incorrecte d'un message connu. Plusieurs cas d'attaques par faute sont présentés dans la publication "On the Importance of Checking Cryptographic Protocols for Faults"de D. Boneh, R. A. DeMillo et R. J. Lipton, Advances in CryptologyEUROCRYPT'97 pp. 37-51, à laquelle on peut se reporter. Une première contremesure pour éviter ce genre de scénario consiste à recalculer l'ensemble de l'algorithme. On compare les valeurs obtenues à l'issue des calculs successifs. S'ils sont identiques, on suppose qu'il n'y a pas eu d'erreur injectée. Un problème avec cette approche est qu'elle ne détecte pas une faute permanente. Par exemple, on ne peut déceler une attaque dans laquelle l'erreur injectée consiste à ce que la valeur d'un bit de mémoire soit toujours fixée à 0 ou à 1 ("sticky bit"en anglais). Une autre contre-mesure à l'attaque par faute est décrite par Shamir dans le document brevet WO 98 52319. On procède selon cette contre-mesure par l'algorithme suivant : 1. Choisir un nombre aléatoire r de faible valeur, 2. Calculer : xrp = yd modulo r. p, et Xrq = yod module r. q ; 3. Si Xrp : l ; Xrq (modulo r), alors il y a erreur, (peut-être induite par une attaque, ) et donc interruption de l'algorithme, sinon ; 4. Appliquer le théorème des restes chinois à xrp et Xrq, pour émettre x en sortie. On effectue ainsi respectivement les calculs modulo r. p et modulo r. q au lieu de modulo p et modulo q. Ensuite, on vérifie que les deux valeurs Xrp et Xrq obtenues par ces calculs sont égales modulo r. Si ces deux valeurs sont différentes, il est certain qu'il y a eu une erreur. Par contre, si elles sont égales, on peut supposer qu'il n'y a pas eu d'erreur, avec une probabilité de 1/r de se tromper dans cette supposition. Un inconvénient de cette méthode est qu'elle est probabiliste, c'est-à-dire que les erreurs sont détectées avec une probabilité inférieure à 1 et que par conséquent, elles ne sont pas toutes détectées. En outre, elle est coûteuse en temps de calcul. Un autre inconvénient de la méthode Shamir est qu'elle ne fonctionne que pour le mode CRT. Or, il est également envisageable d'utiliser le mode standard de l'algorithme RSA. La meilleure protection possible pour se protéger des attaques par faute consiste à vérifier que la valeur x obtenue lors de l'opération privée (3) ou (5) (c'est-à-dire soit en mode standard, soit en mode CRT de l'algorithme RSA), vérifie la relation (2) y = xe modulo N de l'opération publique. En effet, lorsque cette relation est vérifiée, on est assuré qu'il n'y a pas eu d'erreur pendant le déroulement de l'opération privée de l'algorithme RSA. Mais le composant ou le dispositif mettant en oeuvre l'opération privée ne dispose pas toujours de l'exposant public e, notamment lorsqu'il n'exécute que l'opération privée. Au vu de ce qui précède, l'invention propose un procédé permettant de réaliser certaines étapes d'un algorithme de cryptographie utilisant un exposant public e que l'on ne connaît pas a priori. Ce procédé permet en particulier de réaliser une contre-mesure, notamment aux attaques par fautes, qui offre la meilleure protection possible même lorsqu'on ne connaît pas l'exposant public e. L'invention a pour objet un procédé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie utilisant des moyens de calcul, principalement caractérisé en ce que qu'il consiste à réaliser les étapes suivantes : a) choisir une valeur e parmi un nombre déterminé de valeurs ei, ei étant des nombres entiers, b) tester si la valeur ei choisie vérifie une relation prédéterminée : - si c'est le cas, alors e=ei, et mémoriser e en vue de son utilisation dans des calculs dudit algorithme de cryptographie, - si ce n'est pas le cas, réitérer les étapes précédentes en choisissant une autre valeur de ei et si aucune valeur de ei ne peut être attribuée à e alors constater que les calculs dudit algorithme de cryptographie utilisant la valeur e ne peuvent être effectués. Selon un mode de réalisation de l'invention, il consiste préalablement à l'étape b), à choisir une valeur Y comprise dans l'intervalle 0, N [ et à attribuer à une valeur X le résultat de l'opération yd modulo N, d et N étant des nombres entiers déterminés et il consiste en ce que la relation prédéterminée de l'étape b) est Xe, modN =Y On choisit de préférence Y=2. L'algorithme de cryptographie peut être basé sur un algorithme de type RSA, notamment en mode standard ou en mode CRT. Selon un autre mode de réalisation, la relation prédéterminée de l'étape b) est : eidp=l (modulo À (p)), p et dp étant des nombres entiers déterminés et À (. ) étant la fonction de Carmichael. Le nombre dp peut être obtenu par dp=d (module À (p)), d étant un entier prédéterminé. Selon une caractéristique de l'invention, dq et q étant des nombres entiers déterminés, avec pgcd (p, q) =l, l'étape b) consiste à réaliser les étapes suivantes : tester si eidp=l (modulo (p)), si c'est le cas, et si ei (p), alors tester si eidq==l (modulo k (q) ) ; si c'est le cas, alors e=ei et mémoriser e en vue de son utilisation dans des calculs dudit algorithme de cryptographie, si l'un des deux tests précédents n'est pas vérifié, réitérer les étapes précédentes en choisissant une autre valeur de ei et si aucune valeur de ei ne peut être attribuée à e alors constater que les calculs dudit algorithme de cryptographie utilisant la valeur e ne peuvent être effectués. Le nombre dq peut être obtenu par dq=d (modulo d étant un entier prédéterminé. L'algorithme de cryptographie est avantageusement basé sur un algorithme de type RSA en mode CRT. On choisit de préférence ei= 216+1 ou ei=3. Selon une caractéristique de l'invention, une valeur ei ayant été attribuée à e, il consiste à obtenir à l'issue d'une opération privée de l'algorithme RSA, une valeur x à partir d'une valeur y et à ce que ledit calcul utilisant la valeur e consiste à vérifier si y = xe modulo N, N étant un nombre entier prédéterminé. L'invention a aussi pour objet un composant électronique de sécurité, comprenant des moyens de calcul, une mémoire de programme et une mémoire de travail et des moyens de communication de données, caractérisé en ce qu'il met en oeuvre le procédé tel que précédemment décrit. L'invention se rapporte en particulier à une carte à puce comprenant un composant électronique tel que décrit ci-dessus. D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description faite à titre d'exemple non limitatif et en regard de la figure 1 annexée qui représente schématiquement les éléments d'une carte à puce apte à mettre en oeuvre l'invention. Les modes de réalisation sont décrits dans le cadre de cartes à puce, mais peuvent bien entendu s'appliquer à tout autre dispositif ou composant électronique de sécurité doté de moyens de calculs cryptographiques. Ainsi que le montre la figure 1, la carte à puce 1 comprend un microprocesseur 2 couplé à une mémoire figée (ROM) 3 et à une mémoire vive (RAM) 4, le tout formant un ensemble permettant, entre autres, l'exécution d'algorithmes cryptographiques. Plus précisément, le microprocesseur 2 comporte les moyens de calcul arithmétiques nécessaires à l'algorithme, ainsi que des circuits de transfert de données avec les mémoires 3 et 4. La mémoire figée 3 contient le programme exécutoire de l'algorithme cryptographique sous forme de code source, alors que la mémoire vive 4 comporte des registres pouvant être mis à jour pour le stockage de résultats des calculs. La carte à puce 1 comporte aussi une interface de communication 5 reliée au microprocesseur 2 pour permettre l'échange de données avec l'environnement extérieur. L'interface de communication 5 peut être du type"à contacts", étant dans ce cas formée d'un ensemble de plots de contacts destinés à se connecter à un contacteur d'un dispositif externe, tel qu'un lecteur de cartes, et/ou du type"sans contact". Dans ce dernier cas, l'interface de communication 5 comporte une antenne et des circuits de communication par voie hertzienne permettant un transfert de données par liaison sans fil. Cette liaison peut aussi permettre un transfert d'énergie d'alimentation des circuits de la carte 1. On va à présent décrire une méthode permettant de valider la valeur d'un exposant public e que l'on ne connaît pas a priori. Elle est basée sur la constatation suivante : dans 90% des cas, la valeur de e est eo=216+1, dans 5% des cas, la valeur de e est el=3 et dans les autres cas, la valeur de e est autre. La méthode consiste alors à choisir eo et à vérifier que e=eo ; si ewes, alors on essaie avec ei. Il se peut que pour une certaine application correspondant aux 5% d'autres cas, e ne soit pas égal à eo ni à ei. Aussi désigne-t-on plus généralement la valeur de e par ei. Et la méthode consiste finalement à choisir une valeur ei parmi les ei envisagés et à vérifier que e=ei. Selon un premier mode de réalisation, valable pour les modes standard ou CRT de l'algorithme RSA : on choisit arbitrairement une valeur Y comprise dans l'intervalles 0, N [, on choisit une valeur ei, on calcule X = yd modulo N par (3) en mode standard ou par (5) en mode CRT si X'mod N = Y alors e = ej et on mémorise e sinon on choisit une autre valeur pour ei. On peut avantageusement choisir Y=2 de manière à accélérer le calcul d'exponentiation yd qui apparaît dans la relation (3) ou (5) : cela revient alors à faire des additions au lieu de multiplications. On décrit à présent un autre mode de réalisation basé sur la relation (4) ; il n'est valable qu'en mode CRT mais est alors plus efficace que le mode de réalisation précédent : on choisit une valeur ei, on teste si eidp=l modulo (p-1), (ou si eidp=l (modulo Â (p)) dans le cas général) si oui et si ei p, (ou si ei > Â (p) dans le cas général) alors e=ei avec une très grande probabilité de l'ordre de 1-2/p. Dans le cas où ep (ou si ei## (p) dans le cas général), l'ambiguïté peut être levée avec une probabilité égale à 1 en testant si eidq=l modulo (q- 1) (ou si eidq=l (modulo B (q) ) dans le cas général). Si c'est le cas, e=ei et on mémorise e. Cependant, dans la majorité des cas (ei=216+1 ou ei=3), ei Si l'un des tests n'est pas vérifié, on choisit une autre valeur pour ei. Si pour l'un ou l'autre mode de réalisation, il n'existe pas parmi les ei, une valeur telle que e=ei, alors on ne peut effectuer les calculs faisant intervenir e. Lorsqu'on connaît e, par l'un ou l'autre de ces modes de réalisation, on peut alors vérifier chaque opération privée (3) ou (5) en s'assurant que y=xe modulo N ou plus généralement effectuer des calculs utilisant la valeur e qui est mémorisée. Comme on l'a vu, ce procédé peut bien sûr être appliqué à une contre-mesure. Il est plus rapide que la contre-mesure décrite dans l'état de la technique et qui consiste à recalculer l'ensemble de l'algorithme, c'est-à-dire à d'effectuer au moins un deuxième calcul d'exponentiation à la puissance d, d étant de la taille de N, et à comparer les valeurs obtenues à l'issue des calculs successifs. Le procédé selon l'invention consiste aussi à effectuer un deuxième calcul d'exponentiation mais à la puissance e ; or e est petit. Il permet en outre de détecter une faute permanente. Il s'applique aussi bien dans le cas du mode standard de l'algorithme RSA que dans le cas du mode CRT ainsi qu'à la généralisation de ces modes. REVENDICATIONS 1. Procédé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie utilisant des moyens de calcul, caractérisé en ce que qu'il consiste à réaliser les étapes suivantes : a) choisir une valeur e parmi un nombre déterminé de valeurs ei, ei étant des nombres entiers, b) tester si la valeur ei choisie vérifie une relation prédéterminée : - si c'est le cas, alors e=ei, et mémoriser e en vue de son utilisation dans des calculs dudit algorithme de cryptographie, - si ce n'est pas le cas, réitérer les étapes précédentes en choisissant une autre valeur de ei et si aucune valeur de ei ne peut être attribuée à e alors constater que les calculs dudit algorithme de cryptographie utilisant la valeur e ne peuvent être effectués. 2. Procédé selon la revendication précédente, caractérisé en ce que préalablement à l'étape b), il consiste à choisir une valeur Y comprise dans l'intervalle 0, N [ et à attribuer à une valeur X le résultat de l'opération yd modulo N, d et N étant des nombres entiers déterminés et en ce que la relation prédéterminée de l'étape b) est X', modN=Y 3. Procédé selon la revendication précédente, caractérisé en ce que Y=2. 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'algorithme de cryptographie est basé sur un algorithme de type RSA. 5. Procédé selon la revendication précédente, caractérisé en ce que l'algorithme de type RSA est en mode standard ou en mode CRT. 6. Procédé selon la revendication 1, caractérisé en ce que la relation prédéterminée de l'étape b) est : eidp=l (modulo À (p)), p et dp étant des nombres entiers déterminés et À. (. ) étant la fonction de Carmichael. 7. Procédé selon la revendication précédente, caractérisé en ce que dp=d (modulo À, (p)), d étant un entier prédéterminé. 8. Procédé selon l'une quelconque des revendications 6 ou 7, caractérisé en ce que, dq et q étant des nombres entiers déterminés, avec pgcd (p, q) =l, l'étape b) consiste à réaliser les étapes suivantes : tester si eidp=l (moduloÂ (p)), si c'est le cas, et si ei si c'est le cas, et si ei > Â. (p), alors tester si eidq=l (modulo ^ (q) ) ; si c'est le cas, alors e=ei et mémoriser e en vue de son utilisation dans des calculs dudit algorithme de cryptographie, si l'un des deux tests précédents n'est pas vérifié, réitérer les étapes précédentes en choisissant une autre valeur de ei et si aucune valeur de ei ne peut être attribuée à e alors constater que les calculs dudit algorithme de cryptographie utilisant la valeur e ne peuvent être effectués. 9. Procédé selon la revendication précédente caractérisé en ce que dq=d (modulo zu (q)), d étant un entier prédéterminé. 10. Procédé selon l'une quelconque des revendications 6 à 9, caractérisé en ce que l'algorithme de cryptographie est basé sur un algorithme de type RSA en mode CRT. 11. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que ei= 216+1. 12. Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que ei=3. 13. Procédé selon l'une quelconque des revendications précédentes et selon lequel une valeur ei a été attribuée à e, caractérisé en ce qu'il consiste à obtenir à l'issue d'une opération privée de l'algorithme RSA, une valeur x à partir d'une valeur y et en ce que ledit calcul utilisant la valeur e consiste à vérifier si y = xe modulo N, N étant un nombre entier prédéterminé. 14. Composant électronique de sécurité, comprenant des moyens de calcul (2), une mémoire de programme (3) et une mémoire de travail (4) et des moyens de communication de données (5), caractérisé en ce qu'il met en oeuvre le procédé selon l'une quelconque des revendications précédentes. 15. Carte à puce comprenant un composant électronique selon la revendication précédente.