[go: up one dir, main page]

WO2002050658A1 - Procedes de contre-mesure dans un composant electronique mettant en ouvre un algorithme de cryptographie a cle publique de type rsa - Google Patents

Procedes de contre-mesure dans un composant electronique mettant en ouvre un algorithme de cryptographie a cle publique de type rsa Download PDF

Info

Publication number
WO2002050658A1
WO2002050658A1 PCT/FR2001/004081 FR0104081W WO0250658A1 WO 2002050658 A1 WO2002050658 A1 WO 2002050658A1 FR 0104081 W FR0104081 W FR 0104081W WO 0250658 A1 WO0250658 A1 WO 0250658A1
Authority
WO
WIPO (PCT)
Prior art keywords
exponent
modulo
integer
result
bits
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.)
Ceased
Application number
PCT/FR2001/004081
Other languages
English (en)
Inventor
Jean-Sébastien CORON
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 AU2002225112A priority Critical patent/AU2002225112A1/en
Publication of WO2002050658A1 publication Critical patent/WO2002050658A1/fr
Anticipated expiration legal-status Critical
Ceased 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/723—Modular exponentiation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06K—GRAPHICAL DATA READING; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
    • G06K19/00—Record carriers for use with machines and with at least a part designed to carry digital markings
    • G06K19/06—Record carriers for use with machines and with at least a part designed to carry digital markings characterised by the kind of the digital marking, e.g. shape, nature, code
    • G06K19/067—Record carriers with conductive marks, printed circuits or semiconductor circuit elements, e.g. credit or identity cards also with resonating or responding marks without active components
    • G06K19/07—Record carriers with conductive marks, printed circuits or semiconductor circuit elements, e.g. credit or identity cards also with resonating or responding marks without active components with integrated circuit chips
    • G06K19/073—Special arrangements for circuits, e.g. for protecting identification code in memory
    • G06K19/07309—Means for preventing undesired reading or writing from or onto record carriers
    • G06K19/07363—Means for preventing undesired reading or writing from or onto record carriers by preventing analysis of the circuit, e.g. dynamic or static power analysis or current analysis
    • 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
    • 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/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves

