CA2288767A1 - Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d'aleas - Google Patents
Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d'aleas Download PDFInfo
- Publication number
- CA2288767A1 CA2288767A1 CA002288767A CA2288767A CA2288767A1 CA 2288767 A1 CA2288767 A1 CA 2288767A1 CA 002288767 A CA002288767 A CA 002288767A CA 2288767 A CA2288767 A CA 2288767A CA 2288767 A1 CA2288767 A1 CA 2288767A1
- Authority
- CA
- Canada
- Prior art keywords
- secret
- signature
- random
- message
- key
- 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.)
- Abandoned
Links
Classifications
-
- G—PHYSICS
- G07—CHECKING-DEVICES
- G07F—COIN-FREED OR LIKE APPARATUS
- G07F7/00—Mechanisms actuated by objects other than coins to free or to actuate vending, hiring, coin or paper currency dispensing or refunding apparatus
- G07F7/08—Mechanisms actuated by objects other than coins to free or to actuate vending, hiring, coin or paper currency dispensing or refunding apparatus by coded identity card or credit card or other personal identification means
- G07F7/10—Mechanisms actuated by objects other than coins to free or to actuate vending, hiring, coin or paper currency dispensing or refunding apparatus by coded identity card or credit card or other personal identification means together with a coded signal, e.g. in the form of personal identification information, like personal identification number [PIN] or biometric data
- G07F7/1008—Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q20/00—Payment architectures, schemes or protocols
- G06Q20/30—Payment architectures, schemes or protocols characterised by the use of specific devices or networks
- G06Q20/34—Payment architectures, schemes or protocols characterised by the use of specific devices or networks using cards, e.g. integrated circuit [IC] cards or magnetic cards
- G06Q20/341—Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q20/00—Payment architectures, schemes or protocols
- G06Q20/38—Payment protocols; Details thereof
- G06Q20/40—Authorisation, e.g. identification of payer or payee, verification of customer or shop credentials; Review and approval of payers, e.g. check credit lines or negative lists
- G06Q20/409—Device specific authentication in transaction processing
- G06Q20/4097—Device specific authentication in transaction processing using mutual authentication between devices and transaction partners
- G06Q20/40975—Device specific authentication in transaction processing using mutual authentication between devices and transaction partners using encryption therefor
-
- 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/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
- H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
- H04L9/0838—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these
- H04L9/0841—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these involving Diffie-Hellman or related key agreement protocols
-
- 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/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3247—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
- H04L9/3252—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/20—Manipulating the length of blocks of bits, e.g. padding or block truncation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/80—Wireless
Landscapes
- Engineering & Computer Science (AREA)
- Business, Economics & Management (AREA)
- Computer Security & Cryptography (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computer Networks & Wireless Communication (AREA)
- Accounting & Taxation (AREA)
- Theoretical Computer Science (AREA)
- General Business, Economics & Management (AREA)
- Strategic Management (AREA)
- Signal Processing (AREA)
- Microelectronics & Electronic Packaging (AREA)
- Finance (AREA)
- Storage Device Security (AREA)
Abstract
La présente invention concerne un système cryptographique, nécessitant normalement le tirage d'un aléa k, l'aléa étant un entier, caractérisé en ce qu'il est mis en oeuvre en remplaçant ledit aléa k par la quantité h(m/secret) où h est une fonction de hachage, m est le message intervenant dans ledit système et "secret" est un secret inconnu du monde extérieur au système cryptographique. Elle est particulièrement destinée à s'appliquer dans des appareils communiquants qui sont des cartes à puce, des cartes PCMCIA, des badges, des cartes sans contact ou tout autre appareil portable.
Description
GENERATEnR PSEUDO-ALÉATOIRE HASE SûR UNE FONCTION DE HACHAGE
POUR SYSTEMES CRYPTOGRAPHIQUES NÉCESSITANT LE TIRAGE D'ALÉAS
La présente invention décrit un système permettant de générer des signatures numériques ou des cryptogrammes nécessitant le tirage d'aléas (typ:iquement DSA, E1-Gamal, Fiat-Shamir, Guillou-Quisquater pour les signatures, E1-Gamal et McEliece pour le chiffrement), par des dispositifs de signature ou de chiffrement (typiquement microprocesseurs) dépourvus de i0 ressources matérielles ou logicielles permettant le tirage d'alêas.
Elle fournit en outre une parade, ou défense, contre certaines menaces (typiquement le chiffrement de messages courts et les récentes attaques publiêes par Coppersmith et al.
à Eurocrypt ' 96 dans les articles ~ Low Exponent wi th Related Message » et ~ Finding a small root of a univariate modular equation ») par la génération à peu de frais, c'est à dire peu coûteuse, d'une séquence aléatoire permettant de compléter l'information à traiter.
Elle permet également la gênération de facteurs d'aveuglement, utilisés dans le cadre des mécanismes de signatures en blanc ou de maquillage aléatoire.
Elle peut enfin être utilisée dans les protocoles d'échange de clés de type Diffie-Hellman.
Malgré une diffusion généralisêe et une bonne acceptation du concept de la carte à puce de la part du public, la plupart des applications pratiques sont apparues seulement voici quelques années, principalement à cause des limitations de puissance de calcul des cartes. Les progrès en matière de 3o capacité de stockage non volatile des informations, la sécurité
et la technologie des circuits (par exemple l'EEPROM) encouragent l'émergence rapide de nouvelles générations de
POUR SYSTEMES CRYPTOGRAPHIQUES NÉCESSITANT LE TIRAGE D'ALÉAS
La présente invention décrit un système permettant de générer des signatures numériques ou des cryptogrammes nécessitant le tirage d'aléas (typ:iquement DSA, E1-Gamal, Fiat-Shamir, Guillou-Quisquater pour les signatures, E1-Gamal et McEliece pour le chiffrement), par des dispositifs de signature ou de chiffrement (typiquement microprocesseurs) dépourvus de i0 ressources matérielles ou logicielles permettant le tirage d'alêas.
Elle fournit en outre une parade, ou défense, contre certaines menaces (typiquement le chiffrement de messages courts et les récentes attaques publiêes par Coppersmith et al.
à Eurocrypt ' 96 dans les articles ~ Low Exponent wi th Related Message » et ~ Finding a small root of a univariate modular equation ») par la génération à peu de frais, c'est à dire peu coûteuse, d'une séquence aléatoire permettant de compléter l'information à traiter.
Elle permet également la gênération de facteurs d'aveuglement, utilisés dans le cadre des mécanismes de signatures en blanc ou de maquillage aléatoire.
Elle peut enfin être utilisée dans les protocoles d'échange de clés de type Diffie-Hellman.
Malgré une diffusion généralisêe et une bonne acceptation du concept de la carte à puce de la part du public, la plupart des applications pratiques sont apparues seulement voici quelques années, principalement à cause des limitations de puissance de calcul des cartes. Les progrès en matière de 3o capacité de stockage non volatile des informations, la sécurité
et la technologie des circuits (par exemple l'EEPROM) encouragent l'émergence rapide de nouvelles générations de
2 cartes et d'applications de plus en plus ambitieuses telles que le nouveau standard de signature numérique Américain (DSA).
Une grande limitation des cartes à puce comme support d'implémentation d'algorithmes à clé publique est la nécessité
(fréquemment rencontrée), d'avoir un dispositif générant des nombres aléatoires à bord de la carte. En effet, la mise au point d'un tel dispositif, appelé aussi générateur, s'avère complexe et souvent instable (sensibilité aux phénomènes extérieurs à la carte tels que la température ambiante ou la l0 tension appliquée à la carte). Dans le cas où de tels systèmes cryptographiques sont mis en oeuvre sur un ordinateur, d'autres phénomènes, dus à la nature même des générateurs aléatoires logiciels viennent perturber la qualité des aléas. Typiquement, une méthode de génération d'aléas très populaire consiste à
mesurer le temps écoulé entre deux touches du clavier appuyées par l'utilisateur. Des cas de fraude récents montrent que ce genre de générateurs peut être biaisé en simulant le clavier à
l'aide d'un dispositif frauduleux dont le temps écoulé entre les diverses touches est connu de l'attaquant.
La présente invention propose une solution de substitution permettant la mise en oeuvre de systèmes cryptographiques nécessitant le tirage d'un aléa d'une bonne qualité sur des plates-formes logicielles ou matérielles .
1. ne possédant pas de moyen de génération d'aléas, 2. ou générant des aléas de mauvaise qualité,
Une grande limitation des cartes à puce comme support d'implémentation d'algorithmes à clé publique est la nécessité
(fréquemment rencontrée), d'avoir un dispositif générant des nombres aléatoires à bord de la carte. En effet, la mise au point d'un tel dispositif, appelé aussi générateur, s'avère complexe et souvent instable (sensibilité aux phénomènes extérieurs à la carte tels que la température ambiante ou la l0 tension appliquée à la carte). Dans le cas où de tels systèmes cryptographiques sont mis en oeuvre sur un ordinateur, d'autres phénomènes, dus à la nature même des générateurs aléatoires logiciels viennent perturber la qualité des aléas. Typiquement, une méthode de génération d'aléas très populaire consiste à
mesurer le temps écoulé entre deux touches du clavier appuyées par l'utilisateur. Des cas de fraude récents montrent que ce genre de générateurs peut être biaisé en simulant le clavier à
l'aide d'un dispositif frauduleux dont le temps écoulé entre les diverses touches est connu de l'attaquant.
La présente invention propose une solution de substitution permettant la mise en oeuvre de systèmes cryptographiques nécessitant le tirage d'un aléa d'une bonne qualité sur des plates-formes logicielles ou matérielles .
1. ne possédant pas de moyen de génération d'aléas, 2. ou générant des aléas de mauvaise qualité,
3. ou lorsque le concepteur du système suspecte que des éléments extérieurs pourraient compromettre la qualité des alêas par modification des conditions extérieures et intérieures de fonctionnement.
La présente invention s'applique à diverses familles d'algorithmes cryptographiques. Pour une meilleure compréhension- de l'invention et avant de reprendre le contenu des revendications dans la description, il est utile de rappeler les caractéristiques principales desdites familles d'alogorithmes cryptographiques auxquelles s'applique ~5 l'invention, celles-ci étant au nombre de six.
La première famille d'application concerne les schémas de signature de type E1-Gamal.
L'algorithme de signature d'El-Gamal décrit dans l'article intitulé « A public-key crypt;osystem and a signature scheme based on discrete logari.thms » et: publié dans la revue IEEE
Transactions on Information Theory, vol. IT-31, no. 4, 1985, pp. 469-472, a donnê naissance à plusieurs algorithmes de signatûre connus: Schnorr, breveté aux Etats-Unis sous la référence 4.995.082, ou GOST 34-10 - norme fédérale Russe de signature numérique ; DSA-Standart américain de signature numérique.
Une fois illustrée dans le cadre du DSA, l'application de la présente invention à d'autres algorithmes de la même famille pourra aisément être mis en oeuvre par l'homme de l'art.
2o Dans la suite, il est appelé L'algorithme DSA.
Le Standard de Signature Numérique (DSA, brevet américain no. 5.231.668 intitulée "Digital Signature Algorithm") a été
proposé par le US National Institute of Standards and Technology afin de fournir une base appropriée pour des applications requérant une signature numérique au lieu des signatures classiques. Une signature DSA est une paire de grands nombres représentés dans ur~ ordinateur par des chaînes de chiffres binaires. La signature numérique est calculée à
l'aide d'une série de règles de calcul (le DSA) et un ensemble de paramètres d'une façon permettant de certifier à la fois
La présente invention s'applique à diverses familles d'algorithmes cryptographiques. Pour une meilleure compréhension- de l'invention et avant de reprendre le contenu des revendications dans la description, il est utile de rappeler les caractéristiques principales desdites familles d'alogorithmes cryptographiques auxquelles s'applique ~5 l'invention, celles-ci étant au nombre de six.
La première famille d'application concerne les schémas de signature de type E1-Gamal.
L'algorithme de signature d'El-Gamal décrit dans l'article intitulé « A public-key crypt;osystem and a signature scheme based on discrete logari.thms » et: publié dans la revue IEEE
Transactions on Information Theory, vol. IT-31, no. 4, 1985, pp. 469-472, a donnê naissance à plusieurs algorithmes de signatûre connus: Schnorr, breveté aux Etats-Unis sous la référence 4.995.082, ou GOST 34-10 - norme fédérale Russe de signature numérique ; DSA-Standart américain de signature numérique.
Une fois illustrée dans le cadre du DSA, l'application de la présente invention à d'autres algorithmes de la même famille pourra aisément être mis en oeuvre par l'homme de l'art.
2o Dans la suite, il est appelé L'algorithme DSA.
Le Standard de Signature Numérique (DSA, brevet américain no. 5.231.668 intitulée "Digital Signature Algorithm") a été
proposé par le US National Institute of Standards and Technology afin de fournir une base appropriée pour des applications requérant une signature numérique au lieu des signatures classiques. Une signature DSA est une paire de grands nombres représentés dans ur~ ordinateur par des chaînes de chiffres binaires. La signature numérique est calculée à
l'aide d'une série de règles de calcul (le DSA) et un ensemble de paramètres d'une façon permettant de certifier à la fois
4 l'identité du signataire et l'intégrité des données. Le DSA
permèt de générer et vérifier des signatures.
Le procédé de génération de signatures fait usage d'une clé privée (afin de produire une signature numérique). Le procédé de vérification utilise une clé publique qui correspond à la clé secrète sans toutefois lui être identique. Chaque utilisateur possède une paire de clés (publique , secrète). I1 est supposé que les clés publiques sont connues de tous alors que les clés secrètes ne sont jamais dévoilées. Toute personne 1o a la capacité de vérifier la signature d'un utilisateur en utilisant sa clé publique mais des signatures ne peuvent être génêrées autrement qu'en utilisant la clé secrète de l'utilisateur.
Les paramètres du DSA sont .
- O Un module premier p tel que 2L1<p<2L pour 512 <_ L <_ 1024 et L = 64 a pour un a quelconque.
OO Un module premier q tel que 2lss<q<2lso et p-1 est un multiple de q.
OO Un nombre g, d' ordre q modulo p tel que g - hop-1~ /q mod p, où h est un entier quelconque vérifiant 1 < h < p-1.
~ Un nombre x, généré aléatoirement ou pseudo aléatoirement.
D Un nombre y défini par la relation . y = g" mod p.
~ Un nombre k généré aléatoirement ou pseudo aléatoirement tel que 0 < k < q.
Les entiers p, q et g sont des paramêtres du système pouvant être publiés et/ou partagés par un groupe d'utilisateurs. Les clés, secrète et publique, d'un signataire sont respectivement x et y. Les paramëtres x et k sont utilisés pour la génération de la signature et doivent être gardés WO 98lS1038 PCT/FR98/00901 secrets. Le paramètre k doit être régénéré pour chaque signature.
Afin de signer un message m (valeur hachée d'un fichier initial M), le signeur calcule la signature (r, s) par .
k
permèt de générer et vérifier des signatures.
Le procédé de génération de signatures fait usage d'une clé privée (afin de produire une signature numérique). Le procédé de vérification utilise une clé publique qui correspond à la clé secrète sans toutefois lui être identique. Chaque utilisateur possède une paire de clés (publique , secrète). I1 est supposé que les clés publiques sont connues de tous alors que les clés secrètes ne sont jamais dévoilées. Toute personne 1o a la capacité de vérifier la signature d'un utilisateur en utilisant sa clé publique mais des signatures ne peuvent être génêrées autrement qu'en utilisant la clé secrète de l'utilisateur.
Les paramètres du DSA sont .
- O Un module premier p tel que 2L1<p<2L pour 512 <_ L <_ 1024 et L = 64 a pour un a quelconque.
OO Un module premier q tel que 2lss<q<2lso et p-1 est un multiple de q.
OO Un nombre g, d' ordre q modulo p tel que g - hop-1~ /q mod p, où h est un entier quelconque vérifiant 1 < h < p-1.
~ Un nombre x, généré aléatoirement ou pseudo aléatoirement.
D Un nombre y défini par la relation . y = g" mod p.
~ Un nombre k généré aléatoirement ou pseudo aléatoirement tel que 0 < k < q.
Les entiers p, q et g sont des paramêtres du système pouvant être publiés et/ou partagés par un groupe d'utilisateurs. Les clés, secrète et publique, d'un signataire sont respectivement x et y. Les paramëtres x et k sont utilisés pour la génération de la signature et doivent être gardés WO 98lS1038 PCT/FR98/00901 secrets. Le paramètre k doit être régénéré pour chaque signature.
Afin de signer un message m (valeur hachée d'un fichier initial M), le signeur calcule la signature (r, s) par .
k
5 r = g mod p mod q et s = (m + x r) /k mod q, où la division par k s'entend modulo q (i.e. 1/k est le nombre k' tel que k k' - 1 mod q).
Par exemple, si q=5 et k=3 alors 1/k =2 car 3x2 - 6 ---1 mod 5.
lo Après avoir testé que r et s ~ 0, comme expliqué dans la description du DSA, la signature {r, s~ est envoyée au vérifieur qui calcule .
w = 1/s mod q ~ ul = m w mod q OO u2 = r w mod q ~ v = gul yua modp mod q ~ Et compare si v et r sont égaux afin d'accepter ou rejeter la signature.
La deuxième famille concerne également des schémas de signature ; il s'agit de schémas dérivés de protocoles à
divulgation nulle Une seconde famille d'algorithmes de signature à laquelle s'applique l'invention sont ceux dérivés des protocoles à
divulgation nulle (typiquement Fiat-Shamir ou .Guillou-Quisquater brevetës aux Etats-Unis respectivement sous les références 4.748.668 et 5.140.634). Aussi, il sera dêcrit . seulement un de ces protocoles. Une fois appliqué à
l'algorithme de Guillou et Quisquater, l'extension de - l'invention à d'autres algorithmes de cette famille s'avère évidente pour l'homme de l'art.
_ 6 Les paramètres de l'algorithme de _Guillou-Quisquater sont Deux nombres premiers secrets p et q de taille au moins.
égale à 256 bits ; ces nombres premiers sont générés d'une façon particulière dont le détail n'est pas indispensable à la compréhension de la présente invention mais peut être toutefois retrouvé dans l'ouvrage « Cryptographie Appliquée, Algorithmes, Protocoles et Codes Source », par Bruce Schneier (Traduction de Marc Vauclair), Éditions Thomson Publishing ;
i0 20 Un module public n = p q et une chaine ID représentant l'identité du signeur ;
O Un exposant public v et une clé secrète B telle que B"
ID = 1 mod n ; le paramètre B doit rester secret ;
~ Afin de signer le message m, l' expéditeur tire un aléa k, calcule le témoin initial T - k" mod n et génère la signature .
d = h (T, m) et D = k Bh~T'm) mod n ;
OO Le vérifieur s'assure de l'authenticité de la signature en vérifiant que .
d = h ( T' , m) avec T' = D" Idd .
La troisième famille d'application concerne les schémas de chiffrement à clé publique nécessitant un aléa.
Le premier algorithme de chiffrement nécessitant un aléa décrit dans la suite est celui d'El Gamal.
Les paramètres de cet algorithme sont:
O Un module premier p (d'au moins 512 bits) ;
O Un nombre g, d'ordre p-1 modulo p (i. e. tel que, pour tout nombre entier u, 0 < u < p-1, gu ~ 1 mod p ;
OO Un nombre x, 1 <_ x _< p-2, généré aléatoirement ou pseudo aléatoirement ;
Un nombre y défini par la relation . y = g" mod p ;
_ 7 ~ Un nombre k générê aléatoirement ou pseudo aléatoirement tel que 0 < k < q.
Les entiers p et g sont des paramètres système pouvant être publiés, et/ou partagés par un groupe d'utilisateurs. La . 5 clef publique de chiffrement est le nombre y, et la clef secrète de déchiffrement est le nombre x.
Le paramètre k sert à la génêration du cryptogramme, et ne doit pas être divulgué. De plus, il doit être regénéré à chaque chiffrement.
lo Le chiffré d'un message m, 0 <_ m 5 p-1, est la paire d'entiers (r,s), où:
r = gk mod p et s = m yk mod q.
Pour retrouver le message m, le receveur des cryptogrammes (qui possède x), calcule:
15 s/r" mod p, qui est justement m.
Un second algorithme de chiffrement nécessitant la génération d'un aléa est le schéma de McEliece, basé sur un problème de la théorie des codes, plus précisément utilisant 20 une classe de codes particulière connue sous le nom de codes de Coppa. L'idée générale est de déguiser un code de Coppa en code linéaire quelconque ; il existe en effet un algorithme efficace pour décoder un code de Coppa mais en revanche décoder un code linéaire gênéral est un problème difficile. Le récepteur 25 connaissant l'information ayant permis de déguiser le code, pourra donc déchiffrer le message en décodant le code de Coppa obtenu.
Les paramètres de l'algorithme de McEliece (toutes les . formules qui suivent sont entendues dans GF(2)) sont .
_ 8 Des nombres n, k et t, paramètres du système ; dans l'article originel décrivant son schéma de chiffrement, McEliece propose n =1024, t = 50 et k = 524 ;
OO Une clé secrète composée de .
~ Une matrice génératrice G d'un code de Goppa binaire de taille n et de dimension k corrigeant t erreurs et l'algorithme de décodage correspondant ;
Une matrice inversible aléatoire S de dimension k x k ;
~ Une matrice de permutation aléatoire P de taille n ;
OO Une clé publique correspondante composée de .
~ La matrice génératrice T - SGP d'un code équivalent à
G ;
~ Le taux de correction t ;
~ Le chiffrement par l'algorithme de McEliece d'un message m de k bits s'effectue en calculant .
c = mT + e où e est un vecteur d'erreur aléatoirement choisi de poids de Hamming égal â t.
Le déchiffrement de c s'effectue en calculant .
cP 1 - m TP 1 + eP 1 - mSG + eP 1.
Puisque e est de poids t, eP-1 est aussi de poids t. Le vecteur cP 1 est donc corrigible par le code G..Par décodage, le déchiffreur obtient mS, puis m car il connait S et S est inversible.
La quatrième famille concerne les schémas cryptographiques nécessitant un « padding » aléatoire.
I1 n'est pas rare que la donnée à chiffrer doive d'abord être « paddée », c'est-à-dire complétée pour obtenir une donnée d'une taille fixe. L'illustration de cet aspect peut être donné
par l'exemple du chiffrement RSA, publié en 1978 par R. Rivest, A. Shamir et L. Adleman puis breveté sous l'intitulé
Cryptographie Communications System and Method ~ et la référence US 4,405,829.
Un cryptogramme RSA est un grand nombre représenté dans un ordinateur par des chaînes de chiffres binaires ou hexadécimales. Le cryptogramme est calculé à l'aide d'une ressource de calcul logicielle (programme) et/ou matérielle (circuit électronique) mettant en oeuvre une série de règles de calcul (l'algorithme de chiffrement) devant être appliquées Iors du traitement d'un ensemble de paramètres accessible à
1o tous afin de cacher le contenu des données traitées. De façon analogue, le cryptogramme est déchiffré à l'aide d'une ressource de calcul logicielle ou matérielle mettant en oeuvre une série de règles de calcul (l'algorithme de déchiffrement) appliquées (par le récepteur du cryptogramme) sur un ensemble de paramètres secrets et le cryptogramme.
Le procédé de chiffrement fait usage d'une clé publique afin de produire le cryptogramme. Le procëdé de dêchiffrement utilise une clé privée qui correspond à la clé secrète sans toutefois lui être identique. Chaque utilisateur possède une paire de clés (publique, secrète) et l'on suppose que les clés publiques sont connues de tous alors que les clês secrètes ne sont jamais dévoilées. Toute personne a la capacité de chiffrer un message pour un utilisateur en utilisant la clé publique de ce dernier mais des cryptogrammes ne peuvent être déchiffrés autrement qu'en utilisant la clé secrète de l'utilisateur.
Les paramètres de l'algorithme RSA sont .
. ~O Deux nombres premiers secrets p et q de taille au moins égale à 256 bits. Ces nombres premiers sont gënérés d'une façon . particulière dont le détail n'est pas indispensable à la compréhension de la présente invention mais peut être toutefois retrouvé dans l'ouvrage « Cryptographie Appliquée, Algorithmes, Protocoles et Codes Source », par Bruce Schneier (Traduction de Marc Vauclair), Editions Thomson Publishing ;
OO Un module public n = p q ;
O Une paire d'exposants notée (e,d) tels que .
e d = 1 mod {p-1) (q-1).
L'exposant e, appelé « exposant de chiffrement », est accessible à tous alors que « l'exposant de déchiffrement » d doit rester secret.
Afin de chiffrer le message m, l'expéditeur calcule le 10 cryptogramme c - me mod n et le récepteur déchiffre c en calculant m = cd mod n.
La sécurité de l'algorithme, basée sur le problème de la factorisation, permet pour un choix de paramètres effectué dans les règles de l'art d'assurer dans le cas général du chiffrement de messages de la taille du module et ne possédant pas de relations particulières entre eux la confidentialité
entre l'émetteur et le récepteur de l'information chiffrée.
En revanche, de récentes attaques présentées par Coppersmith et al. à Eurocrypt '96 {notamment dans « Low Exponent with Related Message » et ~ Finding a srnall root of a univariate modular equation » publiés dans les actes de la conférence chez Springer-Verlag sous la référence LNCS 1070) montrent que l'existence de relations polynomiales entre des messages chiffrés avec un même exposant de petite taille, ce qui peut tout à fait se produire dans le cadre d'une application oû le dispositif chiffrant utilise en général pour chiffrer un exposant public e=3 pour des raisons de performances, permet des attaques efficaces révélant le texte clair.
Une parade possible est de « padder » le message avec une sêquence aléatoire (mais en prenant certaines précautions) ou de briser toute relation entre les messages, ce qui, suivant les applications, n'est pas toujours possible.
On introduira alors dans l'étape ~ la modification suivante .
Afin de chiffrer le message, l'expéditeur génère une sêquence sr comportant un certain degré d'aléatoirité et calcule le cryptogramme c = (m~sr)~ mod n, le signe ~ indiquant la concaténation; le récepteur déchiffre c en calculant cd mod n et retrouve m en retranchant le ;padding.
l0 Les méthodes exactes de padding des messages peuvent varier suivant les normes, les besoins applicatifs ou le niveau requis en matière de sécurité.
La cinquième famille concerne les facteurs d'aveuglement et signatures en blanc.
Une fonctionnalité de base, appelêe primitive par l'homme de l'art, utilisée dans de nombreux schémas et protocoles cryptographiques est le mécanisme de signature en blanc d'un message donné. Cette fonctionnalité découverte et brevetée par Chaum (brevet US n° 4,759,063 et européen n° 0139313) permet de 2o faire signer un message sans que le signeur puisse prendre connaissance du message. Elle nêcessite la génération d'un facteur d'aveuglement, permettant de dissimuler le message, connu du seul demandeur de la signature. Le mécanisme utilisé
s'applique aussi bien aux schémas de signature de type~El Gamal qu'au RSA.
Une fois illustrée dans le cadre du RSA, l'application de notre invention à d'autres algorithmes de signature s'avère évidente pour l'homme de l'art. I1 sera décrit ici seulement le mécanisme de signature en blanc basé sur le RSA.
_ 12 En reprenant la notation utilisée dans le cadre de la description de la quatrième famille d'application de l'invention, la signature RSA est ainsi définie .
s = md mod n ;
la vérification se faisant naturellement .
se mod n = (md} e mod n = m.
Les étapes de l'obtention d'une signature en blanc par l'expéditeur E d'un message m sont .
E génère un nombre aléatoire k, calcule le facteur d' aveuglement ke mod n et envoie m' = mke mod n au récepteur ou (signeur) ;
OO le récepteur calcule s' - m'd mod n et qui est la signature de m' et envoie s' à E ;
OO E calcule s' /k - (mke) d/k - mdked/k - md mod n, et obtient donc la signature s de m.
Cette technique de multiplication par un facteur d'aveuglement est également reprise dans le cadre du maquillage aléatoire (demande de brevet européen EP 91402958.2).
La méthode du maquillage aléatoire sert par exemple dans le cas où un dispositif A veut sous-traiter des opérations à un dispositif B tout en ne désirant pas lui révéler complètement les opérandes. Prenons par exemple une opération de réduction modulaire: A peut camoufler le nombre à réduire modulo n en le multipliant par un multiple aléatoire du module. Ainsi, si A
désire obtenir c - ab mod n, il peut générer un aléa k, calculer c' - ab + kn {kn masque le produit ab), et envoyer c' au dispositif B pour réduction.
Le dispositif B calcule c' mod n = ab + kn mod n = c.
Cette technique permet enfin de proposer une parade aux attaques de Kocher décrites à Crypto '96 (« Timing attacks on Implementation of Diffie-Hellman, RSA, DSS and Other Systems », actes de la confërence publiës chez Springer-Verlag sous la référence LNCS 1109) qui se basent sur la mesure du temps requis par des opêrations manipulant des grandeurs secrètes pour en deviner les valeurs.
En effet, une parade efficace est la multiplication, par un facteur d'aveuglement, des grandeurs secrètes manipulées afin de décorréler le temps de calcul et la grandeur. Dans le cas de la signature RSA par exemple (l'homme de l'art saura étendre ce résultat à l'ensemble des algorithmes concernés par l'attaque, notamment tous ceux entraînant le calcul d'une exponentielle modulaire avec un exposant secret), en reprenant la notation utilisée dans le cadre de la description de la quatrième famille d'application de l'invention, il suffit que .
le signeur génère un nombre aléatoire k et calcule .
d' - d + k (p-1) (q-1) , D il génère ensuite la signature de m en calculant ma- - ma+xcP-l ~e-1> - ma (mcP-n tq-1> ) x _ ma mod n.
La sixième famille concerne les schémas d'échange de clés basés sur la méthode de Diffie-Hel:lman.
L'algorithme d'échange de clefs de Diffie-Hellman est le premier algorithme â clef publique décrit dans ~ New Directions in Cryptography » paru dans IEEE Transactions on Information Theory, vol. IT-22, n°6 et breveté aux Etats-Unis sous la référence 4.200.770. La méthode met en oeuvre deux participants (ou appareils) désirant convenir d'une information secrète à
travers un canal non sûr.
Les paramètres du protocole Diffie-Hellman sont les suivants .
O Deux paramètres publics sur lesquels l'appareil expéditeur (A) et l'appareil (B) s'entendent . un nombre premier p d'au moins 512 bits et un entier g, racine primitive WO 98/51038 PCTlFR98/00901 modulo p. Ces deux paramètres peuvent être éventuellement communs à un groupe d'utilisateurs ;
le protocole se déroule comme suit .
Afin de partager une information secrète, les deux appareils rêalisent les opérations suivantes .
~ l'appareil A génère un nombre aléatoire x et calcule la grandeur X = g" mod p ;
~ l'appareil B génëre un nombre aléatoire y et calcule la grandeur Y = gy mod p ;
~ les deux appareils s'échangent les quantités X et Y
~ l'appareil A calcule clé = Y" mod p ;
~ l'appareil B calcule clé' - XY mod p.
Les deux appareils partagent ainsi à la fin du protocole lâ connaissance de la quantité clé' - clé = g"Y mod p.
Les deux appareils peuvent par la suite utiliser la quantité secrète « clé » pour s'échanger des messages par un canal sûr à l'aide d'un algorithme de chiffrement symétrique prenant pour paramètres la quantité « clé » et le message à
chiffrer.
Suite à la description des différentes familles d'application de l'invention, il est souhaitable de préciser les principaux avantages de l'invention.
Les contraintes économiques liées au marché de la carte à
puce, entraînent une recherche constante en vue d'améliorer les coûts de revient. Cet effort passe souvent par l'utilisation de produits les plus simples possible. Cet état de fait induit un intérêt sans cesse grandissant pour des solutions permettant d'implémenter des algorithmes à clef publique sur des micro contrôleurs peu chers de type 8 bits, à coeur de 80C51 ou 68HC05 par exemple.
WO 98/51038 pCT/FR9g~0pg01 Le principal avantage du procédé inventif en regard des propositions précédentes en matière de signatures numériques ou de chiffrement réside dans la capacité de calculer des signatures ou d'effectuer des opérations de chiffrement sans pour autant nécessiter un gênérateur d'aléas à bord du circuit signant ou chiffrant.
Pour la clarté de la description, il est nêcessaire de préciser que la génération des clefs et paramètres des divers systèmes présentés reste identique. On se référera donc aux brevets et ouvrages habituels afin de générer, dans les règles de l'art, les divers éléments nécessaires aux algorithmes de signature, authentification et chiffrement présentés dans l'invention. Un ouvrage de référence pratique pourra être « Cryptographie Appliquée, Algorithmes, Protocoles et Codes Source », par Bruce Schneier (Traduction de Marc Vauclair), Editions Thomson Publishing.
La. présente invention concerne un système cryptographique, nécessitant normalement le tirage d'un aléa k, l'aléa étant un entier; le système est caractérisé en ce qu'il est mis en oeuvre en remplaçant ledit alêa k par la quantitê h(m~secret) où h est une fonction de hachage, m est le message intervenant dans ledit systëme et « secret » est un secret inconnu du monde extérieur au système cryptographique.
De manière plus précise, le systême cryptographique de l'invention comprend au moins .
- un système de signature à clé publique ;
- un système de chiffrement à clê publique ;
- un systême de « padding » alêatoire ;
- un système de gênêration de facteurs d'aveuglement ;
- un protocole d'échange de clês.
_ 16 Dans le cas d'un système cryptographique qui comprend un système de signature à clé publique de type DSA, Schnorr, E1-Gamal, GOST 34.10 ou la norme IEEE de courbes elliptiques ECDSA, l'aléa (k) renouvelé par le signeur lors de chaque signature est remplacé par la quantité h(m~x), où x est la clef secrète du signeur.
Dans le cas d'un système cryptographique comprenant un système de signature à clé publique de type Fiat-Shamir ou Guillou-Quisquater, l'aléa renouvelé par le signeur lors de l0 chaque signature est remplaçé par la quantité h(m~B), B étant la clef secrète du signeur et m le message à signer.
Dans le cas d'un système cryptographique comprenant un système de chiffrement à clé publique de type El Gamal, l' aléa (k) renouvelé par le chiffreur lors de chaque envoi de message chiffré est remplacé par la quantité h(m).
Dans le cas d'un système cryptographique comprenant un système de chiffrement à clé publique dé type McEliece le vecteur d'erreur aléatoire e, renouvelé par le chiffreur à
chaque chiffrement est dérivé à partir de la quantité h(m), où
m est le message à chiffrer.
Dans le cas d'un système cryptographique comprenant un système de ~c padding » aléatoire intervenant dans un système de chiffrement à clé publique, le chifreur possède une clé a inconnue du déchiffreur et où le ~ padding »des messages est réalisé selon les étapes suivantes .
a. Générer autant de ki=h(m~a~i) que nécessaire pour que la longueur des ki concaténés soit au moins égale à 1/6 de la taille du module n (dans le cas du chiffrement RSA par exemple) ou bien générer k=h(m~a) et l'expanser ;
b. Composer mr tel que m= = taille (m) ~m~ {ki~ ;
c. Chiffrer mr à la place de m.
Dans le cas d'un système cryptographique comprenant un système de génération d'un facteur d'aveuglement dans le cadre d'une génération signature en blanc ou d'une opération de.
maquillage aléatoire l'aléa (k) renouvelé par l'expéditeur lors de chaque opération d'aveuglement ou de maquillage est remplacé
par la quantité h(m~a) Dans le cas d'un système cryptographique comprenant un protocole d'échange de clés de type Diffie-Hellman selon un appareil souhaitant envoyer un message m utilise, à la place lo d' un secret aléatoire, la quantité h (m ~ a) où a est une donnée secrète.
Dans ce même cas de ce système cryptographique ledit protocole comporte au moins les êtapes suivantes .
a. Un premier appareil, souhaitant envoyer le message m, calcule bl = ghcm'a) mod p ;
b. Un second appareil, récepteur, génère un alêa a et calcule bz = ga mod p ;
c. Les deux appareils êchangent bl et b2, et calculent clé
- ga h (m I a) mOd p i 2o d. Le premier appareil chiffre c - f (m, clé) où f est un mécanisme de chiffrement symétrique ;
le premier appareil envoie c au second appareil qui le dëchiffre et retrouve m.
D'une manière préférentielle, les appareils communiquants sont des cartes à puce, des cartes PCMCIA, des badges, des cartes sans contact ou tout autre appareil portable.
Préférentiellement, la communication entre lesdits appareils mettant en oeuvre l'invention est réalisée par le biais d'echanges de signaux électroniques, d~ondes radio ou de signaux infrarouges.
WO 98!51038 PCT/FR98/00901 Dans la suite, l'invention est présentée d'une façon plus détaillée en reprenant les notations utilisées dans la description des familles d'applications.
Comme dit précédemment, l'idée de générer un aléa par une opération de hachage h. Pour les deux premières familles d'application de l'invention, h prendra pour paramètre une donnée secrète, à savoir la clef secrète du signeur, et une donnée publique, le message à signer.
Pour la troisième famille, h prendra en paramètre l0 seulement le message à signer.
Enfin,~pour les autres familles, h prendra en paramètre une donnée publique et une donnée secrète (notée a dans la suite ) .
Plus précisément .
- pour la première famille concernant lesdits schémas de signature de type E1-Gamal, l'aléa k est généré de la façon suivante . k - h(m'x) où m est le haché du message M devant être signé et x, la clef secrète du signataire. Le reste de la génération de la signature (r, s) s'effectue de façon identique au procédé original. De même la vérification de la signature générée reste inchangée.
- pour la deuxième famille concernant lesdits schémas de signature dérivés des protocoles à divulgation nulle, k est généré de la façon suivante . k - h(m~B) avec m le haché du message M devant être signé et B, la clef secrète du signeur.
Le reste de la génération de la signature (d,D) s'effectue de façon identique au procédé original. De même la vérification de la signature générée reste inchangée.
- pour la troisième famille concernant lesdits schémas de chiffrement nécessitant un aléa, deux cas sont à considérer:
O Cas du chiffrement d'El Gamal .
_ 19 - l'aléa k est généré de la façon suivante . k = h(m) avec m le message devant être chiffré. On effectue ensuite l'algorithme d'El Gamal de la façon décrite précédemment. Le déchiffrement reste également inchangé.
O Cas du chiffrement de Mc Eliece .
- au lieu de dériver le vecteur d' erreur e â partir d' un aléa, il est génêré à partir de h(m), où m est le message à
chiffrer. Il est rappelé que e doit être de poids de Hamming exactement t. Une façon de dériver un vecteur de taille n (taille du code considéré) et de poids t à partir de h (m) est la suivante .
- supposons que l'on ait ordonné les vecteurs de taille n et de poids t. On peut alors choisir le vecteur de cette liste qui est en position h (m) (ou une position dérivée de h (m) , car IS ce nombre peut dépasser binomial.(t,n), suivant t,n, et la fonction de hachage utilisée) comme vecteur e.
On effectue ensuite l'algorit;hme de McEliece de la façon décrite prêcédemment. Le déchiffrement reste également inchangê.
En outre, ce procédé de génération de e permet de résoudre le problème du chiffrement d'un 'même message deux fois. En effet, dans le cas du McEliece générique, il est imprudent de chiffrer un même message deux fois (donc avec deux vecteurs d'erreur différents), car l'on peut deviner une partie du support des vecteurs d'erreurs, et par suite retrouver plus facilement le message clair.
Avec notre génération de e, un même message aura toujours le même chiffré.
L'invention s'applique de la manière suivante à la quatrième famille, qui concerne les schémas cryptographiques nécessitant un « padding » alêatoire .
- comme précisé, une mesure de sécurité recommandable est de ~ padder » les messages avec une séquence aléatoire. Mais là
encore, si la séquence varie pour plusieurs chiffrements d'un même message, une attaque est encore possible révélant le message clair.
L'utilisation de la méthode déterministe de génêration d'un aléa permet d'enrayer efficacement ce type de phénomëne.
En effet, en ajoutant au message m autant de fois que nécessaire (le padding doit être au moins long de 1/6 de la l0 taille de n, soit entre 86 et 171 bits pour des tailles de module classiques allant de 512 à 1024 bits) les valeurs ki =
h(m,a,i), a étant un secret d'au moins 128 bits, l'ensemble des attaques devient impossible car plus aucune relation n'existe entre les messages et de plus, un même message chiffré
plusieurs fois le sera toujours avec le même padding. Le chiffrement d'un message m s'effectue alors de la manière suivante par l'expéditeur .
O Générer autant de ki = h(m~a~i) que nécessaire pour que la longueur des ki concaténés soit au moins égale à 1/6 de la taille de n ; on pourra également préférer utiliser un seul k =
h(m~a) puis expanser k avant de le concaténer au message ;
O Composer mr tel que mr = taille (m) ~m~ tki~ ;
Calculer le cryptogramme c - mre mod n afin que le récepteur déchiffre c en calculant mr = cd mod n. Le récepteur extrait ensuite m simplement, connaissant sa taille et donc les bits significatifs de mr.
Pour la cinquième famille concernant les facteurs d'aveuglement et signatures en blanc, trois cas sont â
considérer .
0 Cas de la Signature en Blanc .
- k est généré de la façon suivante . k.= h(m~a) avec m le messâge devant être signé et a une: donnée secrète. Le reste de la génération de la signature en blanc s'effectue de façon identique au procédê original. De même l'extraction de la signature de m reste inchangée ;
D Cas du maquillage aléatoire .
- on génère k de la façon suivante . k - h ( a t b ~ a) avec a et b les opérandes à multiplier et a une donnée secrète. Le reste de l'opêration de maquillage aléatoire s'effectue de façon identique au procédé original. De même la réduction . modulaire de c' par le receveur reste inchangée ;
~ Cas des mécanismes de protection contre les attaques basées sur la mesure du temps d'un processus .
- dans le cas de la signature RSA par exemple, on génère le multiple aléatoire k de (p-1) (q-1) de la façon suivante . k - h (m ~ a) avec m le message à signer, et a une donnée secrète .
Le reste de l'opération de maquillage de l'exposant (d'=d+k(p 1)(q-1)) s'effectue de façon identique au procêdê original.
L'invention s'applique de la rnanière suivante à la sixième famille, qui concerne lesdits schÉ~mas d'échange de clés basés sur la methode de Diffie-Hellman.
Dans le système d'échange de clés de type Diffie-Hellman l'appareil, appelé aussi dispositif, qui souhaite envoyer un message m, utilise, à la place d'un aléa la quantitê h(m~a) où
a est une donnée secrète fixe. Un peut évidemment de façon naturelle étendre cette méthode à l'ensemble des participants au protocole. Ce dernier comporte, au moins, les étapes suivantes .
un premier dispositif, souhaitant envoyer le message m, cal cule X = gh ~'°' a~ mod p ;
~ un second dispositif, rêcepteur, génère un aléa y et calcule Y = gY mod p ;
~ les deux dispositifs échangent X et Y, et calculent clé
- gY.nc~ I 6> mod p ;
~ le premier dispositif chiffre c - f(m,clé) où f est un mécanisme de chiffrement symétrique ;
~ le premier dispositif envoie c au second dispositif qui le déchiffre et retrouve m.
L'invention sera plus facile à comprendre à l'aide des figures 1 à 4.
La figure 1 décrit l'organigramme d'un appareil de signature ou de déchiffrement mettant en oeuvre le système proposé par la présente invention.
La figure 2 décrit l'organigramme d'un appareil de vérification ou chiffrement mettant en oeuvre le système proposé par la présente invention.
La figure 3 représente les données échangées par le dispositif de signature et le dispositif de vérification.
La figure 4 représente les données échangées par le dispositif de chiffrement et le dispositif de déchiffrement.
Selon l'invention proposée, chaque appareil de signature/déchiffrement (typiquement une carte à puce) se compose d'une unité de traitement (CPU), d'une interface de communication, une mémoire vive (RAM) et/ou une mémoire non inscriptible (ROM) et/ou une mémoire inscriptible (généralement ré inscriptible) (EPROM ou EEPROM).
Le CPU et/ou la ROM de l'appareil de signature/déchiffrement contiennent des programmes ou des ressources de calcul correspondant aux êtapes de l'algorithme 3o de signature/déchiffrement (règles de calcul et d'utilisation de la fonction de hachage, multiplication, mise au carré, z3 addition, inverse modulaire et réduction modulaire). Certaines de ces opérations peuvent être regroupées . par exemple, la réduction modulaire peut-être directement intégrée dans la multiplication.
La RAM contient le message M sur lequel s'applique la fonction de hachage ou les règles de calcul pour la génération de signatures ou les règles de calcul pour la génëration de cryptogrammes. L'E(E)PROM contient au moins les paramètres m ,x et k gënérés et utilisés comme précisé dans la description qui lo suit .
Le CPU commande, via les bus d'adresses et de données, l'interface de communication, les opérations de lecture et d'écriture mémoire.
Chaque appareil de signature est protégé du monde extérieur par des protections physiques. Ces protections devraient être suffisantes pour empêcher toute entité non autorisée d'obtenir la clef secrète. Les techniques les plus utilisées de nos. jours en la matière sont l' intêgration de la puce dans un module de sécurité et l'équipement des puces de dispositifs capables de détecter des variations de température, de lumière ainsi que des tensions et des fréquences d'horloge anormales. Des techniques de conception particulières, telles que l'embrouillage de l'accès mémoire, sont également utilisées.
Selon l'invention proposée, l'appareil de vérification se compose au minimum d'une unité de traitement (CPU) et de ressources mémoires.
Le CPU commande, via les bus d'adresse et de donnêes, l'interface de communication, les opération de lecture et d'écriture mémoire.
Le CPU et/ou la ROM de l'autorité contiennent des programmes ou des ressources de calcul permettant d'implémenter le protocole de signature ou de chiffrement (règles de calcul.
et fonction de hachage, multiplication, exponentiation et réduction modulaire). Certaines de ces opérations peuvent être regroupées (par exemple, la réduction modulaire peut-être directement intégrée dans la multiplication).
Par exemple, si q=5 et k=3 alors 1/k =2 car 3x2 - 6 ---1 mod 5.
lo Après avoir testé que r et s ~ 0, comme expliqué dans la description du DSA, la signature {r, s~ est envoyée au vérifieur qui calcule .
w = 1/s mod q ~ ul = m w mod q OO u2 = r w mod q ~ v = gul yua modp mod q ~ Et compare si v et r sont égaux afin d'accepter ou rejeter la signature.
La deuxième famille concerne également des schémas de signature ; il s'agit de schémas dérivés de protocoles à
divulgation nulle Une seconde famille d'algorithmes de signature à laquelle s'applique l'invention sont ceux dérivés des protocoles à
divulgation nulle (typiquement Fiat-Shamir ou .Guillou-Quisquater brevetës aux Etats-Unis respectivement sous les références 4.748.668 et 5.140.634). Aussi, il sera dêcrit . seulement un de ces protocoles. Une fois appliqué à
l'algorithme de Guillou et Quisquater, l'extension de - l'invention à d'autres algorithmes de cette famille s'avère évidente pour l'homme de l'art.
_ 6 Les paramètres de l'algorithme de _Guillou-Quisquater sont Deux nombres premiers secrets p et q de taille au moins.
égale à 256 bits ; ces nombres premiers sont générés d'une façon particulière dont le détail n'est pas indispensable à la compréhension de la présente invention mais peut être toutefois retrouvé dans l'ouvrage « Cryptographie Appliquée, Algorithmes, Protocoles et Codes Source », par Bruce Schneier (Traduction de Marc Vauclair), Éditions Thomson Publishing ;
i0 20 Un module public n = p q et une chaine ID représentant l'identité du signeur ;
O Un exposant public v et une clé secrète B telle que B"
ID = 1 mod n ; le paramètre B doit rester secret ;
~ Afin de signer le message m, l' expéditeur tire un aléa k, calcule le témoin initial T - k" mod n et génère la signature .
d = h (T, m) et D = k Bh~T'm) mod n ;
OO Le vérifieur s'assure de l'authenticité de la signature en vérifiant que .
d = h ( T' , m) avec T' = D" Idd .
La troisième famille d'application concerne les schémas de chiffrement à clé publique nécessitant un aléa.
Le premier algorithme de chiffrement nécessitant un aléa décrit dans la suite est celui d'El Gamal.
Les paramètres de cet algorithme sont:
O Un module premier p (d'au moins 512 bits) ;
O Un nombre g, d'ordre p-1 modulo p (i. e. tel que, pour tout nombre entier u, 0 < u < p-1, gu ~ 1 mod p ;
OO Un nombre x, 1 <_ x _< p-2, généré aléatoirement ou pseudo aléatoirement ;
Un nombre y défini par la relation . y = g" mod p ;
_ 7 ~ Un nombre k générê aléatoirement ou pseudo aléatoirement tel que 0 < k < q.
Les entiers p et g sont des paramètres système pouvant être publiés, et/ou partagés par un groupe d'utilisateurs. La . 5 clef publique de chiffrement est le nombre y, et la clef secrète de déchiffrement est le nombre x.
Le paramètre k sert à la génêration du cryptogramme, et ne doit pas être divulgué. De plus, il doit être regénéré à chaque chiffrement.
lo Le chiffré d'un message m, 0 <_ m 5 p-1, est la paire d'entiers (r,s), où:
r = gk mod p et s = m yk mod q.
Pour retrouver le message m, le receveur des cryptogrammes (qui possède x), calcule:
15 s/r" mod p, qui est justement m.
Un second algorithme de chiffrement nécessitant la génération d'un aléa est le schéma de McEliece, basé sur un problème de la théorie des codes, plus précisément utilisant 20 une classe de codes particulière connue sous le nom de codes de Coppa. L'idée générale est de déguiser un code de Coppa en code linéaire quelconque ; il existe en effet un algorithme efficace pour décoder un code de Coppa mais en revanche décoder un code linéaire gênéral est un problème difficile. Le récepteur 25 connaissant l'information ayant permis de déguiser le code, pourra donc déchiffrer le message en décodant le code de Coppa obtenu.
Les paramètres de l'algorithme de McEliece (toutes les . formules qui suivent sont entendues dans GF(2)) sont .
_ 8 Des nombres n, k et t, paramètres du système ; dans l'article originel décrivant son schéma de chiffrement, McEliece propose n =1024, t = 50 et k = 524 ;
OO Une clé secrète composée de .
~ Une matrice génératrice G d'un code de Goppa binaire de taille n et de dimension k corrigeant t erreurs et l'algorithme de décodage correspondant ;
Une matrice inversible aléatoire S de dimension k x k ;
~ Une matrice de permutation aléatoire P de taille n ;
OO Une clé publique correspondante composée de .
~ La matrice génératrice T - SGP d'un code équivalent à
G ;
~ Le taux de correction t ;
~ Le chiffrement par l'algorithme de McEliece d'un message m de k bits s'effectue en calculant .
c = mT + e où e est un vecteur d'erreur aléatoirement choisi de poids de Hamming égal â t.
Le déchiffrement de c s'effectue en calculant .
cP 1 - m TP 1 + eP 1 - mSG + eP 1.
Puisque e est de poids t, eP-1 est aussi de poids t. Le vecteur cP 1 est donc corrigible par le code G..Par décodage, le déchiffreur obtient mS, puis m car il connait S et S est inversible.
La quatrième famille concerne les schémas cryptographiques nécessitant un « padding » aléatoire.
I1 n'est pas rare que la donnée à chiffrer doive d'abord être « paddée », c'est-à-dire complétée pour obtenir une donnée d'une taille fixe. L'illustration de cet aspect peut être donné
par l'exemple du chiffrement RSA, publié en 1978 par R. Rivest, A. Shamir et L. Adleman puis breveté sous l'intitulé
Cryptographie Communications System and Method ~ et la référence US 4,405,829.
Un cryptogramme RSA est un grand nombre représenté dans un ordinateur par des chaînes de chiffres binaires ou hexadécimales. Le cryptogramme est calculé à l'aide d'une ressource de calcul logicielle (programme) et/ou matérielle (circuit électronique) mettant en oeuvre une série de règles de calcul (l'algorithme de chiffrement) devant être appliquées Iors du traitement d'un ensemble de paramètres accessible à
1o tous afin de cacher le contenu des données traitées. De façon analogue, le cryptogramme est déchiffré à l'aide d'une ressource de calcul logicielle ou matérielle mettant en oeuvre une série de règles de calcul (l'algorithme de déchiffrement) appliquées (par le récepteur du cryptogramme) sur un ensemble de paramètres secrets et le cryptogramme.
Le procédé de chiffrement fait usage d'une clé publique afin de produire le cryptogramme. Le procëdé de dêchiffrement utilise une clé privée qui correspond à la clé secrète sans toutefois lui être identique. Chaque utilisateur possède une paire de clés (publique, secrète) et l'on suppose que les clés publiques sont connues de tous alors que les clês secrètes ne sont jamais dévoilées. Toute personne a la capacité de chiffrer un message pour un utilisateur en utilisant la clé publique de ce dernier mais des cryptogrammes ne peuvent être déchiffrés autrement qu'en utilisant la clé secrète de l'utilisateur.
Les paramètres de l'algorithme RSA sont .
. ~O Deux nombres premiers secrets p et q de taille au moins égale à 256 bits. Ces nombres premiers sont gënérés d'une façon . particulière dont le détail n'est pas indispensable à la compréhension de la présente invention mais peut être toutefois retrouvé dans l'ouvrage « Cryptographie Appliquée, Algorithmes, Protocoles et Codes Source », par Bruce Schneier (Traduction de Marc Vauclair), Editions Thomson Publishing ;
OO Un module public n = p q ;
O Une paire d'exposants notée (e,d) tels que .
e d = 1 mod {p-1) (q-1).
L'exposant e, appelé « exposant de chiffrement », est accessible à tous alors que « l'exposant de déchiffrement » d doit rester secret.
Afin de chiffrer le message m, l'expéditeur calcule le 10 cryptogramme c - me mod n et le récepteur déchiffre c en calculant m = cd mod n.
La sécurité de l'algorithme, basée sur le problème de la factorisation, permet pour un choix de paramètres effectué dans les règles de l'art d'assurer dans le cas général du chiffrement de messages de la taille du module et ne possédant pas de relations particulières entre eux la confidentialité
entre l'émetteur et le récepteur de l'information chiffrée.
En revanche, de récentes attaques présentées par Coppersmith et al. à Eurocrypt '96 {notamment dans « Low Exponent with Related Message » et ~ Finding a srnall root of a univariate modular equation » publiés dans les actes de la conférence chez Springer-Verlag sous la référence LNCS 1070) montrent que l'existence de relations polynomiales entre des messages chiffrés avec un même exposant de petite taille, ce qui peut tout à fait se produire dans le cadre d'une application oû le dispositif chiffrant utilise en général pour chiffrer un exposant public e=3 pour des raisons de performances, permet des attaques efficaces révélant le texte clair.
Une parade possible est de « padder » le message avec une sêquence aléatoire (mais en prenant certaines précautions) ou de briser toute relation entre les messages, ce qui, suivant les applications, n'est pas toujours possible.
On introduira alors dans l'étape ~ la modification suivante .
Afin de chiffrer le message, l'expéditeur génère une sêquence sr comportant un certain degré d'aléatoirité et calcule le cryptogramme c = (m~sr)~ mod n, le signe ~ indiquant la concaténation; le récepteur déchiffre c en calculant cd mod n et retrouve m en retranchant le ;padding.
l0 Les méthodes exactes de padding des messages peuvent varier suivant les normes, les besoins applicatifs ou le niveau requis en matière de sécurité.
La cinquième famille concerne les facteurs d'aveuglement et signatures en blanc.
Une fonctionnalité de base, appelêe primitive par l'homme de l'art, utilisée dans de nombreux schémas et protocoles cryptographiques est le mécanisme de signature en blanc d'un message donné. Cette fonctionnalité découverte et brevetée par Chaum (brevet US n° 4,759,063 et européen n° 0139313) permet de 2o faire signer un message sans que le signeur puisse prendre connaissance du message. Elle nêcessite la génération d'un facteur d'aveuglement, permettant de dissimuler le message, connu du seul demandeur de la signature. Le mécanisme utilisé
s'applique aussi bien aux schémas de signature de type~El Gamal qu'au RSA.
Une fois illustrée dans le cadre du RSA, l'application de notre invention à d'autres algorithmes de signature s'avère évidente pour l'homme de l'art. I1 sera décrit ici seulement le mécanisme de signature en blanc basé sur le RSA.
_ 12 En reprenant la notation utilisée dans le cadre de la description de la quatrième famille d'application de l'invention, la signature RSA est ainsi définie .
s = md mod n ;
la vérification se faisant naturellement .
se mod n = (md} e mod n = m.
Les étapes de l'obtention d'une signature en blanc par l'expéditeur E d'un message m sont .
E génère un nombre aléatoire k, calcule le facteur d' aveuglement ke mod n et envoie m' = mke mod n au récepteur ou (signeur) ;
OO le récepteur calcule s' - m'd mod n et qui est la signature de m' et envoie s' à E ;
OO E calcule s' /k - (mke) d/k - mdked/k - md mod n, et obtient donc la signature s de m.
Cette technique de multiplication par un facteur d'aveuglement est également reprise dans le cadre du maquillage aléatoire (demande de brevet européen EP 91402958.2).
La méthode du maquillage aléatoire sert par exemple dans le cas où un dispositif A veut sous-traiter des opérations à un dispositif B tout en ne désirant pas lui révéler complètement les opérandes. Prenons par exemple une opération de réduction modulaire: A peut camoufler le nombre à réduire modulo n en le multipliant par un multiple aléatoire du module. Ainsi, si A
désire obtenir c - ab mod n, il peut générer un aléa k, calculer c' - ab + kn {kn masque le produit ab), et envoyer c' au dispositif B pour réduction.
Le dispositif B calcule c' mod n = ab + kn mod n = c.
Cette technique permet enfin de proposer une parade aux attaques de Kocher décrites à Crypto '96 (« Timing attacks on Implementation of Diffie-Hellman, RSA, DSS and Other Systems », actes de la confërence publiës chez Springer-Verlag sous la référence LNCS 1109) qui se basent sur la mesure du temps requis par des opêrations manipulant des grandeurs secrètes pour en deviner les valeurs.
En effet, une parade efficace est la multiplication, par un facteur d'aveuglement, des grandeurs secrètes manipulées afin de décorréler le temps de calcul et la grandeur. Dans le cas de la signature RSA par exemple (l'homme de l'art saura étendre ce résultat à l'ensemble des algorithmes concernés par l'attaque, notamment tous ceux entraînant le calcul d'une exponentielle modulaire avec un exposant secret), en reprenant la notation utilisée dans le cadre de la description de la quatrième famille d'application de l'invention, il suffit que .
le signeur génère un nombre aléatoire k et calcule .
d' - d + k (p-1) (q-1) , D il génère ensuite la signature de m en calculant ma- - ma+xcP-l ~e-1> - ma (mcP-n tq-1> ) x _ ma mod n.
La sixième famille concerne les schémas d'échange de clés basés sur la méthode de Diffie-Hel:lman.
L'algorithme d'échange de clefs de Diffie-Hellman est le premier algorithme â clef publique décrit dans ~ New Directions in Cryptography » paru dans IEEE Transactions on Information Theory, vol. IT-22, n°6 et breveté aux Etats-Unis sous la référence 4.200.770. La méthode met en oeuvre deux participants (ou appareils) désirant convenir d'une information secrète à
travers un canal non sûr.
Les paramètres du protocole Diffie-Hellman sont les suivants .
O Deux paramètres publics sur lesquels l'appareil expéditeur (A) et l'appareil (B) s'entendent . un nombre premier p d'au moins 512 bits et un entier g, racine primitive WO 98/51038 PCTlFR98/00901 modulo p. Ces deux paramètres peuvent être éventuellement communs à un groupe d'utilisateurs ;
le protocole se déroule comme suit .
Afin de partager une information secrète, les deux appareils rêalisent les opérations suivantes .
~ l'appareil A génère un nombre aléatoire x et calcule la grandeur X = g" mod p ;
~ l'appareil B génëre un nombre aléatoire y et calcule la grandeur Y = gy mod p ;
~ les deux appareils s'échangent les quantités X et Y
~ l'appareil A calcule clé = Y" mod p ;
~ l'appareil B calcule clé' - XY mod p.
Les deux appareils partagent ainsi à la fin du protocole lâ connaissance de la quantité clé' - clé = g"Y mod p.
Les deux appareils peuvent par la suite utiliser la quantité secrète « clé » pour s'échanger des messages par un canal sûr à l'aide d'un algorithme de chiffrement symétrique prenant pour paramètres la quantité « clé » et le message à
chiffrer.
Suite à la description des différentes familles d'application de l'invention, il est souhaitable de préciser les principaux avantages de l'invention.
Les contraintes économiques liées au marché de la carte à
puce, entraînent une recherche constante en vue d'améliorer les coûts de revient. Cet effort passe souvent par l'utilisation de produits les plus simples possible. Cet état de fait induit un intérêt sans cesse grandissant pour des solutions permettant d'implémenter des algorithmes à clef publique sur des micro contrôleurs peu chers de type 8 bits, à coeur de 80C51 ou 68HC05 par exemple.
WO 98/51038 pCT/FR9g~0pg01 Le principal avantage du procédé inventif en regard des propositions précédentes en matière de signatures numériques ou de chiffrement réside dans la capacité de calculer des signatures ou d'effectuer des opérations de chiffrement sans pour autant nécessiter un gênérateur d'aléas à bord du circuit signant ou chiffrant.
Pour la clarté de la description, il est nêcessaire de préciser que la génération des clefs et paramètres des divers systèmes présentés reste identique. On se référera donc aux brevets et ouvrages habituels afin de générer, dans les règles de l'art, les divers éléments nécessaires aux algorithmes de signature, authentification et chiffrement présentés dans l'invention. Un ouvrage de référence pratique pourra être « Cryptographie Appliquée, Algorithmes, Protocoles et Codes Source », par Bruce Schneier (Traduction de Marc Vauclair), Editions Thomson Publishing.
La. présente invention concerne un système cryptographique, nécessitant normalement le tirage d'un aléa k, l'aléa étant un entier; le système est caractérisé en ce qu'il est mis en oeuvre en remplaçant ledit alêa k par la quantitê h(m~secret) où h est une fonction de hachage, m est le message intervenant dans ledit systëme et « secret » est un secret inconnu du monde extérieur au système cryptographique.
De manière plus précise, le systême cryptographique de l'invention comprend au moins .
- un système de signature à clé publique ;
- un système de chiffrement à clê publique ;
- un systême de « padding » alêatoire ;
- un système de gênêration de facteurs d'aveuglement ;
- un protocole d'échange de clês.
_ 16 Dans le cas d'un système cryptographique qui comprend un système de signature à clé publique de type DSA, Schnorr, E1-Gamal, GOST 34.10 ou la norme IEEE de courbes elliptiques ECDSA, l'aléa (k) renouvelé par le signeur lors de chaque signature est remplacé par la quantité h(m~x), où x est la clef secrète du signeur.
Dans le cas d'un système cryptographique comprenant un système de signature à clé publique de type Fiat-Shamir ou Guillou-Quisquater, l'aléa renouvelé par le signeur lors de l0 chaque signature est remplaçé par la quantité h(m~B), B étant la clef secrète du signeur et m le message à signer.
Dans le cas d'un système cryptographique comprenant un système de chiffrement à clé publique de type El Gamal, l' aléa (k) renouvelé par le chiffreur lors de chaque envoi de message chiffré est remplacé par la quantité h(m).
Dans le cas d'un système cryptographique comprenant un système de chiffrement à clé publique dé type McEliece le vecteur d'erreur aléatoire e, renouvelé par le chiffreur à
chaque chiffrement est dérivé à partir de la quantité h(m), où
m est le message à chiffrer.
Dans le cas d'un système cryptographique comprenant un système de ~c padding » aléatoire intervenant dans un système de chiffrement à clé publique, le chifreur possède une clé a inconnue du déchiffreur et où le ~ padding »des messages est réalisé selon les étapes suivantes .
a. Générer autant de ki=h(m~a~i) que nécessaire pour que la longueur des ki concaténés soit au moins égale à 1/6 de la taille du module n (dans le cas du chiffrement RSA par exemple) ou bien générer k=h(m~a) et l'expanser ;
b. Composer mr tel que m= = taille (m) ~m~ {ki~ ;
c. Chiffrer mr à la place de m.
Dans le cas d'un système cryptographique comprenant un système de génération d'un facteur d'aveuglement dans le cadre d'une génération signature en blanc ou d'une opération de.
maquillage aléatoire l'aléa (k) renouvelé par l'expéditeur lors de chaque opération d'aveuglement ou de maquillage est remplacé
par la quantité h(m~a) Dans le cas d'un système cryptographique comprenant un protocole d'échange de clés de type Diffie-Hellman selon un appareil souhaitant envoyer un message m utilise, à la place lo d' un secret aléatoire, la quantité h (m ~ a) où a est une donnée secrète.
Dans ce même cas de ce système cryptographique ledit protocole comporte au moins les êtapes suivantes .
a. Un premier appareil, souhaitant envoyer le message m, calcule bl = ghcm'a) mod p ;
b. Un second appareil, récepteur, génère un alêa a et calcule bz = ga mod p ;
c. Les deux appareils êchangent bl et b2, et calculent clé
- ga h (m I a) mOd p i 2o d. Le premier appareil chiffre c - f (m, clé) où f est un mécanisme de chiffrement symétrique ;
le premier appareil envoie c au second appareil qui le dëchiffre et retrouve m.
D'une manière préférentielle, les appareils communiquants sont des cartes à puce, des cartes PCMCIA, des badges, des cartes sans contact ou tout autre appareil portable.
Préférentiellement, la communication entre lesdits appareils mettant en oeuvre l'invention est réalisée par le biais d'echanges de signaux électroniques, d~ondes radio ou de signaux infrarouges.
WO 98!51038 PCT/FR98/00901 Dans la suite, l'invention est présentée d'une façon plus détaillée en reprenant les notations utilisées dans la description des familles d'applications.
Comme dit précédemment, l'idée de générer un aléa par une opération de hachage h. Pour les deux premières familles d'application de l'invention, h prendra pour paramètre une donnée secrète, à savoir la clef secrète du signeur, et une donnée publique, le message à signer.
Pour la troisième famille, h prendra en paramètre l0 seulement le message à signer.
Enfin,~pour les autres familles, h prendra en paramètre une donnée publique et une donnée secrète (notée a dans la suite ) .
Plus précisément .
- pour la première famille concernant lesdits schémas de signature de type E1-Gamal, l'aléa k est généré de la façon suivante . k - h(m'x) où m est le haché du message M devant être signé et x, la clef secrète du signataire. Le reste de la génération de la signature (r, s) s'effectue de façon identique au procédé original. De même la vérification de la signature générée reste inchangée.
- pour la deuxième famille concernant lesdits schémas de signature dérivés des protocoles à divulgation nulle, k est généré de la façon suivante . k - h(m~B) avec m le haché du message M devant être signé et B, la clef secrète du signeur.
Le reste de la génération de la signature (d,D) s'effectue de façon identique au procédé original. De même la vérification de la signature générée reste inchangée.
- pour la troisième famille concernant lesdits schémas de chiffrement nécessitant un aléa, deux cas sont à considérer:
O Cas du chiffrement d'El Gamal .
_ 19 - l'aléa k est généré de la façon suivante . k = h(m) avec m le message devant être chiffré. On effectue ensuite l'algorithme d'El Gamal de la façon décrite précédemment. Le déchiffrement reste également inchangé.
O Cas du chiffrement de Mc Eliece .
- au lieu de dériver le vecteur d' erreur e â partir d' un aléa, il est génêré à partir de h(m), où m est le message à
chiffrer. Il est rappelé que e doit être de poids de Hamming exactement t. Une façon de dériver un vecteur de taille n (taille du code considéré) et de poids t à partir de h (m) est la suivante .
- supposons que l'on ait ordonné les vecteurs de taille n et de poids t. On peut alors choisir le vecteur de cette liste qui est en position h (m) (ou une position dérivée de h (m) , car IS ce nombre peut dépasser binomial.(t,n), suivant t,n, et la fonction de hachage utilisée) comme vecteur e.
On effectue ensuite l'algorit;hme de McEliece de la façon décrite prêcédemment. Le déchiffrement reste également inchangê.
En outre, ce procédé de génération de e permet de résoudre le problème du chiffrement d'un 'même message deux fois. En effet, dans le cas du McEliece générique, il est imprudent de chiffrer un même message deux fois (donc avec deux vecteurs d'erreur différents), car l'on peut deviner une partie du support des vecteurs d'erreurs, et par suite retrouver plus facilement le message clair.
Avec notre génération de e, un même message aura toujours le même chiffré.
L'invention s'applique de la manière suivante à la quatrième famille, qui concerne les schémas cryptographiques nécessitant un « padding » alêatoire .
- comme précisé, une mesure de sécurité recommandable est de ~ padder » les messages avec une séquence aléatoire. Mais là
encore, si la séquence varie pour plusieurs chiffrements d'un même message, une attaque est encore possible révélant le message clair.
L'utilisation de la méthode déterministe de génêration d'un aléa permet d'enrayer efficacement ce type de phénomëne.
En effet, en ajoutant au message m autant de fois que nécessaire (le padding doit être au moins long de 1/6 de la l0 taille de n, soit entre 86 et 171 bits pour des tailles de module classiques allant de 512 à 1024 bits) les valeurs ki =
h(m,a,i), a étant un secret d'au moins 128 bits, l'ensemble des attaques devient impossible car plus aucune relation n'existe entre les messages et de plus, un même message chiffré
plusieurs fois le sera toujours avec le même padding. Le chiffrement d'un message m s'effectue alors de la manière suivante par l'expéditeur .
O Générer autant de ki = h(m~a~i) que nécessaire pour que la longueur des ki concaténés soit au moins égale à 1/6 de la taille de n ; on pourra également préférer utiliser un seul k =
h(m~a) puis expanser k avant de le concaténer au message ;
O Composer mr tel que mr = taille (m) ~m~ tki~ ;
Calculer le cryptogramme c - mre mod n afin que le récepteur déchiffre c en calculant mr = cd mod n. Le récepteur extrait ensuite m simplement, connaissant sa taille et donc les bits significatifs de mr.
Pour la cinquième famille concernant les facteurs d'aveuglement et signatures en blanc, trois cas sont â
considérer .
0 Cas de la Signature en Blanc .
- k est généré de la façon suivante . k.= h(m~a) avec m le messâge devant être signé et a une: donnée secrète. Le reste de la génération de la signature en blanc s'effectue de façon identique au procédê original. De même l'extraction de la signature de m reste inchangée ;
D Cas du maquillage aléatoire .
- on génère k de la façon suivante . k - h ( a t b ~ a) avec a et b les opérandes à multiplier et a une donnée secrète. Le reste de l'opêration de maquillage aléatoire s'effectue de façon identique au procédé original. De même la réduction . modulaire de c' par le receveur reste inchangée ;
~ Cas des mécanismes de protection contre les attaques basées sur la mesure du temps d'un processus .
- dans le cas de la signature RSA par exemple, on génère le multiple aléatoire k de (p-1) (q-1) de la façon suivante . k - h (m ~ a) avec m le message à signer, et a une donnée secrète .
Le reste de l'opération de maquillage de l'exposant (d'=d+k(p 1)(q-1)) s'effectue de façon identique au procêdê original.
L'invention s'applique de la rnanière suivante à la sixième famille, qui concerne lesdits schÉ~mas d'échange de clés basés sur la methode de Diffie-Hellman.
Dans le système d'échange de clés de type Diffie-Hellman l'appareil, appelé aussi dispositif, qui souhaite envoyer un message m, utilise, à la place d'un aléa la quantitê h(m~a) où
a est une donnée secrète fixe. Un peut évidemment de façon naturelle étendre cette méthode à l'ensemble des participants au protocole. Ce dernier comporte, au moins, les étapes suivantes .
un premier dispositif, souhaitant envoyer le message m, cal cule X = gh ~'°' a~ mod p ;
~ un second dispositif, rêcepteur, génère un aléa y et calcule Y = gY mod p ;
~ les deux dispositifs échangent X et Y, et calculent clé
- gY.nc~ I 6> mod p ;
~ le premier dispositif chiffre c - f(m,clé) où f est un mécanisme de chiffrement symétrique ;
~ le premier dispositif envoie c au second dispositif qui le déchiffre et retrouve m.
L'invention sera plus facile à comprendre à l'aide des figures 1 à 4.
La figure 1 décrit l'organigramme d'un appareil de signature ou de déchiffrement mettant en oeuvre le système proposé par la présente invention.
La figure 2 décrit l'organigramme d'un appareil de vérification ou chiffrement mettant en oeuvre le système proposé par la présente invention.
La figure 3 représente les données échangées par le dispositif de signature et le dispositif de vérification.
La figure 4 représente les données échangées par le dispositif de chiffrement et le dispositif de déchiffrement.
Selon l'invention proposée, chaque appareil de signature/déchiffrement (typiquement une carte à puce) se compose d'une unité de traitement (CPU), d'une interface de communication, une mémoire vive (RAM) et/ou une mémoire non inscriptible (ROM) et/ou une mémoire inscriptible (généralement ré inscriptible) (EPROM ou EEPROM).
Le CPU et/ou la ROM de l'appareil de signature/déchiffrement contiennent des programmes ou des ressources de calcul correspondant aux êtapes de l'algorithme 3o de signature/déchiffrement (règles de calcul et d'utilisation de la fonction de hachage, multiplication, mise au carré, z3 addition, inverse modulaire et réduction modulaire). Certaines de ces opérations peuvent être regroupées . par exemple, la réduction modulaire peut-être directement intégrée dans la multiplication.
La RAM contient le message M sur lequel s'applique la fonction de hachage ou les règles de calcul pour la génération de signatures ou les règles de calcul pour la génëration de cryptogrammes. L'E(E)PROM contient au moins les paramètres m ,x et k gënérés et utilisés comme précisé dans la description qui lo suit .
Le CPU commande, via les bus d'adresses et de données, l'interface de communication, les opérations de lecture et d'écriture mémoire.
Chaque appareil de signature est protégé du monde extérieur par des protections physiques. Ces protections devraient être suffisantes pour empêcher toute entité non autorisée d'obtenir la clef secrète. Les techniques les plus utilisées de nos. jours en la matière sont l' intêgration de la puce dans un module de sécurité et l'équipement des puces de dispositifs capables de détecter des variations de température, de lumière ainsi que des tensions et des fréquences d'horloge anormales. Des techniques de conception particulières, telles que l'embrouillage de l'accès mémoire, sont également utilisées.
Selon l'invention proposée, l'appareil de vérification se compose au minimum d'une unité de traitement (CPU) et de ressources mémoires.
Le CPU commande, via les bus d'adresse et de donnêes, l'interface de communication, les opération de lecture et d'écriture mémoire.
Le CPU et/ou la ROM de l'autorité contiennent des programmes ou des ressources de calcul permettant d'implémenter le protocole de signature ou de chiffrement (règles de calcul.
et fonction de hachage, multiplication, exponentiation et réduction modulaire). Certaines de ces opérations peuvent être regroupées (par exemple, la réduction modulaire peut-être directement intégrée dans la multiplication).
Claims (12)
1. Système cryptographique, nécessitant normalement le tirage d'un aléa k, l'aléa étant un entier, caractérisé en ce qu'il est mis en oeuvre en remplaçant ledit aléa k par la quantité h(m~secret) où h est une fonction de hachage, m est le message intervenant dans ledit système et «secret» est un secret inconnu du monde extérieur au systèmes cryptographique.
2. Système cryptographique selon la revendication 1 caractérisé en ce qu'il comprend au moins.
- un système de signature à clé publique;
- un système de chiffrement à clé publique;
- un système de «padding» aléatoire;
- un système de génération de facteurs d'aveuglement;
- un protocole d'échange de clés.
- un système de signature à clé publique;
- un système de chiffrement à clé publique;
- un système de «padding» aléatoire;
- un système de génération de facteurs d'aveuglement;
- un protocole d'échange de clés.
3. Système cryptographique comprenant un système de signature à clé publique de type DSA, Schnorr, E1-Gamal, GOST
34.10 ou la norme IEEE de courbes elliptiques ECDSA, selon la revendication 2, caractérisé en ce que l'aléa (k) renouvelé par le signeur lors de chaque signature est remplacé par la quantité h(m~x), où x est la clef secrète du signeur.
34.10 ou la norme IEEE de courbes elliptiques ECDSA, selon la revendication 2, caractérisé en ce que l'aléa (k) renouvelé par le signeur lors de chaque signature est remplacé par la quantité h(m~x), où x est la clef secrète du signeur.
4. Système cryptographique comprenant un système de signature à clé publique de type Fiat-Shamir ou Guillou-Quisquater, selon la revendication 2, caractérisé en ce que l'aléa renouvelé par le signeur lors de chaque signature est remplaçé par la quantité h(m~B), B étant la clef secrète du signeur et m le message à signer.
5. Système cryptographique comprenant un système de chiffrement à clé publique de type E1 Gamal, selon la revendication 2, caractérisé en ce que l'aléa (k) renouvelé par le chiffreur lors de chaque envoi de message chiffré est remplacé par la quantité h(m).
6. Système cryptographique comprenant un système de chiffrement à clé publique de type McEliece selon la revendication 2, caractérisé en ce que le vecteur d'erreur aléatoire e, renouvelé par le chiffreur à chaque chiffrement est dérivé à partir de la quantité h(m), où m est le message à
chiffrer.
chiffrer.
7 Système cryptographique comprenant un système de «padding» aléatoire intervenant dans un système de chiffrement à clé publique, selon la revendication 2, caractérisé en ce que le chiffreur possède une clé a inconnue du déchiffreur et en ce que le padding des messages est réalisé
selon les étapes suivantes:
a. Générer autant de k i=h(m¦.sigma.¦i) que nécessaire pour que la longueur des k i concaténés soit au moins égale à 1/6 de la taille du module n (dans le cas du chiffrement RSA par exemple), ou bien générer k=h(m¦.sigma.) et l'expanser;
b. Composer m r tel que m r = taille(m)¦m¦{k i};
c. Chiffrer m r à la place de m.
selon les étapes suivantes:
a. Générer autant de k i=h(m¦.sigma.¦i) que nécessaire pour que la longueur des k i concaténés soit au moins égale à 1/6 de la taille du module n (dans le cas du chiffrement RSA par exemple), ou bien générer k=h(m¦.sigma.) et l'expanser;
b. Composer m r tel que m r = taille(m)¦m¦{k i};
c. Chiffrer m r à la place de m.
8. Système cryptographique comprenant un système de génération d'un facteur d'aveuglement dans le cadre d'une génération signature en blanc ou d'une opération de maquillage aléatoire selon la revendication 2, caractérisé en ce que l'aléa (k) renouvelé par l'expéditeur lors de chaque opération d'aveuglement ou de maquillage est remplacé par la quantité
h(m¦.sigma.)
h(m¦.sigma.)
9. Système cryptographique comprenant un protocole d'échange de clés de type Diffie-Hellman selon la revendication 2, caractérisé en ce qu'un appareil souhaitant envoyer un message m utilise, à la place d'un secret aléatoire, la quantité h(m'a) où a est une donnée secrète.
10. Système cryptographique selon la revendication 9, caractérisé en ce que ledit protocole comporte au moins les étapes suivantes.
a. Un premier appareil, souhaitant envoyer le message m, calcule b1 = gh(m~.sigma.) mod p;
b. Un second appareil, récepteur, génère un aléa a et calcule b2 = ga mod p;
c. Les deux appareils échangent b1 et b2, et calculent clé
- ga h(m~.sigma.) mod p d. Le premier appareil chiffre c = f (m, clé) où f est un mécanisme de chiffrement symétrique;
- le premier appareil envoie c au second appareil qui le déchiffre et retrouve m.
a. Un premier appareil, souhaitant envoyer le message m, calcule b1 = gh(m~.sigma.) mod p;
b. Un second appareil, récepteur, génère un aléa a et calcule b2 = ga mod p;
c. Les deux appareils échangent b1 et b2, et calculent clé
- ga h(m~.sigma.) mod p d. Le premier appareil chiffre c = f (m, clé) où f est un mécanisme de chiffrement symétrique;
- le premier appareil envoie c au second appareil qui le déchiffre et retrouve m.
11. Système cryptographique selon l'une quelconque des revendication 1 à 10, caractérisé en ce que les appareils sont des appareils communiquants sont des cartes à puce, des cartes PCMCIA, des badges, des cartes sans contact ou tout autre appareil portable.
12. Système cryptographique selon l'une quelconque des revendication 1 à 11, caractérisé en ce que la communication entre lesdits appareils le mettant en oeuvre est réalisée par le biais d'echanges de signaux électroniques, d'ondes radio ou de signaux infrarouges.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR97/06198 | 1997-05-07 | ||
| FR9706198A FR2763194B1 (fr) | 1997-05-07 | 1997-05-07 | Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d'aleas |
| PCT/FR1998/000901 WO1998051038A1 (fr) | 1997-05-07 | 1998-05-05 | Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d'aleas |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CA2288767A1 true CA2288767A1 (fr) | 1998-11-12 |
Family
ID=9507074
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA002288767A Abandoned CA2288767A1 (fr) | 1997-05-07 | 1998-05-05 | Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d'aleas |
Country Status (7)
| Country | Link |
|---|---|
| EP (1) | EP0980607A1 (fr) |
| JP (1) | JP2001507479A (fr) |
| CN (1) | CN1262830A (fr) |
| AU (1) | AU7659598A (fr) |
| CA (1) | CA2288767A1 (fr) |
| FR (1) | FR2763194B1 (fr) |
| WO (1) | WO1998051038A1 (fr) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2788909B1 (fr) | 1999-01-27 | 2004-02-20 | France Telecom | Procede d'authentification ou de signature a nombre de calculs reduit |
| FR2814577B1 (fr) * | 2000-09-22 | 2003-09-12 | Laurent Francois Ernest Pele | Boitier lecteur de carte a memoire connectable a un autre boitier homologue pour permettre le dialogue entre 2 cartes a puce |
| JP4550438B2 (ja) * | 2004-01-21 | 2010-09-22 | 三菱電機株式会社 | 被認証装置、認証システム、認証方法および認証集積回路 |
| FR2917197B1 (fr) * | 2007-06-07 | 2009-11-06 | Thales Sa | Procede de masquage du resultat d'une operation de multiplication modulaire et dispositif associe. |
| US9621525B2 (en) * | 2014-06-02 | 2017-04-11 | Qualcomm Incorporated | Semi-deterministic digital signature generation |
| US11120167B2 (en) * | 2019-03-25 | 2021-09-14 | Micron Technology, Inc. | Block chain based validation of memory commands |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5299262A (en) * | 1992-08-13 | 1994-03-29 | The United States Of America As Represented By The United States Department Of Energy | Method for exponentiating in cryptographic systems |
| US5432852A (en) * | 1993-09-29 | 1995-07-11 | Leighton; Frank T. | Large provably fast and secure digital signature schemes based on secure hash functions |
-
1997
- 1997-05-07 FR FR9706198A patent/FR2763194B1/fr not_active Expired - Fee Related
-
1998
- 1998-05-05 AU AU76595/98A patent/AU7659598A/en not_active Abandoned
- 1998-05-05 JP JP54778798A patent/JP2001507479A/ja not_active Abandoned
- 1998-05-05 CN CN 98806980 patent/CN1262830A/zh active Pending
- 1998-05-05 EP EP98924379A patent/EP0980607A1/fr not_active Withdrawn
- 1998-05-05 CA CA002288767A patent/CA2288767A1/fr not_active Abandoned
- 1998-05-05 WO PCT/FR1998/000901 patent/WO1998051038A1/fr not_active Application Discontinuation
Also Published As
| Publication number | Publication date |
|---|---|
| EP0980607A1 (fr) | 2000-02-23 |
| WO1998051038A1 (fr) | 1998-11-12 |
| JP2001507479A (ja) | 2001-06-05 |
| FR2763194B1 (fr) | 2000-07-28 |
| AU7659598A (en) | 1998-11-27 |
| FR2763194A1 (fr) | 1998-11-13 |
| CN1262830A (zh) | 2000-08-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP2345202B1 (fr) | Procédé de signature numérique en deux étapes | |
| EP2526505B1 (fr) | Dispositif et procédé d'obtention d'une clé cryptographique | |
| RU2376651C2 (ru) | Использование изогений для разработки криптосистем | |
| EP1710952B1 (fr) | Applications cryptographiques du couplage de Cartier | |
| US7912216B2 (en) | Elliptic curve cryptosystem optimization using two phase key generation | |
| EP1151576B1 (fr) | Procede cryptographique a cles publique et privee | |
| EP3010177A1 (fr) | Procédé d'authentification d'un dispositif client auprès d'un serveur à l'aide d'un élément secret | |
| KR20000071078A (ko) | 유한 필드상의 이산 대수 암호시스템의 원분 다항식 구조 | |
| US20030152218A1 (en) | Cryptography method on elliptic curves | |
| EP0666664B1 (fr) | Procédé de signature numérique et d'authentification de messages utilisant un logarithme discret avec un nombre réduit de multiplications modulaires | |
| CA2288767A1 (fr) | Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d'aleas | |
| KR100971038B1 (ko) | 다수의 엔티티와 그에 따른 장치에 부하를 분배하는암호화 방법 | |
| US7519178B1 (en) | Method, system and apparatus for ensuring a uniform distribution in key generation | |
| EP0962069B1 (fr) | Systeme cryptographique comprenant un systeme de chiffrement et de dechiffrement et un systeme de sequestre de cles | |
| FR2818846A1 (fr) | Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie | |
| WO2002028011A1 (fr) | Procede de transmission accelere de signature electronique | |
| FR2842052A1 (fr) | Procede et dispositifs cryptographiques permettant d'alleger les calculs au cours de transactions | |
| US20050123131A1 (en) | Cryptographic system comprising an encryption and decryption system and a key escrow system, and the associated equipment and devices | |
| EP1829279A2 (fr) | Procede et dispositif d'execution d'un calcul cryptographique | |
| JP2004222331A (ja) | ユーザが電子商取引／情報サービス提供者の正当性をチェックできるようにする方法 | |
| CN116415265A (zh) | 加密、加密签名处理、解密方法及相关设备 | |
| WO2003044619A2 (fr) | Procede de verification de vente dans une transaction privee d'articles electroniques | |
| WO2003021864A2 (fr) | Procede de reduction de la taille d'une signature rsa ou rabin | |
| Song et al. | A distributed E-Business system based on conic curve | |
| Eslami et al. | Secret selling of secrets with elliptic curves |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EEER | Examination request | ||
| FZDE | Discontinued |