Brevet FR3094522A1 — publié le 20201002

Description Titre de l'invention : Protection d'un calcul itératif Domaine technique [0001] La présente description concerne de façon générale les circuits électroniques et, plus particulièrement, les circuits exécutant dès opérations itératives. La présente description concerne plus particulièrement la protection de calculs d'exponentiations modulaires ou de calculs sur courbes elliptiques contre des attaques visant à découvrir des quantités manipulées par ces calculs. Technique antérieure [0002] Dans dc nombreuses applications, des circuits électroniques mettent en oeuvre des al- gorithmes dc chiffrement, d'authentification, de calcul de signature, et, plus généralement, des algorithmes manipulant des données, dites secrètes, c'est-à-dire dont on souhaite réserver l'accès à certains utilisateurs ou circuits. Parmi ces algorithmes, certains utilisent des opérations itératives. H peut s'agir d'exponentiations modulaires, par exemple des algorithmes de type RSA, ou de produits sur courbes elliptiques, par exemple des algorithmes de type ECDH. [0003] De nombreuses méthodes, dites attaques, existent pour tenter de découvrir ou pirater des données secrètes manipulées par ces calculs. Parmi ces attaques, des attaques, dites par canaux cachés, exploitent des informations indirectes telles que la consommation du circuit (attaques SPA, DPA), son rayonnement électromagnétique, etc. L'interprétation dc ces informations renseigne le pirate sur la ou les données secrètes. [0004] Dans les attaques par canaux cachés, on distingue notamment les attaques dites verticales, et les attaques dites horizontales. [0005] Les attaques horizontales, que vise particulièrement la présente description, consistent à comparer des segments issus d'une même trace (par exemple, de consommation ou dc rayonnement) entre eux, afin d'extraire l'information secrète. Elles n'utilisent qu'une seule trace d'exécution. Résumé de l'invention 100061 11 existe un besoin d'améliorer la protection des données, manipulées par des al- gorithmes dont chaque exécution met en oeuvre des étapes itératives, contre des attaques par canaux cachés, en particulier contre des attaques horizontales. 100071 Un mode de réalisation pallie tout ou partie des inconvénients des procédés et circuits usuels de protection de données, manipulées par des algorithmes, contre des attaques horizontales. 100081 Un mode de réalisation prévoit un procédé de protection d'un calcul sur un premier nombre et un deuxième nombre, exécuté par un circuit électronique, dans lequel : 2 le deuxième nombre est décomposé en une somme d'au moins deux troisièmes nombres ; et le calcul est effectué bit par bit pour chaque rang des troisièmes nombres. [0009] Selon un mode de réalisation, le calcul représente une exponentiation modulaire du premier nombre par le deuxième nombre. [0010] Selon un mode de réalisation, le calcul représente une multiplication d'un point d'une courbe elliptique par un scalaire. [0011] Selon un mode de réalisation, les rangs des bits des troisièmes nombres sont balayés par ordre croissant. [0012] Selon un mode de réalisation, les bits de même rang des troisièmes nombres sont traités dans un même ordre, d'un rang à l'autre. [0013] Selon un mode de réalisation, les bits de même rang des troisièmes nombres sont traités dans un ordre aléatoire. [0014] Selon un mode de réalisation, l'ordre de traitement des bits de même rang des troisièmes nombres résulte d'une permutation. [0015] Selon un mode de réalisation, le traitement effectué sur les bits de chaque rang consiste : si le bit considéré est égal à 1, à effectuer une première opération avec un opérateur sur les contenus d'un premier registre et d'un deuxième registre, puis à placer le résultat dans le premier registre ; et si le bit considéré est égal à 0, à conserver inchangés les contenus des deux registres. [0016] Selon un mode de réalisation, le premier registre contient le résultat du calcul. [0017] Selon un mode de réalisation, ledit opérateur est la multiplication. [0018] Selon un mode de réalisation, ledit opérateur est l'addition. [0019] Selon un mode de réalisation, le premier registre est initialisé avec l'élément neutre dudit opérateur. [0020] Selon un mode de réalisation, le deuxième registre est initialisé avec le premier nombre. [0021] Selon un mode de réalisation, après avoir traité tous les bits d'un même rang des troisièmes nombres, une deuxième opération est effectuée avec ledit opérateur sur le contenu du deuxième registre, le résultat de cette deuxième opération étant placé dans le deuxième registre. [0022] Selon un mode de réalisation, la ou les opérations sont effectuées modulo un quatrième nombre. [0023] Un mode de réalisation prévoit un circuit électronique configuré pour la mise en oeuvre du procédé décrit. Brève description des dessins 3 100241 Ces caractéristiques et avantages, ainsi que d'autres, seront exposés en détail dans la description suivante de modes de réalisation et modes de mise en oeuvre particuliers faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : [0025] [fig.1] la figure 1 représente, de façon schématique, un mode de réalisation d'un circuit électronique ; [0026] [fig.2] la figure 2 représente, sous forme de blocs, des étapes d'un calcul usuel d'exponentiation modulaire ; [0027] [fig.3] la figure 3 représente, sous forme de blocs, un mode de mise en oeuvre d'un procédé de protection d'un calcul d'exponentiation modulaire ; [0028] [fig.4] la figure 4 représente, sous forme de blocs, des étapes d'un calcul usuel sur courbe elliptique ; et [0029] [fig.5] la figure 5 représente, sous forme de blocs, un mode de mise en oeuvre d'un procédé de protection d'un calcul sur courbe elliptique. Description des modes de réalisation [0030] De mêmes éléments ont été désignés par de mêmes références dans les différentes figures. En particulier, les éléments structurels et/ou fonctionnels communs aux différents modes de réalisation et modes de mise en oeuvre peuvent présenter les mêmes références et peuvent disposer de propriétés structurelles, dimensionnelles et matérielles identiques. [0031] Par souci de clarté, seuls les étapes et éléments utiles à la compréhension des modes de réalisation et modes de mise en oeuvre décrits ont été représentés et sont détaillés. En particulier, les applications des calculs exécutés ou celles des circuits les exécutant n'ont pas été détaillées, les modes de réalisation et modes de mise en oeuvre décrits étant compatibles avec les applications usuelles. [0032] Sauf précision contraire, lorsque l'on fait référence à deux éléments connectés entre eux, cela signifie directement connectés sans éléments intermédiaires autres que des conducteurs, et lorsque l'on fait référence à deux éléments reliés ou couplés entre eux, cela signifie que ces deux éléments peuvent être connectés ou être reliés ou couplés par l'intermédiaire d'un ou plusieurs autres éléments. [0033] Dans la description qui suit, lorsque l'on fait référence à des qualificatifs de position absolue, tels que les termes "avant", "arrière", "haut", "bas", "gauche", "droite", etc., ou relative, tels que les termes "dessus", "dessous", "supérieur", "inférieur", etc., ou à des qualificatifs d'orientation, tels que les termes "horizontal", "vertical", etc., il est fait référence sauf précision contraire à l'orientation des figures. [0034] Sauf précision contraire, les expressions "environ", "approximativement", "sen- siblement", et "de l'ordre de" signifient à 10 % près, de préférence à 5 % près. [0035] La figure 1 représente, de façon schématique, un mode de réalisation d'un circuit électronique. [0036] Selon ce mode de réalisation, le circuit 1 comporte : une entité de calcul 11 (UC), par exemple une machine d'états, un microprocesseur, un circuit logique programmable, etc. ; une ou plusieurs zones 13 (MEM) de stockage volatil et/ou non volatil pour stocker tout ou partie de données et clés ; un ou plusieurs bus 15 de données, d'adresses et/ou de commandes entre les différents éléments internes au circuit 1 ; et une interface d'entrée-sortie 17 (110) de communication avec l'extérieur du circuit 1. [0037] Le circuit 1 peut inclure divers autres circuits en fonction de l'application, symbolisés en figure 1 par un bloc 19 (FCT). [0038] Des opérations de calcul itératif, par exemple d'cxponcntiation modulaire, se re- trouvent dans de nombreux algorithmes de chiffrement parmi lesquels, par exemple, le système connu sous la dénomination de RSA. [0039] Une exponentiation modulaire consiste à calculer un résultat C d'une exponentiation d'un nombre ou message M par un exposant e (entier) modulo N, c'est-à-dire appliquer une formule du type : [Math.1] C = Mt' (in od N) [0040] Lc plus souvent : le nombre M représente un nombre (ou une information représentative du nombre) que l'on souhaite chiffrer, authentifier, signer, etc. ; et l'exposant e et le modulo N (le couple (e, N)) représentent une clé (ou des informations représentatives de la clé) de chiffrement, d'authentification, de signature, etc. [0041] Le calcul de l'exponentiation modulaire par un circuit électronique (une machine d'états, un processeur exécutant le procédé sous forme de programme, un circuit logique programmable, etc.), par exemple le circuit 1, s'effectue généralement en appliquant des méthodes basées sur l'utilisation de plusieurs variables ou registres et en effectuant des calculs itératifs sur des bits de l'exposant. [0042] On fait référence à une exponentiation modulaire notée arbitrairement C = (mod N), la transposition aux variables utilisées selon l'opération réalisée en pratique étant à la portée de l'homme du métier. [0043] Des opérations de calcul itératif se trouvent également dans des opérations telles que des multiplications scalaires sur courbes elliptiques qui constituent une autre catégorie d'algorithmes de chiffrement. [0044] Une multiplication scalaire consiste à calculer un résultat C d'une multiplication d'un point P d'une courbe elliptique par un entier d (scalaire), c'est-à-dire appliquer une formule du type : [Math.2] C = .P [0045] Le plus souvent : le point P représente le nombre (ou une information représentative du nombre) que l'on souhaite chiffrer, authentifier, signer, etc. ; et le scalaire d représente la clé (ou des informations représentatives de la clé) de chiffrement, d'authentification, de signature, etc. [0046] Comme pour une exponentiation modulaire, la multiplication scalaire sur courhe el- liptique par un circuit électronique (une machine d'états, un processeur exécutant le procédé sous forme de programme, un circuit logique programmable, etc.), par exemple le circuit 1, s'effectue généralement en appliquant des méthodes basées sur l'utilisation de plusieurs variables ou registres et en effectuant des calculs itératifs sur les bits du scalaire. [0047] On fait référence à une multiplication scalaire sur courhe elliptique notée arbi- trairement C = d.P, la transposition aux variables utilisées selon l'opération réalisée en pratique étant à la portée de l'homme du métier. [0048] Divers modes de réalisation sont décrits ci-dessous en prenant tour à tour pour exemple une application à une exponentiation modulaire et une application à un calcul sur courbe elliptique. Dans les exemples décrits ci-dessous, le calcul utilise au moins deux registres du circuit 1, ou deux emplacements mémoire, notés arbitrairement RO et R1, sur lesquels vont être effectuées les opérations. [0049] Pour simplifier, on confondra les registres et leurs contenus, c'est-à-dire qu'en faisant référence à des opérations effectuées sur les registres, on entend sur leurs contenus. [0050] La figure 2 représente, sous forme de blocs, des étapes d'un calcul usuel d'exponentiation modulaire. [0051] Dans une première étape (bloc 20, RO = 1 ; R1 = M), le registre RO est initialisé à 1 et le registre R1 est chargé avec le nombre M. L'exposant e est chargé dans un autre registre (non représenté), ou réside dans la mémoire. Dans l'exemple représenté en figure 2, on considère que l'exposant e comporte n bits ei. [0052] On entame alors un calcul en boucle sur les bits ei de l'exposant e. Par exemple, un compteur i est initialisé à 0, représentant le bit de poids faible (bloc 230, i = 0) et est incrémenté de 1 (bloc 235, i= i + 1) à chaque traitement d'un bit ei de l'exposant tant que tous les bits ei n'ont pas été traités (bloc 239, i = n-1 ?). [0053] À chaque itération, c'est-à-dire pour chaque bit ei (successivement du bit le moins si- gnificatif ou de poids faible vers le bit le plus significatif ou de poids fort), on commence par tester la valeur du bit ei de l'exposant e (bloc 25, ei = 1 ?). [0054] Si le bit courant ei vaut 1, (sortie YES du bloc 25), le contenu du registre RO est 6 multiplié, modulo N, par le contenu du registre R1 et le résultat est placé dans le registre RO (bloc 251, RO = R0.R1 (mod N)). [0055] Puis, ou si le bit courant ei vaut 0 (sortie NO du bloc 25), le contenu du registre R1 est élevé au carré, modulo N, et le résultat est placé dans le registre R1 (bloc 26, R1 = Rl.R1 (mod N)). En d'autres termes, le contenu du registre R1 est multiplié par lui-même et le résultat est placé dans le registre Rl. [0056] Tant que tous les bits ci de l'exposant e n'ont pas été traités (sortie NO du bloc 239), on incrémente le compteur i (bloc 235, i = i + 1) et on revient à l'étape 25 (ei = 1 ?). Une fois que tous les bits ci de l'exposant c ont été traités (sortie YES du bloc 239), le registre RO contient le résultat de l'exponentiation modulaire (bloc 29, RETURN RO (= (mod N))), c'est-à-dire la valeur C = Me (mod N). [0057] Le calcul illustré en figure 2 peut s'écrire également de la façon suivante : RO = 1 (étape 20) R1 = M (étape 20) Pour i = 0 à n-1 (étapes 230, 235, 239) : Sie = 1 (étape 25) alors RO = RO.R1 (mod N) (étape 251) R1 = R1.R1 (mod N) (étape 26) Fin de boucle (sortie YES du bloc 239) Retourner RO (étape 29). [0058] Un circuit mettant en oeuvre le calcul illustré en figure 2 est réputé vulnérable à des attaques horizontales. En d'autres termes, une seule trace d'exécution de ce calcul par un circuit électronique, par exemple le circuit 1, peut être exploitée par un attaquant ou pirate afin de remonter à l'information secrète M manipulée par le circuit. Des méthodes mathématiques (par exemple, des méthodes utilisant l'indicatrice d'Euler) permettent en effet, partant de la trace d'exécution, d'extraire la valeur de l'exposant e utilisé pour déchiffrer, signer, etc. le message M. [0059] Une fois la valeur de l'exposant e connue, l'attaquant peut déchiffrer tous les messages M chiffrés, avec une clé publique correspondante, ou signer n'importe quel message M et ainsi être authentifié comme étant un autre expéditeur. La trace d'exécution peut prendre la forme, par exemple, d'un enregistrement de variation de puissance consommée ou de rayonnement électromagnétique émis, par le circuit électronique, lors de l'exécution du calcul. [0060] La figure 3 représente, sous forme de blocs, un mode de mise en oeuvre d'un procédé de protection d'un calcul d'exponentiation modulaire. [0061] Dans une première étape (bloc 30, RO = 1 ; R1 = M), le registre RO est initialisé à 1 et le registre R1 est chargé avec le nombre M. L'exposant e est chargé dans un autre registre (non représenté), ou réside dans la mémoire. Dans l'exemple représenté en 7 figure 3, l'exposant e comporte n bits et (i désignant le rang du bit ci, avec 0 2) dont le résultat est égal à l'exposant c. L'exposant c peut donc s'écrire sous la forme : [Math.3] e = X1 + X2 + + X q = Xk k = 1 [0063] Selon un mode de mise en oeuvre préféré, chaque Écime Xk de la somme (c'est-à-dire chaque nombre XI à Xq) possède un même nombre de bits, m. [0064] En variante, au moins un terme Xk de la somme possède un nombre de bits strictement inférieur au nombre m de bits des autres Xk. Ledit terme Xk de la somme est alors, le cas échéant, complété, côté bits de poids fort, par des « 0 ». On se ramène ainsi au mode de mise en oeuvre préféré pour lequel tous les termes Xk de la somme possèdent le même nombre m de bits. 100651 Dans l'exemple de la figure 3, on considère que chaque entier Xk (1 2) dont le résultat est égal au scalaire d. Le scalaire d peut donc s'écrire sous la forme : 11 [Math.5] d = + X2 + + Xq =Xk k = [0092] Selon un mode de mise en oeuvre préféré, chaque terme Xk de la somme (c'est-à-dire chaque nombre X1 à Xq) possède un même nombre de bits, m. [0093] En variante, au moins un terme Xk de la somme possède un nombre de bits strictement inférieur au nombre m de bits des autres Xk. Ledit. (cime Xk de la somme est alors, le cas échéant, complété, côté bits de poids fort, par des « 0 ». On se ramène ainsi au mode de mise en oeuvre préféré pour lequel tous les termes Xk de la somme possèdent le même nombre m. de bits. [0094] Dans l'exemple de la figure 5, on considère que chaque entier )a. (1 REVENDICATIONSProcédé de protection d'un calcul sur un premier nombre (M ; P) et un deuxième nombre (c ; d), exécuté par un circuit électronique (1), dans lequel : le deuxième nombre (c ; d) est décomposé en une somme d'au moins deux troisièmes nombres (Xl, X2) ; et le calcul est effectué bit par bit (X l;, X2i) pour chaque rang (i) des troisièmes nombres (Xl, X2). Procédé selon la revendication 1, dans lequel le calcul représente une exponentiation modulaire du premier nombre (M) par le deuxième nombre (e). Procédé selon la revendication 1, dans lequel le calcul représente une multiplication d'un point (P) d'une courbe elliptique par un scalaire (d). Procédé selon l'une quelconque des revendications 1 à 3, dans lequel les rangs (i) des bits (Xl;, X21) des troisièmes nombres (Xl, X2) sont balayés par ordre croissant. Procédé selon l'une quelconque des revendications 1 à 4, dans lequel les bits (Xl;, X2) de même rang (i) des troisièmes nombres (Xl, X2) sont traités dans un même ordre, d'un rang (i) à l'autre. Procédé selon l'une quelconque des revendications 1 à 5, dans lequel les bits (Xl;, X2) de même rang (i) des troisièmes nombres (Xl, X2) sont traités dans un ordre aléatoire. Procédé selon l'une quelconque des revendications 1 à 6, dans lequel l'ordre de traitement des bits (X11, X21) de même rang (i) des troisièmes nombres (Xl, X2) résulte d'une permutation. Procédé selon l'une quelconque des revendications 1 à 7, dans lequel le traitement effectué sur les bits (Xli, X21) de chaque rang (i) consiste : si le bit (X1i, X2i) considéré est égal à 1, à effectuer une première opération avec un opérateur (. ; +) sur les contenus d'un premier registre (RO) et d'un deuxième registre (R1), puis à placer le résultat dans le premier registre (RO) ; et si le bit (Xi,, X21) considéré est égal à 0, à conserver inchangés les contenus des deux registres (RO, R1). Procédé selon la revendication 8, dans lequel le premier registre (RO) contient le résultat (C) du calcul. Procédé selon la revendication 8 ou 9, dans lequel ledit opérateur est la multiplication (.). 15 [Revendication 11] [Revendication 12] [Revendication 13] [Revendication 14] [Revendication 15] [Revendication 16] Procédé selon la revendication 8 ou 9, dans lequel ledit opérateur est l'addition (+). Procédé selon l'une quelconque des revendications 8 à 11, dans lequel le premier registre (RO) est initialisé avec l'élément neutre (1 ; 0) dudit opérateur (. ; -F). Procédé selon l'une quelconque des revendications 8 à 12, dans lequel le deuxième registre (R1) est initialisé avec le premier nombre (M ; P). Procédé selon l'une quelconque des revendications 8 à 13, dans lequel, après avoir traité tous les bits (X1' X2,) d'un même rang (i) des troisièmes nombres (Xl, X2), une deuxième opération est effectuée avec ledit opérateur (. ; +) sur le contenu du deuxième registre (R1), le résultat de cette deuxième opération étant placé dans le deuxième registre (R 1 ) . Procédé selon l'une quelconque des revendications 8 à 14, dans lequel la ou les opérations sont effectuées modulo un quatrième nombre (N). Circuit électronique (1) configuré pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 15.