Definitions

  • the present invention relates to a countermeasure method in an electronic component implementing an RSA type public key encryption algorithm.
  • the disadvantage of the secret key encryption system is that said system requires the prior communication of the key K between the two persons via a secure channel, before any encrypted message is received. be sent through the unsecured channel.
  • the term “secure channel” is understood to mean a channel for which it is impossible to know or modify the information which passes through said channel. Such a secure channel can be achieved by a cable connecting two terminals, owned by the two said people.
  • Public key cryptography solves the problem of distributing keys to through an unsecured channel.
  • the principle of public key cryptography consists in using a pair of keys, a public encryption key and a private decryption key. It must be computationally infeasible to find the private decryption key from the public encryption key.
  • a person A wishing to communicate information to a person B uses the public encryption key of person B. Only person B has the private key associated with his public key. Only person B is therefore capable of deciphering the message addressed to him.
  • McEliece this encryption system is based on the theory of algebraic codes. It is based on the problem of decoding linear codes;
  • Elliptic curves the elliptic curve encryption system constitutes a modification of existing cryptographic systems to apply them to the domain of elliptic curves.
  • the advantage of elliptical curve encryption systems is that they require a smaller key size than other encryption systems.
  • the RSA encryption system is the most widely used public key encryption system. It can be used as an encryption method or as a signature method.
  • the RSA encryption system is used in smart cards, for certain applications of these. Possible applications of RSA on a smart card are access to databases, banking applications, remote payment applications such as for example pay-TV, petrol distribution or payment of motorway tolls.
  • the first part is the generation of the RSA key.
  • Each user creates an RSA public key and a corresponding private key, according to the following 5-step process:
  • the public key is (n, e); the private key is d or (d, p, q)
  • the integers e and d are respectively called encryption exponents and decryption exponents.
  • the integer n is called the module.
  • the second part of the RSA key generation consists in the encryption of a clear message denoted by m using an algorithm with Km ⁇ n in a message.
  • encrypted noted c is as follows
  • the third part of the generation of the RSA key consists of decryption using the private exponent of decryption by means of an algorithm.
  • the algorithm for decrypting an encrypted message denoted c with Kc ⁇ n into a clear message denoted m is as follows:
  • the previously described RSA decryption algorithm can be performed by two different methods. These two methods are: decryption with CRT and decryption without CRT.
  • CRT is an acronym for Chinese Remainder Theorem.
  • the advantage of the decryption algorithm with CRT is that it is theoretically 4 times faster than the decryption algorithm without CRT.
  • the decryption algorithm with CRT consists of the following 4 steps:
  • the "square and multiply” algorithm takes as input a number c, an exponent d and a module n.
  • the first 1 is the most significant bit and the last 1 the least significant bit.
  • the "square and multiply” algorithm has the following 3 steps:
  • step 3 In the case of RSA decryption without CRT, the decryption is carried out as described previously using the "square and multiply” algorithm. In this case, the "square and multiply” algorithm therefore takes as input the encrypted message c, the module n and the decryption exponent d.
  • the decryption is carried out as described previously using twice the "square and multiply" algorithm for the execution of step 3) of the decryption algorithm with CRT.
  • the first time the algorithm takes as input the integer cp, the module p and the exponent dp.
  • the second time the algorithm takes as input the integer cq, the module q and the exponent dq.
  • SPA acronym for Simple Power Analysis.
  • the principle of these SPA attacks is based on the fact that the current consumption of the microprocessor executing instructions varies according to the data manipulated. In particular, when an instruction manipulates data of which a particular bit is constant, the value of the other bits may vary, the analysis of the current consumption linked to the instruction shows that the average consumption of the instruction is not not the same depending on whether the particular bit takes the value 0 or 1.
  • the SPA type attack therefore makes it possible to obtain additional information on the intermediate data manipulated by the microprocessor of the card during the execution of a cryptographic algorithm . This additional information can in certain cases make it possible to reveal the private parameters of the decryption algorithm, rendering the cryptographic system insecure.
  • the method of the invention consists in developing a countermeasure making it possible to prevent an attack by current measurement in which the attacker is able to read the bits manipulated by the processor performing the exponentiation operation.
  • the method of the invention consists manipulating the bits of the exponent d in a random order, unknown to the attacker, so that even if the attacker is able to find the value of these bits, he cannot determine the corresponding exponent d.
  • the method of the invention divides the exponent into blocks of k bits, each of the blocks being divided into sub-blocks of r bits.
  • t the number of bits of the exponent.
  • t a multiple of the integer k. If this is not the case, the number of bits of the exponent d is consequently increased.
  • the size of a block k is a multiple of the size of a sub-block of r bits.
  • the method of the invention comprises the following steps:
  • step 3) 5) Return to step 3) 2) as long as the set S does not include all the integers between 0 and u-1;
  • the countermeasure process can be applied to any process using exponentiation modular, whether for carrying out an encryption process, a signature process, an authentication process, a key exchange process.
  • the countermeasure method can also be applied in the context of the use of an elliptical curve method.
  • the application of the previous countermeasure method makes it possible to protect the exponentiation algorithm against attacks by current measurement.
  • the principle of the process consists in making the reading of the exponent used in the exponentiation random.
  • the invention is particularly intended for use in an electronic portable object of the smart card type.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Microelectronics & Electronic Packaging (AREA)
  • Computer Security & Cryptography (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Storage Device Security (AREA)

Abstract

L'algorithme de chiffrement RSA est l'algorithme de chiffrement à clef publique le plus utilisé. Il est apparu que son application dans le cadre d'un environnement de type carte à puce était vulnérable à des attaques de type DPA (Differential Power Analysis). La présente invention consiste en la description de différents procédés de contre-mesure permettant de se prémunir contre ce type d'attaque DPA. Ces contre-mesures ne diminuent pas les performances de l'algorithme RSA et sont facilement utilisables dans un composant électronique de type carte à puce.

Description

PROCEDES DE CONTRE -MESURE DANS UN COMPOSANT ELECTRONIQUE METTANT EN ŒUVRE UN ALGORITHME DE CRYPTOGRAPHIE A CLE PUBLIQUE DE TYPE RSA
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 RSA.
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 ou 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. La 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. Il 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
1 ' authent i fication par l'utilisation de signature électronique .
La première réalisation de schéma de chiffrement à clef publique fut mise 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. Il est basé sur le problème du décodage de codes linéaires ;
ElGamal : 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'avantage des systèmes de chiffrement à courbes elliptiques est qu'ils nécessitent une taille de clef plus petite que pour les autres systèmes de chi ffrement .
Le système de chiffrement RSA est le système de chiffrement à clé publique le plus utilisé. Il peut être utilisé comme procédé de chiffrement ou comme procédé de signature. Le système de chiffrement RSA est utilisé dans les cartes à puce, pour certaines applications de celles-ci. Les applications possibles de RSA sur une carte à puce sont l'accès à des banques de données, des applications bancaires, des applications de paiements à distance comme par exemple la télévision à péage, la distribution d'essence ou le paiement de péages d'autoroute.
Le principe du système de chiffrement RSA est le suivant. Il peut être divisé en trois parties distinctes qui sont :
1) La génération de la paire de clés RSA
2) Le chiffrement d'un message clair en un message chiffré, et
3) Le déchiffrement d'un message chiffré en un message clair.
La première partie est la génération de la clef RSA. Chaque utilisateur crée une clé publique RSA et une clé privée correspondante, suivant le procédé suivant en 5 étapes :
1) Générer deux nombres premiers distincts p et q de même taille
2) Calculer n=pq et φ=(p-l) (q-l) 3) Sélectionner aléatoirement un entier e,
Ke<φ, tel que pgcd(e, φ)=l
4) Calculer l'unique entier d, Kd<φ tel que e*d=l mod φ
5) La clé publique est (n,e) ; la clé privée est d ou (d,p,q)
Les entiers e et d sont appelés respectivement exposant de chiffrement et exposant de déchiffrement. L'entier n est appelé le module.
La seconde partie de la génération à clé RSA consiste au chiffrement d'un message clair noté m au moyen d'un algorithme avec Km<n en un message chiffré noté c est le suivant
Calculer c=mΛe mod n
La troisième partie de la génération de la clé RSA consiste au déchiffrement utilisant l'exposant privé d de déchiffrement au moyen d'un algorithme. L'algorithme de déchiffrement d'un message chiffré noté c avec Kc<n en un message clair noté m est le suivant :
Calculer m=cAd mod n.
L'algorithme de déchiffrement RSA précédemment décrit peut s'effectuer par deux méthodes différentes. Ces deux méthodes sont : déchiffrement avec CRT et déchiffrement sans CRT. CRT est un acronyme pour Chinese Remainder Theorem. L'avantage de l'algorithme de déchiffrement avec CRT est qu'il est théoriquement 4 fois plus rapide que l'algorithme de déchiffrement sans CRT. L'algorithme de déchiffrement sans CRT consiste à calculer m=cΛd mod n comme décrit précédemment.
L'algorithme de déchiffrement avec CRT consiste en les 4 étapes suivantes :
1) Calculer cp=c modulo p et cq=c modulo q 2) Calculer dp=d modulo p-1 et dq=d modulo q- 1
3) Calculer mp=cpΛdp modulo p et mq=cqΛdq modulo q
4) Calculer m=mp* q* ( qA ( - 1 ) mod p ) +mq*p* (p ( - 1 ) mod q )
Pour réaliser les exponentiations modulaires nécessaires dans les procédés de calcul décrits précédemment, plusieurs algorithmes existent :
- Algorithme appelé " square and multiply
- Algorithme avec chaines 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 " square and multiply ". L'algorithme " square and multiply " prend en entrée un nombre c, un exposant d et un module n. L'exposant d est noté d=(d(t), d(t-l), d(0)), où (d(t), d(t-l),, d(0)) étant la représentation binaire de d, avec d(t) le bit de poids fort et d(0) le bit de poids faible. Par exemple la représentation du nombre cinq en binaire est 101, provenant du fait que 5= 1 * 2 Λ2 + 0* 2 Λ 1 + 1 * 2 Λ 0. Le premier 1 est le bit de poids fort et le dernier 1 le bit de poids faible. L'algorithme retourne en sortie le nombre m=c d mod n. L'algorithme " square and multiply " comporte les 3 étapes suivantes :
1) Initialiser une variable entière A avec la valeur c ;
2) Pour i allant de t-1 à 0 faire:
2a) Remplacer A par A*A mod n ; 2b) Si d(i)=l remplacer A par A*c mod n ;
3) Retourner à l'étape 1 ci-dessus. Dans le cas du déchiffrement RSA sans CRT, le déchiffrement s'effectue comme décrit précédemment en utilisant l'algorithme " square and multiply ". Dans ce cas, l'algorithme " square and multiply " prend donc en entrée le message chiffré c, le module n et l'exposant de déchiffrement d.
Dans le cas du déchiffrement RSA avec CRT, le déchiffrement s'effectue comme décrit précédemment en utilisant deux fois l'algorithme " square and multiply " pour l'exécution de l'étape 3) de l'algorithme de déchiffrement avec CRT. La première fois, l'algorithme prend en entrée l'entier cp, le module p et l'exposant dp. La deuxième fois, l'algorithme prend en entrée l'entier cq, le module q et l'exposant dq.
Il est possible d'effectuer ces opérations à l'intérieur d'une carte à puce, lesdites opérations étant effectuées par le microprocesseur de la carte à puce. Il est apparu que 1 ' implémentation sur carte à puce d'un algorithme de chiffrement à clé publique du type RSA était vulnérable à des attaques consistant en une analyse de la consommation de courant permettant de retrouver la clé privée de déchiffrement. Ces attaques sont appelées attaques
SPA, acronyme pour Simple Power Analysis. Le principe de ces attaques SPA repose sur le fait que la consommation de courant du microprocesseur exécutant des instructions varie selon la donnée manipulée . En particulier, lorsqu'une instruction manipule une 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 SPA 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échi ffrement , rendant le système cryptographique non sûr .
L' inconvénient de la méthode « square and multiply » décrite précédemment est que les bits de l'exposant privé d sont manipulés un par un, dans un ordre déterminé. Il est ainsi possible dans certains cas d'obtenir la valeur de ces bits en examinant la consommation de courant associée à l'exécution de la méthode « square and multiply », car la manipulation d'un bit de l'exposant d valant 1 ne donne pas la même consommation de courant que la manipulation d'un bit de l'exposant d valant 0.
Le procédé de l'invention consiste en l'élaboration d'une contremesure permettant de prévenir une attaque par mesure de courant dans laquelle l'attaquant est en mesure de lire les bits manipulés par le processeur réalisant l'opération d'exponentiation. Le procédé de l'invention consiste à manipuler les bits de l'exposant d dans un ordre aléatoire, inconnu de l'attaquant, de telle sorte que même si l'attaquant est en mesure retrouver la valeur de ces bits, il ne peut pas déterminer l'exposant d correspondant.
Le procédé de l'invention consiste en une méthode permettant de réaliser l'exponentiation c=mAd modulo N, où m est un entier, N le module, d est l'exposant, et c le résultat de 1 ' exponentiation.
Le procédé de l'invention divise l'exposant en blocks de k bits, chacun des blocks étant divisé en sous-blocks de r bits. On note t le nombre de bits de l'exposant. On suppose que t est un multiple de l'entier k. Si ce n'est pas le cas, on augmente en conséquence le nombre de bits de l'exposant d. On suppose de plus que la taille d'un block k est un multiple de la taille d'un sous-block de r bits. On note u l'entier tel que k=u*r.
On divise l'exposant d en L blocks de k bits, et on note : d=bd[L-l] .bd[L-2]...bd[l] .bd[0] .
Chacun des blocks bd est divisé en sous blocks de r bits, et on note : bd[i]=sd[i,u-l]...sd[i, 0]
Le procédé de l'invention comporte les étapes suivantes :
1) Calculer et mettre en mémoire dans un tableau d'entiers a[i] la valeur de mA(2 (r*i)) modulo N pour les entiers i allant de 0 à u-1 ; 2) Initialiser la variable c à 1 ; 3) Pour l'entier i variant entre 0 et L-l, on effectue :
3)1) Initialiser un ensemble d'entiers S à l'ensemble vide.
3)2) Tirer aléatoirement un entier j compris entre 0 et u-1, qui n'appartient pas à l'ensemble S ;
3)3) Calculer le résultat de l'exponentiation modulo N de a[j] avec l'exposant sd[i,j] ; cette exponentiation peut se réaliser par exemple à l'aide de la méthode « square and multiply » ; mettre le résultat en mémoire dans le tableau d'entiers b [ j ] ;
3)4) Ajouter l'élément j à l'ensemble S ;
3)5) Retourner à l'étape 3)2) tant que l'ensemble S ne comprend pas tous les entiers entre 0 et u-1 ;
3)6) Effectuer le produit modulo N de tous les éléments b[j] pour j variant de 0 à u-1 ; mettre le résultat dans la variable entière a ;
3)7) Effectuer le calcul a*cA(2Ak) et mettre le résultat dans c ; 4) Renvoyer le résultat c.
Le procédé de la contre-mesure peut s'appliquer tout procédé utilisant une exponentiation modulaire, que ce soit pour réaliser un procédé de chiffrement, un procédé de signature, un procédé d' authenti fication, un procédé d'échange de clef. Le procédé de la contre-mesure peut aussi s'appliquer dans le cadre de l'utilisation de méthode à base de courbe elliptique.
L'application du procédé de contre-mesure précédent permet de protéger l'algorithme d'exponentiation contre les attaques par mesure de courant. Le principe du procédé consiste à rendre aléatoire la lecture de l'exposant utilisé dans l'exponentiation. L'invention est particulièrement destinée à être utilisée dans un objet portable électronique de type carte à puce.

