FR2829646A1

FR2829646A1 - Procede securise de mise en oeuvre d'un algorithme de cryptographie et composant correspondant

Info

Publication number: FR2829646A1
Application number: FR0111602A
Authority: FR
Inventors: Marc Joye; Karine Gandolfi Villegas
Original assignee: Gemplus Card International SA; Gemplus SA
Current assignee: Gemplus SA
Priority date: 2001-09-07
Filing date: 2001-09-07
Publication date: 2003-03-14
Anticipated expiration: 2021-09-07
Also published as: FR2829646B1; WO2003025739A1

Abstract

L'invention concerne un procédé sécurisé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie utilisant des moyens de calcul destinés à effectuer des opérations d'exponentiation à la puissance d d'un nombre y (yd), d étant un nombre entier de taille déterminée. Il consiste à mémoriser plusieurs algorithmes de calcul d'exponentiation dans ledit composant électronique préalablement au premier calcul de yd , et à réaliser les étapes suivantes à chaque calcul de la valeur yd : a) on décompose le nombre d en n blocs D i de r i bits, i variant de 0 à n-1, n et les r i étant des entiers aléatoires, 1<n<=taille de d, r0+... + rn-1 = taille de d et on considère parmi les algorithmes de calcul d'exponentiation mémorisés, une chaîne de n algorithmes A i, b) on effectue au moyen d'un algorithme A0 et à partir des r0 premiers bits de d et de y, le calcul S0 = yDD et on mémorise le résultat S0 , c) on effectue au moyen d'un algorithme A j et à partir des r j bits suivants de d, d'une fonction de S0 et/ ou... et/ ou de S j-1 , et de y, j variant de 1 à n-1, le calcul S j = y D0|...|Dj et on mémorise le résultat S j , le résultat de yd correspondant à la valeur Sn-1obtenue.

Description

PROCÉDÉ SÉCURISÉ DE MISE EN OEUVRE D'UN ALGORITHME DE
CRYPTOGRAPHIE ET COMPOSANT CORRESPONDANT
La présente invention concerne un procédé sécurisé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie utilisant le calcul d'exponentiation à la puissance d d'un nombre y.

L'invention se rapporte également au composant électronique correspondant.

De tels composants sont utilisés dans des applications où l'accès à des services ou à des données est sévèrement contrôlé. Ils ont une architecture formée autour d'un microprocesseur et de mémoires, dont une mémoire programme de type ROM ("Read Only Memory" en anglais) qui contient le (s) nombre (s) secret (s) d.

Ces composants sont utilisés dans des systèmes informatiques, embarqués ou non ; ils sont notamment utilisés dans les cartes à puce, pour certaines applications de celles-ci. Ce sont par exemple des applications d'accès à certaines banques de données, des applications bancaires, des applications de télépéage, par exemple pour la télévision, la distribution d'essence ou encore le passage de péages d'autoroutes.

Ces composants ou ces cartes mettent donc en oeuvre un algorithme de cryptographie pour assurer le chiffrement de données émises et/ou le déchiffrement de données reçues lorsque celles-ci doivent demeurer confidentielles.

De manière générale et succincte, ces algorithmes cryptographiques ont notamment pour fonction le chiffrement ou la signature numérique d'un message

appliqué en entrée (à la carte) par un système hôte (serveur, distributeur bancaire...) et de nombreux secrets contenus dans la carte, et de fournir en retour au système hôte ce message chiffré ou signé, ce qui permet par exemple au système hôte d'authentifier le composant ou la carte, d'échanger des données,....

Les caractéristiques des algorithmes de cryptographie sont connues : calculs effectués, paramètres utilisés. La seule inconnue est le ou les nombres secrets contenus en mémoire programme. Toute la sécurité de ces algorithmes de cryptographie tient dans ce (s) nombre (s) secret (s) contenu (s) dans la carte et inconnu (s) du monde extérieur à cette carte. Ce nombre secret ne peut être déduit de la seule connaissance du message appliqué en entrée et du message chiffré fourni en retour.

