Brevet FR2819079A1 — publié le 20020705

PROCEDE DE PROTECTION CONTRE LES ATTAQUES PAR MESURE DE COURANT OU DE RAYONNEMENT ELECTROMAGNETIQUE L'invention concerne un procédé algorithmique non déterministe d'inversion d'un élément dans un corps fini de caractéristique deux. Plus généralement, l'invention concerne également un procédé de protection contre les attaques par mesure de courant ou par mesure de rayonnement électromagnétique contre des dispositifs électroniques utilisant des algorithmes effectuant des calculs dans des corps finis de caractéristique deux. Par la suite, on notera GF (2An) un corps fini de caractéristique 2, n étant un nombre entier. Les opérations dans GF (2'n) jouent un rôle important en cryptographie, à cause des systèmes cryptographiques basés sur des corps finis. En particulier, l'inversion dans un corps fini, c'est-à-dire l'opération qui à un élément x de GF (2An) fait correspondre 1/x, est un procédé crucial, du fait qu'il est coûteux en calcul, et peut donc engendrer des variations de temps importantes au cours de l'exécution d'algorithmes cryptographiques. L'algorithme d'inversion dans GF (2'n) le plus efficace connu à ce jour est dit algorithme du quasi-inverse , et procède comme suit. Cet algorithme est décrit dans la publication Fast key exchange elliptic curve systems les auteurs étant R. Schroeppel, H. Orman et 0. Spatscheck présentée à la conférence Crypto en 1995 qui a eu lieu à Santa Barbara, Californie, Etats-Unis d'Amérique. On introduit quelques notations : on note GF (2) [X] l'anneau des coefficients des polynômes à coefficient binaires ; - tous les éléments de GF (2n) sont représentés par des polynômes en la variable x de degré plus petit que n ; on note M (X) le polynôme irréductible à coefficients 0 ou 1, appartenant à GF (2) [X], définissant le corps GF (2"n) si U et V sont des variables d'un algorithme, U V signifie qu'on échange les valeurs de U et de V. De plus U représentation polynomiale en outre, si A=a0+alx+... +a (n-1) x (n-1) est un élément de GF (2An), on dit que A est pair si a0=0 ; enfin, on appelle terme de degré k de A la formulation ak. L'algorithme du quasi-inverse se présente de la façon suivante dénommé ci-après Algorithme 1 , avec une entrée définie, une sortie définie et des étapes d'exécution : Entrée : A, qui est un élément de GF (2) [X] de degré strictement plus petit que n et non nul, et M qui est aussi un élément de GF (2) [X] de degré strictement plus petit que n et non nul ; Sortie : un élément B de GF (2) [X] tel que AB (X) =X~k [M (X)] avec k L'étape 1 consiste en une étape d'initialisation qui consiste à affecter des valeurs à k, B, C, F, G, ce qu'on représente par la formulation suivante : k G et B C ; Etape 5 : F Cet algorithme permet par la suite de calculer l'inverse de A (x) dans GF (2^n) en divisant B (x) par i x k. Cet algorithme est déterministe, dans le sens où son exécution reste identique si son entrée ne change pas. Cette propriété est un inconvénient, du fait d'attaques possibles par mesure de courant ou de rayonnement, qui parviennent à obtenir une trace de l'exécution de l'algorithme, et peuvent, par des raisonnements statistiques et par des tests d'hypothèse, obtenir des informations sur l'entrée et la sortie de l'algorithme. Aujourd'hui, on ne connaît pas de procédé pour calculer des inverses dans GF (2 An) en introduisant un caractère aléatoire dans l'exécution du procédé de calcul. La présente invention consiste à combler cette absence et concerne un procédé algorithmique permettant de calculer l'inverse de tout élément dans GF (2 An) de sorte que l'exécution de cet algorithme soit toujours différente même si l'entrée fournie à l'algorithme reste identique. Ainsi, une analyse statistique par test d'hypothèse appliquée à cet algorithme échoue du fait du caractère aléatoire de l'exécution. L'invention fournit un moyen simple de mise en oeuvre c'est-à-dire facile à faire ou exécuter. Par ailleurs, un second avantage sur la souplesse d'exécution apparaît : en général quand on introduit un aléa dans un algorithme, le temps d'exécution de l'algorithme est augmenté. L'invention permet de moduler de manière très souple l'augmentation du temps d'exécution. L'invention est un procédé algorithmique dérivé de l'algorithme 1, et est détaillée dans l'algorithme 2 présentant un paramètre choisi, une entrée définie, une sortie définie et des étapes d'exécution : Paramètre 1 choisi : un entier 1 > =0 qui permet de contrôler le degré de hasard introduit dans l'algorithme ainsi que le surcroît du temps d'exécution ; Entrée : A, polynôme élément non nul de GF (2) [X] de degré strictement plus petit que n ; Sortie : B, polynôme élément de GF (2) [X] tel que AB (X) =Xk [M (X)] avec k Etape 1 : Tirer un polynôme aléatoire R dans GF (2) [X] de degré égal à l, premier avec le polynôme A, et dont le terme de degré 0 est non nul. Ceci peut être obtenu itérativement, en répétant l'opération, jusqu'à ce qu'un R satisfaisant soit obtenu ; Etape 2 : U Etape 3 : Initialisation qui consiste à affecter des valeurs à k, B, C, F, G, ce qu'on représente par la formulation suivante : ka-0, B Etape 4 : Tant que F est pair, exécuter F G et B C Etape 7 : F Etape 8 : Aller à l'étape 5 Etape 9 : Retourner B. Le procédé de l'invention est donc caractérisé en ce que l'algorithme d'inversion utilise un polynôme multiple de M (X) à la place de M (X) pour faire des calculs modulaires dans l'anneau GF (2) [X]. En effet, le produit (M*R) est introduit pour remplacer (M) dans l'algorithme de l'art antérieur. Cet algorithme est donc non déterministe car son exécution change constamment du fait de la multiplication de M par R. L'invention peut être utilisée dans tout procédé cryptographique utilisant des calculs dans les corps finis de caractéristique 2. En particulier, l'invention peut être utilisée dans tous les procédés cryptographiques basés sur le logarithme discret, à la fois dans les corps de caractéristique 2 et dans les courbes elliptiques. En particulier, l'invention peut être utilisée dans tous les procédés cryptographiques susceptibles d'utiliser des calculs dans des courbes elliptiques, hyperelliptiques et superelliptiques définies sur des corps finis de caractéristique 2, et en particulier les courbes de Koblitz. Ces schémas incluent en particulier l'algorithme de signature ECDSA, et l'algorithme d'échange de clés ECDH. Ces applications énoncées ci-dessus dans le cadre de la cryptographie ne sont pas exhaustives et peuvent s'appliquer à d'autres domaines technologiques comme par exemple le domaine des codes correcteurs. Par ailleurs, l'invention concerne également des dispositifs électroniques mettant en oeuvre le procédé de l'invention. Plus précisément, les dispositifs électroniques sont des objets portables électroniques comme par exemple une carte à puce. REVENDICATIONS 1. Procédé de protection contre les attaques par mesure de courant ou par mesure de rayonnement électromagnétique dans un dispositif électronique mettant en oeuvre un algorithme effectuant des calculs dans des corps finis de caractéristique deux noté GF (2An) caractérisé en ce que ledit procédé comprend l'utilisation d'un paramètre, d'une entrée et d'une sortie suivantes : Paramètre 1 choisi : un entier 1 > =0 permettant de contrôler le degré de hasard introduit dans l'algorithme ainsi que le surcroît du temps d'exécution ; Entrée : A un polynôme élément non nul de GF (2) [X] de degré strictement plus petit que n ; Sortie : B un polynôme élément de GF (2) [X] tel que AB (X) =Xk [M (X)] avec k Et en ce qu'il comprend les étapes d'exécution suivantes : Etape 1 : Tirer un polynôme aléatoire R dans GF (2) [X] de degré égal à l, premier avec le polynôme A, et dont le terme de degré 0 est non nul, ceci pouvant être obtenu itérativement, en répétant l'opération, jusqu'à ce qu'un R satisfaisant soit obtenu ; Etape 2 : calculer : U Etape 3 : Initialiser en affectant des valeurs à k, B, C, F, G, ce qu'on représente par la formulation suivante : k Etape 4 : réaliser la comparaison : tant que F est pair, exécuter F G et B C ; Etape 7 : calculer : F Etape 8 : Aller à l'étape 5 Etape 9 : Retourner B. 2. Dispositif électronique mettant en oeuvre le procédé de protection contre les attaques par mesure de courant ou par mesure de rayonnement selon la revendication 1. 3. Dispositif électronique selon la revendication 2 caractérisé en ce qu'il est un objet portable électronique. 4. Dispositif électronique selon la revendication 3 caractérisé en ce qu'il est une carte à puce.