Brevet FR2775399A1 — publié le 19990827

PROCEDE DE SIGNATURE NUMERIQUE BORGNE DESCRIPTION Domaine technique La présente invention a pour objet un procédé de signature numérique. Ce procédé comprend, d'une part, une opération de retrait et d'autre part, une opération de présentation de la signature. L'invention trouve une application notamment dans le paiement électronique. Etat de la technique antérieure Un concept particulier de signature numérique, dit signature aveugle, a été introduit par D. CHAUM dans un article intitulé "Blind Signatures for Untraceable Payments" publié dans "Proceedings of CRYPTO'82, Plenum Press, 1983, pp. 199-203. Un protocole de signature aveugle est un protocole cryptographique mettant en jeu deux entités, un "utilisateur" et un "émetteur", l'utilisateur faisant signer un message à l'émetteur, de telle manière que ce dernier n'obtienne aucune information sur le contenu du message qu'il signe. De plus, après avoir signé plusieurs messages, l'émetteur est incapable, à la vue d'une signature qu'il a contribué à créer, de déterminer lors de quelle exécution du protocole cette signature a été obtenue. Les protocoles de signature aveugle sont utilisés dans des applications nécessitant l'anonymat, telles que les élections électroniques ou la monnaie électronique. Dans les systèmes de paiement électronique anonyme, l'expression "pièce électronique" désigne une donnée signée numériquement par la banque (l'émetteur de monnaie électronique) . La fonction de signature utilisée par la banque détermine la valeur faciale de la pièce. Lors d'une phase dite de "retrait", l'utilisateur (le client) achète ces pièces électroniques. Pour garantir l'anonymat, les pièces retirées par l'utilisateur doivent être inconnues de la banque. A cette fin, cette dernière signe de manière aveugle des données que l'utilisateur crée de manière secrète. L'utilisateur se trouve ainsi en possession de pièces valides que la banque elle-même est incapable d'associer à l'utilisateur qui les a retirées. L'anonymat est parfait. Le paiement correspond ensuite à un transfert de pièces électroniques du client au commerçant. Ce dernier contacte alors la banque (cas du paiement en ligne), laquelle conserve, dans sa base de données, toutes les pièces non expirées qui ont déjà été dépensées, pour s'assurer que les pièces qui lui sont présentées n'ont pas déjà été dépensées lors d'une transaction antérieure. Les commerçants déposent ensuite à la banque, lors de la phase dite de "remise", les pièces qu'ils ont reçues en paiement, pour compensation de leur valeur. Divers modes de mise en oeuvre d'une signature aveugle ont été développés et décrits. On peut en trouver des exemples notamment dans l'article de D. CHAUM et T.P. PEDERSEN, intitulé "Wallet Databases with Observers", publié dans Proceedings of Crypto'92, Lecture Notes in Computer Science, vol. 740, Springer Verlag, pp. 89-105, ainsi que dans l'article de T. OKAMOTO, intitulé "Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes", publié dans Proceedings of Crypto'92, Lecture Notes in Computer Science, vol. 740, Springer Verlag, pp. 31-53. Le protocole d'authentification de Schnorr, dont dérivent les protocoles de signature aveugle utilisés dans les articles ci-dessus, est lui-même décrit dans l'article de C.P. SCHNORR, intitulé "Efficient Signature Generation by Smart Cards", publié dans Journal of Cryptology, 4(3) 1991, pp. 161-164. Dans le protocole d'authentification de SCHNORR, et dans les schémas de signature aveugle qui en dérivent, l'émetteur E choisit au hasard une clef secrète SE, calcule une clef publique p=gSF, où g est un élément générateur connu de tous. Puis l'entité E publie sa clef publique P de façon que chacun la connaisse comme étant associée à l'identité de E. La clef publique P ne permet pas de retrouver la clef secrète SE que seul E connaît. En effet, la fonction exponentielle , qui permet de passer de SE à P, est difficilement inversible (la taille des paramètres est choisie de façon que le temps nécessaire pour retrouver SE à partir de P soit trop long pour les ordinateurs disponibles à l'époque de la mise en oeuvre du protocole). Dans le schéma d'authentification de SCHNORR, l'entité E prouve à une entité utilisatrice U qu'elle connaît la clef secrète SE sans toutefois révéler celleci. Cette preuve constitue pour E un moyen de s'authentifier auprès de l'utilisateur U. Ce protocole d'authentification comprend une première opération où l'émetteur choisit au hasard un nombre x dans le groupe Zq, c'est-à-dire dans le corps des entiers modulo q où q est un nombre premier (autrement dit x est compris entre 1 et q-l ) et élève son générateur g à la puissance x pour constituer un nombre t qui va lancer le protocole d'authentification. Ce nombre t est transmis à l'utilisateur qui poursuit le protocole en choisissant au hasard un nombre c dans Zq et en le transmettant à l'émetteur, qui calcule alors une réponse appropriée en utilisant sa clef secrète SE que lui seul connaît. Cette clef n'est évidemment pas transmise en l'état mais masquée par le nombre x que l'émetteur seul connaît. La réponse est alors y = x - cSE . L'utilisateur traite cette réponse en calculant, gy qui n est autre que g(x-cSE), soit gxg-cSE. L'utilisateur peut calculer aussi Pc, soit gCsE t de sorte que le produit gYpc est égal à gXgCSF gCSF , c'est-à-dire finalement t. La vérification de l'égalité entre t et gYPc prouve à l'utilisateur que l'émetteur connaît bien la clef secrète SE. Par ailleurs, cette preuve est apportée sans que la clef SE ait été révélée à l'utilisateur. Le protocole peut donc se répéter autant de fois que l'on veut, à condition de changer le nombre x à chaque fois. On peut illustrer un tel protocole par un tableau, (représentation qui sera utilisée constamment dans la suite de la description) dans lequel la notation Zq désigne le corps des entiers modulo q, les flèches horizontales symbolisent la transmission de nombre(s) d'une entité à l'autre, une équation avec un point d'interrogation au-dessus du signe égal (=) signifie que l'entité vérifie que les deux membres de l'égalité sont bien égaux. Avec ces conventions, le protocole d'authentification qui vient d'être décrit, peut être représenté par le Tableau I ci-après. E U clefsecrète SE clef publique : p = gsE choisit x dans Zq calcule t = gx choisit c dans Zq c y=x-cSE y (=gYpC Tableau I Ce protocole constitue une preuve de connaissance par l'émetteur de la clef secrète. On peut lier cette preuve à un message m, de façon à ce que ce protocole constitue en même temps une signature C du message m. En toute rigueur, l'émetteur E ne mériterait pas vraiment le nom de "signataire", car il ne peut être tenu pour responsable du message signé m puisqu'il l'ignore. C'est néanmoins la terminologie usuelle. Un schéma de signature aveugle de ce type peut être illustré par le Tableau II avec les mêmes conventions, où m est le message à signer. Dans ce schéma, l'utilisateur choisit en outre au hasard deux nombres u et v dans Zq, et calcule un nombre t à partir du nombre t qu'il a reçu de l'émetteur, du générateur g de l'émetteur qui est connu de tous et de la clef publique P de ce même émetteur et en utilisant les nombres u et v comme exposants, soit t=tg'P~. L'utilisateur choisit ensuite un nombre c, dit challenge, compris dans Zq et masque ce challenge en lui soustrayant le nombre u connu de lui seul pour obtenir un challenge masqué c=c-u. L'utilisateur transmet le challenge masqué c à l'émetteur. E U clef secrète : SE message : m clefpublique P = gSF choisit x dans Zq calcule î = gx choisit u, v dans Zq calcule t = rg'P" calcule c=H(t, m) calcule c = c ê calcule y = x M > calcule y = y + v t=gyPc obtient la signature G(y, c, m) Tableau II Dans ce protocole, H est une fonction de hachage (ou de condensation) connue de tous. La signature a finalement obtenue est constituée par l'ensemble des nombres y, c et m. Une telle signature ne peut être reconnue par l'émetteur qui ne peut calculer ni y, ni c, puisqu'il ignore les paramètres de masquage Lt et v et ne peut reconnaître le message m, qu'il n'a jamais vu. Les applications de la signature aveugle sont assez limitées, sauf à lui associer d'autres protocoles. Le but de la présente invention est justement de remédier à cet inconvénient pour élargir le champ d'application de tels protocoles. Exposé de l'invention A cette fin, l'invention propose un procédé dans lequel l'émetteur prend connaissance d'une partie du message à signer. Sa cécité n'est donc plus totale mais partielle. On dira que le signataire, et par extension la signature, est "borgne". De façon plus précise, la présente invention a pour objet un procédé de retrait de signature numérique dans lequel une entité dite "émetteur" (E) échange avec une entité dite "utilisateur" (U) des informations selon un protocole permettant à l'utilisateur d'obtenir une signature (o) d'un message (u) à l'élaboration de laquelle l'émetteur a collaboré mais sans que ce dernier puisse la retrouver à partir des éléments connus de lui lors de ces échanges ni la lier, lorsqu'elle lui est présentée a posteriori, au retrait dont elle provient si l'émetteur a émis plusieurs signatures, ce procédé étant caractérisé par le fait que l'utilisateur ne communique à l'émetteur qu'une partie (M) du message à signer, partie que ce dernier incorpore dans des éléments d'information nécessaires à l'élaboration de la signature, qui une fois produite ne peut être vérifiée qu'à l'aide du message (p) entier, dont la partie (M) qui a été vue par l'émetteur. L'invention a également pour objet un procédé de présentation d'une signature borgne obtenue par le procédé qui vient d'être défini, à une entité tierce dite "tiers" qui vérifie cette signature. Exposé détaillé de modes particuliers de réalisation Dans tous ce qui suit on se placera dans un groupe Gq cyclique d'ordre q, où q est un entier premier, et dans lequel la détermination du logarithme est un problème difficile : trouver x, s'il existe, tel que ax=b est difficile. Un exemple de retrait de signature borgne conforme à l'invention va d'abord être décrit. Il s'apparente au schéma de signature aveugle exposé plus haut (Tableau II). Mais selon l'invention, le message à signer comprend deux parties, une premier partie M qui sera rendue visible à l'émetteur et une seconde partie m qui restera invisible (ou masquée) pour celui-ci. Dans l'exemple décrit, l'émetteur E possède une clef secrète SE et deux clefs publiques Pl, P2 associées à cette même clef secrète par deux nombres générateurs giet g2 ; on a donc : Pi = g1SE P2 = g2SE A la différence du schéma de signature aveugle décrit plus haut (Tableau II), l'utilisateur transmet à l'émetteur, au début du procédé, la partie visible M du message et l'émetteur insère cette partie du message dans ses paramètres, par exemple en calculant un nombre générateur gM défini à partir des générateurs gi et g2 par g,9t = g1 g2. C'est ce nombre g qui servira alors à calculer le nombre î et non plus le nombre g comme dans le tableau II. En tirant encore un nombre x au hasard, l'émetteur calculera g;t, et non plus gr La suite des opérations restera sensiblement la même, à cette différence que l'utilisateur devra reconstituer le nombre t en tenant compte de la particularité de tM (et non plus de t) . Les opérations détaillées sont alors celles du tableau III. E U message ,u . clefsecrète . SE partie visible : M clefs publiques . P1, P2 partie invisible : m générateurs : g1, g2 P1 = g1SE , P2 = g2SE M calcule g,W, = g, g2 choisit x dans Zq calcule 1M = tM calcule PM = P,A'P, choisit u, v dans Zq calcule t," = t^Mg,tl Pgu calcule C'H(ln M, m) calcule c = c c calcule y = x- cS,. y calcule y = y + v tM = gMyPMc obtient la signature e(y, c, M, m) Tableau III La signature obtenue est formée des deux nombres y et c, connus du seul utilisateur, et du message u=(M, m), dont la première partie seule, M, est connue de l'émetteur. L'exploitation de cette signature s'effectue par un protocole de présentation auprès d'une troisième entité dit "Tiers" et notée T. Ce tiers calcule d'abord le produit gYsPM, autrement dit (glMg2)(PIMP2) Ce calcul est possible puisque le tiers reçoit y, c et M par la signature et qu'il connaît les clefs publiques PI, P2 ainsi que les générateurs gl, g2 de l'émetteur. Ce produit, qui n'est autre que le nombre tM calculé par l'utilisateur lors du retrait de la signature, permet au tiers de reformer la fonction H(tM, M, m) et de vérifier si le résultat est bien le nombre c contenu dans la signature. Ce protocole de présentation est illustré par le tableau IV suivant U T G(y, C, M, m) (y, c, M, m) tu gMP.U c=H(t, M, m) Tableau IV Le procédé qui vient d'être décrit peut s'appliquer au paiement électronique. Dans le cas d'un système de paiement, l'émetteur émet des signatures représentant des pièces électroniques. Les utilisateurs les emploient pour payer auprès des commerçants, lesquels jouent le rôle de tiers vérificateurs. La présentation de la pièce électronique peut donc s'assimiler à un paiement. Ces pièces doivent pouvoir être utilisées de façon anonyme, comme la monnaie fiduciaire classique, ce qui impose l'utilisation de signatures aveugles. Avec une signature borgne conforme à l'invention, la partie visible (M) du message peut contenir diverses informations, comme un montant maximal, les dates d'émission et d'expiration de la pièce, un nombre maximal d'utilisations autorisées. La partie invisible m peut contenir des données relatives au paiement, notamment l'identité du tiers (T), la date et l'heure, la référence du bien acheté. Pour remédier au problème de rendu de monnaie, une solution possible est d'émettre des pièces de montant faible, ou même correspondant à la granularité de la monnaie (par exemple, des pièces de 1 centime exclusivement). Cependant, cette solution obligerait à émettre des quantités importantes de pièces. Une autre solution consiste à émettre des pièces utilisables plusieurs fois, et constituées d'une signature borgne. La partie visible M du message peut alors contenir le nombre maximal d'utilisations autorisé et le montant maximal autorisé pour l'ensemble de ces utilisations. Le procédé de signature borgne qui vient d'être décrit peut être combiné avec tout procédé de signature "juste" dans lequel des traces du retrait et/ou de la présentation peuvent être insérées dans les protocoles afin, le cas échéant, pour pouvoir retrouver l'utilisateur d'une pièce donnée ou les pièces d'un utilisateur donne. En particulier, le procédé de signature borgne de l'invention peut être combiné à un procédé particulier de signature juste tel que celui qui est décrit et revendiqué dans la demande de brevet déposée le jour même du dépôt de la présente demande par le présent Demandeur, et intitulée "Procédé de signature numérique juste". REVENDICATIONS 1. Procédé de retrait de signature numérique, dans lequel une entité dite "émetteur" (E) échange avec une entité dite "utilisateur" (U) des informations selon un protocole permettant à l'utilisateur d'obtenir une signature (o) d'un message (p) à l'élaboration de laquelle l'émetteur a collaboré mais sans que ce dernier puisse la retrouver à partir des éléments connus de lui lors de ces échanges ni la lier, lorsqu'elle lui est présentée a posteriori, au retrait dont elle provient si l'émetteur a émis plusieurs signatures, ce procédé étant caractérisé par le fait que l'utilisateur ne communique à l'émetteur qu'une partie (M) du message (p) à signer, partie que ce dernier incorpore dans des éléments d'information nécessaires à l'élaboration de la signature, qui une fois produite ne peut être vérifiée qu'à l'aide du message (p) entier, dont la partie (M) qui a été vue par l'émetteur. 2. Procédé selon la revendication 1, dans lequel - l'émetteur (E) possède une première clef publique P1, un premier élément générateur public gi, et une clef secrète SE, avec p -g5 l'émetteur possédant encore une seconde clef publique P2 et un second élément générateur public g2, avec P2=g2't, les nombres P,, P2, gi et g2 étant connus de l'utilisateur (U), - pour incorporer la partie (M) du message (p) qui lui est communiquée dans des éléments d'information nécessaires à l'élaboration de la signature, l'émetteur calcule un élément gM défini par gAl = g1 g2 s - l'émetteur commençant ensuite le protocole de signature en choisissant au hasard un nombre entier x, en calculant un nombre tM égal à gM, et en transmettant ce nombre tM l'utilisateur. 3. Procédé selon la revendication 2, dans lequel l'utilisateur (U), ayant reçu le nombre t^M, calcule un nombre PM égal au produit P1MP2, choisit au hasard deux nombres entiers u et v, calcule un nombre tM défini par tM = tMgMvPMu, calcule un challenge (c) qui est une fonction de ce nombre tM et du message (p (M m)), soit c=H(t, M m) OÙ H est une fonction de hachage connue, puis calcule un challenge masqué (c) égal à c-u et transmet ce challenge masqué (c) à l'émetteur. 4. Procédé selon la revendication 3, dans lequel l'émetteur (E), pour calculer la réponse appropriée au challenge masqué reçu (c), calcule un nombre y égal à Y=X-CSE et transmet ce nombre y à l'utilisateur (U). 5. Procédé selon la revendication 4, dans lequel, l'utilisateur (U) traite la réponse reçue (y) en calculant un nombre y défini par y=y+v, calcule la quantité gMyPMc et vérifie que cette quantité calculée coïncide avec le nombre tM déjà calculé, la signature (a) du message pouvant être alors constituée par l'utilisateur en regroupant la réponse traitée y, le challenge c et le message (p=(Mm)) (#=(y, c, M, m)). 6. Procédé de présentation d'une signature obtenue selon la revendication 5, comprenant les opérations suivantes - l'utilisateur transmet la signature (o=(y c, M m)) à un tiers (T) - le tiers (T), à partir des nombres y,M et c pris dans la signature (a) ainsi que des nombres générateurs gj g2 et des clefs publiques P,, P2 de l'émetteur (E) calcule un nombre tM égal à (g1g2)Y.(P,ILp2)C, - à partir du nombre tM ainsi calculé et des première et seconde parties du message (M, m) prises dans la signature, le tiers (T) calcule la quantité H(tM. M m) et vérifie que cette quantité coïncide bien avec le challenge (c) pris dans la signature reçue. 7. Procédé selon la revendication 6, dans lequel la production d'une signature représente la création d'une pièce de monnaie électronique au profit de l'utilisateur (U) et la présentation de la signature représente un paiement électronique auprès du tiers (T). 8. Procédé selon la revendication 7, dans lequel la partie (M) du message transmise à l'émetteur peut contenir des informations comme un montant maximal, une date d'émission, une date d'expiration, un nombre maximal d'utilisations autorisées. 9. Procédé selon la revendication 7, dans lequel la partie (m) du message non transmise à l'émetteur contient des données relatives au paiement, notamment l'identité du tiers (T), la date et l'heure, la référence du bien acheté. 10. Procédé selon la revendication 1, dans lequel on insère dans la signature (a) une information permettant de retrouver la trace de son retrait auprès de l'émetteur (E). 11. Procédé selon la revendication 10, dans lequel le tiers (T) auquel la signature (o) est présentée inclut, dans la signature, une information permettant de retrouver la trace de la présentation de la signature.