Brevet FR2807248A1 — publié le 20011005

PROCEDE DE SIGNATURES NUMERIQUES PROBABILISTES La présente invention concerne un procédé de génération de signatures numériques probabilistes afin de permettre la vérification de l'intégrité d'un message transmis. La présente invention s'applique en particulier au domaine des cartes à puce avec ou sans contact. De telles cartes constituent en effet des supports d'informations sécurisés et comportent en général un micro-contôleur incorporé sur une puce de circuit intégré. Un micro-contrôleur possède une architecture semblable à celle d'un ordinateur. I1 comporte une unité de traitement constituée d'un microprocesseur ou CPU (de l'anglais Central Processing Unit) associée à différents types de mémoires. Une mémoire non volatile, de type ROM par exemple, comporte en général au moins un programme de mise en oeuvre d'un algorithme de signature. L'invention s'applique en particulier à des algorithmes de génération et de vérification de signatures numériques. L'objectif de ces algorithmes est de calculer un ou plusieurs entiers, en général une paire, appelés la signature et associés à un message donné afin de certifier l'identité du signataire et l'intégrité du message signé. De tels algorithmes permettent d'une part de générer des signatures et d'autre part de vérifier ces signatures. La signature est dite probabiliste lorsque l'algorithme fait appel à un aléas dans la génération de la signature, cet aléas étant secret et régénéré à chaque nouvelle signature. Ainsi, un même message transmis par un même utilisateur peut avoir plusieurs signatures distinctes. Un exemple d'un tel algorithme peut être illustré par le DSA (de l'anglais Digital Signature Algorithm). Les paramètres du DSA sont - p, un grand premier connu, de 512 ou 1024 bits, - q, un premier qui divise p-1, de 160 bits, - g, un entier choisi tel que gq = 1 mod p avec g # 1 mod p. La clé secrète x est un nombre aléatoirement fixé entre 0 et 216o-1, et la clé publique y est liée à x par la relation y = gx mod p. Soit m, le message à envoyer. La signature DSA de m est la paire (r, s) définie comme suit r = (g" mod p) mod q ; s = ( h (m) + r - x) / k mod q ; avec k un nombre aléatoire de 160 bits tel que k La vérification de la signature s'effectue comme suit On réalise un premier calcul intermédiaire w = s-1 mod q on vérifie si ((gW-"(`") y"")mod p)mod q r. Si cette égalité est vrai, la signature est authentique. La génération de la signature (r, s) a été réalisée avec la clé secrète x et un nombre aléatoire k secret et différent pour chaque signature, et sa vérification avec la clé publique y. Ainsi, n'importe qui peut authentifier une carte et son porteur sans détenir sa clé secrète. L'utilisation de la fonction de hachage dans la génération de la signature se retrouve dans quasiment tous les algorithmes de génération de signatures probabilistes basés sur un calcul de logarithme discret. Elle permet en effet de garantir la non reproductibilité de la signature en brisant sa linéarité. L'emploi de cette fonction de hachage présente néanmoins des inconvénients car elle suppose d'une part que cette fonction h se comporte comme une fonction aléatoire, ce qui n'est pas toujours vrai, .et d'autre part que cette fonction h est implémentée dans la mémoire de la puce de circuit intégré du dispositif sécurisé (la carte à puce par exemple). Or la taille de code nécessaire à l'implémentation de la fonction de hachage est très élevée, environ 1 à 2 kilo octets. Les contraintes économiques liées au marché de la carte à puce obligent à une constante recherche en vue de maîtriser ses coûts de revient. Cet effort passe souvent par l'utilisation de composants plus simples. Dans un tel cadre, l'implémentation d'algorithmes à clé publique sur des micro-contrôleurs peu chers de types 8 bits à c#ur de 8051 (Intel) ou 6805 (Motorola) par exemple représente un intérêt grandissant. Il n'est cependant pas possible d'implémenter un algorithme de signature numérique tel que le DSA ou du même type, faisant appel à une fonction de hachage, sur de tels micro-contrôleurs. L'invention a pour but de résoudre ces contraintes et propose une solution qui soit adaptée à des micro- contrôleurs possédant peu de ressources de calcul. La présente invention a pour objet un procédé de génération de signatures numériques probabilistes qui permet de s'affranchir de la fonction de hachage, sans altérer la sécurité des messages échangés. L'invention propose à cet effet un procédé permettant de transformer un algorithme de signature probabiliste utilisant une fonction de hachage en un autre algorithme ne faisant pas appel à cette fonction. A cette fin, l'algorithme probabiliste de départ est utilisé deux fois au lieu d'une pour signer le message directement, c'est à dire le message initial non haché. On génère ainsi des signatures jumelles associées au même message. L'invention concerne plus particulièrement un procédé de signatures numériques probabilistes d'un message, entre un signataire et un vérifieur, à partir d'un algorithme basé sur le calcul d'un logarithme discret, caractérisé en ce qu'il consiste, pour le signataire, à générer au moins deux signatures du même message non haché, lesdites signatures étant calculées par l'algorithme au moyen des mêmes paramètres à clé publique et privée en faisant respectivement appel à des aléas distincts, et en ce qu'il consiste, pour le vérifieur, à vérifier toutes les signatures dudit message. Selon une application, l'algorithme probabiliste est le DSA (Digital Signature Algorithm). Selon une autre application, l'algorithme probabiliste est l'algorithme de Schnorr. L'invention s'applique avantageusement à tout dispositif sécurisé de type carte à puce, et en particulier à des dispositifs comportant un micro- contrôleur 8 bits. Le procédé selon l'invention présente l'avantage de s'affranchir de la fonction de hachage et de minimiser ainsi le taux d'occupation mémoire. En outre, la vitesse de calcul est accrue, même si un double calcul est requis. En effet, l'appel à une fonction de hachage est délicate sur de simples micro-contrôleurs 8 bits, peu chers et de plus en plus souvent utilisés pour contenir les coûts de fabrication des dispositifs. En outre, le procédé selon l'invention permet de garantir la sécurité dans l'exécution de n'importe quel algorithme de génération de signatures numériques probabilistes. La description fait référence à l'algorithme de signature DSA, mais s'applique également à tous les autres algorithmes de signatures probabilistes et à leurs variantes tels que ElGamal, Schnorr, EC-DSA, Abe- Okamoto, par exemple qui utilisent également la fonction de hachage dans la génération de paires de signatures. Le procédé de génération de signatures selon l'invention est basé sur le calcul d'au moins deux signatures, que l'on dit alors jumelles, du même message initial m non haché. La signature comprend ainsi au moins deux signatures calculées à l'aide des mêmes paramètres à clé publique y et privée x en faisant respectivement appel à des aléas distincts k1, k?, ... k,. La signature du message devient ainsi (r;, s;, r-, s@, ...r", s") , avec les n paires (ri, si) (pour i allant de 1 à n) calculées et vérifiées selon les procédés classiques de génération et de vérification de signatures qu'il s'agisse du DSA, de Schnorr ou de tout autre algorithme utilisant une fonction de hachage. REVENDICATIONS 1. Procédé de signatures numériques probabilistes d'un message (m), entre un signataire et un vérifieur, à partir d'un algorithme basé sur le calcul d'un logarithme discret, caractérisé en ce qu'il consiste, pour le signataire, à générer au moins deux signatures (ri, si) et (r2, s2) du même message non haché (m), lesdites signatures étant calculées par l'algorithme au moyen des mêmes paramètres à clé publique et privée (y, x) en faisant respectivement appel à des aléas distincts (k1) et (k2), et en ce qu'il consiste, pour le vérifieur, à vérifier toutes les signatures (rl,sl) et (r2, s2) dudit message (m). 2. Procédé selon la revendication 1, caractérisé en ce que l'algorithme probabiliste est le DSA (Digital Signature Algorithm). 3. Procédé selon la revendication 1, caractérisé en ce que, l'algorithme probabiliste est l'algorithme de Schnorr. 4. Dispositif sécurisé, de type carte à puce, caractérisé en ce qu'il comporte un composant électronique apte à mettre en oeuvre le procédé de signature selon les revendications 1 à 3. 5. Dispositif selon la revendication 4, caractérisé en ce que le composant électronique est un micro- contrôleur 8 bits.