Brevet FR2821944A1 — publié le 20020913

PROCÉDÉ DE PROTECTION CONTRE LES ATTAQUES PAR MESURE DE COURANT OU DE RAYONNEMENT ÉLECTROMAGNÉTIQUE L'invention concerne un procédé algorithmique de protection contre les attaques par mesure de courant ou par mesure de rayonnement électromagnétique contre des dispositifs électroniques utilisant des procédés cryptographiques basés sur des courbes elliptiques. Par la suite, on notera K un corps fini. Une courbe elliptique définie sur K est l'ensemble des points A = (x, y) E K2 (x et y sont par définition les coordonnées du point A) solutions de l'équation y2 + alxy + a3y = x + a2X + a4 + a5, où al, a2, a3, a4, as sont des éléments de K. On note E (K) l'ensemble des points qui sont solutions de cette équation. E (K) forme ce qu'on appelle une courbe elliptique. Une propriété fondamentale d'une courbe elliptique est qu'on peut additionnner des points de la courbe entre eux, comme on pourrait le faire avec des nombres. On dit qu'une courbe elliptique forme un groupe abélien. En cryptographie, l'opération de base qui est effectuée sur une courbe elliptique est d'additionner un point A à lui-même un certain nombre de fois. Si k est un entier, on note kA le résultat de l'addition de A k fois à lui-même. On appelle cette opération une multiplication scalaire. Un exemple d'utilisation de cette opération est fourni par le procédé o de chiffrement dit de ElGamal, ou par le procédé de signature numérique dit ECDSA. Dans chacun de ces exemples, k est une donnée secrète du procédé, qui ne doit pas être dévoilée afin d'en garantir la sécurité. Les procédés cryptographiques cités précédemment, lorsqu'ils sont utilisés dans des dispositifs électroniques, peuvent être soumis à des attaques par mesure de courant, ou par mesure de rayonnement électromagnétique. Le principe de ces attaques est de mesurer la puissance électrique consommée par le dispositif (ou la puissance du champ magnétique rayonné), au cours de l'exécution d'un algorithme cryptographique. Un traitement statistique des données obtenues permet ensuite de déterminer la clé secrète utilisée au cours du déroulement de cet algorithme. Pour déjouer ces attaques, un moyen est de rendre l'exécution de l'algorithme cryptographique probabiliste, de manière que l'exécution de l'algorithme change à chaque fois qu'il est utilisé, même si l'entrée fournie à l'algorithme reste identique. Ainsi, il devient impossible de procéder utilement à un traitement statistique des mesures observées. L'invention est donc un procédé permettant de rendre probabiliste l'opération de calcul de kA, lorsque k est une valeur secrète du procédé cryptographique utilisé. L'invention est expliquée en détail dans la section 4.3 de la publication intitulée Protection against Differential Analysis for Elliptic Curve Cryptography , à paraître dans les actes de la conférence Ches'2001 (Cryptographie Hardware and Embedded Systems), qui se tiendra à Paris au mois de mai 2001. Afin d'en expliquer le fonctionnement, nous commençons par rappeler quelques notions concernant les corps finis. Si p est un nombre premier, on note Fp le corps formé des entiers considérés modulo le nombre p. Si K est un corps, on note K [X] l'anneau des polynômes à coefficients dans K. On dit qu'un polynôme dans K est unitaire si le coefficient de son terme de plus haut degré est égal à un. On dit qu'un polynôme dans K [X] est irréductible si les seuls polynômes qui le divisent sont lui-même et les polynômes de degré nul. Si I est un idéal de K [X], on note K J l'anneau défini par le quotient de K [X] par l'idéal I. Si P est un élément de K[X], on note (P) l'idéal de K engendré par P. Un fait important est tout corps K peut être plongé dans un corps qui le contient, en utilisant le fait que K peut être envoyé injectivement dans K [X]/ (P), où P est un élément irréductible de K [X], ce qu'on symbolise par K / (P). Une telle injection est appellée une extension du corps K, et le degré de l'extension est par définition le degré du polynôme P. Si K est un sous-corps de K', on note K Un résultat mathématique indique que si K Ce résultat est exposé dans le livre intitulé Elliptic Curve Public Key Cryptosystems , d'Alfred Menezes, publié par Kluwer en 1993. Formellement, on peut écrire que (E (K C E (kr), où (x, y) est un point d'une courbe elliptique E (K). Des exemples non limitatifs d'une telle situation sont le schéma de chiffrement ElGamal sur courbe elliptique, ou le schéma de signature ECDSA. L'invention consiste, pour réaliser cette multiplication scalaire, à se placer dans E (K') et à calculer 1 C = k (# (A) + B), où B est un élément aléatoire de Z. Ensuite, selon l'invention, on produit le résultat attendu en calculant 7r (C) = kA, cette égalité provenant de la définition de l'ensemble Z. L'invention est donc caractérisée en ce que l'algorithme produisant kA à partir de k et de A est rendu aléatoire par un choix aléatoire d'un point B dans l'ensemble Z. Ainsi, l'exécution de l'algorithme est bien différente à chaque fois qu'il est employé, même si les entrées fournies à 1 l'algorithme restent identiques. Avec les notations définies précédemment, le procédé de l'invention est résumé par l'identité kA=#(k(#(A)+B)). Formulé différemment, le procédé de l'invention consiste à transformer une courbe E (K) en une courbe E (K'), où K'est un surcorps de K, et à masquer le point à multiplier par un point B de l'ensemble Z, ce qui modifie le déroulement de la multiplication scalaire, mais qui n'affecte pas la valeur du résultat final. Un exemple de réalisation de l'invention consiste à déterminer rapidement des éléments de Z de la façon suivante. Le point A es supposé est d'ordre q : qA = 0E (K). On appelle groupe de travail le groupe engendré par le point A. Si D est un point de E (K) dans le groupe de travail, on peut calculer bzw (D) dans E (K'). Il est facile de constater que B E Z, du fait que le sous-groupe de travail considéré de E (K) est précisément d'ordre q. Un autre exemple de réalisation de l'invention est maintenant décrit, qui utilise les deux pro- cédés exposés précédemments. Nous nous plaçons dans le cas où un dispositif électronique, par exemple une carte à puce, cet exemple n'étant pas limitatif, doit exécuter un algorithme cryptographique qui implique une étape de multiplication scalaire sur une courbe elliptique définie sur un corps fini K de caractéristique p. L'algorithme est exécuté plusieurs fois de suite. Le dispositif électronique a stocké dans sa mémoire certaines informations. La mémoire utilisée est supposée réinscriptible plusieurs fois, et telle que même si le dispositif est réinitialisé, ou privé d'alimentation électrique, les données contenues dans cette mémoire sont conservées inchangées. Un exemple de réalisation d'un tel type de mémoire est la mémoire dite EEPROM. Le dispositif est supposé avoir stocké un point B de Z, ce point pouvant avoir été précalculé au départ. L'algorithme reçoit un point A de E (K), un entier k, et doit produire le point kA. Selon l'invention, et selon la réalisation, l'algorithme commence par calculer C = Ensuite, le dispositif effectue l'addition de Puis, selon la réalisation, le dispositif calcule le point kC, en effectuant une multiplication scalaire. Enfin, l'algorithme calcule, et produit le résultat 7r (C) = kA. Le morphisme 7r est également supposé avoir fait l'objet de précalculs et avoir été stocké en mémoire permanente pour permettre le calcul d'un point 7r (C). Selon la réalisation, la dernière étape de l'algorithme consiste à remplacer en mémoire permanente réinscriptible le point B par le point 2B, qui est toujours un élément du groupe Z. Ainsi, l'algorithme peut être utilisé à nouveau, et dans les mêmes conditions initiales. On voit qu'à chaque exécution de l'algorithme, le point B change de valeur, ce qui produit à chaque exécution un déroulement différent de l'algorithme, d'où découle la protection contre les attaques par mesure de courant ou par mesure de rayonnement. Selon un sous-procédé de l'invention, le rafraîchissement appliqué au point B en le remplaçant par 2B à chaque exécution peut être généralisé, en appliquant au point B tout morphisme Il de groupe du groupe Z, et en remplaçant B par Il (B) à chaque exécution, où Il est un morphisme de groupe du groupe Z choisi aléatoirement à chaque exécution. L'avantage d'un tel procédé est de permettre de modifier la valeur de B à chaque exécution de l'algorithme, avec très peu de calculs requis, ce qui constitue un avantage important dans le cas où le dispositif électronique concerné dispose de peu de capacité de calcul, ou d'un faible volume de mémoire. REVENDICATIONS 1. Procédé de protection contre les attaques par mesure de courant ou de rayonnement élec- tromagnétique d'un algorithme de multiplication scalaire défini sur une courbe elliptique, recevant un point A de la courbe elliptique E (K) munie d'un élément neutre OE (K) et définie sur le corps fini K, un entier k, un corps K'qui est un surcorps de K, un morphisme de groupe X, de E (K) dans E (K'), un morphisme 7r de E (K') dans E (K) tel que 7r o $ soit égal à l'identité, caractérisé en ce qu'il comprend les étapes suivantes : (a) Calcul d'un point B de la courbe E (K') égal à &commat; (A). (b) Addition à B d'un point aléatoire choisi dans un ensemble Z, cet ensemble vérifiant la propriété que Z = a E (K)), ce qui produit un point C de E (K'). propriété que Z = Ir 9E (K 5 (c) Calcul d'un point D de E (K) égal à 7r (C). 2. Procédé de protection selon la revendication 1 caractérisé en ce qu'il comprend une étape dite de rafraîchissement, consistant à appliquer après chaque exécution de l'algorithme de multiplication scalaire une opération qui modifie la valeur d'un point préstocké dans le dis- positif électronique concerné, en appliquant à ce point un morphisme de groupe fin du groupe Z choisi aléatoirement.