Brevet FR2848753A1 — publié le 20040618

PROCEDE DE DIVISION ENTIERE OU DE REbUCTION MODULAIRE SECURISE CONTRE LES ATTAQUES A CANAUX CACHES L'invention concerne un procédé de division entière ou de réduction modulaire sécurisé contre les attaques à canal caché, et notamment les attaques différentielles. L'invention peut être utilisée pour réaliser des 5 opérations de division dans un procédé cryptographique plus général, par exemple un procédé cryptographique à clé secrète ou publique. Un tel procédé cryptographique peut par exemple être mis en oeuvre dans des dispositifs électroniques tels que des cartes à puce. La sécurité des procédés cryptographiques réside dans leur capacité à maintenir cachées les données confidentielles ou des données dérivées des données confidentielles qu'ils manipulent. Un utilisateur malveillant peut éventuellement engager des attaques, visant à découvrir notamment des données confidentielles contenues et manipulées dans des traitements effectués par le dispositif de calcul exécutant un procédé cryptographique. Parmi les attaques les plus connues, on peut citer les attaques à canaux cachés, simples ou différentielles. On entend par attaque à canal caché une attaque basée sur une grandeur physique mesurable de l'extérieur du dispositif, et dont l'analyse directe (attaque simple) ou 25 l'analyse selon une méthode statistique (attaque différentielle) permet de découvrir des données manipulées dans des traitements réalisés dans le dispositif. Ces attaques ont notamment été dévoilées par Paul Kocher (Advances in Cryptology - CRYPTO'99, vol. 30 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 5 utilisée pour exécuter le calcul, etc. Au cours de l'exécution d'un procédé, 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 10 selon l'instruction. Dit autrement, la trace (c'est-àdire l'évolution dans le temps de la grandeur physique considérée) laissée par le composant exécutant le procédé est différente selon qu'on manipule un bit égal à 1 ou un bit égal à 0. Les attaques à canal caché sont basées sur 15 cette faiblesse des procédés cryptographiques. Les procédés cryptographiques utilisant comme opération de base une opération d'exponentiation modulaire de type Y = XD, X, Y et D étant des nombres 20 entiers ont été très largement étudiés ces dernières années. A titre d'exemple, on peut citer le procédé RSA, l'échange de clé selon Diffie-Hellman ou le procédé de signature DSA. Des progrès significatifs ont été réalisés pour protéger ces procédés contre les attaques à canaux 25 cachés. Par contre, certains procédés cryptographiques utilisent comme opération élémentaire une division entière de type q = a div b et / ou une réduction modulaire de type r = a mod b, a et b étant deux 30 opérandes, q et r étant respectivement le quotient et le reste de la division entière de a par b. a et / ou b sont des données secrètes, par exemple des éléments d'une clé du procédé. Par exemple, le procédé de Barrett (P. Barret, "Implementing the RSA public key encryption 35 algorithm on a standard digital signal processing", vol 263 of Lecture Notes in Computer Science, pp. 311-323, Springer Verlag, 1987), le procédé de Quisquater (US patent 5,166,978, nov 92) ou le procédé RSA mis en oeuvre selon le théorème des restes chinois (JJ Quisquater and C Couvreur, "Fast decipherment algorithm for RSA public key 5 cryptosystem", Electronics Letters, vol 18, pp. 905-907, Octobre 1982) sont des procédés cryptographiques utilisant une division entière comme opération élémentaire. De tels procédés cryptographiques utilisant un 10 procédé de division entière et / ou un procédé de réduction modulaire sont sensibles aux attaques à canal caché, comme on va le voir dans l'exemple ci-dessous. Un procédé connu pour mettre en oeuvre à la fois une 15 division entière et une réduction modulaire est le procédé dit "papier crayon". Ce procédé reprend en pratique la méthode utilisée lorsqu'une telle opération est réalisée à la main. Ce procédé est rappelé cidessous. Etant donné deux données a = (am-1, ..., a0) de m bits et b = (bn-1, ..., b0) de n bits, n inférieur ou égal à m et bn-1 t 0, le procédé de division dit "papier crayon" calcule le quotient q = a div b et le reste r = a div b. Pour cela, le procédé réalise successivement 25 plusieurs divisions d'un entier A de n+l bits par l'entier b de n bits. On doit avoir en pratique 0 Le reste r est un nombre de au plus n bits puisque r bn-1*2n-1l et (am_-l, ..., an1) est un nombre de m-n+l bits. A la fin du procédé de division, le quotient q est mémorisé dans les m-n+l bits de poids les plus faibles du registre contenant 35 initialement le nombre a. Le bit de poids le plus fort du reste r est mémorisé dans un registre de 1 bit utilisé comme retenue (carry) pendant le calcul et les n-l bits de poids les plus faibles du reste r sont mémorisés dans les n-i bits de poids les plus forts du registre contenant initialement le nombre a. Comme on travaille en base 2, le bit de quotient de la division entière A div b a seulement deux valeurs possibles: 0 ou 1. Aussi une manière simple de réaliser l'opération A div b consiste à soustraire b à A puis à tester le résultat: si le résultat de A - b est positif, 10 alors A div b = 1, si le résultat de A - b est strictement négatif, alors A div b = 0. Le procédé de division complet peut alors s'écrire de la manière suivante: Entrée: a = (0, am-l..., ao) b = (bn-1, ..., bo) Sortie: q = a div b et r =a mod b A = (0, am-l, ..., am-n+l) Pour j = i à (m-n+l), faire 20 a Par abus de langage mais surtout par souci de 30 clarté, et sauf précision explicite, on utilisera le même nom pour parler d'un registre et de son contenu. Ainsi on parlera du registre A pour parler du registre contenant la donnée A. Le symbole " A est un mot de n bits correspondant au contenu des n bits de poids les plus forts du registre contenant initialement la donnée a. Le registre A est bien sr modifié à chaque itération, de même que le registre contenant initialement a. a indique si la soustraction a été effectuée à tort ou pas (ie si le bit de quotient doit être égal à 0 ou à 1). -- est le complément à 1 (encore appelé négation) 10 de la variable a. VRAI est une constante, égale à 1 dans un exemple. lsb(a) est le bit de poids le plus faible du nombre a, également appelé bit le moins significatif de a. SHLm+i(a, 1) est une opération de décalage à gauche 15 de 1 bit dans le registre de m+1 bits contenant la donnée a, le bit sortant du registre étant mémorisé dans la variable carry et un bit égal à 0 étant entré en bit de poids le plus faible du registre contenant initialement la donnée a. ADDn(A, b) est une opération d'addition des n bits du nombre b aux n bits du mot A. On notera que l'opération SHLn(a, 1) est équivalente à l'opération ADDn(a, a). Bien sr l'addition ADDn(A, b) est réalisée en additionnant, dans un circuit d'addition approprié, le 25 contenu de deux registres contenant respectivement A et b. SUBn(A, b) est une opération de soustraction du nombre b au mot A. Bien sr la soustraction SUBn(A, b) est réalisée en soustrayant, dans un circuit approprié, le 30 contenu d'un registre contenant la donnée b au contenu du registre contenant le mot A. En résumé, le procédé 1 réalise les étapes suivantes: - si a Le procédé 1 permet d'obtenir à la fois le résultat de la division entière (q = a div b) et le reste de la division entière (r = a mod b) qui est aussi le résultat d'une réduction modulaire. D'autres procédés connus 35 présentant les mêmes inconvénients réalisent soit une division modulaire seule, soit une réduction modulaire seule. De manière générale, un procédé de division est assez similaire à un procédé de réduction modulaire. Un but de l'invention est de sécuriser un procédé 5 de mise en oeuvre d'une division et / ou d'une réduction modulaire. Dans ce but, l'invention propose un procédé cryptographique au cours duquel on réalise une division entière de type q = a div b et / ou une réduction 10 modulaire de type r = a mod b, avec q un quotient, a un nombre de m bits, b un nombre de n bits, n inférieur ou égal à m et bn-1 non nul, bn-1 étant le bit de poids le plus fort du nombre b. Selon l'invention, le procédé est caractérisé en ce 15 qu'on masque le nombre a par un nombre aléatoire p avant de réaliser la division entière et / ou la réduction modulaire. Le nombre a étant masqué par un nombre aléatoire, la trace (par exemple la consommation énergétique) 20 laissée lors de l'exécution du procédé est différente à chaque exécution, de sorte qu'il n'est plus possible de mettre en oeuvre une attaque à canal caché différentielle. L'invention peut être appliquée par exemple au procédé 1 qui réalise à la fois une division et une 25 réduction modulaire. L'invention peut être plus généralement appliquée à tout procédé qui réalise l'une ou l'autre des ces opérations. Le nombre aléatoire p peut être modifié à chaque exécution du procédé, ou bien simplement après un nombre 30 prédéfini d'exécutions du procédé. Le cas échéant, le dit nombre prédéfini est choisi de préférence relativement petit, par exemple un nombre de 32 à 64 bits. Selon un mode de réalisation préféré de l'invention, pour masquer le nombre a, on ajoute, au 35 nombre a, b fois le nombre aléatoire (a Puis, on réalise ensuite la division entière et / ou la réduction modulaire souhaitée. Dans le cas o une division entière est réalisée, le résultat de la division entière réalisée avec le nombre a masqué sous la forme a + b*p est égal à 10 a div b + p. Dans ce cas, après la division entière, on enlève au résultat de la division entière la contribution apportée par le nombre aléatoire p pour retrouver le résultat attendu de la division entière sur le nombre a, c'est-à-dire a div b. Dans le cas o réduction modulaire est réalisée, le résultat de l'opération (a + b*p) mod b est égal à a mod b, résultat attendu de la réduction modulaire sur le nombre a. L'invention concerne également un composant électronique comprenant des moyens pour la mise en òuvre d'un procédé selon l'invention, tel que décrit ci-dessus. Les moyens de calcul programmés comprennent notamment plusieurs registres pour mémoriser les nombres a et b. Enfin, l'invention concerne une carte à puce comprenant un composant ayant les caractéristiques décrites ci-dessus. REVENDICATIONS 1. Procédé cryptographique au cours duquel on réalise une division entière de type q = a div b et / ou une réduction modulaire de type r = a mod b, avec q un quotient, a un nombre de m bits, b un nombre de n bits, n 5 inférieur ou égal à m et bn-1 non nul, bn-1 étant le bit de poids le plus fort du nombre b, caractérisé en ce qu'on masque le nombre a par un nombre aléatoire p avant de réaliser la division entière et / ou la réduction modulaire. 2. Procédé selon la revendication 1, au cours duquel, pour masquer le nombre a, on ajoute au nombre a, b fois le nombre aléatoire p (a 3. Procédé selon la revendication 1 ou la revendication 2, dans lequel, après avoir réalisé une division entière, on enlève au résultat de la division entière la contribution apportée par le nombre aléatoire p 4. Procédé selon la revendication 3 en combinaison avec la revendication 2, au cours duquel, pour enlever la contribution apportée par le nombre aléatoire p, on soustrait le dit nombre aléatoire p au résultat de la 25 division entière. 5. Procédé selon l'une des revendications 1 à 4, au cours duquel le nombre aléatoire p est modifié à chaque mise en oeuvre du procédé. 6. Procédé selon l'une des revendications 1 à 4, au cours duquel le nombre aléatoire p est modifié après un nombre prédéterminé de mise en oeuvre du procédé. 7. Composant électronique comprenant des moyens pour la mise en oeuvre d'un procédé selon l'une des revendication précédente, les moyens de calcul programmés 5 comprenant notamment plusieurs registres pour mémoriser les nombres a et b. 8. Carte à puce comprenant un composant selon la revendication précédente.