Brevet FR2942560A1 — publié le 20100827

La présente invention concerne un procédé de traitement impliquant une exponentiation, et un dispositif associé. Les calculs d'exponentiation sont fréquemment utilisés dans les algorithmes cryptographiques et font généralement intervenir, dans ce cadre, un secret, c'est-à-dire un nombre stocké par le dispositif qui met en oeuvre l'algorithme cryptographique et qui n'est pas accessible de l'extérieur. Par exemple, les calculs cryptographiques ont recours à l'exponentiation modulaire pour limiter la taille des valeurs à manipuler. L'exponentiation modulaire est notamment très utilisée dans des applications de type carte à puce. Les étapes qui mettent en oeuvre l'exponentiation, par exemple modulaire, font particulièrement l'objet d'attaques et de cryptanalyse physique de la part de personnes malintentionnées ; il peut s'agir d'attaques par canaux cachés consistant en une analyse de grandeurs physiques (courant électrique circulant dans le dispositif par exemple) lors des calculs cryptographiques ("side channe/ analysis" selon la terminologie anglo-saxonne) ou d'attaques par faute consistant à exploiter un résultat erroné pour en déduire le secret ("fault analysis" selon la terminologie anglo-saxonne). On a de ce fait déjà cherché à protéger ces étapes, en particulier dans le cas où le secret à protéger correspond à l'exposant mis en jeu dans l'exponentiation. Une méthode classique pour protéger un algorithme cryptographique contre les attaques par faute consiste à l'exécuter deux fois, et à comparer les deux résultats obtenus de sorte que s'ils sont égaux, on fournit la valeur calculée à l'extérieur du dispositif cryptographique. Dans la négative, l'attaque a été détectée. Une alternative à cette méthode consiste à décrypter le message crypté lors de l'algorithme pour vérifier qu'il n'a pas été modifié. Toutefois, ces solutions s'avèrent coûteuses en temps et ressources de traitement lorsqu'elles sont mises en oeuvre pour protéger des procédés cryptographiques impliquant une exponentiation, par exemple le cryptosystème RSA (Rivest Shamir Adleman). Cet inconvénient est d'autant plus vrai que nombre de dispositifs cryptographiques courants sont munis de ressources d'exécution limitées. Le cryptosystème RSA utilise une clé publique composée d'un module public N s'exprimant comme le produit de deux nombres premiers secrets p et q ainsi que d'un exposant public e co-premier avec l'indicatrice d'Euler de N définit par (p(N)=(p-l)(q-l). La clé privée correspondante est composée du module public N ainsi que de l'exposant privé d définit comme l'inverse de e modulo (p(N). La signature RSA (ou encore le déchiffrement) s d'un message m (dont la représentation binaire résulte en un nombre strictement inférieur à N) est obtenue comme suit : s=mdmodN. Les clés et module sont choisis grands, typiquement sur 256, 512 ou 1024 bits. Dans le cadre RSA, les clés sont choisies inférieures à cp(N)=(p-1)(q-1) L'algorithme RSA a été rendu plus efficace par l'utilisation du théorème connu des restes chinois (CRT de l'anglais "Chinese Remainder Theorem"). en calculant séparément sp = m' mod p, où dp = d mod (p-1) et sq = mdg mod q, où dq = d mod (q-1), puis en récupérant s à partir de sp et sq, par exemple à l'aide de la recombinaison de Garner. Pour sécuriser cet algorithme RSA contre les attaques par faute, on a pu introduire un vérification de la signature avant de retourner celle-ci comme résultat des calculs, cette vérification étant menée notamment à l'aide de la formule de décryptage correspondante: se mod N. En cas d'inégalité avec la valeur du message 'm' initiale, une faute est détectée. Cette solution présente cependant l'inconvénient de nécessiter une nouvelle et coûteuse exponentiation modulaire, cette fois-ci de la valeur 's'. De ce fait d'autres solutions de protection ont pu être mises au point; d'une part, celles basées sur l'extension du module consistant à ajouter des données de redondance au module public N mais qui ne sont pas satisfaisantes du fait des propriétés cycliques de la fonction modulo appliquée aux données de redondance du module; et d'autre part, celles basées sur une exponentiation auto-protégée ("self secure exponentiation" selon la terminologie anglo- saxonne). Dans ce dernier groupe de solutions, c'est l'algorithme même d'exponentiation qui offre un moyen direct pour vérifier la cohérence des calculs cryptographiques menés. On connaît notamment la solution de Giraud "An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis", IEEE Transactions on Computers, 55(9):1116-1120, Septembre 2006, qui propose un procédé de traitement de données, comprenant une étape de double exponentiation d'un élément appartenant à un groupe fini par un premier exposant, 'd-1', pour fournir une première valeur et par un deuxième exposant, 'd', lié au premier exposant pour fournir une deuxième valeur, et une étape de test d'une relation entre lesdites première et deuxième valeurs. Une solution similaire est décrite dans la demande FR 2 884 004, dans laquelle on réalise une double exponentiation (md md+l) En détail, l'algorithme d'exponentiation de la solution Giraud fait évoluer une paire de variables intermédiaires (ao, a,) stockant les valeurs (ma, m°`+') pour obtenir, à la fins des calculs, les valeurs (md-', md). La cohérence du calcul cryptographique est alors vérifiée en comparant ao.m avec a,. En cas d'inégalité, une faute est détectée. Ces solutions présentent certains inconvénients. D'une part, les calculs pour passer de (1, m) à (md-', md), nécessitant pas moins de (d-1) itérations. D'autre part, ces calculs nécessitent deux multiplications modulaires par bit de l'exposant. Enfin, la comparaison finale fait intervenir à nouveau la valeur du message 'm' conduisant à la détection d'une faute si ce message a été modifié par faute à la fin de l'algorithme alors même que les calculs de ao et a, ont pu être menés correctement. Une variante à la solution de Giraud concerne celle de Boscher et al. décrite dans la publication "CRT RSA Algorithm Protected against Fault Attacks", Information Security Theory and Practices û WISTP 2007, volume 4462 of Lecture Notes in Computer Science, pages 229û243, 2007. Tout comme la solution de Giraud, cette dernière solution nécessite également deux multiplications modulaires par bit de l'exposant. En outre, elle présente l'inconvénient d'utiliser, à chaque itération dans le procédé, quatre registres pour mémoriser un triplet (ao, a,, a2) et la valeur 'm' du message. La présente invention vise à proposer une solution alternative à ces solutions connues de l'art antérieur en vue de pallier au moins un des inconvénients susmentionnés. A cet effet, l'invention concerne notamment un procédé de traitement de données, comprenant une étape de double exponentiation d'un élément d'un groupe fini par un premier exposant pour fournir une première valeur et par un deuxième exposant lié au premier exposant pour fournir une deuxième valeur, et une étape de test d'une relation entre lesdites première et deuxième valeurs, procédé dans lequel : - le deuxième exposant est égal à 1eG û d, où d est le premier exposant et 15'6 est l'ordre du groupe ou un multiple de celui-ci ; et - ladite étape de test comprend une comparaison entre lesdites première et deuxième valeurs et l'élément neutre du groupe. L'ordre 15'6 du groupe G est défini comme étant le nombre d'éléments qu'il contient, également dénommé "cardinal". Selon l'invention, on s'appuie sur les propriétés reliant cet ordre pour un groupe fini et l'élément neutre de ce groupe pour vérifier, de façon efficace et peu coûteuse, la cohérence du calcul cryptographique mené par exponentiation. Si la comparaison n'est pas concluante, une faute est alors détectée. Notamment, la comparaison finale entre les deux résultats d'exponentiation et l'élément neutre n'implique pas à nouveau l'intervention du message 'm' crypté. Dans un mode de réalisation, lors dudit test, on compare le produit de la première valeur et de la deuxième valeur selon la loi interne dudit groupe avec ledit élément neutre, notamment on vérifie la formule suivante : md . m"-d = 1G. On applique ainsi directement la propriété selon laquelle pour tout élément x d'un groupe fini d'ordre 15.6 et d'élément neutre 1G, on a : xeG = 1G. Dans un mode de réalisation, ladite double exponentiation est réalisée de façon itérative, en mettant, à chaque itération, au carré selon la loi du groupe un premier paramètre et à jour deux variables, chacune pour respectivement chaque bit du premier exposant et chaque bit du deuxième exposant, par application dudit premier paramètre selon la loi interne du groupe, généralement une multiplication. On opère ici les deux exponentiations de l'élément selon des mécanismes proches de l'algorithme "square and multiply" dans le cas de l'exponentiation modulaire, également applicable à d'autre type d'exponentiation. Toutefois, dans cette configuration, on évite de mettre au carré deux fois le premier paramètre, réduisant la complexité de la double exponentiation au regard de nombreuses solutions de l'art antérieur. En outre, cette configuration ne requiert l'utilisation que de trois registres: deux pour les deux variables et un pour le paramètre. Dans une variante de réalisation, ladite double exponentiation comprend une étape de calcul desdites première et deuxième valeurs à l'aide d'une double chaîne d'additions, ladite double chaîne étant déterminée pour les deux exposants. Grâce à l'utilisation d'une telle chaîne d'additions, le nombre de multiplication (ou d'addition, selon la loi interne du groupe) lors de l'opération de double exponentiation est nettement réduit par rapport aux solutions de l'art antérieur telles l'algorithme "square and multiply". Corrélativement, l'espace mémoire requis est réduit. C'est notamment en raison du calcul d'un même élément à deux puissances différentes que l'on peut utiliser une telle chaîne d'additions et bénéficier du calcul commun des deux puissances qui en résulte. En particulier, ladite double chaîne d'additions est mémorisée à l'initialisation d'un dispositif mettant en oeuvre la double exponentiation. Dans ce cas, la chaîne d'addition est pré-calculée et stockée en mémoire non-volatile comme un paramètre de l'exponentiation. On évite ainsi de recalculer cette double chaîne à chaque utilisation. Toutefois, une adaptation de l'interface de programmation (API) de la fonction cryptographique (par exemple le RSA) est réalisée afin de ne plus prendre un exposant en paramètre mais une chaîne d'addition. Cette configuration est cependant efficace en ce qu'elle réduit le temps de traitement et les ressources mémoires disponibles. En variante, la double exponentiation comprend une opération de détermination de ladite double chaîne d'additions, notamment lors de la mise en oeuvre de la double exponentiation. Cette configuration permet notamment d'appliquer d'autres mesures protectrices avant le calcul de la double exponentiation, comme par exemple le masquage de l'exposant par l'ajout de valeurs aléatoires comme décrit plus loin. De plus, comme la chaîne est calculée dynamiquement, l'interface de programmation (API) ne change pas. En particulier, ladite opération de détermination comprend la décomposition itérative des deux exposants en paires de valeurs intermédiaires jusqu'à l'obtention de la paire (0,1), chaque élément d'une paire intermédiaire résultant d'une opération sur les éléments de la paire précédente choisie parmi: - la conservation d'un élément précédent, - la soustraction d'un élément précédent à l'autre, - la division d'un élément précédent par deux, ledit élément précédent étant préalablement décrémenté de 1 lorsqu'il est impair. On voit ici que le nombre d'opérations possibles sur les éléments de la chaîne d'additions sont limités (à la conservation, l'addition, la multiplication par 2 [qui est donc une addition d'un élément à lui-même] et l'incrémentation de 1 [ce dernier étant généralement le premier élément de la chaîne]). Dans cette configuration, on arrive à restreindre la profondeur de mémoire utile à 3, c'est-à-dire à trois fois la taille de l'exposant. La profondeur de mémoire est vue ici comme le nombre maximal de variables intermédiaires à garder simultanément pour pouvoir continuer les calculs. Selon une caractéristique particulière, ladite décomposition comprend les itérations suivantes : (al,13Z/2) sial 13Z/2et (3Zmod2 =0 (î1j31)= (al,(13Zû1)/2) si ai 13i /2 et Pi mod2 =1 , ([3Z ùal,al) sial > Ri /2 où (a°, 130) = (a,b), et on représente ladite chaîne d'additions sous forme de chaîne binaire où chaque bit renseigne du résultat des comparaisons de l'itération. Cette chaîne binaire constitue une représentation très compacte de la chaîne d'additions utilisée pour les calculs de double exponentiation. En particulier, ladite décomposition comprend les opérations suivantes: 1.RZ, 4-a;RZR 4-b;j4-n 2. tant que (RZ,, , RZR ) ≠ (0,1) faire les étapes 3 à 9 ci - dessous 3. RZmP 4-RZR ûR. 4. v-RZR mod2 5. RZR 4- RZR / 2 6. t 4_ (RZR Rla ) 7. coJ_1 t; coi t v v 8. (iu,ip, )F(iA (it.p 9. j jû1û(tO1) 10. retourner cO 1R la � y((tO1) A(iî,LR où Ro, RI et R2 sont utilisés pour stocker les valeurs a;, pi et une valeur temporaire, les indices ia, ia, itmp E {0,1,2}, sont tels que Ri,, stocke a;, RZR stocke pi et R. stocke la valeur temporaire, w; désigne un bit d'indice i dans la chaîne binaire (w), n* est la longueur de la chaîne binaire, t et v sont deux variables internes, A représente l'opération logique ET, et v représente l'opération logique OU (par disjonction) et les opérations logiques étant étendues aux espaces {0,1}x {0,1}n _> {0,1}n entre l'argument de gauche et chaque coordonnée de l'argument de droit. Cette réalisation de la décomposition s'appuie sur un algorithme dit "atomique", au sens où les mêmes opérations sont menées quelque soit le secret à protéger. Dans cette configuration, le traitement selon l'invention est résistant aux attaques par analyse de canaux cachés ("side channe/ analysis"). Selon une caractéristique particulière de l'invention, lors de l'exécution des itérations, on utilise un espace mémoire initialement réservé auxdits registres pour stocker au moins partiellement ladite chaîne binaire. Cette gestion économe de la mémoire s'appuie notamment sur le fait que l'algorithme ci-dessus réduit progressivement la taille des données à stocker dans les registres (du fait de la division par deux) alors que la chaîne binaire est progressivement construite. On diminue ainsi l'espace mémoire requis pour le traitement, notamment on peut se limiter à 4,2 I (où I est la longueur des exposants utilisés, la longueur de la chaîne binaire étant estimée en borne supérieure à 2,2 I) au lieu de 5,2 I. Selon une caractéristique de l'invention, la double exponentiation comprend les itérations suivantes : i(ma' , m zb, ) si ti i+I(a, b) = 0 et v i+l(a, b) = 0 (1) (m a- , m b=~) = (m a, , m zbi') si ti i+1(a, b) = 0 et v i+l(a, b) = 1 (2) (m b, , m a,+b,) si t (a, b) =1 (3) OÙ-C.= 0 si a n-i Ç 13,_i /2 1 Si a n-i > 13 n-i /2 et vi = Rn_i mod2 . On observe ici que les valeurs de i et v correspondent aux valeurs stockées dans la chaîne binaire w représentative de la chaîne d'additions 5 correspondante. En particulier, ladite double exponentiation comprend les calculs suivants: R(0,0) 4- 1;R(0,1) m; R(1 0) 4- m y-1;�4-1;i4-0 tant que i Selon une caractéristique de l'invention, ledit groupe présente une loi interne de type multiplication modulaire et la double exponentiation est une double exponentiation modulaire. Ce peut être par exemple le groupe Z*N muni de l'opération multiplication classiquement connue. Dans un mode de réalisation spécifique, on calcule la double exponentiation modulaire, de module N, de l'élément m à l'aide des restes chinois en réalisant les étapes suivantes : une première double exponentiation modulaire, de module p, de l'élément m par un premier exposant dérivé dp égal à d mod (p-1) et un deuxième exposant dérivé égal à n.(p-1)-dp, de sorte à fournir une première valeur intermédiaire et une deuxième valeur intermédiaire; - une deuxième double exponentiation modulaire, de module q, de l'élément m par un troisième exposant dérivé dq égal à d mod (q-1) et un quatrième exposant dérivé égal à n'.(q-l)-dq, de sorte à fournir une troisième valeur intermédiaire et une quatrième valeur intermédiaire; où p et q sont deux entiers premiers tels que N=p.q, et n, n' sont deux entiers positifs non nuls, et ladite étape de test comprend une étape de recombinaison desdites première et troisième valeurs intermédiaires de sorte à obtenir ladite première valeur, et au moins une étape de comparaison entre ladite première valeur obtenue, l'élément neutre et les deuxième et quatrième valeurs intermédiaires. Ces réalisations mettent en oeuvre le théorème des restes chinois dans le cadre de la présente invention. Les deuxième et quatrième valeurs peuvent individuellement comparées à la première valeur recombinée, ou peuvent être recombinée avant que le résultat de la recombinaison soit comparé à ladite première valeur recombinée. Selon une variante, ledit groupe présente une loi interne de type addition sur une courbe elliptique et la double exponentiation est une double multiplication scalaire sur la courbe elliptique. Cette configuration correspond plus spécifiquement à la cryptographie basée sur les courbes elliptiques. Le groupe correspondant est constitué des points d'une courbe elliptique, auxquels est classiquement associée une loi interne additive "+" que nous ne détaillons pas plus ici. Corrélativement, l'invention vise également un dispositif de traitement 15 de données, comprenant - des moyens aptes à calculer une double exponentiation d'un élément d'un groupe fini par un premier exposant pour fournir une première valeur et par un deuxième exposant lié au premier exposant pour fournir une deuxième valeur, 20 - des moyens de test d'une relation entre lesdites première et deuxième valeurs dispositif dans lequel: - le deuxième exposant est égal à 1eG û d, où d est le premier exposant et 15'6 est l'ordre du groupe ou un multiple de celui-ci ; et 25 - les moyens de test sont aptes à comparer lesdites première et deuxième valeurs et l'élément neutre du groupe. De façon optionnelle, le dispositif peut comprendre des moyens se rapportant aux caractéristiques du procédé de traitement exposé précédemment. 30 Selon un mode de réalisation, le dispositif comprend des moyens de détermination d'une double chaîne d'additions en fonction desdits deux exposants de sorte à calculer ladite double exponentiation à partir de ladite double chaîne. En particulier, lesdits moyens de détermination comprennent un espace mémoire initialement dédié à des registres pour le stockage de valeurs intermédiaires de ladite chaîne et progressivement libéré pour le stockage au moins partiel d'une chaîne binaire représentative de ladite chaîne d'additions. Les avantages de tels dispositifs sont similaires aux avantages du procédé présentant des caractéristiques correspondantes. L'invention a également trait à une carte à microcircuit comprenant un dispositif ci-dessus, et présente des avantages similaires. D'autres particularités et avantages de l'invention apparaîtront encore dans la description ci-après, illustrée par les dessins ci-joints, dans lesquels : - la figure 1 représente schématiquement les éléments principaux d'une forme de réalisation possible pour une carte à microcircuit ; - la figure 2 représente l'allure physique générale de la carte à microcircuit de la figure 1 ; - la figure 3 représente, sous forme de logigramme, des étapes du procédé selon l'invention ; - la figure 4 représente, sous forme de logigramme, des étapes de double exponentiation mise en oeuvre lors des étapes de la figure 3 ; - la figure 5 représente, sous forme de logigramme, des étapes de calcul d'une chaîne d'additions de la figure 4 ; - la figure 6 représente, sous forme de logigramme, un autre exemple de double exponentiation ; et - la figure 7 représente, sous forme de logigramme, un autre exemple de l'invention. La figure 1 représente schématiquement un dispositif de traitement de données 40 dans lequel la présente invention est mise en oeuvre. Ce dispositif 40 comprend un microprocesseur 10, auquel est associée d'une part une mémoire vive 60, par exemple au moyen d'un bus 70, et d'autre part une mémoire non volatile 20 (par exemple du type EEPROM), par exemple à travers un bus 50. Le dispositif de traitement de données 40, et précisément le microprocesseur 10 qu'il incorpore, peuvent échanger des données avec des dispositifs extérieurs au moyen d'une interface de communication 30. On a schématiquement représenté sur la figure 1 la transmission d'une donnée d'entrée E reçue d'un dispositif extérieur (non représenté) et transmise de l'interface de communication 30 au microprocesseur 10. De manière similaire, on a représenté la transmission d'une donnée de sortie S du microprocesseur 10 vers l'interface de communication 30 à destination d'un dispositif extérieur. Cette donnée de sortie S est issue d'un traitement de données par le microprocesseur 10, généralement sur la donnée d'entrée E à l'aide d'une donnée secrète 80 interne au système, par exemple une clé privée. Bien que, pour l'illustration, les données d'entrée et les données de sortie figurent sur deux flèches différentes, les moyens physiques qui permettent la communication entre le microprocesseur 10 et l'interface 30 pourront être réalisés par des moyens uniques, par exemple un port de communication série ou un bus. Le microprocesseur 10 est apte à exécuter un logiciel (ou programme d'ordinateur) qui permet au dispositif de traitement de données 40 d'exécuter un procédé conforme à l'invention dont des exemples sont donnés dans la suite. Le logiciel est composé d'une série d'instructions de commande du microprocesseur 10 qui sont par exemple stockées dans la mémoire 20. En variante, l'ensemble microprocesseur 10 - mémoire non-volatile 20 - mémoire vive 60 peut être remplacé par un circuit à application spécifique qui comprend alors des moyens de mise en oeuvre des différentes étapes du procédé de traitement de données. La figure 2 représente une carte à microcircuit qui constitue un exemple de dispositif de traitement de données conforme à l'invention tel que représenté à la figure 1. L'interface de communication 30 est dans ce cas réalisée au moyen des contacts de la carte à microcircuit. La carte à microcircuit incorpore un microprocesseur 10, une mémoire vive 60 et une mémoire non volatile 20 comme cela est représenté sur la figure 1. Cette carte à microcircuit est par exemple conforme à la norme ISO 7816 et munie d'un microcontrôleur sécurisé qui regroupe le microprocesseur (ou CPU) 20 et la mémoire vive 60. En variante, le dispositif de traitement de données peut être une clef USB, un document ou un support d'informations papier comportant dans l'une de ses feuilles un microcircuit associé à des moyens de communication sans contact. Il s'agit de manière préférée d'une entité électronique portable ou de poche. En référence à la figure 3, on décrit maintenant un exemple de procédé de traitement selon l'invention au cours duquel le microprocesseur 10 souhaite crypter un message m en une signature s: s = md. Ce procédé permet un calcul d'exponentiation réalisé conformément aux enseignements de l'invention. De façon classique en informatique, les messages m appartenant au groupe G = Z*N muni de la loi de composition interne de type multiplication "." largement connue sont des mots binaires de [log2(N)1 bits ([xl étant la valeur entière supérieure). On note ici que l'élément neutre de ce groupe est 1, que l'on note ci-après 1G. Dans le cas de tels groupes Z*N , composé des entiers entre 1 et N-1 qui sont inversibles modulo N, les multiplications suivantes sur les messages m sont réalisées modulo N (N est le module de chiffrement public). Il s'agit de l'exponentiation dite modulaire, et l'ordre 1G=15.Z, vaut cp(N), cp étant la fonction N Totient (indicatrice) d'Euler. Si l'ensemble des messages binaires ne forme pas directement le groupe G (ou Z*N ), on peut utiliser une fonction f inversible de mappage qui, à un message m, associe un élément du groupe G. A titre illustratif, si les messages m sont formés de i bits (i A l'étape E100, le microprocesseur reçoit en entrée le message m, la clé secrète d (de longueur /), l'ordre 15'6 du groupe, l'élément neutre 1G et, si nécessaire, le module de chiffrement N pour réaliser le calcul ci-dessus. Comme décrit ci-après, le traitement réalise une double exponentiation de ce message, avec un premier exposant égal à d et un deuxième exposant égal à l'ordre 15'6 du groupe moins d (1eG-d). Les deux résultats, md et meG-d sont alors comparés à l'élément neutre 1G pour garantir que le traitement s'est bien déroulé. Ainsi, à l'étape E102, on initialise les registres du microprocesseur, à savoir l'initialisation à la valeur d d'une première variable a (le premier exposant) et l'initialisation à la valeur 13G-d d'une deuxième variable b (le deuxième exposant). D'une façon générale, on s'assure que l'ordre 13G est supérieur à d, pour que d et 13G-d soient positifs et présentés sur un même nombre de bits. C'est notamment le cas pour l'algorithme RSA où généralement l'exposant d est l'inverse de la clé publique 'e' modulo cp(N). Si tel n'était pas le cas, on pourra utiliser un multiple de l'ordre 13G auquel on soustrait 'd' de sorte à obtenir une valeur positive, et on exprime d sur un même nombre de bits que le multiple obtenu. A l'étape E104, on détermine si a vaut d, de sorte à détecter une éventuelle faute d'exécution (possiblement en cas d'injection malintentionnée de faute) auquel cas le traitement retourne une erreur E106 et le traitement prend fin. La clé secrète d est notamment chargée depuis une mémoire non volatile du dispositif 40 lors du test E104 afin de déterminer une éventuelle corruption de la valeur d. Dans l'affirmative, on initialise, à l'étape E108, une variable binaire 8 par 1 si a > b et par 0 sinon. On compare, à l'étape E110, la variable 8 à 1. Dans l'affirmative, on intervertit a et b (étape E112) puis on passe à l'étape E114, sinon on passe 30 directement à l'étape E114. Lors de cette dernière, on réalise une double exponentiation telle que décrite ci-après dans différents modes de réalisation, pour obtenir dans des registres Ro et RI, respectivement ma et mb. Lorsque les exponentiations sont modulaires, on recharge à ce moment le module de chiffrement N depuis une mémoire non volatile du dispositif 40 afin de déterminer une éventuelle corruption de cette valeur N. A l'étape E116, on compare Ro.R1 à l'élément neutre 1G, ici 1, c'est-à-dire qu'on vérifie l'égalité suivante : ma.mb = 1G, soit md.mbG d = 1 G. Comme évoqué ci-dessus, on note ici que dans le cas d'une exponentiation modulaire, la multiplication est réalisée modulo N. Si l'égalité est vérifiée, le traitement retourne (étape E118) la valeur RS qui correspond à la valeur attendue md, et le traitement prend fin. Sinon, une erreur est retournée (étape El 06). Le traitement décrit ici se base sur la propriété suivante des groupes finis: mbG = 1G, pour tout élément m du groupe G, afin de détecter efficacement une faute injectée pendant le traitement. Dans l'exemple ci-dessus, on peut s'abstenir d'utiliser la variable 8. Dans ce cas, on choisit une fonction de double exponentiation utilisée lors de l'étape E114 qui réalise elle-même la permutation initiale entre a et b de sorte à avoir a b et retourne dans le registre Ro, la valeur ma (a avant permutation). L'étape E118 retourne alors Ro. En référence à la figure 4, on décrit maintenant un exemple de calcul de la double exponentiation mise en oeuvre lors de l'étape E114. A l'étape E150, le microprocesseur 10 reçoit en entrée les valeurs m, a et b évoquées à l'étape E114 supra. On initialise, à l'étape E152, le registre Ro évoqué ci-dessus à la valeur 1G (ici 1), le registre RI à la valeur m, une variable y d'un bit à la valeur 1 et une variable i d'incrémentation d'itérations à la valeur 1. A l'étape E154, on calcule une chaîne binaire w = (w;); pour les valeurs a et b comme décrit plus bas en référence à la figure 5. La chaîne binaire w représente de façon synthétique une double chaîne d'additions liée à a et b. Cette chaîne binaire w peut être calculée dynamiquement lors de chaque double exponentiation telle que décrite ici en lien avec la figure 4, ou être pré-configurée en mémoire volatile du dispositif de traitement avant de procéder aux double exponentiations. Une chaîne d'additions (x;); pour une valeur a est connue comme étant un ensemble de valeurs x;, où chaque élément est la somme de valeurs d'indice inférieur, par exemple telle que : xo=1, xn=a et pour tout k, xk=x;+x1 où i, j b;+1 / 2 v;+1 = b;+1 mod 2. On décrira ci-après une méthode de calcul de cette chaîne. Cette double chaîne d'additions présente l'intérêt d'avoir une profondeur mémoire de 3. En effet, on limite l'évolution des valeurs intermédiaires (a;, b;) de la chaîne d'additions par les opérations suivantes: addition d'une valeur à elle-même (soit une multiplication par 2), addition des deux valeurs intermédiaires entre elles, et incrémentation d'une valeur par 1. Il en résulte qu'à un instant donné, il n'est nécessaire que de stocker ces deux valeurs intermédiaires (a;, b;) ainsi que la valeur 1 (ces valeurs correspondant respectivement à ma, mb et m dans les calculs de double exponentiation). Au contraire, les solutions classiques d'utilisation de simples chaînes d'additions nécessitent un grand espace mémoire afin de stocker l'ensemble des puissances intermédiaires m, utilisées pour le calcul des puissances suivantes. L'invention n'est cependant pas limitée à cette double chaîne d'additions et toute double chaîne plus ou moins longue peut être utilisée. La chaîne binaire w est composée, pour i croissant, des valeurs Ti suivies chacune lorsque Ti = 0 de la valeur v;. Cette chaîne binaire est une représentation compressée de la double chaîne d'additions permettant d'optimiser la mémoire du dispositif 40. On comprend ici que les opérations susmentionnés liant les valeurs (a;+1, b;+1) et (a;, b;) ne sont pas limitatives et peuvent être plus nombreuses. Le choix restreint ci-dessus permet cependant d'obtenir une chaîne binaire w très compacte en raison du faible nombre de bits utilisés pour coder chaque opération. Grâce à cette double chaîne d'additions, on va calculer les deux exponentiations souhaitées : (m°^,mbn )_ (m°,mb) par itérations des paires m b' )i=o... n De retour à la figure 4, on poursuit en comparant w; à 0 (afin de déterminer les opérations reliant (a;+1, b;+1) à (a;, b;)) lors de l'étape E156. Si w;=0 à l'étape E156 (correspondant à Ti = 0), on monte au carré (étape E158, correspondant au fait que b;+1 = f (2b;)) le registre R7. Ce registre correspond initialement à la valeur 0 et au fur et à mesure où y est modifié, le registre R7 stocke à tout instant la valeur mb= On incrémente également l'indice i = i+1 de sorte à récupérer le bit suivant dans la chaîne w (comprenant ici la valeur v;). A l'étape El 60, ce nouveau bit w; est comparé à 1. En cas d'égalité, le registre R7 est multiplié par le message m au cours de l'étape E162, pour prendre en compte que l'on incrémente 2b; obtenu précédemment pour obtenir b;+1 (équation (2)). On poursuit à l'étape E164. Si ce nouveau bit w; est égal à 0, on va directement à l'étape E164. En effet, l'équation (1) n'implique pas d'incrémentation de la valeur 2b;. Suite au test de l'étape E156, si le bit w; est égal à 1 (Ti = 1), on multiplie (étape El 66) les deux registres R7 et R701 et on stocke le résultat dans le registre R701. On remplace ensuite y par yO1, ainsi le résultat du calcul précédent est désormais stocké dans R7 (celui qui stocke mbi+1) et R701 comprend mai+1 = mb= comme on le voit dans la formule (3). Et on poursuit à l'étape E164. A cette dernière étape, on incrémente la valeur i pour passer au bit w; suivant (étape E164). On compare, à l'étape E168, l'indice i avec la valeur n*, où n* est la longueur de la chaîne binaire w; (déterminée lors de l'étape E154 par exemple). Si i Par ailleurs, afin d'éviter toute modification intentionnelle de la chaîne d'additions w, par exemple par remplacement d'un bit final "1" en deux bits finaux "01" ou "00", on prévoit à l'étape El 70 de procéder à une vérification plus précise de l'indice 'i' comparativement à la valeur n*: - si i = n*, les registres peuvent être retournés, - si i > n*, un message d'erreur est alors retourné. On décrit maintenant en référence à la figure 5 la détermination de la chaîne binaire w évoquée à l'étape E154. La solution retenue ici consiste à partir de la paire (a, b) et à diminuer ces valeurs jusqu'à (0, 1) en se limitant aux opérations de division par deux, de soustraction des valeurs intermédiaires et de décrémentation par 1. En effet, si ao Ro alors on a les propriétés suivantes: ai pi il existe n tel que (an, tan) = (0, 1). Ce calcul des valeurs (a;, 13;) est effectué à l'aide des relations suivantes : (ai,(3i /2) siai 13i /2 et (3i mod2=0 (î1j31)= (ai,(t3 -1)/2) siaiRi /2et(3i mod2=1 (13i -ai,ai) si ai >'3i /2 où les valeurs a et 13 sont donc telles que: (ao, 130) = (a, b) et (an, (3n) = (0, 1). On intervertit initialement a et b de telle sorte que ao (30. On remarque que (a;, b;) = (an_;, 13n_;) et que pour obtenir w;, on a : tii=0sian_i13n_i/2 ti;=1 sian_;>(3n_;/2 v;=13n_;mod 2. On cherche ici à diminuer au plus vite les valeurs a; et 13;, en diminuant progressivement 13; jusqu'à ce qu'il soit proche de a; (limite à a;>13;/2). On soustrait alors a; à 13; et on intervertit les deux valeurs de sorte à conserver la propriété a; 13;. On diminuer ainsi plus vite le plus grand des nombres, comparé à une simple division par 2. En conséquence, la chaîne d'additions est plus courte et les calculs d'exponentiation plus rapides. De retour à la figure 5, on calcule donc les valeurs intermédiaires (a;, pi) et on en déduit les bits Ti et v; composant la chaîne w : A l'étape E200, le microprocesseur reçoit en entrée les valeurs a et b avec a b. On initialise, à l'étape E202, un premier registre Ro à la valeur a (c'est-à-dire ao) et un deuxième registre RI à la valeur b (c'est-à-dire (3o). De même, un booléen y (servant par la suite à indiquer le registre Ry stockant pi, Ryal stockant a;) est initialisé à 1 alors qu'une variable j d'incrémentation est elle initialisée à n* correspondant à la longueur de la chaîne w. A ce stade, la chaîne w n'est pas connue donc n* non plus. On peut cependant démontrer que n* est statistiquement borné (borne supérieure) par la valeur 2,2 log2 b. On prévoit donc de stocker w dans une mémoire tampon Q. de longueur 2,2 log2 b en initialisant j par l'index de bit final de cette mémoire tampon: j =1-2,2 log2 dl -1. A l'étape E204, on vérifie si (Ryal, Ry) est égal à (0, 1) auquel cas on a fini la décomposition de (a, b). Dans le cas où cette égalité n'est pas vérifiée, on compare Ry/2 et Ryal (étape E206), afin de déterminer quelle décomposition parmi les trois formules ci-dessus on applique. On note ici que le résultat de cette comparaison correspond à la valeur de i pour cette décomposition. Si Ry/2 Ryal (i = 0), alors on mémorise 52.1 = Ti = 0, puis s = v; = Ry mod 2 et on divise (Ry - Ry mod 2) par deux (les indices 'i' sont renseignés ici à titre indicatif en référence à a; et pi, et varient non linéairement avec l'indice 'j'). Lorsque la division ne conserve que la partie entière du quotient, on peut effectuer uniquement la division de Ry par deux. On décrémente j de 2 (étape E208). Si Ry/2 {0,1}n entre l'argument de gauche et chaque coordonnée de l'argument de droite. T - (A B) représente l'opération qui retourne '1' si la comparaison (A B) est vérifiée et '0' sinon (A > B). Ici, on observe que toutes les opérations sont calculées à chaque itération quelques soient les valeurs de t (correspondant à i) et de v (correspondant à v). L'algorithme est donc bien atomique. On a vu ci-dessus que la longueur de la chaîne w a une limite supérieure égale à 2,2 loge b soit 2,2 / où lest la longueur des exposants. Au lieu de prévoir une mémoire de 5,2 / pour stocker w et les trois registres, on réserve initialement 1,2 / de mémoire pour les bits w; de plus grand index. Puis au cours des calculs ci-dessus, notamment lorsque l'on a rempli ces 1,2 / bits et que les valeurs a; et pi (après les nombreuses opérations ci-dessus) ont une longueur sensiblement également à / = 2, on peut compresser les trois registres sur 2/ bits et récupérer ainsi / bits pour stocker les bits w; de plus faibles index. De façon similaire aux calculs de la chaîne binaire w, on peut envisager une réalisation atomique du calcul de double exponentiation (figure 4) comme suit : 1. R(0,0) 1; R(0,1) m; R(1,0) m 2.y 4-1;g 1;i 4- 0 3.w 4- f (a, b) où f est l' algorithme atomique ci - dessus de calcul de la chaîne w 4. tant que i En référence maintenant à la figure 6, on illustre un autre exemple de réalisation du calcul de double exponentiation de l'étape E114. Cet exemple est de type � square and multiply �. A l'étape E300, le microprocesseur reçoit en entrée les paramètres m, a={a,_1...ao} et b={b1_1...bo} prévus lors de l'étape E114. A l'étape E302, on initialise deux variables A et B chacune à la valeur 1, une variable M à la valeur m, et une variable i d'itération à O. On poursuit à l'étape E304 en comparant le bit a; à 1. En cas d'égalité, on effectue l'opération A = A.M à l'étape E306 puis on passe à l'étape E308. En cas d'inégalité, on passe directement à l'étape E308. A cette dernière, on compare le bit b; à 1. En cas d'égalité, on effectue l'opération B = B.M à l'étape E310 puis on passe à l'étape E312. En cas d'inégalité, on passe directement à l'étape E312. On incrémente alors la valeur i lors de l'étape E312. Si i=l (test à l'étape E314), c'est-à-dire si on a parcouru tous les bits des exposants a et b, il est mis fin au traitement en retournant les valeurs A et B correspondant aux exponentiations ma et mb souhaitées (E316). Si le test de l'étape E314 est faux, on poursuit à l'étape E318 en élevant au carré la variable M, et on retourne à l'étape E304. On décrit maintenant en référence à la figure 7 une adaptation des enseignements de l'invention au cas d'un cryptage de type RSA-CRT, s'appuyant sur des exponentiations modulaires. Dans le cas spécifique du groupe Z*N, le module de chiffrement N vaut p.q (deux grands nombres premiers) et l'ordre du groupe vaut l'indicatrice d'Euler cp(N)=(p-1).(q-1). Comme vu plus haut dans le cas CRT, la signature s est déterminée à partir de sp et sq, par exemple à l'aide de la recombinaison de Garner : s = CRT(sp, Sc) = sq + q.((q-' mod p).(sp - Sc) mod p). Dans les conditions de l'invention, on calcule les paires (sp, cp) et (Sc', 30 cq) où cp = mp-1 dP mod p et cq = mq-1 dg mod q , puis on combine ces deux paires à l'aide de la fonction CRT pour obtenir (md, m`'R-d) mod N. En détail, les étapes E100' à E114' sont similaires aux étapes E100 à E114 susmentionnées, à ceci près que les données d'entrée sont m, d, N et (p(N) pour effectuer des exponentiations modulaires lors de l'étape E114'. A l'étape E116', le traitement fournit en sortie la paire (Ra, Rso1) correspondant à (md, m`'n-d) et prend fin. Ces étapes sont donc utilisées pour calculer (sp, cp) [respectivement (sq, cq)] en fournissant, comme données d'entrée, les valeurs m mod p, dp, p et cp(p)=(p-1) [respectivement m mod q, dq, q et 9(q)=(q-1)]. On effectue alors la combinaison de ces deux paires: s Ainsi, on calcule, selon les cas, (md+r1.14G 13G-d), md,,+n(P(P)mod p, mr2(P(P)-dp mod p , d4+ri.(p(q) modq mrr(P(q)-dq modq). Et la vérification E116 selon l'invention est toujours menée: md+ri.14G .mr2.$G-d _ m(ri+r2).14G = 1G . En particulier, r1=0 et r2=2 permet d'obtenir plus aisément la condition a REVENDICATIONS1. Procédé de traitement de données, comprenant une étape de double exponentiation (E114, E114') d'un élément (m) d'un groupe fini (G) par un premier exposant (a) pour fournir une première valeur (Ro, R8, ma) et par un deuxième exposant (b) lié au premier exposant pour fournir une deuxième valeur (RI, RSOl, mb), et une étape de test (E116) d'une relation entre lesdites première et deuxième valeurs caractérisé en ce que : - le deuxième exposant (b) est égal à 1eG û d, où d est le premier exposant et 15'6 est l'ordre du groupe (G) ou un multiple de celui-ci ; et - ladite étape de test comprend une comparaison entre lesdites première et deuxième valeurs et l'élément neutre (1 G) du groupe. 2. Procédé selon la revendication 1, dans lequel lors dudit test (E116), on compare le produit de la première valeur et de la deuxième valeur selon la loi interne (*) dudit groupe (G) avec ledit élément neutre (1G). 3. Procédé selon l'une des revendications 1 et 2, dans lequel ladite double exponentiation (E114, E114') est réalisée de façon itérative, en mettant, à chaque itération, au carré (E318) selon la loi du groupe un premier paramètre (M) et à jour deux variables (A, B), chacune pour respectivement chaque bit (a;) du premier exposant (a) et chaque bit (b;) du deuxième exposant (b), par application dudit premier paramètre (M) selon la loi interne du groupe. 4. Procédé selon l'une des revendications 1 et 2, dans lequel ladite double exponentiation (E114, E114') comprend une étape de calcul desdites première et deuxième valeurs à l'aide d'une double chaîne d'additions (w), ladite double chaîne étant déterminée pour les deux exposants (a, b). 5. Procédé selon la revendication 4, dans lequel ladite double chaîne d'additions (w) est mémorisée à l'initialisation d'un dispositif mettant en oeuvre la double exponentiation. 6. Procédé selon la revendication 4, la double exponentiation (E114, E114') comprend une opération de détermination (E154) de ladite double chaîne d'additions (w). 7. Procédé selon la revendication précédente, dans lequel ladite opération de détermination (E154) comprend la décomposition itérative des deux exposants (a, b) en paires de valeurs intermédiaires (a;, 13;) jusqu'à l'obtention de la paire (0,1), chaque élément d'une paire intermédiaire (a;, 13;) résultant d'une opération sur les éléments de la paire précédente (a;_,, choisie parmi : - la conservation d'un élément précédent, - la soustraction d'un élément précédent à l'autre, - la division d'un élément précédent par deux, ledit élément précédent étant préalablement décrémenté de 1 lorsqu'il est impair. 8. Procédé selon la revendication précédente, dans lequel ladite décomposition (E154) comprend les itérations suivantes : (ai,(3i /2) siai 13i /2 et (3i mod2=0 (î1j31)= (ai,(t3 -1)12) siai13i /2et(3i mod2=1 , (13i ùai,ai) si ai >'3i /2 où (ao, 13o) = (a,b), et on représente ladite chaîne d'additions sous forme de chaîne binaire (w) où chaque bit (w;) renseigne du résultat des comparaisons de l'itération. 9. Procédé selon la revendication précédente, dans lequel ladite décomposition (E154) comprend les opérations suivantes: 1. Ri,, 4-a;Rip 4_b;j4_n* 2. tant que (Ri,, , Rip ) ≠ (0,1) faire les étapes 3 à 9 ci - dessous 3. R. mP 4- R~~ ûR. 4. v - RZR mod2 5. RZR 4- RZR /2 6. t 4_ (R. ≤R. a ) 7. coj_1 t; coi t v v 8. (la,ip,lbnp) (t(Ltmp,La,L(3))v((t01)n(La,L(3,ibnp) 9. j jû1û(t$1) 10. retourner cO où Ro, RI et R2 sont utilisés pour stocker les valeurs a;, Ri et une valeur temporaire,les indices ia, ia, itmp E {0,1,2}, sont tels que Ria stocke a;, RiR stocke stocke la valeur temporaire, w; désigne un bit d'indice i dans la chaîne binaire (w), n* est la longueur de la chaîne binaire, t et v sont deux variables internes, A représente l'opération logique ET, et v représente l'opération logique OU (par disjonction) et les opérations logiques étant étendues aux espaces {0,1}x {0,1}n _> {0,1}n entre l'argument de gauche et chaque coordonnée de 10 l'argument de droite. 10. Procédé selon la revendication précédente, dans lequel, lors de l'exécution des itérations, on utilise un espace mémoire initialement réservé auxdits registres (Ro, RI, R2) pour stocker au moins partiellement ladite chaîne binaire (w). 15 11. Procédé selon l'une des revendications 8 à 10, dans lequel la double exponentiation (E114) comprend les itérations suivantes : (mai ,mzb,) si ti i+1(a, b) = 0 et v i+1(a, b) = 0 (1) (m a , m zb'+1) si ti i+1(a, b) = 0 et v i+1(a, b) =1 (2) (mb' ma'+b, ) si 2 i+1(a,b) =1 (3) OÙ T.= 1 Si a n-i > 13 n-i /2 et vi =Rn-imod2. 20 12. Procédé selon la revendication précédente, dans lequel ladite double exponentiation (E114, E114') comprend les calculs suivants: pi et Ri,,,, 5 0 si a n-i Ç R n-i / 2R(0,0) 4- 1; R(0,1) m; R(1,0) 4- m y4-1;�4-1;i4-0 tant que i 13. Procédé selon l'une quelconque des revendications précédentes, dans lequel on ajoute, avant ladite double exponentiation (E114, E114') et à chacun des premier et deuxième exposants (a, b), un multiple de l'ordre (1o) dudit groupe fonction respectivement d'une première et d'une deuxième valeurs (ri, r2) générées aléatoirement. 14. Procédé selon l'une des revendications 1 à 13, dans lequel ledit groupe (G) présente une loi interne de type multiplication modulaire et la double exponentiation est une double exponentiation modulaire. 15. Procédé selon la revendication précédente, dans lequel on calcule la double exponentiation modulaire, de module N, de l'élément m à l'aide des restes chinois en réalisant les étapes suivantes : _ une première double exponentiation modulaire, de module p, de l'élément m par un premier exposant dérivé dp égal à d mod (p-1) et un deuxième exposant dérivé égal à n.(p-1)-dp, de sorte à fournir une première valeur intermédiaire (sp) et une deuxième valeur intermédiaire (cp); - une deuxième double exponentiation modulaire, de module q, de l'élément m par un troisième exposant dérivé dq égal à d mod (q-1) et un quatrième exposant dérivé égal à n'.(q-l)-dq, de sorte à fournir une troisième valeur intermédiaire (Sc') et une quatrième valeur intermédiaire (cq); où p et q sont deux entiers premiers tels que N=p.q, et n, n' sont deux entiers positifs non nuls, et ladite étape de test comprend une étape de recombinaison desdites première et troisième valeurs intermédiaires (sp, sq) de sorte à obtenirladite première valeur (s), et au moins une étape de comparaison entre ladite première valeur obtenue (s), l'élément neutre (1 G) et les deuxième et quatrième valeurs intermédiaires (cp, cq); 16. Procédé selon l'une des revendications 1 à 13, dans lequel ledit groupe (G) présente une loi interne de type addition sur une courbe elliptique et la double exponentiation est une double multiplication scalaire sur la courbe elliptique. 17. Dispositif de traitement de données, comprenant - des moyens aptes à calculer une double exponentiation d'un élément (m) d'un groupe fini (G) par un premier exposant (a) pour fournir une première valeur (Ro, R8, ma) et par un deuxième exposant (b) lié au premier exposant pour fournir une deuxième valeur (RI, Rso1, mb) - des moyens de test d'une relation entre lesdites première et deuxième valeurs caractérisé en ce que : - le deuxième exposant (b) est égal à 1eG ù d, où d est le premier exposant et 15'6 est l'ordre du groupe (G) ou un multiple de celui-ci ; et - les moyens de test sont aptes à comparer lesdites première et deuxième valeurs et l'élément neutre (1 G) du groupe. 18. Dispositif selon la revendication précédente, comprenant des moyens de détermination d'une double chaîne d'additions en fonction desdits deux exposants de sorte à calculer ladite double exponentiation à partir de ladite double chaîne. 19. Carte à microcircuit comprenant un dispositif selon l'une des revendications 17 et 18.