Brevet FR2864390A1 — publié le 20050624

PROCEDE CRYPTOGRAPHIQUE D' EXPONENTIATION MODULAIRE PROTEGE CONTRE LES ATTAQUES DE TYPE DPA Dans le domaine de la protection des algorithmes cryptographiques contre les attaques DPA, l'invention concerne un procédé au cours duquel on réalise une exponentiation modulaire de type xAd, avec d un exposant entier de m+l bits, en balayant les bits de d de gauche à droite dans une boucle indicée par i variant de m à 0 et en calculant et en mémorisant dans un accumulateur (RO), à chaque tour de rang i, un résultat partiel actualisé égal à x'b(i). b(i) correspond aux m-i+l bits de poids les plus forts de l'exposant d: b(i) = dm_>i. Le nombre constitué des bits de poids j à k de d est défini par: dk->j= (dk,... , dj)2 = e=j di.2A (i - j) . L'exponentiation modulaire est une des opérations élémentaires utilisés dans de nombreux cryptosystèmes, tels que les cryptosystèmes RSA (Rivest, Shamir and Adleman) ou les cryptosystèmes DH (Diffie and Hellman). Pour de telles applications, x est par exemple un message à chiffrer ou déchiffrer, à signer ou à authentifier, et d est par exemple une clé publique, une clé secrète, ou une partie d'une telle clé. Depuis l'invention de la cryptographie à clé publique par Diffie et Hellman, de nombreux cryptosystèmes à clé publique ont été proposés. Parmi ceux qui résistent à l'analyse cryptographique, le cryptosystème RSA est sans aucun doute le plus largement utilisé. Sa sécurité intrinsèque réside dans la difficulté de factoriser des grands nombres entiers. En dépit d'intensives recherches, le problème de la factorisation est encore considéré comme un important problème, rendant le cryptosystème RSA sûr pour des applications sensibles comme par exemple le chiffrement de données ou la signature digitale. Aussi, plutôt que de tenter de casser l'algorithme RSA à un niveau mathématique, les cryptographes se sont intéressés aux implémentations concrètes des cryptosystèmes RSA. Ceci a conduit à l'essor des attaques par fautes et des attaques à canaux cachés, visant à découvrir notamment des informations confidentielles (comme par exemple des clés ou des parties des clés) manipulées au cours de l'une ou de l'autre des étapes mises en oeuvre par le dispositif de calcul exécutant une opération cryptographique. Les attaques à canaux cachés les plus connues sont dites simples ou différentielles. On entend par attaque à canal caché simple (SPA) ou différentielle (DPA), une attaque basée sur la mesure d'une grandeur physique depuis l'extérieur du dispositif, dont l'analyse directe (attaque simple SPA) ou l'analyse selon une méthode statistique (attaque différentielle DPA) permet de découvrir des informations manipulées dans le dispositif. Ces attaques ont notamment été dévoilées par Paul Kocher (Advances in Cryptology - CRYPTO'99, vol. 1666 of Lecture Notes in Computer Science, pp.388-,397. Springer-Verlag, 1999), Parmi les grandeurs physiques qui peuvent être exploitées à ces fins, on peut citer le temps d'exécution, la consommation en courant, le champ électromagnétique rayonné par la partie du composant utilisée pour exécuter le calcul, etc. Ces attaques sont basées sur le fait que, au cours de l'exécution d'un algorithme, la manipulation d'un bit, c'est à dire son utilisation par une instruction particulière, laisse une empreinte particulière sur la grandeur physique considérée, selon la valeur de ce bit et / ou selon l'instruction. Il existe deux familles d'implémentations des algorithmes d'exponentiation permettant d'évaluer la valeur de y = x"d mod N: les implémentations dites de droite à gauche et les implémentations dites de gauche à droite. Dans les implémentations de gauche à droite, on balaye les bits de l'exposant depuis le bit de poids le plus fort jusqu'au bit de poids le plus faible. Dans cette deuxième famille d'algorithmes d'exponentiation, est notamment connu l'algorithme SAM (pour Square And Multiply ou élever au carré et multiplier) et ses variantes telles que les algorithmes à fenêtre glissante. Par rapport aux algorithmes dits de droite à gauche, les algorithmes de gauche à droite nécessitent moins de mémoire et permettent l'utilisation de puissances x'i précalculées pour accélérer le calcul de y. Tous les algorithmes de gauche à droite ont en commun l'utilisation d'un accumulateur (ou registre) qu'on actualise tout au long du calcul pour mémoriser la valeur de xAdm_>i mod N pour des valeurs décroissantes de i jusqu'à ce que l'accumulateur contienne la valeur finale y = xA dm_>o = xA d mod N. dk_>j est le mot constitué des bits de poids j à k de d. Le principe général de l'algorithme SAM est le suivant. On note d = (dm,.. . , do)2 = m=0 di.2A i, la représentation binaire de l'exposant d, avec di e {0, 1}, le bit de poids i de d. Pour chaque bit de d, l'algorithme SAM mémorise dans un accumulateur (registre RO) un résultat actualisé calculé à partir de la relation de récurrence xA dm_>i = ()eA dm->i+1)2 * xA di, avec xAdm_>m = xAdm, ce qui est résumé par l'algorithme ci- dessous: Entrée: x, d = (dm,... , do)2 Sortie: y = xAd mod N RO j fait référence aux bits de rang j à i de d. Pour prévenir les attaques d'implémentation, il est connu qu'il faut rendre les algorithmes aléatoires. Dans le cas du cryptosystème RSA, on connaît actuellement deux types de contre-mesures pour rendre aléatoire le calcul de y = xAd mod N. Le premier type de contre-mesure consiste à rendre 25 aléatoire les données d'entrée de l'algorithme. Un premier exemple de cette première contre-mesure consiste à rendre aléatoire la donnée x avant de réaliser l'exponentiation modulaire, en ajoutant à x un terme aléatoire et à faire les calculs modulo 2'k N, avant un modulo N final: x Un deuxième exemple de cette première contre-mesure consiste à rendre aléatoire l'exposant d avant de réaliser l'exponentiation modulaire, en lui ajoutant un terme aléatoire: d Le plus souvent, ces deux solutions sont combinées pour réaliser l'opération y = y mod N avec y = xA d mod(2k.N). Un troisième exemple de cette première contre-mesure utilisée seule par exemple lorsque x est le résultat d'un formatage probabiliste (par exemple à l'aide de la fonction PSS ou Probabilistic Signature Scheme), car dans ce cas, x est déjà masqué et on calcule directement y = x d mod N avec d = d + r2.cl)(N) avec r2 aléatoire. Malheureusement, une telle randomisation de l'exposant d est limitée à des implémentations particulières, appelées implémentations CRT, du cryptosystème RSA car la valeur de la constante d'Euler 4)(N) n'est généralement pas connue de l'algorithme d'exponentiation privé dans sa version standard (c'est-à-dire non CRT). La deuxième contre-mesure consiste à rendre l'algorithme d'exponentiation lui-même aléatoire. La meilleure mise en pratique de la 2ème contremesure est l'algorithme MIST de Walter. L'algorithme MIST génère de manière aléatoire une nouvelle chaîne d'addition pour l'exposant d pour réaliser xAd mod N. Pour minimiser le nombre de registres, la chaîne d'addition est réalisée à la volée par l'intermédiaire d'une adaptation d'un algorithme d'exponentiation basé sur des chaînes de divisions. Un autre exemple est une version améliorée d'un algorithme à fenêtre glissante (voir Kouichi Itoh, Jun Yajima, Masahiko Takenaka and Naoya Torii. DPA countermeasures by improving the window method CHES 2002, volume 2523 of Lecture Notes in computer Science, pages 303-317, Springer Verlag 2002). Comparé à la première contre-mesure, ceci permet de rendre aléatoire l'exponentiation sans avoir besoin de connaître 4(N) mais nécessite un algorithme de division sécurisé pour calculer les chaînes de divisions et cause des soucis de gestion des calculs non négligeables. L'invention propose un nouveau procédé pour rendre aléatoire l'exécution d'une exponentiation modulaire, dans le but de prévenir les attaques différentielles (DPA), présentant les avantages des deux contre-mesures connues comme dans la première contre-mesure, le procédé selon l'invention n'impose pas d'algorithme d'exponentiation particulier et s'applique à tout algorithme d'exponentiation, et comme dans la deuxième contre-mesure, dans l'invention, l'algorithme lui-même est rendu aléatoire, et non plus seulement les données qu'il manipule. Ainsi, l'algorithme n'a pas besoin de connaître 4(N) et / ou la clé publique e dans une exponentiation RSA (la clé e est souvent indisponible à l'algorithme de signature ou de déchiffrement). Le procédé selon l'invention introduit le concept de exponentiation autoaléatoire, signifiant que l'exposant d est utilisé lui-même comme une source additionnelle d'aléatoirité dans le processus d'exponentiation. Ainsi, l'invention concerne un procédé cryptographique au cours duquel on réalise une exponentiation modulaire de type xAd, avec d un exposant entier de m+l bits, en balayant les bits de d de gauche à droite dans une boucle indicée par i décrémenté de m à 0 par pas de 1 et en calculant et en mémorisant dans un accumulateur, à chaque tour de rang i, un résultat partiel actualisé égal à xAb(i), b(i) étant les m-i+l bits de poids les plus forts de l'exposant d. Le procédé selon l'invention est caractérisé en ce que: - à la fin d'un tour de rang i(j) (i = i(0)) choisi 10 aléatoirement, on réalise une étape El de randomisation au cours de laquelle: El: on soustrait un nombre z (z= b(i(j)), z = b(i(j)) .2i, z = u) aléatoire à une partie des bits de d non encore utilisés (di_1_>0) dans le procédé - puis, après avoir utilisé les bits de d modifiés par l'étape de randomisation El, on réalise une étape de consolidation E2 au cours de laquelle: E2 on mémorise (RO D'un point de vue pratique, au cours de l'étape El, le nombre z est soustrait au contenu d'un registre dans lequel est mémorisé initialement l'exposant d, et le résultat de la soustraction est mémorisé dans le même registre, puis on continue de balayer les bits de b. Pour que le résultat de l'exponentiation xAd mod N soit correct à la fin du procédé, l'étape de randomisation El, ne doit pas modifier les bits de d déjà utilisés dans le calcul (on rappelle que le procédé utilise un algorithme de gauche à droite). L'index i(j) auquel on réalise la randomisation El, choisi aléatoirement, doit donc être choisi tel que les m-i (j) +l bits de poids les plus forts du registre contenant initialement l'exposant d restent inchangés lors de l'étape El. On appellera par la suite cette condition une condition de "consistance". L'idée essentielle de l'invention st ainsi d'utiliser un découpage du calcul de xAd mod N de la forme: xAd = xA(d-z)*xAz (décrit dans la demande de brevet français n 02 04117 (n à confirmer) avec z un nombre aléatoire utilisé comme moyen de masquage de l'exposant d. On choisit de préférence des valeurs de z appropriées telles que xAz puisse être obtenu facilement à partir de x'b déjà calculé par ailleurs au cours du procédé. A noter qu'un choix totalement aléatoire de z entraîne un quasi doublement du temps de calcul. Le procédé selon l'invention s'applique indépendamment de l'algorithme d'exponentiation de gauche à droite. Par ailleurs, le rang i(j) auquel on réalise l'étape El est choisi aléatoire donc le procédé lui-même est aléatoire, et non pas seulement les données qu'il manipule. Le procédé selon l'invention est également efficace en termes de place (il ne nécessite qu'un seul registre de calcul supplémentaire) et en terme de temps de calcul, comme on le verra mieux par la suite dans l'exemple de l'algorithme SAM. Le procédé selon l'invention est encore facile à mettre en oeuvre quel que soit l'algorithme auquel il est appliqué : il ne repose sur aucune propriété de groupe et sa mise en oeuvre ne nécessite pas de connaître au préalable l'ordre du groupe dans lequel l'exponentiation est réalisée. Enfin, le procédé selon l'invention peut être utilisé conjointement avec d'autres mesures de protection des algorithmes, comme par exemple les contre mesures dévoilées par P. Kocher et rappelées précédemment. L'étape El de randomisation peut être réalisée une seule fois au cours du procédé. L'étape El peut également être réalisée plusieurs fois, à la fin de différents tours de rang i(j) (c'est-à-dire au rang i = i (0) , puis au rang i = i (1) , ..., puis enfin au rang i = i (f)) choisis aléatoirement entre 0 et m. L'idée est ici d'améliorer encore la sécurité du procédé en utilisant la relation xAd = xA(d-zl-z2-_-zf)xxAzlxxAz2x xxAzf = xA(((d-zl)-z2)-...-zf)x((xAzl)xxAz2)x... xxAzf On peut choisir au début du procédé le ou les rangs i (j) aléatoires auxquels on réalise une randomisation El. Par exemple, au début du procédé, on détermine un ensemble prédéfini {i (0) , i (1) , ..., i (f) } de f+l (f étant aléatoire ou non) valeurs de l'index i pour lesquelles on souhaite réaliser une randomisation El. Dans ce cas, à chaque tour, on décide de réaliser ou non une randomisation El selon que l'index courant i fait partie ou non de l'ensemble prédéfini. On peut aussi choisir aléatoirement au début de chaque tour i de réaliser ou non l'étape El de randomisation. Dans ce cas, on utilise par exemple une variable booléenne p, tirée aléatoirement à la fin de chaque tour d'index i. Différents modes de réalisation de l'invention vont maintenant être décrits, qui diffèrent l'un de l'autre essentiellement par le mode de réalisation de l'étape El, et notamment par le choix de z et par le choix de la partie de d à laquelle on soustrait z. Selon un premier mode de réalisation, on choisit de réaliser l'étape de consolidation une seule fois à la fin du procédé. Ceci impose de soustraire z systématiquement aux bits de poids les plus faibles de l'exposant d, de sorte à obtenir un résultat correct à la fin du procédé. Selon une première variante de ce mode de réalisation, on choisit z = b (i (j)) = dm_>i (j) pour un nombre aléatoire i(j) choisi et, au cours de l'étape de randomisation El, on soustrait b (i (j)) à d, c'est-à-dire aux bits de poids les plus faibles de d. Le choix z = b(i(j)) est particulièrement avantageux puisque xAb (i (j)) = x'dm_>i (j) est déjà disponible dans l'accumulateur à la fin du tour i(j) et n'a donc pas besoin d'être calculé. La variable i(j) est choisie telle que les bits de poids i(j) à m du nombre d-b(i(j)) soient égaux aux bits de poids i(j) du nombre d, de sorte que les m-i(j)+l premiers tours du calcul de xAd sont identiques aux m-i(j)+l premiers tours du calcul de x'(db(i(j))) (condition de consistance). A la fin du tour i(j), on calcule d-z = d-b(i(j)) et on mémorise le contenu de l'accumulateur xAb dans le registre (El). Dans un exemple particulier, une variable booléenne p est utilisée pour déterminer, à la fin de chaque tour d'index i, si on réalise ou non une randomisation. Si p prend une valeur active, alors on réalise l'étape El: on remplace le nombre d par le nombre d-b(i(j)) et on mémorise xAb(i(j)). Comme dans l'algorithme de gauche à droite classique, l'accumulateur RO est utilisé pour conserver la valeur de x'dm_>i, à chaque tour d'index i. On utilise le registre R1 pour conserver le produit jljx^ dm->i(j) Le tout appliqué à l'algorithme SAM connu, on obtient le l'algorithme I suivant: Entrée. x, d = (dm,... , do)2 Sortie: y = x'd mod N RO 0 alors d i R1 L'étape de randomisation El (d i(j) ; R1 0 >_ dm-> i (j) La condition di(j)_I_>0 ? dm->i (j) signifie que les bits de poids 0 à i-1 de d sont supérieurs à b(i(j)), b(i(j)) étant égal aux bits de poids i(j) à m de d. Ceci permet de garantir que les m-i+l bits de poids les plus forts de d-b(i(j)) sont identiques aux m- i+l bits de poids forts de d, et donc que les m-i+l premiers tours du calcul de xAd sont identiques aux m-i+l premiers tours du calcul de xA(d- b(i(j))). La condition de "consistance" (di (j) -1->0 ? d>) implique que seulement les bits de poids faibles de l'exposant d sont rendus aléatoires. De plus, on remarque que l'étape de randomisation d i (j) modifie uniquement les (m-i(j)+l) bits les moins significatifs de d. A noter que, dans l'algorithme I, comme à l'itération i = i(j) l'étape de mise à jour d i ne modifie pas les (m-i+l) bits les plus significatifs de d, cette étape peut être remplacée par l'étape équivalente: di-1->0 0 - dm->i. Selon une deuxième variante du premier mode de réalisation, on choisit z égal g.b(i), avec g un nombre aléatoire tel que di(j)_I_>0 ? g É dm->i (j) É On utilise dans ce cas la relation xAd = xA(d-z).xAz = x dg.b(i)). (xAb(i))g, et, d'un point de vue pratique, pour réaliser une randomisation El à la fin du tour d'index i(j): - on calcule z = g.b(i) et on soustrait le résultat à l'exposant d, - le registre R1 est mis à jour en multipliant son contenu par le contenu de l'accumulateur (xAb(i)) exposé à la puissance g. Ce qui concrètement peut être réalisé par l'instruction Rl i(7) revient à un simple décalage de bits et l'évaluation de (x 'b (i)) 'g mod N revient à réaliser le calcul de i carrés. Puisque multiplier par 21 revient à un décalage de bits, l'instruction d i qui calcule d-g.b(i) peut être remplacée par dm_>1 t - dm->i ou mieux, par l'instruction équivalente di_1_>T 1 dm->i De plus, comme pour les autres modes de réalisation, on doit vérifier que à l'itération i=i (j) , di-1->0 ? 21É dm->i Cette condition de consistance peut être remplacée par un test équivalent mais plus efficace: di_1_>T dm-iÉ De préférence, on choisit t aléatoire dans l'ensemble {0, T}. La borne T est choisie comme le meilleur compromis entre la randomisation des bits les plus significatifs de d et l'efficacité (en terme de temps de calcul notamment) du calcul des i carrés. Dans l'exemple particulier de l'algorithme SAM, on obtient finalement l'algorithme I' suivant. Entrée: x, d = (dm,... , do)2 Sortie: y = xAd mod N RO T - dm->i R3 0) faire R3 Les algorithmes I et I' peuvent être suffisants pour protéger les exposants dans certains cas. Par exemple, en raison de sa construction, le cryptosystème RSA dévoile toujours la moitié la plus significative de l'exposant d privé si l'exposant public correspondant est petit. Rendre aléatoire les bits de poids forts de d 10 20 n'apporterait donc aucune protection pour un tel algorithme. Toutefois, pour d'autres algorithmes et dans d'autres situations, rendre aléatoire tous les bits de d apporterait une sécurité supplémentaire. Pour cela, on propose, dans un deuxième mode de réalisation, de choisir z = b (i (j)) = dm->i(j) pour un nombre aléatoire i(j) et, au cours de l'étape El, on soustrait b(i) non plus à d, mais à une partie des bits de d correspondant aux bits de d de poids i(j)-c(j) à i (j) -1, c(j) étant un nombre entier tel que i(j) c(j) 0. Ceci peut être exprimé par l'instruction suivante: dm->i(j)-c(j) i(j)-c(j) - dm->i(j) Préférentiellement, comme lors de l'étape El d'une randomisation au rang i (j) , on modifie les bits de poids i(j) - c(j) à i(j) - 1 de d et on choisit de ne réaliser qu'une seule randomisation à la fois, et on choisit de réaliser une étape de consolidation à la fin du rang utilisant le dernier bit de d modifié lors de l'étape de randomisation El précédente (et non plus à la fin du procédé), c'est à dire après l'évaluation du résultat partiel x' (dm->i (j) -c (j)) mod N. Ceci revient à imposer la condition i(j+l) S i(j) - c(j), i(j+l) étant l'index de la randomisation suivante. Ceci permet de ne pas utiliser de registres supplémentaires pour mémoriser les bits de l'exposant qui ont été modifiés lors d'une randomisation précédente. Egalement, on choisit i(j) - c(j) i (j) -c (j)) mod N. Ces deux conditions peuvent être concrétisées par l'utilisation d'un sémaphore booléen c qui indique si une mise à jour est autorisée ou pas 6 a une valeur inactive tant que i i(j) - c(j) et est activée lorsque i i(j)- c(j) dm->i(j) (i(j) - 1) (i(j) - c(j) ) m - i(j) q c(j) m - i(j) + 1 Selon une première variante du deuxième mode de réalisation, on choisit c(j) égal à m-i(j)+l. Avec la condition i(j) c(j) ? 0, la condition c(j) m - i(j) + 1 est vérifiée si 2.i(j) _> m+l. L'algorithme SAM modifié selon cette variante peut alors s'écrire (algorithme II) . Entrée. x, d = (dm,... , d0)2 Sortie: y = xAd mod N RO i-c dm->i) ET a si s = 1 alors R1 i-c i- c dm -> i fin si si c = 0 alors RO i(j)-c(j) et dm->i(j) sont des nombres aléatoires de (m-i(j)+l) bits. On notera, dans cet algorithme, que tous les bits de l'exposant sont randomisés. 10 15 20 Selon une deuxième variante du deuxième mode de réalisation, on choisit c(j) aléatoire et compris entre i(j) et m-i(j)+l. On a vu précédemment que la condition c(j) m - i(j) + 1 doit être vérifiée. En posant c(j) = m - i(j) + 1 + v(j), on doit donc vérifier v(j) O. Par ailleurs, avec la condition i(j) c(j) >- 0, il vient 2.i(j) m+l+v(j). Donc la plus grande valeur possible pour v(j) est 2.i(j)-m-1 et donc, comme v(j) >_0, le paramètre c(j) = m- i(j)+1+v(j) peut prendre toute valeur dans l'ensemble {mi(j)+l, ..., i(j)} . On peut alors généraliser l'algorithme II en choisissant c(j) aléatoire dans l'ensemble {m-i(j)+l, ..., i(j)}. Dans l'exemple particulier de l'algorithme II cela revient à remplacer l'instruction: si (2i >- m+l) ET (a = 1) alors c _ m+1) ET (a = 1) alors c _ m+l) ET (a = 1) alors c i-c dm->i) ET a si E = 1 alors R1 i-c i-c - dm -> i fin si si c = 0 alors RO La fréquence d'occurrence de la valeur p = 0 de la variable booléenne p est un paramètre du procédé permettant de choisir le meilleur compromis entre 10 15 20 performance et sécurité, en fonction de l'application envisagée: plus on réalise d'étapes de randomisation, plus on pénalise le temps de calcul global; inversement, moins on réalise d'étapes de randomisation, plus on facilite les attaques par recherche exhaustive. Un bon moyen pour minimiser le coût des opérations additionnelles consiste à modifier légèrement le générateur de nombres aléatoires produisant le nombre p de sorte que, lorsque le poids de Hamming de d-z (z peut avoir différentes valeurs en fonction de b(i), selon le mode de réalisation envisagé) est plus faible que le poids de Hamming de d, p a une plus forte probabilité de valoir 1, et inversement. Avec cette astuce, l'algorithme va tendre à sélectionner le cas ayant le plus faible poids de Hamming, c'est-à-dire la branche la plus rapide. On note seulement que cet algorithme ne peut pas toujours sélectionner la branche la plus rapide, sinon, il deviendrait déterministe et donc facilement attaquable. Selon un troisième mode de réalisation de l'invention, on choisit au début du procédé un nombre u aléatoire de v bits et on mémorise x'u dans le registre Rl. De préférence, le nombre u est modifié plusieurs fois au cours du procédé, pour augmenter le facteur aléatoire dans le procédé. Puis, au cours du calcul, pour un rang i (j) donné, on se demande, pour un paquet w de v bits de d tel que w>u, si le calcul de xAw est plus coûteux (en terme de temps de calcul) que celui de xA(w-u)*xAu. Pour répondre à cette question, il suffit de déterminer si H(w > H(w-u) + 1. H (w) est le poids de Hamming de w, il est représentatif du coût de l'opération x'w. H(w-u) est le poids de Hamming de x'(w-u), représentatif de x'(w-u). Le terme " + 1" est représentatif du coût de la multiplication de x'(w-u) par x'u (x'u étant mémorisé par ailleurs). Si le calcul de x'w est moins coûteux que le calcul de x w-u)*xAu, alors on continue le procédé. Sinon, si le calcul de xAw est plus coûteux que le calcul de xA(wu)*x'u, alors on remplace le paquet w de bits de d par le nombre w-u. L'étape de consolidation (ici, une multiplication par xAu, qui ce traduit par l'opération RO Par rapport aux deux précédents modes de réalisation décrits, ce troisième mode de réalisation présente l'avantage d'être plus rapide, puisque, poureffectuer une randomisation, on choisit chaque fois le chemin le plus rapide (le moins coûteux). Ainsi, on montre expérimentalement que la complexité de ce procédé est d'environ 1.4. La complexité est le nombre moyen de multiplications de contenus de registres réalisées pour chaque bit de l'exposant d. La complexité d'un algorithme SAM non protégé est de 1.5; la complexité des procédés selon le premier ou le deuxième modes de réalisation de l'invention est quant à elle légèrement supérieure à 1.5. Par ailleurs, dans ce troisième mode de réalisation, la source d'aléatoirité (le nombre u) est extérieure au procédé. Enfin, les ressources (notamment le nombre de registres) utilisées sont les mêmes. 15 20 25 30 Ce troisième mode de réalisation peut être concrétisé par l'algorithme IV suivant: Entrée. x, d = (dm,... , do)2 Paramètres: v, k Sortie: y = xAd mod N RO i-v+l h _0)] A [ (h>ha) OU ((p=1) ET (h=ho)) ] alors (on choisit de réaliser x"(w-u)) di->i-v+1 L'exposant d est ici découpé en k blocs, de taille identique si m+l est divisible par k ou de taille identique à une unité près sinon. A chaque début de bloc (c'est à dire pour i = m mod((1+1)/k)), on met la variable a à 1. Ensuite, quand a vaut 1, il faut attendre que l'ensemble L soit vide avant d'effectuer une nouvelle étape de randomisation. A chaque étape de consolidation, on enlève un indice i(j) correspondant de l'ensemble L (instruction L Lorsque l'ensemble L est vidé, une nouvelle valeur de u peut être choisie et xAu est calculé par un algorithme SAM classique utilisant les registres Rl et R2. Au milieu de chaque bloc (a = 0), on réalise une ou plusieurs étapes de randomisation, lorsque h>hA ou (p=1 et h = hA), et on mémorise à chaque fois (instruction L _0 (condition de consistance). A chaque étape de randomisation, si h > hA, on choisit de réaliser l'opération xA(w-u)*xAu, moins coûteuse, et on modifie les bits de d en conséquence (di->i-v+1 A titre indicatif, on donne le nombre moyen de multiplications modulaires nécessaires pour réaliser une exponentiation de longueur 1024 avec l'algorithme SAM, protégé ou non: É SAM sans protection: 1536 multiplication É SAM protégé en ajoutant un multiple de c(n) (r.IV(n) avec r de 64 bits) ajouté à l'exposant d (art antérieur) : 1536 + 96 multiplications É SAM protégé selon l'algorithme II ou III. 1536 + 10 10 multiplications É SAM protégé selon l'algorithme I' 1536+512 multiplications. p, p étant la valeur moyenne de p É SAM protégé selon l'algorithme IV 1443 multiplications On constate par ces exemples qu'un algorithme protégé selon l'invention est très efficace, en terme de multiplications réalisées (et donc de temps de calcul). REVENDICATIONS 1. Procédé cryptographique dans un composant électronique au cours duquel on réalise une exponentiation modulaire de type x^d, avec d un exposant entier de m+1 bits, en balayant les bits de d de gauche à droite dans une boucle indicée par i variant de m à 0 et en calculant et en mémorisant dans un accumulateur (RO), à chaque tour de rang i, un résultat partiel actualisé égal à x^b(i), b(i) étant les m-i+1 bits de poids les plus forts de l'exposant d (b(i) = dm_,i), le procédé étant caractérisé en ce que, à la fin d'un tour de rang i(j) (i = i(0)) choisi aléatoirement, on réalise une étape El de randomisation au cours de laquelle: E1 on soustrait un nombre z (z= b(i(j)), z = b (i (j)) . 2i, z = u) aléatoire à une partie des bits de d non encore utilisés (di-1->o) dans le procédé puis, après avoir utilisé les bits de d modifiés par l'étape de randomisation El, on réalise une étape de consolidation E2 au cours de laquelle: E2: on mémorise (RO 2. Procédé selon la revendication précédente, dans lequel l'étape El est répétée une ou plusieurs fois, à la fin de différents tours de rang i(j) (i = i(0), i = i(1), ...) choisis aléatoirement entre 0 et m. 2864390 26 3. Procédé selon la revendication précédente, dans lequel, à chaque tour i, on décide aléatoirement (p=1) si on réalise l'étape El ou pas. 4. Procédé cryptographique selon l'une des revendications 1 à 3, dans lequel le nombre z (z= b(i(j)), z = b(i(j)).2'r) est fonction de l'exposant d, dans lequel, lors de l'étape de randomisation, on mémorise (R1 5. Procédé selon la revendication 4, dans lequel l'étape de consolidation E2 est réalisée après le dernier tour de rang i égal à 0. 6. Procédé selon la revendication précédente, au cours duquel, lors de l'étape El, on soustrait à d le nombre b(i). 7. Procédé selon la revendication 6, au cours duquel, pour calculer y = x^d mod N, on réalise les étapes 20 suivantes: A: initialisation des registres RO, R1, R2 et d'une variable de boucle i: RO _ 0, répéter les étapes suivantes: a: multiplication du contenu du registre RO par lui-même modulo N et mémorisation du résultat dans le registre RO RO o dm-i alors aa: soustraction des bits de rangs i à m de la variable d à la variable d et mémorisation dans la variable d d d - dm_>i bb: multiplication du contenu du registre R1 par le contenu du registre RO modulo N et mémorisation du résultat dans R1 R1 9. Procédé selon la revendication précédente, dans lequel g est égal à 21, ti étant un nombre aléatoire choisi entre 0 et T. 10. Procédé selon la revendication précédente, dans lequel, pour calculer y = x^d mod N, on réalise: A: initialisation des registres RO, R1, R2 et d'une variable de boucle i: RO i bb: mémorisation du registre RO dans le registre R3: R3 0), élever au carré modulo N le contenu du registre R3, mémoriser loe résultat dans R3 et décrémenter la variable ti tant que (t > 0) faire R3 12. Procédé selon la revendication 11, au cours duquel, lors de l'étape El, on soustrait le nombre b(i) aux bits de d de rang i (j) - c(j) à i (j) -1, c(j) étant un nombre entier et on mémorise le contenu de l'accumulateur (x^b(i(j)) dans le registre (R1). 13. Procédé selon la revendication précédente, au cours duquel, lors du tour de rang i(j+1), on choisit 5 aléatoirement de réaliser l'étape El uniquement si i(j+l) i(j)-c(j). (a = 1 sémaphore libre). 14. Procédé selon la revendication 12 ou 13, dans lequel c(j) est égal à m-i(j)+1. 15. Procédé selon la revendication précédente, au cours 10 duquel, pour calculer Y = x^d mod N, on réalise les étapes suivantes: A: initialisation des registres RO, Ri, R2 et des variables i, c, a: RO _ 0, faire: a: multiplication du contenu du registre RO par lui-même modulo N et mémorisation du résultat dans le registre RO RO - m+l) ET (a = 1) alors mise à jour de la variable c, sinon mise à zéro de la variable a si (2i > _ m+l) ET (a = 1) alors c i-c dm->i) ET a f: si e = 1 alors mémorisation du registre RO dans le registre R1, mise à zéro de la variable a, soustraction des bits de rangs i à m de la variable d aux bits de rangs i-c à i-1 de la variable d et mémorisation du résultat dans les bits de rangs i-c à i-1 de la variable d 35 si e = 1 alors R1 i fin si g: si c = 0 alors multiplication du contenu du registre R1 par le contenu du registre RO modulo N et mémorisation du résultat dans le registre RO; mise à 1 de la variable a si c = 0 alors RO 17. Procédé selon la revendication précédente, au cours duquel, pour calculer y = x^d mod N, on réalise: A: initialisation des registres RO, R1, R2 et des variables de boucle 20 c, a: RO - m+1) ET (a = 1) alors choix d'une valeur de c aléatoirement parmi les entiers compris entre m-i+l et i, sinon mise à zéro de la variable a si (2i >_ m+1) ET (a = 1) alors c i-c dm-> i) ET a e: si s = 1 alors mémorisation de RO dans R1, mise à zéro de a, soustraction des bits de rangs i à m de la variable d aux bits de rangs i- c à i-1 de la variable d et mémorisation du résultat dans les bits de rangs i-c à i-1 de la variable d si e = 1 alors Ri i-c i-c dm -> i fin si f: si c = 0 alors multiplication du contenu du registre R1 par le 10 contenu du registre RO modulo N, mémorisation du résultat dans le registre RO, et mise à 1 de la variable a si c = 0 alors RO 19. Procédé selon la revendication précédente, dans lequel, au cours de l'étape El, le nombre u est soustrait à un paquet w de v bits de d. 20. Procédé selon la revendication précédente, au cours duquel: É si H(w-u) + 1 H(w), on choisit de ne pas réaliser 30 d'étape El, É si H(w-1) + 1 = H(w), on choisit aléatoirement de réaliser ou non une étape El de randomisation. 21. Procédé selon la revendication précédente, au cours duquel, v, k étant des paramètres et x, d des données 35 d'entrée, pour calculer y = x^d mod N, on réalise: 10 20 25 30 A: initialisation des registres RO, R2, de la variable de boucle i et de l'ensemble L: RO _ 0, faire a: multiplication du contenu du registre RO par lui-même modulo N et mémorisation du résultat dans le registre RO RO i-v+1 f: mémorisation du poids de Hamming de la variable w dans la variable h h _ u alors -0)] n [(h>hp)OU((p=1)ET(h=hp))] alors mémorisation de p dans les bits de rangs i-v+l à i de la variable d, ajout de la 40 valeur i-v+l à l'ensemble L si [(a=O)n(i-v+1>_0)] n [(h>hp)OU((p=1)ET(h=hp))] alors di->i-v+l