Brevet FR3076013A1 — publié le 20190628

DOMAINE TECHNIQUE AUQUEL SE RAPPORTE L'INVENTION La présente invention concerne de manière générale le domaine de la cryptographie. Elle concerne plus particulièrement un procédé de traitement cryptographique, ainsi qu'un programme d'ordinateur et un dispositif associés. ARRIERE-PLAN TECHNOLOGIQUE Certains procédés de traitement cryptographique, tels que l'algorithme RSA, mettent en oeuvre une exponentiation modulaire de la donnée à traiter (l'exposant correspondant à une clé cryptographique à appliquer). Afin de contrer d'éventuelles attaques, il est connu de modifier de manière aléatoire les données manipulées à chaque mise en oeuvre de l'algorithme (même lorsque la donnée traitée et la clé cryptographique appliquée sont identiques). Il a par exemple été proposé pour ce faire de masquer la clé cryptographique par addition d'un multiple aléatoire de l'indicatrice d'Euler associée au module utilisé, ce qui permet de modifier les données manipulées sans incidence sur le résultat de l'exponentiation modulaire. Il a aussi été proposé, en tant qu'alternative, d'effectuer à chaque fois une division entière de la clé cryptographique par un nombre aléatoire (fournissant un quotient et un reste différents à chaque fois) et de réaliser alors deux exponentiations modulaires : l'une avec pour exposant le produit du quotient et du nombre aléatoire, l'autre avec pour exposant le reste (le résultat de l'algorithme étant obtenu en combinant les deux résultats d'exponentiation modulaire par multiplication modulaire). Chacune de ces contremesures peut toutefois se révéler inefficace pour certaines valeurs de module ou de clé cryptographique, ce qui rend possible certaines attaques lorsque l'attaquant peut avoir une influence sur le processus de génération de la clé cryptographique. OBJET DE L'INVENTION Dans ce contexte, la présente invention propose un procédé de traitement cryptographique d'une donnée par exponentiation modulaire de module prédéterminé, comprenant les étapes suivantes : 2 - masquage d'une clé cryptographique par addition, à la clé cryptographique, d'un multiple de l'indicatrice d'Euler associée au module prédéterminé; - détermination du quotient et du reste de la division entière de la clé 5 cryptographique masquée par une constante ; - obtention d'un premier nombre par exponentiation modulaire de la donnée à un premier exposant égal au produit du quotient par la constante modifiée en fonction du reste ; - obtention d'un second nombre par exponentiation modulaire de la 10 donnée à un second exposant déterminé en fonction du quotient et du reste ; - multiplication modulaire du premier nombre et du second nombre. Selon cette conception, il est possible de choisir la constante précitée (par exemple 232-1 ou 232+1) de manière à rendre quasi-immédiate la division entière susmentionnée, comme expliqué dans la description qui suit. 15 Le premier exposant utilisé ci-dessus est de l'ordre de grandeur du produit du quotient par la constante, mais est lui aussi en quelque sorte masqué par l'intervention du reste. Le second exposant utilisé ci-dessus permet quant à lui de tenir compte du reste dans l'exponentiation modulaire, mais aussi de corriger la modification du 20 premier exposant du fait de l'intervention du reste. On assure par ailleurs une protection contre d'éventuelles attaques quelles que soient la valeur du module et la valeur de la clé cryptographique puisqu'on utilise à la fois le masquage par un multiple de l'indicatrice d'Euler et la séparation de l'exposant en deux parties à chaque fois distinctes, sans toutefois 25 augmenter sensiblement le coût calculatoire. D'autres caractéristiques non limitatives et avantageuses d'un tel procédé, prises individuellement ou selon toutes les combinaisons techniquement possibles, sont les suivantes : - ledit multiple de l'indicatrice d'Euler est déterminé par multiplication de 30 l'indicatrice d'Euler par un nombre aléatoire ; - le premier exposant est égal au produit du quotient par la constante diminuée du reste ; - le second exposant est égal au produit du quotient incrémenté de un et du reste ; 3 - ladite constante est une puissance entière de deux diminuée de un ou incrémentée de un ; L'invention propose également un programme d'ordinateur comprenant des instructions exécutables par un processeur conçues pour mettre en oeuvre un 5 procédé tel que présenté ci-dessus lorsque ces instructions sont exécutées par le processeur. L'invention propose également un dispositif de traitement cryptographique d'une donnée par exponentiation modulaire de module prédéterminé, comprenant : 10 - un module de masquage d'une clé cryptographique par addition, à la clé cryptographique, d'un multiple de l'indicatrice d'Euler associée au module prédéterminé; - un module de détermination du quotient et du reste de la division entière de la clé cryptographique masquée par une constante ; 15 - un module d'obtention d'un premier nombre par exponentiation modulaire de la donnée à un premier exposant égal au produit du quotient par la constante modifiée en fonction du reste ; - un module d'obtention d'un second nombre par exponentiation modulaire de la donnée à un second exposant déterminé en fonction du quotient 20 et du reste ; - un module de multiplication modulaire du premier nombre et du second nombre. Ce dispositif peut comprendre en outre un module de détermination du multiple de l'indicatrice d'Euler par multiplication de l'indicatrice d'Euler par un 25 nombre aléatoire. Ce dispositif peut également comporter certaines au moins des caractéristiques optionnelles présentées ci-dessus en terme de procédé. DESCRIPTION DETAILLEE D'UN EXEMPLE DE REALISATION La description qui va suivre en regard des dessins annexés, donnés à 30 titre d'exemples non limitatifs, fera bien comprendre en quoi consiste l'invention et comment elle peut être réalisée. Sur les dessins annexés : - la figure 1 représente schématiquement les éléments principaux d'un dispositif au sein duquel peut être mise en oeuvre l'invention ; 4 - la figure 2 représente, sous forme fonctionnelle, le dispositif de la figure 1 ; et - la figure 3 représente, sous forme de logigramme, un exemple de procédé mis en oeuvre dans le dispositif de la figure 1 et conforme à l'invention. 5 La figure 1 représente schématiquement les éléments principaux d'un dispositif de traitement cryptographique de données, ici une entité électronique 1, au sein de laquelle est mise en oeuvre l'invention. Cette entité électronique est par exemple une carte à microcircuit, telle qu'une carte à circuit intégré universelle (ou UICC pour "Universal Integrated Circuit Card"). En variante, il pourrait s'agir d'un 10 é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 processeur 2 (ici un 15 microprocesseur), une mémoire 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 20 processeur 2 de sorte que le processeur 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, lorsque ces instructions sont exécutées par le processeur 2, la mise en oeuvre des 25 modules fonctionnels présentés ci-dessous en référence à la figure 2 et/ou la mise en oeuvre d'un procédé par le processeur 2, tel que le procédé décrit ci-dessous en référence à la figure 3. 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 30 exemple, la mémoire non-volatile réinscriptible 6 mémorise une clé cryptographique K (telle qu'une clé privée) utilisée dans les procédés de traitement cryptographique exécutés par l'entité électronique 1 (tel que le procédé décrit plus bas en référence à la figure 3). La mémoire non-volatile réinscriptible 6 mémorise également une 5 constante v (égale par exemple à 232-1 ou à 232+1) utilisée dans le procédé décrit ci-dessous en référence à la figure 3. Comme décrit ci-après, l'entité électronique 1 permet d'effectuer des calculs d'arithmétique modulaire de module N prédéterminé et mémorise ainsi en 5 outre dans la mémoire non-volatile 6 l'indicatrice d'Euler (p(N) associée à ce module N. En variante, l'indicatrice d'Euler (p(N) pourrait être calculée à chaque itération de l'algorithme cryptographique concerné et ne serait pas alors mémorisée au sein de l'entité électronique 1. On se place ici dans le cas d'une mise en oeuvre de l'algorithme RSA 10 utilisant le théorème des restes chinois (ou RSA CRT selon l'appellation anglo- saxonne). Dans une telle mise en oeuvre, le module N utilisé dans les calculs est un nombre premier et la donnée x traitée est donc un nombre premier avec le module prédéterminé N. La mémoire vive 4 mémorise par ailleurs, par exemple au sein de 15 variables, des données traitées au cours des procédés décrits ci-dessous. 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 à 20 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 processeur 2 peut ainsi recevoir en entrée une donnée x en 25 provenance de l'autre entité électronique via l'interface de communication 8 et émettre en sortie une autre donnée, par exemple le résultat y obtenu par application d'un algorithme cryptographique (tel que celui décrit ci-dessous en référence à la figure 3) à la donnée x, à destination de l'autre entité électronique via l'interface de communication 8. 30 La figure 2 représente le dispositif électronique de la figure 1 (c'est-à-dire ici l'entité électronique 1) sous forme de modules fonctionnels 10, 12, 14, 16, 18, 20, 22, réalisés ici chacun au moyen du processeur 2, de la mémoire vive 4 et d'une partie correspondante des instructions mémorisées dans la mémoire non-volatile 6 et exécutables par le processeur 2. 6 L'entité électronique 1 comprend un premier module 10 conçu pour déterminer un multiple M de l'indicatrice d'Euler cp(N) par multiplication de l'indicatrice d'Euler (mémorisée dans la mémoire non-volatile réinscriptible 6 ou en variante calculée au sein du premier module 10) par un nombre aléatoire VAL 5 (obtenu par exemple par tirage aléatoire au sein du processeur 2). L'entité électronique 1 comprend également un second module 12 conçu pour masquer la clé cryptographique K (mémorisée dans la mémoire non-volatile réinscriptible 6) en ajoutant à la clé cryptographique K le multiple M de l'indicatrice d'Euler cp(N) déterminé par le premier module 10. 10 L'entité électronique 1 comprend un troisième module 14 conçu pour déterminer le quotient q et le reste r de la division entière de la clé cryptographique masquée K* (produite par le second module 12) par la constante v mémorisée dans la mémoire non-volatile réinscriptible 6. On rappelle que la constante v est ici égale à 232-1 (ou en variante à 232+1). La constante pourrait 15 toutefois avoir une autre valeur, par exemple du type 2a-1 (avec a> 16). Selon une possibilité de mise en oeuvre, le reste r peut être par exemple déterminé (au sein du troisième module 14) au moyen d'une méthode dite "ruban de Pascar, présentée par exemple dans le prologue "M. Pascal's Division Machine" de l'ouvrage "Elements of Automata Theory", de J. Sakarovitch, pp. 1-6, 20 Cambridge, 2009, en utilisant r = K* mod v. Le quotient peut alors par exemple être déterminé en divisant (K*-r) par v (cette dernière division étant exacte, c'est-à-dire ayant un reste nul), par exemple en déterminant l'inverse v-1 de la constante v et en multipliant (K*-r) par v-1 (au sens de la multiplication modulaire de module 21 où I est la longueur de la clé 25 cryptographique K). L'entité électronique 1 comprend un quatrième module 16 conçu pour recevoir la donnée x sur l'interface de communication 8 et fournir cette donnée x au cinquième module 18 et au sixième module 20 décrits ci-après. L'entité électronique 1 comprend en effet un cinquième module 18 conçu 30 pour obtenir un premier nombre Ni, ici égal à xcl(vm, par exponentiation modulaire de la donnée x à un premier exposant égal au produit du quotient q par la constante v modifiée en fonction du reste r. Précisément ici, comme déjà indiqué, le premier exposant est égal au produit du quotient q par la constante v modifiée par soustraction du reste r (c'est-à-dire au produit du quotient q par la constante v 7 diminuée du reste r). On rappelle que le quotient q et le reste r sont produits par le troisième module 14 mentionné plus haut. On remarque que l'on pourrait utiliser en variante une autre valeur de premier exposant égal au produit du quotient q par la constante v modifiée du 5 reste r, par exemple un premier exposant égal à q(v+r). L'entité électronique 1 comprend aussi un sixième module 20 conçu pour obtenir un second nombre N2, ici égal à eq+1), par exponentiation modulaire de la donnée x à un second exposant déterminé en fonction du quotient q et du reste r. Précisément ici, comme déjà indiqué, le second exposant est égal au produit du 10 quotient incrémenté de 1 (soit q+1) et du reste r. Comme représenté en pointillés sur la figure 2, le sixième module 20 peut éventuellement utiliser un résultat partiel fourni par le cinquième module 18 (comme expliqué ci-dessous à propos de la variable x1 déterminée à l'étape E14 et utilisée à l'étape E18). 15 Comme pour le premier exposant, on pourrait utiliser en variante une autre valeur de second exposant déterminé en fonction du quotient q et du reste r. Dans la variante mentionnée ci-dessus où le premier exposant est égal à q(v+r), le second exposant déterminé en fonction du quotient q et du reste peut valoir par exemple r(1-q). 20 Enfin, l'entité électronique 1 comprend un septième module 22 conçu pour effectuer une multiplication modulaire du premier nombre Ni et du second nombre N2 afin d'obtenir le résultat y recherché. En effet, x étant premier avec N : Ni N2 mod N = xci(v4) x*I+1) mod N = xgv+I- mod N = XK* mod N = xk mod N. On remarque que, comme indiqué ci-dessus, les multiplications 25 modulaires et les exponentiations modulaires mentionnées ci-dessus sont des multiplications modulo le nombre prédéterminé N déjà mentionné. La figure 3 représente, sous forme de logigramme, un exemple de procédé conforme à l'invention. Ce procédé est ici mis en oeuvre au sein de l'entité électronique 1, dans 30 le cadre de l'architecture fonctionnelle décrite ci-dessus. L'invention n'est toutefois pas limitée à une mise en oeuvre dans une telle entité électronique. Le procédé décrit ci-dessous est un procédé de traitement cryptographique de la donnée x, par exemple un procédé cryptographique de déchiffrement de la donnée x au moyen de la clé cryptographique (communément 8 désignée dans ce cas clé privée) K, ou un procédé cryptographique de signature de la donnée x au moyen de la clé cryptographique (communément désignée dans ce cas clé privée) K. Le procédé de la figure 3 débute à l'étape E2 par la réception de la 5 donnée x par le processeur 2 via l'interface de communication 8. Le processeur 2 détermine alors un nombre VAL, ici par tirage aléatoire (étape E4). Le processeur 2 peut ainsi déterminer à l'étape E6 un multiple M (ici aléatoire) de l'indicatrice d'Euler yo(N) en multipliant l'indicatrice d'Euler 10 (mémorisée ici dans la mémoire non-volatile réinscriptible 6 comme déjà indiqué ou en variante calculée au sein de l'étape E6) par le nombre VAL déterminé à l'étape E4: M = VAL (p(N). Dans le mode de réalisation de la figure 2, les étapes E4 et E6 sont mises en oeuvre par le premier module 10. 15 Le processeur 2 procède alors à l'étape E8 au masquage de la clé cryptographique K (mémorisée dans la mémoire non-volatile réinscriptible) en additionnant le multiple M déterminé à l'étape E6 et la clé cryptographique K, ce qui permet d'obtenir la clé masquée K*: K* = K + M. Dans le mode de réalisation de la figure 2, l'étape E8 est mise en oeuvre 20 par le second module 12. Le processeur 2 peut ainsi déterminer à l'étape E10 le reste r de la division entière de la clé masquée K* par la constante v, puis, à l'étape E12, le quotient q de la division entière de la clé masquée K* par la constante v. Dans le mode de réalisation de la figure 2, ces étapes E10 et E12 sont mises en oeuvre 25 par le troisième module 14. Le processeur 2 va alors procéder au calcul d'exponentiation modulaire (de module prédéterminé N) souhaité comme suit. Le processeur 2 effectue tout d'abord à l'étape E14 l'exponentiation modulaire de la donnée x en utilisant le quotient q (déterminé à l'étape E12) en 30 tant qu'exposant et mémorise (par exemple dans la mémoire vive 4) le résultat de cette exponentiation modulaire dans une variable x1 : x1 = xq mod N. On remarque que la valeur de la clé masquée K* est différente à chaque mise en oeuvre du procédé (grâce à l'utilisation du nombre aléatoire VAL) et que la valeur du quotient q (utilisé en tant qu'exposant) est donc elle aussi différente à 9 chaque mise en oeuvre du procédé. Ainsi, le contenu de la variable x1 (puis de la variable x2 mentionnée ci-dessous) est différent à chaque mise en oeuvre des étapes décrites ci-dessous. Le processeur 2 effectue ensuite à l'étape E16 l'exponentiation 5 modulaire de la variable x1 (déterminée à l'étape E14) en utilisant un exposant égal à la différence entre la constante v et le reste r, et mémorise le résultat de cette exponentiation modulaire dans une variable x2: x2 = x1v4 mod N. Dans le mode de réalisation de la figure 2, les étapes E14 et E16 sont mises en oeuvre par le cinquième module 18 et la valeur de la variable x2 (après 10 l'étape E16) correspond au premier nombre Ni produit par le cinquième module 18. (On a en effet : = mod N = q(vm mod N = N1.) Le processeur 2 effectue alors à l'étape E18 la multiplication modulaire du contenu de la variable x1 par la donnée x et mémorise le résultat (qui vaut donc mod N) dans la variable x1 (avec écrasement). 15 Le processeur 2 effectue à l'étape E20 l'exponentiation modulaire de la variable x1 à un exposant égal au reste r et mémorise le résultat dans la variable x1 (avec écrasement). En sortie de l'étape E20, la variable x1 vaut donc : eq+1) mod N. Dans le mode de réalisation de la figure 2, les étapes E18 et E20 sont 20 mises en oeuvre par le sixième module 20 et la valeur de la variable x1 (après l'étape E20) correspond au second nombre N2 produit par le sixième module 20. Le processeur 2 peut ainsi procéder à l'étape E22 à la multiplication modulaire de la variable x1 et de la variable x2, ce qui permet d'obtenir le résultat recherché y. En effet, comme déjà indiqué (x étant premier avec N) : 25 y = x1 x2 mod N = eq+1). >ce-1-) mod N = xclv+t- mod N = mod N = x1 REVENDICATIONS1. Procédé de traitement cryptographique d'une donnée (x) par exponentiation modulaire de module prédéterminé (N), comprenant les étapes suivantes : - masquage (E8) d'une clé cryptographique (K) par addition, à la clé cryptographique (K), d'un multiple (M) de l'indicatrice d'Euler ()(N)) associée au module prédéterminé (N) ; - détermination (E10, E12) du quotient (q) et du reste (r) de la division entière de la clé cryptographique masquée (K*) par une constante (v) ; - obtention (E14, E16) d'un premier nombre (Ni) par exponentiation modulaire de la donnée (x) à un premier exposant égal au produit du quotient (q) par la constante (v) modifiée en fonction du reste (r) ; - obtention (E14, E18, E20) d'un second nombre (N2) par exponentiation 15 modulaire de la donnée (x) à un second exposant déterminé en fonction du quotient (q) et du reste (r) ; - multiplication modulaire (E22) du premier nombre (Ni) et du second nombre (N2). 20 2. Procédé selon la revendication 1, dans lequel ledit multiple (M) de l'indicatrice d'Euler (cp(N)) est déterminé par multiplication de l'indicatrice d'Euler (9(N)) par un nombre aléatoire (VAL). 3. Procédé selon la revendication 1 ou 2, dans lequel le premier 25 exposant est égal au produit du quotient (q) par la constante (v) diminuée du reste (r). 4. Procédé selon l'une des revendications 1 à 3, dans lequel le second exposant est égal au produit du quotient (q) incrémenté de un et du reste (r). 30 5. Procédé selon l'une des revendications 1 à 4, dans lequel ladite constante (v) est une puissance entière de deux diminuée de un ou incrémentée de un. 11 6. Programme d'ordinateur comprenant des instructions exécutables par un processeur (2) conçues pour mettre en oeuvre un procédé selon l'une des revendications 1 à 5 lorsque ces instructions sont exécutées par le processeur (2). 5 7. Dispositif (1) de traitement cryptographique d'une donnée (x) par exponentiation modulaire de module prédéterminé (N), comprenant : - un module (12) de masquage d'une clé cryptographique (K) par addition, à la clé cryptographique (K), d'un multiple (M) de l'indicatrice d'Euler ((p(N)) associée au module prédéterminé (N) ; 10 - un module (14) de détermination du quotient (q) et du reste (r) de la division entière de la clé cryptographique masquée (K*) par une constante (v) ; - un module (18) d'obtention d'un premier nombre (Ni) par exponentiation modulaire de la donnée (x) à un premier exposant égal au produit du quotient (q) par la constante (v) modifiée en fonction du reste (r) ; - un module (20) d'obtention d'un second nombre (N2) par exponentiation modulaire de la donnée (x) à un second exposant déterminé en fonction du quotient (q) et du reste (r) ; - un module (22) de multiplication modulaire du premier nombre (Ni) et du second nombre (N2). 8. Dispositif selon la revendication 7, comprenant un module (10) de détermination du multiple (M) de l'indicatrice d'Euler ()(N)) par multiplication de l'indicatrice d'Euler ()(N)) par un nombre aléatoire (VAL). 9. Dispositif selon la revendication 7 ou 8, dans lequel le premier exposant est égal au produit du quotient (q) par la constante (v) diminuée du reste (r). 10. Dispositif selon l'une des revendications 7 à 9, dans lequel le second exposant est égal au produit du quotient (q) incrémenté de un et du reste (r). 11. Dispositif selon l'une des revendications 7 à 10, dans lequel ladite constante (v) est une puissance entière de deux diminuée de un ou incrémentée de un.