Brevet FR2763194A1 — publié le 19981113

GENERATEUR PSEUDO-ALEATOIRE BASE SUR UNE FONCTION DE HACHAGE POUR SYSTEMES CRYPTOGRAPHIQUES NECESSITANT LE TIRAGE D'ALEAS 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 (typiquement DSA, El-Gamal, Fiat-Shamir,10 Guillou- Quisquater pour les signatures, El-Gamal et McEliece pour le chiffrement), par des dispositifs de signature ou de chiffrement (typiquement microprocesseurs) dépourvus de ressources matérielles ou logicielles permettant le tirage d'aléas.15 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 with Related Message " et " Finding a small root of a univariate modular equation ") par la génération à peu de frais, c'est à dire peu couteuse, 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 cles de type Diffie-Hellman. Malgré une diffusion généralisée et une bonne acceptation du concept de carte à puce de la part du public, la plupart des applications pratiques sont apparues seulement voici quelques 2 2763194 années, principalement à cause des limitations de puissance de calcul des cartes. Les progrès en matière de capacité de stockage non volatile des informations, la sécurité et la technologie des circuits (par exemple l'EEPROM) encouragent5 l'émergence rapide de nouvelles générations de 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 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,20 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é entre25 les diverses touches est connu de l'attaquant. La présente invention propose une solution de substitution permettant la mise en oeuvre de slstè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 2763194 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'algorithmes cryptographiques auxquelles s'applique l'invention, celles-ci étant au nombre de six. La première famille d'application concerne les schémas de signature de type El-Gamal. L'algorithme de signature d'El-Gamal décrit dans l'article intitulé " A public-key cryptosystem and a signature scheme based on discrete logarithms " 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 signature connus: Schnorr, breveté aux EtatsUnis 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. Dans la suite, il est rappelé l'algorithme DSA. Le Standard de Signature Numérique (DSA, brevet américain no. 5.231.668 intitulée "Digital Signature Algorithm") a été 4 2763194 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 de5 grands nombres représentés dans un 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 l'identité du signataire et l'intégrité des données. Le DSA10 permet 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). Il 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 a la capacité de vérifier la signature d'un utilisateur en20 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 = 64 a pour un a quelconque. Un module premier q tel que 2159 h est un entier quelconque vérifiant i c h Un nombre x, généré aléatoirement ou pseudo aléatoirement. 2763194 Un nombre y défini par la relation: y = gx mod p. ) Un nombre k généré aléatoirement ou pseudo aléatoirement tel que 0 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 secrets. Le paramètre k10 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 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. Après avoir testé que r et s X 0, comme expliqué dans la description du DSA, la signature {r, s} est envoyée au vérifieur qui calcule:25 w = 1/s mod q u1 = m w mod q u2 = r w mod q v =gul yu2 modp mod q 0 Et compare si v et r sont égaux afin d'accepter ou rejeter la signature. 6 2763194 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. Les paramètres de l'algorithme de Guillou-Quisquater 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; Un module public n = p q et une chaine ID représentant l'identité du signeur; 3 Un exposant public v et une clé secrète B telle que Bv 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 = kv mod n et génère la signature: 7 2763194 d = h(T,m) et D = k Bh(Tm) mod n; Le vérifieur s'assure de l'authenticité de la signature en vérifiant que: d = h(T',m) avec T'= Dv 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); () Un nombre g, d'ordre p-1 modulo p (i.e. tel que, pour tout nombre entier u, 0 que 0 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 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. Le chiffré d'un message m, 0 m p-1, est la paire d'entiers (r,s), o: k k r = g mod p et s = m y mod q. 8 2763194 Pour retrouver le message m, le receveur des cryptogrammes (qui possède x), calcule: s/rX 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 une classe de codes particulière connue sous le nom de codes de Goppa. L'idée générale est de déguiser un code de Goppa en code linéaire quelconque; il existe en effet un algorithme efficace pour décoder un code de Goppa mais en revanche décoder un code15 linéaire général est un problème difficile. Le récepteur connaissant l'information ayant permis de déguiser le code, pourra donc déchiffrer le message en décodant le code de Goppa obtenu. Les paramètres de l'algorithme de McEliece (toutes les formules qui suivent sont entendues dans GF(2)) sont: O 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; 0 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; 9 2763194 3 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-l = m TP-1+ eP'l = mSG + eP'l Puisque e est de poids t, eP1- est aussi de poids t. Le vecteur CP-l 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 d'application concerne les schémas cryptographiques nécessitant un " padding " aléatoire Il 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é 2763194 " Cryptographic 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 lors du traitement d'un ensemble de paramètres accessible à 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 l 2763194 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; Un module public n = p q; 3 Une paire d'exposants notée (e,d) tels que: e d = 1 mod (p-l) (q-l). 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 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 small 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 de chiffrement la modification suivante: Afin de chiffrer le message m, l'expéditeur génère une séquence sr comportant un certain degré d'aléatoirité et calcule le cryptogramme c = (misr)e mod n, le signe I indiquant la concaténation; le récepteur déchiffre c en calculant cd mod n et retrouve m en retranchant le padding. 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 d'application 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 faire signer un message sans que le signeur puisse prendre 13 2763194 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 Gamal5 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. Il sera décrit ici seulement le10 mécanisme de signature en blanc basé sur le RSA. 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::15 s = m mod n la vérification se faisant naturellement: se mod n = (m) e mod n = m Les étapes de l'obtention d'une signature en blanc par l'expéditeur E d'un message m sont: O E génère un nombre aléatoire k, calcule le facteur d'aveuglement k' mod n et envoie m'= mke mod n au récepteur ou (signeur); le récepteur calcule s' = m'ld mod n et qui est la signature de m' et envoie s' à E; E calcule s'/k = (mke) d/k = mk' /k = m mod n, et obtient donc la signature s de m. 14 2763194 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: O le signeur génère un nombre aléatoire k et calcule: d' = d + k(p-l) (q-l), il génère ensuite la signature de m en calculant: d' d+k(p-1) (q-1) d ((p-1) (q-1) k d m = mo =modn. La sixième famille d'application concerne les schémas d'échange de clés basés sur la méthode de Diffie-Hellman 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 parties (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 (A) et l'appareil (B) s'entendent:un nombre premier p d'au moins 512 bits et un entier g, racine primitive 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 = gX 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 la connaissance de la quantité clé' = clé = gxy 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 à10 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,20 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 possibles. 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 micro25 contrôleurs peu chers de type 8 bits, à coeur de 80C51 ou 68HC05 par exemple. Le principal avantage du procédé inventif en regard des propositions précédentes en matière de signatures numériques ou30 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(mlsecret) 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. Dans le cas d'un système cryptographique qui comprend un système de signature à clé publique de type DSA, Schnorr, El- 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(mlx), 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 chaque signature est remplacé par la quantité h(mIB), 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 de 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 " padding " aléatoire intervenant dans un système de chiffrement à clé publique, le chifreur possède une clé a inconnue du déchiffreur et le " padding " des messages par le chiffreur est réalisé selon les étapes suivantes: a. Générer autant de ki=h(maJ1i) que nécessaire pour que la longueur des ki concaténés soit au moins égale à 1/6 de la 19 2763194 taille du module n (dans le cas du chiffrement RSA par exemple) ou bien générer k=h(mclo) et l'expanser; b. Composer mr tel que mr = taille(m) ImI{k }; 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(mla). Dans le cas d'un système cryptographique comprenant comprenant un protocole d'échange de clés de type Diffie-Hellman, un appareil souhaitant envoyer un message m utilise, à la place d'un secret aléatoire, la quantité h(mlc) 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 b1 = gh(mGa) mod p b. Un second appareil, récepteur, génère un aléa a et calcule b2 = ga mod p a c. Les deux appareils échangent b1 et b2, et calculent clé = g h(ml1) 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. 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. 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'application. Comme dit précédemment, l'idée est 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 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 El-Gamal, l'aléa k est généré de la façon suivante: k = h(mlx) 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(mlB) 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 de10 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: 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é.20 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 qui30 est en position h(m) (ou une position dérivée de h(m), car 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'algorithme 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 a 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 taille de n, dans le cas du chiffrement RSA, soit entre 86 et 171 bits pour des tailles de module classiques allant de 512 à 1024 bits) les valeurs ki = h(m,o,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 23 2763194 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(mlali) 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(mla) puis expanser k avant de le concaténer au message; Composer mr tel que mr = taille(m) ImI{ki}; ( 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:20 O Cas de la Signature en Blanc: k est généré de la façon suivante: k = h(mlc) avec m le message 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; - e Cas du maquillage aléatoire: On génère k de la façon suivante: k = h(albla) avec a et b les opérandes à multiplier et a une donnée secrète. Le reste de 24 2763194 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; 0 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-l) (q- l) de la façon suivante: k = h(mla) 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-l) (q-l)) s'effectue de façon identique au procédé original. L'invention s'applique de la maniè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(mla) o a est une donnée secrète fixe. On 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, calcule X = gh(M1) mod p; * Un second dispositif, recepteur, génère un aléa y et calcule Y = gy mod p; * Les deux dispositifs échangent X et Y, et calculent clé = gy.h(ml) 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 i 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 de signature/ déchiffrement (règles de calcul et d'utilisation de la fonction de hachage, multiplication, mise au carré, 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 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). Revendications 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(mlsecret) 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. 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. 3. Système cryptographique comprenant un système de signature à clé publique de type DSA, Schnorr, El-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(mlx), 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(mlB), 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 El 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. 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 chifreur 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 ki=h(mlali) 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(ml[) et l'expanser; b. Composer mr tel que mr = taille(m) m {ki}; c. Chiffrer mr à 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(mlao). 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(mla) 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 bl = gh déchiffre et retrouve m. 11. Système cryptographique selon l'une quelconque des revendications 1 à 10, caractérisé en ce que les 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 revendications 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.