Brevet FR2729807A1 — publié le 19960726

La présente invention concerne un procédé de signature électronique numérique, basé sur une information d'identification certifiée automatiquement, et plus particulièrement l'application du concept de clé publique certifiée automatiquement à un procédé basé sur l'identification. Généralement, un traitement d'information, qui utilise un système informatique, dépend largement du développement de logiciels et de dispositifs à semi-conducteur. Une société informatisée, où toutes les affaires sont traitées par ordinateur avec le développement de techniques de traitement d'information et de techniques de communication d'information sophistiquées, est en train d'apparaître. Par conséquent, toutes les affaires sont réalisées conformément à la société informatisée. Une de celles-ci est une signature électronique numérique. La signature électronique numérique consiste à réaliser électroniquement une signature et une marque. I1 existe deux procédés pour éliminer le répertoire de clé publique des méthodes à clé publique conventionnelles, l'un d'eux étant le procédé basé sur l'identification et l'autre le procédé basé sur la certification. Dans le procédé basé sur la certification, un centre de confiance publie sa clé publique et donne à un utilisateur A sa signature S de la paire d'identité Id et de clé publique PK de A. L'utilisateur A adresse (IdA, PRIA, S) au vérificateur qui vérifie la validité de PK en vérifiant la signature S du centre de confiance pour (IdA, PKA) au lieu de retrouver PKA à travers IdA du répertoire de clés publiques. Cependant, dans le procédé basé sur l'identification, la clé publique est remplacée par la valeur indiquant l'identité de l'utilisateur. En général, la différence principale entre le procédé basé sur la certification et le procédé basé sur l'identification est la suivante 1) N'importe quel système à clé publique peut être converti dans la variante basée sur la certification par la même technique, tandis que chaque système à clé publique nécessite une technique particulière pour la conversion dans la variante basée sur l'identification. 2) Le centre de confiance du procédé basé sur la certifica tion ne connaît pas la clé secrète de chaque utilisateur, tandis que le centre de confiance du procédé basé sur l'identification engendre et connaît la clé secrète de chaque utilisateur. 3) La forme de la clé publique qu'un utilisateur garde et adresse au vérificateur dans le procédé basé sur la certification est plus longue que celle dans le procédé basé sur l'identification. M. Girault propose une méthode "paradoxale" basée sur l'identification. Cependant, comme sa méthode utilise le certificat, sa méthode n'est pas réellement une méthode basée sur l'identification. Aussi, M. Girault introduit la notion de clé publique certifiée automatiquement, qui est une méthode intermédiaire entre le procédé basé sur la certification et le procédé basé sur l'identification. Dans la méthode de clé publique certifiée automatiquement, le certificat est juste la clé publique, c'est-à-dire qu'il n'y a pas de certificat séparé. Et il a défini les niveaux de confiance comme suit - Niveau 1 Le centre de confiance connalt la clé secrète de l'utili sateur et, par conséquent, il peut se faire passer pour chaque utilisateur à tout moment sans être détecté. - Niveau 2 Le centre de confiance ne connalt pas la clé secrète de l'utilisateur. Cependant, le centre de confiance peut quand même se faire passer pour l'utilisateur en engen drant de faux certificats. - Niveau 3 Le centre de confiance ne connaît pas la clé secrète de l'utilisateur et il ne peut pas se faire passer pour l'utilisateur sans être détecté. On commence par une brève revue de terminologies et de résultats de la présente invention. Pour des nombres entiers positifs donnés y et n, un nombre entier z est un ye-résidu si gcd(z, n)=l et il existe un nombre entier x tel que ZEXY mod n, unye-non-résidu autrement. Le problème de ye-résidu (ye-RP) désigne le problème pour déterminer le ye-résidu de l'élément donné zszn, ou n est l'ensemble des entiers inférieurs à n entre 0 et n. Lorsque n est un nombre premier, le problème peut toujours être résolu. Cependant, pour un nombre entier composé donné n, dont la factorisation n'est pas connue, ce problème est considéré comme très difficile. Si y est 2, le problème est désigne problème de résidu quadratique, qui est appliqué à de nombreux protocoles codés. On désigne un triplet (n,y , y) comme acceptable si n, y et y satisfont aux trois conditions suivantes (i) n est le produit de puissances de différents nombres premiers impairs, c'est-à-dire n = nln2...nt, où chaque ni est une puissance d'un nombre premier impair. (ii) y est un nombre entier impair plus grand que 2 avec gcd(&gamma;, #(nl)) = 1 pour juste un 1 # 1 # t, et gcd(&gamma;, #(ni)) = 1 pour tous les i # 1, 1 # 1 # t. Dans un but de simplification, on supposera que 1=1. (iii) y est un élément de Zn*, vérifiant t y = h1bl&gamma;+e # hjbj mod n, j=2 où o chaque i # 1, 1 S j S t, et est un vecteur générateur pour Zn Si un triplet (n, y , y) est acceptable, il existe un unique i tel que z=yi x&gamma; mod n pour chaque z dans Zn*. On désigne i l'indicateur de classe de z par rapport au triplet acceptable (n,y , y). Il existe deux autres problèmes liés étroitement au ye-RP. Pour être complet, trois problèmes sont formellement définis comme suit * (1) ye-RP : n, y et un élément Zn étant donnés, décider si z est ou non un ye-résidu (mod n). (2) Un problème de comparaison d'indicateur de classe : un triplet acceptable (n, r, y) et deux éléments z1,z2#Zn* étant donnés, juger si zl et z2 présentent le même indicateur de classe par rapport à (n,y , y). (3) Un problème de recherche d'indicateur de classe : un triplet acceptable (n,y , y) et un élément Z#Zn* étant donnés, trouver l'indicateur de classe de z par rapport à (n,y , y). Zheng a prouvé que les définitions précédentes présentent les relations suivantes (a) ye-RP et le problème de comparaison d'indicateur de classe sont équivalents. (b) ye-RP et le problème de comparaison d'indicateur de classe peuvent être réduits au problème de recherche d'indicateur de classe. (c) ye-RP et le problème de comparaison d'indicateur de classe sont équivalents pour le problème de recherche d'indicateur de classe lorsque y=O(poly(k)), où poly(.) correspond à un polynôme. Et il considère que ye-RP avec un y important ne semble pas être applicable pour construire un codage de probabilité. M. Girault a introduit la notion de clé publique certifiée automatiquement, qui est une méthode intermédiaire entre le procédé basé sur la certification et le procédé basé sur l'identification. Dans les méthodes à clé publique, chaque utilisateur a une paire de clés (s, P). La première clé, s, est une clé secrète, connue uniquement par cet utilisateur. La seconde clé, P, est une clé publique, que tout le monde peut connaître. Par définition, des clés publiques ne doivent pas être protégées de façon confidentielle. Au contraire, elles doivent pouvoir être aussi accessibles que possible. Mais cette "publicité" les rend particulièrement vulnérables contre des attaques actives, comme par exemple la substitution d'une clé publique "fausse" à une clé publique "vraie" dans un répertoire. C'est pourquoi, en plus de la paire de clés (s, P) et de sa chaîne d'identification (ou identité) I, les attributs d'un utilisateur doivent également contenir un "certificat" G qui est réellement la clé publique de l'utilisateur I, et non celle d'un imposteur r'. Dans les procédés basés sur la certification, le certificat G prend la forme d'une signature numérique de la paire (s, P) calculée et délivrée par le centre de confiance. Dans un tel cas, les quatre attributs (I, s, P et G) sont distincts : trois sont publics (I, P et G) et doivent être disponibles dans un registre. Dans les procédés basés sur l'identification, la clé publique n'est rien d'autre que l'identité I (c'est-à-dire P=I). Et le certificat n'est rien d'autre que la clé secrète elle-même (c'est-à-dire G=s), de sorte qu'uniquement deux attributs existent (I et s) au lieu de quatre. Dans les procédés à clé publique certifiée automatiquement, le certificat est égal à la clé publique (c'est-à-dire G=P), qui de ce fait peut être désigné comme certifié automatiquement, et chaque utilisateur a trois attributs (I, s et P). Dans la présente invention, on propose un nouveau type de méthode, avec une information d'identification certifiée automatiquement, qui applique la notion de clé publique certifiée automatiquement au cas où la clé publique est uniquement l'information d'identification. Dans les méthodes proposées, le certificat, la clé publique et l'identité sont les mêmes (c'est-à-dire G=P=I), et chaque utilisateur a deux attributs (I et s), tel que dans les procédés basés sur l'identification. Et la différence essentielle entre le procédé basé sur l'identification et le procédé d'information d'identification certifiée automatiquement est le niveau de confiance. Ainsi, le procédé basé sur l'identification atteint le niveau 1, tandis que notre procédé d'information d'identification certifiée automatiquement atteint le niveau 3. Un objet de la présente invention est de fournir un nouveau procédé pour signer une signature électronique numérique, basé sur une information d'identification certifiée automatiquement, qui applique la notion de clé publique certifiée automatiquement au cas dans lequel la clé publique est uniquement l'information d'identification. Un autre autre objet de la présente invention est de fournir un nouveau procédé pour une méthode d'identification réellement "paradoxale", le centre de confiance ne connaissant pas la clé secrète de chaque utilisateur, une méthode de signature correspondante et un protocole d'échange de clé basé sur l'identification, de sorte que chaque utilisateur peut choisir sa propre clé secrète comme si c'est un procédé basé sur l'identification (ce n'est pas un procédé basé sur la certification), utilisant la notion d'information d'identification certifiée automatiquement. A cet effet, selon l'invention, le procédé pour signer une signature électronique numérique dans un système de communication comprenant les équipements d'un réseau informatique comportant un certain nombre d'ordinateurs personnels connectés a chaque utilisateur et un ordinateur central, est remarquable en ce qu'il presente les étapes suivantes - on initialise le système comme suit 1) on sélectionne un modulo n(n=pq, p=2Ydfp'+l, q=2fq'+1) où f, p' et q' sont des nombres premiers distincts satisfaisant gcd(y, q')=l et gcd(y, f)=l et y est un nombre impair constant d 2) on considère y comme y non residu (mod n) d 3) on sélectionne (n, y d, y) comme un triplet acceptable ; 4) on sélectionne un élément primitif b (nombre impair constant) pour le modulo f, satisfaisant bf (mod n)=l ;; et 5) on sélectionne n, Y d, y, b et f comme des clés publi ques et p' et q' comme des clés secrètes dans le centre, respectivement - on sélectionne une clé secrète s dans un utilisateur et on calcule bs (mod n) après avoir sélectionné une identité I en tant que clé publique, et on adresse I et bs (mod n) au système ; - on calcule une information de vérification i et x et on adresse l'information de vérification calculée i et x à l'utilisateur - on sélectionne un nombre entier aléatoire r et on calcule une valeur intermédiaire v de la signature et une fonction numérique e=h(v,m) et on calcule une information de signature z dans l'utilisateur - on adresse z, i, x, e à un vérificateur ; et - on calcule une valeur intermédiaire v' de vérification et la fonction numérique e'=h(v',m), et on vérifie que e=e' dans le vérificateur. De plus, selon l'invention de façon avantageuse l'information de vérification i et x dans le système satisfait à l'équation suivante I = b Sy-i (mod n) ; et/ou s i ~yd - le nombre aléatoire r est sélectionné dans une fourchette de 0 à f-l ; et/ou - la valeur intermédiaire de la signature v satisfait à l'équation suivante v = br ; et/ou l'information de signature z satisfait à l'équation suivante z = r + se (mod f) ; et/ou - la valeur intermédiaire de vérification v' satisfait à l'équation suivante v' = (Iyix&gamma;d )ebz (mod n) ; et/ou - l'information de vérification I dans le système satisfait à l'équation suivante d I = b y x y (mod n) ; et/ou - l'information de vérification I dans le système satisfait à l'équation suivante : I = bsy-ix&gamma;d (mod n). D'autres objets, caractéristiques et avantages- de l'inven- tion, son organisation, sa construction et son mode d'opération sont précisés dans la description détaillee suivante, en référence au dessin. La figure 1 est une vue schématique montrant le système, conforme à la présente invention. Les figures 2A et 2B sont des schémas de principe illustrant un procédé d'identification certifié automatiquement, conforme à la présente invention. La présente invention démontre que ye-RP précité et le problème de comparaison d'indicateur de classe peuvent être étendus à la relation (c') précisée ci-dessous. (c')ye-RP et le problème de comparaison d'indicateur de classe sont équivalents au problème de recherche d'indicateur de classe lorsque Y = (O(polyl(k))O(poly2(k)), où polyl(.) et poly2(.) concernent des polynômes. Tout d'abord, la figure 1 montre un système conforme & la présente invention. Le système comporte une pluralité d'ordinateurs personnels 13 connectés à chacun des utilisateurs, un ordinateur 12 qui sert de centre, et un réseau informatique 11 relié aux ordinateurs 12 et 13. La présente invention peut être appliquée à un réseau de communication unidirectionnel et à d'autres architectures de réseau, d'un type de non-communication. La sécurité de l'invention est basée sur la difficulté du problème de re-résidu et du problème de logarithme discret, simultanément. Aussi, la présente invention atteint le niveau 3 de confiance. Les figures 2A et 2B montrent un procédé de signature conforme à la présente invention. On considère n comme le produit de deux nombres premiers p et q tels que p=2&gamma;dfp'+1 et q=2fq'+l, où f, p' et q' sont des nombres entiers distincts et gcd(y, q')=l, gcd(y, f)=l. On considère que y est un (&gamma;d )e-non-résidu mod n et (n,&gamma;d, y) est un triplet acceptable, et l'ordre de b modulo n est f, à l'étape 21. La clé publique du centre de confiance est (n,&gamma;d ,y,b,f) et la clé secrète du centre de confiance est une paire (p',q'). Chaque utilisateur choisit une clé secrète s, inférieure & f, et adresse l'identité I et b5 au centre de confiance, à l'étape 22. Ensuite, le centre de confiance, à l'étape 23, calcule i et x, où i est l'indicateur de classe de (lb5) -i (mod n) et I=b-sy-1x-&gamma;d. Les équations I=bsyix&gamma;d (mod n) et I=bsy-ix&gamma;d (mod n) sont équivalentes à l'équation I=b-sy-ix-&gamma;d. Et le centre de confiance adressei et x à l'utilisateur I. Ici , i et x ne doivent pas être secrets, c'est-à-dire la seule clé secrète de l'utilisateur est s. Lorsqu'un utilisateur A désire se montrer à un autre utilisateur B, le protocole est le suivant 1) L'utilisateur A choisit un nombre entier aléatoire r dans l'intervalle [0, f-l] à l'étape 24, calcule v=br (mod n) et adresse son identité I et v au vérificateur à l'étape 25. 2) L'utilisateur B choisit un nombre entier aléatoire e dans l'intervalle [0, 2t-1] (où, t est typiquement situé entre 20 et 70) et l'adresse à l'utilisateur A. 3) L'utilisateur A calcule z=r+se (mod f) et adresse z, i et x à l'utilisateur B à l'étape 26. d 4) L'utilisateur B vérifie que (IyiXY )ebZ (mod n) = v l'étape 28. On peut démontrer que - l'utilisateur A sera accepté par l'utilisateur B à une probabilité à peu près égale à 1 (état complet), - un imposteur, qui ne connaît pas s, sera détecté à la probabilité 1-2 t (bon état), - le protocole révèle difficilement quelque chose concernant s (connaissance minimale). On remarquera qu'il n'existe aucun certificat à vérifier, c'est-à-dire l'identité I est juste la clé publique et le certificat. Bien entendu, le centre de confiance peut toujours calculer des clés secrètes "fausses" liées à l'utilisateur A, en choisissant un nombre s' et en calculant i' et x'. Cependant, comme uniquement le centre de confiance est capable de calculer l'indicateur i et x, l'existence de deux i, i' et x, x' différents pour le même utilisateur est en soi une preuve que le centre de confiance s'est trompé. Ceci montre que l'invention atteint le niveau 3 de confiance, au contraire de la méthode basée sur l'identification qui se trouve dans le niveau 1 de confiance. Lorsque l'utilisateur A désire signer le message m, le protocole est le suivant 1) L'utilisateur A choisit un nombre entier aléatoire r dans l'intervalle, il calcule v=br (mod n) et e=h(v,m), où h est une fonction numérique, à l'étape 25. 2) L'utilisateur A calcule z=r+se (mod f) et adresse z, i, x et e à l'utilisateur B, aux étapes 26 et 27. iy e2 3) L'utilisateur B calcule la valeur v telle que (Iyix&gamma;d)eb2 (mod n) = v, à l'étape 28. 4) L'utilisateur B vérifie que e=h(v,m), à l'étape 29. Il peut être démontre que - l'utilisateur B acceptera la signature valide 1 (état complet), - un imposteur, qui ne connaît pas s, ne peut pas engendrer une signature valide (bon état). Finalement, le protocole d'échange de clé basé sur l'identification de l'invention est décrit. Lorsque l'utilisateur A et l'utilisateur B désirent partager une clé secrète, le protocole est le suivant 1) L'utilisateur A adresse IA, iA, XA à l'utilisateur B et l'utilisateur B adresse IB, iB, XB à l'utilisateur A. 4) L'utilisateur A et l'utilisateur B peuvent obtenir une clé secrète commune K telle que K = (I AyiA XA&gamma;d)sB = (IByiB XB&gamma;d)SA = B-sAsB mod n. Ce protocole est clairement lié à celui de "Diffie Hellman", mais au contraire de ce dernier, il assure à l'utilisateur A qu'il partage K avec l'utilisateur B, et inversement. REVENDICATIONS 1. Procédé pour signer une signature électronique numérique dans un système de communication comprenant les équipements d'un réseau informatique comportant un certain nombre d'ordinateurs personnels connectés à chaque utilisateur et un ordinateur central, caractérisé en ce qu'il présente les étapes suivantes - on initialise le système comme suit 1) on sélectionne un modulo n(n=pq, p=2&gamma;dfp'+1, q=2fq'+1) où f, p' et q' sont des nombres premiers distincts satisfaisant gcd(Y, q')=l et gcd(Y, f)=l eut y est un nombre impair constant 2) on considère y comme (&gamma;d)-non résidu (mod n) ;; d 3) on sélectionne (n, yod, y) comme un triplet acceptable 4) on sélectionne un élément primitif b (nombre impair constant) pour le modulo f, satisfaisant b f (mod n)=l et d 5) on sélectionne n,y , y, b et f comme des clés publi- ques et p' et q' comme des clés secrètes dans le centre, respectivement - on sélectionne une clé secrète s dans un utilisateur et on calcule bs (mod n) après avoir sélectionné une identité I en tant que clé publique, et on adresse I et bs (mod n) au système - on calcule une information de vérification i et x et on adresse l'information de vérification calculée i et x à l'utilisateur - on sélectionne un nombre entier aléatoire r et on calcule une valeur intermédiaire v de la signature et une fonction numérique e=h(v,m) et on calcule une information de signature z dans l'utilisateur - on adresse z, i, x, e à un vérificateur ; et - on calcule une valeur intermédiaire v' de vérification et la fonction numérique e'=h(v',m), et on vérifie que e=e' dans le vérificateur. 2. Procédé selon la revendication 1, caractérisé en ce que l'information de vérification i et x dans le système satisfait à l'équation suivante -s -i ~ d I = b y x Y (mod n). 3. Procédé selon la revendication 1, caractérisé en ce que le nombre entier aléatoire r est sélectionné dans une fourchette de O à f-l. 4. Procédé selon la revendication 1, caractérisé en ce que la valeur intermédiaire de la signature v satisfait à l'équation suivante v = br. 5. Procédé selon la revendication 1, caractérisé en ce que l'information de signature z satisfait à l'équation suivante : = r + se (mod f). 6. Procédé selon la revendication 1, caractérisé en ce que la valeur intermédiaire de verification v' satisfait à l'équation suivante v' = (IyixY ) ebz (mod n). 7. Procédé selon la revendication 1, caractérisé en ce que l'information de vérification I dans le système satisfait à l'équation suivante : I = bsyix&gamma;d (mod n). 8. Procédé selon la revendication 1, caractérisé en ce que l'information de vérification I dans le système satisfait à l'équation suivante : I = bsy-ix&gamma;d (mod n).