Brevet FR2847402A1 — publié le 20040521

PROCEDE DE DIVISION ENTIERE SECURISE CONTRE LES ATTAQUES A CANAUX CACHES L'invention concerne un procédé de division entière sécurisé contre les attaques de type à canal caché. L'invention est notamment intéressante pour réaliser des 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 òuvre dans des dispositifs électroniques tels que des cartes à puce. La sécurité des procédés cryptographiques résident 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 l'analyse selon une méthode statistique (attaque différentielle) permet de découvrir des données contenues et 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. 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 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 selon l'instruction. 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 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 cachés. Par contre, aucune étude n'a été faite sur la sécurisation des procédés cryptographiques utilisant comme opération élémentaire une division entière de type q = a div b et r = a mod b, a et b étant deux 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 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 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. Un procédé connu pour mettre en oeuvre une division entière 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é ci-dessous. Etant donné deux données a = (am-1,..., ao) de m bits et b = (bn-1,..., bo) de n bits, n inférieur ou égal à m et bn-1 * 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 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-l et (am-1,.. ., an 1) 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 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-l 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, 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 = (O, am-1,..., am-n+i) Pour j = 1 à (m-n+l), faire a notations suivantes sont utilisées. Le symbole " contenu est appelé y. 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. A est bien sr modifié à chaque itération. a indique si la soustraction a été effectuée à tord ou pas (ie si le bit de quotient doit être égal à 0 ou à 1). -_6 est le complément à 1 (encore appelé négation) 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 de 1 bit dans le registre de m+l 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 de contenu de registre approprié, le 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 contenu d'un registre contenant la donnée b au contenu du registre contant le mot A. Enfin, par abus de langage mais surtout par souci de clarté, on utilisera le même nom pour parler d'un registre et de son contenu. Ainsi le registre A est en fait le registre contenant la donnée A. En résumé, le procédé 1 réalise les étapes suivantes: - si a déterminer bit à bit la valeur des bits de résultat. Un autre procédé également connu pour réaliser des division entière est une variante du procédé "papiercrayon", dite "sans restauration" (NonRestoring Binary Division Algorithm, notamment décrit dans "J.J.F. Cavanagh, Digital Computer Arithmetic, Mac Graw-Hill Company, 1984". Entrée: a = (0, am-l,..., ao) b = (bn- 1..., bo) Sortie: q = a div b et r = a mod b a' G' Fin Pour si (_6 = VRAI) alors A en cours comme dans le cas du procédé 1. Quelle que soit la valeur de a au cours d'une itération, le procédé réalise le même nombre d'opérations au cours de chaque itération. Cette précaution n'est cependant pas suffisante pour protéger le procédé contre les attaques à canal caché. En effet, à chaque itération, on réalise une opération de décalage a ou une soustraction A Or, la réalisation d'une soustraction est plus longue et consomme plus d'énergie que la réalisation d'une opération d'addition. En effet, le plus souvent, les moyens de calcul utilisés pour mettre en oeuvre le procédé ne comprennent pas de circuit de soustraction. L'opération de soustraction est réalisée en calculant d'abord le complément à 2n de b, noté b, puis en additionnant b à A, la retenue éventuelle de l'addition étant mémorisée dans la variable carry. Ce mode de réalisation d'une soustraction est justifié par le fait que, par définition de b, on a b + b = 2n. On a donc A - b = A + b - 2n = A + b mod (2n), mod (2n) étant une réduction modulo 2n. Deux opérations, une opération de complément à 2n et une addition, sont donc en pratique nécessaires pour réaliser une soustraction. Comme les procédés connus de division entière ne sont pas protégés contre les attaques à canal caché, tout procédé cryptographique utilisant les procédés de division entière connu ne sont donc pas plus protégés contre de telles attaques à canal caché. Par ailleurs, statistiquement, 50% des bits du quotient obtenu par un procédé de division sont égaux à 0, ce qui signifie que statistiquement, le procédé compense une soustraction sur deux faite à tord. Le temps d'exécution du procédé 1 est donc statistiquement 1,5 fois plus long que le temps d'exécution du procédé 2. Au vu des problèmes des procédés cryptographiques actuels, un objet essentiel de l'invention est un nouveau procédé de réalisation d'une division entière, protégé contre les attaques à canal caché. Un objet supplémentaire de l'invention est un procédé de réalisation d'une division entière dont le temps d'exécution est très faible. Un objet supplémentaire également de l'invention est un procédé de réalisation d'une division entière au cours duquel seul le registre contenant la donnée initiale a est modifié, remplacé par le quotient et le résultat, tout autre registre de la mémoire (et notamment le registre contenant initialement la donnée b) restant inchangé à la fin de l'exécution du procédé. Avec cet objectif principal et ces objectifs subsidiaires en vue, l'invention propose un procédé cryptographique au cours duquel on réalise une division entière de type q = a div b et r = a mod b, avec a un nombre de m bits, b un nombre de n bits avec n inférieur ou égal à m et bn-1 non nul, bnl étant le bit de poids le plus fort de b, procédé au cours duquel, à chaque itération d'une boucle indicée par i variant entre 1 et m-n+l, on réalise une division partielle d'un mot A de n bits du nombre a par le nombre b pour obtenir un bit du quotient q. Selon l'invention, les mêmes opérations sont réalisées à chaque itération, quelque soit la valeur du bit de quotient obtenu. Ainsi, avec le procédé selon l'invention, il n'est plus possible de déterminer les bits du résultat à partir de la trace laissée lors de l'exécution du procédé de l'invention. Selon un premier mode de réalisation du procédé de l'invention, à chaque itération, on réalise une opération d'addition du nombre b au mot A et une soustraction du nombre b au mot A. Selon ce premier mode de réalisation, le procédé comprend de préférence l'ensemble des étapes suivantes Entrée: a = (0, am.1,..., ao) b = (bn-/,. ., bo) Sortie: q = a div b et r = a mod b a' l'opération ADDn(A, b) lorsque a' vaut 0. Selon un deuxième mode de réalisation du procédé selon l'invention, à chaque itération, on réalise une opération d'addition soit du nombre b soit d'un nombre b complémentaire du nombre b avec le mot A. De préférence, au cours de chaque itération, on réalise également une mise à jour d'une première variable (a') en fonction du bit du quotient produit, la dite première variable (a') indiquant si, lors de l'itération suivante, le nombre b ou le nombre b doit être additionné au mot A. De préférence encore, selon ce mode de réalisation, le procédé comprend l'ensemble des étapes suivantes Entrée a = (0, am-,,..., ao) b = (bn-1,..., bo) Sortie: q = a div b et r =a mod b A = (O, am-l..., am-n+l); 6' ) (a ET carry) E (a' ET carry) lsb(a) donnée fictive. De préférence encore, au cours de chaque itération, on réalise également à chaque itération la mise à jour d'une troisième variable (D) indiquant si la donnée actualisée est égale au nombre b ou au nombre complémentaire b. De préférence encore, selon ce mode de réalisation, le procédé comprend l'ensemble des étapes suivantes Entrée: a = (O, amil,..., ao) b = (bn-1,.. ., bo) Sortie: q a div b and r = a mod b 6' registres pour mémoriser les données a et b. Enfin, l'invention concerne également une carte à puce comprenant un circuit intégré tel que décrit cidessus. L'invention sera mieux comprise et d'autres caractéristiques et avantages apparaîtront à la lecture de la description qui va suivre, d'exemples de réalisation de procédés de division entière selon l'invention. Dans un 1er exemple de mise en òuvre de l'invention, on réalise un procédé sécurisé contre les attaques à canal caché en supprimant les opérations de test (de type si... alors... si non...) du procédé 2 et donc les conséquences de leur présence. Selon l'invention, on remplace, dans le procédé 2, les étapes si... alors. sinon par les trois étapes suivantes: A Le procédé 3 est non seulement équivalent au procédé 2 mais il est également sr vis-à-vis des attaques à canal caché. En effet, le procédé ne contient aucune opération de test de type si... alors... sinon, et les mêmes opérations sont réalisées à chaque itération, quels que soient le bit de la donnée d'entrée utilisé et / ou le bit de résultat obtenu au cours d'une itération. Il est donc impossible, à partir de la trace laissée par le composant, de séparer les différentes itérations et de déterminer les bits de la donnée d'entrée et / ou de la donnée de sortie. Dans un 2ème exemple de mise en oeuvre de l'invention, on modifie le procédé 3 selon l'invention en limitant de plus le temps d'exécution du procédé. Comme on l'a vu précédemment, pour réaliser une opération de soustraction A A Ce qui signifie, pour le procédé 3, qu'à chaque itération une opération de complément à 2n est réalisée, en plus d'une opération d'addition A A Pour diminuer le temps d'exécution, on limite le nombre d'opérations de complément à 2n b d'exécution est encore augmentée. On utilise ici deux registres b et b pour mémoriser respectivement les données b et b et ayant pour adresse baddr et baddr. On appelle d le registre dont le contenu est additionné au contenu du registre A au cours d'une itération donnée et on appelle daddr son adresse. En pratique, à chaque itération, le registre d est soit le registre contenant b soit le registre contenant b. Comme dans le procédé 3, la variable a' est utilisée pour garder une trace de ce qui s'est passé au cours d'une itération donnée et déterminer si une addition ou une soustraction doit être réalisée à l'itération suivante. En regroupant le tout, on obtient finalement le procédé 4 suivant: Entrée: a = (0, aml,..., ao) b = (bn-a,..., bo) Sortie: q = a div b et r = a mod b A = (0, am-l,..., am-n+i); 6' procédé. Pour cela, la valeur b complémentaire de b résultat de l'opération CPL2n(b) est mémorisée à la place de la valeur initiale de b, dans le même registre. L'opération de soustraction est ainsi réalisée en remplaçant b par son complément b dans le même registre puis en additionnant à A le contenu du dit registre. De plus, on évite le calcul de valeurs inutiles de b (c'est le cas lorsque deux itérations successives j et j+l utilisent toutes deux la même addition soit A selon l'invention. On appelle daddr l'adresse du registre contenant la valeur qui sera remplacée par son complément à 2n lors de l'itération en cours: daddr est soit baddr si le contenu du registre contenant initialement b doit être complémenté à 2n, soit caddr sinon. On appelle d le contenu du registre dont l'adresse est daddr. On utilise également des variables I et y pour garder une trace de l'état de la valeur contenue dans les registres localisés à l'adresse baddr et caddr. Cet état est soit la valeur originale soit la valeur originale complémentée à 2n. On choisit P = 1 (resp. y = 1) lorsque la valeur localisée à l'adresse baddr (resp. caddr) est la valeur originale, et P = 0 (resp. Y = 0) lorsque la valeur localisée à l'adresse baddr (resp. caddr)est le complément à 2n de la valeur originale. La variable (' est utilisée pour garder une trace de la valeur de la variable a à l'itération précédente. Comme précédemment, 6' = 0 signifie qu'une soustraction (A non nécessaire a été effectuée à l'itération précédente et qu'une opération d'addition A lors de l'itération en cours. On obtient la table de vérité suivante valeurs précédentes valeurs actualisées a' P 'y Y Y O O O 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 I 0 0 1 1 1 1 0 1 On en déduit d protégés. REVENDICATIONS 1. Procédé cryptographique au cours duquel on réalise une division entière de type q = a div b et r = a mod b, avec q un quotient, a un nombre de m bits, b un nombre de n bits avec n inférieur ou égal à m et bn-j non nul, bn.1 étant le bit de poids le plus fort de b, procédé au cours duquel, à chaque itération d'une boucle indicée par i variant entre 1 et m-n+1, on réalise une division partielle d'un mot A de n bits du nombre a par le nombre b pour obtenir un bit du quotient q, le procédé étant caractérisé en ce que les mêmes opérations sont réalisées à chaque itération, quelque soit la valeur du bit de quotient obtenu. 2. Procédé selon la revendication 1, au cours duquel, à chaque itération, on réalise une addition du nombre b au mot A et une soustraction du nombre b au mot A. 3. Procédé selon l'une des revendications 1 à 2, au cours duquel on réalise l'ensemble des étapes suivantes Entrée: a = (0, am-l,..., ao) b = (bn-1,..., bo) Sortie: q = a div b et r = a mod b A = (0, am.1,..., am-n+i); a' 6' Fin Pour si (-,a = VRAI) alors A produit (lsb(a)). 6. Procédé selon la revendication 4 ou la revendication 5, au cours duquel on réalise l'ensemble des étapes suivantes: Entrée: a = (0, amrl1.. ., ao) b = (bn-1,..., bo) Sortie: q = a div b et r = a mod b A = (0, am1,. , am-n+l); 6' Fin Pour si (-,a = VRAI) alors A actualisée ou sur la donnée fictive. 9. Procédé selon l'une des revendications 7 ou 8, dans lequel on réalise également à chaque itération, une mise à jour d'une troisième variable (p) indiquant si la donnée actualisée est égale à la donnée b ou à son complément à 2n. 10. Procédé selon l'une des revendications 7 à 9, au cours duquel on réalise l'ensemble des étapes suivantes Entrée: a = (0, am-l,..., ao) b = (bn-1,..., bo) Sortie: q a div b and r = a mod b G' 8 daddr l'une des revendications 1 à 11, les moyens de calcul comprenant notamment une unité centrale associée à une mémoire comprenant plusieurs registres pour mémoriser les données a et b. 13. Carte à puce comprenant un circuit intégré selon la revendication 12.