Brevet FR2895609A1 — publié le 20070629

Références : 105784 FR Procédé cryptographique comprenant une exponentiation modulaire sécurisée contre les attaques à canaux cachés, cryptoprocesseur pour la mise en oeuvre du procédé et carte à puce associée L'invention concerne un procédé cryptographique sécurisé contre les attaques à canaux cachés au cours duquel, pour réaliser une exponentiation modulaire de type C = AB1 mod N, où A est un opérande, B1 un premier exposant, N est un module et C est un résultat, on réalise les étapes suivantes, consistant à : • El : masquer l'opérande A par un nombre s, s est un nombre aléatoire, ou un nombre résultant d'une fonction générant une suite de nombres s l0 déterministe, ou une nombre secret fixe, • E2 réaliser une exponentiation modulaire de l'opérande masqué par l'exposant Bl, puis • E3 . démasquer le résultat de l'exponentiation, en enlevant au résultat de l'exponentiation une 15 contribution du nombre aléatoire s. De tels procédés sont notamment intéressants pour des applications asymétriques de signature et de chiffrement. A est alors selon l'application un message à signer, à vérifier, à chiffrer ou à déchiffrer. B1 est selon 20 l'application une clé publique ou privée. C est un résultat selon l'application un message signé, ou déchiffré. Masquer le nombre A par un nombre s est une contre-mesure connue pour sécuriser les opérations d'exponentiation 25 modulaire, notamment lorsqu'elles sont implémentées dans les microcircuits de type carte à puce, contre des attaques dites par canaux auxiliaires ou à canaux cachés (en anglais Side Chanel Attacks) qui permettent d'obtenir de l'information sur le nombre B1. Ref: 105784 FR Une première contre-mesure connue du document Dl (Timing Attack on Implementations of Diffie-Hellman, RSA, DSS and Other Systems, Paul Kocher, Crypto 1996, LNCS Springer) consiste à tirer un aléa s, calculer sB2, où B2 est une clé privée ou publique associée à B1, puis multiplier sB2 par A (sB2.A), élever le résultat de la multiplication à la puissance Bl ((sB2.A)B1) puis réduire modulo N. Bi et B2 étant une clé publique et une clé privée associée, on a Bl.B2 = 1 modulo (p(N),où cp représente la fonction d'Euler, de sorte que le résultat ((sB2.A)B1) modulo N se simplifie pour donner (s.AB1) modulo N. Une division par s permet finalement d'obtenir le résultat recherché C = AB1 mod N. Cette solution est certes efficace, mais sa mise en oeuvre est onéreuse. En effet, pour que la mesure soit efficace, il est indispensable que sB2 soit de taille supérieure à la taille de A. Ce qui suppose que s soit de grande taille, plus précisément de taille supérieure à la taille de A divisée par la taille de B2. Si B2 est de petite taille (par exemple de moins de dix-sept bits), s doit être de grande taille (par exemple de plus du nombre de bits du module divisé par dix-sept). Produire des nombres aléatoires de grandes tailles nécessite l'utilisation d'un générateur de grande taille, qui d'une part consomme un courant important et d'autre part nécessite un temps relativement important, ce qui n'est pas toujours compatible avec des applications de type carte à puce. De plus le temps pour réaliser la division peut être long. Une deuxième contre-mesure, connue notamment du document D2 (J.S. Coron, P. Paillier Countermeasure method in an electronic component which uses on RSA-type public key cryptographic algorithm Patent number FR 2799851. Publication date 2001-04-20. Int Pub Numb. WO0128153), consiste à utiliser deux nombres aléatoires sl, s2 pour réaliser :L'opération (A+sl.N)Bl mod (s2.N). On enlève ensuite à la fin du calcul la contribution apportée par Ref: 105784 FR sl et s2. Comme sl, s2 peuvent être de petite taille, leur obtention est plus aisée. Toutefois, cette méthode nécessite de réaliser une opération modulo s2.N. Ceci nécessite :L'utilisation d'un multiplieur de plus grande taille et n'est pas toujours compatible avec des applications de type carte à puce. Un but de l'invention est de proposer une solution pour réaliser une opération modulaire de type AB1 mod N plus intéressante que les solutions connues car peu onéreuse à mettre en œuvre. Pour cela, l'invention propose de masquer l'opérande A en multipliant l'opérande A par un paramètre de la forme Ks.82, où K est une constante (éventuellement publique) et B2 est un deuxième exposant tel que Bl.B2 = 1 mod (p(N). Pour les applications cryptographiques envisagées, B1 et B2 sont naturellement des clés privée et publique associées. Lors de l'étape de démasquage après exponentiation, on enlève la contribution Ks apportée par l'aléa s. Dans l'invention, l'aléa s est d'une part multiplié par B2 et d'autre part il est placé en exposant. Ainsi, le paramètre KS_B2 est suffisamment grand pour masquer l'opérande A, même lorsque s est petit. Avec l'invention, il n'est donc pas nécessaire de disposer d'un générateur aléatoire de grande taille. Un autre but de l'invention est de proposer un procédé rapide à mettre en oeuvre. Pour cela, dans un mode préféré de mise en oeuvre de l'invention, on réalise les étapes de masquage El, d'exponenti.ation E2 et de démasquage E3 en utilisant un multiplieur de Montgomery, qui a l'avantage de réaliser des multiplications modulaires qui sont particulièrement 4 Ref:105784 FR rapides à exécuter par rapport à des multiplieurs classiques et très utiles pour les exponentiations. De préférence également, on choisit la constante K égale à 2P, p étant un nombre entier compris entre 0 et n, n étant un majorant de la taille du module N. Par majorant de la taille de N, on entend ici un nombre égal ou légèrement supérieur à la taille de n, et classiquement dépendant du choix d'implémentation de la multiplication de Montgomery et /ou des possibilités matérielles du processeur dans lequel la multiplication est implémentée. Par exemple, si N est un nombre de 520 bits, et si le processeur utilisé travaille avec des mots de 576 bits, on choisira avantageusement n égal à 576 bits. Le choix de la constante K = 2P permet d'utiliser avantageusement les propriétés des multiplieurs de Montgomery pour accélérer les calculs tout en garantissant la sécurité du procédé. Le choix d'un nombre p = n tel que K = 2n est optimal comme on le verra mieux par la suite. L'invention concerne également un cryptoprocesseur comprenant notamment un multiplieur de Montgomery pour la mise en oeuvre d'un procédé tel que décrit ci-dessus. L'invention concerne enfin une carte à puce comprenant un cryptoprocesseur tel que décrit ci-dessus. L'invention sera mieux comprise, et d'autres caractéristiques et avantages de l'invention ressortiront clairement de la description qui est faite ci-après, à titre indicatif et nullement limitatif, du mode préféré de mise en ouvre de l'invention. Ref:105784 FR Comme on l'a dit précédemment, l'invention concerne un procédé cryptographique sécurisé au cours duquel, pour réaliser une exponentiation modulaire de type C = AB1 mod N, où A est un opérande, B1 un premier exposant, N est un module et C est un résultat, on réalise les étapes suivantes, consistant à : • El : masquer l'opérande A par un nombre aléatoire s, • E2 réaliser une exponentiation modulaire de 10 l'opérande masqué par l'exposant B1, puis • E3 : démasquer le résultat de l'exponentiation, en enlevant au résultat de l'exponentiation une contribution du nombre aléatoire s. Selon l'invention, lors de l'étape El de masquage de 15 l'opérande A, on multiplie l'opérande A par un paramètre de la forme KS.B2, où K est une constante et B2 est un deuxième exposant tel que Bl. B2 = 1 mod cp (N) . On obtient ainsi un opérande masqué A' = KS'B2 .A. L' exponentiation de A' (étape E2) par Bl donne le résultat masqué C' = KS. AB1 20 mod N. Enfin, lors de l'étape E3, on enlève à C' la contribution Ks apportée par l'aléa s pour retrouver le résultat recherché C. L'invention est mise en oeuvre de préférence en utilisant un multiplieur de Montgomery. 25 Avant de décrire plus complètement le procédé de l'invention, il convient de rappeler quelques propriétés connues d'un multiplieur de Montgomery, décrites par exemple dans le document D3 (P.L. Montgomery, Modular 30 Multiplication without trial division, Mathematics of computation, 44(170) pp 519-521, april 1985). Un multiplieur de Montgomery permet de réaliser des multiplications du type Mgt(A,B,N) = A.B.R-1 mod N. Un avantage de ce multiplieur est sa rapidité de calcul. Un Ref:105784 FR inconvénient de ce multiplieur est qu'il introduit dans le calcul une constante R, appelée constante de Montgomery. R est une puissance de 2 co-première avec N : R = 2n avec n tel que PGCD(R, N) = 1. La constante de Montgomery est intrinsèque au multiplieur et il est nécessaire de supprimer sa contribution en amont du calcul, au cours du calcul ou à la fin. Ainsi, pour calculer C = A.B mod N, on peut par exemple calculer d'abord A.R puis Mgt(A.R,B,N) = A.B mod N. On peut également réaliser une lère multiplication Co = Mgt(A.R, B.R, N) = A.B.R mod N puis une deuxième multiplication de type C = Mgt(l,Co, N) = A.B mod N. Le multiplieur de Montgomery permet également de réaliser des exponeritiations modulaires de type C = MgtExp(A,B,N) = AB.R-(B-1) mod N ou C = MgtExp(A.R,B,N) = AB.R mod N (on compense dans ce cas la constante R-B introduite par le calcul en multipliant A par R en Concrètement, pour réaliser une Montgomery, on exécute un algorithme celui communément appelé "square consistant, dans une boucle indicée par q-1 et 0, q étant la taille du nombre B, en une succession de multiplications de type Ui = Mgt (Ui_1r Ui_1r N) et éventuellement Mgt(Ui,A,N) (ou Mgt(Ui,A.R,N)), selon la valeur d'un bit Bi de B associé à l'indice i, Ui étant une variable de boucle initialisée à la valeur Uq = R. Cette exponentiation est expliquée plus en détails dans le document D4 (Handbook of Applied Cryptography par A. Menezes, P. Van Oorschot et S. Vanstone, CRC Press 1996, chapitre 14, algorithme 14.94). Ce calcul d'exponentiation a l'avantage d'être particulièrement rapide. Les opérations de Montgomery ont notamment les propriétés suivantes, qui seront utilisées par la suite : amont du calcul). exponentiation de comme par exemple and multiply" i variant entre Ref: 105784 FR Mgt(A,B,N) = A.B.R-1 mod N Mgt(A.R,B.R,N) = A.B.R mod N Mgt(l,l,N) = Mgt(N-1,N-1,N) = R 1 mod N Mgt(A,1,N) = Mgt(N-A,N-1,N) = A.R-1 mod N MgtExp(A.R,B,N) = AB.R mod N Dans le mode préféré de mise en oeuvre du procédé de l'invention, on utilise les multiplications et les exponentiations de Montgomery pour accélérer le calcul d'exponentiation masqué par l'aléa K5.B2 . Tout d'abord, lors de l'étape El de masquage de l'opérande A on réalise les sous-étapes suivantes, consistant à : • Ell réaliser une première exponentiation de Montgomery de la constante K par le produit du nombre aléatoire s par le deuxième exposant B2 ; on obtient ainsi le masque K5.B2 mod N puis • E12 : réaliser une multiplication de Montgomery du résultat de la première exponentiation de Montgomery (= le masque K5.B2) par l'opérande A pour produire un opérande masqué A' (A' = Ks.B2.A mod N). Ensuite, lors de l'étape d'exponentiation E2 de l'opérande masqué A', on réalise la sous-étape suivante : • E212 réaliser une deuxième exponentiation de Montgomery de l'opérande masqué A' par le premier exposant B1 pour produire un résultat masqué C' Enfin, lors de l'étape E3 de démasquage du résultat masqué, on réalise les sous-étapes suivantes : • E31 réaliser une troisième exponentiation de Montgomery pour calculer le paramètre K-5, • E32 : réaliser une multiplication de Montgomery du résultat masqué C' par K-5. â Ref: 105784 FR Comme on l'a vu précédemment, les multiplications et les exponentiations de Montgomery introduisent dans le résultat une contribution fonction de la constante R de Montgomery. Cette constante peut être éliminée en fin de chaque multiplication, par exemple en réalisant une multiplication de Montgomery par R2 après un calcul. Lorsque cela est possible, et notamment pour les exponentiations, il est plus facile de compenser la constante R en amont, en multipliant l'opérande par la constante R, plutôt que de compenser une puissance de R (à fortiori une puissance négative de R) en sortie. Egalement, un choix approprié de la constante K permet d'accélérer encore le calcul, et notamment l'étape E31 de calcul de K-S. Plus précisément, choisir une constante K = 2P (p compris entre 0 et n) de la même forme que la constante de Montgomery R = 2n, permet de simplifier les calculs. On a en particulier : Mgt (l, l,N) = Mgt (N-1,N-1,N) = R-1 mod N Mgt (A, 1, N) = Mgt (N-A, N-1, N) = A. R 1 mod N Mgt (2P, 1,N) = Mgt (N-2P,N-1,N) = 2P.2-n mod N = (2n-P)-1 mod N Mgt (2n-P, l,N) = Mgt (N-2n P,N-1,N) = 2n-P.2-n mod N = (2P) -1 mod N, avec 2n-P = R/K Le calcul de l'inverse de K puis de K-S est ainsi facilité. Après diverses simplifications suite au choix de K = 2P, on obtient finalement un procédé comprenant l'ensemble des étapes suivantes. EO : initialisation : E011 choisir un entier j et calculer la constante K = R/23, (comme R = 2n, K = 2P avec p=n-j) E012 choisir un nombre aléatoire s et le multiplier par B2 pour obtenir sl, Ref:105784 FR E013 : calculer R2, El : masquer A en A' Ell : calculer le masque Ksl Elli : calculer Tl = Mgt(K,RZ1N) = K*R mod N ; cette étape permet de compenser en amont la contribution de R dans l'exponentiation qui suit E112 : calculer Ul = MgtExp(Tl,sl,N) = Ksl*R mod N E12 : masquer A en A' E121 : calculer Ml = Mgt(Ul,A,N) = Ks1.A mod N E2 : calculer C' = A' B1 mod N E211 : calculer M2 = Mgt (Ml, R2, N) = Ksl. A. R mod N cette étape permet de compenser en amont la contribution de R dans l'exponentiation qui suit E212 calculer U2 = MgtExp (M1, Bl , N) = AB1. Ks . R mod N E3 : retrouver C à partir de C' E31 : calculer K-s E311 : calculer Il = Mgt (23 , 1, N) = K 1 mod N E312 : calculer I2 = Mgt (Il, R2, N) = K-1 . R mod N E313 : calculer V = MgtExp(I2,s,N) = K-s.R mod N E32 : calculer C = C'.K-s E321 : calculer U3 = Mgt(U2,V,N) = AB1.R mod N E322 : calculer U4 = Mgt(U3,l,N) = AB1 mod N A noter que, lors de la mise en oeuvre du procédé ci-dessus dans un cryptoprocesseur, un même registre ou une même partie de mémoire peut être utilisé pour mémoriser des variables intermédiaires dont le nom comprend la même lettre : Ml, M2 peuvent être stockées successivement dans un registre M, de même les variables Il, I2, V peuvent être stockées dans un même registre I, et les variables Ul, U2, U3, U4 peuvent être stockées dans un même registre U. Ref105784 FR Le choix particulier de K = 2 permet encore d'accélérer le calcul car le fait que K = R permet des simplifications supplémentaires. Après simplifications, on obtient le procédé ci-dessous : EO : initialisation E012 : choisir le nombre aléatoire s et calculer sl = s.B2+l, E013 : calculer R2, El : masquer A en A' Ell : calculer le masque RS1 E112 : calculer Ul = MgtExp(R2,sl,N) = Rs1.R mod N E12 : masquer A en A' E121 : calculer Ml = Mgt (Ul , A, N) = Rs1. A mod N = Rs.B2.A.R mod N E2 : calculer C' = A' B1 mod N E212 calculer U2 = MgtExp(Ml,Bl,N) = AB1.Rs.R mod N E3 : retrouver C à partir de C' E31 : calculer R- (5+1) E313 : calculer V = MgtExp (l, s+l, N) = R- (S+1) . R mod N E32 : calculer C = C' . K- (s+1) E321 : calculer U3 = Mgt(U2,V,N) = AB1 mod N Par rapport au cas général où K = 2p, les simplifications suivantes ont été faites : • K étant égal à R, l'étape E011 devient inutile, • l'étape Elll devient également inutile puisque R2 a été calculé lors de l'étape E013 • en calculant sl =s.B2+l (au lieu de sl = s.B2) lors de l'étape E012, l'étape E211 devient inutile • le calcul de R-1 est immédiat de sorte que les étapes E311 et E312 deviennent inutiles Ref:105784 FR • en choisissant à l'étape E31 s = s+l on évite ainsi l'étape E322. Bien sûr, dans le procédé détaillé ci-dessus, certaines étapes peuvent être déplacées ou permutées par rapport aux autres. Par exemple, dans l'étape d'initialisation E0, les sous-étapes peuvent être réalisées dans un ordre différent. Comme on vient de le voir ci-dessus, l'invention peut être avantageusement mise en oeuvre pour la réalisation de l'exponentiation C = AB1 mod N selon les 3 principales étapes suivantes . • El : A' = A. K5 B2 (masquage de A) • E2 : C' = A'B1 mod N (exponentiation) • E3 : C = C'*Ks (démasquage) L'invention peut également être avantageusement combinée avec le théorème des restes Chinois pour accélérer le calcul de l'exponentiation, on parle alors communément de RSA-CRT. Selon le théorème des restes chinois (ou CRT pour Chinese Remainder Theorem, connue du document D5 (Cryptography Theory and Practice, chapter 4, Douglas R. Stinson, 1995, CRC Press), un calcul d'exponentiation classique C = AB1 mod N peut se décomposer de la manière suivante : • Cp = (A mod p) Bpl mod p • Cq = (A mod q) Be mod q • C = Cq + q*(Iq*(Cp-Cq) mod p) mod N où • p et q sont deux entiers premiers tels que p*q = N, • Bpl = Bl mod (p-l) • Bql = Bl mod (q-l) • Iq = q-1 mod p Ref105784 FR Appliquée à cette décomposition CRT, l'invention conduit au procédé suivant : • El : masquer l'opérande A (A' = Ku.B2 * A) par un nombre u égal à deux fois le nombre s, en multipliant l'opérande A par un paramètre K1B2 • E2 : calcul de C' par le théorème des Restes Chinois (exponentiation) . Cp' = (A' mod p) B1p mod p ; Cq' = (A' mod q) Blq mod q ; C' = Cq' + q*(Iq.(Cp'-Cq') mod p) mod N = Ku*AB1 mod N = K2s*C' mod N • E3 : C = C' * K-2s mod N (démasquage) De préférence, pour un calcul plus facile, on calculera d'abord K2, puis (K2) -s . Dans une variante, on peut aussi réaliser : • El : masquer l'opérande A par un nombre u égal à deux fois le nombre s, de la manière suivante : Ap' = Ku.B2 * A mod p Aq' = Ku.B2 * A mod q • E2 calcul de C' par le théorème des Restes Chinois (exponentiation) . Cp' = (Ap') B1p mod p ; Cq' _ (Aq') Blq mod q ; C' = Cq' + q*(Iq.(Cp'-Cq') mod p) mod N = Ku*AB1 mod N = K2s*C' mod N • E3 : C = C' * K-2s mod N (démasquage) Dans un mode préféré de réalisation, on choisira une constante K = 2max(taille(p), taille(q)) = 2r, où r est la plus grande taille parmi la taille de p et la taille de q. Ce Ref:105784 FR choix permet des simplifications lors de la mise en oeuvre du procédé à l'aide d'un processeur de Montgomery. On remarque alors qu'à l'étape E3 la valeur K2 dans (K2) -S est appropriée pour les opérations modulaires de Montgomery sur le module N sachant que la taille de N est inférieure ou égale à la somme des tailles de p et q, taille (N) REVENDICATIONS 1. Procédé cryptographique au cours duquel, pour réaliser une exponentiation modulaire de type C = AB1 mod N, où A est un opérande, Bi est un premier exposant, N est un module et C est un résultat, on réalise les étapes suivantes, consistant à : • E1 : masquer l'opérande A par un nombre s, • E2 réaliser une exponentiation modulaire de l'opérande masqué par l'exposant B1, puis • E3 : démasquer le résultat de l'exponentiation, en enlevant au résultat de l'exponentiation une contribution du nombre s, le procédé étant caractérisé en ce que, lors de l'étape El de masquage de l'opérande A, on multiplie l'opérande A par un paramètre de la forme Ks B2, où K est une constante et B2 est un deuxième exposant tel que Bl.B2 = 1 mod (p(N). 2. Procédé selon la revendication 1, dans lequel l'étape El de masquage de l'opérande A comprend les sous-étapes suivantes, consistant à • Ell réaliser une première exponentiation de Montgomery de la constante K par le produit du nombre s par le deuxième exposant B2, puis • E12 . réaliser une multiplication de Montgomery du résultat de la première exponentiation de Montgomery par l'opérande A pour produire un opérande masqué A' (A' = Ks-B2). 3. Procédé selon la revendication 2, dans lequel l'étape E2 d'exponentiation comprend la sous-étape suivante consistant à : 20Ref: 105784 FR E212 : réaliser une deuxième exponentiation de Montgomery de l'opérande masqué A' par le premier exposant Bl pour produire un résultat masqué C' 4. Procédé selon la revendication 3, dans lequel l'étape de démasquage E3 du résultat de l'exponentiation comprend les sous-étapes suivantes, consistant à : • E31 réaliser une troisième exponentiation de Montgomery pour calculer le paramètre K-s, • E32 : réaliser une multiplication de Montgomery du résultat masqué C' par K-s. 5. Procédé selon l'une des revendications 2 à 4, dans lequel la constante K est égale à 2p, p étant un nombre entier compris entre 0 et n, n étant un majorant de la taille du module N. 6. Procédé selon la revendication 5, dans lequel la constante K est égale à 2n. 7. Procédé selon la revendication 5 ou 6, comprenant l'ensemble des étapes et sous-étapes suivantes : EO initialisation : E01.1 choisir un entier j et calculer la 25 constante K = 2n/2j, E012 : choisir le nombre s et le multiplier par B2 pour obtenir sl, E01.3 calculer R2, R étant une constante de Montgomery égale à 2n, 30 El : masquer A en A' Ell : calculer le masque Ksl E111 : calculer Tl = Mgt(K,R2,N) = K*R mod N E112 : calculer Ul = MgtExp (T1, sl,N) = Ksl*R mod NRef105784 FR E12 : masquer A en A' E121 : calculer M1 = Mgt(Ul,A,N) = Ksl.A mod N E2 : calculer C' = A' B1 mod N E211 : calculer M2 = Mgt (M1, R2, N) = Ks1. A. R mod N E212 calculer U2 = MgtExp(Ml,Bl,N) = AB1. Ks. R mod N E3 : retrouver C à partir de C' E31 : calculer K-s E311 : calculer Il = Mgt (N-2j,N-1,N) = Mgt (23, 1,N) 10 = K1 mod N E312 : calculer I2 = Mgt(I1,R2,N) = K-1.R mod N E313 : calculer V = MgtExp(I2,s,N) = K-s.R mod N E32 : calculer C = C'.K-s E321 : calculer U3 = Mgt(U2,V,N) = AB1.R mod N 15 E322 : calculer U4 = Mgt(Ul,l,N) = AB1 mod N 8. Procédé selon la revendication 6, comprenant l'ensemble des étapes et sous-étapes suivantes : EO : initialisation 20 E012 : choisir le nombre aléatoire s et calculer sl = s.B2+l, E013 : calculer R2, El : masquer A en A' E11 : calculer le masque Rs1 25 El:L2 : calculer Ul = MgtExp (R2, sl, N) = RS1. R mod N E12 : masquer A en A' E121 : calculer Ml = Mgt(Ul,A,N) = Rsl.A mod N = Rs.B2 . A. R mod N E2 : calculer C' = A' Bl mod N 30 E2:12 calculer U2 = MgtExp(Ml,Bl,N) = AB1. Rs . R mod N E3 : retrouver C à partir de C' E31 : calculer R- (s+1)17 Ref: 105784 FR E313 : calculer V = MgtExp (1, s+l , N) = R- (s+1) . R mod N E32 : calculer C = C' . K-(s+1> E321 : calculer U3 = Mgt(U2,V,N) = AB1 mod N 5 9. Procédé selon l'une des revendications précédentes, dans lequel les étapes El à E3 sont modifiées comme suit: • El : masquer l'opérande A (A' = Ku.B2 * A) par un nombre u égal à deux fois le nombre s, en 10 multipliant l'opérande A par un paramètre Ku.B2, • E2 réaliser une exponentiation modulaire de l'opérande masqué par l'exposant B1, décomposée selon le Théorème des Restes Chinois selon les sous-étapes suivantes : 15 Cp' = (A' mod p) BP1 mod p ; Cq' = (A' mod q) Bql mod q ; C' = Cp' + q*(Iq.(Cp'-Cq') mod p) mod N • E3 : démasquer le résultat de l'exponentiation (Cl), en multipliant le résultat de l'exponentiation (C') 20 par K-2s mod N, où p et q sont deux nombres entiers dont le produit est égal à N (p*q = N), Bpl est égal à Bl modulo p-1, Bql est égal à B1 mod q-1, Iq est égal à q 1 mod p 10. Procédé selon la revendication 9, dans lequel K est 25 égal à 2r, où r est la plus grande taille parmi la taille de p et la taille de q 11. Cryptoprocesseur comprenant notamment un multiplieur de Montgomery pour la mise en oeuvre d'un procédé selon 30 l'une des revendications 2 à 10. 12. Carte à puce comprenant un cryptoprocesseur selon la revendication 11.