Brevet FR3055437A1 — publié le 20180302

B15092 - 16-R0-0237 1 PROTECTION D'UN CALCUL D'EXPONENTLATION MODULAIRE Domaine La présente description concerne de façon générale les circuits électroniques et, plus particulièrement, les circuits exécutant des opérations d'exponentiation modulaire. La présente description concerne plus particulièrement la protection de tels calculs contre des attaques visant à découvrir des quantités manipulées par ces calculs. Exposé de l'art antérieur Dans de nombreuses applications, des circuits électroniques mettent en oeuvre des algorithmes de 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 d'exponentiation modulaire, par exemple des algorithmes de type RSA. De nombreuses méthodes, dites attaques, existent pour tenter de découvrir ou pirater des données secrètes manipulées 20 par ces calculs. Parmi ces attaques, des attaques dites par canaux cachés, exploitent des informations indirectes telles que la 3055437 B15092 - 16-R0-0237 2 consommation du circuit (attaques SPA, DPA), son rayonnement, etc. L'interprétation de ces informations renseigne le pirate sur la donnée secrète. Dans les attaques par canaux cachés, on distingue 5 notamment les attaques dites verticales, et les attaques dites horizontales. Les attaques verticales consistent à exploiter les variations d'une même quantité secrète sur plusieurs traces successives, par exemple de consommations, enregistrées en ayant fait différentes hypothèses sur la quantité secrète. Les attaques 10 horizontales consistent à exploiter les différentes opérations d'une même trace et relatives aux quantités secrètes. Les contremesures qui sont généralement efficaces contre des attaques verticales par canaux cachés ne le sont généralement pas contre les attaques horizontales. 15 Il existe un besoin d'améliorer la protection des données manipulées par des algorithmes exécutant des exponentiations modulaires contre des attaques par canaux cachés. Résumé Un mode de réalisation pallie tout ou partie des 20 inconvénients des procédés et circuits usuels de protection de données manipulées par des algorithmes contre des attaques par canaux cachés. Un mode de réalisation propose un procédé de calcul d'une exponentiation modulaire par un circuit électronique qui 25 pallie tout ou partie des inconvénients des procédés usuels. Un mode de réalisation propose un procédé de calcul efficace contre des attaques horizontales. Ainsi, un mode de réalisation prévoit un procédé de protection d'un calcul d'exponentiation modulaire sur un premier 30 nombre et un exposant, modulo un premier modulo, exécuté par un circuit électronique utilisant un premier registre ou emplacement mémoire et un deuxième registre ou emplacement mémoire, comportant successivement, pour chaque bit de l'exposant : un tirage d'un nombre aléatoire 3055437 B15092 - 16-R0-0237 3 une multiplication modulaire du contenu du premier registre ou emplacement mémoire par celui du deuxième registre ou emplacement mémoire, en plaçant le résultat dans l'un des premier et deuxième registres ou emplacements mémoire choisi en fonction 5 de l'état du bit de l'exposant ; un carré modulaire du contenu de l'un des premier et deuxième registres ou emplacements mémoire choisi en fonction de l'état de l'exposant, en plaçant le résultat dans ce registre ou emplacement mémoire choisi, 10 les opérations de multiplication et de carré étant effectuées modulo le produit du premier modulo par ledit nombre aléatoire. Selon un mode de réalisation, le résultat du calcul d'exponentiation modulaire est contenu dans ledit premier registre 15 ou emplacement mémoire. Selon un mode de réalisation, le procédé comporte les étapes suivantes : initialiser le premier registre ou emplacement mémoire à la valeur 1 ; initialiser le deuxième registre ou emplacement mémoire à la valeur du premier nombre. Un mode de réalisation prévoit un circuit électronique adapté à la mise en oeuvre du procédé ci-dessus. Brève description des dessins Ces caractéristiques et avantages, ainsi que d'autres, seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : la figure 1 représente, de façon schématique, un mode 30 de réalisation d'un circuit électronique ; la figure 2 représente, sous forme de blocs, les étapes d'un calcul par la méthode de carré-multiplication par l'échelle de Montgomery ; et 3055437 B15092 - 16-R0-0237 4 la figure 3 représente, sous forme de blocs, un mode de réalisation d'un procédé de protection d'un calcul d'exponentiation modulaire. Description détaillée 5 De mêmes éléments ont été désignés par de mêmes références aux différentes figures. En particulier, les éléments structurels et/ou fonctionnels communs aux différents modes de réalisation peuvent présenter les mêmes références et peuvent disposer de propriétés structurelles, dimensionnelles et 10 matérielles identiques. Par souci de clarté, seuls les éléments utiles à la compréhension des modes de réalisation décrits ont été représentés et seront 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 15 décrits étant compatibles avec les applications usuelles. La figure 1 représente, de façon très schématique un circuit électronique 1 du type auquel s'appliquent les modes de réalisation qui vont être décrits. Le circuit 1 comporte : 20 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 volatile et/ou non volatile pour stocker tout ou partie des données et 25 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 (I/O) de communication avec l'extérieur du circuit 1. Le circuit 1 peut inclure divers autres circuits en fonction de l'application, symbolisés en figure 1 par un bloc 19 (FCT). Des opérations d'exponentiation modulaire se retrouvent dans de nombreux algorithmes de chiffrement parmi lesquels, par 35 exemple, l'algorithme connu sous la dénomination RSA. 3055437 B15092 - 16-R0-0237 5 Une exponentiation modulaire consiste à calculer le résultat C de l'exponentiation d'un nombre M par un entier d (exposant) modulo N, c'est-à-dire appliquer la formule : C = Md (mod N). 5 Le plus souvent : le nombre M représente le nombre (ou une information représentative du nombre) que l'on souhaite chiffrer, authentifier, signer, etc. ; et l'exposant d et le modulo N (le couple (d, N)) 10 représentent la clé (ou des informations représentatives de la clé) de chiffrement, d'authentification, de signature, etc. Dans l'exemple d'application au chiffrement RSA, la clé de chiffrement est le couple (d, N) et la clé de déchiffrement est un couple (d', N), où N est le module de chiffrement et d' 15 l'exposant de déchiffrement. 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 le plus souvent en 20 appliquant une méthode dite échelle de Montgomery (Montgomery Powering Ladder). La figure 2 représente, sous forme de blocs, les étapes d'un calcul par la méthode de l'échelle de Montgomery. Le calcul utilise au moins deux registres du circuit 1, 25 ou deux emplacements mémoire, notés arbitrairement TO et Tl, sur lesquelles vont être effectuées les opérations. On fera par la suite référence, pour simplifier, à des registres mais il peut à chaque fois également s'agir d'emplacements mémoire. Le message, par exemple le nombre M, à soumettre à 30 l'exponentiation modulaire est chargé dans le registre Tl. L'exposant d est lu bit par bit au cours du calcul. On note di chaque bit de l'exposant d, où i désigne le rang allant de 0 à k-1, où k représente la taille de l'exposant d. 3055437 B15092 - 16-R0-0237 6 Par la suite, pour simplifier, on confondra les registres et leur contenu, c'est-à-dire qu'en faisant référence à des opérations sur les registres, on entend sur leurs contenus. Dans une première étape (bloc 21, T1=M, 10=1), le 5 registre Tl est donc chargé avec le nombre M et le registre TO est initialisé à 1. On entame alors un calcul en boucle sur les bits de l'exposant d. Par exemple, un compteur i est initialisé à k-1 (bloc 22, i=k-1) et est décrémenté de 1 (bloc 23, i=i-1) à chaque 10 traitement d'un bit di de l'exposant tant que tous les bits n'ont pas été traités (bloc 24, i=0 ?). A chaque itération, c'est à dire pour chaque bit di, on commence par tester la valeur du bit de l'exposant (bloc 25, di=1 ?). 15 Si le bit courant di vaut 1 (sortie Y du bloc 25), le contenu du registre TO est multiplié, modulo N, par le contenu du registre Tl et le résultat est placé dans le registre TO (bloc 26, TO=10.11 (mod N)), puis le contenu du registre Tl est élevé au carré, modulo N, et le résultat est placé dans le registre Tl 20 (bloc 27, T1=11.11 (mod N)). Cela revient à effectuer l'opération de multiplication-carré, le produit des deux registres est mis dans le registre TO, puis le contenu du registre Tl est remplacé par son carré. Si le bit courant di vaut 0 (sortie N du bloc 25), le 25 contenu du registre TO est multiplié, modulo N, par le contenu du registre Tl et le résultat est placé dans le registre Tl (bloc 26', T1=10.11 (mod N)), puis le contenu du registre TO est élevé au carré, modulo N, et le résultat est placé dans le registre TO (bloc 27', TO=TO.TO (mod N)). Cela revient à effectuer l'opération 30 de multiplication-carré, le produit des deux registres est mis dans le registre Tl, puis le contenu du registre TO est remplacé par son carré. Tant que tous les bits de l'exposant d n'ont pas été traités (sortie N du bloc 24), on décrémente le compteur i (bloc 35 23) et on revient à l'étape 25. Une fois que tous les bits de 3055437 B15092 - 16-R0-0237 7 l'exposant d ont été traités (sortie Y du bloc 24), le registre TO contient le résultat de l'exponentiation modulaire (bloc 29, TO), c'est-à-dire la valeur C = Md (mod N). Le calcul illustré par la figure 2 peut s'écrire 5 également de la façon suivante : TO = 1 (étape 21) Tl = M (étape 21) Pour i=k-1 à 0 (étapes 22 à 27) : b = 1-di 10 Tb = TO.T1 (mod N) Tdi = Tdi.Tdi (mod N) Fin de boucle (sortie Y du bloc 24) Retourner TO (étape 29). Pour protéger le calcul contre des attaques exploitant 15 une analyse par canaux cachés du type par analyse différentielle de la consommation (DPA ou Differential Power Analysis), on a déjà proposé d'introduire un nombre aléatoire dans le modulo N au début du calcul. Ainsi, on tire un nombre aléatoire r avant le calcul en boucle et les multiplications des étapes 26, 26', 27 et 27' 20 sont en fait effectuées modulo rN. Une telle solution est efficace sur les attaques verticales. Toutefois, ce nombre aléatoire est sans effet sur des attaques horizontales dans la mesure où elles n'exploitent qu'une seule trace, donc une seule exécution. 25 La figure 3 représente, sous forme de blocs, un mode de réalisation d'un procédé de protection d'un calcul d'exponentiation modulaire résistant à des attaques horizontales par canaux cachés. Comme précédemment, l'objectif est de calculer la valeur 30 C = Md (mod N) par la méthode de l'échelle de de Montgomery. Le calcul utilise toujours deux registres du circuit 1, notés arbitrairement TO et Tl sur lesquelles vont être effectuées les opérations. De même, le message, par exemple le nombre M, à soumettre à l'exponentiation modulaire, est chargé dans le 35 registre Tl. L'exposant d est chargé dans un autre registre ou 3055437 B15092 - 16-R0-0237 8 réside dans la mémoire. (di représentant chaque bit de l'exposant d, où i désigne le rang allant de 0 à k-1). Dans une première étape (bloc 31, T1=M, 10=1), le registre Tl est comme précédemment chargé avec le nombre M et le 5 registre TO est initialisé à 1. On entame alors un calcul en boucle sur les bits de l'exposant d. Par exemple, un compteur i est initialisé à k-1 (bloc 32, i=k-1) et est décrémenté de 1 (bloc 33, i=i-1) à chaque traitement d'un bit di de l'exposant tant que tous les bits n'ont 10 pas été traités (bloc 34, i=0 ?). A chaque itération, c'est à dire pour chaque bit di, on tire (bloc 38, ri) un nombre aléatoire ri. Le nombre ri comporte un nombre de bits quelconque, c'est-à-dire choisi sans lien avec le modulo ou la taille des autres quantités manipulées. Puis, on 15 teste la valeur du bit de l'exposant (bloc 35, di=1 ?). Si le bit courant di vaut 1 (sortie Y du bloc 35), le contenu du registre TO est multiplié, modulo riN, par le contenu du registre Tl et le résultat est placé dans le registre TO (bloc 36, TO=10.11 (mod riN)), puis le contenu du registre Tl est élevé 20 au carré, modulo riN, et le résultat est placé dans le registre Tl (bloc 37, T1=11.11 (mod riN)). Cela revient à effectuer l'opération de multiplication-carré, le produit des deux registres est mis dans le registre TO, puis le contenu du registre Tl est remplacé par son carré. 25 Si le bit courant di vaut 0 (sortie N du bloc 35), le contenu du registre TO est multiplié, modulo riN, par le contenu du registre Tl et le résultat est placé dans le registre Tl (bloc 36', T1=10.11 (mod riN)), puis le contenu du registre TO est élevé au carré, modulo riN, et le résultat est placé dans le registre 30 TO (bloc 37', TO=TO.TO (mod riN)). Cela revient à effectuer l'opération de multiplication-carré, le produit des deux registres est mis dans le registre Tl, puis le contenu du registre TO est remplacé par son carré. Tant que tous les bits de l'exposant d n'ont pas été 35 traités (sortie N du bloc 34), on décrémente le compteur i et on 3055437 B15092 - 16-R0-0237 9 revient à l'étape 38. Une fois que tous les bits de l'exposant d ont été traités (sortie Y du bloc 34), le registre TO contient le résultat de l'exponentiation modulaire (bloc 39, TO), c'est-à-dire la valeur C = Md (mod N). En effet, l'introduction d'un 5 modulo différent, à chaque itération ne change pas le résultat final une fois que celui-ci est réduit modulo N. Le calcul illustré par la figure 3 peut s'écrire également de la façon suivante : TO = 1 (étape 31) 10 Tl = M (étape 31) Pour i=k-1 à 0 (étapes 32 à 38) : Tirer ri b = 1-di Tb = TO.T1 (mod riN) 15 Tdi = Tdi.Tdi (mod riN) Fin de boucle (sortie Y du bloc 34) Retourner TO (mod N) (étape 39). Un avantage qu'il y a à changer le nombre aléatoire ri à chaque itération de la boucle est que cet aléa masque 20 différemment le calcul à chaque itération de cette boucle. Ainsi, l'analyse de la trace en cas d'attaque horizontale devient inexploitable. Un autre avantage est que cette contremesure est également efficace en cas d'attaques verticales. 25 Divers modes de réalisation ont été décrits. Diverses variantes et modifications apparaîtront à l'homme de l'art. En particulier, la dénomination des registres est arbitraire et pourra être inversée. Enfin, la mise en oeuvre pratique des modes de réalisation qui ont été décrits est à la portée de l'homme du 30 métier à partir des indications fonctionnelles données ci-dessus. REVENDICATIONS1. Procédé de protection d'un calcul d'exponentiation modulaire sur un premier nombre (M) et un exposant (d), modulo un premier modulo (N), exécuté par un circuit électronique (1) utilisant un premier registre ou emplacement mémoire (TO) et un deuxième registre ou emplacement mémoire (Tl), comportant successivement, pour chaque bit de l'exposant (d) : un tirage d'un nombre aléatoire (ri) ; une multiplication modulaire (36, 36') du contenu du premier registre ou emplacement mémoire par celui du deuxième registre ou emplacement mémoire, en plaçant le résultat dans l'un des premier et deuxième registres ou emplacements mémoire choisi en fonction de l'état du bit de l'exposant ; un carré modulaire (37, 37') du contenu de l'un des premier et deuxième registres ou emplacements mémoire choisi en 15 fonction de l'état de l'exposant, en plaçant le résultat dans ce registre ou emplacement mémoire choisi, les opérations de multiplication et de carré étant effectuées modulo le produit du premier modulo par ledit nombre aléatoire. 20 2. Procédé selon la revendication 1, dans lequel le résultat du calcul d'exponentiation modulaire est contenu dans ledit premier registre ou emplacement mémoire (TO). 3. Procédé selon la revendication 1 ou 2, comportant les étapes suivantes : 25 initialiser (31) le premier registre ou emplacement mémoire (TO) à la valeur 1 ; initialiser (31) le deuxième registre ou emplacement mémoire (Tl) à la valeur du premier nombre (M). 4. Circuit électronique (1) adapté à la mise en 30 oeuvre du procédé selon l'une quelconque des revendications 1 à 3.