Brevet FR2997780A1 — publié le 20140509

PROCEDE DE CRYPTOGRAPHIE COMPRENANT UNE OPERATION D'EXPONENTIATION MODULAIRE La présente invention concerne un procédé de calcul itératif du résultat de l'exponentiation d'une donnée m par un exposant d, mis en oeuvre dans un dispositif électronique. Divers procédés de cryptographie connus reposent sur l'opération d'exponentiation modulaire, qui a pour expression mathématique : Md modulo(n), m étant une donnée d'entrée, d un exposant et n un module. La fonction d'exponentiation modulaire consiste à calculer le reste de la division par n de m à la puissance d. io Une telle fonction est utilisée par divers algorithmes de cryptographie tels que l'algorithme RSA (Rivest, Shamir et Adleman), l'algorithme DSA ("Digital Signature Algorithm"), El Gamal, etc. La donnée m est généralement un message à chiffrer ou déchiffrer ou bien un message à signer ou une signature à vérifier, et l'exposant d est une clé privée ou publique. 15 Il est connu d'exécuter un calcul d'exponentiation modulaire au moyen de l'algorithme "Square & Multiply" ("élever au carré et multiplier") Al ou Ai' figurant en Annexe I. L'algorithme Al est dit "de gauche à droite" car les premières étapes de la boucle de calcul commencent par les bits de poids fort de l'exposant, 20 pour aller vers les bits de poids faible. L'algorithme Ai' est dit "de droite à gauche" car les premières étapes de la boucle de calcul commencent par les bits de poids faible de l'exposant, pour aller vers les bits de poids fort. Ces algorithmes comprennent pour chaque itération, c'est-à-dire chaque bit de l'exposant, une multiplication de deux variables identiques de 25 grande taille et si le bit de l'exposant traité par l'itération est égal à 1, une multiplication de deux variables différentes de grande taille. Il est généralement fait appel à des fonctions différentes pour exécuter chacune de ces opérations, la multiplication de deux variables identiques de grande taille étant exécutée au moyen d'une fonction d'élévation au carré ou fonction 30 "CARRE", tandis que la multiplication de deux variables différentes de grande taille est exécutée au moyen d'une fonction de multiplication ou fonction "MULT". Cette distinction est due au fait qu'il est possible de calculer plus rapidement xxy lorsque x=y que dans le cas contraire, au moyen de la fonction CARRE. Le ratio entre le temps d'exécution de la fonction CARRE et le temps d'exécution de la fonction MULT est généralement de l'ordre de 0,8 mais peut varier entre 0,5 et 1 suivant la taille des nombres considérés, la façon dont la multiplication est exécutée, etc. Dans un dispositif électronique de type carte à puce, le calcul cryptographique est généralement exécuté par un processeur spécifique, tel un coprocesseur arithmétique ou un crypto-processeur. Le calcul de "Md modulo n", et plus particulièrement l'exécution des multiplications de nombres de grande taille, occupe la majeure partie du temps de calcul du processeur relativement au temps total de calcul d'une signature, de vérification de signature, ou d'une opération de chiffrement ou de déchiffrement. Le fait d'utiliser alternativement la fonction CARRE ou la fonction MULT en fonction du type de calcul à effectuer permet donc d'optimiser le temps de calcul global de chiffrement, de déchiffrement, de signature ou de vérification de signature. Toutefois, l'utilisation de deux fonctions différentes CARRE et MULT conduit à une fuite d'information détectable par analyse SPA ("Simple Power Analysis"), c'est-à-dire par analyse de la consommation électrique de la carte. La fonction CARRE ayant un temps d'exécution plus court que la fonction MULT, il est possible de différencier ces deux opérations en observant la courbe de consommation électrique du composant. On entend par "consommation électrique" toute grandeur physique observable trahissant le fonctionnement du composant électronique exécutant l'opération, notamment le courant électrique consommé ou le rayonnement électromagnétique du composant. La figure 1 représente une courbe de consommation électrique d'un composant exécutant l'algorithme Al. On distingue clairement le profil de consommation de la fonction CARRE et celui de la fonction MULT. Une opération CARRE suivie d'une opération MULT (étape 2.1 suivie d'une étape 2.2) révèle que le bit de l'exposant d est égal à 1 puisque le branchement conditionnel vers l'étape 2.2 nécessite que la condition ds=1 soit réalisée. Inversement, une opération CARRE suivie d'une autre opération CARRE (étape 2.1 suivie d'une autre étape 2.1) révèle que le bit de l'exposant est égal à O. Les bits de l'exposant d peuvent ainsi être découverts les uns après les autres par une simple observation de la courbe de consommation électrique. Pour pallier cet inconvénient, les étapes 2.1 et 2.2 des algorithmes Al et Ai' pourraient être effectuées au moyen de la fonction MULT uniquement, sans utiliser la fonction CARRE. Toutefois, une analyse plus fine de la consommation électrique permettrait de distinguer l'étape 2.1 de l'étape 2.2 car l'algorithme Al ou Ai' n'est pas régulier. En effet, dans ce cas, le temps s'écoulant entre deux multiplications successives n'est pas le même lorsque io les deux multiplications correspondent à l'exécution successive de deux étapes 2.1 (bit de l'exposant égal à 0) ou correspondent à l'exécution d'une étape 2.1 suivie d'une étape 2.2 (bit de l'exposant égal à 1). Un attaquant pourrait ainsi "zoomer" sur la partie de la courbe de consommation s'étendant entre les multiplications et observerait une dissymétrie temporelle 15 révélatrice du branchement conditionnel et donc de la valeur du bit de l'exposant. L'algorithme A2 figurant en Annexe I est une variante de l'algorithme Al qui permet de pallier cet inconvénient. L'algorithme A2 est appelé "Square & Multiply Always" ("toujours élever au carré et multiplier") car une 20 multiplication factice (étape 2.3) utilisant un paramètre factice b est insérée après une élévation au carré lorsque le bit de l'exposant d est égal à 0, grâce à un double branchement conditionnel "si" et "sinon". La figure 2 montre la consommation électrique d'un composant exécutant l'algorithme A2. On constate une régularité des pics de 25 consommation correspondant à la succession des étapes 2.1 et 2.2, qui protège l'algorithme contre une attaque SPA. On suppose donc que le double branchement conditionnel "si" et "sinon" ne produit pas de fuite détectable par analyse SPA, car on ne peut pas distinguer si la condition est vraie ou fausse, puisqu'une multiplication est toujours exécutée. L'algorithme 30 A2 est dit "régulier" puisque l'attaquant voit une succession d'étapes identiques. Il ne répond toutefois pas au principe d'atomicité. Le principe d'atomicité a été introduit par B. Chevallier-Mames, M. Ciet et M. Joye, dans un article intitulé "Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity', paru dans IEEE 35 Transactions on Computers, Volume 53, Issue 6 (June 2004), Pages: 760 - 768, 2004. Il est également décrit dans la demande internationale WO 03 083 645 ou le brevet US 7 742 595. L'application du principe d'atomicité conduit à transformer une boucle non régulière, par exemple la boucle constituée par les étapes 2.1 et 2.2 de l'algorithme Al ou Ai', en une suite régulière de multiplications, sans utiliser de multiplication factice, pour un gain de temps dans l'exécution de l'algorithme. A titre d'exemple, l'algorithme d'exponentiation A3 figurant en Annexe I, appelé "Multiply Always", est la version atomique de l'algorithme Al. L'algorithme est parfaitement régulier en ce qu'il ne comporte que des multiplications et en ce que chaque itération de la boucle principale ne comprend qu'une seule multiplication. La figure 3 représente la courbe de consommation électrique de l'algorithme A3 et montre la régularité des pics de consommation électrique. Dans cet algorithme, certaines multiplications sont des multiplications de variables différentes et d'autres sont des multiplications de variables identiques. Or, dans l'article "Distinguishing Multiplications from Squaring Operations", Selected Areas in Cryptography, volume 5381 of Lecture Notes in Computer Science, pages 346-360, Springer, 2008, les auteurs F. Amiel, B. Feix, M. Tunstall, C. Whelan, et W. Marnane divulguent un procédé d'analyse à canal caché qui exploite une différence intrinsèque entre la multiplication de deux variables différentes et la multiplication de deux variables identiques (équivalente à une élévation au carré), le résultat de la seconde ayant en moyenne un poids de Hamming inférieur au résultat de la première. L'algorithme A3 est donc exposé à ce type d'attaque, car il contient des multiplications de termes différents et des multiplications de termes égaux. L'algorithme A2 "Square & Multiply Always" n'est pas sensible à ce type d'attaque car les multiplications exécutées à l'étape 2.2 sont toutes des multiplications de variables différentes, et l'étape 2.1 est exécutée avec la fonction CARRE. Il présente toutefois l'inconvénient d'un temps d'exécution non optimisé en raison de l'exécution de multiplications factices. De plus, il existe une classe d'attaques dite "safe errors" qui permettent de détecter les opérations factices qu'un algorithme comporte. Ces attaques consistent à injecter une faute dans un calcul cryptographique à un instant particulier, et à observer si le résultat du calcul est juste ou faux. Ce type d'attaque appliqué à l'algorithme A2 permet de savoir si une multiplication est faite après un "si" ou après un "sinon". En effet, dans le second cas, le résultat de la multiplication factice n'est pas utilisé pour le calcul du résultat final. Une injection d'erreur dans une boucle dans laquelle le branchement conditionnel "sinon" est actif n'affecte donc pas le résultat et permet de savoir que le branchement conditionnel "sinon" a été retenu et non le branchement "si". L'algorithme A4 figurant en Annexe I, appelé "Montgomery Ladder", permet également de réaliser un calcul d'exponentiation modulaire. Cet io algorithme consiste à chaque itération à effectuer deux multiplications, l'une appliquée à deux nombres différents, et l'autre appliquée à deux nombres identiques et pouvant donc être effectuée par une multiplication ou une élévation au carré. A chaque itération, l'un des deux registres Ro, R1 reçoit le produit du contenu des deux registres, et le contenu de l'autre des deux 15 registres est élevé au carré. Si le bit ds correspondant à l'itération en cours, de l'exposant d est à 0, le registre R1 reçoit le résultat de la multiplication, et le registre Ro est élevé au carré, et inversement si le bit ds est à 1. Cet algorithme présente l'avantage d'être parfaitement régulier en ce que chaque itération comporte systématiquement deux multiplications, ou 20 une multiplication et une élévation au carré. Cet algorithme est également optimisé en terme de temps de calcul dans la mesure où il ne comporte pas d'opération factice. Cet algorithme présente également l'avantage d'être parallélisable moyennant l'utilisation d'un registre supplémentaire. L'algorithme A4' figurant en Annexe I est une variante parallélisée de 25 l'algorithme A4. L'algorithme A4' utilise un registre supplémentaire R2 (cf. étape 2.2 de l'algorithme A4' en Annexe I) pour ne pas écraser l'opérande Ro ou R1 de la multiplication, lors de l'opération d'élévation au carré. Les figures 4A et 4B représentent des courbes de consommation électrique d'un composant exécutant l'algorithme A4'. Ces courbes de 30 consommation montrent une régularité dans la succession des pics de consommation électrique, que la seconde multiplication soit réalisée par la fonction MULT (figure 4A) ou la fonction CARRE (figure 4B). La demande EP 2 492 804 (U52012/0221618) déposée par le Demandeur propose de remplacer dans les algorithmes Al, Ai' ou A2, les opérations de multiplication par des opérations d'élévation au carré en utilisant l'une ou l'autre des formules suivantes : (i) xxy = [(x+y)x(x+y) - xxx - yxy]i2 (ii) xxy = [(x+y)/2]x[(x+y)/2] - [(x-y)/2]x[(x-y)/2] L'algorithme A5 figurant en Annexe I présente un exemple de calcul d'exponentiation modulaire mettant en oeuvre la formule (ii), de gauche à droite. Le fonctionnement de cet algorithme peut être compris en se référant à l'algorithme classique Al décrit plus haut. Deux cas peuvent se produire : 1) Le bit d, de l'exposant vaut O: - l'algorithme calcule R0=R0xR0 (étape 3.1), ce qui correspond à l'étape 2.1 de l'algorithme Ai, 2) le bit d, vaut 1, l'algorithme effectue trois itérations de la boucle "tant que" : - Ro = R0xR0 (étape 3.1), ce qui correspond à l'étape 2.1 de l'algorithme Ai) - R2 = ((R0-FM)/2)X((R0-FM)/2) (étapes 3.3, 3.4, puis 3.1) - Ro = ((R0-m)/2)x((R0-m)/2) et Ro = R2-R0 (étapes 3.2, 3.4, puis 3.1), ce qui correspond à l'étape 2.2 de l'algorithme Al mise en oeuvre avec la formule (ii)). Le profil de consommation électrique d'un composant exécutant l'algorithme A5 se présente sous la forme d'une succession de pics correspondant à des appels à la fonction MULT (ou CARRE). Une telle courbe de consommation ne permet pas de déduire la valeur des bits de l'exposant secret et est donc protégée d'une attaque SPA. D'autre part, l'attaque consistant à distinguer une multiplication de deux variables différentes d'une multiplication de deux variables identiques n'est pas applicable puisque le procédé ne comporte que des multiplications de termes égaux. Le temps d'exécution par itération (par bit de l'exposant d) de l'algorithme A5 peut être évalué à 2 fois le temps de calcul d'une élévation au carré, soit 1,6 fois le temps de calcul d'une multiplication,. Une variante parallélisable peut être dérivée de l'algorithme A5. Ainsi, l'algorithme A5' figurant en Annexe I présente un autre exemple de calcul d'exponentiation modulaire mettant en oeuvre la formule (ii), de droite à gauche, sous une forme atomique, parallélisée. Le profil de consommation électrique d'un composant exécutant l'algorithme A5' se présente sous la forme d'une double succession de pics correspondant à des appels à la fonction MULT (ou CARRE). Une telle succession ne permet pas de déterminer les bits de l'exposant d. Le temps d'exécution de cet algorithme dépend du nombre de registres mis en oeuvre, et tend vers le temps de calcul d'un carré par bit de l'exposant d, au prix de l'utilisation d'un très grand nombre L de registres de la taille de la donnée m à élever à la puissance d. Il pourrait donc être souhaité de réduire le temps de calcul et la taille io de mémoire utilisée par un procédé d'exécution d'un calcul d'exponentiation appliqué à une donnée de grande taille. Il pourrait être également souhaité de protéger un tel procédé contre les attaques à canal caché mentionnées précédemment, en pénalisant le moins possible le temps de calcul. Des modes de réalisation concernent un procédé de calcul itératif 15 d'exponentiation d'une donnée de grande taille par un exposant formé d'un certain nombre de bits, le procédé étant mis en oeuvre dans un dispositif électronique et comprenant un calcul d'élévation au carré d'une variable de grande taille pour chaque bit de l'exposant, et des calculs de multiplication de variables de grande taille pour traiter des bits à un de l'exposant. Selon un 20 mode de réalisation, les calculs d'élévation au carré et de multiplication de variables de grande taille sont effectués en parallèle, par des blocs d'élévation au carré et de multiplication appartenant au dispositif électronique, le procédé comprenant, des étapes consistant à: tant qu'une mémoire tampon de stockage temporaire de résultats fournis par le bloc 25 d'élévation au carré n'est pas pleine de résultats non utilisés par le bloc de multiplication, déclencher un calcul par le bloc d'élévation au carré pour un bit de l'exposant, lorsque le bloc d'élévation au carré est inactif, stocker chaque résultat fourni par le bloc d'élévation au carré dans la mémoire tampon, si le bit de l'exposant correspondant est à 1, et tant que la mémoire 30 tampon contient un résultat d'élévation au carré non utilisé par le bloc de multiplication, déclencher un calcul par le bloc de multiplication portant sur le résultat d'élévation au carré non utilisé, lorsque le bloc de multiplication est inactif. Selon un mode de réalisation, le procédé comprend un 35 déclenchement de calcul factice par le bloc d'élévation au carré, si la mémoire tampon est pleine, si le bit correspondant de l'exposant est à 1, et si le bloc d'élévation au carré est inactif. Selon un mode de réalisation, le procédé comprend un déclenchement de calcul factice par le bloc de multiplication si la mémoire tampon est vide, et si le bloc de multiplication est inactif. Selon un mode de réalisation, tous les résultats fournis par les blocs d'élévation au carré et de multiplication sont utilisés pour l'obtention du résultat de l'exponentiation. Selon un mode de réalisation, plusieurs résultats fournis par le bloc io d'élévation au carré, sont stockés dans la mémoire tampon. Selon un mode de réalisation, la mémoire tampon est gérée de manière cyclique, avec un indice d'écriture, un indice de lecture et un compteur de résultats non utilisés. Selon un mode de réalisation, la mémoire tampon est configurée pour 15 stocker trois à cinq résultats fournis par le bloc d'élévation au carré. Selon un mode de réalisation, les calculs réalisés par les blocs d'élévation au carré et de multiplication sont des opérations modulaires. Selon un mode de réalisation, plusieurs bits de l'exposant sont traités à chaque itération. 20 Des modes de réalisation concernent également un dispositif électronique comprenant un processeur configuré pour calculer une exponentiation d'une donnée de grande taille par un exposant, un bloc de calcul d'élévation au carré d'une variable de grande taille, et un bloc de calcul de multiplication de variables de grande taille. Selon un mode de 25 réalisation, le dispositif comprend une mémoire tampon pouvant stocker plusieurs résultats fournis par le bloc d'élévation au carré, le dispositif étant configuré pour mettre en oeuvre le procédé tel que précédemment défini. Selon un mode de réalisation, la mémoire tampon est configurée pour stocker trois à cinq résultats fournis par le bloc d'élévation au carré. 30 Selon un mode de réalisation, les blocs d'élévation au carré et de multiplication comprennent chacun un coprocesseur de type à unité centrale programmable, ou un coprocesseur entièrement hardware de type machine d'état, ou bien sont réalisés chacun par une tache exécutée de manière indépendante d'un programme principal, les taches et le programme principal 35 étant exécutés par le processeur de type multi-coeur. Des exemples de réalisation de l'invention seront décrits dans ce qui suit, à titre non limitatif en relation avec les figures jointes parmi lesquelles : la figure 1 précédemment décrite représente la courbe de consommation électrique d'un composant exécutant un premier algorithme d'exponentiation classique, la figure 2 précédemment décrite représente la courbe de consommation électrique d'un composant exécutant un second algorithme d'exponentiation classique, io la figure 3 précédemment décrite représente la courbe de consommation électrique d'un composant exécutant un troisième algorithme d'exponentiation classique, les figures 4A, 4B représentent des courbes de consommation électrique d'un composant exécutant deux variantes d'un algorithme 15 d'exponentiation classique, la figure 5 représente un dispositif électronique mettant en oeuvre un algorithme d'exponentiation selon un mode de réalisation, les figures 6 et 7 représentent des courbes de consommation électrique du dispositif électronique exécutant deux modes de réalisation 20 d'un algorithme d'exponentiation, la figure 8 représente un dispositif électronique mettant en oeuvre un algorithme d'exponentiation selon un autre mode de réalisation. L'invention concerne un procédé de calcul cryptographique comportant des multiplications de variables identiques de grande taille et des 25 multiplications de variables différentes de grande taille. Il est mis en oeuvre par un dispositif électronique configuré pour exécuter des calculs cryptographiques, incluant des exponentiations. Le procédé peut être un calcul d'exponentiation RSA, DSA, El Gamal, etc. Selon un mode de réalisation, ce procédé se base sur une dérivation 30 de l'algorithme Al ', dans lequel les calculs d'élévation au carré sont effectués en utilisant une multiplication optimisée tenant compte de l'égalité des opérandes, et dans lequel les calculs de multiplication et d'élévation au carré effectués à chaque itération sont réalisés en parallèle d'une manière asynchrone. Ainsi, un nouveau calcul d'élévation au carré peut être 35 déclenché dès qu'un précédent calcul d'élévation au carré s'est terminé, sans attendre qu'une multiplication éventuellement en cours de calcul soit terminée. De même, un nouveau calcul de multiplication peut être déclenché dès qu'un précédent calcul de multiplication s'est terminé, sans attendre qu'une élévation au carré éventuellement en cours de calcul soit terminée. De cette manière, le résultat d'une élévation au carré ou d'une multiplication peut être exploité dès qu'il est disponible. L'algorithme A6 figurant en Annexe II est un exemple d'algorithme d'exponentiation, de droite à gauche, selon un mode de réalisation. Dans l'algorithme A6 et dans les algorithmes décrits plus loin : M(a,b) désigne une fonction de calcul asynchrone du produit de nombres a et b de grande taille, S(a) désigne une fonction de calcul asynchrone du carré du nombre a de grande taille, FinM() désigne une fonction fournissant un indicateur à FAUX tant qu'un calcul de produit est en cours (fonction M active) et qui passe à VRAI dès qu'un produit est disponible (fonction M inactive), et FinS() désigne une fonction fournissant un indicateur à FAUX tant qu'un calcul d'élévation au carré est en cours (fonction S active) et qui passe à VRAI dès qu'un carré est disponible. L'algorithme A6 utilise un ensemble de L registres R de la taille de la donnée m à élever à la puissance d. Cet ensemble peut avantageusement être géré comme une mémoire tampon de type FIFO (First In - First Out) cyclique (étapes 3.1.1.1.2 et 3.2.1.2). A cet effet, un compteur k mémorise le nombre de carrés chargés dans les registres R, non utilisés par les multiplications. Un indice d'écriture j définit le registre R dans lequel le résultat de l'élévation au carré suivante doit être chargé, et un indice de lecture i définit le registre R où se trouve l'opérande de la multiplication suivante. Dans cet algorithme, l'étape 3 est un contrôle de boucle sur le nombre v de bits de l'exposant d. Les étapes 3.1.x sont exécutées lorsqu'un calcul d'élévation au carré s'est terminé (FinS = VRAI - étape 3.1), et lorsque la mémoire tampon formée par les registres n'est pas pleine (ic#L) et qu'un carré doit être chargé dans un registre R (ds = 1 - étape 3.1.1.1). Un calcul d'élévation au carré (étape 3.1.1.2) est effectué pour chaque bit ds de l'exposant d, mais seuls les résultats des élévations au carré sont chargés dans l'un des registres R (étape 3.1.1.1.1) lorsque le bit ds de l'exposant en cours de traitement est égal à 1. Les étapes 3.2.1.x sont exécutées lorsqu'un calcul de produit s'est terminé (FinM = VRAI - étape 3.2) et lorsque la mémoire tampon n'est pas vide (k#0 - étape 3.2.1). Un calcul de produit (étapes 3.2.1.1 et 4.1.1) est effectué pour chaque calcul d'élévation au carré chargé dans un registre R. Les étapes 4.x permettent d'effectuer les multiplications restantes une fois que toutes les élévations au carré nécessaires ont été effectuées. Les étapes 5.x forment une boucle d'attente de la fin du dernier calcul de multiplication ou d'élévation au carré, le dernier calcul de multiplication fournissant le résultat du calcul d'exponentiation. io Le temps d'exécution par itération de cet algorithme dépend du nombre L de registres R utilisés. Plus ce nombre est grand, plus la probabilité que tous les registres R soient pleins durant l'exécution de l'algorithme est faible, et donc plus la probabilité qu'un calcul d'élévation au carré soit retardé est faible. A partir de L=3, le temps d'exécution par itération 15 de cet algorithme atteint sensiblement une valeur minimum égale au temps de calcul d'une élévation au carré, soit environ 0,8 fois le temps de calcul d'une multiplication. L'algorithme A6 permet donc d'atteindre les performances de l'algorithme A5' avec beaucoup moins de registres de la taille de la donnée m à élever à la puissance d. 20 La figure 5 représente sous forme de schéma bloc un dispositif électronique DV1 configuré pour exécuter un calcul cryptographique incluant l'algorithme A6. Le dispositif DV1 peut être un circuit intégré sur microplaquette de semi-conducteur agencé sur un support portatif comme une carte en matière plastique, l'ensemble formant une carte à puce. Le 25 dispositif DV1 peut également être n'importe quel appareil équipé d'un processeur multi-tâche, tel qu'un téléphone mobile intelligent ("smartphone"), un lecteur multimédia, une tablette tactile, ou un ordinateur personnel. Le dispositif DV1 peut également être un composant d'un tel appareil, par exemple relié à un processeur principal de l'appareil. 30 Le dispositif DV1 comprend un processeur FROC, un bloc de calcul MB1 configuré pour exécuter la fonction M(a,b) de multiplication de variables a, b, de grande taille un bloc de calcul SB1 configuré pour exécuter la fonction S(a) d'élévation au carré d'une variable a de grande taille, une mémoire MEM et un circuit d'interface de communication IC. Le circuit 35 d'interface IC peut être du type à contact ou sans contact, par exemple un 2 99 7780 12 circuit d'interface RF ou UHF fonctionnant par couplage inductif ou par couplage électrique. Les blocs de calcul MB1, SB1 peuvent comprendre chacun un coprocesseur équipé d'une unité centrale programmable, un coprocesseur entièrement hardware de type machine d'état, ou une tache ou 5 fil d'exécution (thread) exécuté de manière indépendante d'un programme principal, notamment par un processeur multi-coeur. Les deux blocs de calcul MB1, SB1 peuvent être intégrés dans un même composant (coprocesseur ou machine d'état) s'ils peuvent fonctionner indépendamment l'un de l'autre. De façon en soi classique, une variable est dite "de grande taille" io lorsque sa taille (en nombre de bits) est supérieure à celle des registres de calcul du processeur FROC. Ce dernier effectue lui-même, sans faire appel aux blocs de calcul MB1, SB1, des multiplications de variables de petite taille, c'est-à-dire de taille inférieure ou égale à celle de ses registres de calcul, et fait appel aux blocs de calcul MB1, SB1 pour les multiplications et 15 les élévations au carré de variables de grande taille, c'est-à-dire supérieure à la taille de ses registres de calcul. Par exemple, si la taille des registres de calcul du processeur FROC est de 32 bits, une variable de grande taille est une variable de plus de 32 bits. En cryptographie, les variables manipulées peuvent atteindre plusieurs centaines ou plusieurs milliers de bits (512, 1024, 20 2048, 4096 bits). La mémoire MEM est couplée au processeur FROC et permet au dispositif DV1 de mémoriser une clé secrète d. Le processeur FROC reçoit, par l'intermédiaire du circuit d'interface IC, un message m à chiffrer ou à signer, et renvoie un message chiffré ou une signature du type Fd(m), F étant 25 une fonction de cryptographie basée sur la clé d comprenant un calcul d'exponentiation de type Md modulo(n) exécuté au moyen de l'algorithme A6. Pendant le calcul d'exponentiation, le processeur FROC fait appel aux blocs de calcul MB1, SB1, en fournissant des variables a, b au bloc de calcul MB1 qui retourne axb, et en fournissant une variable a au bloc de calcul SB1 qui 30 retourne a2. Le bloc MB1 fournit un signal EM dans un état par exemple actif lorsqu'un résultat de multiplication est disponible, et dans un état inactif lorsqu'il est en train de calculer un produit. De même, le bloc SB1 fournit un signal ES dans un état par exemple actif lorsqu'un carré est disponible, et dans un état inactif lorsqu'il est en train d'effectuer une élévation au carré. 35 Une partie de la mémoire MEM peut également être utilisée comme mémoire tampon pour mémoriser le contenu des registres R mentionnés dans l'algorithme A6. La figure 6 représente un profil de consommation électrique d'un composant tel que le dispositif DV1, exécutant l'algorithme A6. Ce profil de consommation se présente sous la forme d'une double succession de pics correspondant à l'activité respective des blocs SB1 et MB1, c'est-à-dire aux appels des fonctions M() et S(). Au début de l'exécution de l'algorithme A6, aucun appel de la fonction M() ne peut être effectué tant que la fonction S() n'a pas fourni de résultat mémorisé dans un registre R, c'est-à-dire pour un bit ds égal à 1 de l'exposant d. L'activité du bloc SB1 comprend des périodes Ti durant lesquelles le bloc est inactif. Ces périodes correspondent aux périodes durant lesquelles la mémoire tampon R[L] est pleine (de résultats d'élévation au carré non utilisées par une multiplication précédente) et qu'un résultat d'élévation au carré doit être chargé dans cette mémoire tampon (ds = 1 - condition de l'étape 3.1.1. non satisfaite). L'activité du bloc MB1 comprend également des périodes T2 durant lesquelles le bloc est inactif. Ces périodes correspondent aux périodes durant lesquelles la mémoire tampon R[L] est vide (ne contient aucun résultat d'élévation au carré non utilisé par une multiplication précédente). Une analyse de l'activité des blocs SB1, MB1 peut donc permettre de déterminer la valeur de l'exposant d. Par conséquent, l'algorithme A6 est vulnérable aux attaques SPA. Cependant, l'analyse de cette activité pour en déduire l'exposant d peut être rendue plus difficile en augmentant le nombre L de registres R. L'algorithme A7 figurant en Annexe Il est un autre exemple d'algorithme d'exponentiation, de droite à gauche, selon un mode de réalisation. Cet algorithme qui peut être mis en oeuvre dans le dispositif DV1, diffère de l'algorithme A6 en ce qu'il comporte des opérations factices permettant de neutraliser les attaques SPA. Ces opérations factices figurent aux étapes 3.1.2.1 et 3.2.2.1 où le résultat S(b) d'une élévation au carré factice et le résultat M(a,b) d'une multiplication factice sont chargés dans un registre x quelconque. Il en résulte que les profils de consommation électrique des blocs SB1, MB1 ne comportent plus de périodes d'inactivité Ti, T2. Ces profils ne permettent donc pas de déterminer les bits de l'exposant d. Cependant, ce résultat est obtenu au prix de l'ajout d'opérations factices et donc d'une augmentation du temps d'exécution de l'exponentiation. Ici encore, une augmentation du nombre L de registres R peut permettre de diminuer le nombre d'opérations factices à exécuter, en particulier le nombre d'élévations au carré factices. L'algorithme A8 figurant en Annexe II est une version atomisée, selon un mode de réalisation, de l'algorithme A7. Cet algorithme qui peut également être mis en oeuvre dans le dispositif DV1, diffère de l'algorithme A7 en ce que tous les branchements conditionnels ont été remplacés par une matrice binaire QL de 4(L+1) lignes et 3 colonnes (L étant le nombre de registres R), qui définit les opérations à réaliser à chaque itération. Par ailleurs, les étapes 4.x ont été intégrées dans la boucle formée par les étapes 3.x, le test de fin de boucle (étape 3) étant modifié de manière à inclure le cas traité par les étapes 4.x de l'algorithme A6 ou A7, c'est-à-dire lorsqu'une élévation au carré a été effectuée pour chacun des bits de l'exposant d et qu'il reste des carrés non utilisés par les multiplications dans les registres R. L'algorithme A8 calcule à l'étape 3.3 un indice de ligne g de lecture de la matrice QL en utilisant une fonction pos(x) qui retourne 1 si x>0 et sinon O. La valeur de l'indice de ligne g dépend du numéro s du bit ds en cours de traitement de l'exposant d, de la valeur de ce bit ds, du nombre k de carrés non utilisés dans les registres R, et du nombre L de registres R. Cet algorithme utilise également deux paires de registres a[O], a[1], b[O], b[1] en remplacement des registres a et b, les registres a[0] et b[0] étant prévus pour recevoir le résultat des calculs factices d'élévation au carré et de multiplication, et les registres a[1] et b[1] les résultats des calculs non factices. Il peut être noté que l'algorithme A8 continue à effectuer des élévations au carré une fois que tous les bits ds de l'exposant d ont été traités, tant qu'il reste des carrés non utilisés dans les registres R. Toutefois, ces élévations au carré supplémentaires ne pénalisent pas le temps global d'exécution du calcul d'exponentiation étant donné qu'elles sont réalisées en même temps que des multiplications nécessaires au calcul d'exponentiation. Le contenu de la matrice QL dépend du mode de calcul de l'indice de ligne g calculé à l'étape 3.3. Dans l'exemple du calcul de l'indice de ligne g effectué à l'étape 3.3 de l'algorithme A8, le contenu et la taille de la matrice QL dépend de la valeur du nombre L de registres R. L'Annexe III fournit les valeurs de la matrice QL pour L égal à 1, 2 et 3. La matrice 02 (L = 2) est construite à partir de la matrice 01 (L = 1) en ajoutant à cette dernière à la troisième ligne en partant des première et dernière lignes de la matrice, les deux blocs de deux lignes (0,1,1 / 1,1,1) et (0,0,1 / 0,0,1) indiqués en gras dans la matrice 02 fournie en Annexe III. La matrice 03 est construite à partir de la matrice 02 en dupliquant les blocs de deux lignes ajoutés dans la matrice 02, à la troisième ligne en partant de la première ligne et de la dernière ligne. Les lignes ainsi ajoutées sont indiquées en gras dans la matrice 03 fournie en Annexe III. De même, la matrice QL (L>1) est construite en ajoutant à la troisième ligne à partir des première et dernière io lignes de la matrice 01, respectivement (L-1) fois les deux blocs (0,1,1 / 1,1,1) et (0,0,1 / 0,0,1). D'autres formules de calcul de l'indice de ligne pour lire la matrice QL peuvent être aisément imaginées. Ainsi, si l'on initialise l'indice g (à l'étape 1) tel que g= 4*(1-ds)+ds+2 (= 6-3ds) , et que l'on choisit pour le calcul des 15 indices g suivants, la formule suivante : g = pos(v-s) * [4*(1-ds) + ds + 2*pos(L-k)] + pos(k) (1) on obtient la matrice référencée Q, fournie en Annexe IV. Il peut être noté que la matrice Q est indépendante du nombre L de registres R et présente une taille fixe de 8 lignes et 3 colonnes. 20 L'algorithme A9 figurant en Annexe II est une version dérivée de l'algorithme A6 avec application d'une fenêtre glissante de 2 bits sur l'exposant d, selon un mode de réalisation. En d'autres termes, l'algorithme A9 est obtenu en modifiant l'algorithme A6 de manière à traiter à chaque itération non pas un, mais deux bits consécutifs de l'exposant d. Plus 25 précisément, l'algorithme A9 réalise une seule multiplication par groupe de deux bits de l'exposant d comportant au moins un bit à 1, et réalise finalement une élévation au carré et deux multiplications. L'algorithme A9 peut être aisément modifié pour traiter les bits de l'exposant d par groupes de plus de deux bits. Dans ce cas, une seule multiplication sera effectuée par 30 groupe de bits comportant au moins un bit à un. Plusieurs élévations au carré et plusieurs multiplications seront nécessaires à la fin de l'algorithme pour déterminer le résultat. Il peut donc en résulter une réduction du nombre de multiplications de nombres de grande taille, au détriment de l'utilisation de p-1 registres supplémentaires de grande taille, p étant le nombre de bits par 35 groupe. Bien entendu, une version robuste aux attaques SPA de l'algorithme A9 peut être dérivée d'une manière analogue de l'un ou l'autre des algorithmes A7 et A8. Le résultat du calcul d'exponentiation fourni par le processeur FROC peut être modulaire ou non modulaire. Le dispositif DV1 représenté sur la figure 5 réalise des opérations d'exponentiation non modulaires. Les blocs MB1 et SB1 du dispositif DV1 réalisent des opérations d'élévation au carré et de multiplication non modulaires. Par ailleurs, il peut être noté que les algorithmes A6, A7, A8 ne nécessitent pas d'être modifiés pour obtenir un io résultat d'exponentiation modulaire ou non modulaire, seuls les blocs de calcul MB1 et SB1 devant être adaptés à cet effet. La figure 8 représente un dispositif DV2 réalisant des exponentiations modulaires. A cet effet, le dispositif DV2 diffère du dispositif DV1 en ce qu'il comprend des blocs de multiplication MB2 et d'élévation au carré SB2 15 réalisant des calculs modulaires. Les blocs MB2, SB2 comprennent une entrée supplémentaire pour recevoir le module n des calculs modulaires. Le processeur FROC est alors configuré pour fournir une valeur du module n aux blocs MB2, SB2. Le message m à élever à la puissance d est alors inférieur au module n. 20 Les temps d'exécution par bit de l'exposant d et le nombre de registres utilisés pour chacun des algorithmes précédemment présentés sont rassemblés dans le tableau 1 suivant : Tableau 1 Algorithme Sécurisé SPA Temps d'exécution par bit de l'exposant d Nombre de registres Ai, Ai' NON r-zz 1S + 0.5M = 1.30M 2 A2 OUI = 1S + 1M = 1.80M 2 A3 OUI r-zz 1.5M 2 A4 OUI r-zz 1M + 1S = 1,80M 2 A4' OUI r-zz 1M 3 A5 OUI r-zz 2S= 1.60M 3 A5' OUI r-zz 7/6S r-zz 0,93M 5 (L = 1) A5' OUI r-zz 15/14S r-zz 0,86M 7 (L = 3) A6 NON r-zz 0.80M 3 (L = 1) A7 OUI r-zz 0,84M 4 (L = 1) A7 OUI r-zz 0,80M 6 (L = 3) A8 OUI r-zz 0,84M 5 (L = 1) A8 OUI r-zz 0,80M 7 (L = 3) Il ressort du tableau 1 que seuls les algorithmes A5' à A8 atteignent un temps de calcul par bit de l'exposant, inférieur au temps de calcul M d'une multiplication de nombres de grande taille. Par ailleurs, les algorithmes A6, A7 et A8 permettent d'atteindre un temps de calcul sensiblement égal à celui d'une élévation au carré d'un nombre de grande taille (S =--.. 0,8M) par bit de l'exposant d, avec un nombre de registres notablement plus faible que l'algorithme A5'. Il apparaîtra clairement à l'homme de l'art que la présente invention est susceptible de diverses variantes de réalisation et diverses applications. io En particulier, des multiplications factices, notamment au démarrage d'un calcul d'exponentiation, peuvent être réalisées sans effectuer d'élévations au carré factices (suppression des étapes 3.1.2 et 3.1.2.1 dans l'algorithme A7). Inversement, des élévations au carré factices peuvent être réalisées sans effectuer de multiplications factices (suppression des étapes 3.2.2, et 3.2.2.1 15 dans l'algorithme A7). D'autres modes de gestion des registres R(L) peuvent être mis en oeuvre dans les algorithmes A6, A7 et A8. Par exemple ces registres peuvent être utilisés en prévoyant des étapes telles que 2.1.1.4, 2.1.2.3 et 2.2.2.1 de l'algorithme A5', pour décaler le contenu de ces registres. 20 ANNEXE I (Faisant partie intégrante de la description) Algorithme Al - Exponentiation "Square & Multiply", de gauche à droite" Entrée : un message m et un module n entiers tels que m Algorithme A4 - Montgomery Ladder (de gauche à droite) Entrée : un message m et un module n entiers tels que m REVENDICATIONS1. Procédé de calcul itératif d'exponentiation d'une donnée (m) de grande taille par un exposant (d) formé d'un certain nombre de bits (de), le procédé étant mis en oeuvre dans un dispositif électronique (DV1, DV2) et comprenant un calcul d'élévation au carré d'une variable de grande taille pour chaque bit de l'exposant, et des calculs de multiplication de variables de grande taille pour traiter des bits à un de l'exposant, caractérisé en ce que les calculs d'élévation au carré et de multiplication de variables de grande taille sont effectués en parallèle, par des blocs d'élévation au carré (SB1, 5B2) et de multiplication (SM1, 5M2) io appartenant au dispositif électronique, le procédé comprenant, des étapes consistant à: tant qu'une mémoire tampon (R) de stockage temporaire de résultats fournis par le bloc d'élévation au carré n'est pas pleine de résultats non utilisés par le bloc de multiplication, déclencher un calcul par le bloc 15 d'élévation au carré pour un bit de l'exposant, lorsque le bloc d'élévation au carré est inactif, stocker chaque résultat fourni par le bloc d'élévation au carré dans la mémoire tampon, si le bit de l'exposant correspondant est à 1, et tant que la mémoire tampon contient un résultat d'élévation au carré 20 non utilisé par le bloc de multiplication, déclencher un calcul par le bloc de multiplication portant sur le résultat d'élévation au carré non utilisé, lorsque le bloc de multiplication est inactif. 2. Procédé selon la revendication 1, comprenant un déclenchement 25 de calcul factice par le bloc d'élévation au carré (SB1, 5B2), si la mémoire tampon est pleine (R), si le bit (de) correspondant de l'exposant (d) est à 1, et si le bloc d'élévation au carré est inactif. 3. Procédé selon la revendication 1 ou 2, comprenant un 30 déclenchement de calcul factice par le bloc de multiplication (SM1, 5M2) si la mémoire tampon (R) est vide, et si le bloc de multiplication est inactif. 4. Procédé selon la revendication 1, dans lequel tous les résultats fournis par les blocs d'élévation au carré (SB1, SB2) et de multiplication (SM1, SM2) sont utilisés pour l'obtention du résultat de l'exponentiation. 5. Procédé selon l'une des revendications 1 à 4, dans lequel plusieurs résultats fournis par le bloc d'élévation au carré (SB1, SB2), sont stockés dans la mémoire tampon (R). 6. Procédé selon l'une des revendications 1 à 5, dans lequel la io mémoire tampon (R) est gérée de manière cyclique, avec un indice d'écriture (j), un indice de lecture (i) et un compteur (k) de résultats non utilisés. 7. Procédé selon l'une des revendications 1 à 6, dans lequel la mémoire tampon (R) est configurée pour stocker trois à cinq résultats fournis 15 par le bloc d'élévation au carré (SB1, SB2). 8. Procédé selon l'une des revendications 1 à 7, dans lequel les calculs réalisés par les blocs d'élévation au carré (SB2) et de multiplication (SM2) sont des opérations modulaires. 20 9. Procédé selon l'une des revendications 1 à 8, dans lequel plusieurs bits de l'exposant (d) sont traités à chaque itération. 10. Dispositif électronique (DV1, DV2) comprenant un processeur 25 (PROC) configuré pour calculer une exponentiation d'une donnée de grande taille (m) par un exposant (d), un bloc de calcul d'élévation au carré (SB1, SB2) d'une variable de grande taille, et un bloc de calcul de multiplication (SM1, SM2) de variables de grande taille, caractérisé en ce qu'il comprend une mémoire tampon (R) pouvant 30 stocker plusieurs résultats fournis par le bloc d'élévation au carré, le dispositif étant configuré pour mettre en oeuvre le procédé selon l'une des revendications 1 à 9. 11. Dispositif selon la revendication 10, dans lequel la mémoire tampon (R) est configurée pour stocker trois à cinq résultats fournis par le bloc d'élévation au carré (SB1, SB2). 12. Dispositif selon la revendication 10 ou 11, dans lequel les blocs d'élévation au carré (SB1, SB2) et de multiplication (MB1, MB2) comprennent chacun un coprocesseur de type à unité centrale programmable, ou un coprocesseur entièrement hardware de type machine d'état, ou bien sont réalisés chacun par une tache exécutée de manière io indépendante d'un programme principal, les taches et le programme principal étant exécutés par le processeur (FROC) de type multi-coeur.