Claims

REVENDICATIONS
1. Procédé de contre-mesure consistant à prévenir une attaque par mesure de courant en réalisant le calcul d'exponentiation de formulation c=mAd modulo N, m étant un entier, N étant le module, d étant l'exposant, c étant le résultat de ladite exponentiation, ledit procédé divisant l'exposant en blocks de k bits, chacun des blocks étant divisé en sous-blocks de r bits, le nombre de bits de l'exposant étant un multiple de k, la taille d'un block k étant telle que k=u*r pour un entier u donné, l'exposant d étant divisé en L blocks de k bits, d étant représenté par d=bd[L-l] .bd[L- 2 ] ...bd [ 1 ] . bd [ 0 ] , chacun des blocks bd étant divisé en sous-blocks de r bits, un block bd étant noté bd [ i ] =sd [ i , u-1 ] ...sd [ i , 0 ] , ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes :
1) Calculer et mettre en mémoire dans un tableau d'entiers a[i] la valeur de m (2A(r*i)) modulo N pour les entiers i allant de 0 à u-1 ;
2) Initialiser la variable c à 1 ;
3) Pour l'entier i variant entre 0 et L-l, on effectue :
3)1) Initialiser un ensemble d'entiers S à l'ensemble vide ;
3)2) Tirer aléatoirement un entier j compris entre 0 et u-1, qui n'appartient pas à l'ensemble S ;
3)3) Calculer le résultat de l'exponentiation modulo N de a[j] avec l'exposant sd[i,j] et mettre le résultat en mémoire dans le tableau d'entiers b[j] ;
3)4) Ajouter l'élément j à l'ensemble S ;
3)5) Retourner à l'étape 3)2) tant que l'ensemble S ne comprend pas tous les entiers entre 0 et u-1 ;
3)6) Effectuer le produit modulo N de tous les éléments b[j] pour j variant de 0 à u-1 ; mettre le résultat dans la variable entière a ;
3)7) Effectuer le calcul a*cA(2Ak) et mettre le résultat dans c ; 4) Renvoyer le résultat c.
2. Procédé de cont e-mesure consistant à prévenir une attaque par mesure de courant selon la revendication 1, caractérisé en ce que l'exponentiation réalisée à l'étape 3)3) comporte les 3 étapes suivantes :
1) Initialiser une variable entière at avec la valeur a [ j ] ;
2) Pour it allant de r-1 à 0 faire:
2a) Remplacer at par at*at modulo N ; 2b) Si sd[i,it]=l remplacer at par at*a [ j ] modulo N;
3) Renvoyer le résultat at.
3. Procédé de contre-mesure selon la revendication 1 ou 2, caractérisé en ce qu'il s'applique à une méthode de chiffrement.
4. Procédé de contre-mesure selon la revendication 1 ou 2, caractérisé en ce qu'il s'applique à une méthode de signature électronique.
5. Procédé de contre-mesure selon la revendication 1 ou 2, caractérisé en ce qu'il s'applique à une méthode d'échange de clefs.
6. Procédé de contre-mesure selon la revendication 1 ou 2, caractérisé en ce qu'il s'applique à une méthode d' authent i ficat ion .
7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le procédé utilise la méthode des courbes elliptiques.
Composant électronique utilisant le procédé selon l'une quelconque des revendications précédentes caractérisé en ce qu'il peut être une carte à puce .
PCT/FR2001/004081 2000-12-19 2001-12-19 Procedes de contre-mesure dans un composant electronique mettant en ouvre un algorithme de cryptographie a cle publique de type rsa Ceased WO2002050658A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU2002225112A AU2002225112A1 (en) 2000-12-19 2001-12-19 Countermeasure methods in an electronic component using an rsa-type public key encryption algorithm

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0016577A FR2818473B1 (fr) 2000-12-19 2000-12-19 Procedes de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type rsa
FR00/16577 2000-12-19

