Brevet FR2810821A1 — publié le 20011228

PROCEDES DE CONTRE-MESURE DANS UN COMPOSANT ELECTRONIQUE METTANT EN #UVRE UN ALGORITHME DE CRYPTOGRAPHIE A CLE PUBLIQUE DE TYPE COURBE ELLIPTIQUE DE KOBLITZ La présente invention concerne un procédé de contre-mesure dans un composant électronique mettant en #uvre un algorithme de chiffrement à clé publique de type courbe elliptique de Koblitz. Dans le modèle classique de la cryptographie à clef secrète, deux personnes désirant communiquer par l'intermédiaire d'un canal non sécurisé doivent au préalable se mettre d'accord sur une clé secrète de chiffrement K. La fonction de chiffrement et la fonction de déchiffrement utilisent la même clef K. L'inconvénient du système de chiffrement à clé secrète est que ledit système requiert la communication préalable de la clé K entre les deux personnes par l'intermédiaire d'un canal sécurisé, avant qu'un quelconque message chiffré ne soit envoyé à travers le canal non sécurisé. Dans la pratique, il est généralement difficile de trouver un canal de communication parfaitement sécurisé, surtout si la distance séparant les deux personnes est importante. On entend par canal sécurisé un canal pour lequel il est impossible de connaître de modifier les informations qui transitent par ledit canal. Un tel canal sécurisé peut être réalisé par un câble reliant deux terminaux, possédés par les deux dites personnes. Le concept de cryptographie à clef publique fut inventé par Whitfield DIFFIE et Martin HELLMAN en 1976. cryptographie à clef publique permet de résoudre le problème de la distribution des clefs à travers un canal non sécurisé. Le principe de la cryptographie à clef publique consiste à utiliser une paire de clefs, une clef publique de chiffrement et une clef privée de déchiffrement. I1 doit être calculatoirement infaisable de trouver la clef privée de déchiffrement à partir de la clef publique de chiffrement. Une personne A désirant communiquer une information à une personne B utilise la clef publique de chiffrement de la personne B. Seule la personne B possède la clef privée associée à sa clef publique. Seule la personne B est donc capable de déchiffrer le message qui lui est adressé. Un autre avantage de la cryptographie à clé publique sur la cryptographie à clé secrète est que la cryptographie à clef publique permet l'authentification par l'utilisation de signature électronique. La première réalisation de schéma de chiffrement à clef publique fut mis au point en 1977 par Rivest, Shamir et Adleman, qui ont inventé le système de chiffrement RSA. La sécurité de RSA repose sur la difficulté de factoriser un grand nombre qui est le produit de deux nombres premiers. Depuis, de nombreux systèmes de chiffrement à clef publique ont été proposés, dont la sécurité repose sur différents problèmes calculatoires (cette liste n'est pas exhaustive) . - Sac à dos de Merckle-Hellman Ce système de chiffrement est basé sur la difficulté du problème de la somme de sous-ensembles. - McEliece Ce système de chiffrement est basé sur la théorie des codes algébriques. I1 est basé sur le problème du décodage de codes linéaires. - ElGama1 Ce système de chiffrement est basé sur la difficulté du logarithme discret dans un corps fini. - Courbes elliptiques Le système de chiffrement à courbe elliptique constitue une modification de systèmes cryptographiques existant pour les appliquer au domaine des courbes elliptiques. L'utilisation de courbes elliptiques dans des systèmes cryptographiques fut proposé indépendamment par Victor Miller et Neal Koblitz en 1985. Les applications réelles des courbes elliptiques ont été envisagées au début des années 1990. L'avantage de crypto systèmes à base de courbe elliptique est qu'ils fournissent une sécurité équivalente aux autres crypto systèmes mais avec des tailles de clef moindres. Ce gain en taille de clé implique une diminution des besoins en mémoire et une réduction des temps de calcul, ce qui rend l'utilisation des courbes elliptiques particulièrement adaptées pour des applications de type carte à puce. Une courbe elliptique sur un corps fini GF(2^n) (n étant un entier) est l'ensemble des points (x, y) avec x l'abscisse et y l'ordonnée appartenant à GF(2^n) solution de l'équation y^2+x*y=x^3+a*x^2+b On définit les opérations d'addition de point et de doublement de point. L'addition de point est l'opération qui étant donné deux points P et Q calcule la somme R=P+Q, R étant un point la courbe dont les coordonnées s'expriment à l'aide des coordonnées des points P et Q suivant des formules dont l'expression est donnée dans l'ouvrage " Elliptic curve public key cryptosystem " par Alfred J. Menezes. Le doublement de point est l'opération qui, étant donne un point P, calcule le point R=2*P, R étant un point de la courbe dont les coordonnées s'expriment à l'aide des coordonnées du point P suivant des formules dont l'expression est donnée dans l'ouvrage " Elliptic curve public key cryptosystem " par Alfred J. Menezes. Les opérations d'addition de point et de doublement de point permettent de définir une opération de multiplication scalaire étant donné un point P appartenant à une courbe elliptique et un entier d, le résultat de la multiplication scalaire de P d est le point Q tel que Q=d*P=P+P±+P d fois. I1 existe une famille de courbes elliptiques dites courbes binaires anormales ou courbes de Koblitz. Cette famille de courbes est définie par l'équation y^2+x.y=x^3+a.x^2+1 a est un entier égal à 0 ou 1. Cette famille de courbe présente la propriété suivante : si le point coordonnées (x, y) appartient à la courbe, point (x^2,y^2) appartient aussi à la courbe. On définit en conséquence l'opérateur Frobenius noté i qui à tout point de coordonnées (x, y) associe le point de coordonnées ,y^2). Selon une méthode décrite dans l'article " An improved Algorithm for Arithmetic on a Family of Elliptic Curves " de J.A. Solinas publié à la conférence " Crypto'97 ", il est possible de représenter tout entier d sous la forme d'une somme de puissances de i =E di -c^i l'entier di vaut -1, 0, ou 1. I1 existe deux représentations possibles d'un élément de l'ensemble GF(2^n). La première est appelée représentation polynomiale et consiste à représenter un élément x sous la forme d'un polynôme en t X=Xn_ltn-1+...+Xp La deuxième représentation est la représentation en base normale, qui consiste à représenter un élément x sous la forme X- 1 .e^ (2n-1) +...+ Xp L'avantage de la représentation en base normale que la mise au carre d'un élément est très rapide. L'avantage de la représentation en base polynomiale est que les opérations de multiplication et d'inversion sont plus rapides. I1 est possible de passer d'une représentation en base polynomiale à une représentation en base normale. Des méthodes de conversion efficaces sont décrites dans l'article " Storage efficient finite field basis conversion " par B.S. Kaliski Jr. And Y.L.Yin publié à la conférence " SAC'98 ". La sécurité des algorithmes de cryptographie sur courbes elliptiques est basée sur la difficulté du probleme du logarithme discret sur courbes elliptiques, ledit probleme consistant à partir de deux points Q et P appartenant à courbe elliptique E, de trouver, s'il existe, un entier x tel que Q=x*P. I1 existe de nombreux algorithmes cryptographiques basés sur le problème du logarithme discret. Ces algorithmes sont facilement transposables aux courbes elliptiques. Ainsi, il est possible de mettre en oeuvre des algorithmes assurant l'authentification, la confidentialité, le contrôle d'intégrité et l'échange de clé. Un point commun à la plupart des algorithmes cryptographiques basés sur les courbes elliptiques est qu' comprennent comme paramètres une courbe elliptique définie un corps fini et un point P appartenant à cette courbe elliptique. La clé privée est un entier d choisi aléatoirement. La clef publique est un point de la courbe Q tel que Q=d*P. algorithmes cryptographiques font généralement intervenir multiplication scalaire dans le calcul d'un point R=d*T où d est la clef secrète. Dans le paragraphe ci dessous, on décrit un algorithme de chiffrement à base de courbe elliptique. Ce schéma est analogue au schéma de chiffrement d'El Gamal. Un message m est chiffré de la manière suivante le chiffreur choisit un entier k aléatoirement et calcule les points k*P=(xl,yl) et k*Q=(x2,y2) de la courbe, et l'entier c= x2 + m. Le chiffré de m est le triplet (xl,yl,c). Le déchiffreur qui possède d déchiffre m en calculant (x'2,y'2)=d(xl,yl) et m=c-x'2 Pour réaliser les multiplications scalaires nécessaires dans les procédés de calcul décrits précédemment, plusieurs algorithmes existent - Algorithme " double and add "; - Algorithme " addition-soustraction " - Algorithme avec chaînes d'addition ; - Algorithme avec fenêtre ; - Algorithme avec représentation signée. Cette liste n'est pas exhaustive. L'algorithme le plus simple et le plus utilisé est l'algorithme " double add ". L'algorithme " double and add " prend en entrée un point P appartenant à une courbe elliptique donnée et un entier d. L'entier d est noté d= (d (t),d(t-1),...,d(0)), où (d(t),d(t- 1) , ..., d (0) ) est la représentation binaire de d, avec d (t) le bit de poids fort et d(0) le bit de poids faible. L'algorithme retourne en sortie le point Q=d.P. L'algorithme " double and add " comporte les 3 étapes suivantes . 1) Initialiser le point Q avec la valeur P 2) Pour i allant de t-1 à 0 exécuter 2a) Remplacer Q par 2Q 2b) Si d(i)=1 remplacer Q par Q+P 3) Retourner Q. Dans le cas de l'utilisation d'une courbe elliptique binaire anormale (dite de Koblitz), il est possible de remplacer l'algorithme précédent par l'algorithme suivant plus efficace comportant les 3 étapes suivantes. L'entier d est représenté selon d=E di 2^i où l'entier di vaut -1, 0, ou 1 et 0 2b) Si di=1 remplacer Q par Q+P. 2c) Si di=-1 remplacer Q par Q-P. 3) Retourner Q. L'avantage de l'algorithme décrit précédemment sur l'algorithme " Double and Add " décrit précédemment est que l'opération de doublement de Q de l'étape 2a) est remplacée par l'opération du Frobenius plus rapide. I1 est apparu que l'implémentation sur carte ' puce d'un algorithme de chiffrement à clé publique du type courbe elliptique était vulnérable à des attaques consistant en une analyse différentielle de consommation de courant permettant de retrouver la clé privée de déchiffrement. Ces attaques sont appelées attaques DPA, acronyme pour Differential Power Analysis. Le principe de ces attaques DPA repose sur fait que 1a consommation de courant du microprocesseur exécutant des instructions varie selon la donnée manipulée. En particulier, lorsqu'une instruction manipule donnée dont un bit particulier est constant, la valeur des autres bits pouvant varier, l'analyse de la consommation de courant liée à l'instruction montre que la consommation moyenne de l'instruction n'est pas la même suivant que le bit particulier prend la valeur 0 ou 1. L'attaque de type DPA permet donc d'obtenir des informations supplémentaires sur les données intermédiaires manipulées par le microprocesseur de la carte lors de l'exécution d'un algorithme cryptographique. Ces informations supplémentaires peuvent dans certain cas permettre de révéler les paramètres privés de l'algorithme de déchiffrement, rendant le système cryptographique non sûr. Dans la suite de ce document on décrit un procédé d'attaque DPA sur un algorithme de type courbe elliptique réalisant une opération du type multiplication scalaire d'un point P par un entier d, l'entier d étant la clé secrète. Cette attaque permet de révéler directement la clé secrète d. Elle compromet donc gravement la sécurité de l'implémentation de courbes elliptiques sur une carte à puce. La première étape de l'attaque est l'enregistrement de la consommation de courant correspondant à l'execution de l'algorithme " double and add " décrit précédemment pour N points distincts P(1),...,P(N). Dans un algorithme à base de courbes ,elliptiques, le microprocesseur de la carte à puce va effectuer N multiplications scalaires d.P(1),...,d.P(N) Pour la clarté de la description de l'attaque, commence par décrire une méthode permettant d'obtenir la valeur du bit d(t-1) de la clé secrète d, où (d(t),d(t-1),...,d(0) est la représentation binaire de d, avec d(t) le bit de poids fort et d(0) le bit de poids faible. On donne ensuite la description d'un algorithme qui permet de retrouver la valeur de d. On groupe les points P(1) à P(N) suivant la valeur du dernier bit de l'abscisse de 4.P, où P désigne un points P(1) à P(N). Le premier groupe est constitué des points P tels que le dernier bit de l'abscisse de 4.P est égal à 1. Le second groupe est constitué des points P tels que le dernier bit de l'abscisse de 4.P est égal à 0. On calcule la moyenne des consommations de courant correspondant à chacun des deux groupes, et on calcule la courbe de différence entre ces deux moyennes. Si le bit d(t-1) de d est égal à 0, alors l'algorithme de multiplication scalaire précédemment décrit calcule et met en mémoire la valeur de 4.P. Cela signifie que lors de l'exécution de l'algorithme dans une carte à puce, le microprocesseur de la carte va effectivement calculer 4.P. Dans ce cas, dans le premier groupe de message le dernier bit de la donnée manipulée par le microprocesseur est toujours à 1, et dans le deuxième groupe de message le dernier bit de la donnée manipulée est toujours à 0. La moyenne des consommations de courant correspondant à chaque groupe est donc différente. apparaît donc dans la courbe de différence entre les 2 moyennes un pic de différentiel de consommation de courant. Si au contraire le bit d(t-1) de d est égal à 1, l'algorithme d'exponentiation décrit précédemment ne calcule pas le point 4.P. Lors de l'exécution de l'algorithme par la carte à puce, le microprocesseur ne manipule donc jamais la donnée 4.P. Il n'apparaît donc pas de pic de différentiel de consommation. Cette méthode permet donc de déterminer la valeur du bit d (t-1) de d. L'algorithme décrit dans le paragraphe suivant est une généralisation de l'algorithme précédent. Il permet de déterminer la valeur de la clé secrète d. On définit l'entrée par N points notés P(1) à P(N) correspondant à N calculs réalisés par la carte à puce et la sortie par un entier h. Ledit algorithme s'effectue de la manière suivante trois étapes 1) Exécuter h=1 ; 2) Pour i allant de t-1 à 1, exécuter 2)1) Classer les points P(1) à P(N) suivant la valeur du dernier bit de l'abscisse de (4*h).P ; 2)2) Calculer la moyenne de consommation de courant pour chacun des deux groupes ; 2)3) Calculer la différence entre les 2 moyennes ; 2)4) Si la différence fait apparaître un pic de différentiel de consommation, faire h=h*2 ; sinon faire h=h*2+1 ; 3) Retourner h. L'algorithme précédent fournit un entier h tel que -2*h ou d=2*h+l. Pour obtenir la valeur de d, il suffit ensuite de tester les deux hypothèses possibles. L'attaque de type DPA décrite permet donc de retrouver la clé privée d. Une attaque similaire est possible dans le cas de l'utilisation courbe elliptique dite " courbe de Koblitz ". invention consiste en la définition de 3 procédés de contre mesures permettant de se prémunir contre les attaques par mesure de courant. procédé de la première contre-mesure consiste à rendre aléatoire l'exécution de l'algorithme " i and substract " décrit précédemment. Ce procédé permet d'exécuter une opération de multiplication scalaire. Ainsi l'algorithme s'exécute suivant des étapes de calculs différentes pour chaque nouvelle exécution et l'attaque décrite précédemment n'est plus possible. L'algorithme " i and substract " modifié consiste en les 4 étapes suivantes. L'entier d est représenté selon d=E d; i^i où l' entier di vaut -1, 0, ou 1 et OSi 1) Tirer aléatoirement un entier i compris entre 0 et t-1 tel que di soit différent de 0. 2) Initialiser le point Q avec la valeur diii P 1) Répéter u-1 fois 3a) Tirer aléatoirement un entier i compris entre 0 et t-1, tel que di soit différent de 0, et qui n'ait pas été tiré auparavant. 3b) Remplacer Q par Q+di ii P 2) Retourner Q. Le premier procédé de la contre-mesure comprend deux variantes. Dans la première variante, le point P est représenté en base polynomiale. Dans la deuxième variante, le point P est représenté initialement en base normale. Le calcul de di ii P s'effectue également en base normale, ce qui permet un calcul plus rapide qu'en base polynomiale. Le point di il P est ensuite converti en base polynomiale. Le procédé de la deuxième contre-mesure consiste à protéger l'opération de mise au carré d'un élément contre les attaques par mesure de courant. Cette opération est utilisee en particulier dans l'application de l'opérateur de Frobenius tel que décrit précédemment. L'opération de mise au carré d'un élément dans un corps de caractéristique 2 est une opération lineaire. (x+y)^2=x^2+y^2. Le procédé de la deuxième contre- mesure consiste à remplacer l'opération de mise au carre d'un élément x par le procédé suivant en 3 étapes 1) Tirer aléatoirement un élément r de GF(2^n). 2) Calculer y=x+r 3) Calculer y^2 et r^2 4) Retourner y^2+r^2 Ainsi, l'élément r étant aléatoire, l'élément y l'est aussi, et opération de mise au carré de y et de r de l'étape 3 intervient sur des éléments aléatoires, ce qui la protège contre des attaques par mesure de courant. Le procédé de la deuxième contre-mesure comprend deux variantes. Dans la première variante, les éléments x,y et r sont representés en base polynomiale. Dans la deuxième variante, les éléments x,y et r sont représentés en base normale. Le procédé de la troisième contremesure consiste à effectuer un masquage de l'algorithme " i and substract " décrit précédemment. L'algorithme " i and substract " permet de calculer le point d.P étant donné le point P et l'entier d. On suppose par la suite que l'entier d est un entier fixe connu à l'avance. Le procédé de la troisième contre-mesure consiste à pré stocker en mémoire des couples de points de la forme : (Si , Ri) avec Si =d . Ri On note u le nombre de couples stockés. Le procédé de la troisième contre-mesure consiste à remplacer l'algorithme " i and substract " décrit précédemment par le procédé suivant en 6 étapes 1) Tirer aléatoirement un entier i compris entre 1 et u. 2) Tirer aléatoirement un entier j compris entre 0 et n-1. 3) Calculer P' =P+ii Ri 4) Calculer Q'=d.P' en utilisant l'algorithme " i and substract " décrit précédemment. 5) Calculer Q=Q' Si 6) Retourner Q. Le procédé de troisième contre-mesure comprend une première variante dans laquelle les points Ri et Si sont représentés en base polynomiale Dans une deuxième variante, les points Ri et Si sont représentés base normale. Le calcul de ii Ri à l'étape 3) et le calcul de Si s'effectuent en base normale. Les points i' Ri et ii S;, sont ensuite convertis en base polynomiale. Les trois procédés de contre-mesures précédemment décrits permettent de protéger l'exécution d'un algorithme de multiplication scalaire sur courbe elliptique binaire anormale (dite de Koblitz) contre les attaques par mesure de courant. I1 est possible d'utiliser simultanément deux ou trois de ces contre-mesures. Ces trois procédés peuvent être utilisés lors de l'exécution de tout protocole cryptographique basé sur les courbes elliptiques, en particulier un protocole d'échange de clef, un protocole de signature électronique ou un protocole de chiffrement. Ces trois procédés sont particulièrement destinés à être utilisés dans un environnement électronique de type carte à puce. REVENDICATIONS 1) Procedé de contre-mesure dans un composant electronique exécutant une opération de multiplication scalaire d' point P appartenant à une courbe elliptique binaire anormale par un entier d représenté sous la forme d=E dii"i l'entier di valant -1, 0, ou 1, l'entier i étant tel que 0