Or il est apparu que des attaques externes basées sur des grandeurs physiques mesurables à l'extérieur du dispositif de calcul lorsque celui-ci est en train de dérouler l'algorithme de cryptographie, permettent à des tiers mal intentionnés de trouver le (s) nombre (s) secret (s) contenu (s) dans cette carte. Ces attaques sont appelées attaques à canaux cachés ("Side channel attacks"en anglais) ; on distingue parmi ces attaques à canaux cachés, les attaques SPA acronyme anglo-saxon pour Single Power Attack et les attaques DPA, acronyme anglo-saxon pour Differential Power Analysis.

Le principe de ces attaques à canaux cachés repose par exemple sur le fait que la consommation en courant du microprocesseur exécutant des instructions varie selon l'instruction ou la donnée manipulée.

Notamment, quand une instruction exécutée par le microprocesseur nécessite une manipulation d'une donnée ou d'une instruction bit par bit, on a deux profils de courant différents selon que ce bit vaut" 1" ou "0". Typiquement, si le microprocesseur manipule un"0", on a à cet instant d'exécution une première amplitude du courant consommé et si le microprocesseur manipule un "1", on a une deuxième amplitude du courant consommé, différente de la première.

Ainsi les attaques à canaux cachés exploitent dans ce cas la différence du profil de consommation en courant dans la carte pendant l'exécution d'une instruction suivant la valeur du bit manipulé. Pour une description plus détaillée des attaques à canaux cachés, on se reportera à la publication de Paul Kocher "Advances in Cryptology-CRYPTO'99", vol. 1666 of Lectures Notes in Computer Science, pp 388-397, Springer Verlag 1999.

Ce type d'attaque est notamment envisageable avec l'algorithme RSA du nom de ses auteurs (Rivest, Shamir et Adleman), sur lequel sont basés de nombreux algorithmes de cryptographie. La sécurité de l'algorithme RSA est basée sur la difficulté de factoriser de grands nombres. Ces algorithmes utilisent notamment des calculs d'exponentiation à la puissance d, d étant un nombre secret.

On rappelle brièvement les principales étapes de l'algorithme RSA.

On établit un nombre N qui est le produit de deux nombres premiers p et q (N=p. q), ainsi qu'un exposant

public ou clé publique e et un exposant privé ou clé privée ou secrète d, satisfaisant la relation :

e. d = 1 (module À (N)),

Â. (.) étant la fonction de Carmichael.

