FR 2817422 A1 20020531 FR 0015529 A 20001130 PROCEDE DE SIGNATURE ELECTRONIQUE A NIVEAUX MULTIPLES L'invention concerne un procédé de signature électronique d'un message par un dispositif mettant en oeuvre un algorithme de signature à clé publique, comprenant une clé secrète compatible avec une clé publique de vérification. L'invention concerne également un procédé de vérification correspondant. Le domaine de l'invention est celui. de la cryptographie et plus particulièrement celui de la sécurité de documents individuels à signature électronique produits en grande quantité sur des supports passifs bon marché, par exemple en papier : il s'agit notamment des cartes d'identité, des passeports, des permis de conduire, des cartes électorales, des cartes médicales, etc. Par la suite, on désignera ces documents par un terme générique : documents d'identité. Ils sont destinés à être vérifiés au moyen d'équipements déployés selon leur finalité dans divers endroits : postes de douane, postes de police, bureaux de vote, hôpitaux, Ces documents d'identité sont produits par une autorité délivrant la signature électronique selon un algorithme de signature à clé. Cette clé permet seule de produire la signature des documents d'identité, et est détenue par cette autorité. Cette autorité dispose d'un dispositif A mettant en oeuvre les étapes du procédé de signature. Si cette clé est volée, la falsification de tels documents devient possible. Une solution consiste à ce que la clé soit partagée entre n individus, parmi lesquels un quorum de k doit être atteint pour obtenir la signature. Mais cette solution n'est plus valable si la clé est obtenue par coercition exercée au moyen par exemple d'une prise d'otages contraignant les n individus à révéler la partie de la clé qu'ils détiennent. Dans le cas d'une prise d'otages, le criminel . vérifie que la clé de signature révélée est correcte en produisant lui-même des documents d'identité accompagnés de leur signature, et en utilisant la clé publique de l'autorité pour vérifier que les documents qu'il a lui-même produit sont valables. Ensuite, il relâche les otages, puis commence à produire des documents falsifiés, indiscernables des documents originaux. Actuellement, la seule solution pour l'autorité pour discerner les documents falsifiés des documents originaux, est alors de révoquer tous les documents d'identité qu'elle a produits jusqu'à la prise d'otage. A grande échelle, comme c'est le cas pour ces documents d'identité produits en grande quantité, cette solution est prohibitive, du fait du coût et des délais qu'elle implique. Le but de la présente invention est donc de permettre à l'autorité de distinguer les documents d'identité falsifiés des documents originaux, sans que le criminel puisse lui-même être capable de faire cette distinction. Ce but est atteint en faisant varier les critères de vérification de la signature. Cette nouvelle catégorie d'algorithmes de signature est appelée algorithmes de signature à niveaux multiples, ou aussi algorithmes de signature monotone. Grâce à cette solution, il suffit, lorsque la coercition cesse de s'exercer, de mettre à jour les équipements de vérification en publiant de nouveaux critères de vérification, ce qui est exceptionnellement acceptable, même à l'échelle d'un grand pays. . Le procédé de signature à niveaux multiples selon l'invention est dérivé du schéma classique de signature à clé publique. Par conséquent, il peut s'appliquer à tous les algorithmes de signature à clé publique tels que, en particulier, l'algorithme RSA du nom de ses auteurs (Rivest, Shamir et Adleman), l'algorithme d'El Gamal ou de Schnorr. Un schéma à clé publique comprend trois sousalgorithmes : un algorithme G de génération d'une clé publique de vérification v et d'une clé secrète s, un algorithme S de production de la signature, et un algorithme V de vérification. Selon un tel schéma à clé publique, une autorité signe au moyen d'un dispositif A mettant en oeuvre une clé secrète s, un document généralement appelé message m : S (s, m) = ci. Dans le cas des documents d'identité, le message m est constitué des informations portées sur le document, exception faite de la signature elle-même. Le document d'identité est finalement le document signé, c'est-à-dire constitué de m et cy. Pour s'assurer que le document signé émane bien de l'autorité, c'est-à-dire du dispositif A, la signature est vérifiée par un ou plusieurs vérificateurs du document au moyen de la clé publique de vérification v qui leur est fournie par le dispositif A : ils vérifient que V (v, m, cy) est vrai. On assimilera par la suite les vérificateurs aux équipements de vérification dont ils disposent. En cas d'attaque (prise d'otages,...), l'autorité se trouve contrainte de révéler au criminel sa clé t secrète. Celle-ci permet alors au criminel, qui par ailleurs s'est procuré la clé publique v, de fabriquer des documents d'identité pouvant obtenir un certificat de vérification valide avec la clé publique v (V (v, m, o) est vrai). Le criminel libère les otages. Un document d'identité comprend typiquement un message à signer m contenant notamment les caractéristiques du détenteur de ce document et une signature a. Selon l'invention la clé secrète est constituée de s et de clés secrètes partielles sj : on dénomme s' cette nouvelle clé secrète. s'= (s, sI,..., sj,..., sn). C'est une clé à niveaux multiples utilisée par le dispositif A pour produire des documents signés. La signature par le dispositif A au moyen de cette clé s', devient alors : S (s', m) = S (s, sl,..., sn, m) =' De même, la clé publique de vérification est constituée de v et de clés publiques partielles vj : on dénomme v'cette nouvelle clé publique. v'= (v, vl, vj,..., vn). Mais la clé publique fournie initialement et sans contrainte aux vérificateurs des messages est en fait v, les clés vl, v2,..., vn étant des clés de réserve secrètes détenues par le dispositif A, qui ne seront introduites dans la clé publique de vérification que si besoin est. De plus, quelle que soit la forme de la clé publique de vérification, la vérification des documents produits par le dispositif A avec la clé s'est positive. Les clés s'et v'sont telles que V (v, m, o') . est vrai. De même, V (v, vl, m, Lors de la première attaque coercitive, l'autorité révèle s. Cette première attaque est un cas particulier, du fait que l'autorité dévoile la clé s, qui est une donnée différente des si. Le criminel produit des documents d'identité, c'est-à-dire qu'il signe les messages m avec s : S (s, m) = ci. Puis, s'étant procuré la clé publique v, il vérifie que V (v, m, ci) est vrai, ce qui est le cas et cesse d'exercer sa contrainte : il libère les otages. L'autorité affine alors les critères de vérification en publiant à l'attention des vérificateurs autorisés, via le dispositif A, une nouvelle clé publique de vérification parmi les clés de réserve dont l'autorité dispose. Cette nouvelle clé de vérification sera par exemple : (v, vl). En appliquant l'algorithme de vérification V, les vérificateurs obtiennent alors que V (v, m, o) est vrai mais que V (v, vl, m, a) est faux. On rappelle que V (v, vl, m, ci') est vrai. Ainsi, les documents produits par le criminel peuvent être facilement discriminés à l'aide de ce nouveau critère vl, de ceux produits par l'autorité, qui, elle, utilise toutes les clés secrètes pour produire des documents signés. Lors d'une attaque ultérieure, l'autorité dévoile la clé secrète si par exemple. Le criminel produit des documents qu'il signera au moyen de la clé (s, si) : S (s, sl, m) = cri. Puis, s'étant par ailleurs procuré (v, vl), il vérifie que V (v, vl, m, al) est vrai ce qui est le cas. Il cesse alors d'exercer sa contrainte et libère les otages. L'autorité affine alors les critères de vérification en publiant à l'attention des vérificateurs autorisés, via le dispositif A, une nouvelle clé publique de vérification parmi les clés de réserve dont l'autorité dispose. Cette nouvelle clé de vérification sera par exemple : (v, vl, v2). En appliquant l'algorithme de vérification V, les vérificateurs obtiennent alors que V (v, vl, m, (JI) est vrai mais que V (v, vl, v2, m, al) est faux. Ainsi, les documents produits par le criminel peuvent être facilement discriminés à l'aide de ce nouveau critère v2, de ceux produits par le dispositif A. Le criminel peut bien sûr demander que toutes les clés secrètes lui soient révélées en une fois. Il se procure alors la clé publique de vérification correspondante. Dans ce cas l'autorité lui fournira plusieurs clés secrètes partielles, mais pas toutes car un autre avantage de l'invention est que le criminel ne peut discerner si les signatures produites par l'autorité ont été obtenues seulement avec les clés secrètes qui sont en sa possession, ou si des clés secrètes additionnelles ont été nécessaires. L'invention a pour objet un procédé de signature électronique d'un message m par un dispositif A mettant . en oeuvre un algorithme de signature utilisant un schéma de signature à clé publique comprenant une clé secrète s compatible avec une clé publique de vérification v, principalement caractérisé en ce qu'il consiste à : - générer et mémoriser une nouvelle clé secrète s' formée de s et de clés secrètes partielles sl,..., sj,..., sn, n étant un entier positif, - générer et mémoriser une nouvelle clé publique de vérification v'formée de v et de clés publiques de réserve vl,..., vj,..., vn, les clés secrètes (s, sI,..., sj) étant compatibles avec les clés publiques de vérification (v, vl,..., vj) et la clé secrète s'étant compatible avec n'importe quelle clé de vérification (v, vl,..., vj) j variant de 1 à n, - à signer le message m au moyen de la clé secrète s' pour obtenir une signature a'. Selon une caractéristique de l'invention, le procédé consiste en outre à fournir à un équipement de vérification du message m signé, au moins une clé publique de réserve. Un aléa r constitué d'éléments d'information peut être introduit dans le message m ou plus pécisément, concaténé au message m. Selon une autre caractéristique de l'invention, l'aléa est constitué d'éléments d'information aléatoires et d'éléments d'information non aléatoires, les éléments d'information non aléatoires étant chacun déterminés par une fonction fkj pseudo-aléatoire différente, j variant de 1 à n. Avantageusement, les éléments d'information de . l'aléa r sont des bits et l'aléa r est constitué d'une suite de bits. Selon une caractéristique additionnelle, kj = sj = vj. Selon une autre caractéristique, le procédé est appliqué à la phase d'initialisation et aux sousalgorithmes G de génération de clés et S de signature de l'algorithme de Schnorr-Okamoto. L'invention concerne également un procédé de vérification par un équipement de vérification d'un message signé de manière électronique, ledit équipement de vérification disposant au moins d'une clé publique v, caractérisé en ce que ledit équipement de vérification dispose en outre d'au moins une clé de réserve vj, et en ce qu'il applique la clé publique v et la ou les clés de réserve vj à tout ou partie du message signé et vérifie que la clé publique v et la ou les clés de réserve vj sont valides. Selon une caractéristique de l'invention, un aléa r étant introduit dans le message m, et l'ensemble (m, r) constitué du message et de l'aléa étant signé de manière électronique, le procédé consiste en ce que : - l'équipement de vérification applique la clé publique v à l'ensemble (m, r) ou une fonction de (m, r) et vérifie que la clé publique v est valide, - l'aléa r soit constitué d'une chaîne de bits rI... rj... rn, dont certains sont aléatoires, - l'équipement de vérification dispose des bits aléatoires de r, de rj et d'une famille de fonctions pseudo-aléatoires fed, et vérifie que fiv (bits aléatoires . de r) = rj. Selon une autre caractéristique de l'invention, un aléa r étant introduit dans le message m, l'ensemble (m, r) constitué du message et de l'aléa étant signé de manière électronique, ledit équipement de vérification disposant d'une fonction de hachage H, de m, et de la signature'de l'ensemble (m, r), le procédé consiste en ce que : - la clé publique v soit constituée d'un entier y et d'une suite d'entiers gui,..., gn - la signature soit de la forme o'= (h, u1, ..., un) avec h=H (m, r) - l'équipement de vérification dispose en outre d'un nombre premier p, et vérifie que la clé v est valide c'est-à-dire que H (m, glul x... x gnun X yh mod p) = h - l'équipement de vérification dispose en outre d'au moins une clé de réserve vj et de uj, et d'une famille de fonctions peudo-aléatoires fk, et vérifie que la clé de réserve vj est valide c'est-à-dire que uj = fvj (m, r). D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description suivante faite à titre d'exemple non limitatif. Dans la plupart des algorithmes à clé publique, un aléa r, constitué d'éléments d'informations au sens de la théorie de l'information (un élément d'information . est un ensemble de 1 à plusieurs bits, comme par exemple, un nombre entier, une matrice,...), est introduit dans le message m à signer. Une fonction de hachage est ensuite appliquée à l'ensemble (m, r) : H (m, r) = h. La signature intervient alors : cr = S (s, h). C'est ce qui est communément dénommé sous le nom de méthode hachage puis signature ("hash and sign paradigm", en anglais). Le vérificateur dispose de h, cr et d'une clé publique de vérification v, communiqués par le dispositif A : il vérifie que V (v, h, cv) est juste. Selon un premier mode de réalisation de l'invention, l'aléa r est une chaîne de bits (0 ou 1) apparemment aléatoires, introduite dans le message m, en l'occurrence concaténée à m. L'expression apparemment aléatoire signifie que r inclut de l'information qui a une signification pour qui sait l'interpréter. Cette chaîne r est en fait constituée de bits aléatoires et d'autres bits déterminés en fonction de ces bits aléatoires. On définit un ensemble E c ; {l,..., n} et un ensemble E'= {l,..., n}-E r = rI... rj... rw... rn avec : rj = 0 ou 1 aléatoires pour jeE rj = fkj (rw) pour les autres j, c'est-à-dire pour jeE', pour weE et où fkj est une famille de fonctions pseudo-aléatoires et kj une clé secrète ; kj est un nombre réel représenté sous forme binaire par exemple sur 128 bits. On va illustrer cette formulation de r par un exemple : en choisissant n=5, on a par exemple ri, r3 et r4 aléatoires et r2 et r5 déterminés par r2=fk2 (rl, r3, r4) et r5=fk5 (rl, r3, r4). Bien entendu, n est en réalité un entier beaucoup plus grand tel que par 128 exemple 2128. Le nombre de ces clés kj dépend donc du nombre de bits de r obtenus en appliquant ces fonctions pseudoaléatoires. Le terme pseudo-aléatoire désigne des fonctions qui produisent des bits indiscernables au sens de la complexité de bits purement aléatoires. Selon ce premier mode de réalisation, sj = kj = vj. Le dispositif A a mémorisé bien sûr la clé secrète s ainsi que toutes les clés secrètes partielles kj. Ce premier mode de réalisation présente des inconvénients : on remarque en effet que révéler une clé publique partielle kj revient à révéler en même temps la clé secrète partielle correspondante. Sachant cela, le criminel ayant déjà obtenu kj, pourra alors attendre la divulgation d'une nouvelle clé publique de vérification, par exemple k (j+l) et produire des documents signés au moyen de k (j+l). Il s'agit d'un cas d'attaque différée. De plus, dans la mesure où l'on souhaite pouvoir inscrire plusieurs signatures sur un document d'identité de dimensions nécessairement limitées, il est avantageux d'appliquer ce procédé de signature à . niveaux multiples à un algorithme de signature à clé publique particulier : celui de Schnorr-Okamoto, car les signatures selon cet algorithme sont très courtes. La variante d'Okamoto de la signature de Schnorr est présentée dans la publication Advances in cryptology CRYPTO'92, Springer-Verlag, LNCS 740, pp. 31-53, 1992 . On va détailler un second mode de réalisation qui est une variante de l'invention, et qui est basé sur l'algorithme de Schnorr-Okamoto. On débute par une phase d'initialisation qui consiste à choisir et mémoriser : - un grand nombre premier p (de 512 bits par exemple) tel que p-l= q x 1, q étant un grand nombre premier (par exemple de 160 bits) et 1 un entier positif, une fonction de hachage H s'appliquant dans l'ensemble des entiers modulo p, - et fk (. ) = H (k, .), une famille de fonctions aléatoires. Le sous-algorithme G de génération de clé consiste à : choisir et mémoriser n et une permutation P de {l, 2,..., n} telle que P (l) = PI, etc. On va illustrer une permutation de {1, 2,3, 4} (n=4) en choisissant la permutation 4,2, 1, 3 ; on définit alors P (1) =4, P (2) =2, P (3) = l et P (4) =3. Dans la réalité, n peut par exemple être égal à 20. - choisir et mémoriser i tel que i - choisir et mémoriser des nombres aléatoires kl,..., ki-i . - choisir et mémoriser des entiers xi,..., xn dans le groupe multiplicatif Zq* des entiers modulo q, - choisir et mémoriser des nombres entiers gp ;,..., gP (n) dans le groupe multiplicatif Zp* des entiers modulo p et tels que gp (m) q =1 pour m=i, ..., n - définir gp (j) = gp (i) mo P pour j = 1, ..., i-1 : on impose ainsi une relation entre les gp (1),..., gp (i-i ; xi - définir y tel que y = glXl x... x gn"mod p On obtient finalement comme : - clé publique v' : v constitué de y et des éléments {gp (j)} pour j=l,..., n et vj = kj pour j =1, ..., i-1 - clé secrète s' : s= (xi,..., xn) et sj= (ap(j)), kp(j)) pour j=l,..., i-1, On remarque que dans la mesure où les entiers al,..., ai-i sont secrets, les relations entre les gp (l),..., gp (i-i), correspondants le sont aussi. Ces clés publiques et secrètes sont mémorisées. Le sous-algorithme S de signature consiste à : - choisir et mémoriser des entiers ti,..., tn dans le groupe multiplicatif Zq* des entiers modulo q, - calculer et mémoriser l'aléa r=g1ti x... x gn tn mod p - calculer et mémoriser h = H (m, r) - calculer et mémoriser : pour j=l,..., i - 1 up (j) = fkj(m, r) pour j=i, Up (i) = ti-hxi-aiUp (1)- ... -a1-1 Up(#-1) mod q pour j=i+l,..., n up (j) = tj-hxj mod q poser et mémoriser #' = (h, ul,..., un) ; (on a S (s, si,..., s1-1, h) =o'). Le sous-algorithme V de vérification du message et de la signature'consiste à vérifier que H (m, g1 x. x gn x y mod p) = h et que les Uj sont valables pour les j communiqués par l'autorité A. Vérifier cette seconde condition revient à vérifier : Uj = fk[p-1 (j)] (m, r), P-1 (j) étant la fonction inverse de P (j), c'est-à-dire uj = fkj (m, r). Après la première attaque, l'autorité A révèle au criminel s= (xi,..., xn) et éventuellement certaines clés secrètes partielles sj c'est-à-dire certains éléments P (j), ap (j) et kp (,). Puis, après libération des otages, l'autorité ajoute un nouveau critère de vérification, en imposant une nouvelle relation entre les gp (l). Le dispositif A mettant en oeuvre un procédé de signature électronique tel que décrit comporte une unité principale de traitement, des mémoires de programmes et une mémoire de travail, associées à l'unité de traitement. Parmi les programmes mis en mémoire, on peut citer outre le programme correspondant au procédé de signature selon l'invention, un programme permettant d'effectuer les permutations P ainsi qu'un programme permettant d'appliquer une fonction de hachage H. Le dispositif comporte également un processeur arithmétique capable d'effectuer des calculs modulaires t et une mémoire sécurisée dans laquelle seront stockées la clé secrète s et les clés secrètes partielles sl, ..., sn, ainsi que la clé de vérification v et les clés de réserve vil,..., vn. Le dispositif possède également un générateur de fonctions pseudo-aléatoires. Un équipement de vérification comprend également une unité principale de traitement, des mémoires de programmes et une mémoire de travail, associées à l'unité de traitement. L'équipement de vérification comporte également un processeur arithmétique capable d'effectuer des calculs modulaires et une mémoire sécurisée dans laquelle seront stockées la clé de vérification v et les clés de réserve vj éventuelles, ainsi que tout autre élément secret dont il dispose. REVENDICATIONS 1. Procédé de signature électronique d'un message m par un dispositif A mettant en oeuvre un algorithme de signature utilisant un schéma de signature à clé publique comprenant une clé secrète s compatible avec une clé publique de vérification v, caractérisé en ce qu'il consiste à : - générer et mémoriser une nouvelle clé secrète s' formée de s et de clés secrètes partielles sl,..., sj,..., sn, n étant un entier positif, - générer et mémoriser une nouvelle clé publique de vérification v'formée de v et de clés publiques de réserve vl,..., vj,..., vn, les clés secrètes (s, spi,..., sj) étant compatibles avec les clés publiques de vérification (v, vl,..., vj) et la clé secrète s'étant compatible avec n'importe quelle clé de vérification (v, vl,..., vj) j variant de 1 à n, - à signer le message m au moyen de la clé secrète s' pour obtenir une signature'. 2. Procédé selon la revendication précédente, caractérisé en ce qu'il consiste en outre à fournir à un équipement de vérification du message m signé, au moins une clé publique de réserve. 3. Procédé selon l'une des revendications précédentes, caractérisé en ce qu'un aléa r constitué d'éléments d'information est introduit dans le message m. 4. Procédé selon la revendication précédente, caractérisé en ce que l'aléa r est concaténé au message m. 5. Procédé selon l'une des revendications 3 ou 4, caractérisé en ce que l'aléa est constitué d'éléments d'information aléatoires et d'éléments d'information . non aléatoires, les éléments d'information non aléatoires étant chacun déterminés par une fonction fkJ pseudo-aléatoire différente, j variant de 1 à n. 6. Procédé selon la revendication précédente, caractérisé en ce que les éléments d'information de l'aléa r sont des bits et en ce que l'aléa r est constitué d'une suite de bits. 7. Procédé selon l'une des revendications 5 ou 6, caractérisé en ce que kj = sj = vj. 8. Procédé selon l'une des revendications 1 à 4, caractérisé en ce qu'il est appliqué à la phase d'initialisation et aux sous-algorithmes G de génération de clés et S de signature de l'algorithme de Schnorr-Okamoto. 9. Procédé de vérification par un équipement de vérification d'un message signé de manière électronique, ledit équipement de vérification disposant au moins d'une clé publique v, caractérisé en ce que ledit équipement de vérification dispose en outre d'au moins une clé de réserve vj, et en ce qu'il applique la clé publique v et la ou les clés de réserve vj à tout ou partie du message signé et vérifie que la clé publique v et la ou les clés de réserve vj sont valides. 10. Procédé de vérification selon la revendication précédente, un aléa r étant introduit dans le message . m, et l'ensemble (m, r) constitué du message et de l'aléa étant signé de manière électronique, caractérisé en ce que : - l'équipement de vérification applique la clé publique v à l'ensemble (m, r) ou une fonction de (m, r) et vérifie que la clé publique v est valide, - l'aléa r est constitué d'une chaîne de bits rI... rj... rn, dont certains sont aléatoires, - l'équipement de vérification dispose des bits aléatoires de r, de rj et d'une famille de fonctions pseudo-aléatoires fkj, et vérifie que fvj (bits aléatoires de r) = rj. 11. Procédé de vérification selon la revendication 9, un aléa r étant introduit dans le message m, l'ensemble (m, r) constitué du message et de l'aléa étant signé de manière électronique, ledit équipement de vérification disposant d'une fonction de hachage H, de m, et de la signature'de l'ensemble (m, r) caractérisé en ce que : - la clé publique v est constituée d'un entier y et d'une suite d'entiers gai,..., gn - la signature est de la forme'= (h, ul,..., un) avec h=H (m, r) - l'équipement de vérification dispose en outre d'un nombre premier p, et vérifie que la clé v est valide c'est-à-dire que H (m, glul x... x gnun x yh mod p) = h - l'équipement de vérification dispose en outre d'au moins une clé de réserve vj et de uj, et d'une famille de fonctions peudo-aléatoires fk, et vérifie que . la clé de réserve vj est valide c'est-à-dire que uj = fiv, (m, r).