FR 2713420 A1 19950609 FR 9314466 A 19931202 PROCEDE DE GENERA TION DE SICNA TURES DSA AVEC DES APPAREILS PORTABLES A BAS COUTS La présente Invention concerne un procédé permettant de faciliter la génération de signatures numériques de type DSA (Digital Signature Algorithm. proposé par le US National institut oj .Stal7dards and Technology (A Proposed Federal Information Processma Standard for Digital Signature Standard (DSS), Annoncé au Registre Féderal le 30 août 1991, pp 42980-42982) par des appareils portables notamment 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 a cause des limitations de la 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'existence de mémoires effaçables électriquement EEPROM) encouragent 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 (DSS) dans lequel on utilise l'algorithme connu sous l'abréviation DSA. Le Standard dc Signature Numérique (DSS, décrit dans la demande de brevet américain no. 07/738.43 1 intituiée "Digital Signature Algorithm") a été proposé par le U:S National Institute of Standards and Technology aI n 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 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. 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). 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 recevant un message signé, a ia 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 de l'algorithme DSA sont: O Un module premier p tel que 2 L-l (2) Un module premier q tel que 2 159 3 Un nombre g, d'ordre q modulo p tel que g = h (p-1)/q, ou h est un entier quelconque vérifiant l 1 C4 Un nombre 9. généré aléatoirement ou pseudo aléatoirement. O Un nombre y défini par la relation y = gx mod p. 8 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 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, sl par m + xr r = (g k mod p ) mod q et s = mod q k 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 k =2 car 3x2 = 6 -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: 1 w = i mod q s 2 u1 = m w mod q 3 u2 = r w mod q 4 v =( g ul yu2mod p )mod q O Et compare si v et r sont égaux afin d'accepter ou rejeter la signature. La présente invention s'applique à tout appareil portable comportant des moyens de calculs et des moyens de mémorisation, elle s'applique notamment à des cartes à puce avec microprocesseur. Elle s'applique par conséquent aux cartes répondant à la norme PCMCIA, aux cartes badge, aux cartes à lecture sans contact. 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 8051 ou 6805 par exemple. Afin d'atteindre ce but dans le cadre de l'implémentation de l'algorithme de Signature numérique DSA, I'invention proposée introduit le concept des coupons de signatures, c'est à dire un ensemble de certificats pré calculés et pouvant être fournis par un centre certifié (autorité) au cours d'une phase préliminaire de communication en ligne. l e principal avantage des coupons de signature en regard des propositions précédentes en matière de signature numériques réside dans la vitesse de calcul d'une signature de type DSA par une carte basée sur un simple micro contrôleur 8 bits (aux alentours de 300ms, temps de transmission compris) et le faible taux d'occupation mémoire du coupon (seulement 28 octets en EPROM ou EEPROM). La présente invention a plus particulièrement pour objet un procédé de génération de signatures numériques à partir d'appareils portables (A I .-A2,. Ai.. An) comportant des moyens de calculs, de communication et de rétention de données lesquels comprennent au moins une mémoire non volatile programmable électriquement. caractérisé en ce qu'il comporte les étapes suivantes: - préparation de données chiffrées constituant des coupons et chargement de ces coupons dans les mémoires non volatiles, - utilisation de ces coupons pour signer un message envoyé par un organe vérifieur. Selon un premier mode de réalisation, les coupons sont obtenus par une autorité centrale certifiée B ayant des moyens de calcul et établissant périodiquement des sessions individuelles avec les appareils Ai, par le biais d'une interface de communication commune, afin d'envoyer à chaque appareil les données chiffrées et pré calculées qui permettront à l'appareil de générer une signature numérique lors d'une session d'authentification mettant en oeuvre un protocole à clé publique. Afin de générer un coupon, I'autorité et la carte réalisent les actions suivantes: O L'autorité tire un nombre aléatoire J de Z1 octets ( en pratique Zl sera inférieur ou égal à 20 octets, on a choisi de manière préférée Zl=8) (2) L'autorité expanse J afin d'obtenir un nombre i de Z2 octets, Z2 étant supérieur ou égal à Z1 (on a choisi de manière préférée 72=20) 3 L'autorité calcule c = DES(clé~carte, J) 4 L'autorité calcule à rebours k = 1 mod q i o L'autorité calcule r = (g k mod p ) mod q 06 L'autorité envoie c et r à la carte O La carte calcule J = DES-1(clé~carte, c) X) La carte enregistre J and r en EPROM (ou EEPROM) Quand la carte désire signer un message m le protocole suivant est utilisé: O La carte extrait les valeurs J et r de l'EPROM (ou EEPROM) O La carte expanse J pour obtenir i sur Z2 octets O La carte reçoit le message m de la part du vérifieur. O La carte calcule s = (m + x r) i mod q. O La carte envoie s et r au vérifieur et invalide le couple (r, I} en l'effaçant de la mémoire (EEPROM). Selon une variante de réalisation la clef DES clé~carte peut-être une partie de x - Les coupons de signature se révèlent avantageux dans tous les cas ou une carte entre régulièrement en contact avec une autorité distante et certifiée afin de se ré-alimenter en coupons. - Etant donné que le nombre J ne sortira jamais en clair de la carte un procédé rudimentaire de chiffrement consistant en un simple ou exclusif de J avec une clé constante peut remplacer le DES. De façon plus générale, les coupons de signature peuvent être étendus à une grande variété de cryptosystèmes ou le pré calcul est possible (Schnorr, Guillou-Quisquater etc.) L'invention a pour second obiet de réduire le temps nécessaire pour la génération d'une signature DSA. Selon un autre mode de réalisation, on équipe l'appareil Ai (la carte) d'un opérateur cryptographique (par exemple, du type 83C852 Philips). Selon ce mode de réalisation, le calcul du terme r = (g k mod p ) mod q est repoussé au moment de la vérification ce qui permet de profiter du temps de travail du vérifieur. Dans ce protocole, la carte recalcule elle-même son coupon pendant la vérification O La carte extrait J et r de l'E PROM (ou EEPROM) O La carte expanse J pour obtenir i sur Z2 octets O La carte reçoit le message m de la part du vérifieur. O L'autorité calcule pour b = I à n Jb = nombre aléatoire de Z I octets ib = expanse(Jb) 4 La carte calcule s = (m + x r) i mod q. O La carte envoie s et r au vérifieur et invalide le couple Cr, J: en l'effaçant de l'EEPROM. 6 Pendant que le vérifieur vérifie la validité du couple tr. J', la carte tire dn nouveau nombre aléatoire J de Z 1 octets et l'expanse afin d'obtenir un nombre i de Z2 octets, calcule à rebours. k = 1/i mod q, calcule r = (g k mod p ) mod q et réécrit ie nouveau coupon {r, Jl en EEPROM. En pratique Zl=8 et Z2=20 L'invention a pour troisième objet de proposer un moyen de chargement rapide et simultané de n coupons par l'autorité kb = l/ib mod q Rb= I O L'autorité calcule Acc = g Pour a = 0 à 159 faire Pour b = I à n faire si kb[aj=l alors Rb=Rb Acc Mod q Acc = Acc2 mod p Pour b = I à n: couponb = I Rb mod q, Jbj O I autorité envoie les n coupons à la carte. La présente invention sera mieux comprise à l'aide de la description qui va suivre, qui est donnée à titre d'exemple non limitatif et en regard des dessins sur lesquels La figure I représente un schéma de principe des moyens de traitement et de mémorisation d'une carte pour la mise en oeuvre le système proposé par la présente invention. La figure 2 représente un schéma de principe des moyens de traitement et de mémorisation d'une autorité certifiée pour la mise en oeuvre le système proposé par la présente invention. La figure 3 représente les étapes mises en oeuvre dans la carte et par l'autorité et les échanges de données entre la carte à puce et l'autorité pendant la phase de chargement d'un coupon. La figure 4 décrit les données transmises entre la carte et le vérifieur au moment de l'utilisation du coupon La description qui va suivre va être donnée pour une carte à puce et on parlera dans toute la suite de carte étant bien entendu que l'invention s applique à tout appareil portable susceptible de communiquer avec un autre appareil dénommé autorité et/ou vérifier au moyen de signaux infrarouges ou radio. L'invention a, à titre d'exemple, pour application la signature de messages envoyés par un organe vérifieur V à une carte C en vue d'une authentification. Le vérifieur peut etre réalisé par un poste de travail type PC. Le vérifieur pourra selon un exemple de réalisation être relié par le réseau téléphonique (par exemple par le réseau téléphonique à intégration de services RNIS) à un ordinateur plus puissant tel qu'un VAX ou qu'une station SPARC, assurant les fonctions "d'autorité" détaillées dans la suite de la description. Selon l'invention proposée, chaque carte à puce représentée sur la figure l se compose d'une unité de traitement CPtJ 11, d'une interface de communication 10, d'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. L'interface de communication est classique en soi et adaptée au mode de transmission (signaux électroniques ou infrarouges ou ondes radio). Le CPU 11 et/ou la ROM 14 de la carte à puce contiennent des programmes existants sur le marché ou des ressources de calcul permettant de mettre en oeuvre la seconde partie du protocole DSS c'est à dire les règles de calcul pour la génération de s à partir de m x, r et l'inverse modulaire de k, et l'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 même que pour l'implémentation du DSA, la RAM contient le message M sur lequel s'applique la fonction de hachage SHS et les règles de calcul pour la génération de signatures DSS. L'E(E)PROM 15 contient les paramètres p, q, g, x et le jeu de coupons Cri ,Ji } généré et utilisé comme précisé dans la description qui suit. Selon une exemple de réalisation la carte dispose de moyen de déchiffrement par exemple un programme chargé en mémoire non volatile EEPROM permettant de mettre en oeuvre un algorithme tel que DES ou IDEA dont elle possède la clef secrète. Selon un autre exemple de réalisation, étant donné que le nombre J ne sort jamais en clair de la carte, on peut prévoir un chiffrement consistant à opérer un OU exclusif de J avec une clé constante (au lieu de chiffrer avec un algorithme DES). 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 mémoire 13, 14 and 15. Chaque carte à puce est protégée du monde extérieur par des protections physiques 17. Ces protections devraient être suffisantes pour empêcher toute entité non autorisée d'obtenir la clef 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 util isées. Selon l'invention proposée et comme cela est représenté sur la figure 2, I'autorité B se compose au minimum d'une unité de traitement (CPU) 30 et de ressources mémoires 32,33 et 34. On pourra utiliser par exemple un ordinateur tel qu'un VAX ou qu'une station SPARC, I'ordinateur étant relié à des points de vente par le réseau téléphonique. Le CPU 30 commande, via les bus d'adresse et de données 35, l'interface de communication 31, les opération de lecture et d'écriture mémoire 32, 33 and 34. Le CPU 30 et/ou la ROM 34 de l'autorité contiennent des programmes ou des ressources de calcul permettant d'implémenter l'ensemble du protocole DSS (règles de calcul et fonction de hachage SHS), multiplication, addition, inverse modulaire, 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). L'autorité dispose de moyen de chiffrement semblables à ceux de la carte dont elle possède la clef secrète. Il s'agira par conséquent d'un programme de mise en oeuvre de l'algorithme DES, si les cartes sont équipées de moyens de déchiffrement de cet algorithme. Dans le cadre général de l'invention proposée et comme on peut le voir sur les figures 3 et 4, le chargement à distance des coupons est réalisé en échangeant entre la carte, I'autorité et le vérifieur au moins les signaux suivants: Afin de charger un coupon à distance, I'autorité tire un nombre aléatoire de 8 octets J, I'expanse pour obtenir un nombre i de 20 octets, calcule c = DES(clé carte, J) et calcule à rebours k=l/i mod q. Par la suite, I'autorité calcule r = (g k mod p ) mod q. envoie c et r à la carte qui calcule alors J = DES-l(clécarte. c) et enregistre J et r dans l'E(E)PROM Quand la carte désire signer un message m, elle extrait J et r de l'E(E)PROM, expanse J pour obtenir un nombre i de 20 octets et calcule s = (m + x r) i mod q. Par la suite, la signature {r, s} est envoyée au vérifieur et le couple {r, J} est invalidé. Une autre variante de la présente invention a pour objet de réduire le temps nécessaire pour la génération d'une signature DSS avec une carte pourvue d'un opérateur cryptographique (par exemple, du type 83C852 Philips). Ce but est atteint en repoussant le calcul du terme r = (g k mod p ) mod q au moment de la vérification afin de pouvoir profiter du temps de travail du vérifieur. Dans ce protocole, la carte recalcule elle-même son coupon pendant la vérification O La carte extrait J et r de l'EPROM (ou EEPROM) (2) La carte expanse J pour obtenir i sur 20 octets O La carte reçoit le message m de la part du vérifieur. (E9 La carte calcule s = (m + x r) i mod q. O La carte envoie s et r au vérifieur et invalide le couple {r, J; en l'effaçant de l'EEPROM. ' > Pendant que le vérifieur vérifie la validité du couple {r, J}, la carte tire un nouveau nombre aléatoire J de 8 octets afin d'obtenir un nombre i de 20 octets, calcule à rebours k=l /i mod q, calcule r = (g k mod p ) mod q et réécrit le nouveau coupon t r, J ' en EEPROM L'invention consiste également à réaliser un chargement rapide et simultané de n coupons par l'autorité O L'autorité calcule pour b = 1 à n : Jb = nombre aléatoire de 8 octets ib = expanse(Jb) kb = I/ib mod q Rb = 1 Q2 L'autorité calcule Acc = , g Pour a = 0 à 159 faire Pour b = I à n faire si kb[a]=l alors Rb=Rb Acc Mod q Acc = Acc2 mod p Pourb=1 à n :couponb = {Rb mod q, Jb} O L'autorité envoie les n coupons à la carte. Pour de nombreux objets portables tels que les cartes PCMCIA, les notebooks, ou encore dans le cadre des applications autour des lignes de transmission à très haut débit super data highways), le temps de transmission des données est négligeable en regard de celui consacré au calcul d'une exponentiation modulaire. De ce fait. I'invention proposée offre d'intéressantes possibilités de gain de performances que l'état actuel de l'art ne permet pas. REVENDICATIONS 1. Procédé de génération de signature numériques à partir d'appareils portables (A I ,A2,.. .AI. .An) comportant des moyens de calculs, de communication et de rétention de données comprenant au moins une mémoire non volatile programmable électriquement, caractérisé en ce qu'il comporte les étapes suivantes: - préparation de données chiffrées constituant des coupons et chargement de ces coupons dans les mémoires non volatiles, - utilisation de ces coupons pour signer un message envoyé par un organe vérifieur. 2. Procédé selon la revendication 1, dans lequel, la préparation des coupons est réalisée par une autorité centrale certifiée B ayant des moyens de calcul et établissant périodiquement des sessions individuelles avec les appareils Ai, par le biais d'une interface de communication commune, afin d'envoyer à chaque appareil les données chiffrées et pré calculées qui permettront à l'appareil de générer une signature numérique ou de participer à une session d'authentification mettant en oeuvre un protocole à clé publique. 3. Procédé selon la revendication 1, caractérisé en ce que le protocole à clé publique est réalisé par l'algorithme de signature numérique DSA et en ce que l'échange de données entre un appareil Ai et l'autorité certifiée B comporte au moins les étapes suivantes. - B tire un aléa J de Z I octets. I'expanse en un nombre de Z2 octets i. - calcule c = DES(clé~carte J) calcule k= I!i mod q r=(gkmodp )modqet, - envoie c et r à la carte qui calcule J = DES1(clé~carte c) el sauvegarde J et r en mémoire non volatile (EEPROM). 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que l'opération de chargement de J et r en mémoire (EEPROM) est répétée t fois afin d'aboutir à la sauvegarde de t couples différents {J, r} dans cette mémoire. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le paramètre clé~carte est dérivé directement de x. la clé secrète DSA étant détenue par l'appareil. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'algorithme DES utilisé dans le calcul de c est remplace par tout autre algorithme de chiffrement à clé secrète et en particulier par un ou exclusif avec une constante secrète. 7. Procédé selon l'une quelconque des revendications précédente, caractérisé en ce que l'appareil Ai génère une signature DSA d'un message m envoyé par un vérifieur en effèctuant au moins les opérations suivantes a. Extraire J et r de la mémoire (EEPROM) b. Expanser J en un nombre i de Z2 octets c. Calculer s = (m+x r) i mod q d. Envoyer s et r au vérifieur e. Invalider le couple tJ r' en l'effaçant de la mémoire (EEPROM) 8. Procédé selon la revendication i. caractérisé en ce qu'il consiste à réaliser un chargement rapide e! simultané de n coupons par l'autorité comportant les étapes suivantes: a. L'autorité calcule pour b î 1 à n Jb = nombre aléatoire de Z I octets ib = expanse(Jb) kb=l/ib mod q Rb=l b. L'autorité calcule: Acc = g Pour a = 0 à 159 faire Pour b = I à n faire si kb[a]=l alors Rb=Rb Acc Mod q Acc = Acc2 mod p } Pour b = àn : couponb = { Rb mod q, Jb} c. L'autorité envoie les n coupons aux appareils 9. Procédé selon la revendication 1, caractérisé en ce que la préparation des données chiffrées constituant les coupons est réalisée par l'appareil Ai ce qui permet de réduire le temps de génération d'une signature DSA, I'appareil comportant pour cela un opérateur cryptographique apte à calculer r le coupon r J pendant le temps de travail du vérifieur, ce calcul étant repoussé au moment de la vérification 10. Procédé selon la revendication I ou 8, caractérisé en ce que l'appareil extrait J et r de la mémoire (EEPROM), expanse J pour obtenir i sur Z2 octets reçoit le message m de la part du vérifieur, calcule s = (m + x r) i mod q, envoie s et r au vérifieur et invalide le couple {r, J} en l'effaçant de l'EEPROM pendant que le vérifieur vérifie la validité du couple {r, Jf, la carte tire un nouveau nombre aléatoire J de Zi octets et lexpanse afin d'obtenir un nombre i de Z2 octets, calcule à rebours k=l/i mod q, calcule r=(g k mod p )mod q et réécrit le nouveau coupon (r, J} en mémoire (EEPROM). il .Procédé selon l'une quelconque des revendications I à 10 où les appareils :Ai) sont des cartes à puce, des cartes PCMCIA, des badges, des cartes sans contact ou tout autre appareil portable. 12. Procédé selon l'une quelconque des revendications I à 11, où 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. 13. Procédé selon l'une quelconque des revendications I à 12, où la communication entre chaque appareil Ai, etiou 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. 14. Procédé selon l'une quelconque des revendications suivantes ou Zl=8 et Z2=20