Brevet FR2917197A1 — publié le 20081212

Procédé de masquage du résultat d'une opération de multiplication modulaire et dispositif associé La présente invention concerne un procédé de masquage du résultat d'une opération de multiplication modulaire et le dispositif associé. Elle s'applique notamment à la sécurisation des processeurs dédiés aux calculs cryptographiques. Un but de la cryptographie est de chiffrer des données sensibles à l'aide d'un élément secret, généralement une clé cryptographique. La valeur de la clé doit être impérativement protégée pour éviter la divulgation des données sensibles. Les algorithmes cryptographiques sont conçus pour que la clé ne puisse pas être retrouvée en pratique. Théoriquement, la recherche de la clé nécessite des moyens de calcul difficilement à la portée d'un gouvernement et un temps de calcul dépassant l'échelle humaine. Néanmoins, certains attaquants ont contourné ces difficultés d'ordre mathématique pour permettre de trouver la valeur de la clé via des mesures physiques. Ainsi, une méthode utilisée est l'attaque par canaux auxiliaires. Il s'agit de mesurer le comportement d'un bloc de calcul cryptographique pendant l'utilisation de la clé. En effet, certaines opérations sont effectuées en fonction de la valeur de la clé. Or, des grandeurs physiques évoluent selon les opérations effectuées par le bloc de calcul et des données mises en jeu lors de ces opérations. Par exemple, la mesure de la consommation électrique d'un circuit, du temps de calcul ou du rayonnement électromagnétique produit par un composant permet de retrouver certaines opérations effectuées ou certaines données manipulées. Une analyse de ces mesures peut donc conduire à trouver la valeur de la clé utilisée. Afin de protéger les systèmes de sécurité mettant en oeuvre des procédés de cryptographie asymétrique, il est souhaitable de rendre ce type d'attaques au moins aussi difficile à réaliser que les attaques cryptographiques classiques. Des solutions connues permettent de diminuer l'efficacité de ces attaques, sans pouvoir cependant les empêcher. Ces solutions peuvent impliquer des modifications de l'algorithme de calcul et/ou des données manipulées afin que les mesures de grandeurs physiques révèlent le moins d'informations possible sur les opérations réalisées par le bloc de calcul. Plusieurs catégories de méthodes de protection ont été établies. Une prernière catégorie concerne l'ajout de blocs de calcul fantôme. Ces blocs particuliers n'interviennent pas dans le calcul mais modifient la consommation électrique et/ou le rayonnement électromagnétique. Ce type de contre-mesures n'est pas totalement efficace car un traitement des mesures permet de supprimer l'influence de ces blocs de calcul fantôme, et ainsi de les ignorer. Une deuxième catégorie de méthodes de protection permet 10 d'éviter que l'exécution de l'algorithme soit dépendante de la valeur de la clé. Cette méthode s'avère nécessaire mais non suffisante. Une troisième catégorie introduit une perturbation aléatoire des données. Cette méthode de protection est généralement qualifiée de masquage . II s'agit de manipuler les données n'ayant, a priori, aucun 15 rapport avec les données claires ou chiffrées en vue de diminuer la corrélation entre les mesures et les données connues. La mise en oeuvre de ces méthodes de protection s'accompagne inévitablement de quelques inconvénients. D'une part, elle entraîne une augmentation du temps de calcul et/ou de la taille du code pour les 20 réalisations logicielles, ou de la surface de circuits pour les réalisations matérielles. D'autre part, la mise en oeuvre des algorithmes cryptographiques dans un système de calcul est généralement effectuée par couches. Des blocs de calcul élémentaires sont utilisés par des algorithmes de plus haut niveau, eux-mêmes utilisés pour la mise en oeuvre d'algorithmes 25 cryptographiques. La modification d'un bloc élémentaire peut donc engendrer des comportements inattendus, voire erronés, dans certains algorithmes de plus haut niveau utilisant ce bloc élémentaire modifié. Afin d'éviter ces erreurs, certaines adaptations au niveau des algorithmes et/ou de l'architecture du système de calcul sont parfois nécessaires. L'intégration 30 d'un bloc élémentaire modifié est ainsi rendue complexe, du fait des nombreux impacts sur les couches algorithmiques supérieures. A titre d'illustration, l'appel au masquage multiplicatif est couramment employé car il semble naturel en matière de cryptographie asymétrique. Classiquement, les calculs sont effectués dans un anneau 35 modulaire de congruence n. Le masquage multiplicatif se traduit, lors de l'exécution d'un algorithme, par la manipulation d'un nombre x' égal à ((x • r) modulo n) au lieu de manipuler le nombre (x modulo n), r étant un aléa et n étant le module. Cependant, le masquage multiplicatif comporte plusieurs inconvénients. D'une part, il nécessite une division supplémentaire permettant de retrouver le résultat attendu. Or, l'opération de division est coûteuse en temps de calcul et en ressources matérielles. D'autre part, l'aléa r est fixé pour toute la durée d'exécution d'un l'algorithme, ce qui peut faire émerger une faiblesse exploitable par un attaquant. De plus, lors de l'utilisation par un algorithme de certaines courbes elliptiques, d'autres vulnérabilités peuvent apparaître avec le masquage multiplicatif, notamment lorsque qu'un attaquant choisit un point de coordonnées nulles sur ladite courbe. Une autre méthode de masquage connue est l'exécution des algorithmes dans un anneau modulaire de congruence k.n, k étant un entier naturel. Cependant, l'augmentation de la taille du module utilisé pour les calculs nécessite un dimensionnement plus élevé des ressources logicielles et/ou matérielles mises en oeuvre. Un autre procédé de masquage a été divulgué dans une demande de brevet européen publiée sous le numéro EP1239364. Il s'agit d'une technique de double multiplication dont une est masquée. Cette solution, tout comme les précédentes, ne s'intègre pas aisément dans un système de calcul existant et multicouches. En effet, elle implique notamment des modifications dans les algorithmes utilisés par les fonctions cryptographiques. Une des opérations de base utilisée par les algorithmes de cryptographie asymétrique est la multiplication modulaire. Cette opération permettant de calculer un produit modulo n de deux entiers, est utilisée par un grand nombre d'algorithmes. II est donc souhaitable d'y introduire une protection contre les attaques par canaux auxiliaires. Par ailleurs, une contrainte supplémentaire à satisfaire est la flexibilité de la solution, c'est à dire l'aptitude à traiter des nombres de tailles variables. Un but de l'invention est la mise en oeuvre, au niveau de l'opération de multiplication modulaire, d'une méthode de protection entraînant un faible surcoût de temps de calcul, requérant très peu de ressources matérielles supplémentaires, et sans impact sur les algorithmes de plus haut niveau. A cet effet, l'invention a pour objet un procédé de masquage des résultats issus d'une opération de multiplication modulaire en congruence n, caractérisé en ce qu'il comporte au moins une étape permettant de générer un nombre pseudo-aléatoire z et une étape ajoutant au résultat le produit dudit nombre z par n. La multiplication modulaire peut comporter les étapes du procédé de multiplication de Montgomery. Selon un mode de réalisation, la multiplication modulaire est effectuée en base de numération élevée, supérieure ou égale à 4. Selon un mode de réalisation, le nombre pseudo-aléatoire z est calculé en fonction des opérandes d'entrée x, y de la multiplication. Selon un mode de réalisation dans lequel le nombre x est formé par les mots-machine xo xi ... xtn et le nombre y est formé par les mots-machine yo yi • • • ytn, le mot pseudo-aléatoire z est égal à xo xor xi xor ... xor xtn xor yo xor yi xor ... xor ytn, xor désignant l'opération de ou exclusif binaire. L'invention a également pour objet l'utilisation du procédé de masquage décrit plus haut dans un composant cryptographique. D'autres caractéristiques apparaîtront à la lecture de la description 20 détaillée donnée à titre d'exemple et non limitative qui suit faite en regard de dessins annexés qui représentent : la figure 1, un exemple de cellule de multiplication-addition utilisée dans la multiplication modulaire masquée selon l'invention, la figure 2, un synoptique d'utilisation d'un multiplieur mettant en 25 oeuvre le procédé de masquage selon l'invention par un algorithme faisant appel à l'opération de multiplication modulaire. Le multiplieur selon l'invention est implémenté en matériel sur ASIC (Application-Specific Integrated Circuit) ou FPGA (Field-Programmable Gate Array) et fonctionne sur un bus de données de b bits. 30 Un nombre de b bits est qualifié par la suite de mot machine . La taille de bus est souvent une puissance de 2. La base de numération r est définie comme étant égale à 2b. Le module n est un nombre impair enregistré sur tn mots machine. Enfin, on définit R comme une puissance de la base de numération, R étant supérieur au module n. Un nombre x peut se 35 décomposer dans la base r en t+1 chiffres x; comme suit : x=xo+xt.r+x2.r2+ ... +xt.rt, où chaque chiffre x; est de la taille d'un mot machine. Le multiplieur selon l'invention, à partir de deux nombres x et y, permet de calculer x.y.R"' mod n + e.n, où e est une valeur dépendant de x et y, et comprise entre 0 et r/2. L'opération x.y.R"' mod n est la multiplication modulaire de Montgomery. Le multiplieur effectue donc une multiplication modulaire de Montgomery et un masquage additif du résultat de cette multiplication. Comme la valeur e dépend de x et y, lorsque les valeurs d'entrée x et y sont déjà masquées par une valeur aléatoire avant d'être utilisées par le multiplieur, le résultat est lui aussi masqué par une valeur aléatoire. Le multiplieur permet donc de propager le masquage des données d'entrée. Selon une variante de réalisation, la valeur e dépend d'une variable aléatoire indépendante de x et de y. Avant d'effectuer des multiplications, une valeur, notée n', est précalculée : n' = -n-' mod r. Le résultat de la multiplication est noté S. Les chiffres d'un nombre N dans la base r sont notés Ni. Le calcul de la multiplication modulaire de Montgomery avec masquage additif du résultat est réalisé par le procédé suivant : i. S L'étape (ii. b.) (S(-x;.y + (m;.n+S)/r) est la plus coûteuse en temps de calcul. Elle peut être réalisée par l'enchaînement de deux opérations de multiplication-addition, ^ la première multiplication-addition étant S (m;.n+S)/r, ^ et la seconde multiplication-addition étant SE-x;.y + S. Chaque multiplication-addition est effectuée par une boucle, la première multiplication-addition se différenciant de la seconde par une division par r. Selon un mode de réalisation, la boucle effectuée par la seconde multiplication-addition est la suivante : 1 o c=O Pour j allant de 0 à tri faire : P p;q+vj+c si LSB(P) c MSB(P) 15 sn+1=c s désignant le résultat de la multiplication-addition p;.q +v, et c une variable de retenue. Lors de l'étape (ii. b.) de la multiplication modulaire, la valeur p; est remplacée par x;, la valeur q est remplacée par y et la valeur v est remplacé 20 par S. L'opération de base P p;qi+vj+c est réalisée avec p;, qi, v1, c compris entre 0 et r-1. Le résultat intermédiaire P est donc compris entre 0 et r2-1, et exprimé sur deux chiffres. La notation LSB(P) désigne le chiffre de poids faible, et MSB(P) le chiffre de poids fort du nombre P. Sur la dernière itération de la boucle (lorsque j=n), contrairement à 25 une multiplication-addition opérant sur des nombres non masqués, où bn serait inférieur ou égal à 1, la multiplication-addition mise en oeuvre par le dispositif selon l'invention effectue une opération sur un chiffre bä compris entre 0 et r/2. Ainsi, la valeur sn+1 peut être supérieure à 2. La première multiplication-addition S (m;.n+S)/r est effectuée de 30 manière similaire par rapport à la seconde multiplication-addition mais comprend également un décalage du résultat de b bits vers le bit de poids faible. Ce décalage équivaut à une division par r. La multiplication-addition avec décalage est effectuée comme suit : c=O 35 Pour j allant de 0 à tri faire : P - p;qi+vi+c si_1 LSB(P) c MSB(P) sn=c+vn+1 Lors de l'étape (ii. b.) de la multiplication modulaire, la valeur p; est remplacée par m;, la valeur q est remplacée par n et la valeur v est remplacé par S. Ainsi, pour l'itération j=tn, ni=0 par définition de tn, donc P 2(r-1), ce qui implique MSB(P) 1. La boucle est donc, à un décalage d'indice près, proche de la boucle correspondant à la seconde multiplication-addition, ce qui permet d'envisager la réalisation d'un composant capable d'effectuer les deux boucles. Un multiplieur peut notamment scinder l'opération pigi+vi+c en (p;qi+vi)+c, en pipelinant l'opération de multiplication-addition (p;qi+vi) et en ajoutant, à mesure que les résultats sont obtenus, la variable c. La figure 1 est un exemple de cellule de multiplication-addition utilisée dans la multiplication modulaire masquée selon l'invention. La cellule permet de calculer les deux opérations de multiplication-addition décrites plus haut. Elle est pipelinée pour améliorer ses performances. Le pipeline consiste à rajouter des barrières de registres entre les phases logiques afin de réduire le chemin critique, et ainsi d'augmenter la fréquence maximale de fonctionnement (théoriquement celle d'un additionneur en base r). On définit la profondeur de pipeline d'un composant élémentaire par son nombre de registres internes. On ne compte pas le registre de sortie. L'exemple donné à la figure 1 suppose que l'on dispose d'un multiplieur-additionneur 1 pipeliné, de profondeur p. II comporte notamment un ensemble de couples logique-registre (Ii, ri). Le nombre p de ces couples est notamment choisi pour que la fréquence maximale F1 max du multiplieur-additionneur pipeliné soit supérieure ou égale à la fréquence maximale F2max de l'additionneur, les valeurs de ces deux fréquences étant les plus proches possibles. La fréquence maximale de fonctionnement du multiplieur-additionneur est donnée par l'inverse du temps d'exécution de l'opération de multiplication-addition, alors que la fréquence maximale de fonctionnement du multiplieur-additionneur pipeliné est donné par l'inverse du temps d'exécution d'un seul des p étages. Pour un fonctionnement optimal, on détermine la fréquence maximale de l'additionneur, ce qui donne le temps d'exécution de l'additionneur et on découpe le multiplieur-additionneur en p étages de temps de traversée inférieur ou égal, mais le plus proche possible, au temps d'exécution de l'additionneur. Les entrées du multiplieur-additionneur 1 correspondent à trois chiffres : pi, qi et vi et la sortie est un couple de chiffres correspondant à LSB(p;gi+v1) et MSB(p;qi+vi). La sortie tient sur deux chiffres. Les résultats du multiplieur-additionneur sont transmis à un 10 additionneur trois entrées, référencé 2 : chiffre+chiffre+carry ù chiffre+carry, fonctionnant en 1 cycle (pipeline 0) à la fréquence F2max. Le registre Temp correspond au stockage de c nécessaire au calcul suivant : addition de c avec le LSB suivant et la retenue précédente. Les données (chiffres de pxQ +V) sortent donc en série à chaque 15 cycle, chiffre de poids faible en tête, dans le même sens que la propagation de la retenue. L'opération sn=c+vn+1 peut être effectuée par un additionneur, non représenté sur la figure, additionneur sur b-1 bits + 1 bit = b bits et non pas 2 bits +1 bits = 3 bits, comme dans un dispositif classique, puisque vn+1 peut 20 être supérieur à 2. Les autres étapes du procédé de multiplication modulaire de Montgomery avec masquage additif du résultat peuvent être effectuées en utilisant des multiplexeurs et registres classiques. Un multiplieur permettant d'effectuer une multiplication modulaire selon la méthode de Montgomery est 25 décrit dans la demande de brevet publiée sous le numéro WO2006103288. Les étapes du procédé de masquage selon l'invention peuvent être aisément mises en oeuvre dans un dispositif comportant une cellule de multiplication-addition tel que décrit plus haut. La génération du nombre pseudo-aléatoire z peut être réalisée par un composant logique à deux 30 entrées et une sortie, la première entrée permettant de recevoir la première opérande x à multiplier, la seconde entrée permettant de recevoir la seconde opérande y à multiplier, et la sortie produisant une combinaison de x et y, par exemple, un nombre égal à x xor y, la notation xor désignant l'opération de OU exclusif binaire. Le nombre pseudo-aléatoire z issu de ce composant logique peut alors être combiné avec n dans un multiplieur pour fournir un multiple pseuso-aléatoire de n, égal à z.n. La figure 2 est un synoptique d'utilisation d'un multiplieur mettant en oeuvre le procédé de masquage selon l'invention par un algorithme faisant appel à l'opération de multiplication modulaire. Au cours de l'exécution de l'algorithme, toutes Nes multiplications effectuées opèrent sur des nombres, tous obtenus à partir de quelques valeurs initiales fixées. A titre d'exemple, quatre valeurs initiales notées h, x, d, et s sont utilisées pour générer toutes les autres valeurs utilisées dans les algorithmes. Lors d'une première étape 21, un masquage additif est opéré sur ces valeurs initiales h, x, d, et s. Ainsi, des valeurs masquées hm, xm, dm, et sm sont obtenues comme suit : hm=h+eh.n ; xm= ex.n ; dm=ed.n ; sm=es.n ; où eh, ex, ed, es, sont des valeurs aléatoires comprises entre 0 et 2P. En pratique, la valeur p est de préférence au moins égale à 63 pour que le masquage additif soit efficace. Lors d'une deuxième étape 22, l'algorithme est exécuté en faisant appel, autant de fois que nécessaire, au multiplieur selon l'invention. Aucune modification de l'algorithme n'est requise, et tous les résultats produits par le multiplieur selon l'invention sont masqués, ce qui permet à l'algorithme de ne manipuler que des données masquées. Lors d'une troisième étape 23, après l'exécution de l'algorithme, une opération de démasquage est appliquée sur les valeurs masquées 231 pour retrouver les résultats qui auraient été obtenus sans masquage. Cette opération peut, par exemple, être réalisée par le multiplieur selon l'invention en choisissant des valeurs d'entrée particulières. L'utilisation du dispositif illustrée en figure 2 montre que les valeurs utilisées dans les calculs sont décorrelées des valeurs initiales. Par conséquent, un attaquant analysant des grandeurs physiques pendant l'exécution de l'algorithme ne peut donc plus, en choisissant judicieusement les variables d'entrée, retrouver les données secrètes utilisées pendant le calcul. Par exemple, sur un dispositif classique, un attaquant peut choisir une variable d'entrée comportant un grand nombre de '0' ou un grand nombre de '1', puis analyser la consommation électrique pour déterminer une relation entre les variables d'entrée et la consommation et/ou déduire le type d'opérations effectuées par l'algorithme. Grâce à l'utilisation du masquage additif, ces longues chaînes initiales de `0' ou de `1' sont éliminées dans les opérandes utilisés par l'algorithme, affaiblissant ainsi les hypothèses que l'attaquant a pu faire vis à vis des variables d'entrées qu'il a lui-même choisi. Le surcoût en temps de calcul et, dans le cas d'une intégration matérielle, en surface de circuit, est très faible. Avantageusement, le bloc multiplieur permet d'exécuter les algorithmes sur des nombres de taille quelconque sans modifier l'implémentation matérielle. Ainsi, un multiplieur synthétisé en FPGA ou ASIC et réalisé selon l'invention permet d'exécuter des multiplications indifféremment sur des modules de taille 128, 256, 512, 1024, et 2048 bits, par exemple. Un avantage du procédé selon l'invention est qu'il peut être mis en oeuvre dans un composant de calcul cryptographique existant de manière transparente vis à vis de l'architecture du composant. En effet, il suffit de remplacer l'opérateur de calcul de multiplication modulaire classique par un opérateur mettant en oeuvre le procédé selon l'invention. Le remplacement de cette opération élémentaire se traduit alors par une amélioration globale de la protection du composant, puisque les fonctions utilisées par les mécanismes de sécurité tels que le chiffrement ou l'authentification font appel à l'opérateur selon l'invention. REVENDICATIONS 1. Procédé de masquage des résultats issus d'une opération de multiplication modulaire en congruence n, caractérisé en ce qu'il comporte au moins une étape permettant de générer un nombre pseudo-aléatoire z et une étape ajoutant le produit dudit nombre z par n au résultat de l'opération de multiplication modulaire. 2. Procédé selon la revendication 1, caractérisé en ce que la multiplication modulaire utilise un procédé de multiplication de Montgomery. 3. Procédé selon la revendication 2, caractérisé en ce que la multiplication modulaire est effectuée en base de numération élevée, supérieure ou égale à 4. 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que le nombre pseudo-aléatoire z est calculé en fonction des opérandes d'entrée x, y de la multiplication. 20 5. Procédé selon la revendication 4, le nombre x étant formé par les mots-machine xo xi ... xt,,, et le nombre y étant formé par les mots-machine yo yi ... ytn, caractérisé en ce que le mot pseudo-aléatoire z est égal à xo xor xi xor ... xor xtn xor yo xor yi xor ... xor ytn. 25 6. Utilisation du procédé de masquage selon l'une des revendications 1 à 5 dans un composant cryptographique.15