Brevet FR3038473A1 — publié le 20170106

DOMAINE TECHNIQUE AUQUEL SE RAPPORTE L'INVENTION La présente invention concerne le domaine de la cryptographie. Elle concerne plus particulièrement un procédé de traitement cryptographique de données et un programme d'ordinateur associé. L'invention s'applique particulièrement avantageusement dans le cas où un algorithme cryptographique utilise une exponentiation modulaire réalisée sous forme atomique. ARRIERE-PLAN TECHNOLOGIQUE On connaît des procédés de traitement cryptographique de données, dans lesquels une clé (par exemple secrète) est appliquée à une donnée (par exemple un message) au moyen d'un algorithme cryptographique. Un tel algorithme cryptographique est par exemple un algorithme de type 15 RSA : dans ce type d'algorithme cryptographique, la clé comprend un exposant et un module et on applique l'exposant au message par exponentiation modulaire, modulo le module précité. Pour effectuer un tel calcul en pratique, l'algorithme cryptographique est fréquemment réalisé au moyen d'une pluralité d'itérations et d'une valeur donnée 20 (égale par exemple à la valeur représentant le message). Dans ce type de solution, on prévoit que chaque itération comprenne ou non, en fonction d'au moins un bit de la clé secrète, une étape de mise en oeuvre d'une opération arithmétique impliquant une première variable et une seconde variable mémorisant la valeur donnée. Dans le cas d'un algorithme 25 cryptographique basé sur une exponentiation modulaire (tel qu'un algorithme de type RSA), cette opération arithmétique est la multiplication. Il a toutefois été remarqué qu'une attaque, dite attaque horizontale, était possible contre ce type de solution du fait que la même valeur est utilisée dans l'opération arithmétique précisément pour les itérations où le bit de la clé secrète a 30 une certaine valeur (par exemple 1). En effet, la consommation électrique liée à la mise en oeuvre de cette opération (avec la même valeur) étant semblable d'une itération à l'autre, il est possible de détecter des corrélations dans la consommation électrique de certaines itérations et d'en déduire quels bits de l'exposant valent 1. 3038473 2 Afin de rendre impossible l'établissement d'une telle corrélation, il a été proposé que chaque itération comprenne une étape de perturbation par combinaison de la première variable avec un élément de perturbation, comme dans l'article "ROSETTA for Single Trace Analysis - Recovery Of Secret Exponent 5 by Triangular Trace Analysis", de C. Clavier, B. Feix, G. Gagnerot, C.Giraud, M. Rousselet and V. Verneuil, in Progress in Cryptology - INDOCRYPT 2012, volume 7668 of LNCS, pages 140-155. Springer, 2012. OBJET DE L'INVENTION Dans ce contexte, la présente invention propose un procédé de 10 traitement cryptographique de données, dans lequel une clé est appliquée à une donnée au moyen d'un algorithme cryptographique comprenant une pluralité d'itérations et utilisant une valeur donnée, chaque itération comprenant ou non, en fonction d'au moins un bit de la clé, une étape de mise en oeuvre d'une opération arithmétique impliquant une première variable et une seconde variable mémorisant la valeur donnée, dans lequel certaines itérations comprennent une étape de perturbation par combinaison de la première variable avec un élément de perturbation, caractérisé en ce que les itérations comprenant ladite étape de perturbation forment au maximum la moitié de ladite pluralité d'itérations. La contremesure n'est ainsi appliquée qu'à un nombre limité d'itérations, ce qui diminue son coût calculatoire. En utilisant une étape de perturbation dans une proportion suffisante d'itérations, on empêche toutefois un attaquant de découvrir l'intégralité de la clé par observation d'éventuelles corrélations entre les différentes itérations. Selon une première possibilité de réalisation (qui correspond au premier exemple décrit plus loin en référence à la figure 2), chaque itération comprend une application, au moyen de l'opération arithmétique, de la première variable à elle-même. Lorsque l'opération arithmétique est une multiplication, ce type de mise en oeuvre prévoit donc que la première variable est systématiquement mise au carré (en utilisant toutefois l'opération arithmétique de multiplication) à chaque itération. Selon une seconde possibilité de réalisation (qui correspond notamment aux second et troisième exemples décrits plus loin, respectivement en référence aux figures 3 et 4), chaque itération comprend sélectivement, en fonction dudit au moins un bit, ladite mise en oeuvre de l'opération arithmétique ou une application, au moyen de l'opération arithmétique, de la première variable à elle-même. 3038473 3 C'est notamment le cas lorsqu'une exponentiation modulaire est réalisée sous forme atomique, c'est-à-dire en mettant en oeuvre précisément une multiplication à chaque itération : c'est alors le second opérande de la multiplication qui varie en fonction dudit au moins un bit (le premier opérande étant 5 ici la première variable). Ce second opérande peut être la première variable (ce qui permet une mise au carré de celle-ci), une autre variable (préalablement initialisée avec ladite valeur donnée, ici la valeur du message reçu), voire une autre variable encore (préalablement initialisée, dans le cas du troisième exemple décrit plus loin en référence à la figure 3, avec le cube de la valeur du message 10 reçu). En pratique, l'étape de perturbation est par exemple mise en oeuvre une unique fois pour un nombre prédéterminé d'itérations (ce nombre prédéterminé étant de manière générale supérieur à 2). En variante, l'étape de perturbation peut être mise en oeuvre une unique fois pour un nombre prédéterminé de bits de la 15 clé, ce qui permet également de diminuer la proportion d'itérations comprenant une étape de perturbation. Quoiqu'il en soit, le nombre prédéterminé précité est typiquement compris entre 2 et 12 Dans le cas vu ci-dessus où la première variable est appliquée à elle- 20 même (en pratique, multipliée par elle-même) à chaque itération, le nombre prédéterminé peut être compris entre 2 et 4. Dans le cas où une mise en oeuvre atomique est utilisée, le nombre prédéterminé peut être compris entre 6 et 12. L'algorithme cryptographique implique par exemple une exponentiation 25 modulaire (comme dans le cas d'un algorithme cryptographique de type RSA) ; l'opération arithmétique peut alors être une multiplication. L'invention propose également un programme d'ordinateur comprenant des instructions exécutables par un processeur et adaptées à mettre en oeuvre un procédé tel que présenté ci-dessus lorsque ces instructions sont exécutées par le 30 processeur. DESCRIPTION DETAILLEE D'UN EXEMPLE DE REALISATION La description qui va suivre en regard des dessins annexés, donnés à titre d'exemples non limitatifs, fera bien comprendre en quoi consiste l'invention et comment elle peut être réalisée. 3038473 4 Sur les dessins annexés : - la figure 1 représente schématiquement les éléments principaux d'une entité électronique au sein de laquelle est mise en oeuvre l'invention ; - la figure 2 représente un premier exemple de procédé dans lequel 5 l'entité électronique applique un algorithme cryptographique à un message reçu ; - la figure 3 représente un second exemple de procédé dans lequel l'entité électronique applique un algorithme cryptographique à un message reçu ; et - la figure 4 représente un troisième exemple de procédé dans lequel 10 l'entité électronique applique un algorithme cryptographique à un message reçu. La figure 1 représente schématiquement les éléments principaux d'une entité électronique 1 au sein de laquelle est mise en oeuvre l'invention. Cette entité électronique est par exemple une carte à microcircuit, par exemple une carte à circuit intégré universelle (ou UICC pour "Universal Integrated Circuit Card'). En 15 variante, il pourrait s'agir d'un élément sécurisé (ou SE pour "Secure Element") - par exemple un microcontrôleur sécurisé, d'un dispositif électronique portatif (ou "hand-held electronic device" selon l'appellation anglo-saxonne) - par exemple un terminal de communication ou un passeport électronique, ou d'un ordinateur. L'entité électronique 1 comprend un microprocesseur 2, une mémoire 20 vive 4 et une mémoire non-volatile réinscriptible 6 (par exemple de type EEPROM pour "Electrically Erasable and Programmable Read-Only Memory"). L'entité électronique 1 pourrait éventuellement comprendre en outre une mémoire morte. La mémoire vive 4 et la mémoire non-volatile réinscriptible 6 (ainsi que le cas échéant la mémoire morte) sont chacune liées au microprocesseur 2 de sorte que 25 le microprocesseur 2 peut lire ou écrire des données dans chacune de ces mémoires. Une de ces mémoires, par exemple la mémoire non-volatile réinscriptible 6, mémorise des instructions de programme d'ordinateur qui permettent la mise en oeuvre de l'un au moins des procédés décrits ci-dessous en référence aux figures 30 2 à 4 lorsque ces instructions sont exécutées par le microprocesseur 2. Les mémoires 4, 6 stockent également des données représentatives de valeurs utilisées lors de la mise en oeuvre des procédés décrits ci-dessous. Par exemple, la mémoire non-volatile réinscriptible 6 mémorise une clé (par exemple une clé privée ou une clé publique) formée d'un exposant d et d'un module p. 3038473 5 La mémoire non-volatile réinscriptible peut également mémoriser un nombre n définissant, comme expliqué ci-après, la proportion d'itérations pour lesquelles une étape de perturbation est appliquée. En variante, l'application d'une étape de perturbation à certaines itérations seulement pourrait toutefois découler 5 d'une programmation particulière des programmes susmentionnés, sans utilisation d'une variable mémorisée telle que le nombre n mentionné ci-dessus. La mémoire vive 4 mémorise par ailleurs, par exemple au sein de variables, des données traitées au cours des procédés décrits ci-dessous, notamment, comme expliqué plus bas, un message m et une variable k 10 mémorisant une valeur aléatoire. L'entité électronique 1 comprend en outre une interface de communication 8 avec des dispositifs électroniques externes. Dans le cas décrit ici où l'entité électronique 1 est une carte à microcircuit, l'interface de communication 8 comprend par exemple des contacts affleurant sur une face de la carte à 15 microcircuit. En variante, l'interface de communication 8 pourrait être réalisée par un module de communication sans contact. De manière générale, l'interface de communication 8 peut être un module de communication (filaire ou sans fil) avec une autre entité électronique. Le microprocesseur 2 peut ainsi recevoir des données (par exemple un 20 message m) de l'autre entité électronique via l'interface de communication 8 et émettre des données, par exemple un résultat d'application d'un algorithme cryptographique au message m, à l'autre entité électronique via l'interface de communication 8. Dans les exemples qui suivent, l'algorithme cryptographique appliqué est 25 de type RSA et vise donc l'exponentiation modulaire du message m par l'exposant d, en utilisant le module p, soit le calcul de : Md mod p. Un tel algorithme cryptographique peut être un algorithme de chiffrement ou de vérification de signature (la clé formée par l'exposant d et le module p étant alors une clé publique), ou bien un algorithme de déchiffrement ou de signature (la 30 clé formée par l'exposant d et le module p étant alors une clé privée). L'algorithme cryptographique pourrait toutefois être d'un autre type, par exemple un autre algorithme cryptographique basé sur le problème du logarithme discret tel que l'algorithme de signature numérique sur courbe elliptique ECDSA (pour "Elliptic Curve Digital Signature Algorithm"). Dans le cas d'un algorithme 3038473 6 cryptographique utilisant une courbe elliptique, l'opération arithmétique concernée est une addition de points de la courbe elliptique (au lieu d'une multiplication modulaire dans l'exemple décrit ci-dessous). On peut également être amené à mettre en oeuvre dans ce cas un procédé comprenant, pour chacune d'une 5 pluralité d'itérations, une mise en oeuvre de cette opération cryptographique ; un tel procédé est par exemple un procédé de doublement et d'addition (ou "Double and Add' selon l'appellation anglo-saxonne). Un tel procédé peut, comme les procédés décrits ci-dessous, être réalisé sous forme atomique et être l'objet d'attaques horizontales telles que présentées en introduction. 10 On peut ainsi dans ce cas également appliquer une étape de perturbation à certaines itérations seulement, comme décrit ci-dessous pour un algorithme RSA. Dans le cas d'un algorithme sur courbe elliptique, l'étape de perturbation peut comprendre l'ajout d'une valeur p (comme décrit ci-dessous dans un autre cadre) à chacune des coordonnées du point de la courbe traité (les 15 itérations suivantes étant réalisées sans réduction modulo p) ; en variante et dans le cas d'une représentation en coordonnées projectives, l'étape de perturbation peut comprendre une multiplication par une constante (en jouant sur la classe d'équivalence pour ne pas obtenir d'effet sur le résultat final). La figure 2 représente, sous forme de logigramme, un premier exemple 20 de procédé conforme aux enseignements de l'invention, dans lequel l'entité électronique 1 applique un algorithme cryptographique à un message reçu m. Dans cet exemple, l'exposant d comprend I bits et sa décomposition binaire est de la forme (1,c11-2,...,do), dO étant le bit de poids le plus faible. Le procédé de la figure 2 débute à l'étape E10 par la réception du 25 message m par l'entité électronique 1 (précisément par le microprocesseur 2), via l'interface de communication 8. L'entité électronique 1 (c'est-à-dire par exemple le microprocesseur 2, ou en variante un crypto-processeur distinct) peut éventuellement alors procéder (étape E12) à la génération d'une valeur aléatoire k (c'est-à-dire précisément à la 30 mémorisation dans une variable k d'un nombre obtenu par tirage aléatoire ou pseudo-aléatoire). En variante, le procédé pourrait se poursuivre directement à l'étape E16 décrite ci-après. Lorsqu'une valeur aléatoire k est générée à l'étape E12, le message m peut être masqué par ajout à la variable m (qui mémorise le message) d'un 3038473 7 nombre k.p égal au produit de la valeur aléatoire k et du module p. Puisque les étapes qui suivent (ici dans le cadre d'un algorithme de type RSA) effectue des calculs d'arithmétique modulaire modulo p, l'ajout du nombre k.p à l'étape E12 n'aura aucune conséquence sur le résultat de l'algorithme 5 cryptographique ; toutefois, grâce à l'utilisation de la valeur aléatoire k, les nombres manipulés seront différents d'une mise en oeuvre de l'algorithme cryptographique à l'autre, ce qui permet de lutter contre certaines attaques par canal auxiliaire (ou SCA pour "Side-Channel Attacks"). Le procédé se poursuit à l'étape E16 par l'initialisation d'une variable T 10 avec la valeur de la variable m (c'est-à-dire par exemple en pratique en recopiant, dans la variable T, la valeur mémorisée dans la variable m représentative du message reçu, éventuellement masqué par l'étape E14). Une variable d'indice i est par ailleurs initialisée à l'étape E18 à la valeur 1-2 (où 1 représente comme indiqué ci-dessus le nombre de bits de l'exposant d). 15 Le procédé de la figure 2 entre alors dans une boucle qui permet de mettre en oeuvre une pluralité d'itérations (ici 1-1 itérations), chaque itération correspondant aux étapes E20 à E32 décrites ci-dessous. Le microprocesseur 2 détermine à l'étape E20 si le nombre prédéterminé n (mentionné plus haut) divise la valeur courante de la variable d'indice i. 20 En cas de résultat négatif à l'étape E20, le procédé se poursuit directement à l'étape E24. En cas de résultat positif à l'étape E20 (c'est-à-dire si n divise i), le microprocesseur 2 procède à l'étape E22 en ajoutant à la variable T le module p (ou un multiplie du module p) : la variable T est modifiée en y ajoutant a.p (avec a 25 un nombre entier non-nul, généralement petit, a ayant typiquement une valeur qui s'écrit en binaire sur 32 bits maximum). L'étape E22 permet de perturber la valeur de la variable T (ici par combinaison avec la valeur de perturbation a.p au moyen d'une addition) ; cette valeur sera ainsi complètement différente de celle manipulée aux précédentes 30 itérations et un attaquant ne pourra donc pas observer de corrélation entre les différentes itérations. On comprend en effet qu'une étape de perturbation entraîne une modification de la valeur de la variable perturbée, sans incidence toutefois sur le résultat final. L'utilisation du test de l'étape E20 permet toutefois de ne mettre en 3038473 8 oeuvre cette étape de perturbation que pour une itération sur n itérations, ce qui allège le coût calculatoire de la contremesure. Selon les applications, n peut valoir par exemple 2, 3 ou 4, comme expliqué plus bas. On remarque par ailleurs (comme déjà indiqué à propos de l'étape E14) 5 que cette perturbation n'aura pas d'effet sur le résultat du calcul puisqu'une réduction modulo p est appliquée (voir ci-dessous l'étape E34) avant émission du résultat. Dans tous les cas, le procédé se poursuit à l'étape E24 à laquelle le microprocesseur 2 applique à la variable T une multiplication modulaire par elle- 10 même. Cette opération permet une mise au carré (modulaire) de la variable T; on utilise toutefois une opération de multiplication afin de rendre plus difficile pour un attaquant la distinction entre la présente étape E24 et l'étape E28 décrite plus bas. On remarque par aillleurs que la multiplication modulaire de l'étape E24 est réalisée modulo 6.p, avec 13 un entier supérieur à a, de manière à ne pas 15 annuler l'effet de la perturbation de l'étape E22. En variante, on pourrait utiliser (à la place de la réduction modulo 13.p) une réduction modulo p partielle (le résultat y de l'application d'une telle réduction modulo p partielle et le résultat x de l'application d'une réduction modulo p vérifiant : x = q.p + y avec p REVENDICATIONS1. Procédé de traitement cryptographique de données, dans lequel une clé (d) est appliquée à une donnée (m) au moyen d'un algorithme cryptographique comprenant une pluralité d'itérations et utilisant une valeur donnée (m), chaque itération comprenant ou non, en fonction d'au moins un bit (c11) de la clé (d), une étape de mise en oeuvre d'une opération arithmétique (E28; E56; E86) impliquant une première variable (T; Ro) et une seconde variable (m ; R; R1) mémorisant la valeur donnée (m), dans lequel certaines itérations comprennent une étape de perturbation (E22; E54; E84) par combinaison de la première variable (T; Ro) avec un élément de perturbation (a.p), caractérisé en ce que les itérations comprenant ladite étape de perturbation (E22; E54; E84) forment au maximum la moitié de ladite pluralité d'itérations. 2. Procédé selon la revendication 1, dans lequel chaque itération comprend une application (E24), au moyen de l'opération arithmétique, de la première variable à elle-même. 3. Procédé selon la revendication 1, dans lequel chaque itération comprend sélectivement, en fonction dudit au moins un bit (d1), ladite mise en oeuvre de l'opération arithmétique ou une application, au moyen de l'opération arithmétique, de la première variable à elle-même. 4. Procédé selon l'une des revendications 1 à 3, dans lequel l'étape de perturbation (E22 ; E84) est mise en oeuvre une unique fois pour un nombre prédéterminé (n) d'itérations. 5. Procédé selon l'une des revendications 1 à 3, dans lequel l'étape de perturbation (E54) est mise en oeuvre une unique fois pour un nombre prédéterminé (n) de bits de la clé (d). 6. Procédé selon la revendication 4 ou 5, dans lequel le nombre prédéterminé (n) est compris entre 2 et 12. 7. Procédé selon la revendication 4 prise dans la dépendance de la revendication 2, dans lequel le nombre prédéterminé (n) est compris entre 2 et 4. 8. Procédé selon la revendication 4 prise dans la dépendance de la revendication 3, dans lequel le nombre prédéterminé (n) est compris entre 6 et 12. 9. Procédé selon l'une des revendications 1 à 8, dans lequel l'algorithme 3038473 17 cryptographique implique une exponentiation modulaire et dans lequel l'opération arithmétique est une multiplication. 10. Programme d'ordinateur comprenant des instructions exécutables par un processeur et adaptées à mettre en oeuvre un procédé selon l'une des 5 revendications 1 à 9 lorsque ces instructions sont exécutées par le processeur.