[go: up one dir, main page]

FR2818846A1 - Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie - Google Patents

Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie Download PDF

Info

Publication number
FR2818846A1
FR2818846A1 FR0016993A FR0016993A FR2818846A1 FR 2818846 A1 FR2818846 A1 FR 2818846A1 FR 0016993 A FR0016993 A FR 0016993A FR 0016993 A FR0016993 A FR 0016993A FR 2818846 A1 FR2818846 A1 FR 2818846A1
Authority
FR
France
Prior art keywords
algorithm
factors
calculation
mod
countermeasure
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
FR0016993A
Other languages
English (en)
Other versions
FR2818846B1 (fr
Inventor
Frederic Amiel
David Naccache
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Gemplus SA
Original Assignee
Gemplus Card International SA
Gemplus SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Gemplus Card International SA, Gemplus SA filed Critical Gemplus Card International SA
Priority to FR0016993A priority Critical patent/FR2818846B1/fr
Publication of FR2818846A1 publication Critical patent/FR2818846A1/fr
Application granted granted Critical
Publication of FR2818846B1 publication Critical patent/FR2818846B1/fr
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/722—Modular multiplication
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/723—Modular exponentiation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/002—Countermeasures against attacks on cryptographic mechanisms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7223—Randomisation as countermeasure against side channel attacks
    • G06F2207/7252—Randomisation as countermeasure against side channel attacks of operation order, e.g. starting to treat the exponent at a random place, or in a randomly chosen direction

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Computing Systems (AREA)
  • Computational Mathematics (AREA)
  • Computer Security & Cryptography (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Storage Device Security (AREA)

Abstract

L'invention concerne un procédé de contre-mesure dans un composant électronique mettant en oeuvre un algorithme de cryptographie utilisant des moyens de calcul de multiplication modulaire par une puissance de x et/ ou de calcul d'exponentiation modulaire à la puissance x, x étant un nombre entier. Le nombre x étant décomposable en facteurs x1 , x2 ,..., x i , le procédé consiste à choisir une permutation aléatoire P, à considérer le nombre x sous la forme Xp (1) . Xp(2) ... Xp (i) , et à effectuer ledit calcul à partir de cette nouvelle forme de x.

Description

<Desc/Clms Page number 1>
PROCÉDÉ DE CONTRE-MESURE DANS UN COMPOSANT ÉLECTRONIQUE
Figure img00010001

METTANT EN OEUVRE UN ALGORITHME DE CRYPTOGRAPHIE La présente invention concerne un procédé de contre-mesure dans un composant électronique mettant en oeuvre un algorithme de cryptographie utilisant un ou plusieurs nombres secrets notamment une clé privée. Ils sont utilisés dans des applications où l'accès à des services ou à des données est sévèrement contrôlé. De tels composants ont une architecture formée autour d'un microprocesseur et de mémoires, dont une mémoire programme qui contient le (s) nombre (s) secret (s).
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 tels que l'algorithme RSA du nom de ses auteurs (Rivest, Shamir et Adleman), ou l'algorithme DSA, acronyme anglo-saxon pour Digital Signature Algorithm. Cette liste n'est bien sûr pas exhaustive. Ces algorithmes utilisent des calculs de multiplication modulaire par une puissance de x et/ou d'exponentiation modulaire à la puissance x, x étant un nombre secret.
De manière générale et succincte, ces algorithmes ont pour fonction de calculer un message chiffré ou
<Desc/Clms Page number 2>
signé à partir d'un message appliqué en entrée (à la carte) par un système hôte (serveur, distributeur bancaire...) et de nombres 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 les consommations de courant ou une analyse différentielle de consommation en courant lorsque le microprocesseur d'une carte 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 DPA, acronyme anglo-saxon pour Differential Power Analysis.
Le principe de ces attaques DPA repose sur le fait que la consommation en courant du microprocesseur exécutant des instructions varie selon la donnée manipulée.
<Desc/Clms Page number 3>
Figure img00030001
Notamment, quand une instruction exécutée par le microprocesseur nécessite une manipulation d'une donnée bit par bit, on a deux profils de courant différents selon que ce bit vaut"1"ou"O". 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 l'attaque DPA exploite 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 d'une attaque en courant, on se reportera à la demande de brevet FR no2 789 776.
Ainsi en mesurant la consommation en courant de la carte par exemple, lors de ces calculs de multiplication modulaire par une puissance de x et/ou d'exponentiation modulaire à la puissance x, x étant un nombre secret x comme par exemple une clé privée, un fraudeur peut, à partir de multiples mesures, déduire la suite de bits composant la clé x.
Sachant que la clé x est un grand nombre représenté sur 512, voire 1024 bits, on admet qu'il faut en moyenne 40 000 mesures de consommation pour pouvoir déduire x. A l'échelle informatique, c'est réalisable ; en particulier pour un fraudeur disposant par exemple d'une carte à puce volée et d'un système apte à effectuer et enregistrer un nombre suffisant de mesures de consommation de la carte.
<Desc/Clms Page number 4>
D'autres attaques de type TA/SPA (Timing Attack/Single Power Attack) existent et sont l'objet de problèmes majeurs. A l'inverse des attaques DPA, l'analyse de consommation de courant s'effectue dans le temps par l'attaquant.
Le but de la présente invention est donc de protéger le nombre secret x contre ce genre d'attaque DPA ou autres, intervenant lorsque x est utilisé dans des calculs de multiplication et/ou d'exponentiation modulaires, en modifiant le déroulement du calcul, d'un calcul à l'autre.
Le nombre secret x étant en général un nombre premier, la modification du calcul faisant intervenir x est obtenue en substituant dans le calcul un nombre x' à x, x'permettant d'une part d'obtenir le même résultat qu'avec x et pouvant d'autre part être décomposé en i facteurs xi, x2,..., xi (x'= xi. x2..... x).
On va illustrer les avantages de cette modification sur un exemple de calcul de multiplication modulaire à la puissance x de la forme z. xp mod t, en prenant P=l.
Selon l'invention, x'est tel que : z. x mod t = z. x'mod t = z. (Xi. X2..... xi) mod t
Le produit z. x'peut être obtenu par différentes étapes. On peut multiplier z directement par le nombre x' ; on peut aussi multiplier z par les facteurs de x' en les prenant dans l'ordre xi, dz,..., xi au fur et à mesure que les étapes de la multiplication se déroulent. Ces étapes sont représentées dans la formule suivante par des parenthèses :
Figure img00040001

Z. (Xi-X2-----Xi) = ( ( (Z-Xi)-X2)----)-Xi
<Desc/Clms Page number 5>
Figure img00050001

En permutant en outre l'ordre des facteurs d'un calcul à l'autre (en prenant Xi. X2..... xi par exemple pour le calcul de z. x mod t suivant), on modifie les étapes de la multiplication.
On change ainsi la forme de x'd'un calcul à l'autre : on multiplie alors le nombre de mesures de consommation à effectuer pour déduire x'. Ce nombre de mesures devient tellement important qu'il devient quasiment impossible de déduire x'et a fortiori x.
En effet, il y a i. (i-1). (i-2)..... 2=i ! possibilités de permutations de l'ordre des facteurs.
En choisissant i=8 par exemple, on obtient 40230 possibilités de calcul. Il faudrait alors en moyenne 40000 x 40230 soit environ 16 millions de mesures de consommation pour déduire x', ce qui devient tout à fait dissuasif pour l'attaquant. Dans la pratique plus de 8 facteurs peuvent être utilisés, ce qui rend l'attaque extrêmement difficile.
L'invention a pour objet un procédé de contremesure dans un composant électronique mettant en oeuvre un algorithme de cryptographie utilisant des moyens de calcul destinés à effectuer des opérations de multiplication modulaire par une puissance de x et/ou de calcul d'exponentiation modulaire à la puissance x, x étant un nombre entier, principalement caractérisé en ce que, le nombre x se présentant sous la forme d'un produit de facteurs xi, x2,..., Xi, prédéterminés, il consiste à :
<Desc/Clms Page number 6>
a) choisir à chaque opération effectuée, une permutation aléatoire P, à considérer le nombre x sous la forme XP (1). Xp (2)..... Xp (i), b) effectuer ledit calcul à partir de cette nouvelle forme de x.
Selon une caractéristique de l'invention, le calcul effectué est de la forme zx mod t, z et t étant des nombres entiers.
L'algorithme de cryptographie est éventuellement un algorithme RSA.
Selon une autre caractéristique de l'invention, le calcul consiste à effectuer x-1 mod t, t étant un nombre entier q et x un nombre K aléatoire éventuellement de N bits, ou z. x mod t, z et t étant des nombres entiers.
L'algorithme de cryptographie est éventuellement un algorithme DSA.
Selon une caractéristique additionnelle, le procédé de contre-mesure comprend une étape préalable consistant à initialiser le composant électronique pour ses utilisations futures, le composant électronique mettant alors en oeuvre les étapes a) et b) du procédé, l'étape préalable consistant à : - choisir un nombre entier i, - calculer un nombre x'tel que x'= x1, x2. ... . xi, les facteurs x1, X2,..., xi étant des entiers, et tel qu'en remplaçant x par x'dans ledit calcul, on obtienne le même résultat, - à mémoriser les facteurs xi, X2,..., Xl à la place de x.
L'étape préalable peut être réalisée par ledit composant électronique ou par un autre composant électronique.
<Desc/Clms Page number 7>
Figure img00070001
De préférence, chaque facteur Xl,..., Xi est inférieur à une valeur limite déterminée.
Dans certains cas, comme par exemple pour l'algorithme RSA, x'= x+k mod (D (t), et comme par exemple pour l'algorithme DSA, x'= x + k. (t-1), k étant un entier supérieur ou égal à 1.
Dans d'autres cas, comme par exemple pour l'algorithme DSA, les facteurs xl,..., xi sont des nombres aléatoires de L bits, N > L et i=N/L.
L'invention concerne également un composant électronique de sécurité, caractérisé en ce qu'il met en oeuvre le procédé de contre-mesure tel que précédemment décrit, et en ce qu'il comprend des moyens de permutation aléatoire et/ou un générateur de nombres aléatoires.
L'invention concerne aussi une carte à puce comprenant un composant électronique de sécurité tel que décrit.
D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description faite à titre d'exemple non limitatif et au regard de la figure 1 qui représente un schéma-bloc d'une carte à puce dans laquelle on peut mettre en oeuvre un procédé de contre-mesure selon l'invention.
On va plus particulièrement considérer un algorithme de cryptographie à clé publique.
On rappelle qu'un algorithme de cryptographie à clé publique d'un message, peut être décomposé en sous-
<Desc/Clms Page number 8>
algorithmes de génération des clés privée et publique, de cryptage (ou chiffrement) du message, et de décryptage du message chiffré. On peut citer l'algorithme RSA comme exemple d'algorithme de cryptographie de ce type.
Dans certains cas, le sous-algorithme de cryptage est remplacé par un sous-algorithme de signature du message et le sous-algorithme de décryptage est remplacé par un sous-algorithme de vérification du message signé. L'algorithme DSA est de ce type.
Le cryptage/la signature du message est réalisée par un composant électronique. Le message chiffré/signé est en général envoyé à un composant électronique destinataire apte à décrypter/vérifier ledit message chiffré/signé.
Le décryptage/la vérification du message est réalisé par le composant électronique destinataire c'est-à-dire un autre composant électronique que celui qui a réalisé le cryptage/la signature.
Un même composant électronique peut aussi être apte à chiffrer/signer un message et à l'envoyer à un composant électronique destinataire et apte à recevoir un message chiffré/signé d'un composant électronique émetteur et à le décrypter/vérifier.
Préalablement à leur mise en service, ces composants électroniques sont initialisés, c'est-à-dire que les données et les programmes permettant de mettre en oeuvre les sous-algorithmes de cryptographie les concernant sont stockés dans leur mémoire programme.
L'initialisation peut être réalisée par le composant électronique lui-même ou par un autre
<Desc/Clms Page number 9>
composant électronique éventuellement intégré dans un dispositif tel qu'un ordinateur.
On va à présent considérer plus particulièrement les algorithmes de cryptographie utilisant un calcul d'exponentiation modulaire à la puissance x, notamment
Figure img00090001

le calcul ZX mod t, z, x et t étant des entiers.
On cherche un nombre z'décomposable en i facteurs Xl, X2,..., x, c'est-à-dire tel que x'= xl. X2..... xi, et tel que, zx mod t donne les mêmes résultats que zx mod t : X, zxmodt = z"'modt = z"'"'modt On peut éventuellement imposer que chacun des facteurs xl,... Xi respecte une condition de valeur limite, comme on le verra plus loin dans un exemple.
Lors du processus d'initialisation du composant électronique, les facteurs xl,..., xi sont mémorisés dans le composant électronique, à la place de x.
On va considérer plus précisément comme exemple d'algorithme de cryptographie utilisant le calcul zx mod t, le sous-algorithme de décryptage de l'algorithme RSA.
On rappelle au préalable les différentes étapes de cet algorithme RSA.
L'étape de génération des clés privée et publique RSA consiste à : - choisir 2 grands nombres premiers de tailles équivalentes p et q ; - définir n=p. q et (D (n) = (p-l). (q-l) (la fonction (D (n) est appelée totient) ;
<Desc/Clms Page number 10>
Figure img00100001

- choisir un nombre e aléatoire tel que l < e < C (n) et tel que le plus grand dénominateur commun entre e et # (n) soit 1 ; - choisir d tel que 1 < d < # (n) et tel que e. d=l mod # (n).
La clé publique est (n, e) et la clé privée est d.
L'étape de cryptage RSA d'un message m (0 < =m < =n-1) consiste à calculer c = me mod n, c étant le message chiffré de m.
L'étape de décryptage RSA du message chiffré c consiste à calculer m= Cd mod n.
On souhaite protéger contre les attaques en courant, la clé privée d utilisée lors du décryptage RSA. On applique le procédé selon l'invention en considérant dans la formule zx mod t que z = c, x = d et t = n.
On obtient alors x'de la façon suivante : k=l ; tant que les facteurs xl,..., xi de x'=x+k. mod (D (n) n'existent pas alors, k=k+1 ; mémorisation des facteurs x1, ..., xi, à la place de la clé privée d.
On va illustrer le calcul de x'dans l'exemple suivant, en prenant i=3, x=d=3 et # (n) =6 : pour k=l, x+k. mod (D (n) = 9 = 3. 3 pour k=2, x+k. mod (D (n) = 15 = 3. 5 pour k=3, x+k. mod # (t) = 21 = 3. 7
Figure img00100002

pour k=4, x+k. mod (D (n) = 27 = 3. 3. 3
<Desc/Clms Page number 11>
Figure img00110001

On a alors x'=27 et xl=3, x2=3, x3=3.
Bien sûr le procédé selon l'invention est mis en oeuvre avec des nombres i, x et (D (n) tels que par exemple i=64, x est un nombre de 512 bits environ et (D (n) de 1024 bits environ.
Selon un mode de réalisation préférentiel, on
Figure img00110002

impose aux facteurs kl,.. xi une valeur limite.
On obtient alors x'de la façon suivante : k=l ; tant que les facteurs ei,..., x, de x'=x+k. mod (D (t) ne sont pas inférieurs à 2 alors, k=k+l ; mémorisation des facteurs ei,..., xi à la place de la clé secrète x.
La valeur limite 264 qui signifie que les facteurs sont écrits sur 64 bits, est indiquée à titre d'exemple ; on peut choisir 128,132, ou... bits.
Par la suite, on substituera cx'mod n à chaque nouveau calcul de cd mod n, c'est-à-dire à chaque nouveau décryptage, en prenant les facteurs de x'dans un ordre différent, celui obtenu à la suite d'une permutation aléatoire P des facteurs kl,.., xi de x'.
On va à présent illustrer une permutation aléatoire P en prenant par exemple i=5 : x'= x1, x2, x3, x4, x5
Le premier calcul s'effectue en considérant d'abord Xi puis X2,..., puis X5.
Avant d'effectuer un second calcul, on applique par exemple la permutation P suivante P (1) =5, P (2) =3, P (3) =4, P (4) =2 et P (5) =1.
<Desc/Clms Page number 12>
Figure img00120001
On a ainsi x'= X5. X3. X4. X2. Xi et ce second calcul s'effectue en considérant d'abord X5 puis X3, puis X4, puis X2 et enfin xl.
Bien sûr le procédé selon l'invention est mis en oeuvre avec un nombre i plus grand, comme par exemple i=64.
Ainsi selon une permutation aléatoire P, x' devient : x' = xp(1)-xp(2). ... . xp (i)
Le calcul s'effectue alors en considérant d'abord xp (l) puis xp (2), etc.
On obtient alors :
Figure img00120002

, (..."F (j) cdmodn=c"modn = c ""'modn Etant donné les propriétés de ce calcul modulaire, le calcul sera obtenu de la façon suivante : choix de P ;
A = c ; pour j= 1 à i, A = Axp@ modn;
Lorsque j a atteint la valeur i, A contient le résultat de cx mod n.
On considère à présent un autre exemple d'algorithme de cryptographie utilisant un calcul de la forme zx mod t. Il s'agit de l'algorithme DSA dont on rappelle les différentes étapes.
L'étape de génération des clés privée et publique DSA consiste à :
Figure img00120003

159 160.
- choisir un grand nombre premier q, 21S9 < q < 2l6O ;
<Desc/Clms Page number 13>
Figure img00130001

- choisir b, 0 < =b < =8 et un nombre premier p tel que 511. 64. bpsi2. 64. b q q divise (p-1) ; - choisir g dans le groupe multiplicatif Zp* des entiers module p, et calculer &alpha;=g(p-1)/q mod p ; si a=l, on réitère le calcul en choisissant un nouveau g jusqu'à trouver &alpha;#1 ; générer aléatoirement un entier a tel que 1 < =a < =q-1 ; - calculer y=&alpha;a mod p.
La clé publique est (p, q, a, y) et la clé privée est a.
L'étape de signature DSA d'un message m consiste à : - générer aléatoirement un nombre K tel que O < K < q, sachant que K doit rester secret ; - calculer r= (aK mod p) mod q ; - calculer K-1 mod q ; - calculer s= K-1. (h (m) +a. r) mod q où h est une fonction de hachage ;
La signature du message m est (r, s).
L'étape de vérification de la signature DSA consiste à : - vérifier que O < r < q et O < s < q, sinon la signature n'est pas valide ; - calculer w = s-lmod q et h (m) ; - calculer ul = w. h (m) mod q et u2 = r. w mod q ; - calculer v = (ayu2 mod p) mod q ; - la signature est valide seulement si : v = r.
<Desc/Clms Page number 14>
On souhaite protéger contre les attaques en courant, le nombre aléatoire K secret, présent deux fois lors de l'étape de signature DSA : lors du calcul de r ou de s.
On applique le procédé selon l'invention en considérant que aK mod p est de la forme ZX mod t avec z = a, x = K et t=p. Le nombre K étant un nombre aléatoire de N bits, pour obtenir les mêmes résultats dans les calculs faisant intervenir K, en remplaçant K par x', il faut que x'soit également un nombre aléatoire de N bits.
Les composants électroniques mettant en oeuvre un algorithme de cryptographie tel que cet algorithme DSA, dispose de générateurs de nombre aléatoires de L bits.
Ainsi, pour obtenir un nombre aléatoire K de N bits, avec N > L, on génère N/L nombres aléatoires de L bits dont le produit permet d'obtenir un nombre aléatoire de N bits ; le rapport N/L est tel que si le résultat de N/L n'est pas entier, on prend l'entier supérieur.
Lorsque par exemple, le composant électronique dispose d'un générateur 32-bits et que K est un nombre aléatoire de 64 bits, le générateur 32-bits génère 2 (64/32) nombres aléatoires de 32 bits dont le produit sera le nombre aléatoire K de 64 bits.
Les facteurs ei,..., ei de x'sont les nombres aléatoires de L bits : i = N/L.
Mais dans la pratique, un générateur aléatoire Lbits est moins aléatoire qu'un générateur N-bits : on
<Desc/Clms Page number 15>
dit qu'il y a une perte d'entropie. Tous les nombres ne sont pas générés avec la même probabilité.
Pour compenser cette perte d'entropie, on multiplie x'par au moins un nombre aléatoire K'de L bits.
Finalement K sera remplacé dans les calculs par K', x' c'est-à-dire K'.x1. .... xN/L, en prenant les facteurs de x'dans un ordre différent d'un calcul à l'autre, celui obtenu à la suite d'une permutation aléatoire P des facteurs x1, ..., Xi de x', comme dans l'exemple précédent.
Le calcul de aK mod p devient celui de &alpha;K'.x1....xN/L modp et est obtenu de la façon suivante : choix d'une permutation P ;
A=a ; pour j=l à i, A = Axp(j) modp ;
A = AK'modp ;
Lorsque j a atteint la valeur i, A contient le résultat de aK''mod p.
On considère à présent le calcul K-1modq faisant également intervenir K. C'est un exemple de multiplication modulaire par une puissance de x, de la forme z. xPmod t en considérant : z=l, x=K, P=-l et t=q.
De même que dans le calcul précédent faisant
Figure img00150001

intervenir K, le calcul de K-lmodq devient celui de (K'. x')-lmodq et est obtenu de la façon suivante : choix d'une permutation P ; A=l ; pour j=l à i, A=A. xp'modq ;
<Desc/Clms Page number 16>
Figure img00160001

A = A. K'-'mod ; Lorsque j a atteint la valeur i, A contient le résultat de (K'. x')-1modq.
On souhaite également protéger contre les attaques en courant, la clé privée a utilisée lors de la signature DSA, dans le calcul a. r mod q. Ce calcul est aussi un exemple de multiplication modulaire par une puissance de x de la forme z. xPmod t en considérant : z=r, x=a, P=l et t=q.
On cherche alors un nombre x'décomposable en i facteurs x1, X2,..., Xi c'est-à-dire tel que x'= Xl. X2..... Xu et tel que x'. r mod q donne les mêmes résultats que a. r mod q : x'. r mod q = (x1.x2. .... x1). r mod q
On peut imposer aux facteurs xl,... xi une valeur limite, comme dans l'exemple précédent ; de même, les facteurs x1, ..., xi sont mémorisés dans la carte à puce à la place de la clé privée a, lors du processus d'initialisation de la carte à puce.
On obtient x'de la façon suivante : k=l ; tant que les facteurs x1, ..., xi de x'= a + k. (q-l) n'existent pas alors, k=k+l ; mémorisation des facteurs x1, ..., x1 à la place de la clé privée a.
On peut là encore imposer une valeur limite aux facteurs xl,..., xi. On obtient alors x'de la façon suivante : k=l ;
<Desc/Clms Page number 17>
Figure img00170001

tant que les facteurs xl,..., xi de x'= x + k. (q-l) ne sont pas inférieurs à 2 alors, k=k+l ; mémorisation des facteurs xl,..., xi à la place de la clé privée a.
Par la suite comme dans l'exemple précédent, on substituera x'. r mod q pour chaque nouveau calcul de a. r mod q, c'est-à-dire à chaque nouvelle signature, en prenant les facteurs de x'dans un ordre différent, celui obtenu à la suite d'une permutation aléatoire P des facteurs xl,..., Xi de x'. Ainsi x'devient : x1' = xp(1).xp(2). ... . xp (i)
La multiplication s'effectue alors en considérant d'abord Xp (l) puis Xp p(2), etc.
On obtient alors : x'. r mod q = (xp (l). Xp (2..... Xp (i)). r mod q
Etant donné les propriétés de ce calcul modulaire, le calcul sera obtenu de la façon suivante : choix de P ;
A = r ; pour j= 1 à i, A = A. xp (j) mod q ;
Lorsque j a atteint la valeur i, A contient le résultat de x'. r mod q.
La présente invention s'applique aux algorithmes de cryptographie à clé publique, pour lequel des exemples de mise en oeuvre ont été décrits. Il s'applique plus généralement à tout algorithme de cryptographie dont l'exécution par le microprocesseur nécessite un calcul de multiplication modulaire par une puissance de x et/ou de calcul d'exponentiation modulaire à la puissance x, x étant un nombre secret.
<Desc/Clms Page number 18>
Un composant électronique 1 mettant en oeuvre un procédé de contre-mesure selon l'invention dans un algorithme de cryptographie, comprend typiquement, comme représenté sur la figure 1, un microprocesseur P. P, une mémoire programme 2 et une mémoire de travail 3. Des moyens 4 de permutation aléatoire, sont prévus qui fourniront les permutations aléatoires des facteurs kl,..., xi à chaque exécution de l'algorithme de cryptographie. Le composant électronique 1 peut également comporter un générateur de nombre aléatoire 5. Un tel composant peut tout particulièrement être utilisé dans une carte à puce 6, pour améliorer son inviolabilité.

Claims (19)

  1. Figure img00190001
    NOUVELLES REVENDICATIONS 1. Procédé de contre-mesure dans un composant électronique consistant à empêcher la mesure de consommation de courant générée par des manipulations bits par bits par la mise en oeuvre d'un algorithme de cryptographie utilisant des moyens de calcul destinés à effectuer des opérations de multiplication modulaire par une puissance de x et/ou de calcul d'exponentiation modulaire à la puissance x, x étant un nombre entier, caractérisé en ce que, le nombre x se présentant sous la forme d'un produit de facteurs xl, X2,..., x, prédéterminés, il consiste à : a) choisir à chaque opération effectuée, une permutation aléatoire P, et considérer le nombre x sous la forme xp (l). Xp (2)..... Xp (i), b) effectuer ledit calcul à partir de cette nouvelle forme de x.
  2. 2. Procédé de contre-mesure selon la revendication précédente, caractérisé en ce que le calcul effectué est de la forme zu mode t, z et t étant des nombres entiers.
  3. 3. Procédé de contre-mesure selon la revendication précédente, caractérisé en ce que z est un message chiffré c, t le produit n de deux nombres premiers et x une clé privée d.
    <Desc/Clms Page number 20>
  4. 4. Procédé de contre-mesure selon l'une des revendications précédentes, caractérisé en ce que l'algorithme de cryptographie est un algorithme RSA.
  5. 5. Procédé de contre-mesure selon la revendication 2, caractérisé en ce que x est un nombre K aléatoire et t un nombre premier p.
  6. 6. Procédé de contre-mesure selon la revendication 1, caractérisé en ce que le calcul effectué consiste à effectuer x-l mod t, t étant un nombre entier q et x un nombre K aléatoire.
  7. 7. Procédé de contre-mesure selon la revendication précédente, caractérisé en ce que x est un nombre aléatoire de N bits.
  8. 8. Procédé de contre-mesure selon la revendication 1, caractérisé en ce que le calcul effectué est de la forme z. x mod t, z et t étant des nombres entiers.
  9. 9. Procédé de contre-mesure selon la revendication précédente, caractérisé en ce que x est une clé privée a, z un aléa r et t un nombre premier q.
  10. 10. Procédé de contre-mesure selon la revendication 1 ou l'une des revendications 5 à 9, caractérisé en ce que l'algorithme de cryptographie est un algorithme DSA.
    <Desc/Clms Page number 21>
  11. 11. Procédé de contre-mesure selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comprend une étape préalable consistant à initialiser le composant électronique pour ses utilisations futures, le composant électronique mettant alors en oeuvre les étapes a) et b) du procédé, l'étape préalable consistant à : - choisir un nombre entier i, - calculer un nombre x'tel que x'= xi. x..... xi, les facteurs xi, x2, ..., Xi étant des entiers, et tel qu'en remplaçant x par x'dans ledit calcul, on obtienne le même résultat, - à mémoriser les facteurs x1, x2, ..., Xi à la place de x.
  12. 12. Procédé'selon la revendication précédente, caractérisé en ce que l'étape préalable est réalisée par ledit composant électronique.
  13. 13. Procédé selon la revendication 11, caractérisé en ce que l'étape préalable est réalisée par un autre composant électronique.
  14. 14. Procédé selon l'une des revendications 11 à 13, caractérisé en ce que chaque facteur x1, ..., x1 est inférieur à une valeur limite déterminée.
  15. 15. Procédé selon l'une des revendications 2 à 4 prise en combinaison avec l'une des revendications 11 à 14, l'algorithme de cryptographie étant éventuellement
    <Desc/Clms Page number 22>
    un algorithme RSA, caractérisé en ce que x'= x+k mod (t), k étant un entier supérieur ou égal à 1.
  16. 16. Procédé l'une des revendications 5 à 7 prise en combinaison avec l'une des revendications 11 à 14, l'algorithme de cryptographie étant éventuellement un algorithme DSA, caractérisé en ce que les facteurs xl,..., xi sont des nombres aléatoires de L bits, N > L et i=N/L.
  17. 17. Procédé selon l'une des revendications 8 à 10 prise en combinaison avec l'une des revendications 11 à 14, l'algorithme de cryptographie étant éventuellement un algorithme DSA, caractérisé en ce que x'= x + k. (t- 1), k étant un entier supérieur ou égal à 1.
  18. 18. Composant électronique de sécurité, 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 des moyens (4) de permutation aléatoire et/ou un générateur (5) de nombres aléatoires.
  19. 19. Carte à puce (6) comprenant un composant électronique (1) de sécurité selon la revendication 18.
FR0016993A 2000-12-22 2000-12-22 Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie Expired - Fee Related FR2818846B1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
FR0016993A FR2818846B1 (fr) 2000-12-22 2000-12-22 Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
FR0016993A FR2818846B1 (fr) 2000-12-22 2000-12-22 Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie

Publications (2)

Publication Number Publication Date
FR2818846A1 true FR2818846A1 (fr) 2002-06-28
FR2818846B1 FR2818846B1 (fr) 2004-03-05

Family

ID=8858170

Family Applications (1)

Application Number Title Priority Date Filing Date
FR0016993A Expired - Fee Related FR2818846B1 (fr) 2000-12-22 2000-12-22 Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie

Country Status (1)

Country Link
FR (1) FR2818846B1 (fr)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2009136361A1 (fr) * 2008-05-07 2009-11-12 Koninklijke Philips Electronics N.V. Dissimulation d'exposant.
WO2010070579A1 (fr) * 2008-12-15 2010-06-24 Nxp B.V. Système et procédé permettant de contrer des attaques par canaux auxiliaires contre le cryptage sur la base de groupes cycliques
FR2956932A1 (fr) * 2010-03-01 2011-09-02 Inside Contactless Procede de test de la resistance d'un circuit integre a une analyse par canal auxiliaire
EP2365659A1 (fr) * 2010-03-01 2011-09-14 Inside Secure Procédé de test de la résistance d'un circuit intégré à une analyse par canal auxiliaire
US8457919B2 (en) 2010-03-31 2013-06-04 Inside Secure Process for testing the resistance of an integrated circuit to a side channel analysis
DE102012015899A1 (de) * 2012-08-10 2014-02-13 Giesecke & Devrient Gmbh Verfahren zum Erzeugen von ausführbarem Programmcode

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1999035782A1 (fr) * 1998-01-02 1999-07-15 Cryptography Research, Inc. Procede et appareil cryptographiques resistant aux fuites

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1999035782A1 (fr) * 1998-01-02 1999-07-15 Cryptography Research, Inc. Procede et appareil cryptographiques resistant aux fuites

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
KOCHER P C: "TIMING ATTACKS ON IMPLEMENTATIONS OF DIFFIE-HELLMAN, RSA, DSS, AND OTHER SYSTEMS", ADVANCES IN CRYPTOLOGY - CRYPTO '96. 16TH. ANNUAL INTERNATIONAL CRYPTOLOGY CONFERENCE. SANTA BARBARA, AUG. 18 - 22, 1996. PROCEEDINGS, PROCEEDINGS OF THE ANNUAL INTERNATIONAL CRYPTOLOGY CONFERENCE (CRYPTO), BERLIN, SPRINGER, DE, vol. CONF. 16, 18 August 1996 (1996-08-18), pages 104 - 113, XP000626590, ISBN: 3-540-61512-1 *

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2009136361A1 (fr) * 2008-05-07 2009-11-12 Koninklijke Philips Electronics N.V. Dissimulation d'exposant.
US8600047B2 (en) 2008-05-07 2013-12-03 Irdeto Corporate B.V. Exponent obfuscation
WO2010070579A1 (fr) * 2008-12-15 2010-06-24 Nxp B.V. Système et procédé permettant de contrer des attaques par canaux auxiliaires contre le cryptage sur la base de groupes cycliques
CN102246456A (zh) * 2008-12-15 2011-11-16 Nxp股份有限公司 用于对抗对基于循环群的加密的侧通道攻击的系统和方法
FR2956932A1 (fr) * 2010-03-01 2011-09-02 Inside Contactless Procede de test de la resistance d'un circuit integre a une analyse par canal auxiliaire
EP2365659A1 (fr) * 2010-03-01 2011-09-14 Inside Secure Procédé de test de la résistance d'un circuit intégré à une analyse par canal auxiliaire
US8457919B2 (en) 2010-03-31 2013-06-04 Inside Secure Process for testing the resistance of an integrated circuit to a side channel analysis
DE102012015899A1 (de) * 2012-08-10 2014-02-13 Giesecke & Devrient Gmbh Verfahren zum Erzeugen von ausführbarem Programmcode

Also Published As

Publication number Publication date
FR2818846B1 (fr) 2004-03-05

Similar Documents

Publication Publication Date Title
JP4841785B2 (ja) 鍵の細分化によってアクセスを防止する携帯可能なデータ記憶媒体
EP2345202B1 (fr) Procédé de signature numérique en deux étapes
EP2893431B1 (fr) Protection contre canaux auxiliaires
EP1166494B1 (fr) Procedes de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type courbe elliptique
EP2296086B1 (fr) Protection d&#39;une génération de nombres premiers contre des attaques par canaux cachés
EP1327932A1 (fr) Dispositif et procédé de cryptage résistants aux attaques par observation des caractéristiques physiques d&#39;un circuit
EP2005291A2 (fr) Procédé de déchiffrement
FR2926652A1 (fr) Procede et dispositifs de contre-mesure pour cryptographie asymetrique a schema de signature
EP2638660B1 (fr) Protection contre les ecoutes passives
CN103221917A (zh) 加密运算中模幂的保护
EP2248009A2 (fr) Procede et dispositifs de contre-mesure pour cryptographie asymetrique
EP1166495A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type courbe elliptique
WO2005022820A1 (fr) Procede pour la mise en oeuvre securisee d&#39;un algorithme de cryptographie de type rsa et composant correspondant
FR2829335A1 (fr) Procede de brouillage d&#39;un calcul a quantite secrete
WO2005109183A1 (fr) Procede de protection d’un ensemble cryptographique par masquage homographique
FR2799851A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type rsa
FR2818846A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie
EP0980607A1 (fr) Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d&#39;aleas
EP1254408B1 (fr) Procede de calcul d&#39;exponentation modulaire dans un composant electronique mettant en oeuvre un algorithme de chiffrement a cle publique
FR2888690A1 (fr) Procede cryptographique pour la mise en oeuvre securisee d&#39;une exponentiation et composant associe
EP1520370A1 (fr) Procede et dispositifs cryptographiques permettant d alleger les calculs au cours de transactions
FR2879866A1 (fr) Procede et dispositif d&#39;execution d&#39;un calcul cryptographique
FR3016987A1 (fr) Echelle de montgomery desequilibree
WO2002001343A1 (fr) Procedes de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type courbe elliptique de koblitz
EP4572223A1 (fr) Procédé pour le calcul d&#39;une fonction dans un contexte boîte bleanche et système associé

Legal Events

Date Code Title Description
ST Notification of lapse

Effective date: 20090831