FR 2733378 A1 19961025 FR 9504753 A 19950420 PROCEDE DE GENERATION DE SIGNATURES NUMERIQUES DE MESSAGES L'invention concerne un procédé de génération de signatures numériques de messages envoyés par un dispositif vérifieur à un dispositif prouveur comportant des moyens de calcul, de communication et de rétention de données comprenant au moins une mémoire non volatile programmable électriquement, selon lequel on prépare des données chiffrées constituant des coupons de signature que l'on charge dans la mémoire non volatile et que le dispositif prouveur utilise pour signer des messages connus par le dispositif vérifieur. Le procédé s'applique particulièrement à la signature de messages par des appareils portables du type cartes à microprocesseur. Le procédé est particulièrement adapté à la mise en oeuvre d'algorithmes de signatures du type DSA [(pigital Signature Algorithm, proposé par le US National Institute of Standards and Technology (A Proposed Federal Information Processing Standard for Digital Signature Standard (DSS), annoncé au Registre Fédéral le 30 août l991, pp 42980-42982)] par des cartes à microprocesseur dépourvues de ressources matérielles permettant de réaliser des opérations arithmétiques sur des grands nombres. 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 années principalement à cause des limitations de la puissance de calcul des cartes Les progrès constants en matière de 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ératicns de cartes et d'applications de plus en plus ambitieuses telles que le nouveau standard de signature numérique Américain (DSA). La Norme de Signature Numérique (DSA, demande de brevet américain no. 07/738.431 intitulée "Digital Signature Algonthm") a été proposée par le US National Institue of Standards and Technology afin de fournir une base appropriée pour des applications requérant des signature numériques au lieu de signatures classiques. Une signature DSA est une paire de 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 DSA permet de générer et vérifier des signatures. Ce 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). 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 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. On rappelle que les paramètres du DSA sont: O Un module premierp tel que 2L I quelconque. # Un module prem@er q tel que 2159 p-1 # Un nombre g, d'ordre q modulo p tel que g = h q mod p, où h est un entier quelconque p-1 vérifiant 1 I # Un nombre x, généré aléatoirement ou pseudo aléatoirement O 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ées 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 signataire calcule la signature {r,s} par : r=(gk mod p) mod q et s= m+xr/k mod q Où la division par k s'entend modulo q (i.e. 1/k est le nombre k' tel que kk' # 1 mod q). Par exemple, si q = 5 et k = 3 alors - =2 car 3x2 = 6 i 1 mod 5. k Après avoir testé que r # 0 # s, comme expliqué dans la description du DSA, la signature {r,s} est envoyée au vérifieur qui calcule: # w=1/s mod q # u1=mw mod q # u2 = r W mod q G) v =1 I yU2 mod p) mod q O Et compare si v et r sont égaux afin d'accepter ou rejeter la signature. Un procédé de signatures numériques basé sur l'utilisation de coupons c'est à dire encore de certificats pré-calculés a été décrit dans la demande de brevet français n 93 14466. Selon ce procédé la taille des coupons chargés dans la mémoire est relativement importante c'est à dire de l'ordre de 20 octets Un premier objet de l'invention est de réduire la taille des coupons afin de pouvoir charger un plus grand nombre de coupons dans le même espace mémoire tout en conservant bien sûr le même degré de sécurité que celui obtenu dans le cas de coupons de taille plus importante. Le procédé selon l'invention permet de charger un nombre plus important de coupons, 120 à 140, de taille plus réduite, 2 à 4 octets, tout un conservant toute la sécurité assurée avec l'utilisation de coupons plus longs. Selon l'invention les coupons sont compressés par une fonction de compression dite encore fonction de hachage. On rappelle qu'une fonction de hachage permet d'obtenir une chaîne de caractères de taille fixe en sortie quelque soit la taille de la chaîne de caractères en entrée. Selon une autre caractéristique de l'invention, on introduit une condition de temps dans l'étape de vérification afin d'empêcher tout dispositif ne possédant pas le secret de signer les messages ou d'être authentifié par le dispositif vérifieur, en trouvant la signature prouvant son authentification. A cette fin, l'étape de vérification v = f (r,s,m) = r inclue un chronométrage du dispositif vérifieur pendant le calcul de la signature de manière à invalider la signature si le temps pour fournir cette signature a dépassé celui imparti et la fonction f est choisie de manière à introduire une durée de calcul suffisante pour que la condition de temps ne soit pas remplie lorsque s est calculé à partir r = f(r, s, m). L'invention a plus particulièrement pour objet, un procédé de génération de signatures numériques de messages envoyés par un dispositif vérifieur à un dispositif prouveur comportant des moyens de calcul, de communication et de rétention de données comprenant au moins une mémoire non volatile programmable électriquemeat, selon lequel on prépare des données chiffrées constituant des coupons (ri) de signature que l'on charge dans la mémoire non volatile et que le dispositif prouveur utilise pour signer des messages envoyés par le dispositif vérifieur principalement caractérisé en ce que: les coupons sont compressés par l'application d'une fonction de compression dite encore fonction de hachage par une autorité certifiée avant d'être chargés dans la mémoire, et en ce qu'il comporte les échanges suivants:: le vérifieur et le prouveur conviennent d'un message m, le prouveur envoie un coupon ri au vérifieur, le vérifieur envoie un nombre aléatoire au prouveur et déclenche un chronomètre, le prouveur calcule la signature s du message et l'envoie au vérifieur, le vérifieur arrête le chronomètre et vérifie que la signature a été obtenue par le secret détenu par la carte et le coupon ri reçu à partir de la relation suivante v = f(ri,s,m) = le vérifieur accepte la signature si la condition de vérification v = ri est remplie et si le temps chronométré t ne dépasse pas une durée prédéterminée impartie. Selon une autre caractéristique de l'invention la fonction de compression utilisée pour obtenir les coupons et la fonction f utilisée pour la vérification de la signature sont les mêmes. Pour simplifier dans toute la suite de la description, on parlera de carte pour le dispositif prouveur et de terminal pour le dispositif vérifieur. Les contraintes économiques liées au marché de la carte à puce, entraînent une recherche constante en vue d'en 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 micro-contrôleurs peu chers de type 8 bits, à coeur de 8051 (Intel) ou 6805 (Motorala) par exemple. Afin d'atteindre ce but dans le cadre de l'implémentation d'un algorithme de signature numérique apparenté au DSA, I'invention proposée reprend le concept des coupons de signature : un ensemble de certificats pré-calculés et fournis par un centre certifié (autorité) au cours d'une phase préliminaire de communication on-line. Le principal avantage des coupons de signature dont il sera question ici en regard des propositions précédentes en matière de signature numérique réside dans la vitesse de calcul d'une signature par une carte basée sur un simple microcontrôleur 8 bits (aux alentours de 300ms, temps de transmission compris) et le faible taux d'occupation mémoire du coupon (typiquement de deux à quatre octets sauvegardés en EPROM ou en EEPROM). Le procédé de génération des signatures se décompose en deux phases distinctes le chargement des coupons par l'autorité ayant délivré la carte et l'utilisation des coupons par la carte face à un terminal ne connaissant pas x, le secret de la carte. Les deux phases font appel à deux fonctions de hachage. La première est une fonction de hachage au sens classique, par exemple la récente norme américaine SHA (Secure Hash Algorithm FIPS PUB XX, February 1, 1993, Digital Signature Standard), la fonction MDA, MD5 ou un hachage basé sur l'algorithme DES. La seconde fonction, dite de ralentissement et notée "f' est un procédé de hachage ayant pour but de ralentir (volontairement) la vérification de la signature f(m) et produire des chaînes (h) de taille (e) relativement courte (16 bits Dans l'exemple qui va suivre, nous proposons de reprendre les paramètres du DSA et une fonction f telle que: f (m) = SHA(SEIA(SElA(m)) mop)mo e CHARGEMENT DE n COUPONS DANS LA CARTE O La carte remet à zéro un compteur i en EPROM (ou EEPROM), génère un aléa J de 10 à 20 octets, I'enregistrc en EPROM (ou EEPROM) et l'envoie à l'autorité qui calcule, pour z allant de 1 à n L'autorité envoie les nombres r à la carte pour sauvegarde en EPROM (ou EEPROM) Lorsque la carte désire signer un message m, le protocole suivant est utilisé UTILISATION DU COUPON POUR SIGNER UN MESSAGE O La carte O Extrait J, x, i et r. de l'EPROM (ou EEPROM) o Calcule f = SHA(x, J, I) et A = xSHA(ri)mod q O Incrémente i et envoie r. au tçrminal (2) Le terminal génère un aléa a, I'expédie à la carte et déclenche un chronomètre t # La carte calcule, aussi vite que possible, s= I(SHA(m,a) + A)mod q et retourne cette valeur au terminal O Dès réception de s, le terminal arrête t et calcule # Le terminal accepte la signature si v=ri et si t est raisonnablement petit (par exemple @ 1 T2e 1.000.000 De façon plus générale, les coupons de signature interactive peuvent être étendus à tout protocole de Signature où le pré-calcul est possible, dont, en particulier, les protocoles de - # Rueppel-Nyberg New signature schemes based on the discrete logarithm problem publié dans les actes du colloque Eurocrypt'94. G!) Schnorr Efficient identification and signatures for smart-cards publié dans les actes du colloque Crypto'89. # El-Gamal A public-key cryptosystem and a signature scheme based on discrete logarithms publié dans la revue IEEE Transactions on Information Theory, vol. IT30, no. 4, pages 469472. # Guillou-Quisquater A practical zero-knowledge protocol fitted to security microprocessors minimizing hoth transmission and memory publié dans les actes du colloque Eurocrypt'88 et A paradoxical identity-based signature scheme resulting from zero-knowledge publié dans les actes du colloque Crypto'88. Os ou tout autre système à clé publique basé sur le logarithme discret où l'équation (m + xr) I k mod q est remplacée par une autre égalité faisant intervenir m, x, r, et k (comme expliqué dans l'article Me ta Message Recovery and Meta Blind signature schemes based on the discrete logarithm problem and their applications publié par Horster & al. dans les actes du colloque Asiacrypt'94) ou encore en utilisant plusieurs aléas distincts k ou plusieurs secrets distincts x dans la même signature. L'invention a pour second objet de mettre au point un protocole de paiement électronique permettant l'utilisation de cartes bas coûts. Ce protocole se déroule ainsi UTILISATION DU COUPON COMME CIIEQUE ELECTRONIQUE # La carte O Extrait J, x, i et r de l'EPROM (ou EEPROM) O Calcule I = SHA(x, J, i) et A = xSHA(ri)mod q # envoie r. et i au terminal et incrémente i # Le terminal génère un aléa a, I'expédie à la carte et déclenche un chronomètre t # La carte calcule, aussi vite que possible, s= I(SHA(m,i,a) + A) mod q et retourne cette valeur au terminal # Dès réception de s, le terminal arrête t et calcule : : 5 Le terminal accepte la signature si v=ri et si t est raisonnablement petit (par exemple t 1 T2e 1.000.000 6 Le terminal transmet (de façon différée) à l'autorité le cheque électronique 7 L'autorité s'assure que: s=SHA(x,J,i)(SHA(m,i,a)+xSHA(ri))mod q et crédite le compte du terminal du montant de la transaction signé par la carte. La figure 1 décrit l'organigramme d'une carte mettant en oeuvre le système proposé par la présente invention. La figure 2 décrit les données transmises entre la carte et le terminal au moment de l'utilisation du coupon: La figure 3 décrit l'organigramme d'un terminal mettant en oeuvre le système proposé par la présente invention. La figure 4 représente les données transmises entre la carte et l'autorité pendant la phase de chargement des coupons et l'organisation de la mémoire d'une carte après le chargement de n coupons. Selon l'invention proposée, chaque carte à puce se compose d'une unité de traitement (CPU) 11, d'une interface de communication 10, une mémoire vive (RAM) et/ou une mémoire non inscriptible (ROM) 14 et/ou une mémoire inscriptible (généralement réinscriptible) (EPROM ou EEPROM) 15. Le CPU 11 et/ou la ROM 14 de la carte à puce contiennent le message m des programmes ou des ressources de calcul correspondant à l'exécution des étapes Ci et (3) des protocoles de signature ou paiement (règles de calcul pour la génération de s et d'utilisation de la fonction de hachage SHS), multiplication, addition 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). De rnême que pour le DSS, la RAM de la carte contient le message M et l'aléa a sur lesquels s'applique la fonction de hachage SHS. L'E(E)PROM 15 contient typiquement les paramètres q, x, Jet le jeu de coupons généré et utilisé comme précisé dans la description qui suit. Le CPU 11 commande, via les bus d'adresse et de données 16, I'interface de communication 10, les opération de lecture et d'écriture en mémoire 13, 14 et 15. Chaque carte à puce est protégée du monde extérieur par des protections physiques 17. Ces protections devaient être suffisante pour empêcher toute entité non autorisée d'obtenir la clé secrète x. 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, le terminal se compose au minimum d'une unité de traitement (CPU) 30 et de ressources mémoires 32,33 et 34. Le CPU 30 commande, via les bus d'adresse et de données 35, I'interface de communication 31, les opération de lecture et d'écriture mémoire 32, 33 et 34. Le CPU 30 et/ou la ROM 34 de l'autorité contiennent des programmes ou des ressources de calcul permettant d'implémenter les règles de calcul et fonctions de hachage, ralentissement, multiplication, addition, inverse modulaire, exponentiation et réduction modulaire nécessaires au protocole de signature interactive.Certaines de ces opérations peuvent etre regroupées (par exemplc, la réduction modulaire peut-être directement intégrée dans la multiplication) Dans le cadre général de l'invention proposée, le chargement à distance et l'utilisation des coupons sont réalisés en échangeant entre la carte, I'autorité et Ic terminal-vérifieur au moins les signaux suivants CHARGEMENT DE n COUPONS DANS LA CARTE # La carte remet à zéro un compteur i en EPROM (ou EEPROM), génère un aléa J de 10 à 20 octets, I'enregistre en EPROM (ou EEPROM) et l'envoie à l'autorité qui calcule, pour z allant de I à n (D L'autorité envoie les nombres r. à la carte pour sauvegarde en EPROM (ou EEPROM) Lorsque la carte désire signer un message m, le protocole suivant est utilisé UTLLISA TION D U COUPON POUR SIGNER UN MESSAGE O ) La carte:: O Extrait J, x, i et r. de l'EPROM (ou EEPROM) O Calcule I = SHA(x, J, i) et A = xSHA(ri) ) mod q O Incrémente i et envoie r. au terminal (2) Le terminal génère un aléa a, I'expédie à la carte et déclenche un chronomètre t # La carte calcule, aussi vite que possible, s= J(SHA(m,a) + A) modq et retourne cette valeur au terminal # Dès réception de s, le terminal arrête t et calcule : # Le terminal accepte la signature si v=ri et si t est raisonnablement petit (par exemple t 1 T2e 1.000.000 Dans le cadre général du système de paiement proposé, le chargement à distance et l'utilisation des coupons en tant que chèque électronique est réalisé en échangeant entre la carte, l'autorité et le terminal-vérifieur au moins les signaux SuivantS CHARGEMENT DE,i COUPONS DANS LA CARTE # La carte remet à zéro un compteur i en EPROM (ou EEPROM), génère un aléa J de 10 à 20 octets, I'enregistre en EPROM (ou EEPROM) et l'envoie à l'autorité qui calcule, pour I allant de I à n . L'autorité envoie les nombres r. à la carte pour sauvegarde en EPROM (ou EEPROM) Lorsque le titulaire de la carte désire effectuer un paiement, le protocole suivant est utilisé UTILISA TION DU COUPON COMME CHEQUE ELECTRONIQUE O La carte: O Extrait J, x, i et r. de l'EPROM (ou EEPROM) O Calcule I = SHA(x, J, i) et A = xSHA(ri) ) mod q # envoie r. et i au terminal et incrémente i O Le terminal génère un aléa a, I'expédie à la carte et déclenche un chronomètre t # La carte calcule, aussi vite que possible, s = I(SHA(m,i,a) + A) mod q et retourne cette valeur au terminal # Dès réception de s, le terminal arrête t et calcule: : Os Le terminal accepte la signature si v = r. et si t est raisonnablement petit (par exemple t 1 T2e 1.000.000 Le Le terminal transmet (de façon différée) à l'autorité le cheque électronique O7 L'autorité s'assure que s=SHA(x,J,i)(SHA(m,i,a)+xSHA(ri))mod q et crédite le compte du terminal du montant de la transaction signé par la carte. Pour de nombreux objets portables tels que les cartes PCMCIA, les notebooks, ou encore dans le cadre des applications autour des autoroutes de l'information, le temps de transmission des données est négligeable en regard de celui consacré au calcul d'une exponentiation modulaire. De ce fait, l'invention proposée offre d'intéressantes possibilités de gain de performances que l'état actuel de l'art ne permet pas. A titre d'exemple, t est compris entre 200 ms et 1 s. Le défi a a une longueur de l'ordre de 10 octets. Un coupon ri a une longueur de l'ordre de 2 à 4 octets. REVENDICATIONS 1. Procédé de génération de signatures numériques de messages envoyés par un dispositif vérifieur à un dispositif prouveur comportant des moyens de calcul de communication et de rétention de données comprenant au moins une mémoire non volatile programmable électriquement selon lequel on prépare des données chiffrées constituant des coupons (ri) de signatures que l'on charge dans la mémoire non volatile et que le dispositif prouveur utilise pour signer des messages envoyés par le dispositif vérifieur, principalement caractérisé en ce que: les coupons sont compressés par l'application d'une fonction de compression dite encore fonction de hachage par une autorité certifiée avant d'être chargés dans la mémoire, et en ce qu'il comporte les échanges suivants:: le vérifieur et le prouveur conviennent d'un message m, le prouveur envoie un coupon ri au vérifieur, le vérifieur envoie un nombre aléatoire au prouveur et déclenche un chronomètre, le prouveur calcule la signature s du message et l'envoie au vérifieur, le vérifieur arrête le chronomètre et vérifie que la signature a été obtenue par le secret détenu par la carte et le coupon ri reçu à partir de la relation suivante: v = f(ri,s) = ri, le vérifieur accepte la signature si la condition de vérification v = ri est remplie et si le temps chronométré t ne dépasse pas une durée prédéterminée impartie. 2. Procédé de génération de signatures selon la revendication 1, caractérisé en ce que la fonction de compression utilisée pour obtenir les coupons et la fonction f utilisée pour la vérification de la signature sont les mêmes. 3. Procédé de génération de signatures selon la revendication 1 ou 2 dans lequel le vérifieur est un terminal et dans lequel le prouveur est une carte à microprocesseur, caractérisé en ce que l'obtention des coupons par l'autorité certifiée comporte les échanges suivants: O La carte remet à zéro un compteur i en EPROM (ou EEPROM), génère un aléa J de 10 à 20 octets, I'enregistre en EPROM (ou EEPROM) et l'envoie à l'autorité qui calcule, pour i allant de I à n: L'autorité envoie les coupons r. à la carte pour sauvegarde en (E)EPROM. 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la carte signe interactivement le message m en effectuant au moins les opérations suivantes O La carte O Extrait .1, x, r et r de l'EPROM (ou EEPROM) O Calcule I = SHA(x, J, i) et A = xSHA(ri, ) mod q O Incrémente Z et envoie ri au terminal # Le terminal génère un aléa a, I'expédie à la carte et déclenche un chronomètre t La carte calcule, aussi vite que possible, s=I(SHA(m,a)+A)mod q et retourne cette valeur au terminal # Dès réception de s, le terminal arrête t et calcule Os Le terminal accepte la signature si v = r et si t est raisonnablement petit. 5. Procédé, comme décrit dans les revendications 1 à 4, caractérisé en ce que la taille e d'un coupon est telle que: 16 bits 6. Procédé selon la revendication 1 ou 2, caractérisé en ce que le protocole interactif d'authentification est un algorithme permettant le pré calcul de coupons tel que l'algorithme DSA ou autre et en ce que O La carte: O Ex-trait J, x, i et r. de l'EPROM (ou EEPROM) O Calcule I = SHA(x, J, i) et A = xSHA(ri ) mod q O envoie r. et i au terminal et incrémente i # Le terminal génère un aléa a, I'expédie à la carte et déclenche un chronomètre t d) La carte calcule, aussi vite que possible, s = I(SHA(m,i,a) + A) mod q et retourne cette valeur au terminal O Dès réception de s, le terminal arrête t et calcule Os Le terminal accepte la signature si v = r- et si t est raisonnablement petit. Le Le terminal transmet (de façon différée) à i'autorité le cheque électronique O7 L'autorité s'assure que s = SHA( x, J, i)(SHA(m i a) + xSHA(ri )) mod q et crédite le compte du terminal du montant de la transaction signé par la carte. 7. Système permettant de mettre en oeuvre le procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les dispositifs prouveurs Ai sont des cartes à microprocesseur, des cartes PCMCIA, des badges, des cartes sans contact ou tout autre appareil portable. 8. Système selon la revendication 7, caractérisé en ce que la communication entre chaque appareil Ai, et/ou l'autorité certifiée B et/ou le vérifieur de la signature est réalisée par un échange de signaux électroniques. 9. Système selon la revendication 7, caractérisé en ce que la communication entre chaque appareil Ai, et/ou l'autorité certifiée B et/ou le vérifieur de la signature est réalisée par un échange d'ondes radio ou de signaux infrarouges.