Selon un premier mode de fonctionnement de l'algorithme RSA dit classique, les paramètres publics sont (N, e) et les paramètres privés sont (N, d). Etant donné x compris dans l'intervalles 0, N [, l'opération publique sur x qui peut être par exemple le chiffrement du message x ou encore la vérification de la signature

x, consiste à calculer :

y = Xe module N

L'opération privée correspondante qui peut être par exemple le déchiffrement du message chiffré y ou la génération d'une signature x, est alors :

x = yd module N
Un autre mode de fonctionnement dit mode CRT car basé sur le théorème des restes chinois ("Chinese Remainder Theorem"ou CRT en anglais) est quatre fois plus rapide que celui de l'algorithme RSA classique.

Selon ce RSA mode CRT, on n'effectue pas directement les calculs modulo N mais on effectue d'abord les calculs modulo p et modulo q.

Les paramètres publics sont (N, e) mais les paramètres privés sont (p, q, d) ou (p, q, dp, dq, iq) avec

dp = d modulo (p-1), dq = d modulo (q-1) et iq= q' module p.

L'opération publique s'effectue de la même façon que pour le mode de fonctionnement classique ; par contre pour l'opération privée, on calcule d'abord :

x-y"modp et dq odq

Ensuite, par application du théorème des restes chinois, on obtient x = yd mod N par :

x = xq+q[iq (xp-xq) modulo p]
Ainsi en mesurant la consommation en courant de la carte par exemple, lors de ces calculs d'exponentiation à la puissance d, un fraudeur peut déduire la suite de bits composant la clé d à partir de multiples mesures.

Les procédés de contre-mesure permettant de parer ce type d'attaque consistent à ne pas manipuler directement la clé secrète d.

Selon une première contre-mesure, on décompose d sous la forme suivante d = (d+a)-a et l'on calcule alors y (d+a) puis y'. Mais a et d étant de même ordre de grandeur, le temps de calcul est alors doublé.

Une autre contre-mesure seulement utilisable en mode CRT et décrite dans le brevet WO n 9935782 consiste à exprimer l'exposant privé dp sous la forme aléatoire suivante : dp* = dp+r. (p-1), r étant un nombre aléatoire.

Mais cette contre-mesure ne peut s'appliquer au mode RSA classique.

Une troisième contre-mesure consiste à représenter l'exposant d par une chaîne d'addition. Par exemple, une chaîne d'addition possible du nombre 10 est (1,2, 3,5, 8,10). Pour calculer ylO, on calcule R1=y. y=y2

2 3 3 2= 5 puis R2=Rl. y=y2. y=y3 puis R3=R2. R1=y3. l=y5 puis 5 3 8 2= 10 R4=R3. R2=y\y et enfin R5=R4. R1=y8. y2=ylO. Bien sûr dans la réalité la clé secrète d est un nombre beaucoup plus grand, de 512 bits ou plus.

Pour une description plus détaillée des représentations d'un nombre par chaînes d'addition, on peut se reporter à la publication de C. Clavier et de M. Joye CHESS'01 "Universal exponentiation algorithm : a first step toward provable SPA resistance".

Dans ce cas de contre-mesure, la taille des données à garder en mémoire en l'occurrence la chaîne d'addition, est doublée.

Le but de la présente invention est donc de protéger le nombre secret'd contre les attaques à canaux cachés intervenant lorsque d est utilisé dans des calculs d'exponentiation, sans pour autant être pénalisé au niveau du temps de calcul, de l'emplacement mémoire ou encore limité dans le choix de l'algorithme de cryptographie.

L'invention a pour objet un procédé sécurisé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie utilisant des moyens de calcul destinés à effectuer des opérations d'exponentiation à la puissance d d'un nombre y (yd), d étant un nombre entier de taille déterminée, caractérisé en ce qu'on mémorise plusieurs algorithmes de calcul d'exponentiation dans ledit composant électronique préalablement au premier calcul de la valeur yd, et en ce qu'il consiste à réaliser les étapes suivantes à chaque calcul de la valeur yd : a) on décompose le nombre d en n blocs Di de ri bits, i variant de 0 à n-1, n et les ri étant des entiers aléatoires, l < n < =taille de d, ro+... +rn-i=taille de d et on considère parmi les algorithmes de calcul

d'exponentiation mémorisés, une chaîne de n algorithmes Ai, b) on effectue au moyen d'un algorithme Ao et à partir des ro premiers bits de d et de y, le calcul

et on mémorise le résultat So, c) on effectue au moyen d'un algorithme Aj et à partir des rj bits suivants de d, d'une fonction de So et/ou... et/ou de Sj-i, et de y, j variant de 1 à n-1, le calcul

et on mémorise le résultat Sj, le résultat de yd correspondant à la valeur Sn-i obtenue.

Selon une caractéristique de l'invention, parmi la chaîne des n algorithmes Ai, certains desdits algorithmes sont identiques.

La chaîne des n algorithmes Ai i variant de 0 à n- 1, est de préférence établie de manière aléatoire.

La chaîne des n algorithmes Ai i variant de 0 à n- 1, peut être prédéterminée.

Selon un mode de réalisation de l'invention, l'algorithme de cryptographie est du type RSA classique ou en mode CRT.

L'invention a également pour objet un composant électronique de sécurité, comprenant des moyens de calcul, une mémoire de programme et une mémoire de travail et des moyens de communication de données, caractérisé en ce qu'il met en oeuvre le procédé de

