Brevet FR2843507A1 — publié le 20040213

PROCEDE SECURISE DE REALISATION PARALLELE D'UNE EXPONENTIATION MODULAIRE. PROCEDE CRYPTOGRAPHIQUE ET CIRCUIT DE CALCUL ASSOCIES L'invention concerne un procédé sécurisé pour réaliser une exponentiation modulaire du type S = X^Y mod Z; X, Y, Z et S étant respectivement une base, un exposant, un module et un résultat de m bits. Le procédé selon l'invention peut être mis en #uvre dans un circuit de exponentiation comprenant deux registres et deux processeurs travaillant en parallèle. Le procédé selon l'invention est également sécurisé contre les attaques à canaux cachés, notamment en courant, et les attaques par fautes. Il est de ce fait notamment intéressant pour réaliser des opérations dans le cadre de procédés cryptographiques à clé publique. L'invention peut être mise en #uvre par exemple dans des cartes à puce. Les procédés de cryptographie à clé publique sont généralement basés sur des algorithmes d'exponentiation modulaire, de type c = md mod N, où m est selon le cas un message clair, un message chiffré, un message signé ou un message à signer, c est un message chiffré, un message clair, un message à signer ou un message signé et où d et N sont des éléments d'une clé publique ou d'une clé privée associée. Un premier critère de choix d'un algorithme cryptographique est le temps d'exécution de l'algorithme, qui ne doit pas être prohibitif, notamment lorsque des clés de grandes tailles sont utilisées. Un deuxième critère de choix d'un algorithme est sa sécurité (c'est-à-dire sa capacité à maintenir secrètes les clés qu'il utilise, et plus généralement toutes les données qu'il manipule) vis-à-vis d'une attaque extérieure visant à casser l'algorithme (c'est-à-dire à trouver les dites clés). Pour des raisons de sécurité, les éléments des clés publiques ou privées sont en général de grands nombres, par exemple des nombres de 1024 bits. Les algorithmes d'exponentiation modulaire utilisés en cryptographie décomposent en général les données qu'ils utilisent en mots de petite taille, exécutent ensuite une série de multiplications modulaires élémentaires sur des mots appropriés et dans un ordre approprié pour produire des résultats partiels, puis recombinent les résultats partiels obtenus pour fournir le résultat de l'exponentiation réalisée. Une multiplication modulaire élémentaire est une opération de type S = A. B mod Z, où A est un multiplicateur et B est un multiplicande, Z est un module et S est un résultat, tous de même taille m. m est la taille en bits des mots manipulés dans l'algorithme et correspond en pratique à la taille des registres du circuit de multiplication utilisé. Un algorithme connu pour réaliser une exponentiation modulaire à partir de telles multiplications modulaires élémentaires est l'algorithme de Montgomery parallèle qui réalise l'opération : S = f(X,Y,Z) = X^Y mod Z L'algorithme d'exponentiation de Montgomery, est décrit dans [P. Montgomery, Speeding the Pollard and elliptic curve methods of factorization Mathematics of Computation, vol. 48, no. 477, pages 243-267, 1987]. Le fait que cet algorithme puisse être exécuté en parallèle a été noté par plusieurs auteurs ; notamment dans [W. Fischer, C. Giraud, E. W. Knudsen et J.-P. Seifert, Parallel scalar multiplication on general elliptic curves over Fp hedged against non differential side-channel attacks, Report 2002/007, Cryptology ePrint Archive, January 2002 ; disponible à l'URL http://eprint.iacr.org/]. L'algorithme est décrit en termes de courbes elliptiques mais s'applique trivialement à n'importe quel autre groupe abélien. Dans notre cas, nous décrivons l'algorithme parallèle de Montgomery pour le groupe multiplicatif des entiers modulo Z. L'algorithme est dit parallèle car on exécute deux multiplications modulaires en parallèle. Ceci est possible car l'exécution de l'une des instructions n'est pas liée par le résultat de l'autre. Dans un exemple d'utilisation de l'algorithme de Montgomery, Y et Z sont des nombres de m bits d'une clé publique ou privée, X est un nombre de m bits d'un message chiffré, à chiffrer, signé ou à signer, et l'opération S = f(X,Y,Z)= X^Y mod Z est l'opération de base nécessaire pour obtenir un résultat final du type c = m^d mod N. L'algorithme de Montgomery parallèle réalisant S = X^Y mod Z peut s'écrire sous la forme mathématique suivante : Ro RI Ro Le symbole " L'instruction Ra On rappelle que si les opérations Rb.Rc mod Z et Rc.Rb mod Z produisent des résultats identiques, les algorithmes permettant de les réaliser et les circuits utilisés pour mettre en #uvre les algorithmes sont différents. L'algorithme de Montgomery parallèle peut également s'écrire de manière plus générale, mais équivalente : Ro R/YJ R/yj est le registre d' indice /Yj, où Yj est le bit de rang J de l'exposant Y, /Yj étant le bit complémentaire du bit Yj. Par exemple, si Yj = 0 alors /Yj = 1, le registre R/yj est le registre R1 et le registre Ryj est le registre Ro. Mettre en #uvre l'algorithme de Montgomery parallèle nécessite un circuit d'exponentiation comprenant deux processeurs travaillant en parallèle, et réalisant notamment en parallèle des opérations de multiplication de contenus de registres. Cet algorithme est notamment apprécié car il est rapide (de par la présence de deux processeurs travaillant en parallèle) et car il utilise seulement deux registres de calcul Ro et R1 pour réaliser une exponentiation modulaire. S'il est rapide, l'algorithme de Montgomery parallèle connu n'est cependant pas sûr, car il est notamment sensible à une attaque particulière, que nous appellerons "attaque M neutre". De manière générale, une attaque vise à découvrir des données confidentielles, en l'occurrence les éléments d'une clé privée, manipulées dans des traitements effectués par le circuit de calcul. Dans le cas particulier de l'algorithme de Montgomery utilisé dans un procédé cryptographique, une attaque vise à obtenir une information sur les bits de l'exposant Y, qui peut représenter un élément d'une clé privée. L'attaque M neutre consiste à introduire une erreur de registre dans un calcul en cours, c'est-à-dire à modifier, à un instant approprié, la valeur d'un ou plusieurs bits d'un registre de calcul, et à exploiter ensuite les conséquences de l'erreur introduite. L'attaque M neutre et ses effets sont détaillés dans les quelques exemples suivants. On considère dans un premier exemple l'opération Ri bit Ri, de rang I du registre de multiplicande Ri avant utilisation de ce bit pour calculer Ra. Rl mod Z et donc avant mémorisation du résultat de cette opération dans le registre R1. Comme le bit R1,I est faux (i.e. il est égal à la valeur complémentaire fixée par l'attaquant et non à la valeur attendue par l'utilisateur légitime réalisant l'opération) au moment de son utilisation pour calculer Ro.Ri mod Z, le résultat de l'opération RO.RL mod Z est également faux. Le contenu actualisé du registre R1, après mémorisation du résultat de l'opération Ra. Rl mod Z est donc faux. L'erreur introduite par l'attaquant va donc se propager si un calcul suivant est réalisé sur la base du contenu du registre R1. On considère dans un deuxième exemple l'opération : Rl bit Ri, de rang I du registre Ri de multiplicande après utilisation de ce bit pour calculer Ra. Rl mod Z et avant mémorisation du résultat de cette opération dans le registre R1. Comme le bit R1,I est juste (i.e. il est égal à la valeur attendue par l'utilisateur légitime et non à la valeur fixée par un attaquant) au moment de son utilisation pour calculer RO.RL mod Z, le résultat de l'opération Ro.Rl mod Z est également juste. Le contenu actualisé du registre R1, après mémorisation du résultat de l'opération R0.R1 mod Z est donc juste. L'erreur introduite par l'attaquant est donc effacée lors de la mise à jour du registre R1 et elle ne se propage pas si un calcul suivant est réalisé en utilisant le contenu du registre R1. On considère dans un troisième exemple l'opération : Ro Comme le bit R1,I est juste au moment de son utilisation pour calculer R0.R1 mod Z, le résultat de l'opération Ro.Rl mod Z est également juste. Le contenu actualisé du registre Ro, après mémorisation du résultat de l'opération R0.R1 mod Z est donc juste. Par contre, le contenu du registre R1 n'étant pas actualisé à la fin de l'opération Ro.Rl mod Z, l'erreur introduite sur le bit R1,I n'est pas effacée et elle se propage si un calcul suivant est réalisé en utilisant le contenu du registre Ri. On considère dans un quatrième exemple l'opération : si Yj = 0 faire R1 Comme le bit R1,I est juste au moment de son utilisation pour calculer R0.R1 mod Z, le résultat de l'opération Ro.Rl mod Z est également juste. Si Yj = 0, alors le registre R1 est actualisé par le résultat de la multiplication et l'erreur est effacée (cf. 2ème exemple) Par contre, si Yj = 1, alors le contenu du registre R1 n'est pas actualisé et l'erreur va se propager si le registre Ri est utilisé dans une opération suivante (cf. 3ème exemple) . On considère enfin l'algorithme de Montgomery parallèle dans un cinquième et dernier exemple : Ro R/YJ Comme, dans l'itération J = K, le bit R1,I est juste au moment de son utilisation pour calculer R0.R1 mod Z, le résultat de l'opération R0.R1 mod Z est également juste. Si Yj = 0, alors le registre R1 est actualisé par le résultat de la multiplication à la fin de l'itération J = K, l'erreur est ainsi effacée (cf. 2ème exemple) et ne se propage pas à l'itération suivante J = K-1 suivante. Le résultat final, à la fin de l'itération J = 0 sera donc juste, c'est-à-dire égal au résultat légitime attendu. Par contre, si Yj = 1, alors le contenu du registre R1 n'est pas actualisé à la fin de l'itération J = K et l'erreur va se propager à l'itération suivante J = K-1 (cf. 1er et 3ème exemples) . Le résultat final, à la fin de l'itération J = 0 sera donc faux, c'est-à-dire différent du résultat légitime attendu. A noter que quand le bit YJ vaut 0, l'étape RYJ RYJ RYJ mod Z est insensible à une erreur sur le registre R1, puisque le registre R1 n'est pas utilisé dans cette étape. En résumé, si on modifie un bit du registre de multiplicande R1 à un instant approprié, alors, à la fin de l'algorithme, le résultat final de l'exponentiation modulaire renvoyé dans le registre R0 est juste ou faux, selon la valeur du bit Yj associé à l'instant auquel on a modifié le contenu du registre R1. On en déduit immédiatement la valeur du bit Yj. Dans le cas de l'algorithme de Montgomery parallèle, comme on l'a vu dans les exemples précédents, l'instant approprié est, au cours de la réalisation d'une opération de multiplication de contenus de registres, compris entre la fin de l'utilisation du bit qu'on souhaite modifier et le début de la mémorisation du résultat obtenu. Dans la plupart des algorithmes de multiplication modulaire [voir A.J Menezes, P. C. van Oorschot et S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997, chapitre 14.], la multiplication est entrelacée avec la réduction modulaire pour accélérer les calculs. Dans le calcul d'une multiplication de type A. B mod Z, le multiplicande B est découpé en mots de w bits ; ces mots sont ensuite multipliés par le multiplicateur A, réduits modulo Z et ajoutés au résultat courant pour finalement donner la valeur de A. B mod Z. Dans ce type d'algorithme, les mots du multiplicande B ne sont utilisés qu'une seule fois. Cela permet à un attaquant d'introduire une erreur de type M-neutre dans un tel mot après qu'il ait été utilisé par l'algorithme de multiplication modulaire. Pour déterminer si un résultat est juste ou faux, pour un nombre X donné, il est possible par exemple d'effectuer d'abord une première opération X^Y mod Z, pour un nombre X donné, et obtenir un résultat SI ; d'effectuer ensuite une deuxième opération XY mod Z, pour le même nombre X, en modifiant à un instant approprié un bit du registre R1, et obtenir un résultat S2 ; puis finalement de comparer les deux résultats obtenus. Lorsque l'exponentiation modulaire est utilisée pour une opération secrète avec le cryptosystème RSA (déchiffrement ou signature) , il est possible de vérifier l'exactitude de cette exponentiation modulaire avec la clé publique correspondante. Enfin, nous notons que la plupart des systèmes cryptographiques vérifient automatiquement l'exactitude des résultats retournés et renvoie un code d'erreur en cas de faute. Comme on vient de le voir, notamment dans le sème exemple ci-dessus, l'algorithme parallèle de Montgomery connu est sensible aux attaques M neutres. Un but de l'invention est de proposer une variante de l'algorithme parallèle de Montgomery, insensible aux attaques M neutre. Avec cet objectif en vue, l'invention a pour objet un procédé de réalisation d'une exponentiation modulaire de type S = X^Y mod Z où Y est un exposant, à l'aide de deux processeurs pouvant fonctionner en parallèle. Au cours du procédé un premier processeur réalise l'étape ET1 suivante : ET1 : multiplication modulo Z (R/yj.Ryj mod Z) du contenu d'un registre de multiplicateur (R/yj) par le contenu d'un registre de multiplicande (Ryj), et mémorisation d'un résultat dans le registre de multiplicateur (R/yj). Selon l'invention, en fonction d'un bit de rang J de l'exposant Y, on utilise : - le premier registre Ro comme registre de multiplicateur (R/yj) et le deuxième registre R1 comme registre de multiplicande (Ryj) , ou - le deuxième registre R1 comme registre de multiplicateur (R/yj) et le premier registre Ro comme registre de multiplicande (Ryj). Ainsi, avec l'invention, quelle que soit la valeur du bit considéré de l'exposant, le registre contenant le multiplicande n'est jamais remis à jour à la fin de l'étape ET1. En langage mathématique, l'étape ET1 peut s'écrire simplement : R/yj Le procédé selon l'invention est sécurisé contre les attaques M neutres. En effet, même si on modifie un bit du registre de multiplicande après son utilisation pour réaliser la multiplication modulo Z du contenu du registre de multiplicateur R/yj par le contenu du registre de multiplicande Ryj, l'erreur n'est jamais effacée à la fin de l'étape ET1, puisque le contenu du registre de multiplicande, qui contenait une erreur, n'est pas remis à jour lors de la mémorisation du résultat, et ce qu'elle que soit la valeur du bit Yj de l'exposant. L'erreur va alors se propager aux étapes suivantes, donnant lieu au final à une exponentiation modulaire dont le résultat sera faux, quelque soit la valeur du bit Yj. Il n'est donc pas possible de réaliser une attaque M neutre sur le registre de multiplicande au cours d'une étape ET1 dans le but de découvrir la valeur d'un bit de Y. De préférence, le procédé de l'invention comprend également l'étape ET2 suivante, effectuée parallèlement par un deuxième processeur: ET2 : multiplication (Ryj.Ryj mod Z) du contenu du registre de multiplicateur (Ryj) par le contenu du registre de multiplicande (Ryj), et mémorisation d'un résultat dans le même registre (Ryj), Une telle étape ET2 est également insensible aux attaques M neutres, puisqu'une éventuelle modification d'un bit du registre de multiplicande à un instant approprié au cours de la réalisation de la multiplication Ryj.Ryj mod Z n'est jamais effacée lors de la mémorisation du résultat dans le registre Ryj car le registre Ryj est également utilisé comme multiplicateur ; la multiplication sera donc toujours incorrecte. Plus généralement, un procédé selon l'invention comprend les étapes suivantes : EO : mémorisation du nombre "1" dans le premier registre (Ro) et mémorisation du nombre X dans le deuxième registre (R1), El : pour J descendant de m-1 à 0, réalisation de l'étape ET1 et de l'étape ET2 en fonction du bit Yj de rang J du multiplicateur Y, respectivement, par un processeur 1 et un processeur 2, E2 : production du résultat S contenu dans le premier registre (R0). Ceci peut s'écrire, en langage mathématique de la manière suivante : Ro R/yj Les étapes ET1, ET2 sont réalisées en parallèle, respectivement par un premier processeur et un deuxième processeur du circuit de multiplication, le premier processeur et le deuxième processeur utilisant tous deux le premier registre Ro et le deuxième registre R1 du circuit d'exponentiation. L'invention a également pour objet un procédé cryptographique, par exemple à clé publique, au cours duquel met en #uvre un procédé de réalisation d'une exponentiation modulaire tel que décrit ci-dessus. L'invention a encore pour objet un circuit d'exponentiation comprenant un premier registre Ro, un deuxième registre R1, un premier processeur et un deuxième processeur agencés pour mettre en #uvre un procédé de réalisation d'une exponentiation modulaire ou un procédé cryptographique tels que décrit ci-dessus. Enfin, l'invention a pour objet une carte à puce, comprenant un tel circuit d'exponentiation. REVENDICATIONS 1. Procédé de réalisation d'une exponentiation modulaire de type XY mod Z dans un circuit de calcul comprenant un premier processeur et un deuxième processeur, Y étant un exposant, procédé au cours duquel le premier processeur réalise l'étape ET1 suivante : ET1 : multiplication modulo Z (R/yj.Ryj mod Z) du contenu d'un registre de multiplicateur (R/yj) par le contenu d'un registre de multiplicande (Ryj), et mémorisation d'un résultat dans le registre de multiplicateur (R/yj) , le procédé étant caractérisé en ce que, en fonction d'un bit de rang J de l'exposant Y, on utilise : - un premier registre (Ro) comme registre de multiplicateur (R/yj) et un deuxième registre (R1) comme registre de multiplicande (Ryj), ou - le deuxième registre (R1) comme registre de multiplicateur (R/yj) et le premier registre (Ro) comme registre de multiplicande (Ryj). 2. Procédé selon la revendication 1, au cours duquel le deuxième processeur réalise parallèlement l'étape ET2 suivante : ET2 : multiplication (Ryj.Ryj mod Z) du contenu du registre de multiplicande (Ryj) par le contenu du registre de multiplicande (Ryj) en fonction du bit (Yj) de rang J de l'exposant Y, et mémorisation d'un résultat dans le registre de multiplicande (Ryj), 3. Procédé selon la revendication 2, au cours duquel on réalise les étapes suivantes : EO : mémorisation du nombre "1" dans le premier registre (R0) et mémorisation du nombre X dans le deuxième registre (R1), El : pour J descendant de m-1 à 0, réalisation de l'étape ET1 et de l'étape ET2 en fonction du bit Yj de rang J du multiplicateur Y, les étapes ET1 et ET2 étant réalisées en parallèle, respectivement par un premier processeur et un deuxième processeur du circuit d'exponentiation, le premier et le deuxième processeur utilisant tous deux le premier registre (RO) et le deuxième registre (RI) du circuit d'exponentiation. E2 : production du résultat S contenu dans le premier registre (Ro) . 4 Procédé de calcul cryptographique, au cours duquel on met en #uvre un procédé de réalisation d'une exponentiation modulaire selon l'une des revendications 1 à 3. 5 Circuit de calcul comprenant un premier registre (Ro), un deuxième registre (R1), un premier processeur et un deuxième processeur agencés pour mettre en #uvre un procédé selon l'une des revendications 1 à 3. 6 Circuit de calcul comprenant un premier registre (RO), un deuxième registre (R1), un premier processeur et un deuxième processeur agencés pour mettre en #uvre un procédé cryptographique selon la revendication 4. 7 Carte à puce comprenant un circuit de calcul selon la revendication 5 ou la revendication 6.