Brevet FR2828608A1 — publié le 20030214

PROCEDE SECURISE DE REALISATION D'UNE OPERATION D'EXPONENTIATION MODULAIRE La présente invention concerne un procédé sécurisé pour réaliser une opération d'exponentiation, avec application notamment dans le domaine de la cryptographie. L'invention s'applique en particulier à des algorithmes cryptographiques mis en oeuvre dans des dispositifs électroniques tels que des cartes à puce. De nombreux algorithmes cryptographiques sont basés sur des calculs d'exponentiation du type U = V W modulo X, où U, V et X sont des nombres entiers le plus souvent de grande taille, et W un nombre prédéterminé. Les nombres U, V peuvent correspondre par exemple à un texte chiffré ou à chiffrer, une donnée signée ou à signer, une donnée vérifiée ou à vérifier, etc. Les nombres W et X peuvent correspondrent à des éléments de clés, privées ou publiques utilisées pour le chiffrage ou le déchiffrage des nombres U, V. L'un de ces algorithmes est l'algorithme RSA (de Rivest, Shamir et Adleman), qui permet d'obtenir une signature ou un message déchiffré s à partir d'une clé privée comprenant trois nombres entiers d, p et q, p et q étant des nombres premiers de grande taille dont le produit est égal à N. Dans un exemple typique, d et N sont de 1024 bits, et p et q sont de 512 bits. De nombreux ouvrages présentent en détails l'algorithme RSA, il est cependant nécessaire de rappeler ici les principes de base de cet algorithme, qui permet de calculer la signature s : s = mAd mod (p. q) = mAd mod (N) L'algorithme RSA peut être mis en oeuvre en utilisant le théorème des restes chinois (en anglais Chinese Remainder Theorem). Par l'application de ce théorème, la signature s est obtenue par : s = m'd mod (N) = CRT (sp, Sq) La fonction CRT (sp, Sq) est couramment appelée formule de recombinaison selon le théorème des restes chinois. La fonction CRT se calcule par exemple de la manière suivante : CRT (sp, Sq) = Sp + pxY 1 avec : y = ip (Sq-Sp) mod (q) dp = d mod (p-l) 1 Sp = m^dp mod (p) dq = d mod (q-l), Sq = m'dq mod (q) ip = (1/p) mod (q) Le même algorithme permet de vérifier la validité de la signature s d'un message m en vérifiant que la relation : m = s Ae mod (N) est satisfaite. Les nombres e et N forment la clé publique associée à la clé privée (d, p, q) ; les nombres e et N vérifient les relations : N = pxq pgcd (e, (D (N)) = 1 exd = 1 mod ( (D (N)), (D (N) étant la fonction indicatrice d'Euler définie par (D (N) = (p-l) (q-l). On notera que tous les éléments d, p, q d'une clé privée et tous les éléments e, N d'une clé publique associée sont impairs. En effet p et q étant des grands nombres premiers, ils sont nécessairement impairs. # (N) = (p-1) (q-l) est donc pair et N = pxq est impair. Comme e et (D (N) sont premiers entre eux, e est impair. Comme exd = 1 mod (C (N)), exd est impair, et donc d est également impair. D'autres algorithmes, cryptographiques ou non, utilisent également des opérations d'exponentiation de type U = VAW module X, éventuellement mis en oeuvre par la théorème des restes chinois. Par exemple le cryptosystème de Rabin-Williams ou encore l'échange de clé DiffieHellman modulo un nombre composé. Un utilisateur malveillant peut éventuellement engager des attaques à canaux cachés, visant à découvrir notamment des informations confidentielles (comme par exemple les nombres d ou p) contenues et manipulées dans des traitements effectués par le dispositif de calcul exécutant une opération d'exponentiation. Les attaques à canaux cachés les plus connues sont dites simples ou différentielles. On entend par attaque à canal caché simple ou différentielle, une attaque basée sur une grandeur physique mesurable de l'extérieur du dispositif, et dont l'analyse directe (attaque simple) ou l'analyse selon une méthode statistique (attaque différentielle) permet de découvrir des informations contenues et manipulées dans des traitements réalisés dans le dispositif. Ces attaques peuvent ainsi permettre de découvrir des informations confidentielles. 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 traitement 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. Les algorithmes d'exponentiation précités ont dû inclure des contre-mesures pour empêcher de telles attaques d'aboutir. Paul Kocher a notamment proposé, dans le document WO 99/35782, une méthode qui consiste notamment à masquer les variables dérivées dp, dq du nombre d par l'ajout d'un nombre entier aléatoire. Plus précisément, les variables dp, dq ne sont pas utilisées directement dans l'algorithme, mais elles sont utilisées sous la forme de nombres masqués di* = di + rlx (p-l), avec i égal à p ou q et rl (rp ou rq) des nombres entiers aléatoires, modifiés à chaque mise en oeuvre de l'algorithme. Dans un exemple dévoilé dans le document WO 99/35782, cette méthode est utilisée dans le cadre d'un algorithme RSA mis en oeuvre selon le théorème des restes chinois. L'algorithme se décompose alors de la manière suivante : On calcule tout d'abord sp* et Sq* : sp* = [m"dp*] mod (p) = [mA (dp + rpx (p-l))] mod (p) Sq* = [MA dq*l mod (q) = [m" (dq + ix (p-l))] mod (q) On calcule ensuite le nombre s par la formule de recombinaison : s = s* = CRT (Sp*, Sq*). L'égalité s = s* se déduit de la définition de dp, dql dp*, dq* et du théorème de Fermat, selon lequel A (B-l) = 1 mod (B) lorsque B est un nombre entier premier et que A est relativement premier avec B. Dans le cas présent, on déduit du théorème de Fermat : m'dp* = m (dp + rpx (p-l)) = m"dpXm" (rpX (p-l)) = m"dpxl [mod (p)]. Puisque dp* = [mdj [mod (p)], on a sp = sp*. Un raisonnement similaire permet de déduire Sq = Sq*. Finalement, comme sp = sp* et Sq = Sq*, s = s*. La méthode dévoilée dans le document WO 99/35782 est notamment efficace pour contrer les attaques à canaux cachés différentielles, elle complique également les attaques simples. Cependant, cette méthode n'est pas efficace contre une attaque particulière détaillée ci dessous (que l'on appellera par la suite par souci de simplification attaque CRT) dans le cadre d'un exemple relatif à l'algorithme RSA. Plus généralement, l'attaque CRT peut être envisagée pour tout algorithme mis en oeuvre par l'intermédiaire du théorème des restes chinois. Dans l'exemple d'un algorithme RSA mis en oeuvre à l'aide du théorème des restes chinois, l'attaque CRT permet d'obtenir le nombre p de la clé privée. On a vu précédemment que la formule de recombinaison permettant de calculer s s'écrit : s = CRT (sp, Sq) = Sp + pxY, avec y = ipx (Sq-Sp) mod (q) Si p, q sont de a bits (par exemple 512 bits), alors,ip,Sp,sq sont de a bits, de même que Y. Le produit pxY et le nombre s sont donc de 2a bits. Comme sp est de a bits, on en déduit que les a bits de poids fort de s sont égaux aux a bits de poids fort du produit pxY. Par ailleurs, le poids de Hamming H (Y) du nombre Y peut être obtenu par une attaque à canal caché simple lors du calcul de Y. On rappelle que le poids de Hamming du nombre Y est le nombre de bits à"1"du nombre Y. Connaissant les bits de poids forts du produit pxY et le poids de Hamming du nombre Y, il est possible de retrouver le nombre p par itérations successives de la manière suivante : - on fait une hypothèse sur la valeur de b bits (par exemple b = 8) de poids le plus fort de p et on détermine les b bits du poids fort correspondant de Y à partir des bits de poids fort du produit pxY, lesquels sont donnés par la valeur de s. On calcule ensuite la probabilité pour que l'hypothèse sur les b bits de poids le plus fort de p soit correcte à partir du poids de Hamming de Y, mesuré par un canal caché. - on réitère pour chaque valeur possible des b bits de poids les plus forts de p et on retient finalement l'hypothèse la plus probable pour ces b bits. - on réitère ensuite pour chaque paquet de b bits de p, jusqu'à l'obtention d'un nombre suffisant des bits de p. La méthode dévoilée dans le document WO 99/35782 n'est pas efficace contre cette attaque CRT. En effet, dans le document WO 99/35782, la formule de recombinaison utilisée s'écrit : S = CRT (sp*, Sq*) = Sp* + pxY*, avec s, pxY* de taille 2a bits et Sp* de taille a bits. Il est donc possible, par une attaque CRT telle qu'on vient de la décrire, de déterminer le nombre p à partir du nombre s connu, du produit pxY*, et du poids de Hamming de (Y*). Au vu des limites de la méthode dévoilée dans le document WO 99/35782, un objet de l'invention est de proposer un procédé sécurisé de réalisation d'une opération d'exponentiation, protégé contre toutes les attaques, y compris les attaques CRT telles que décrites ci-dessus. Un autre objet de l'invention est de proposer un procédé sécurisé de réalisation d'une opération d'exponentiation, au moins aussi performant que le procédé dévoilé dans le document WO 99/35782, notamment en terme de taille de circuit et de temps de calcul. Un autre objet de l'invention enfin est de réaliser un procédé sécurisé de calcul d'une opération d'exponentiation, pouvant être incorporé à tout procédé de calcul au cours duquel un calcul du type U = V^W modulo X doit être réalisé. Avec ces objectifs en vue, l'invention a pour objet un procédé sécurisé de réalisation d'une opération d'exponentiation au cours duquel on réalise une opération du type U = VAW modulo X, U, V, X étant des nombres entiers, W étant un nombre entier utilisé sous la forme d'un nombre W* masqué par un paramètre de masquage choisi de manière aléatoire à chaque exécution du procédé. Selon l'invention, le paramètre de masquage est un nombre fractionnaire. Les nombres W, X sont en pratique des nombres qui doivent être maintenus cachés, comme des éléments d'une clé privée, et/ou des nombres dérivés d'une telle clé. Par exemple, si le procédé selon l'invention est utilisé dans le cadre d'un algorithme RSA mis en oeuvre selon le théorème des restes chinois, le nombre W peut être les variables dp, dq utilisées de manière habituelle. La taille des nombres W, X est indifférente, elle est par exemple de 1024 bits. L'utilisation d'un paramètre de masquage aléatoire fractionnaire, au lieu d'un paramètre de masquage aléatoire entier, rend impossible l'obtention d'une information sur le nombre W par un attaque à canaux cachés, ou par une attaque CRT, comme on le verra mieux par la suite dans des exemples. Selon des modes de réalisation préférés, le paramètre de masquage est de la forme R/K. R est un nombre entier aléatoire modifié à chaque exécution du procédé. La taille du nombre R détermine la sécurité de l'algorithme par rapport aux attaques dites différentielles, R peut être choisi par exemple de taille 32 bits. K est un nombre entier diviseur du nombre (D (X), $étant la fonction indicatrice d'Euler. K peut être choisi constant ou bien peut être modifié à chaque exécution du procédé. La taille de K est indifférente, elle est par exemple proche de la taille du nombre R. Avantageusement, le nombre masqué W* est de la forme W* = W + R. W est la partie par défaut du résultat de la division de W par K, et R est égal au produit du paramètre de masquage (R/K) par le nombre (D (X). Le résultat U peut alors être exprimé en fonction de (U*) AK modulo X, avec U* = VW* modulo X. Plus précisément, le résultat U est égal à U = (U*) AK x V Z modulo X, avec U* = VW* modulo X. Z est le reste de la division entière de W par K. Le procédé de l'invention, tel que décrit ci-dessus peut être utilisé avantageusement dans un procédé cryptographique global. Dans un exemple qui sera décrit plus précisément, le procédé cryptographique est de type RSA, et il est mis en oeuvre selon le théorème des restes chinois. Dans ce cas, l'invention est utilisée notamment pour masquer une clé éventuellement dérivée (par exemple les clés dérivées dp, dq) par un paramètre de masquage choisi de manière aléatoire à chaque exécution du procédé, le paramètre de masquage étant un nombre fractionnaire. L'invention a également pour objet un composant électronique comprenant un circuit de calcul pour mettre en oeuvre un procédé selon l'invention, par exemple, mais non nécessairement, dans le cadre d'un algorithme cryptographique. Enfin, l'invention a également pour objet une carte à puce comprenant ledit composant électronique. L'invention et les avantages qui en découlent apparaîtront plus clairement à la lecture de la description qui suit d'un exemple particulier de réalisation de l'invention, donné à titre purement indicatif et en référence à la figure unique en annexe. Celle-ci est un dispositif électronique permettant de mettre en oeuvre l'invention. La figure unique représente sous forme de schéma bloc un dispositif 1 électronique apte à réaliser des calculs d'exponentiation. Dans l'exemple, ce dispositif est une carte à puce destinée à exécuter un programme cryptographique. A cette fin, le dispositif 1 réunit dans une puce des moyens de calcul programmés, composés d'une unité centrale 2 reliée fonctionnellement à un ensemble de mémoires dont : - une mémoire 4 accessible en lecture seulement, dans l'exemple du type ROM masque, aussi connue sous l'appellation anglaise"mask read-only memory (mask ROM)", une mémoire 6 re-programmable électriquement, dans l'exemple du type EEPROM (de l'anglais"electrically erasable programmable ROM"), et - une mémoire de travail 8 accessible en lecture et en écriture, dans l'exemple du type RAM (de l'anglais "random access memory"). Cette mémoire comprend notamment les registres utilisés par le dispositif 1. Le code exécutable correspondant à l'algorithme d'exponentiation est contenu en mémoire programme. Ce code peut en pratique être contenu en mémoire 4, accessible en lecture seulement, et/ou en mémoire 6, réinscriptible. L'unité centrale 2 est reliée à une interface de communication 10 qui assure l'échange de signaux vis-àvis de l'extérieur et l'alimentation de la puce. Cette interface peut comprendre des plots sur la carte pour une connexion dite"à contact"avec un lecteur, et/ou une antenne dans le cas d'une carte dite"sans contact". L'une des fonctions du dispositif 1 est de crypter ou décrypter un message m confidentiel respectivement transmis vers, ou reçu de, l'extérieur. Ce message peut concerner par exemple des codes personnels, des informations médicales, une comptabilité sur des transactions bancaires ou commerciales, des autorisations d'accès à certains services restreints, etc. Une autre fonction est de calculer ou de vérifier une signature numérique. A cette fin, l'unité centrale 2 exécute un algorithme cryptographique, utilisant un calcul d'exponentiation, sur des données de programmation qui sont stockées dans les parties ROM masque 4 et/ou EEPROM 6. Dans l'exemple décrit ici, l'algorithme d'exponentiation est de type RSA, mis en oeuvre par l'utilisation du théorème des restes chinois. L'algorithme est utilisé pour signer un message m à partir d'une clé privée comprenant trois nombres entiers d, p et q. Dans l'exemple, d est de 1024 bits, et p et q sont de 512 bits. Dans l'exemple, on réalise un calcul d'exponentiation s = md mod (p. q), où m est un message prédéterminé et d, p, q des nombres entiers éléments de la clé privée. Le nombre s obtenu constitue une signature du message m. Les nombres d, p, q (éléments de la clé) sont stockés dans une portion de la mémoire re-inscriptible 6, de type EEPROM dans l'exemple. Lorsque le dispositif 1 de calcul d'exponentiation est sollicité pour le calcul d'exponentiation, l'unité centrale mémorise tout d'abord le nombre m, transmis par l'interface de communication 10, en mémoire de travail 8, dans un registre de calcul. L'unité centrale va ensuite lire les clés d, p, q contenues en mémoire reinscriptible 6, pour les mémoriser temporairement, le temps du calcul d'exponentiation, dans un registre de calcul de la mémoire de travail 8. L'unité centrale lance alors l'algorithme d'exponentiation. Selon l'invention, les clés dérivées dp, dq de la clé d sont masquées par un nombre fractionnaire aléatoire de la manière suivante. L'unité centrale choisit tout d'abord un nombre kp diviseur de p-1, et un nombre kq diviseur de q-1, p, q étant des éléments de la clé ; kp, kq sont mémorisés dans un autre registre de calcul de la mémoire de travail 8. Selon le mode de réalisation choisi, kp peut être modifié à chaque mis en oeuvre de l'algorithme ou bien peut être maintenu constant. La taille de kp est indifférente, mais nécessairement inférieure à la taille de p-1. L'unité centrale choisit également deux nombres rp, ra, aléatoires et les mémorise dans deux autres registres de calcul de la mémoire de travail. rp, rq sont de préférence modifiés à chaque mise en oeuvre de l'algorithme. La taille des nombres rp, rq est généralement un compromis entre d'une part la taille de la mémoire 8 dans laquelle ils sont mémorisés et les temps de calcul (qui augmentent avec la taille des nombres rp, rq) et d'autre part la sécurité de l'algorithme (qui augmente également avec la taille des nombres rp, rq). L'unité centrale calcule ensuite les variables dp*, ap, dq*, aq suivantes : dp* = dp + rp, (formule 1) ap = dp mod kp (formule 2) avec dp = Ldp/kpJ et r ? = rpX (p-l)/kp dq* = dq + rq, (formule 3) aq = dq mod kq (formule 4) avec dq = Ldq/kqj et rq = rqx (q-l)/kq dp, ap sont respectivement le résultat et le reste de la division entière de dp par kp dq, aq sont respectivement le résultat et le reste de la division entière de dq par kq L'unité centrale mémorise les variables dp*, api dq aq dans des registres de la mémoire de travail. Par la suite, les variables intermédiaires obtenues tout au long du calcul seront également mémorisées dans une portion de la mémoire de travail 8. L'unité centrale calcule ensuite les variables : sp* = made* mod p Sq* = made* mod q puis la signature s à partir des variables sp*, ap, kpl Sq*, a., k.. Pour cela, l'unité centrale utilise le fait que : sp = [ du*) kip x map] mod (p), (formule 5) Sq = [ (m"dq*) kq x m'asz mod (q), (formule 6) s = CRT (sp, Sq) (formule 7) On notera que les expressions ci-dessus de sp, Sq se déduisent du fait que dp, dq et ap, aq sont définis de sorte que dp = dpxkp + ap et dp = dpxkp + ap 1 ce qui permet d'écrire : s = [m^dp] mod (p) = (m"dp) kp x m'ap mod (p) (p p p P = m (dpxkp) xmap mod (p) = MA (dpxkp) xm" (rpx (p-l)) xmap mod (p) (th. de Fermat) = m [ ( dp+ rp) xkp] xmap mod (p) P P p P = (MA dp*)'kp x m^ap mod (p) = (sp*)"kp x m"ap mod (p). La démonstration de l'exactitude de l'expression pour Sq est bien entendu similaire. Dans un exemple de mise en oeuvre pratique où kp = kq et ap = aq, les égalités 5 et 6 permettent de simplifier l'égalité 7 sous la forme : s = CRT (sp, Sq) = { [CRT (sp*, Sq*)] kkpxm"ap} mod N = { (Sp*+pxY*) Akpxm"ap} mod N (formule 7') = { [CRT (Sp*, Sq*)]"kpxm"ap} mod N Dans un exemple numérique, on choisit kp = kq =2. Dans ce cas, ap = ag = 1 car tous les éléments d'une clé secrète et d'une clé publique associée sont impairs (voir plus haut). En effet, d, p et q étant des nombres impairs, les nombres dp = d mod (p-1) et dq = q mod (q-1) sont également impairs. En conséquence, ap, le reste de la division de dp par kp = 2 est nécessairement égal à 1. Pour les mêmes raisons, aq, le reste de la division de dq par kq = 2 est bien sûr égal à 1. L'égalité 7 est insensible aux attaques à canaux cachés différentielles et simples. En effet, les termes aléatoires dans les nombres sp*, Sq* masquent les données dp, dq, de même que dans le document WO 99/35782. Par ailleurs, l'égalité 7 est insensible aux attaques CRT. Ceci apparaît plus clairement sur la formule simplifiée 7'. La somme sp*+pxY*, indispensable pour mener à bien une attaque CRT, n'apparaît pas directement dans la relation 7', elle apparaît uniquement à la puissance kp. Or, il est conjecturé impossible d'extraire de s une racine kp-ième sans connaître le module N. Il n'est donc pas possible de calculer sp*+pxY*, il n'est donc pas possible d'obtenir les bits de p par une attaque CRT. Un algorithme selon l'invention est donc bien protégé contre toutes ces attaques. REVENDICATIONS 1. Procédé cryptographique sécurisé au cours duquel on réalise une opération d'exponentiation du type U = V"% W modulo X, U, V, X étant des nombres entiers, W étant un nombre entier utilisé sous la forme d'un nombre W* masqué par un paramètre de masquage choisi de manière aléatoire à chaque exécution du procédé, caractérisé en ce que le paramètre de masquage est un nombre fractionnaire. 2. Procédé selon la revendication 1, caractérisé en ce que le paramètre de masquage est de la forme R/K, où R est un nombre entier aléatoire et où K est un nombre entier diviseur du nombre (D (X), (D étant une fonction indicatrice d'Euler. 3. Procédé selon la revendication 2, caractérisé en ce que le nombre K et/ou le nombre R sont modifiés à chaque exécution du procédé. 4. Procédé selon la revendication 2 ou la revendication 3, caractérisé en ce que le nombre masqué W* est de la forme W* = W + R, W étant la partie par défaut du résultat de la division de W par K, et R étant égal au produit du paramètre de masquage R/K par le nombre zu (X). 5. Procédé selon l'une des revendications 2 à 4, caractérisé en ce que le résultat U est fonction de (U*) K modulo X, avec U* = VW* module X. 6. Procédé selon l'une des revendications 1 à 5, caractérisé en ce qu'il est mis en oeuvre selon le théorème des restes chinois, et en ce que le nombre entier w est une clé du procédé, éventuellement dérivée. 7. Procédé selon l'une des revendications 1 à 6, caractérisée en ce qu'il est de type RSA. 8. Composant électronique comprenant un circuit de calcul pour mettre en oeuvre un procédé selon l'une des revendications 1 à 7, le circuit de calcul comprenant notamment une unité centrale (2) associée à une mémoire (4, 6, 8). 9. Carte à puce comprenant un composant électronique selon la revendication 8.