contre-mesure selon l'une quelconque des revendications précédentes, et en ce qu'il comprend un générateur de nombres aléatoires et en ce que la mémoire de programme comporte plusieurs algorithmes de calcul d'exponentiation.

L'invention concerne aussi une carte à puce comprenant un composant électronique tel que décrit précédemment.

D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description faite à titre d'exemple non limitatif et en regard de la figure 1 annexée qui représente schématiquement les éléments d'une carte à puce apte à mettre en oeuvre l'invention.

Les modes de réalisation sont décrits dans le cadre de cartes à puce, mais peuvent bien entendu s'appliquer à tout autre dispositif ou composant électronique de sécurité doté de moyens de calculs cryptographiques.

Ainsi que le montre la figure 1, la carte à puce 1 comprend un microprocesseur 2 couplé à une mémoire figée (ROM) 3 et à une mémoire vive (RAM) 4, le tout formant un ensemble permettant, entre autres, l'exécution d'algorithmes cryptographiques. Plus précisément, le microprocesseur 2 comporte les moyens de calcul arithmétiques nécessaires à l'algorithme, ainsi que des circuits de transfert de données avec les mémoires 3 et 4. La mémoire figée 3 contient le programme exécutoire de l'algorithme cryptographique sous forme de code source, alors que la mémoire vive 4

comporte des registres pouvant être mis à jour pour le stockage de résultats des calculs.

La carte à puce 1 comporte aussi une interface de communication 5 reliée au microprocesseur 2 pour permettre l'échange de données avec l'environnement extérieur. L'interface de communication 5 peut être du type"à contacts", étant dans ce cas formée d'un ensemble de plots de contacts destinés à se connecter à un contacteur d'un dispositif externe, tel qu'un lecteur de cartes, et/ou du type"sans contact". Dans ce dernier cas, l'interface de communication 5 comporte une antenne et des circuits de communication par voie hertzienne permettant un transfert de données par liaison sans fil. Cette liaison peut aussi permettre un transfert d'énergie d'alimentation des circuits de la carte 1.

Le procédé selon l'invention consiste à calculer yd au moyen d'une chaîne de n algorithmes d'exponentiation appliqués à n blocs de bits de d. On entend par algorithme de calcul d'exponentiation, une suite d'instructions permettant d'effectuer ce calcul ; comme on le verra par la suite dans un exemple, il y a plusieurs algorithmes possibles.

Cette chaîne de n algorithmes d'exponentiation Ai (i variant de 0 à n-1) est établie à partir de plusieurs algorithmes d'exponentiation que l'on met en mémoire préalablement au premier calcul de yd. Les algorithmes Ai ne sont pas nécessairement tous différents : certains peuvent être identiques.

A chaque calcul de la valeur yd, par exemple à chaque fois que l'on effectue l'opération privée

décrite précédemment pour l'algorithme RSA, on découpe comme représenté ci-dessous la clé d comportant K bits (la taille de d est K), en n blocs Di (i varie de 0 à n- 1) de ri bits (0 ou 1), n et ri étant des nombres entiers aléatoires, 1 < n < =K générés par exemple par la carte à puce au moyen d'un générateur 6 de nombres aléatoires représenté figure 1 :

d = dk............... dj......... do (représentation binaire de d) 1-1 ro... r[... rn-l (nombre de bits de chaque bloc D) Do... D,... Dn-l

avec Douro premiers bits de d, Dl=rl bits suivant ceux du bloc Do, ....

Di= ri bits suivant ceux des blocs Doll.. J 1 Di-l, ..., Dn-i= rn-i derniers bits de d, avec d= Doll.. J 1 Dn-l, le symbole # signifiant concaténé.

Les blocs Di qui se suivent sont contigus.

La clé d est lue de gauche à droite ; on peut bien sûr tout aussi bien la lire de droite à gauche. De même on peut lire les bits d'un bloc de gauche à droite et ceux d'un autre bloc de droite à gauche.

On effectue ensuite le calcul d'exponentiation yd au moyen de la chaîne de n algorithmes : on calcule au moyen d'un algorithme Ao le calcul d'exponentiation de y à partir des ro premiers bits de d et de y pour obtenir So que l'on mémorise :

on calcule au moyen d'un algorithme Ai le calcul d'exponentiation de y à partir des ri bits suivants de d, d'une fonction de So et de y pour obtenir

Si que l'on mémorise :

--y on calcule au moyen d'un algorithme Ai le calcul d'exponentiation de y à partir des ri bits suivants de d, d'une fonction de So et/ou de Si et/ou

..., et/ou de Spi1, et de y pour obtenir Si que l'on mémorise :

'"/ on calcule au moyen d'un algorithme A le calcul d'exponentiation de y à partir des rn-i derniers bits de d, d'une fonction de So et/ou de Si et/ou..., et/ou de Sn-2, et de y pour obtenir Sn-1, le résultat recherché, que l'on mémorise :

Selon l'algorithme Ai mis en oeuvre, le calcul de Si s'effectue à partir notamment d'une fonction du résultat Si-i de l'algorithme précédent sans utiliser toute la chaîne So,..., Si-2 des résultats précédents (ou d'une fonction des résultats précédents), ou encore à

partir de quelques uns de ces résultats (ou d'une fonction de ces résultats).

Par ailleurs, la chaîne d'algorithme est de préférence déterminée de manière aléatoire pour chaque calcul de yd ; elle peut cependant être prédéterminée.

Ce procédé permet ainsi de se protéger dans le cas de la mise en oeuvre d'un algorithme de cryptographie basé sur un calcul d'exponentiation du type yd.

En effet, les attaques à canaux cachés qui sont réalisées au terme de multiples mesures, consistent dans un premier temps, lors d'une phase d'apprentissage à identifier l'algorithme d'exponentiation utilisé. Pour ce faire, le fraudeur relance l'algorithme en changeant la clé. Connaissant cet algorithme, il peut alors identifier les bits de la véritable clé d.

Selon l'invention, le calcul de yd n'est pas effectué de la même manière d'une fois sur l'autre : la décomposition de d en blocs Di est déterminée de façon aléatoire d'une fois sur l'autre car le nombre n de blocs et leur taille ri sont des entiers aléatoires, les algorithmes de calcul d'exponentiation diffèrent les uns des autres (même si certains sont identiques, il y en a au moins deux qui diffèrent) et éventuellement, la chaîne d'algorithmes d'exponentiation varie également de façon aléatoire d'un calcul de yd à l'autre.

Il devient ainsi beaucoup plus difficile voire impossible d'identifier l'algorithme d'exponentiation utilisé et par conséquent de déterminer l'exposant secret.

On va à présent illustrer le procédé précédemment décrit par l'exemple suivant qui consiste à réaliser le

calcul d'exponentiation modulaire suivant : yd modulo p, d étant une clé de k bits et p étant un nombre premier.

On décompose la clé d en 2 blocs (n=2), un bloc Do de k-r bits et un bloc Dl de r bits (d=DID1).

Le calcul"yd modulo p"va donc s'effectuer au moyen de deux algorithmes Ao et Ai permettant d'obtenir respectivement So et Si avec Si=y module p.

L'algorithme choisi pour Ao est l'algorithme "Square and Always Multiply"qui consiste à élever au carré et à multiplier dans tous les cas. Il s'agit, pour des exposants de même taille, d'un algorithme à temps constant et à code constant c'est-à-dire qui exécute toujours les mêmes instructions, quelle que soit la valeur de l'exposant manipulé ; il n'inclut pas d'instructions de test pouvant donner une information sur la valeur manipulée. Un tel algorithme à temps constant et à code constant est bien sécurisé mais il est coûteux en temps de calcul car il exécute parfois des opérations inutiles.

L'algorithme choisi pour Ai est l'algorithme "Square and Multiply"qui consiste à élever au carré et à multiplier. Il ne s'agit pas d'un algorithme à temps constant, ni à code constant sauf si l'on rajoute artificiellement une instruction comme on le verra plus loin. C'est donc un algorithme moins sécurisé que le précédent mais plus rapide.

On calcule donc d'abord So au moyen de Ao à partir de 1, y, des k-r premiers bits de d et de p selon la suite d'instructions suivante :

RO=l Pour i=k-1 à r par pas de (-1) R1=R02 modulo p RO=Rl*y RO=R [complément de di] FinPour So=RO

On rappelle que si di=O, le complément de di est 1 et R [complément de di] =Rl, et que si di=l, le complément de di est 0 et R [complément de di] =RO.

On enchaîne ensuite avec le calcul de Si (c'est-àdire yd modulo p) au moyen de Ai à partir de So, y, des r bits suivants de d et de p selon la suite d'instructions suivante :

RO==So Pour i=r-1 à 0 par pas de (-1) R1=R02 si di=l alors RO=Rl*y modulo p sinon RO=R1 FinPour Sl=RO

Pour que l'algorithme Al soit à code constant, il suffit de remplacer l'instruction RO=R1 par : RO=R1*1 modulo p.

L'invention est valable pour les algorithmes cryptographiques utilisant des calculs d'exponentiation comme par exemple le calcul d'exponentiation modulaire (yd modulo p) dans le cas de l'algorithme de type RSA ou encore le calcul d'exponentiation sur une courbe elliptique où il est d'usage d'écrire l'exponentiation

de façon additive. L'exponentiation se nomme alors multiplication scalaire : b yb=y*... *y (b fois) devient b*y=y+... +y (b fois).

Claims

REVENDICATIONS

1. Procédé sécurisé de mise en oeuvre, dans un composant électronique, d'un algorithme de cryptographie utilisant des moyens de calcul destinés à effectuer des opérations d'exponentiation à la puissance d d'un nombre y (yd), d étant un nombre entier de taille déterminée, caractérisé en ce qu'on mémorise plusieurs algorithmes de calcul d'exponentiation dans ledit composant électronique préalablement au premier calcul de la valeur yd, et en ce qu'il consiste à réaliser les étapes suivantes à chaque calcul de la valeur yd : a) on décompose le nombre d en n blocs Di de ri bits, i variant de 0 à n-1, n et les ri étant des entiers aléatoires, l < n < =taille de d, ro+... +rn-i=taille de d et on considère parmi les algorithmes de calcul d'exponentiation mémorisés, une chaîne de n algorithmes

Ai, b) on effectue au moyen d'un algorithme Ao et à partir des ro premiers bits de d et de y, le calcul

2. Procédé selon la revendication précédente, caractérisé en ce que parmi la chaîne des n algorithmes Ai, certains desdits algorithmes sont identiques.

3. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la chaîne des n algorithmes Ai i variant de 0 à n-1, est établie de manière aléatoire.

4. Procédé selon l'une quelconque des revendications 1 à 2, caractérisé en ce que la chaîne des n algorithmes Ai i variant de 0 à n-1, est prédéterminée.

5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'algorithme de cryptographie est du type RSA.

6. Procédé selon la revendication précédente, caractérisé en ce que l'algorithme de type RSA est du type CRT.

7. Composant électronique de sécurité, comprenant des moyens de calcul (2), une mémoire de programme (3) et une mémoire de travail (4) et des moyens de

communication de données (5), caractérisé en ce qu'il met en oeuvre le procédé de contre-mesure selon l'une quelconque des revendications précédentes, et en ce qu'il comprend un générateur (6) de nombres aléatoires et en ce que la mémoire de programme (3) comporte plusieurs algorithmes de calcul d'exponentiation.

8. Carte à puce comprenant un composant électronique selon la revendication précédente.