Publications (1)

Publication Number Publication Date
WO2002050658A1 true WO2002050658A1 (fr) 2002-06-27

Family

ID=8857861

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2001/004081 Ceased WO2002050658A1 (fr) 2000-12-19 2001-12-19 Procedes de contre-mesure dans un composant electronique mettant en ouvre un algorithme de cryptographie a cle publique de type rsa

Country Status (3)

Country Link
AU (1) AU2002225112A1 (fr)
FR (1) FR2818473B1 (fr)
WO (1) WO2002050658A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007000702A2 (fr) 2005-06-29 2007-01-04 Koninklijke Philips Electronics N.V. Dispositif et procede de protection de dispositif de traitement de donnees contre une attaque ou analyse

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5999627A (en) * 1995-01-07 1999-12-07 Samsung Electronics Co., Ltd. Method for exponentiation in a public-key cryptosystem
WO2000067410A1 (fr) * 1999-04-29 2000-11-09 Motorola Inc. Procede pour prevenir les attaques par analyse de puissance sur des ensembles microelectroniques

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5999627A (en) * 1995-01-07 1999-12-07 Samsung Electronics Co., Ltd. Method for exponentiation in a public-key cryptosystem
WO2000067410A1 (fr) * 1999-04-29 2000-11-09 Motorola Inc. Procede pour prevenir les attaques par analyse de puissance sur des ensembles microelectroniques

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007000702A2 (fr) 2005-06-29 2007-01-04 Koninklijke Philips Electronics N.V. Dispositif et procede de protection de dispositif de traitement de donnees contre une attaque ou analyse
US8738927B2 (en) 2005-06-29 2014-05-27 Irdeto B.V. Arrangement for and method of protecting a data processing device against an attack or analysis

Also Published As

Publication number Publication date
AU2002225112A1 (en) 2002-07-01
FR2818473A1 (fr) 2002-06-21
FR2818473B1 (fr) 2003-04-18

Similar Documents

Publication Publication Date Title
EP2946284B1 (fr) Procédé de cryptographie comprenant une opération de multiplication par un scalaire ou une exponentiation
FR2791497A1 (fr) Procedes de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de crytographie a cle publique de type courbe elliptique
FR2760583A1 (fr) Systeme de verification de cartes de donnees
WO2001093014A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un alrogithme de cryptographie a cle publique sur courbe elliptique
EP1166495A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type courbe elliptique
EP1224765B1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type rsa
EP1350357B1 (fr) Procede d&#39;amelioration de la securite de schemas de chiffrement a clef publique
EP0909495B1 (fr) Procede de cryptographie a cle publique
WO2007104706A1 (fr) Procede de securisation d&#39;un calcul d&#39;une exponentiation ou d&#39;une multiplication par un scalaire dans un dispositif electronique
EP1325584A1 (fr) Procede d&#39;encodage de messages longs pour schemas de signature electronique a base de rsa
FR3024808A1 (fr) Procede de cryptographie sur courbe elliptique comprenant une detection d’erreur
FR2888690A1 (fr) Procede cryptographique pour la mise en oeuvre securisee d&#39;une exponentiation et composant associe
WO1998051038A1 (fr) Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d&#39;aleas
WO2002028011A1 (fr) Procede de transmission accelere de signature electronique
WO2002050658A1 (fr) Procedes de contre-mesure dans un composant electronique mettant en ouvre un algorithme de cryptographie a cle publique de type rsa
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
FR2818846A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie
WO2004111833A1 (fr) Procede de contre-mesure dans un composant electronique
WO2003021864A2 (fr) Procede de reduction de la taille d&#39;une signature rsa ou rabin
EP3716044B1 (fr) Protection d&#39;un calcul itératif
FR3010562A1 (fr) Procede de traitement de donnees et dispositif associe
FR2734679A1 (fr) Procede de cryptographie a cle publique base sur le logarithme discret
FR2797126A1 (fr) Procede d&#39;amelioration de performance de l&#39;operation de multiplication sur corps fini de caracteristique 2
FR3013476A1 (fr) Securisation de procede de cryptographie sur courbes elliptiques
FR2952774A1 (fr) Procede et dispositif permettant d&#39;optimiser le dechiffrement et la signature rsa pour mieux securiser les cartes bancaires et les telephones portables

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SD SE SG SI SK SL TJ TM TN TR TT TZ UA UG US UZ VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP