Brevet FR2824974A1 — publié le 20021122

(SD). La présente invention concerne les procédés, les systèmes ainsi que les dispositifs destinés à prouver l'authenticité d'une entité et/ou l'intégrité s et/ou l'authenticité d'un message. Le brevet EP 0 311 470 B 1 dont les inventeurs sont Louis Guillou et Jean Jacques Quisquater décrit un tel procédé. On y fera ci-après rétérence en le désignant par les termes: "brevet GQ" ou " procédé GQ". Par la suite on désignera parfois par "GQ2", "invention GQ2" ou "technologie GQ2" la o présente invention. Selon le procédé GQ, une entité appelée " autorité de confiance " attribue une identité à chaque entité appelée " témoin " et en calcule la signature RSA; durant un processus de personnalisation, l'autorité de confiance donne identité et signature au témoin. Par la suite, le témoin proclame: s " Voici mon identité; j 'en connais la signatre RSA. " Le témoin prouve sans la révéler qu'il connat la signature RSA de son identité. Grâce à la clé publique de vérification RSA distribuée par l'autorité de confiance, une entité appelée " contrôleur" vérifie sans en prendre connaissance que la signature RSA correspond à l'identité proclamée. Les mécanismes utilisant o le procédé GQ se déroulent éé sans transfert de connaissance ". Selon le procédé GQ, le témoin ne connaît pas la clé privée RSA avec laquelle l'autorité de confiance signe un grand nombre d'identités. La technologie GQ précédemment décrite fait appel à la technologie RSA. Mais si la technologie RSA dépend bel et bien de la factorisation du s module n, cette dépendance n'est pas une équivalence, loin s'en faut, comme le démontrent les attaques dites "multiplicatives" contre les diverses normes de signature numérique mettant en oeuvre la technologie RSA. L'objectif de la technologie GQ2 est double: d'une part' améliorer les performances par rapport à la technologie RSA, d'autre part, éviter les problèmes inhérents à la technologie RSA. La connaissance de la clé privée GQ2 est équivalente à la connaissance de la factorisation du module n. Toute attaque au niveau des triplets GQ2 se ramène à la factorisation du module n: il y a cette fois équivalence. Avec la technologie GO2, la charge de travail est réduite, tant pour l'entité qui signe ou qui s'authentifie que pour celle qui contrôl:e. Grâce à un meilleur usage du problème de la factorisation, tant en sécurité qu'en performance, la technologie GQ2 évite les inconvénients présentés par la technologie RSA. o Le procédé GQ met en _uvre des calculs modulo des nombres de 512 bits ou davantage. Ces calculs concernent des nombres ayant sensiblement la méme taille élevés à des puissances de l'ordre de 26 + 1. Or les infrastructures microélectronques existantes, notamment dans le domaine des cartes bancaires, font usage de microprocesseurs auto-programmables s monaIithiques dépourvus de coprocesseurs anthmétiques. La charge de travail liée aux multiples opérations arithmétiques impliquées par des procédés tels que le procédé GQ entrâîne des temps de calcul qui dans certains cas siavèrent pénalisant pour les consommateurs utilisant des cartes bancaires pour acquitter lèurs achats. I1 est rappelé ici, qu'en cherchant à accroître la sécurité des cartes de paiement, les autorités bancaires posent un problème particulièrementdélicat à résoudre. En effet, il faut traiter deux questions apparemment contradictoires: augmenter la sécurité en utilisant des clés de plus en plus longues et distinctes pour chaque carte tout en évitant que la charge de travail n'entrâîne des temps de calcul prohibitifs pour les utilisateurs. Ce problème prend un relief particulier dans la mesure o, en outre, il convient de tenir compte de l' infrastructure en place et des composants microprocesseurs existants. La technologie GQ2 a pour objet d'apporter une solution à ce problème tout en renforçant la sécurité. - - Procédé Plus particulièrement, i'invention concerne un procédé destiné à prouver à une entité contrôleur, - l'authenticité d'une entité et/ou l'intégrité d'un message M associé à cette entité. Cette preuve est établie au moyen de tout ou partie des paramètres suivants ou dérivés de ceux-ci: - m couples de valeurs privées Q1, Q2'... Qm et publiques G, G2,... Gm (m étant supéneur ou égal à 1), o - un module public n constitué par le produit de f facteurs premiers P1, P2' À. pf (f étant supérieur ou égal à 2)7 - un exposant public v. Ledit module, ledit exposant et lesdites valeurs sont liés par des relations du type: Gi.Qjv_1. mod nouG;_QjV mod n Ledit exposant v est tel que V = 2k o k est un paramètre de sécurité plus grand que 1. Ladite valeur publique G.; est le carré gj2 d'un nombre de base g; inférieur aux f facteurs premiers P1, P2, pf. Le nombre de base g; est tel que: les deux équations: X2 _ g; mod n et x2 - - gi mod n n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: l'équation: xV-- gi2 mod n a des solutions en x dans l'anneau des entiers modulo n. Ledit procédé met en _uvre selon les étapes ci-après définies une entité appelée témoin. Cette entité dispose des f facteurs premiers Pi et/ou des paramètres des restes chinois des facteurs premiers et/ou du module public n et/ou des m valeurs pnvées Qj et/ou des f.m composantes Q; j (Qi j - Q mod pj) des valeurs privées Qi et de l'exposant public v. Le témoin calcule des engagements R dans l'anneau des entiers modulo n. Chaque engagement est calculé: À soit en effectuant des opérations du type R_rVmodn o r est un aléa tel que O À. puis en appliquant la méthode des restes chinois. Le témoin reçoit un ou plusieurs défis d. Chaque défi d comporte m entiers di ci-après appelés défis élémentaires. Le témoin calcule à partir de chaque défi d une réponse D, À soit en effectuant des opérations du type: D-r Q dl Q d2... Q dm mod n À soit À. en effectuant des opérations du type: : Di-ri ' Qi 1 À Qi 2 À Qi m mod Pi À. puis en appliquant la méthode des restes chinois. Ledit procédé est tel qu'il y a autant de réponses D que de défis d que 2s d' engagements R. Chaque groupe de nombres R. d, D constitue un triplet noté {R. d, D}. C as de la preuve de l' authenticité d' une entité Dans une première variante de réalisation le procédé selon l' invention est destiné à prouver l'authenticité d'une entité appelée démonstrateur à une --- 2824974 entité appelée-contrôleur. Ladite entité démonstrateur comprend le témoin. Lesdites entités démonstrateur et contrôleur exécutent les étapes suivantes: À étape 1: acte d'engagement R A chaque appel, le témoin calcule chaque engagement R en appliquant le processus spécifié ci-dessus. Le démonstrateur transmet au contrôleur tout ou partie de chaque engagement R. À étape 2: acte dè défi d Le contrôleur, après avoir reçu tout ou partie de chaque engagement R. o produit des défis d en nombre égal au nombre d' engagements R et transmet les défis d au démonstrateur. À étape 3: acte de réponse D Le témoin calcule des réponses D à partir des défis d en appliquant le processus spécifié ci-dessus. À étape 4: acte de contr81e Le démonstrateur transmet chaque réponse D au contrôleur. Premier cas: le démonstrateur a transmis une partie de chaque engagement R Dans le cas o le démonstrateur a transmis une partie de chaque engagement R. le contrôleur, disposant des m valeurs publiques G1, G2, Gm' calcule à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R' -G1 dl. G2 d2 Gm dm. DV mod n ou a une relation du type, R.-DV / G1 dl. G2 d2 Gm dm. mod n. Le contrôleur vérifie que chaque engagement reconstruit R' reproduit tout ou partle de chaque engagement R. qui lui a été transmis, Deuxième cas: le démonstrateur a transmis l'intégralité de chaque engagement R Dans le cas-o le démonstrateur a transmis l'intégralité de chaque engagement R. le contrôleur, disposant des m valeurs publiques G1, G2,... Gm, vérifie que chaque engagement R satisfait à une relation du type: R-G dl G d2... Gm dm. Dv mod n s ou a une relation du type, R _ DV / G di G2 d2.... Gm dm. mod n. Cas de la preuve de l'intégrité d'un message : Dans une deuxième variante de réalisation susceptible d'être combinée avec la première, le procédé selon l' invention est destiné à prouver à une to entité appelée contrôleur l'intégrité d'un message M associé à une entité appelée démonstrateur. Ladite entité démonstrateur comprend le témoin. Lesdites entités démonstrateur et contrôleur exécutent les étapes suivantes: À étape 1: acte d'engagement R i5 A chaque appel, le témoin calcule chaque engagement R en applquant le processus spécifié ci-dessus. À étape 2: acte de défi d Le démonstrateur applique une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R pour calculer au moins un jeton T. Le démonstrateur transmet le jeton T au :: contrôleur. Le contrôleur, après avoir reçu un jeton T. produit des défis d en nombre égal au nombre d' engagements R et transmet les défis d au démonstrateur. À étape 3: acte de réponse D 2s Le témoin calcule des réponses D à partir des défis d en appliquant le processus spécifié ci-dessus. :: À étape 4: acte de contrôle Le démonstrateur transmet chaque réponse D au contrôleur. Le contrôleur, disposant des m valeurs publiques G, G2,... Gm7 calcule à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R' _ G d}. G2 02Gm dm. Dv mod n ou à une relation du type: R'-Dv / G. d. G2 d2Gm dm. mod n Puis le contrôleur applique la fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement reconstruit R' pour reconstruire le jeton T'. Puis le contrôleur vérifie que le jeton T' est identique aueton T transmis. o Signature numérique d'un message et preuve de son authenticité Dans une troisième variante de réalisation susceptible d'être combinée aux deux précédentes, le procédé selon l' invention 1 est destiné à produire la signature numérique d'un message M par une entité appelée entité signataire. Ladite entité signataire comprend le témoin. s Opération de signature Ladite entité signataire exécute une opération de signature en vue d'obtemr un message signé comprenant: - le. message M, les défis d et/ou les engagements R. - les réponses D. Ladite entité signataire exécute l'opération de signature en mettant en oeuvre les étapes suivantes À étape 1: acte d'engagement R A chaque appel, le témoin calcule chaque engagement R en appliquant le processus spécifié ci-dessus. À étape 2: actede défi d Le signataire applique une fonction de hachage h ayant comme arguments le message M et chaque engagement R pour obtenir u train binaire. Le signataire extrait de ce train binaire des défis d en nombre égal au nombre - 2824974 8 - - . d' engagements 11. À étape 3: acte de réponse D Le témoin calcule des réponses D à partir des défis d en appliquant le processus spécifié ci-dessus. s Opération de contrôle Pour prouver l'authenticité du message M, une entité, appelée contrôleur, contrôle le message signé. Ladite enhté contrôleur disposant du message signé exécute une opération de contrôle en procédant comme suit. À cas o le contrôleur dispose des engagements R. des défis d, des réponses D, Dans le cas o le contrôleur dispose des engagements R. des défis d, des réponses D le contrôleur vénfie que les engagements R. les défis d et les réponses D satisfont à des relations du type R_ G d' G d2, Gm dm. Dv mod n s ou à des relations du type: R_ Dv / G d! G2 d2.... Gm dm. mod n Puis le contrôleur vérifie que le.: message M, Ies défis d et les engagements R satisfont à la fonction de hachage d = h (message, R) À cas o le contrôleur dispose des défis d et des réponses D Dans le cas o le contrôleur dispose des défis d et des réponses D, le contrôleur reconstruit, à partir de chaque défi d et de chaque réponse D, des engagements R' satisfaisant à des relations du type: - R. _ G dl. G2 d2... . Gm dm. Dv mod n 2s ouàdes relations du type: R.-Dv / G d! G2 d2.... Gm dm. mod n Puis le contrôleur vérifie que le message M et les défis d satisfont à la fonction de hachage d = h (message, R') - --- 2824974 À cas o le contrôleur dispose des engagements R et des réponses D Dans le cas o le contrôleur dispose des engagements R et des réponses D, le contrBleur applique la fonction de hachage et reconstruit d' : d' = h (message, R) PUiS, contrôleur vérifie que les engagements:R, les défis d' et les réponses D, satisfont à des relations du type: R_Gld.G262....Gmd'm. Dvmodn ou à des relations du type: R _ Dv / G d'] G2 d'2.... Gm d'm. mod n o Système La présenté invention concerne également un système destiné à prouver à un serveur contrôleur,: - l'authenticité d'une entité et/ou - l'intégrité d'un message NI associé à cette entité. s Gette preuve:est établie au moyen de tout ou partie des paramètres suivants ou dérivés de ceux-ci: - m couples de valeurs pnvées Q, Q2,... Qm et publiques G1, G2,... Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers p,, P2, À. pf (f étant supérieur ou égal à 2), - un exposant public v;: Ledit module, ledit exposant et lesdites valeurs sont liés par des relations du type: : Gi. Qiv -1. mod n ou Gi - QiVmod n. 2s Ledit exposant v est tel que V=2k o k est un paramètre de sécurité plus grand que 1. Ladite valeur publique G.; est le carré g'2 d'un nombre de base gi inférieur aux f facteurs premiers p', P2,... pf. Le nombre de base g; est tel que: les deux équations: x2 - gi mod n et x2 - - gi mod n n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: s l'équation: xV-gi2 mod n a des solutions en x dans L'anneau des entiers modulo n. Ledit système comprend un dispositif témoin, notamment contenu dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire to à microprocesseur. Le dispositif témoin comporte une zone mémoire contenant les f facteurs premiers Pi et/ou les paramètres des restes chinois des facteurs premiers et/ou le module public n et/ou les m valeurs privées Qi et/ou les f.m composantes Qi, j (Qi, j -- Qi mod pj) des valeurs privées Qi et l'exposant public v. Ledit dispositif témoin comporte aussi: s - des moyens de production d'aléas, ci-après désignés les moyens de production d'aléas du dispositif témoin,: - des moyens de calcul, ci-après désignés les moyens de calcul des engagements R du dispositif témoin. Les moyens de calcul permettent de calculer des engagements R dans l'anneau des entiers modulo n. Chaque engagement est calculé: À soit en effectuant des opérations du type R _ rV mod n o r est un aléa produit par les moyens de production d'aléas, r étant tel queO : de production d'aléas, pus en appliquant la méthode des restes chinois. Ledit dispositiftémoin comporte aussi: - des moyens de réception, ciaprès désignés les moyens de réception des défis d du dispositif témoin, pour recevoir un ou plusieurs défis d; chaque défi d comportant m entiers di ci-après appelés défis élémentaires; - des moyens de calcul, ci après désignés les moyens de calcul des réponses D du dispositif témom, pour calculer à part* de chaque défi d une réponse D, À soit en effectuant des opérations du type: D-r Q dl Q d2,. Q dm mod n o À soit en effectuant des opérations du type: Di-ri. Qil dl, Qi2 d2.,,, Qm dm mod Pi, puis en appliquant la méthode des restes chinois, Ledit dispositif témoin comporte aussi des moyens de transmission pour transmettre un ou plusieurs engagements R et une ou plusieurs réponses D. I1 y a autant de réponses D que de défis d que d'engagernents R Chaque groupe de nombres R. d, D constitue un triplet noté {R. d, D}. Cas de la preuve de l'authenticité d'une entité Dans une première variante de réalisation le système selon l' invention est destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur, - Ledit système est tel qu'il comporte un dispositif démonstrateur associé à l'entité démonstrateur. Ledit dispositif démonskateur est interconnecté au dispositif témoin par des moyens d'interconnexion. n peut se présenter notamment sous la forme de microcircuits logiques dans un obJet nomade, par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur. Ledit système comporte aussi un dispositif contrôleur associé à l'entité contrôleur. Ledit dispositif contrôleur se présente notamment sous la forme d'un terminal ou d'un serveur distant. Ledit dispositif contrôleur comporte des moyens- de connexion pour le connecter électriquement; électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif démonstrateur; s Ledit système permet d'exécuter les étapes suivantes: À étape 1: acte d'engagement R A chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R. en appliquant le processus spécifié ci-dessus. Le dispositif témoin comporte des moyens de transmission, ci o aprés désignés ies rnoyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif démonstrateur, via les moyens d'interconnexion. Le dispositif démonstrateur comporte aussi des moyens de transmission, ciaprès désignés les moyens de transrnission du dérnonstrateur, pour transmettre s tout ou partie de chaque engagement R au dispositif contrôleur, via les moyens de connexion. À étape 2: actede défi d Le dispositif contrôleur comporte des moyens de production de défis pour produire, aprés avoir reçu tout ou partie de chaque engagement R. des défis d en nombre égal au nombre d' engagements R Le dispositif contrôleur comporte aussi des moyens de transmission, ciaprès désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion. À étape 3: acte de réponse D Les moyens de réception des défis d du dispositif témoin, reçoivent chaque défi d provenant du dispositif démonstrateur, via les moyens d'interconnexion. Les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des défis d en appliquant le processus spécifié ci-dessus. À étape 4: acte de contrôle Les moyens de transmission du démonstrateur transmettent chaque réponse D au contrôleur. Le dispositif contrôleur comporte aussi: - des moyens de calcu, ci-après désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, cl-après désignés les moyens de comparaison du dispositif contrôleur. Premier cas: le démonstrateur a transmis une partie de chaque engagement R o Dans le cas o les moyens de transmission du démonstrateur ont transmis une partie de chaque engagement R. les moyens de calcul du dispositif contrôleur, disposant des m valeurs publiques G1, G2,... Gm' calculent à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R.--G dl G: d2... Gm dm. Dv mod n ou à une relation du type, R. _ Dv / G1 dl. G2 d2.... Gm dm. mod n. Les moyens de comparaison du dispositif contrôleur comparent chaque engagement reconstruit R' à tout ou partie de chaque engagement R reçu. Deuxième cas: le démonstrateur a transmis l'intégralité de chaque engagement R Dans le cas o les moyens de transmission du démonstrateur ont hansmis l'intégralité de chaque engagement R. les moyens de calcul et les moyens de comparaison du dispositif contrôleur, disposant des m valeurs publiques G, G2, Gm, vérifient que chaque engagement R satisfait à une relation du type: R-G1 dl. G2 i.... Gm dm. Dv mod n ou à une relation du type, 1 _ Dv / G d!. G2 d2.... Gm dm. mod n. : Cas de la preuve de l'intégrité d'un message. Dans une deuxième variante de réalisation susceptibie d'être combinée avec la première, le système selon l' invention est destiné à prouver à une entité appelée contrôleur l'intégrité d'un message M associé à une entité s appelée démonstrateur. Ledit système est tel qu'il comporte un dispositif démonstrateur associé à l'entité démonstrateur. Ledit dispositif démonstrateur est interconnecté au dispositif témoin par des moyens d'interconnexion. Ledit dispositif démonstrateur peut se présenter notamment sous la forme de microcircuits logiques dans un objet nomade o par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur. Ledit système comporte aussi dispositif contrôleur associé à l'entité contrôleur. Ledit dispositif contrôleur se présente notamment sous la forme d'un tenninal ou d'un serveur distant. Ledit dispositif contrôIeur comporte des moyens de connexion pour le connecter électnquement; électromagnétiquement, optiquement ou de manière acoustique, notarnment via un réseau de communication informatique, au dispositif démonstrateur. Ledit système exécute les étapes suivantes: À étape 1: acte d'engagement R A chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié ci-dessus. Lé dispositif témoin comporte des moyens de transmission, ci aprés désignés les moyens de transmission du dispositif témoin, pour transméttre tout ou partie de chaque engagement R au dispositif s démonstrateur, via les moyens d'interconnexion. À étape 2: acte de défi d Le dispositif démonstrateur comporte des moyens de calcul, ci-après désignés les moyens de calcul du démonstrateur, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R. pour calculer au moins un jeton T. Le dispositif démonstrateur comporte aussi des moyens de transmission, ci-après déslgnés les moyens de transmisslon du dispositif démonstrateur, pour transmettre chaque jeton T. via les moyens de connexion, au dispositif s contrôleur. Le dispositif contrôleur comporte aussi des moyens de production de défis pour produire, après avoir reçu le jeton T. des défis d en nombre égal au nombre d' engagements R Le dispositif contrôleur comporte aussi des moyens de transmission, ci-après désignés les moyens de transmission du contrôleur, pour transmettre les défis d au o démonstrateur, via les moyens de connexion. À étape 3: acte de réponse D Les moyens de réception des défis d du dispositif témoin, reçoivent chaque défi d provenant du dispositif démonstrateur, via les moyens d'interconnexion. Les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des défis d en appliquant le processus spécifié ci-dessus. étape 4: acte de contrôle ::: Les moyens de transmission du démonstrateur transmettent chaque réponse D au contrôleur. Le dispositif contrôleur comporte aussi des moyens de calcul, ci-après désignés les moyens de calcul du dispositif - contrôleur, disposant des m valeurs publiques G, G2,... Gm' pour d'une part, calculer à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R.-G dl G2 d2... G. dm. Dv mod n 2s ou à une relation du type: R. -Dv / G dl G2 d2.... Gm dm. mod n puis d'autre part, calculer en appliquant la fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement reconstruit R', un jeton T'. Le dispositif contrôleur comporte aussi des moyens de comparaison, ci après désignés les moyens de comparaison du dispositif contrôleur, pour comparer le jeton calculé T' au jeton T reçu. Signature numérique d'un message et preuve de son authentieité s Dans une troisième vanante de réalisation susceptible d'être combinée avec l'une et/ou l'autre des deux premières, le système selon l'invention est destiné à prouver la signature numérique d'un message M, ci-après désigné le message signé, par une entité appelée entité signataire. Le message signé comprend: o - le message M, - les défis d et/ou les engagements R. - les réponses D; Opération de signature Ledit systène est tel qu'il comporte un disposit f signataire associé à s 1?entité signataire. Ledit dispositif signataire est interconnecté au dispositif témom par des moyens d'interconnexion et peut se présenter notamment sous la forme de microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur. Ledit système permet d'exécuter les étapes suivantes: À étape 1: acte d'engagement R A chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié ci-dessus. 2s Le dispositif témom comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif signataire, via les moyens d'interconnexion. À étape 2: acte de défi d Le disposit f signataire comporte des moyens de calcul, ci-après désignés les moyens de calcul du dispositif signataire, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R. pour calculer un train binaire et extraire de ce train binaire des défis d en nombre égal au nombre d' engagements R. À étape 3: acte de réponse D Les moyens de réception des défis d du dispositif témoin, reçoivent chaque défi d provenant du dispositif signataire, via les moyens d'interconnexion. Les moyens de calcul des réponses D du dispositif témoin, calculent les o réponses D à partir des défis d en appliquant le processus spécifié ci dessus. Le dispositif témoin comporte des moyens de transmission, ciaprès désignés les moyens de transmission du dispositif témoin, pour transmettre les réponses D au dispositif signataire, via les moyens d'interconnexion. is Opération de contrôle Pour prouver l'authenticité du message M, une entité appelée contrôleur, contrôle le. message signé. Ledit système comporte un dispositif contrôleur associé à l'entité contrôleur. Ledit dispositif contrôleur se présente notamment sous la forme d'un terminal ou d'un serveur distant. Ledit dispositif contrôleur comporte des moyens de connexion pour le connocter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication mormatique, au disposihf sgnatare. : 2s Le dispositif signataire associé à l'entité signataire comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif signataire, pour transmettre au dispositif contrôleur, le message signé,via les moyens de connexion. Ainsi, le dispositif contrôleur dispose d'un message signé comprenant: - le message M, - les défis d et/ou les engagements R. - les réponses D; Le dispositif contrôleur comporte: - des moyens de calcul, c-après désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur. À cas o le dispositif contrôleur dispose des engagements R. des défis d, o des réponses D, Dans le cas o le dlsposibf contrôleur dispose des engagements R. des déhis d, des réponses D, les rnoyens de calcul et de comparaison du dispositif contrôleur vérifient que les engagements R. les déhis d et les réponses D satisfont à des relations du type :: R 9 G1 dl. G2 d2.,.. Gm dm. Dv mod n ou à:des relations du type:: : R_ Dv / G1 dl. G2 d2.... Gm dm. mod n Puis, les moyens de calcul et de comparaison du dispositif contrôleur: vérifient que le message M, les défis d et les engagements R satisfont à la fonction de hachage - : d = h (message, R) À cas o le dispositif contrôleur dispose des défis d et des réponses D Dans le. cas o le dispositif contrôleur dispose des déhis d et des réponses ::D, les moyens de calcul du dispositif contrôleur calculent, à partir de 2s chaque défi d et de chaque réponse D, des engagements R' satisfaisant à des relatlons du type:: R'-G1 dl. G2 d2.... Gm dm. Dv mod n : ou à des relations du type: R.-Dv j G dl G2 d2.... Gm dm. mod n - Puis, les moyens de calcul et de comp-araison du dispositif contrôleur vérifient que le message M et les défis d satisfont à la fonction de hachage d = h (message, R') À cas o le dispositif contrôleur dispose des engagements R et des s réponses D Dans le cas o le dispositif contrôleur dispose des engagements R et des réponses D, les moyens de calcul du dispositif contrôleur appliquent la fonction de hachage et calculent d' tel que d' = h (message, R) o Puis, les moyens de calcul et de comparaison du dispositif contrôleur vérifient que les engagements R. les défis d' et les réponses D, satisfont à des relations du type: R-G d'1 G d'2... Gm d'm. Dv mod n ou à des relations du type: s R_DV/Gdi.G2d2 Gmdm. mod n Dispositif Termina 1 L'invention concerne aussi un dispositif tennir associé à une entité. Le dispositif terminal se présènte notamment sous la forme d'un objet nomade par exemple sous la formè d'une carte bancaire à microprocesseur. Le. dispositif terminal est destiné à prouver à un dispositif contrôleur: - l' authenticité de l' entité et!ou - l'intégrité d'un message M associé à cette entité. Cette preuve;est établie au moyen de tout ou partie des paramètres suivants ou dérivés de ceux-ci: - m couples de valeurs privées Q, Q2,... Qm et publiques G', G2,... Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers p', P2, À. pf (f étant supérieur ou égal à 2), - un exposant public v. Ledit module,-ledit exposant et lesdites valeurs sont liés par des relations du type: : Gj. Qiv _1. mod n ou Gi - Qiv mod n. Ledit exposant v est tel. que - v = 2k o k est un paramètre de sécurité plus grand que 1. : Ladite valeur publique Gi est le carré gi2 d'un nombre de base gi inférieur aux f facteurs premiers p" P2,... pf. Le nombre de base gi est tel que: les: deux équations:: o: x2 - gimod n et x2 _ - gimod n n'ont pas de solution en x dans i'anneau des entiers modulo n et tel que: l'équation: : xV- gi2 mod n s a dessolutions en x dans l'anneau des entiers modulo n. Ledit dispositif terminal comprend un dispositif témoin comportant une zone mémoire contenant les f facteurs premiers Pi etlou les paramètres des restes chinois des facteurs premiers et/ou le module public n et/ou les m valeurs privées Qi eVou les fm composantes Qi j (Qi j - Qi mod pj) des valeurs- privées Qi et l'exposant public v. Ledit dispositif témoin comporte aussi: :- des moyens de production d'aléas, ci-après désignés les moyens de production d'aléas du dispositif témoin, - des moyens de calcul, ci-après désignés les moyens de calcul des engagements R du dispOsitif témoin, pour calculer des engagements R dans l'anneau des entiers modulo n.: Chaque engagement est calculé: : À soit en effectuant des opérations du type : R_rVmodn ou r est un aléa produit par les moyens de production d'aléas, r étant tel queO de production d'aléas, puis en appliquant la méthode des restes chinois. Le dispositif témoin comporte aussi: - des moyens de réception, ci-après désignés les moyens de réception o des défis d du dispositif témom, pour recevoir un ou plusieurs défis d; chaque défi d comportant m entiers d; ci-après appelés défis élémentaires; - des moyens de calcul, Cl après désignés les moyens de calcul des réponses D du dispositif témom, pour calculer à partir de chaque défi d une réponse D, soit en effectuant des opérations du type: D-r. Q1 dl À Q2 d2 Q dm mod n À soit en effectuant: des opérations du type: Di-ri. Qi l dl. Q"2 d2.... Qm dm mod P puis en appliquant la méthode des restes chinois. Ledit dispositif témoin comporte aussi des moyens de transmission pour transmettre un ou plusieurs engagements R et une ou plusieurs réponses D. I1 y a autant de réponses D-que de défis d que d' engagements R Chaque groupe de nombres R. d, D constituant un triplet noté {R. d, D}. C as de la preuve de l' authenticité d'une entité 2s Dans une première variante de réalisation le dispositif terminal selon ltinvention est destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur. Ledit dispositif tenninal est tel qu'il comporte un dispositif démonstrateur associé à l'entité démonstrateur. Ledit dispositif démonstrateur est 22 2824974 interconnecté- au dispositif témoin par des moyens d'interconnexion. n peut se présenter notamment sous la forme de microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur. s Ledit dispositif démonstrateur comporte aussi des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif contrôleur associé à l'entité contrôleur. Ledit dispositif contrôleur se présente notamment sous la forme d'un terminal ou to d'un serveur distant. Ledit dispositif terminal permet d'exécuter les étapes suivantes: À étape 1: acte d'engagement R A chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaqué engagement R en appliquant le processus spécifié s ci-dessus. - Le dispositif témoin comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif démonstrateur, via les moyens d'interconnexion. Le dispositif démonstrateur comporte aussi des moyens de transmission, ci-après désignés les moyens de transmission du démonstrateur, pour transmettre tout ou partie de chaque engagement R au disposihf contrôleur, via les moyens de connexion. À étapes 2 et 3: acte de défi d, acte de réponse D Les moyens de réception des détis d du dispositif témoin, recoivent chaque - 2s défi d provenant du dispositif contrôleur via les moyens de connexion entre le dispositif contrôleur et le dispositif démonstrateur et via les moyens d'interconnexion entre le dispositif démonstrateur et le dispositif témoin. Les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des défs d en appliquant le processus spécifié ci 23 2824974 : - - dessus.:- À étape 4: acte de contrôle : Les moyens de ransmission du démonstrateur transmettent chaque réponse D au dispositif contrôleur qui procède au contrôle. s Cas de la preuve de l'intégritéd'un message : Dans une deuxième variante de réalisahon susceptible d'hre combinée à la première, le dispositifterminal selon l'invenhon est destiné à prouver à une entité appelée contrôleur l'intégrité d'un message M associé à une entité appelée démonstrateur. Ledit dispositif terminal est tel qu'il comporte un to dispositif démonstrateur associé à l'entité démonstrateur, ledit dispositif démonstrateur est interconnecté au dispositif témoin par des moyens d'interconnexion. I1 peut se présenter notamment sous la forme de microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur. Ledit : dispositif démonstrateur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au disposihf contrôleur associé à l'entité contrôleur. Ledit dispositif contrôleur se présente notamment sous la forme d'un terminal ou d'un serveurdistant. Ledit dispositif terminal permet d'exécuter les étapes suivantes: À étape 1: acte d'engagement R A chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifé - 2s ci-dessus Le dispositif témoin comporte des moyens de transmission, ci après désignés les moyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif démonstrateur, via les moyens d'interconnexion. À étapes 2 et 3: acte de défi d, acte de réponse D Le dispositif démonstrateur comporte des moyens de calcul, ci-après désignés les moyens de calcul du démonstrateur, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R. pour calculer au moins un jeton T. Le dispositif démonstrateur comporte aussi des moyens de transmission, ci-après désignés les moyens de transmission du dispositif démonstrateur, pour transmettre chaque jeton T. via les moyens de connexion, au dispositif contrôleur. Ledit dispositif contrôleur produit, après avoir reçu le. jeton T. des défis d to en nombre égal au nombre d'engagements R. Les moyens de réception des défis d du dispositif témoin, reçoivent chaque défi d provenant du dispositif contrôleur via les moyens de connexion entre le dispositif contr61eur et le dispositif démonstrateur et via les moyens d'interconnexion entre le dispositif démonstrateur et le dispositif témoin. t5 Les moyens de calcul des réponses D du dispositif témoin calculent les réponses D à partir des défis d en appliquant le processus spécifé ci dessus.: À étape 4: acte de contrôle Les moyens de transmisson du démonstrateur transmettent chaque réponse D au dispositif contrôleur qui procède au contrôle. Signature numérique d'un message et preuve de son authenticité Dans une troisième variante de réalisation susceptible d'être combinée avec l'une ou l'autre des deux premières, le dispositif terminal selon l' invention est destiné à produire la signature numérique d' un message M, - 25 ci-après désigné le message signé, par une entité appelée entité signataire. Le message signé comprend: - le message M, - les défis d et/ou les engagements R. - les réponses D. :: Ledit dispositif-terminal est tel qu'il comporte un dispositif signataire associé à l'entité signatalre. Ledit disposihf signataire est interconnecté au dispositif témoin par des moyens d'mterconnexion. I1 peut se présenter notarrment sous la forme de microcircuits logiques dans un obJet nomade s par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur. Ledit dlspositif signataire comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réscau de : communication informatique, au dispositif contrôleur associé à l'entité :: contrôleur. Ledit dispositif contrôleur se présente notamment sous la forme d'un terminal ou d'un serveur distant. :: Opération de signature Ledit dspositif terminal pemmet d'exécuter les étapes suivantes: étape l: acte d'engagement R s A chaque appeI, les moyens de calcuI des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié ci-dessus. Le dispositif témoin comporte des moyens de transmission, ci après désignés les moyens de transmission du dispositif témoin, pour transmettre tout ou piartie de chaque engagement R au dispositif signataire, via les moyens d'interconnexion étape 2: acte de defi d Le dispositif signataire comporte des moyens de calcul, ci-après désignés les moyens de calcul du dispositif signataire, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de - 2s chaque engagement R. pour calculer un train binaire et extraire de ce train binaire des détis d en nombre égal au nombre d' engagements R. À étape 3: acte de réponse D Les moyens de réception des défis d du dispositif témoin reçoivent chaque déti d provenant du dispositif signataire, via les moyens d'interconnexion. Les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des défis d en appliquant le processus spécifié ci dessus. Le dispositif témoin comporte des moyens de transmission, ciaprès désignés les moyens de transmission du dispositif témoin, pour transmettre s les réponses D au dispositif signataire, via les moyens d'interconnexion. Dispositif contrôleur L'invention concerne aussi un dispositif contrôleur. Le dispositif contrôleur peut se présenter notamment sous la forme d'un terminal ou d'un serveur distant associé à une entité contrôleur. Le dispositif o contrôleur est destiné à contrôler: - l'authenticité d'une entité et/ou - l'intégrité d'un message M associé à cette entité, Cette preuve est établie au moyen de tout ou partie des paramétres suivants ou dérivés de ceux-ci: s - m couples:de valeurs publiques G" G2, Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers p" P2,... pf (f étant supérieur ou égal à 2) inconnus du dispositif contrôleur et de l'èntité contrôleur associé, - un exposant public v. Ledit module, ledit exposant et lesdites valeurs sont liés par des relations du type: Gi.QiV-l.modnouG'-QiVmodn; o Qi désigne une valeur privée, inconnue du dispositif contrôleur, 2s associée à la valeur publique Gi. L'exposant v esttel que v = 2 o k est un paramètre de sécurité plus grand que 1. Ladite valeur publique Gi est le carré gi2 d'un nombre de base gi inférieur aux f facteurs premiers P1, P2, pf. Le nombre de base g; est tel que: les deux équations: x2- gj mod n et x2 - - gj mod n; n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: l'équation: x -gj mod n a des solutions en x dans l'anneau des entiers modulo n. C as de la preuve de l' authenticité d'une entité o Dans- une première variante de réalisation le dispositif contrôleur selon l'invention est destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur. Ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquemet, électromagnétiquement, optiquement ou de is manière acoustique, notamment via un réseau de communication informahque' à un dispositif démonstrateur associée à l'entité démonstrateur. Ledit dispositif contrBleur permet d'exécuter les étapes suivantes: À étapes 1 et 2: acte d'engagement R. acte de défi d Ledit dispositif contrôleur comporte aussi des moyens de réception de tout ou partie des engagements R provenant du dispositif démonstrateur, via les moyens de connexion. Le dispositif contrôleur comporte des moyens de production de défis pour produire' après avoir reçu tout ou partie de chaque engagement R. des - 2s défis d en nombre égal au nombre d' engagements R. chaque défi d comportant m entiers dj ci-après appelés défis élémentaires. Le dispositif contrôleur comporte aussi des moyens de transmission, ci après désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion. À étapes -3 et 4: acte de réponse D, - acte dè contrôle Ledit dispositif contrôleur comporte aussi: - des moyens de réception des réponses D provenant du dispositif démonstrateur, via le s moyens de connexi on des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur. Premier cas: le démonstrateur a transmis une partie de chaque o engagement R Dans le cas o les moyens de réception du dispositif contrôleur ont reçus une part e de chaque engagement R. les moyens de calcul du dispositif contr81eur, disposant des m valeurs publiques G1, G2, ... Gm' calculent à partir de chaque défi d et de chaque réponse D un engagement reconstruit s R' satisfaisant à une relation du type: R' -G dl G2 d2.... Gm dm. Dv mod n ou à une relation du type, R' _ Dv / G dl G2 d2. ... Gm dm. mod n, Les moyens de comparaison du dispositif contrôleur comparent chaque engagement reconstruit R' à tout ou partie de chaque engagement R reçu. Deuxième cas: le démonstrateur a transmis l'intégralité de chaque : engagement R Dans le cas o les moyens de réception du dispositif contrôleur ont reçus l'intégralité de chaque engagement R. les moyens de calcul et les moyens de comparaison du dispositif contrôleur, disposant des m valeurs publiques G1, G2,... Gm, vérifient que chaque engagement R satisfait à une relation du type: R-G1 dl. G2 d2.... Gm dm. Dv mod n ou à une relation du type, R _ Dv / G d' G2 d2.... Gm dm. mod n. Cas de la preuve de l'intégrité d'un message Dans une deuxième variante de réalisation susceptible d'être combinée avec la première, le dispositif contrôleur selon l' invention est destiné à prouver l'intogrité d'un message M associé à une entité appelée démonstrateur. Ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, éIectromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication o informatique, à un disposinf démonstrateur assoctée à l'entité démonstrateur. Ledit dispositif contrôleur permet d'exécuter les étapes suvantes: À étapes 1 et 2: acte d'engagement R. acte de def d :: L:edit dispositif contrôleur comporte aussi des moyens de réception de s jetons T provenant du spositif démonstrateur, via les moyens de connexion. Le dispositif contrôleur comporte des moyens de production de défis pour produire, après avoir reçu le jeton T. des défis d en nombre égal au nombre d'engagements R. chaque défi d comportant m entiers d ci-après appelés défis élémentaires. Le dispositif contrôleur comporte aussi des moyens de transmission, ci-après désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion. À étapes 3 et 4: acte de réponse D, acte de contrôle Ledit dispositif contrôleur comporte des moyens de réception des réponses D provenant du dispositif démonstrateur, via les moyens de connexion. Ledit dispositif contrôleur comporte aussi des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, disposant des m valeurs publiques G, G2,... Gm' pour d'une part, calculer à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' ^- 2824974 satisfaisant à une relation du type: R'-G dl G d2... Gm dm. Dv mod n ou à une relation du type: R'-Dv / G dl G2 d2.... Gm dm. mod n s puis d'autre part, calculer en appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement reconstruit R', un jeton T'. Le dispositif contrôleur comporte aussi des moyens de comparaison, ci après désignés les moyens de comparaison du dispositif contrôleur, pour comparer le jeton calculé T' au jeton T reçu. Signature numérique d'un message et preuve de son authenticité Dans une troisième variante de réalisation susceptible d'être combinée avec l'une et/ou l'autre des deux premières, le dispositif contrôleur selon l'invenhon est destiné à prouver l'authenticité du message M en s contr81ant, par une entité appelée contr81eur, un message signé. Le message signé, émis par un dispositif signataire associé à une entité signataire disposant d'une fonction de hachage h (message, R), comprend: le message M, - des défis d et/ou des engagements R. - des réponses D; Opération de contrôle Ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication - 2s informatique, à un dispositif signataire associée à l'entité signataire. Ledit dispositif contrôleur reçoit le message signé du dispositif signataire, via les moyens de connexion. Le dispositif contrôleur comporte: - des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur. À cas: o le dispositif contrôleur dispose des engagements R. des défis d, : s des réponsesD, Dans le cas o le dispositif contrôleur dispose des engagements R. des défis d, des réponses D, les moyens de calcul et de comparaison du : dispositif contrôleur: vérifi nt que les engagements R. les défis d et les réponses D satisfont à des relations du type R_ G d! G d2... G. dm. DV mod n : ou à des relations du type: R _ Dv / G d} G2 d2... . Gm dm. mod n Puis, les moyens de calcul et de comparaison du disposltif contrôleur vérifient que le message M, les défis d et les engagements R satisfont à la 1S fonction de hachage: : d = h (message, R) À cas o le dispositif contrôleur dispose des déffs d et des réponses D Dans le cas o le dispositif contrôleur dispose des défis d et des réponses D, les moyens de calcul du dispositif contrôleur calculent, à partir de : 20 chaque:défi d et de chaque réponse D, des engagements R' satisfaisant à des relations du type: R. _ G d! G2 d2.... Gm dm. Dv mod n :: ou à des relations du type: R.-Dv / G' J!. G2 d2.... Gm dm. mod n 2s puis, les moyens de calcul et de comparaison du dispositif contrôleur vérifient que le message M et les défs d satisfont à la fonction de hachage d = h (message, R') À cas o le dispositif contrôleur dispose des engagements R et des réponses D / Dans le cas o le dispositif contrôleur dispose des engagements R et des réponses D, les moyens de calcul du dispositif contrôleur appliquent la fonction de hachage et calculent d' tel que d' = h (message, R) Puis, les moyens de calcul et de comparaison du dispositif contrôleur vérifient que les engagements R. les défis d' et les réponses D, satisfont à des relations du type:: R g G1 d'1. G2 d'2.... G. d'm Dv mod n ou à des relations du type:: o:: R-Dv / G dil G2 d'2,.,. Gm d'm. mod n 33 2824974 Description- -: Rappelons l'objectif de la technologie GQ: l'authentification dynamique d'entités et de messages associés, ainsi que la signature numérique de :: messages. s La version classique de la technologie GQ fait appel à la technologie RSA. Mais, si la technologie RSA dépend bel et bien de la factorisation, cette dépendance n' est. pas une équivalence, loin s ' en faut, comme le démontrent les attaques dites " multiplicatives " contre diverses normes de signature numérique mettant en _uvre la technologie RSA. to Dans le cadre de la technologie GQ2, la présente partie de 1'invention porte plus précisément sur l'utilisabon des eux de clés GQ2 dans le cadre de l'authentificahon dynamique et de la signature numérique. La technologie GQ2 ne fait pas appel à la technologie RSA. L'objectif est double: d'une part, améliorer les performances par rapport à la technologie RSA; d'autre part, éviter les problèmes inhérents à la tecologie RSA. La clé privee GQ2 est la factorisation du module n. Toute attaque au niveau de striplets GQ2 se ramène à la factorisation du module n: il y a cette fois équivalence. Avec la technologie GQ2, la charge de travail est réduite, tant pour l'entité qui signe ou qui s'authentifie que pour celle qui contrôle.Grâce à un meilleur usage du probléme de la factorisation, tant en sécurité qu'en * performance, la technologie GQ2 concurrence la technologie RSA. La technologie GQ2 utilise un ou plusieurs petits nombres entiers plus grands que 1, disons m petits nombres entiers (m 2 1) appelés " nombres de base " et notés par g. Les nombres de base étant fixés de g à gm avec m > 1, une cle publique de vérification (v, n) est choisie de la manière suivante. L'exposant public de vérification v est 2k o k est un petit nombre entier plus grand que 1 (k 2 2). Le module public n est le produit d'au moins deux facteurs premiers plus grands que les nombres de base, disons f facteurs premiers J2 2) notés parp" dep... Pr Lesf facteurs premiers sont choisis de façon à ce que le module public n ait les propriétés suivantes par rapport à chacun des m nombres de base de g, à gm. - D'une part, les équations (13 et (2) n'ont pas de solution en x dans l'anneau des entiers modulo n, c'est-à-dire que g,. et -g. sont deux résidus nouquadratiques(modn). x2_gi (mod n) (1) :: X2--gi (mod n) (2) D'autre part, I'équation (3) a des solutions en x dans l'anneau des entiers modulo n. X2 ag'2 (mod n) (3) La clé publique de vérification (v, n) étant fixée selon les nombres de base de g, à gm avec m 2 1, chaque nombre de base gi détermine un couple de valeurs GQ2 comprenant une valeur publique G' et une valeur privée Q..: soit m couples notés de G. Q. à Gm Qm La valeur publique G; est le carré du nombre de base gj: soit G; = gi2. La valeur pnvée Q est une des solutions à l'équation (3) ou bien l'inverse (mod n) d'une telle solution. De même que le module n se décompose enf facteurs premiers, l'anneau des entiers modulo n se décompose en f corps de Galois, de CG(p,) à CG(pf). Voici les projechons des équations (1), (2) et (3) dans CG(p,). - 20 x2 egi (mod p) (l.a) x2_-gi (mod pj) (2.a) x2 agi2 (modp,) (3.a) Chaque valeur privée Q; peut se représenter de manière unique par f composantes privées, une par facteur premier: Q,j -- Qi (mod p,). Chaque composante privée Qv est une solution à l'équation (3.a) ou bien l'inverse (mod p,) d'une telle solution. Après que toutes les solutions possibles à chaque équation (3.aj aient été calculées, la technique des restes chinois - permet d'établir toutes les valeurs possibles pour chaque valeur privée Q à partir defcomposantes de Qil à Qj,: Qi = Restes Chinois (Qi" Qi2,... Q.f) 2824974 - de manière à obtenir toutes les solutions possibles à l'équation (3). Voici la technique des restes chinois: soient deux nombres entiers positifs premlers entre eux a et b tels que O a b, et deux composantes Xa de O. à a-1 et Xb de O à b-l; il s'agit de déterrnmer X= Restes Chinois (XO, X", C 'est-à-dire, le nombre unique Xde O à a.b-l tel que Xa_X(moda)et Xb sX(mod b). Voici le paramètre des restes chinois: a - {b (mod a)}' (mod a). Voici l'opération des restes chinois: ú -- Xb (mod a); = Xa-ú Si est. négatif, remplacer par 6+a;y-. (mod a); X=. b +Xb. Lorsque les facteurs premiers sont rangés dans l'ordre croissant, du plus o pentp, au plus grand pp les paramètres des restes chinois peuvent être les suivants (il y en af-1, c'est-à-dire, un de moins que de facteurs premiers). Le: premier paramètre des restes chinois est a - {P2 (mod Pl)}-' (modp,). Le second pararnètre des restes chinols est, - {PI.P2 (mod p3)}-1 (mod p3) . Le i ième paramètre des restes chinois est \- {Pl-P2- ÀÀ Pi I (modp,}l (modpi). s Et ainsi de suite. Ensuite,enf-l opérations des restes chinois, on établit un premier résultat (modp2 fois Pl) avec le premier paramètre, puis, un second résultat (modpl.p2 fois p3) avec le second paramètre, et ainsi de suite, jusqu'àunrésultatmodp,.... pf foisp,),c'est-à-dire, (mod n). I1 y a plusieurs représentations possibles de la clé pnvée GQ2, ce qui traduit le polymorphisme de la clé privée GQ2. Les diverses représentations s'avèrent équivalentes: elles se ramènent toutes à la connaissance de la factorisation du module n qui est la véritable clé privée GQ2. Si la représentation affecte bien le comportement de l'entité qui siane ou qui s'authentifie. elle n'affecte pas le comportement de l'entité qui contrôle. Voici les trois principales représentations possibles de la clé privée GQ2. 1) La représentation classigue en technologie GQ consiste à stocker m valeurs privées Qj et la clé publique de vérification (v, n); en technologie GQ2, cette représentation est concurrencée par les deux suivantes. 2) La représentation optimale en termes de chares de travail consiste à stocker 36 2824974 - - l'exposant public -v, lesf facteurs premiers pj, m.f composantes privées Qi et f-1 paramètres des restes chinois. 3) La représentation optimale en termes de taille de clé privée consiste à stocker l'exposant public v, les m nombres de base gi et lesffacteurs premiers pj, puis, à commencer chaque utilisation en établissant ou bien m valeurs privées Qi et le module n pour se ramener à la première représentation, ou bien m.f composantes privées Q, et f-1 paramètres des restes chinois pour se ramener à la seconde. Les entités qui signent ou s'authentifient peuvent toutes utiliser les mêmes nombres de base, sanf contre indication, les m nombres de base de g, à gm o peuvent alors avantageusement être les m premiers nombres premiers. Parce que la sécurité du mécanisme d'authentification dynamique ou de signature numérique équivaut à la connaissance d'une décomposition du module, la technologie GQ2 ne permet pas de distinguer simplement deux entités utilisan t le même module. Généralement, chaque entité qui s'authentifie ou signe dispose de son propre module GQ2. Toutefois, on peut spécifer des modules GQ2 à quatre facteurs premiers dont deux sont connus d'une entité et les deux autres d'une autre. Voici unpremier jeu de clés GQ2 avec k = 6, soit-v = 64, m = 3, soit trois nombres de base: g = 3, g2 = 5 et g3 = 7, et.f = 3, soit un module à ois facteurs premiers: deux congrus à 3 (mod 4) et un à 5 (mod 8). Notons que g = 2 est incompatible avec un facteur premier congru à 5 (mod 8). p, = 03CD2F4F21EOEAD60266D5CFCEBB6954683493E2E833 P2 = 0583B097E8D8D777BAB3874F2E76659BB614F985EC 1B p3 = 0C363CD93D6B3FEC78EEI 3D7BE9D84354B8FDD6DA l FD - 25 n = p,.P2. p3 = FFFF81CEA149DCF2F72EB449CS724742FE2A3630D9 02CCOOEAFEElB957F3BDC49BE9CBD4D94467B72ÀF28CFBB26144 CDF4BBDBA3 C97578E29CC9BBEE8FB6DDDD Q. = 0279C60D216696CD6F7526E23512DAE09OCFF879FDDE Q2 1 = 7C977FC38F8413A284E9CE4EDEF4AEF3 SBF7793B89 37 2824974 Q3 = 6FB3B9COSA03D7CADA9A3425571EF5ECC54D7A7B6F Q. 2 = 0388EC6AAlE87613D832E2B80E5AE8ClDF2E74BFF502 Q2 2 = 04792CE70284D16E9A158C688A7B3FEAF9C40056469E Q3 2 = FDC4A8ES3E185A4BA793E93BEE5C636DA731BDCA4E: : 5 Q13 = 07BCIAB048A2EAFDABS9BD40CCF2F657AD8A6BS73BDE Q2 = 0AE8551E116A3AC089566DFDB3AE003CF174FC4E4877 Q3 3 = 01682D490041913A4EA5B80D16B685E4A6DD88070501 Q,=D7EiCAF28192CED6549FF457708D50A7481572DDSF2C335D8 C69É22521B51OB64454FB7A19AEC8D06985558E764C6991B05FC2A 0 C74D9743435AB4D7CFOFF6557 Q2=CBlED6BIDD649B89B9638DC33876C98AC7AF689E9DI359E4 DB17563B9B3DC582D5271949F3DBASA70C108F561A274405A5CB8 :82288273ADE67353ASBC316C093 Q3 =09 6F4930E51A70CCDFA77442B10770DDlCD77490E3398A AD9DC50249C34312915ES5917AlED4D83AA3D607E3EBSC8Bl97 : 697238537FE7A0195C5E8373EB74D: Voici un second jeu de clés GQ2, avec k = 9, soit v = 512, m = 2, soit dex : nombres de base: g, = 2 et g2= 3, etf= 3, soit un module à trots facteurs premiers congrus à 3 (mod 44. : : p,=03852103E40CD4F06FA7BAA9CC8D5BCE96E3984570CB p2=062AC9EC42AA3E688DC2BC871C8315GB939089B61DD7 p3 = 0BCADEC219FlDFBB8AB5FE808AOFFCBS3458284ED8E3 n =P,. P2. p3 = FFFF5401ECD9ES37F167A80COA91119$6F7A8EBA4D 6698AD68FF670DESD9D77DFF00716DC7539F7CBBCF969E73A0649 - 25 761B276A8E6B6977A21D51;669D039FID7 Q"=0260BC7243C22450D566B5C6EF74AA29F2B927AF68E1 Q2,=0326Cl2FC7991ECDC9BB8D7ClC4501BElBAE9485300E Q12 = 02DOB4CC95A2DD435DOE22BFBB29C59418306F6CDOOA Q2 2 = 045ECB881387582E7C556887784D2671CA118E22FCF2 À. 3g 2824974 - - Ql 3 = BOC2B lF808D24F6376E3A534EB555EF54E6AEF5982 2 3 = 0AB9F81DF462F58A52D937E6D81 F48PA4A87A9935AB Q. = 27F7B9FC82C 19ACAE47F3FE9560C3536A7E90F8C3C51 E13C F32FD8C6823DF753685DD63555D2146FCDB9B28DA367327DD6 s EDDA092DOCF108DOAB708405DAA6 Q2 = 230DOB9595E5AD388F lF447A69918905EBFB05910582E5BA64 :: 9C94BOB2661 E49DF3C9B42FEFlF37A7909B l C2DD54113ACF87C6 F1 lF19874DE7DC5DlDF2A9252D Authentification dynamique o Le mécanisme d'authentification dynamique est destiné à prouver à une entité appelée contrôieur l'authenticité d'une autre entité appelée démonstrateur ainsi que l'authenticité d'un éventuel message associé M, de sorte que le contrôleur s' assure qu'il s'agit bien du démonstrateur et éventuellement que lu et le démonstrateur parlent bien du rnême message M. Le message associé M est optionnel, ce qui signifie qu'il peut être vide. Le mécanisme d'authentification dynamique est une séquence de quatre actes: u acte d'engagement, un acte de défi, un acte de réponse et un acte de contrôle. Le démonstrateur joue les actes d' engagement et de réponse. Le contrôleur joue les actes de déft et de contrôle. Au sein du démonstrateur, on peut isoler un témoin, de manière à isoler les paramètres et les fonctions les plus sensibles du démonstrateur, c'est-à dire, la production des engagements et des réponses. Le témoin dispose du paramètre k et de la clé privée GQ2, c'est-à-dire, de la factorisation du module n selon l'une des trois representations évoquées ci-dessus: les f - 25 facteurs premiers et les m nombres de base, À les m. f composantes privées, lesf facteurs premiers etf-1 paramètres des restes chinois, les m valeurs privées et le module n. Le témoin peut correspondre à une réalisation particulière, par exemple, une carte à puce reliée à un PC formant ensemble le démonstrateur, ou 39 2824974 - - encore, des programmes particulièrement protégés au sein d'un PC, ou encore, À des programmes particulièrement protégés au sein d'une carte à puce. Le témoin ainsi isolé est semblable au témoin défini ci-après au seln du signataire. A chaque: exécution du mécanisme, le témoin produit un ou plusleurs engagementsR, puis, autant de réponses D à autant de défis d. Chaque ensemble {R. d,D} constitue un triplet GQ2. Outrequ'il comprend le témoin, le démonstrateur dispose également, le cas échéant, d'une fonction de hachage et d'un message M. Le contrôleur dispose du module n et des paramètres k et m; le cas échéant, 0 il dispose également de la même fonchon de hachage et d'un message M'. Le contrôleur est apte à reconstituer un engagement R' à partir de n'importe quel défi d et de n'importe quelle réponse D. Les paramèes k et m renseignent le contrôleur. Faute dindicahon contraire, les m nombres de base de g, à gm sont les m premiers nombres premiers. Chaque défi d doit comporter m défis élémentaires notés de d, à dm: un par nombre de base. Chaque défi élémentaire de d, à dm doit prendre une valeur de 0 à 2k-'-1 (les valeurs de v/2 à v-1 ne sont pas utilisées). Typiquement, chaque défi est codé par m fois k-l bits (et non pas m fois k bits). Par exemple, avec k = 6 et m = 3 et les nombres de base 3, 5 et 7, chaque défi comporte 15 bits trànsmis sur deux octets; avec k= 9, m = 2 et les nombres de base 2 et 3, chaque défi comporte 16 bits transmis sur deux octets. Lorsque les (k-l).m défis possibles sont également probables, la valeur (k-l).m détermine la sécurité apportée par chaque triplet GQ2: un imposteur qui, par déhinition, ne conna^t pas la factorisation du module n a exactement une chance de 2s succès sur 2k-"m. Lorsque (k-l).m vautde 15 à 20, un triplet sufft à assurer - raisonnablement l'authentification dynamique. Pour atteindre n'importe quel niveau de sécurité, on peut produire des triplets en parallèle; on peut également en produire en séquence, c'est-à-dire, répéter l'exécution du mécanisme. 2824974 - - 1) L'acte d'engagement comprend les opérations suivantes. Lorsque le témoin dispose des m valeurs privées de Ql à Qm et du module n, il. tire au hasard et en privé un ou plusieurs aléas r (O Voici un exemple avec le premier jeu de clés avec k = 6. : r = B8AD426C lAC0165E94B894AC2437C 1B 1797EF562CFA53A4AF8 43131FFlC89CFDA131207194710EF9COlOE8F09C60D9815121981260 919967C3E2FB4B4566088E R = FFDD736B666F41FB771776D9DSODB7CDF03F3D97647 lB25C56 D3AF07BE692CB iFE4EE70FA77032BECD8411B813B4C21210C:6B04 49CC4292E5DD2BDB00828AF 18 Lorsque le témoin dispose des f facteurs premiers de p, a pf et des mf lS composantes privées Q,, il tire au hasard ét en privé une ou plusieurs collechons de f aléas: chaque collection comporte un aléa r' par facteur premier pi (O ri P,); puis, par k élev:ations successives au carré (mod p) , il transforme chaque aléa ri en une composante d'engagement Ri. :: Ri-riV (modpi) Voici un exemple avec le second jeu de clés avec k = 9. rl = B04I8EABEBADF0553A28903F74472CD49EE8C82D86 R. = 022B365FOBEA8E157E94A9DEB0512827FFD5149880F 1 r2 = 75A8DA8FEOE60BDSSD28A218E31347732339F 1D667 : R2 = 057E43A242C485FC20DEEF291 C774CF lB30F0163DEC2 r3 = 0D74D2BDAS302CF8BE2F6D406249D148C6960A7D27 R3 = 06E14C8FC4DD312BA3B475FlF40CFO lACE2A88D5BB3C : Pour chaque collection def composantes d' engagement, le témoin établit un engagement selon 1 a technique des restes chinois. Il y a autant d' engagements que le collections d' aléas. 41 2824974 - -..:. R = Restes Chinois(RI'R2, R) R = 28AA7F 12259BFBA81368EB49C93EEAB3F3EC6BF73BOEBD7 D3FC;8395CFAI AD7FCOF9DAC169A4F6F l C46FB4C3458D lE37C9 9123BS6446F6C928736B 17B4BA4A529 s Dans les deux cas, le démonstrateur transmet au contrôleur tout ou partie de chaque engagement R. ou bien, un code de hachage H obtenu en hachant chaque engagement R et un message M. 2) L'acte de défi consiste à tirer au: hasard un ou plusieurs défis d composés chacun de m défis élémentaires 1, â2... dm; chaque déf o élémentaire prend l'une des valeurs de O à v/2-l. d= d d2 À m Voici un exemple pour le premier jeu de clés avec k = 6 et m = 3. d,= 10110=22='16';d2=OOlll =7;d3=00010=2, : d =0 | d, I d2 d3=O1011000 11100010= 58 E2 i5: Voici un exemple pour le second jeu de clés avec k = 9 et m = 2. d = d, d2 = 58 E2 = soit en décimal, 88et 226 : Le contrôleur transmet au démonstrateur chaque défi d. : 3) L'acte de réponse comporte les opérations.suivantes. : Lorsque le témoin dispose des m valeurs privées de Q. à Qm et du module n, il calc.ule une ou plusieurs réponses D en utilisant chaque aléa r de l'acte d'engagement et les valeurs privées selon les défis élémentaires. x_Qdi Q42...Qâm (mod n) D_r.X (mod n) Voici un exemple pour le. premier jeu de clés. - s D = FF257422ECD3C7A03706B9A7B28EE3FC3A4E974AEDCDF386 SEEF38760B859FDBS333E9O4BBDD37BO97A989F69b85FE8EF6480 A2C6A29O273479FEC' 1 7 l 99OA 17 Lorsque le témoin dispose des f facteurs premiers de p, à p, et des mf composantes privées Q4, il calcule une ou plusieurs collections de f 42 2824974 - composantes-de réponse en utilisant chaque collection d'aléas de l'acte d'engagement: chaque collection de composantes de réponse comporte une composante par facteur premier. Xi - Ql À ?2d,2,.. Qmmi (mod Pi) Di - ri.Xi (mod Pi) Voici un exemple pour le second jeu de clés. D, = r,. Q" Q2, (m: odp) = 02660ADF3C73B6DC 15E196152322DDE8EB5B35775E38 D2 = r2. Q2 À Q22 (modp2) 04C15028ESFD1175724376C1 lBE77052205F7C62AE3B D3= r3. Q,3. é23 (mOdP3) = 0903D20DOC306C8EDA9D8FB5B3BEB55E061AB39CCF52 Pour chaque collection de composantes de réponse, le témoin établit une réponse selon la technique des restes chinois. I1 y a autant de réponses que de défis. D = Restes Chinois(D, D2,... Df) D = 85C3B00296426E97897F73C7DC6341FB8FFE6E879AE 12EF 1F36 4CBB55BC44DEC437208CFS30F8402BD9CS l l FSFB3B3A309257AOO A7305C6FF3323F72DC1AB Dans les deux cas, le démonstrateur transmet chaque réponse D au contrôleur. 4) L'acte de contrôle consiste à contrôler que chaque triplet {R. d, D} vérifie une équation du type suivant pour une valeur non nulle, R.n[Gi sD2 (mod nj oubien RzD2.1[l[Gait (mod n) i=1 i=1 2s ou bien, à rétablir chaque engagement: aucun ne doit être nul. : k m k m R'-D2 /nG4i (mod n) oubien R'-D2.Gii (mod n) i=1 i=1 Eventuellement, le contrôleur calcule ensuite un code de hachage H' en 43 2824974 -: -;: hachart chaque engagement rétabli R ' et un message M'. L'auentificatlon dynamique est réussie lorsque le contrôleur retrouve ainsi ce qu'il a reçu à l' issue de l'acte d'engagement, c'est-à-dire, tout ou parue de chaque : engagement R. ou bien, le code de hachage H. Pax exemple, une séquence d'opérations élémentaires transforme la réponse : D en un engagement R '.: La séquence comprend k carrés (mod n) séparés par k-1 divisions ou multiplications (mod n) par des nombres de base. Pour la i ième division ou muluplication, qui s'effect:ue entre le i ième carré et le i+1 ième carré, le i ième bit du défi élémentaire d, indique s'il faut utiliser o gl, le i ième bit du défi élémentaire d2 indique s'il faut utiliser g2, jusqu'au i ième bit du défi élémentaire dm qui indique s'il faut utiliser gm. :Voici un exemple pour le premier jeu de clés. D2 (mod n) = FD 12E8ElFi 370AEC9C7BA2E05C80AD2B692D341D46F3 2B93948715491 FOEB09lB7606GAlE744E0688367D7BB998F7B73DSF7 FDA95DSBD6347DC8B978CA217733 3. D2(mod n) = F739B708911166DFE715800D8A9D78FC3F332FF6221D 3EAB8E7977C6&ÀD44962BEE4DAE3 C0345D lCB34526D3B67EBE8BF ::: 98704 lB4852890D83FC6B48D3EF6A9DF 32. D4 (mod n) = 682A7AF280C49FE230BEE354BF6FFB30B7519E3C8 92DD07E5A781225BBD33920E5ADABBCD7284966D7114IEAA17AF 8826635790743EA7D9A15A33ACC7491D4A7 34. D8 (mod n) = BE9D828989A2C184E34BA8FEOF384811642B7BS48F 870699E7869F8ED85 lFC3DB3830B2400CS 1651 lAOC28AFDD210EC3 939E69D413FOBABC6DEC441974B lA291 35. 5. Dé (mod n) = 2B40122E225CD858B26D27B768632923F2BBE5 DB 1 SCA9EFA77EFA667E554A02AD lA1 E4F6B59BD9E1 AE4A537D 4AC lE89C2235C363830EBF4DB42CEA3DA98CFEOO 3' . 52. D6 (mod n) = BDD3B34C9OABBC870C604E27E7F2E9DB2D383 G8EA46C931 C66F6C7509B 118E3C162811Ag81 G9C30D4DEF768397DD 44 2824974 I- - B8F6526B67142 18DEB627EllFACA4B9DB268 3".53.7. D'6 (mod n)= DBFA7F40D338DE4FBA73D42DBF427BBF195 C13D02ABOFA5F8C8DDB5025E34282311CEF80BACDCE5DOC433444 : A2AF2B153I8C36FE2AE02F3C8CB25637C9AD712F : s 322. 56. 72. D32 (mod n)= C60CA9C4AllF8AA89D9242CE717E3DC6C1 . A95D5D09A2278F8FEElDFD94EE84D09DOOOEA8633B53C4AOE7FOA EECB70509667A3CB052029C94EDF27611FAE286A7 : 322.57.72. D32 (mod n)= DE40CB6B41COlE722E4F312AE7205FI8CDD 0303EA52261CBOEA9FOC7EOCDSEC53D42E5CB645B6BB1A3BOOC77 : 886F4AC5222F9C863DACA440CF5FlA8E374807AC 344 5'4.74. D64 (mod n), c'està-dire, 32C. 5. 7. D (mod n) avec les exposants en hexa = FFDD736B666F4lFB771776D9DSODB7CDF03F3D9 76471B25C56D3AF07BE692CBlFE4EE70FA77032BECD8411B813B4C 21210C6B0449CC4292E5DD2BDB00828AF18: Is On retrouve bien l'engagement R. L'authentification est réussie. : Voici un exemple pour le second jeu de clés. D2 (mod n) = C66E585D8F132F7067617BC6DOOBA699ABD74FB9D13E :24E6A6692CC8D2FC7BS7352D66D34FS273C13F20E3FAA228D70AEC 693F8395ACEF9206B172A8A2C2CCBB : 20 3.D2 (mod n) = 534C6114D385C3E15355233CSBOOD09C2490DlB8D8E D3D59213CB83EAD41C309A187519E5F501C4A45C37EB2FF38FBF20 lD6D138F3999FClD06A2B2647D48283 32. D4 (mod n) = A9DC8DEA867697E76B4C18527DFFC49F4658473D03 4ECLDDEOEB21F6F65978BE477C423lAC9BIEBD93D5D49422408E47: 15919023B16BC3C6C46A92BBD326AADF 2.33. D4 (mod n) = FB2D57796039DFC4AF9199CAD44B66F257AlFF 3F2BA4C12BOA8496A0148B4DFBAFE838EOBSA7D9FB4394379D72A : 107E45CSlFCDB7462D03A35002D29823A2BB5 22. 36. D (mod n) = 4C210Fg6FF6C77541gl0623B1E4g533206DFB9E91 2824974 652lF305F12C5DB054D4ElBF3A37FA293854DF02B49283B6DE5ESD 82ACB23DAFlAOD5A721A1890D03AOOBD8 22.37.D8(modn) =E4632EC4FE4565FC4B3126Bl5ADBF996149F2D BB42F65D9llD385191OFE7EAS3DAEA7EE7BA8FE9D08lDB78B249 - BlB18880616B9OD4E280F564E49B270AE02388 24. 314.DI6 (mod n) =ED3DDC716AE3DlEA74C5AF935DE814BCC 2C78B12A6BB29FA542F9981C5D954F53D153B F0198BA82690EF 665C17C399607DEAS4E218C2COlA890D422EDA16FA3 : 2s I. 3'4.D'6(modn) =DA7C64EOE8EDBE9CF823B71ABl3Fl7El1614g7 lo 6BOOOFBB473F5FCBFSASD8D26C7B2AOSD03BDDD588164E562DOF5 7AE94AEOAD3F35C61C0892F4C9lDCOB08ED6F 21 .328.D32(modn) =6ED6AFCSA87D2DDl17BOD89O72CggFBgDCg SD558F65B6A1967E6207D4ADBBA32001D3828A35069B256A07C3D 722F17DA30088E6E739FBC419FD7282D16CD6542 :: 2".328.D32 (mod n)=DDADSF8B50FA5BA22F61Bl20ES933F73B92 BAABlECB6D432CFCC40FA95B77464003A705146AOD364AD40F8 7AE45E2FB460111CDCE73F78833FAESOSA2D9ACA84 222.356.D64(modn)=A466DOCBl7614EFD961000BD9EABF4FO21 36F8307101882Bé1764DBAACB715EFBF5D8309AEOOlEB5DEDA 8F0OOE44B3D4578ESCA55797FD4BDlF8E919BE787BDO 2.3'l2.Dl28(modn) =925BOEDFS047EFECSAFABDCO3A8309l9761 B8FBDD2BF934E2A8A3lE29B976274DS13007EF1269E4638B4F65F 8FDEC740778BDC178AD7AF2968689B930D5A2359 2". 3i'3.D'28(modn):=B711D89CO3FDEA8DlF889134A4F809B3F2D 8207F2AD8213D169F2E99ECEC4FE08038900FOC203B55EE4F4C803 BFB912A04FllD9DB9D076021764BC4FS7D47834: 288.3226.D256 (mod n) =4lA83Fll9FFE4A2F4Ac7E55g7A5DoBEB4D4c 08D19E597FD034FE720235894363A19D6BCSAF323D24BlB7FCFD8D FCC62802lB4648D7EF757A3E461EFOCFFOEA13 46- 2824974 276 3452 D5'2 (mod n), soit 48a. g226. D52 (mod n) = 287F12259BFBA8 1 3 68EB49C93EEAB3F3EC6BF73BOEBD7D3EC8395CFA l AD7FCOF9D AC 1 69A4F6F1 C46FB4C3458DlE37C99l 23B56446F6C928736B 17B4BA 4A529 s On retrouve bien l'engagement R. L'authentifcation est réussie. Signature numérique Le mécanisme de signature numènque permet à une entité appelée signataire de produtre des messages signés et à une entité appelée contrôleur de vérifier des messages signés. Le message M est une séquence to binaire quelconque: il peut être vide. Le message M est signé en lui adjoignant un appendice de signature qui comprend un ou plusieurs engagements et / ou défis, ainsi que les réponses correspondantes. Le contrôleur dispose de la même fonction de hachage, des paramètres k et m et du module n. Les paramètres k et m renseignent le contrôleur. D'une s part, chaque défi élémentaire, de d, à dm, doit prendre une valeur de 0 à 2k-- : 1 (les valeurs de v/2 à - 1 ne sont pas utilisées). D'autre part, chaque défi d doit comporter m défis élémentaires notés de d-, à dm, autant que de nombres de base. En outre, faute d' indication contraire, les -m nombres de base, de g, à gm, sont les m premers nombres premiers. Avec (k-l).m valant de 15 à 20, on peut signer avec quatre triplets C}Q2 produits en parallèle; avec (k-l).m valant 60 ou plus, on peut signer avec un seui triplet GQ2. Par exemple, avec k= 9 et m = 8, un seul triplet GQ2 suffit; chaque défi comporte huit octets et les nombres de base sont 2, 3, 5, 7, 11, 13, 17 et 19. L'opération de signature est une séquence de trois actes: un acte - 25 d' engagement, un acte de défi et un acte de réponse. Chaque àcte produit un ou plusieurs triplets GQ2 comprenant chacun: un engagement R (= 0), un défi d composé de m défis élémentaires notés par d" d2,... dm et une réponse D (= 0). Le signataire dispose d'une fonction de hachage, du paramètre k et de la clé 47 2824974 - privée GQ2, c'est-à-dire, de la factorisation du module n selon 1'une des trois représentations évoquées ci-dessus. Au sein du signataire, on peut isoler un témoin qui exécute les actes d' engagement et de réponse, de manière à isoler les fonctions et les paramètres les plus sensibles du démonstrateur. Pour calculer engagements et réponses, le témoin dispose du paramètre k et de la clé privée GQ2, c'est-à-dire, de la factorisation du module n selon l'une des trois représentations évoquées ci-dessus. Le témoin ainsi isolé est semblable au témoin défini au sein du démonstrateur. Il peut correspondre à une iréalisation particulière, par exemple, À une carte o à pucereliéeà un PC formant ensemble le signataire, ou encore, Àdes programmes particulièrement protégés au sein d'un PC, ou encore, des prograrnmes particulièrement protégés au sein d'une carte à puce. 1) L'acte d'engagement comprend les opérations suivantes. Lorsque le témoin dispose des m valeurs privées de Q. à ém et du module n, tire au hasard et en prvé un ou plusieurs aléas r (0 il transforme chaque aléa r, en une composante d'engagement Ri. Ri--rV (mod pi) Pour chaque collection def composantes d' engagement, le témoin établit un engagement selon la technique des restes chinois. I1 y a autant d' engagements que de collections d'aléas. R = Restes Chinois(R" R2,... Rf) 2) L'acte de défl consiste à hacher tous les engagements R et le message à 48- 2824974 : signer M pour obtenir un code de hachage à partir duquel le signataire forme un ou plusieurs défis comprenant chacun m défis élémentaires, chaquedéfi élémentaireprend une valeur de O à v/2-1, par exenple, avec k= 9 et m = 8, chaque défi comporte huit octets. I1 y a autant de déhis que d' engagements. d - d, d2... dm' extraits du résultat Hash(M, R) 3) L'acte de réponse comporte les opérations suivantes. Lorsque la témoin dispose des m valeurs prlvées de Ql à Q et du module n, il calcule une ou plusieurs réponses D en utilisant chaque aléa r de l'acte o d'engagement et les vileurs privées selon les défis élémentaires. x-Qd.Q42 Qaim (mod n) D - r.X (mod n) Lorsque le témoin dispose des f facteurs premiers de p à pf et des m.f composantes privées Q,, il calcule une ou plusieurs collections de f s composantes de réponse en:utilisant chaque collection d'aléas de l'acte d'engagement: chaque collection de composantes de réponse comporte une composante par facteur premier. Xi-- Q i ÀQ2,2, Qm,mi (mod Pi) Di-ri.Xi (mod Pi) Pour çhahue collection de composantes de réponse, le témoin établit une réponse selon la technique des restes chinois. I1 y a autant de réponses que de défis. D = Restes Chinois(D, D2, D,) Le signataire signe le message M en lui adjoignant un appendice de signature comprenant: - ou bien, chaque triplet GQ2, c'est-à-dire, chaque engagement R. chaque défi d et chaque réponse D, - ou bien, chaque engagement R et chaque réponse D correspondante, - ou bien, chaque déf d et chaque réponse D correspondante. 49 2824974 Le déroulement de l'opération de vérification dépend du contenu de I'appendice de signature. On dlstingue les trois cas. Au cas o l'appendice comprend un ou plusieurs triplets, l'opération de contrôle comporte deux processus indépendants dont la chronologie est s indifférente. Le contrôleur accepte le message signé si et seulement si les deux conditions suivantes sont remplies. D'une partj chaque triplet doit étre cohérent (une relation appropnée du type suvant doit être vérifiée) et recevable (la comparaison doit se faire sur une valeur non nulle). o RrIGi sD2 (mod n) oubien R-D2.0Gié, (mod n) i=!:: i=!: Par exemple, on transforme la réponse D par une séquence d'opérations élémentaires: k carrés (mod n) séparés par k-1 multiplications ou divisions (mod n) par; des nombres de base. Pour la i ième multiplication ou division, qui s'effectue entrele i ième carré et le i+1 ième carré, le i ième bit du défi is élémentaire d indique s'il faut utiliser g, le i ième bit du défi élémentaire d2 i ndique s'il faut utiliser g2,... jusqu'au i ième bit du défi élémentaire dm qui indique s?il faut utiliser gm. On doit ainsi retrouver chaque engagement R présent dans l'appendice de signature. D'autre part, le ou les triplets doivent être liés au message M. En hachant tous les engagements R et le message M, on obtient un code de hachage à partir duquel on doit retrouver chaque défi d. d = d, d2... dm, identiques à ceux extraits du résultat Hash(M, R) Au cas o l'appendice ne comprend pas de d:efi' l'opération de contrôle commence par la reconstitution de un ou plusieurs déf;s d ' en hachant tous les engagements R et le message M. d ' = d ' d '2... d m' extraits du résultat Hash(M, R) Ensuite, le contrôleur accepte le message signé si et seulement si chaque triplet est cohérent (une relation appropriée du type suivant est vénfée3 et recevable (la comparaison se fait sur une valeur non nulle). m. k m R.0Gii eD2 (mod n) oubien R-D2.0Gii (mod n) i=1 i=1 Au cas o l' appendice ne comprend pas d'engagement, l' opération de contrôle commence par la reconstitution de un ou plusieurs engagements R ' sélon une des deux formules suivantes, celle qui est appropriée. Aucun engagement rétabli ne doit être nul. m m R'_D2 /0Géi (mod n) oubien Ri_D2.Il[Gari (mod n) i=1; i=1 Ensuite, le contrôleur doit hacher tous les engagements R' et Ie message M de façonà reconstituer chaque défis d. to d = d, d2... dm, identiques à ceux extraits du résultat Hash(M? R Le contrôleur accepte le message signé si et seulement si chaque déh reconstitué est identique au défi correspondant figurant en appendice. : : Dans la présente demande, on a montré qu'il existait des couples de valeurs privée Q et publique G permettant de mettre en _uvre le procèdé, le système et le dispositif selon l'invention destiné à prouver l'authentieité d'une entité etlou l'intégrité (et/ou l'authenticité d'un message. Dans la demande pendante déposée le méme j our que la présente demande parFrance Télécom, TDF et la Société Math RiZK et ayant pour inventeurs Louis Guillou et Jean-Jacques Quisquater, on a décrit un procédé pour produire des jeux de clés GQ2, à savoir, des modules n et des couples de valeurs publique G et privée Q dans le cas o l'exposant v est égal à 2k. Elle est incorporée ici par référence. 51 2824974 - - - Revendications: : 1. Procédé destmé à prouver à une entité contrôleur, - l'authenticité d'une entité et/ou - l'intégrité d'un message M associé à cette entité, : s au moyen de tout ou partie des paramètres suivants ou dénvés de ceuxci:: - m couples de valeurs privées Q, Q2,.. Qm et publiques G, G2, Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers P1, P2, À. pf (f étant supérieur ou égal à 2), - un exposant public v; ledit module, ledit exposant et lesdites valeurs étant liés par des relations du :: type: Gi.Q,V_l. modnouGi_QjVmodn; ledit exposant v étant tel que:: : v = 2: o k: est un paramètre de sécurité plus grand que 1; ladite valeur publique Gi étant le carré gi2 d'un nombre de base gj inférieur aux f facteurs premiers p, P2,... pf; le nombre de base gi étant tel que: les deux équations: x2 - gi mod n et x2 - - gi mod n n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: l'équation: x - gi2 mod n a des soluhons en x dans I'anneau des entiers modulo n; ledit procédé met en ceuvre selon les étapes suivantes une entité appelée témoin disposant des f facteurs premiers Pi et/ou des paramètres des restes chinois des facteurs premiers et/ou du module public n et/ou des m valeurs privées Qi et/ou des f.m composantes Qi j (Q; j - Qi mod pj) des valeurs 52- 2824974 privées Qiet de l'exposant public v; - le témoin calcule des engagements R dans l'anneau des entiers modulo n; chaque engagement étant calculé: À soit en effectuant des opérations du type R-rVmodn o r est un aléa tel que O c r triplet noté {R. d, D}. 2. Procédé selon la revendication 1 destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur, ladite entité démonstrateur comprenant le témoin, lesdites entités démonstrateur et contrôleur exécutant les étapes suivantes: À étape 1: acte d'engagement R - 53 2824974 - - à chaque appel,-le témoin calcule chaque engagement R en appliquant le processus spécifié selon la revendication 1, - le démonstrateur transmet au contrôleur tout ou partie de chaque engagement R. À étape 2: acte de défi d - le contrôleur, après avoir reçu tout ou partie de chaque engagement R. produit des défis d en nombre égal au nombre d' engagements R et transmet les défis d au démonstrateur, À étape 3: acte de réponse D le témoin calcule des réponses D à partir des défis d en appliquant le processus spécifé selon la revendication 1, À étape 4: acte de contrôle le démonstrateur transmet chaque réponse D au contrôleur, cas:o le démonstrateur a transmis une partie de chaque engagement R dans le cas o le démonstrateur a transmis une partie de chaque engagement R. le contrôleur, disposant des m valeurs publiques G, G2, Gm' calcule à partir:de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R' _G d G d2.... Gm dm. DV mod n ou a une relation dutype, R'-Dv / G d' G2 d2.... Gm dm. mod n, le contrôleur vérife que chaque engagement reconstruit R' reproduit tout ou partie de chaque-engagement R qui lui a été transmis,: cas o le démonstrateur a transmis l'intégralité de chaque engagement - 25 R: dans le cas o le démonstrateur a transmis l'intégralité de chaque engagement R. le contrôleur, disposant des m valeurs publiques G" G2, Gm, vérifie que chaque engagement R satisfait à une relation du type: R-G dl G2 d2.... Gm dm. Dv mod n l' 54," ou aune relation du type, R _ Dv / G d' G2 d2.... Gm dm. mod n. 3. Procédé selon la revendication 1 destiné à prouver à une entité : appelée contrôleur l'intégrité d'un message M associé à une entité appelée démonstrateur, ladite entité démonstrateur comprenant le témoin; lesdites entités démonstrateur et contrôleur exécutant les étapes suivantes: : À étape 1: acte d'engagementR - à chaque appel, le témoin calcuIe chaque engagement R en appliquant le processus spécifé selon la revendication 1, À étape 2: acte de défi d - le démonstrateur applique une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R pour calculer au moins un jeton T. - le démonstrateur transmet le jeton T au contrôleur, - le. conhôleur, aprés avoir reçu un jeton T. produit des défs d en nombre égal au nombre d'engagements R et transmet les défis d au démonstrateur, : À étape 3: acte de réponse D - le témoin calcule des réponses D à p:artir des défis d en appIiquant le processus spécifié selon la revendication 1,:: À étape 4: acte de contrôle - le démonstrateur transmet chaque réponse D au contrôleur, - le contrôleur, disposant des m valeurs publiques G, G2, Gm, calcule à : partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: -: - 25 R.-G d! G d2 G dm. Dv mod n ou à une relation du type: R' _ DY / G dl, G2 d2.... Gm dm. mod n puis Ie contrôleur applique la fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement reconstruit R' pour reconstruire le jeton T',: : - puis le contrôleur vénle que le jeton T' est identique au jeton T transmis. 4. Procédé selon la revendication 1 destiné à produire la signature numérique d'un message M par une entité appelée entité signataire, ladite entité signataire comprenant le témoin; :: Opération de signature ladite entité signataire exécute une opération de signature en vue : d'obtenir un message signé comprenant: - le message M,: - les déhs d et/ou les engagements R. : - les réponses D; ladite entité signataire exécute l'opération de signature en mettant en oeuvre les étapes suivantes: À étape lt: acte d'engagement R :- à chaque appel, le témoin calcule chaque engagement R en appliquant le processus spécifié selon la revendication 1, À étape 2: acte de défi d: - le signataire applique une fonction de hachage h ayant comme arguments le message M et chaque engagement R pour obtenir un train binaire, - le signataire extrait-de ce train binaire des défis d en nombre égal au nombre d' engagements R.: À étape 3: acte de réponse D : - le témoin calcule des réponses D à partir des défis d en appliquant le : :: processus spécifiéselonlarevendication 1. - 25 5. Procédé selon la revendication 4 destiné à prouver l'authenticité du message M en contrôlant, par une entité appelée contrôleur, le message signé, Opération de contrôle ladite entité contrôleur disposant du message signé exécute une opération 56 2824974 de contrôle en procédant comme suit: À cas o le contrôleur dispose des engagements R. des defis d, des réponses D, dans le cas o le contrôleur dispose des engagements R. des défis d, des réponses D, :. À le contrôleur vénfie que les engagements R. les défis d et les réponses D satisfont à des relations du type R--G dl G d2... Gm dm. Dv ou à des relations du type:: R_DVJGldl.G2d2 Gmdm. mod n À. le contrôleur vérifie que le message M? les déhis d et les engagements R satisfont à la fonction de hachage d =:h (message, R) À cas:o le contrôleur dispose des défis d et des réponses D dans le cas o le contr81eur dispose desdétis d et des réponses D, : À À le contrôleur: reconstruit, à partir de chaque défi d et de chaque réponse D, des engagements R' satisfaisant à des relations du type: R-G dI G2 d2.... Gm dm. Dv mod n : ou à des relations du type: -- R'-Dv / G dl G2 d2 Gm dm. mod n À le contrôleur vérifie que le. message M et les déLis d satisfont à la fonction de hachage : d = h (message, R') À cas o le contrôleur dispose des engagements R et des réponses D dans le. cas o le contrôleur dispose des engagements R et des réponses D, À À le contrôleur applique la fonction de hachage et reconstruit d': d' = h (message, R) À. le contrôleur vérifie que les engagements R. les défis d' et les réponses D' satisfont à des relations du type: R_ G d'l G d'2.... Gm d'm. Dv mod n ou à des relations du type: R _ Dv 1 G d'! G d'2 G. d'm mod n : 6. Système destiné à prouver à un serveur contrôleur, l'authenticité d'une entité et/ou - l'intégrité d'un message M associé à cette entité, au moyen de tout ou partiedes paramètres suivants ou dérivés de ceux-:ci: - m couples de valeurs privées Q, Q2, *. Qm et publiques G, G2, Gm (m étant supérieur ou égal à 1), : 10::- un module public n constitué par le produit de f facteurs premiers P, Pi, À. P (f étant supéneur ou égal à 2), - un exposant public v, ledit module, ledit exposant: et lesdites valeurs étant liés par des relations du type:: G.'. Qjv - I. mod n ou Gi - Qiv mod n; ledit exposant v étant tel que: v=2k o k est un paramètre de sécurité plus grand que 1; ladite valeur publique G; étant le carré gi2 d'un nombre de base gi inférieur aux f facteus premiers p', P2' pf; le nombre de base gi étant tel que: les deux équations:: x2 g; mod n et x2 - gi mod n n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: l'équation: xV-g; mod n a des solutions en x dans l'anneau des entiers modulo n; ledit système comprend un dispositif témoin, notamment contenu dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, le dispositif témoin comporte : - une zone mémoire contenant Ies f facteurs premiers Pi et/ou les paramètres des restes chinols des facteurs premiers et/o le module public n et/ou les m valeurs privoes Q; etlou les f.m composantes Qi, j (Qi j -- Q mod pj) des valeurs privées Qj et l'exposant public v;:: ledit dispositif témoin comporte aussi: - des moyens de production d'aléasj ci-après désignés les moyens de production d'aléas du dispositif témoin, des moyens de calcul, ci-après désignés les moyens de calcul des engagements R du disposltif témoin, pour calculer des engagements R dans I'anneau des entiers modulo n; chaque engagement étant calculé: : soit en effectuant des opérations du type R _ rV mod n o r est un aléa produit par les moyens de production d'aléas, r étant tel queO 59 2824974 - - À- soit en effectuant des opérations du type: D-r Q dl Q d2... Qm dm mod n À soit en effectuant des opérations du type: : - Di a ri Qi d À Qi2 d2- --- Qim d mod P puis en appliquant la méthode des restes chinois, des moyens de transmission pout transmettre un ou plusieurs engagements R et une ou plusieurs réponses D; il y a autant de réponses D que de défis d que d' engagements R. chaque :groupe de nombres R. d, D constituant un triplet noté {R. d, D}. 7. Système selon la revendication 6 destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur, ledit système étant tel qu'il comporte : - un dispositif démonstrateur associé à l'entité démonstrateur, ledit dispositif démonstrateur étant interconnecté au dispositif témoin par des moyens d'interconnexion et pouvant se présenter notamment sous la forme de microclrcuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur, - un dlspositif contrôleur associé à l'entité contrôleur, ledit dispositif : contrôleur se présentant notamment sous la forme d'un termina ou d'un serveur distant, ledit dispositif contrôleur comportant des moyens de : connexion pour le connecter électriquement, électromagnétiquement, ::: optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif démonstrateur, ledit système permettant d'exécuter les étapes suivantes: - 25 À étape 1: acte d'engagement R : à chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié selon la revendication 1, le dispositif témoin comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif démonskateur, via les moyens d'interconnexion, le dispositif démonstrateur comporte aussi des moyens de transmission, ci après désignés les moyens de transmission du démonstrateur, pour transmettre tout ou partie de chaque engagement R au dispositif contrôleur, va les moyens de connexion; À étape 2: acte de défi d le dispositif contrôleur comporte des moyens de production de déf s pour : 10 produire,aprés avoir reçu tout ou partie de chaque engagement R. des défis d en nombre égal au nombre d' engagements R. : le dispositif contrôleur comporte aussi des moyens de transmission, ci-aprés désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion; À étape 3: acte de réponse D les moyens de réception des défis d du dispositif témoin, reçoivent chaque défi d provenant du dspositif démonstrateur, via les moyens d'interconnexion, les moyens de calcul des:réponses D du dispositif témoin, calculent les réponses D à partir des défis d en appliquant le processus spécifié selon la revendication 1,: : À étape 4: acte de contrôle les moyens de transmission du démonstrateur transmettent chaque réponse D au contrôleur, - 25 le dispositif contrôleur comporte aussi - des moyens de calcul, ciaprès désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur, : cas o le démonstrateur a transmis une partie de chaque engagement R dans le cas o les moyens de transmission du démonstrateur ont transmis : une partie de chaque engagement R. les moyens de calcul du dispositl f contrôleur, disposant des m valeurs publiques G1, G2,... Gm, calculent à partir de chaque déf1 d et de chaque réponse D un engagement reconstruit R' satisfalsant à une relation du type: R.-G1 dl. G2 d2..,. Gm dm, DV mod n ou à une relation du type,: R. _ Dv / Gl dl, G2 d2.,,. Gm dm, mod n, les moyens de comparaison du dispositif contrôleur comparent chaque engagement reconstruit R' à tout ou partie de chaque engagement R reçu, cas ob le démonstrateur a transmis l'intégralité de chaque engagement R: dans le cas o les moyens de transmission du démonstrateur ont transmis l'intégralité de chaque engagement R. les moyens de calcuI et les moyens : de eomparaison du dispositif contrôleur, dsposant des m valeurs publiques G., G2,... Gm' vérifient que chaque engagement R satisfait à une relation du type: : R _ G1 dl, G2 d2,... Gm dm, Dv mod n ou à une relation du type, R-Dv / G1 dl. G2 d2.... Gm dm. mod n.: : 8. Système selon la revendication 6 destiné à prouver à une entité appelée contrôleur L'intégrité d'un message M associé à une entité appelée démonstrateur, ledit système étant tel qu'il comporte - un dispositif démonstrateur associé à l'entité démonstrateur, ledit dispositif démonstrateur étant interconnecté au dispositif témoin par des moyens djinterconnexion et pouvant se présenter notamment sous la forme de microcircuits logiques dans un objet nomade par exemple sous la :- - forme d'un microprocesseur dans une ca:rte bancaire à microprocesseur, - un dispositif contrôleur associé à l'entité contrôleur, ledit dispositif contrôleur se présentant notamment sous la forme d'un terminal ou d'un serveur distant, ledit.dispositif contrôleur comportant des moyens de connexion pour le connecter électriquement; électromagnétiquement, : optiquement ou de manière acoustique, notamment via: un réseau de communication informahque,: au dispositif démonstrateur; ledit système permettant d'exécuter les étapes suivantes: : À étape 1: acte d'engagement R: : 10 à chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié selon la revendication 1, le dispositif témoin comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif témoin, pour transmettre tout ou i5 partie de chaque:engagement R au dispositif démonstrateur, via les moyens d'interconnexion,; À étape 2: acte de défi d le dispositi f démonstrateur c omp orte de s moyens de calcul, c i- après : désignés les moyens de calcul du démonstrateur, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chàque engagement R. pour calculer au moins un jeton T. le dispositif démonstrateur comporte aussi des moyens de transmission, ci - après désignés les moyens: de transmission du dispositif démonstrateur, : pour transmettrè chaque jeton T. via les moyens de connexion, au dispositif contrôleur, le dispositif contrôleur comporte aussi des moyens de production de déhis pour produire, après avoir reçu le jeton T. des défis d en nombre égaI au nombre d' engagements R. le dispositif contrôleur comporte aussi des moyens de transmission, ci-après - désignés lesmoyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion; À étape 3: acte de réponse D les moyens de réception des défis d du dispositif témoin, reçoivent chaque: S défi d provenant du dispositif démonstrateur, via les moyens : d'interconnexion, les moyens de calcul des réponses D du dispositif témoin, calculent les À: réponses D à partir des défis d en appliquant le processus spécifié selon la revendication 1, À étape 4: acte de contrôle les moyens de transmission du démonstrateur transmettent chaque réponse: D au contrôleur,: le dispositif contrôleur comporte aussi des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, disposant des m valeurs publiques G" G2, Gm, pour d'une part, calculer à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R.-G dl d2 G. dm Dv d = 1 ÀG2 À.. m. mo n ou à une relation du type: : 20: R' _DV jG dl G2 d2 Gmdm. mod n puis d'autre part, calculer en appliquant la fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement reconstruit R', un jeton T', le dispositif contrôleur comporte aussi des moyens de comparaison, ci- après désignés les moyens de comparàison du dispositif contrôleur, pour : comparer le jeton calculé T' au jeton T reçu. 9. Système selon la revendication 6 destiné à produire la signature : numérique d'un message M, ci-après désigné le. message signé, par une entité appelée entité signataire; - le message signé comprenant: - le message M, - les défis d et/ou les engagements R. : - les réponses D; Opération de signature ledit système étant tel. qu'il comporte un dispositif signataire associé à l'entité signataire? ledit dispositif signataire étant mterconnecté au : dispositif témoin par:des moyens d'interconnexion et pouvant se présenter notamment sous la forme de microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à: microprocesseur, ledit système permettant d'exécuter les étapes suivantes: À étape 1: acte d'engagement R à chaque appel, les moyens de calcul des engagements R du dispositif :15 témoin calculent chaque engagement R en appliquant le processus spécifié selon la revendication 1,:: le dispositif témoin comporte des moyens de transmission, ci-après désignés: : les moyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif signataire, via les moyens : 20 d'interconnexion, À étape 2: acte de défi d le dispositif signataire comporte des moyens de calcul, ci-après désignés les moyens de calcul du dispositif signataire, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de - 25 chaque engagement R. pour calculer un *ain binaire et extraire de ce train binaire des défis d en nombre égal au nombre d' engagements R. À étape 3: acte de réponse D les moyens de réception des déLis d du dispositif témoin, reçoivent chaque défi d provenant du dispositif signataire, via les moyens d'interconnexion, - les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des défis d en appliquant le processus spécifié selon la revendication 1, le dispositif témoin comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif témoin, pour transmettre les réponses D au dispositif slgnataire, via les moyens d'interconnexion. 10. Système selon la revendication 9 destiné à prouver l'authenticité du message M en contrôlant, par une entité appelée contrôleur, le message signé;:: Opération de contrôle ledit système étant tel qu'il comporte un dispositif contrôleur associé à l'entité contrôleur, ledit dispositif contrôleur se présentant notamment sous la forme d'un terminal ou d'un serveur distant, ledit dispositif contrôleur comportant des moyens de connexion pour le connecter électriquement, éiectromagnétiquement,; optiquement ou de manière acoustique, notamment via un réscau de communication informatique, au dispositif . sgnatare; : le dispositif signataire associé à l'entité signataire comporte des moyens de transmission, ci-après désignés les moyens de transmission du: dispositif signataire, pour transmettre au dispositif contrôleur, le message signé, via : les moyens de connexion, de telle sorte que le dispositif contrôleur dispose : d'un message signé comprenant: - le message M, : - les défis d et/ou les engagements R. - les réponses D; le dispositif contrôleur comporte: - des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur, À cas o le dispositif contrôleur dispose des èngagements R. des défis d, des réponses D, dans le cas o le dispositif contrôleur dispose des engagements R. des défis d, des réponses D, À À les moyens de calcul et de comparaison du dispositif contrôleur vérifient que les engagements R.? les défis d et les réponses D satisfont à des relations du type : R_G d G202.Gmdm.DVm0dn ou à des relations du type: R-Dv / G d! G2 d2.... Gm dm. mod n À À les moyens de calcul et de comparaison du dispositif contrôleur vérifient que le message M, les défis d et les engagements R satisfont à la fonction de hachage d = h (message, R) À eas o le dispositif contrôleur dispose des déffs d et des réponses D dans le cas o le dispositif contrôleur dispose des défis d et des réponses D, : À À les moyens de calcul du dispositif contrôleur calculent, à partir de chaque défi d et de chaque réponse D, des engagements R' satisfaisant à des relations du type::: R. _ G d! G2 d2.... Gm dm. Dv mod n ou à des relations du type: : R. _ Dv / G dl G2 d2.... Gm dm. mod n À À les moyens de calcul et de comparaison du dispositif contrôleur vérifient que le message M et les défs d satisfont à la fonction de hachage d = h (message, R') À cas o le dispositif contrôleur dispose des engagements R et des réponses D dans le cas o le dispositif contrôleur dispose des engagements R et des - 2824974 réponses D, - ÀÀ les moyens de calcul du dlspositif contrôleur appliquent la fonction de hachage et calculent d' tel que d' = h (message, R) À À les moyens de calcul et de comparaison du dispositif contrôleur vérifient que les engagements R. les défis d' et les réponses D, satisfont à des relations du type: R-G d'l G2 (192Gm d'm. Dv mod n ou à des relations du type: R-Dv / G d'l G d'2 G. d'm mod n 11. Dispositifterminal associé à une entité, se présentant notamment sous la forme d'un objet nomade par exemple sous la forme d'une carte bancaire à microprocesseur, destiné à prouver à un dispositif contrôleur, À:: - l' authenticité de l' entité etlou l'intégrité d'un message M associé à cette entité, au moyen de tout ou partie des paramètres suivants ou dérivés de ceux-ci: - m couples de valeurs privées Ql, Q2,... Qm et publiques G1, G2'... Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers Pl, P2, pf (f étant supérieur ou égal à 2), - un exposant publlc v; ledit module, ledit exposant et lesdites valeurs étant liés par des relations du type::: : G'.QjV-l.modnouGj_QiVmodn; ledit exposant v étant tel que : V=2k o k est un paramètre de sécurité plus grand que 1; ladite valeur publique G; étant le carré gj2 d'un nombre de base g; inférieur aux f facteurs premiers pl, P2'... pf; le nombre de base g; étant tel que: les deux équations: X2 _ gi mod n: et X2 _ - gi mod n n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: l'équation: : xV_gj2 mod n a des solutions en x dans l'anneau des entiers moduIo n, ledit dispositif terminal comprend un dispositif témoin comportant, : - une zone mémoire:contenant les f facteurs premiers p; etlou les paramètres des restes chinois des facteurs premiers et/ou le. module public n etlou les m valeurs privées Q; etlou les f.m composantes Qi j (Q; j - Q; mod pj) des valeurs privées Q; et l'exposant public v; ledit dispositif témoin comporte aussi : - des moyens de production d'aléas, ci-après désignés les moyens de production d'aléas du dispositif témoin" - des moyens de calcul, ci-après désignés les moyens de calcul des engagements R du dispositif témoin, pour calculer des engagements R dans l'anneau des entiers modulo n; chaque engagement étant calculé: : À soit en effectuant des opérations du type : R-rVmodn ou r est un aléa produit par les moyens de production d'aléas, r étant tel queO 69 2824974 réception des-déhis d du dispositif témoin, pour recevoir un ou plusieurs défis d; chaque défi d comportant m entiers di ci-aprés appelés défis élémentaires; - des moyens de calcul, ci après désignés les moyens de calcul des réponses D du dispositif témoin, pour calculer à partir de chaque défi d une réponse D, À soit en effectuant des opérations du type: D-r Q dl Q d2... Qm dm mod n À soit en effectuant des opérations du type:D -4 Q dl Qi2 d2 Q; m dm mod pi puis enappliquant la méthode des restes chinois,: - des moyens de transmission pout transmettre un ou plusieurs engagements R et une ou plusieurs réponses D; il y a autant de réponses D que de défis d que d' engagements R. chaque : 15 groupe de nombres R. d, D constituant un triplet noté {R. d, D}. 12. Dispositif teminal selon la revendication 11 destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur,:: : ledit dispositif terminal étant tel qu'il comporte un dispositif démonstrateur associé à l'entité démonstrateur, ledit dispositif démonstrateur étant interconnocté au dispositif témoin par des moyens d'interconnexion et pouvant se présenter notamment sous la forme de microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur, ledit dispositif démonstrateur comportant des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif contrôleur associé à l'entité contrôleur, ledit dispositif contrôleur se présentant notamment sous la forme d'un terminal - 2824974 ou d'un serveur distant; : ledit dispositif terminal permettant d'exécuter les étapes suivantes: : À étape 1: acte d'engagement R à chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié selonlarevendicationl, le dispositif témoin comporte des moyens de transmission, ci-après désignés les moyens de transmssion du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif démonstrateur, via les moyens : 10: d'interconnexion, le dispositif démonstrateur comporte aussi des moyens de transmission, ci après désignés les moyens de transmission du démonstrateur, pour transmettre tout ou partie de chaque engagement R au dispositif: contrôleur, via les moyens deconnexion; : : étapes 2 et 3: acte de défi d, acte de réponse D les moyens de réception des défis d du dispositif témoin, reçoivent chaque : défi d provenant du dispositif contrôleur via les moyens de connexion entre le dispositif contrôleur et le dispositif démonstrateur et via les moyens d'interconnexion entre le dispositif démonstrateur et le dispositif témom, les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à parhr des défis d en appliquant le processus spécifié selon la revendication 1, À étape 4: acte de contrôle les moyens de transmission du démonstrateur transmettent chaque réponse - 25: D au dispositif contrôleur qui procède au contrôle, 13. Dispositif terminal selon la revendication 11 destiné à prouver à une entité appelée contrôleur l'intégnté d'un message M associé à une entité appelée démonstrateur, ledit dispositif terminal étant tel qu'il comporte un dispositif démonstrateur 71: associé à l'entité démonstrateur, ledit dispositif démonstrateur étant interconnecté au dispositif témoin par des moyens d'interconnexion et pouvant se présenter notamment sous la fome de microcircuits logiques dans un objet nomadepar exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur, ledit dispositif démonstrateur comportant des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique,: notamment via un réseau de communication informatique, au dispositif contrôleur assocé à l'entité contrôleur, ledit dispositif contrôleur se présentant notamment sous la forme d'un terminal ou d'un serveur distant;: ledit dispositif terminal permettant d'exécuter les étapes suivantes: : À étape 1: acte d'engagement R à chaque appel, les moyens de calcul des engagements R du dispositif témoin calculent: chaque engagement R en appliquant le processus spécifié selon la revendication 1, :le dispositif témoin comporte des moyens de transmission, ci-après désignés ::: les moyens de transmission du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif démonstrateur, via les moyens d'interconnexion, d: À étapes 2 et 3: acte de défi d, acte de réponse D le dispositif démonstrateur comporte des moyens de calcul, ci-après désignés les moyens de calcul du démonstrateur, appliquant une fonction de hachage h ayant: comme arguments le message M et tout ou partie de - 2s chaque engagement R. pour calculer au moins un jeton T. le dispositif démonstrateur comporte aussi des moyens de transmission, ci après désignés les moyens de transmission du dispositif démonstrateur, pour transm ttre chaque jeton T. via les moyens de connexion, au dispositif contrôleur, (ledit disposit- if contrôleur produit, après avoir reçu le jeton T. des défis d en nombre égal au nombre d'engagements R.) les moyens de réception des défis d du dispositif témoin, reçoivent chaque défi d provenant du dispositif contrôleur via les moyens de connexion entre le dispositif contrôleur et le dispositif démonstrateur et via les moyens d'interconnexion entre le dispositif démonstrateur et le dispositif témoin, les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des défis d en appliquant le processus spécifié selon la revendication 1, À étape 4: acte de contr81e les moyens de transmission du démonstrateur transmettent chaque réponse D au dispositif contrôleur qui procède au contrôle. 14. Dispositif terminal selon la revendcation 11 destiné à produire la signature numérique d'un message M, ci-après désigné le message signé, par une entité appelée entité signataire; le message signé comprenant: - le message M, - les défis d et/ou les engagements R. - les réponses D, ledit dispositif terminal étant tel qu'il comporte un dispositif signataire associé à l'entité sgnataire, ledit dispositif signataire étant interconnecté au dispositif témoin par des moyens d'interconnexion et pouvant se présenter notamment sous la fonne de microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte bancaire à microprocesseur, ledit dispositif signataire comportant des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif contrôleur associé à l'entité contrôleur, ledit dispositif contrôleur se présentant notamment sous la forme d'un terminàl ou d'un serveur: distant;:: Opération de signature ledit dispositif terminal permettant d'exécuter les étapes suivantes: s À étape 1: acte d'engagement R : à chaque appel, les moyens de calcul des engagements R. du dispositif témoin calculent chaque engagement R en appliquant le processus spécifié : selon la revendication 1, le dispositif témoin comporte des moyens de transmission, ci-après désignés les moyens de transmisslon du dispositif témoin, pour transmettre tout ou partie de chaque engagement R au dispositif signataire, via les moyens d'interconnexion, : étape 2: acte de défi d le dispositif signataire comporte des moyens de calcul, ci-après désignés les 1S moyens de calcul du dispositif signataire, appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R. pour calculer un train binaire et extraire de ce train binaire des déLis d en nombre égal au nombre d' engagements R. À étape 3: acte de réponse D les moyens de réception des déLis d du dispositif témoin, reçoivent chaque déh1 d provenant du dispositif signataire, via les moyens d'interconnexion, les moyens de calcul des réponses D du dispositif témoin, calculent les réponses D à partir des déhis d en appliquant le processus spécifié selon la revendication 1,: - 25 le dispositiftémoin comporte des moyens de transmission, ci-après désignés les moyens de transmission du dispositif témoin, pour transmettre les réponses D au dispositif signataire, via les moyens d'interconnexion. 15. Dispositif contrôleur, se présentant notamment sous la forme d'un terminal ou d'un serveur distant, associé à une entité contrôleur, destlné à contrôler: : - I'authenticité d'une entité et/ou - l'intégrité d'un message M associé à cette entité, au moyen de tout ou partie des paramètres suivants ou dénvés de ceux-ci: - m couples de valeurs publiques G" G2, Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers P1, P2,... pf (f étant supérieur ou égal à 2) inconnus du dispositif contrôleur et de l'entité contrôleur associé, - un exposant public v; ledit module, ledit exposant et lesdites valeurs étant liés par des relahons du type: Gi.;Q'.V- 1. mod n ou Gj _ QjV mod n;: :o Qi désigne une:valeur privée, inconnue du: dispositif contrôleur, associce à la valeur publique Gj, ledit exposant v étant tel que : v = 2 o k est un paramètre de sécurité plus grand que 1; ladite valeur publique Gj étant le. carré gj2 d'un nombre de base g; inférieur aux f facteurs premiers P1, P2, pf; le nombre de base gj étant tel que: les deux équations: : x2 _ gjmod n et x2 - - g; mod n n'ont pas de solution en x dans l'anneau des entiers modulo n et tel que: l'équation: xV- g; mod n a: des solutions en x dans l'anneau des entiers modulo n; 16. Dispositif contrôleur selon la revendication 15 destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur; - - ledit dispositif contrôleur comportant des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement: ou de manière acoushque, notamment via un réseau de communicahon :informabque, à un dispositif démonstrateur associée à l'entité démonstrateur; ledit dispositif contrôleur permettant d'exécuter les étapes suivantes: : À étapes I et 2: acte d'engagement R. acte de défi d ledit dispositif contrôleur comporte aussi des moyens de réception de tout ou partie des engagements R provenant du dspositif démonstrateur, via les moyens de connexion,: le dispositif contrôleur comporte des moyens de production de défis pour produire, après avoir reçu tout ou partie de chaque engagement R. des défis d en nombre égal au nombre d' engagements R. chaque défi d comportant:m entiers d; ci-après appelés défis élémentaires, le dispositif contrôleur comporte aussi des moyens de transmission, ci-après désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion; À étapes 3 et 4: acte de réponse D, acte de contr81e ledit dispositif contrôleur comporte aussi: des moyens de réception des réponses D provenant du dispositif démonstrateur, vla les moyens de connexion - des moyens de calcul, ciaprès désignés les moyens de calcul du dispositif contrôleur, - des moyens de comparaison, ci-aprés désignés les moyens de comparaison du dispositif contrôleur,: cas o le démonstrateur a transmis une partie de chaque engagement R dans le cas o les moyens de réception du dispositif contrôleur ont recus une partie de chaque engagement R. les moyens de calcul du dispositif contrôleur, disposant des m valeurs publiques Gl, G2, ... Gm, calculent à partir de chaque déLi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R'-G J. G2 02.... Gm dm. Dv mod n ou à une relation du type, R'-Dv / G â. G2 d2.... Gm dm. mod n, les moyens de comparaison du dispositif conhôleur comparent chaque éngagement reconstruit R' à tout ou partie de chaque engagement R reçu, cas o le démonstrateur a transmis l'intégralité de chaque engagement : R dans le cas o les moyens de réception du dispositif contrôleur ont reçus l'intogralité de chaque engagement R. les moyens de calcul et les moyens : de comparaison du dispositif contrôleur, disposant des m valeurs publiques G G2,... Gm, vérifient que chaque engagement R satisfait à une relation du type::; R--G d G 02.... Gmdm. DV mod n: ou à une relation du type, R_Dv/Gd.G2d2....GmJm.mOdn. 17. Dispositif contrôleur selon la revendication 15 destiné à prouver l'intégrité d'un message M associé à une entité appelée démonstrateur,: ledit dispositif contrôleur comportant des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, à un dispositif démonstrateur associée à l'entité démonstrateur; ledit dispositif contrôleur permettant d'exécuter les étapes suivantes: À étapes 1 et 2: acte d'engagement R. acte de déf d ledit dispositif contrôleur comporte aussi des moyens de réception de jetons T provenant du dispositif démonstrateur, via les moyens de connexion, - - le dispositif contrôleur comporte des moyens de production de défis pour produire, après avoir reçu le jeton T. des défis d en nombre égal au nombre d'engagements R. chaque défi d comportant m entiers di ci-après appelés défis élémentaires; le dispositif contrôleur comporte aussi des moyens de transmission, ci-après désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion;: : À étapes 3 et 4: acte de réponse D, acte de contrôle leditdispositfcontrôleurcomporteaussi:: - des moyens de réception des réponses D provenant du dispositif démonstrateur, via les moyens de connexion, : - des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, disposant des m valeurs publiques G" G2,. .. Gm' pour d'une part, calculer à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R.-G d! G2 d2 Gm Jm. Dv mod n: : ou à une relation du type: R. _ Dv / G d!. G2 d2.... Gm dm. mod n puis d'autre part, calculer en appliquant une fonction de hachage h ayant comme arguments le message M et tout ou partie de chaque engagement reconstruit R', un jeton T', le dispositif contrôleur comporte aussi - des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur, pour comparer le jeton calculé T' au jeton T reçu. 18. Dispositif contrôleur selon la revendication lS destiné à prouver l'authenticité du message M en contrôlant, par une entité appelée contrôleur, un message signé; le message signé, émis par un dispositif:signataire associé à une entité signataire disposant d'une fonction de hachage h (message, R), À comprenant: - le message M, - des; défis d et/ou des engagements R. : - des réponses D; Opération de contrôle ledit dispositif contrôleur comportant des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, à un dispositif signataire associée à l'entité signataire; ledit dispositif contrôleur ayant reçu le message signé du dispositif signataire, via les moyens de connexion, : le dispositif contrôl comporte: - des moyens de calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, des moyens de comparaison, ci-après désignés les moyens de comparaison du dispositif contrôleur, À cas o le dispositif contrôleur dispose des engagements R. des défis d, : des réponses D, dans le cas o le dispositif contrôleur dispose des engagements R. des défis d, des réponses D, À À les moyens de calcul et de comparaison du dispositif contrôleur vénfient que les engagements R. les défis d et les réponses D satisfont à des: relations du type R-Gl dl. G2 d2.... Gm dm. Dv mod n ou à des relations du type: R _ Dv / G dl G2 d2. ... Gm dm. mod n À À les moyens de calcul et de comparaison du dispositif contrôleur vérifient que le message M, les déhis d et les engagements R satisfont à la fonction de hachage: d = h (message, R) À cas o le dispositif contrôleur dispose des déffs d et des réponses D dans le cas o le dispositif contrôleur dispose des défis d et des réponses D, À À les moyens de calcul du dispositif contrôleur calculent, à partir de chaque défi d et de chaque réponse D, des engagements R' satisfalsant à des relations du type: R. _ G1 dl. G2 d2.... Gm dm. Dv mod n ou à des relations du type: R. _ Dv 1 G1 dl. G2 d2.... Gm dm À mod n : À À les moyens de calcul et dè comparaison du dispositif contrôleur vérifent que le message M et les défis d satisfont à la fonction de hachage: d = h (message, R'): À cas o le dispositif contrôleur dispose des engagements R: et des : réponses D dans le cas o le:dispositif contrôleur dispose des engagements R. et des réponses D, À. les moyens de calcul du dispositif contrôleur appliquent la fonction de hachage et calculent d' tel que d' = h (message, R) À À les moyens de calcul et de comparaison du dispositif contrôleur vérifient que les engagements R. les défis d' et les répons es D, s atis font à des relations du type: R_G d'1 G d'2 Gm d'm. DvmOdn ou à des relations du type: