Brevet FR2880148A1 — publié le 20060630

PROCEDE D'EXPONENTIATION SECURISEE ET COMPACTE POUR LA CRYPTOGRAPHIE La présente invention concerne un procédé d'exponentiation sécurisée et compacte, avec application notamment dans le domaine de la cryptologie où l'on met en oeuvre des algorithmes cryptographiques dans des dispositifs électroniques tels que des cartes à puce. De nombreux algorithmes cryptographiques sont basés sur des calculs d'exponentiation, dans un groupe algébrique, du type xd où x et d sont respectivement un élément et un exposant prédéterminés. Ceci est notamment le cas avec l'algorithme RSA (Rivest, Shamir et Adleman), lequel repose sur l'exponentiation dans le groupe multiplicatif de l'anneau des entiers modulo N, où N est le produit de deux grands nombres premiers. Le résultat de l'exponentiation peut correspondre par exemple à un texte chiffré ou déchiffré, une donnée signée ou vérifiée. D'autres algorithmes cryptographiques tels que l'algorithme d'ElGamal ou de Diffie- Hellman reposent sur l'exponentiation dans le groupe multiplicatif d'un corps ou dans le groupe des points d'une courbe elliptique. Un dispositif électronique prévu pour exécuter un tel algorithme doit contenir en mémoire d'une part la partie exécutoire pour élever x à la puissance de d, et d'autre part les valeurs de x et d. Il existe différents types d'algorithmes d'exponentiation. On connaît notamment la méthode binaire 30 de type élévation au carré et multiplication , plus habituellement connue sous la terminologie anglosaxonne Square and Multiply . Cet algorithme prend en entrée un élément x et un exposant d dont la représentation binaire est: {d[t-1], d[t-2],..., d[1], d[O]} avec d[i] égal à 0 ou à 1, et retourne l'élément y = x^d, c'est-à-dire x.x x (d fois). L'algorithme Square and Multiply peut être 10 schématisé ainsi: 1) Initialiser le:registre RO à 1 et le registre R1 à x 2) Pour i allant de t-1 à 0, effectuer a) RO = R0^2 [mise au carré] ; b) si d[i] = 1, alors effectuer RO = RO * Rl [multiplication] ; 3) Retourner RO. D'autres algorithmes connus pour l'exponentiation existent tels que la méthode de Yacobi, dite M, M3, la méthode des fenêtres glissantes, etc. Mais ces algorithmes sont plus complexes à mettre en oeuvre et par conséquent moins adaptéE aux composants électroniques contraints du type carte à puce. Dans la suite de la description, le composant électronique comporte une unité centrale principale et une mémoire de travail avec au moins trois registres (RO, R1, R2) L'algorithme Square and Multiply (et les algorithmes cités ci-dessus) doivent inclure des contre-mesures adaptées, c'est-à-dire sécurisées, contre des attaques visant à découvr:_r des informations contenues et manipulées dans des traitements effectués par le dispositif de calcul. Notamment, des contre-mesures sont prévues contre les attaques dites à canaux cachés, simples ou différentielles. On entend par attaque à canal caché simple ou différentielle, une attaque basée sur une grandeur physique mesurable de l'extérieur du dispositif, et dont l'analyse directe (attaque simple) ou l'analyse selon une méthode statistique (attaque différentielle) permet de découvrir des informations contenues et manipulées dans des trai- :ements dans le dispositif. Ces attaques peuvent ainsi permettre de découvrir des informations confidentielles. Ces attaques ont notamment été dévoilées par Paul Kocher (Advances in Cryptology - CRYPTO'99, vol. 1966 de Lecture Notes in Computer Science, pp.388-397. Springer-Verlag, 1999). Parmi les grandeurs physiques qui peuvent être exploitées à ces fins, on peut citer la consommation en courant, le champ électromagnétique... Ces attaques sont basées sur le fait que la manipulation d'un bit, c'est à dire son traitement par une instruction particulière a une empreinte particulière sur la grandeur physique considérée selon sa valeur. Les algorithmes d'exponentiation précités ont dû inclure des contre-mesures pour empêcher ces attaques de prospérer. Par exemple, l'algorithme Square and Multiply Always , selon la terminologie anglosaxonne, et qui signifie élever au carré et multiplier toujours , est une variante sécurisée de l'algorithme Square and Multiply dans lequel l'opération était conditionnelle à la valeur du bit en cours de traitement, donc permettant des attaques à canaux cachés. Cet algorithme prend en entrée un élément x et un exposant d dont la représentation binaire est: {d[t-1], d[t-2],..., d[1], d[O]} avec d[i] égal à 0 ou à 1, et retourne l'élément y = x^d, c'est à dire x.x x (d fois). L'algorithme Square and Multiply Always peut être schématisé ainsi: 1) Initialiser les registres RO et R1 à 1 et le registre R2 à x; 2) Pour i allant da t-1 à 0, effectuer a) RO = ROA2 [mise au carré] ; b) b = 1 d[i] ; Rb = Rb * R2 [multiplication] ; 3) Retourner RO. L'algorithme du Square and Multiply Always résiste contre certaines attaques simples (dites de type SPA pour Simple Power Analysis selon la terminologie anglo-saxonne) mais demande un registre supplémentaire. Il est important de remarquer que le registre R1 est inutile au calcul lui-même; il est utilisé pour effectuer une multiplication factice lorsque à l'itération i le bit d[i] de l'exposant d est égal à 0 (et par conséquent b=1) de sorte que quelle que soit la valeur du bit de l'exposant d, une itération i consiste en une étape de mise au carré suivie d'une multiplication. Malheureusement, bien que résistant aux attaques de type SPA, l'introduction d'opérations factices engendre un autre type de faiblesse. Une classe d'attaques (appelées selon la terminologie anglo-saxonne safe- error attacks ) a été introduite par Sung-Ming Yen et 35 Marc Joye ( Checking before output may not be enough against fault-based cryptanalysis , IEEE Transactions on Computers, vol. 49, pages 967-970, 2000). Appliquée à l'algorithme du Square and Multiply Always , l'idée consiste à induire une faute durant l'opération de multiplication (Etape 2b) à l'itération i. Si le résultat de l'exponentiation y = x^d est correct, cela signifie que cette opération de multiplication était factice et par conséquent que le bit correspondant de d est égal à 0 (i.e. , d[i] = 0). Au ccntraire, si le résultat de l'exponentiation est incorrect, cela signifie que le bit correspondant de d est égal à 1 (i. e. , d[i] = 1). Un attaquant peut ainsi retrouver bit à bit la valeur de l'exposant d. Dans l'invention, on s'intéresse à un procédé d'exponentiation possédant les mêmes avantages que l'algorithme du Square and Multiply Always , à savoir la résistance contre les attaques de type SPA, mais, contrairement a celui-ci, en n'effectuant aucune opération factice. En outre, de façon remarquable, le procédé selon l'invention possède la particularité de n'effectuer que des opérations de multiplications. Cela est particulièrement intéressant dans les environnements plus contraints du type carte à puce car seule cette dernière opération doit être implémentée, soit de façon logicielle, soit de façon matérielle. Ainsi, il en résulte: - soit un gain en taille de mémoire code (de type ROM ou EEPRON par exemple) pour une implémentation logicielle, -soit un gain de taille de circuit pour une implémentation matérielle, parce que l'opération de mise au carré n'est pas nécessaire. On rappellera çue sur un ensemble noté additivement, tel le groupe des points d'une courbe elliptique, l'exponentiation s'écrit Q = d.P, où P et Q sont des éléments de l'ensemble noté additivement (courbe elliptique) et d est un exposant. Ceci est également le cas lorsqu'on travaille dans le groupe additif d'un anneau ou d'un corps. Dans la suite, on se place dans le cas général, conventionnel, ce qui veut dire que l'on utilisera la notation multiplicative, sauf mention explicite contraire. De façon plus détaillée, le procédé d'exponentiation selon l'invention repose sur l'algorithme suivant. Cet algorithme prend en entrée un élément x et un exposant d dont la représentation binaire est: {d[t-1], d[t-2], ..., d[1], d[0]l avec d[i] égal à 0 ou à 1, et retourne l'élément y = x^d, c'est à dire x.x x (d fois). En notation multiplicative, le procédé selon l'invention peut être schématisé de la façon suivante: 1) Initialiser le registre RO à 1 et les registres R1 et R2 à x; 2) Pour i allant de 0 à t-1, effectuer a) b = 1 d[i] ; b) Rb = Rb * R2 [lère multiplication] ; c) R2 = RO * R1 [2nde multiplication] ; 3) Retourner RO. L'algorithme précédent peut évidemment s'écrire de façon additive. Comme précédemment, il prend en entrée un élément P et un exposant d dont la représentation binaire est {d[t-1], d[t-2],..., d[1], d[O]} avec d[i] égal à 0 ou à 1, et retourne l'élément Q = d.P, c'est à dire P + P... + P (d fois). Dans ce cas, en notation additive, le procédé selon l'invention peut être schématisé de la façon suivante: 1) Initialiser le registre RO à 0 et les registres R1 et R2 à P; 2) Pour i allant d 0 à t-1, effectuer a) b = 1 d[i]; b) Rb = Rb + R2 [lere addition] ; c) R2 = RO + Rl [2nde addition] ; 3) Retourner RO. Dans certains groupes algébriques, l'addition avec l'élément neutre 0 (respectivement la multiplication avec l'élément neutre 1 en notation multiplicative) peut se comporter différemment par rapport aux mesures à canaux cachés et par conséquent engendrer une faiblesse. Dans ce cas, le procédé selon l'invention peut être facilement adapté. Nous illustrons la technique pour un groupe noté de façon additive, comme par exemple l'ensemble des points d'une courbe elliptique. L'algorithme commence à l'itération i=1 de sorte qu'aucun des registres n'est initialisé avec la valeur 0 (appelé point à l'infini pour une courbe elliptique) de la façon suivante. En conservant la notation additive, il existe une variante selon l'inventicn qui peut être schématisée de la façon suivante: 1) Initialiser le registre RO et Rl à P et le registre R2 à 2.P; 2) Pour i allant de 1 à t-1, effectuer a) b = 1 - d[i] ; b) Rb = Rb + R2 [lé- addition] ; c) R2 = RO + Rl [2nae addition] ; 3) Si d[0] = 0 alors effectuer RO = RO - P 4) Retourner RO. On notera que l'initialisation de cette variante (étape 1 ci- dessus) demande que le registre R2 contient la valeur de 2.P. Cette valeur peut être soit pré-calculée, soit calculée au moment de l'exponentiation Q=d.P. Dans ce dernier cas, si aucune routine de doublement n'est disponible, l'évaluation de 2.P peut se faire à partir d'addition uniquement en effectuant ((P+T) + (P-T)) où T est un élément connu, distinct de P, du groupe sous-jacent, typiquement un élément de la clé publique. Le procédé d'exponentiation de l'invention et ses variantes présentent l'avantage d'être résistants aux attaques à canaux cachés de type SPA et aux attaques Safe-Error , contrairement aux algorithmes d'exponentiation habituels qui doivent intégrer des contre-mesures pour résister à ces attaques De plus, et de manière remarquable, le procédé d'exponentiation de l'invention et ses variantes présentent l'avantage supplémentaire de ne réaliser que des opérations de multiplication (ou d'addition en notation additive). On comprendra que l'invention se prête à de nombreuses variantes de mise en oeuvre. La description a été donnée dans le cadre d'un environnement de type carte à puce. I1 est cependant clair que les enseignements se transposent à d'autres applications, telles que dans les terminaux informatiques, de communication sur réseau ou autres, et à tout autre dispositif éLectronique qui fait appel à des calculs cryptographiques. REVENDICATIONS 1. Procédé destiné à réaliser des calculs d'exponentiation dans un groupe algébrique noté de façon multiplicative, du type x puissance d (xd), où x est un élément dudit groupe et d un exposant prédéterminé dont la représentation binaire est {d[t-1], d[t-2], ..., d[1], d[O]} avec d[i] égal à 0 ou à 1, destiné à un composant électronique comportant une unité centrale principale et une mémoire de travail avec au moins trois registres (RO, RI, R2), procédé caractérisé en ce qu'il retourne l'élément y tel que y = x^d, c'est-à-dire x.x x (d fois), et en ce qu'il comprend les étapes suivantes: 1) Initialiser le registre RO à 1 et les registres R1 et R2 à x; 2) Pour i allant de 0 à t-1, effectuer: a) b = 1 - d[i]; b) Rb = Rb * R2 [lère multiplication] ; c) R2 = RO * R1 [2nde multiplication] ; 3) Retourner RO. 2. Procédé d'exponentiation dans un groupe algébrique noté de façon additive, du type d fois P (d.P), où P est un élément dudit groupe et d un exposant prédéterminé dont la représentation binaire est {d[t-1], d[t-2], ..., d[1], d[O]} avec d[i] égal à 0 ou à 1, destiné à un composant électronique comportant une unité centrale principale et une mémoire de travail comportant au moins trois registres (RO, R1, R2), procédé caractérisé en ce qu'il retourne l'élément Q tel que Q = d.P, c'est-à-dire P + P... + P (d fois), et en ce qu'il comprend les étapes suivantes: . 1) Initialiser le registre RO à 0 et les registres R1 et R2 à P; 2) Pour i allant de 0 à t-1, effectuer a) b = 1 - d[i] ; b) Rb = Rb + R2 [lère addition] c) R2 = RO + R1 [2nde addition] 3) Retourner RO. 3. Procédé d'exponentiation selon la revendication 2, caractérisé en ce qu'il comporte les étapes suivantes: 1) Initialiser le registre RO à p et les registres R1 et R2 à 2.P; 2) Pour i allant de 1 à t-1, effectuer a) b = 1 - d[i] ; b) Rb = Rb + R2 [lère addition] ; c) R2 = RO + R1 [2nde addition] 3) Si d[O] = 0 alo::s effectuer RO = RO - P 4) Retourner RO. 4. Procédé d'exponentiat:on selon la revendication 3, caractérisé en ce que l'évaluation du double de l'élément P (2.P) dans le dit groupe se fait à partir d'additions uniquement ((P+T) + (P-T)) en additionnant un premier élément (P+T) formé de la somme dudit élément P et d'un autre élément connu T, distinct de P, dudit groupe et un second élément (P-T) formé de la différence dudit élément P et dudit élément T. 5. Procédé d'exponentiation selon la revendication 1, caractérisé en ce que ledit groupe algébrique est le groupe multiplicatif d'un anneau ou d'un corps. 6. Procédé d'exponentiation selon l'une quelconque des revendications 2 à 4, caractérisé en ce que ledit groupe algébrique est le groupe additif d'un anneau ou d'un corps. 7. Procédé d'exponentatisn selon l'une quelconque des revendications 2 à 4, caractérisé en ce que ledit groupe algébrique est le groupe des points d'une courbe elliptique. 8. Procédé d'exponentiation selon la revendication 4, appliqué à la cryptographie à clé publique et caractérisé en ce que l'élément connu (T) est un élément de la clé publique. 9. Procédé d'exponentiat__on selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il est mis en oeuvre dans un composant électronique. 10. Procédé d'exponentiation selon la revendication 9, caractérisé en ce que ledit composant électronique est une carte à puce.