Brevet FR2788908A1 — publié le 20000728

I Procédé, système, dispositif destinés à prouver l'authenticité d'une entité et/ou l'intégrité et/ou l'authenticité d'un message. 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é 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éfé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 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: "Voici mon identité;j'en connais la signature RSA." Le témoin prouve sans la révéler qu'il connaît 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 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. Le procédé GQ met en oeuvre 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 216 + 1. Or les infrastructures microélectroniques existantes, notamment dans le domaine des cartes bancaires, font usage de microprocesseurs auto-programmables monolithiques dépourvus de coprocesseurs arithmé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, entraine des temps de calcul qui dans certains cas s'avèrent pénalisant pour les consommateurs utilisant des cartes bancaires pour acquitter leurs achats. Il est rappelé ici, qu'en cherchant à accroître la sécurité des cartes de paiement, les autorités bancaires posent un problème particulièrement dé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'entraî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 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 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 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 évite les inconvénients présentés par la technologie RSA. Procédé Méthode des restes chinois appliquée à la famille GQ Plus particulièrement, l'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 QI, Q2,... Qm et publiques Gl, G2,... Gm (m étant supérieur ou égal à 1), - un module public n constitué par le produit de f facteurs premiers pi, 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. Qv = 1. mod n ou Gi - Qv mod n; Ledit procédé met en oeuvre selon les étapes ci-après définies 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 _ Q1 mod pi) 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é en effectuant des opérations du type R1i riv mod pi o ri est un aléa associé au nombre premier pi tel que 0 rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le témoin reçoit un ou plusieurs défis d. Chaque défi d comportant m entiers d1 ci-après appelés défis élémentaires. Le témoin calcule à partir de chaque défi d une réponse D, en effectuant des opérations du type: D ri -r Qi dl Qi,2 d2.... Qim dm mod pi puis en appliquant la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo pi à effectuer pour calculer chacune des réponses Di pour chacun des pi est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le procédé est tel qu'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 o triplet noté {R, d, D}. Cas 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 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é cidessus. 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. e é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 contrôle 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,... s 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 m Dv mod n ou à une relation du type, R' Dv / G dl G2 '....Gm d. mod n. Le contrôleur vérifie que chaque engagement reconstruit R' reproduit tout ou partie 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: RG1 dl G2 d... Gm dm Dvmod n ou à une relation du type, R-Dv / G! dl 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 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 A chaque appel, le témoin calcule chaque engagement R en appliquant 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ôl61eur, 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 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,... Gm, calcule à partir de chaque défi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R' - GI dl.G2 2....Gm dm. DV mod n ou à une relation du type: m- dl d2 d R' - DV/G G. G2 d2....Gm 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 au jeton T transmis. Signature numérique d'un message et preuve de son authenticité Opération de signature Dans une troisième variante de réalisation susceptible d'être prise en combinaison avec l'une et/ou l'autre des autres variantes de réalisation, le procédé selon l'invention 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. Ladite entité signataire exécute une opération de signature en vue d'obtenir 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: 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é ci-dessus. Opération de contrôle Pour l'authenticité du message M, une entité, appelée contrôleur, contrôle le message signé. Ladite entité contrôleur disposant du message signé exécute une opération de contrôle en procédant comme ci-après décrit. * 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érifie que les engagements R, les défis d et les réponses D satisfont à des relations du type R = G dl. G2 d2... Gm dm. Dvmod n ou à des relations du type: R- Dv/G dl. G2d2....Gmdm. modn Puis, le contrôleur vérifie que le message M, les défis d et les engagements R satisfont à la fonction de hachage d = h (M, 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' G1 dl G d2... Gm dm. Dv mod n ou à des relations du type: R'- Dv / G dl. 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 (M, 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 (M, R) Puis, 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'. G2 d'2...Gm d'm Dv mod n ou à des relations du type: R - Dv/G1 d'l.G2 d'2....Gm d'm. mod n. Cas o on choisit la valeur privée Q en premier et o on déduit la valeur publique G de la valeur privée Q Dans certains, notamment afin de faciliter la production des couples de valeurs privées Q et publiques G, on choisit la valeur privée Q en premier et on déduit la valeur publique G de la valeur privée Q. Plus particulièrement dans ce cas, le procédé selon l'invention est tel que les composantes Qi,-l, Qi, 2,... Qi, r des valeurs privées Qi, sont des nombres tirés au hasard à raison d'une composante QI J (Q, j - Q; mod pj) pour chacun desdits facteurs premiers pj. Lesdites valeurs privées Qi peuvent être calculées à partir desdites composantes Qi,, Qi, 2... Qi, f par la méthode des restes chinois. Lesdites valeurs publiques GQ, sont calculées en effectuant des opérations du type G Q iv mod pj puis, en appliquant la méthode des restes chinois pour établir G1 tel que Gi. QiV-. mod n ou G -= Qivmod n; Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des Gi, j pour chacun des pj est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Avantageusement dans ce cas, le procédé selon l'invention est tel que l'exposant public de vérification v est un nombre premier. On démontre que la sécurité est équivalente à la connaissance de la valeur privée QI. Cas o on choisit la valeur publique G en premier et o on déduit la valeur privée Q de la valeur publique G. De préférence dans ce cas, ledit exposant v est tel que v =2k o k est un paramètre de sécurité plus grand que 1. Ladite valeur publique G1 est le carré gi2 d'un nombre de base gi inférieur aux f facteurs premiers pl, P2,... pf. Le nombre de base g; est tel que les deux équations: x = g1 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 modn a des solutions en x dans l'anneau des entiers modulo n. Système La présente 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 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 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 public v. Ledit module, ledit exposant et lesdites valeurs étant liés par des relations du type: G1. Qv _ 1. mod n ou Gi _ Qivmod 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 les 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 (Qi, j _ Qi mod p,) des valeurs privées Q1 et de l'exposant public v. Le 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é en effectuant des opérations du type Ro _ rev mod pi o ri est un aléa associé au nombre premier pi tel que 0 rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le dispositif témoin comporte aussi: - des moyens de réception, ci-aprè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émoin, pour calculer à partir de chaque défi d une réponse D en effectuant des opérations du type: Di ri - Q, dl Qi,2 d2.... Qim dm mod pi puis, en appliquant la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo pi à effectuer pour calculer chacune des réponses Di pour chacun des pi est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Ledit dispositif témoin comporte aussi des moyens de transmission pour 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}. 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émonstrateur est interconnecté au dispositif témoin par des moyens d'interconnexion. Il 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. 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- 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é les moyens de transmission du dispositif démonstrateur, pour transmettre tout ou partie de chaque engagement R au dispositif contrôleur, via les moyens de connexion. e étape 2: acte de défi d Le dispositif contrôleur comporte des moyens de productions 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, 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 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, - 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 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 dispositif contrôleur, disposant des m valeurs publiques G, 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' - G1 dl G2 d... Gm dm. Dv mod n ou à une relation du type, R' -Dv / G G dZ.... 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 o 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 calcul et les moyens de comparaison du dispositif contrôleur, disposant des m valeurs publiques GV, G2,... Gm, vérifient que chaque engagement R satisfait à une relation du type: R-= G dl.....G2 Gm dm Dv mod n ou à une relation du type, R--- Dv/ Gdl l. * 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 système selon l'invention est 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 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. Il 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. Ledit système exécute les étapes suivantes e é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- 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. é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 dispositif 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 démonstrateur, pour transmettre chaque jeton T, via les moyens de connexion, au dispositif au contrôleur. Le dispositif contrôleur comporte aussi des moyens de productions 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 dispositif 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 calcul, ci-après désignés les moyens de calcul du dispositif contrôleur, disposant des m valeurs publiques G1, 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' G1 d.G2... Gm dm Dvmod n ou à une relation du type: R-=Dv / G dl Gd2....Gmdm. mod n puis d'autre part, calculer en appliquant la fonction de hachage h ayant s 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 T' au jeton T reçu. Signature numérique d'un message et preuve de son authenticité Opération de signature Dans une troisième variante de réalisation, susceptible d'être combinée à l'une et/ou à l'autre des deux autres, le système selon l'invention est 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é comprend: - le message M, - les défis d et/ou les engagements R, - les réponses D. Ledit système est tel qu'il comporte un dispositif signataire associé à l'entité signataire. Ledit dispositif signataire est interconnecté au dispositif témoin 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. 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 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 d hachage h ayant comme arguments le message M et tout ou partie de chaque engagement R pour calculer un train binaire et extraire de cetrain 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 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. Opération de contrôle Pour prouver l'authenticité du message NM, par une entité appelée contrôleur, contrôle le message signé. Le 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 connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif démonstrateur. Ledit 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 s 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éponse 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 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érifient que les engagements R, les défis d et les réponses D satisfont à des relations du type R- G dl G2 z... Gm dm Dvmod n ou à des relations du type: R-Dv / Gi dl.G2d2....Gm dm. modn 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 (M,R) * cas o le contrôleur dispose des défis 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 dl. G2 d2.... Gm am. Dv mod n ou à des relations du type: R' -Dv / dl 1 dl. G2 d2....Gm dm. mod n Puis, les moyens de calcul et de comparaison du dispositif contrôleur vérifie que le message M et les défis d satisfont à la fonction de hachage d = h (M, R') * cas o le 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 (M,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, l. G2 d'2.... Gm d'm. Dv mod n ou à des relations du type: R Dv / Gdl G2.... G m 'm. mod n Cas o on choisit la valeur privée Q en premier et o on déduit la valeur publique G de la valeur privée Q Dans certains, notamment afin de faciliter la production des couples de valeurs privées Q et publiques G, on choisit la valeur privée Q en premier et on déduit la valeur publique G de la valeur privée Q. Plus particulièrement dans ce cas, le système selon l'invention est tel que les composantes Q, 1, Qi, 2... QI, f des valeurs privées Q, sont des nombres tirés au hasard à raison d'une composante Qi j (Qi, j - Q mrod pj) pour chacun desdits facteurs premiers pj. Lesdites valeurs privées QI peuvent être calculées à partir desdites composantes Qi,, QI, 2... Qi, f par la méthode des restes chinois. Lesdites valeurs publiques Gi, sont calculées en effectuant des opérations du type Gi, j - Qi, j mod pj puis, en appliquant la méthode des restes chinois pour établir G1 tel que Gi. Qiv -. mod n ou Gi - Qiv mod n; Ainsi, le nombre d'opérations arithmétiques modulo pi à effectuer pour calculer chacun des Gi, j pour chacun des pi est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Avantageusement dans ce cas, le système selon l'invention est tel que l'exposant public de vérification v est un nombre premier. On démontre que la sécurité est équivalente à la connaissance de la valeur privée Q. Cas o on choisit la valeur publique G en premier et o on déduit la valeur privée Q de la valeur publique G. De préférence dans ce cas, ledit exposant v est tel que v = 2k o k est un paramètre de sécurité plus grand que 1. Ladite valeur publique G1 est le carré gi2 d'un nombre de base gi inférieur aux f facteurs premiers PI, P2,... pf. Le nombre de base gi 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 l'équation: Xv gi. modn a des solutions en x dans l'anneau des entiers modulo n. Dispositif terminal Méthode des restes chinois appliquée à la famille GQ L'invention concerne aussi un dispositif terminal associé à une entité. Le dispositif terminal se présente notamment sous la forme d'un objet nomade par exemple sous la forme d'une carte bancaire à microprocesseur. Le - -......- 2788908 dispositif terminal est destiné à prouver à dispositif 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 Ql, Q2,... Qm et publiques Gl, 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 public v. Ledit module, ledit exposant et lesdites valeurs sont liés par des relations du type: Gi. QiV _. mod n ou Gi Qivmod n. Ledit dispositif terminal comprend un dispositif témoin comportant une zone mémoire contenant les f facteurs premiers pi et/ou les paramètres des restes chinois des facteurs premiers et/ou du module public n et/ou les m valeurs privées Q1 et/ou les f.m composantes Qi, j (Q, j - Qi mod pj) des valeurs privées Qi et de l'exposant public v. Le 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. Les moyens de calcul permettent de calculer des engagements R dans l'anneau des entiers modulo n. Chaque engagement est calculé en effectuant des opérations du type R _ riv mod pi o ri est un aléa associé au nombre premier pi tel que 0 -.... -. - 2788908 moyens de production d'aléas, puis en appliquant la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo Pi à effectuer pour calculer chacun des engagements Rt pour chacun des pi est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le dispositif témoin comporte aussi: - des moyens de réception, ci-aprè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émoin, pour calculer à partir de chaque défi d une réponse D en effectuant des opérations du type: Di; = ri - Qi,1 dl Q2 d2.. Qim dm mod pi puis, en appliquant la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo pi à effectuer pour calculer chacune des réponses Dû pour chacun des pi est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le dispositif témoin comporte aussi des moyens de transmission pour 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}. Cas de la preuve de l'authenticité d'une entité Dans une première variante de réalisation, le dispositif terminal selon l'invention est destiné à prouver l'authenticité d'une entité appelée démonstrateur à une entité appelée contrôleur. Ledit dispositif terminal 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. Il 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, à 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 terminal permet d'exécuter les étapes suivantes e é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-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 dispositif contrôleur, via les moyens de connexion. * étape 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é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é ci- dessus. * étape 4: acte de contrôle Les moyens de transmission du démonstrateur transmettent chaque réponse D au dispositif contrôleur qui procède au contrôle. Cas de la preuve de l'intégrité d'un message Dans une deuxième variante de réalisation, susceptible d'être combinée aux autres variantes de réalisation, le dispositif terminal selon l'invention 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 dispositif démonstrateur associé à l'entité démonstrateur. Ledit dispositif démonstrateur est interconnecté au dispositif témoin par des moyens d'interconnexion. Il 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, à 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 terminal permet d'exécuter les étapes suivantes e é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- 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. e étape 2 et 3: acte de défi d, acte de réponse Le dispositif démonstrateur comporte des moyens de calcul, ci-après désignés les moyens de calcul du dispositif démonstrateur, appliquant 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 démonstrateur, pour transmettre chaque jeton T, via les moyens de connexion, au dispositif au contrôleur. Ledit dispositif 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 démonstrateur, 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é ci- dessus. e étape 4: acte de contrôle Les moyens de transmission 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é Opération de signature Dans une troisième variante de réalisation, susceptible d'être combinée aux autres, le dispositif terminal selon l'invention est 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é comprend: - 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é signataire. Ledit dispositif signataire est interconnecté au -* 2788908 dispositif témoin par des moyens d'interconnexion. i 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 signataire 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, à 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 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é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 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 moyens de calcul du dispositif signataire, appliquant une fonction d 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 reçoivent les défis 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, 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. Dispositif contrôleur Méthode des restes chinois appliquée à toute la famille GQ 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 contrôleur est destiné à prouver à un serveur 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 QI, 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 Pi, 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 - Qiv mod n; o Qi désigne une valeur privée, inconnue du dispositif contrôleur, associée à la valeur publique G. Cas de la preuve de l'authenticité d'une entité Dans une première variante de réalisation, susceptible d'être combinée avec les autres, 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 électriquement, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, à un dispositif démonstrateur associé à l'entité démonstrateur. Ledit dispositif contrôleur permet d'exécuter les étapes suivantes e étape 1 et 2: acte d'engagement R, acte de défi 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 productions 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 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 dispositif contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion. * étapes 3 et 4: acte de réponse, acte de contrôle Le dispositif contrôleur comporte aussi - 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, - 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 engagement R Dans le cas o les moyens de réception du dispositif contrôleur ont reçus 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éfi d et de chaque réponse D un engagement reconstruit R' satisfaisant à une relation du type: R' G l G2 2....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 Gl, G2,... Gm, vérifient que chaque engagement R satisfait à une relation du type: R=- G dl G2 d2... Gm dm. Dvmod n ou à une relation du type, R -Dv / G1 dl. 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 les autres, le dispositif contrôleur selon l'invention est destiné à prouver l'intégrité d'un message M associé à une entité appelée démonstrateur. 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, à un dispositif démonstrateur associé à l'entité démonstrateur. Ledit dispositif contrôleur permet d'exécuter les étapes suivantes e étapes 1 et 2: acte d'engagement R, acte de défi Ledit dispositif contrôleur comporte aussi des moyens de réception de jetons T provenant du démonstrateur, via les moyens de connexion. Le dispositif contrôleur comporte aussi des moyens de productions de défis pour produire, après avoir reçu le jeton T, défis d en nombre égal au nombre d'engagements R, chaque défi d comportant m entiers, ci-après appelés les 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 dispositif 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 Le dispositif contrôleur comporte des moyens de réception des réponses D provenant du dispositif démonstrateur, via les moyens de connexion. 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 G1, 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' Gi dl. G2 dz...G dm.Dvmodn ou à une relation du type: - d. dl. d2 d R Dv / G1 dl...... Gm. 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 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 aux autres variantes de réalisation, le dispositif contrôleur selon l'invention est destiné à prouver l'authenticité du message M en contrôlant, par une entité appelée contrôleur, le message signé. Le message signé, émis par un dispositif signataire associé à une entité signataire disposant d'une fonction de hachage h (MNI, R); comprend: - le message M, - les défis d et/ou les engagements R, - les réponse D. 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, à un dispositif signataire associé à 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 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érifient que les engagements R, les défis d et les réponses D satisfont à des relations du type R-Gdl G d2..Gmdm.Dvmodn ou à des relations du type: R _ DV / G dl G 2. .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 (M, R) cas o le contrôleur dispose des défis 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 dl. G2 d2...Gm rdm. 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 et les défis d satisfont à la fonction de hachage d=h (M,R') * cas o le 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 (M, 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 d'l G2 d'2....Gm d'm. DV mod n ou à des relations du type: R - Dv/ G d'l. G2d'2....Gm d'm. mod n..DTD: Description détaillée de la variante de réalisation dans le cas o l'exposant public v =2 k 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. 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 numérique mettant en oeuvre la technologie RSA. Dans le cadre de la technologie GQ2, la présente partie de l'invention porte plus précisément sur l'utilisation des jeux de clés GQ2 dans le cadre de l'authentification 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 technologie RSA. La clé privée 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 > 1) appelés " nombres de base " et notés par g:. Les nombres de base étant fixés de g, à g avec m > 1, une clé 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). Le module public n est le produit d'au moins deux facteurs premiers plus grands que les nombres de base, disons f facteurs premiers (f> 2) notés par p, de p,... Pf Lesffacteurs 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. à g,. - D'une part, les équations (1) 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 non quadratiques (mod n). x2 -gi (mod n) (1) x2 --gi (mod n) (2) D'autre part, l'équation (3) a des solutions en x dans l'anneau des entiers modulo n. X2 = g2 (mod n) (3) La clé publique de vérification (v, n) étant fixée selon les nombres de base de g, à g,,, avec m > 1, chaque nombre de base g, 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 g,: soit G, = g,2. La valeur privé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 projections des équations (1), (2) et (3) dans CG(p,). X2- -= gi (mod pj) (l.a) x2 _-gi (mod pj) (2.a) x2 =g2 (mod pj) (3.a) Chaque valeur privée Qi peut se représenter de manière unique par f composantes privées, une par facteur premier: Qj - Q, (mod p.). Chaque composante privée Q,4 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. a) 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 Q,. à Q.z: Q, = Restes Chinois (Q,.,, Q,.2,... Q,) de manière à obtenir toutes les solutions possibles à l'équation (3). Voici la technique des restes chinois: soient deux nombres entiers positifs premiers entre eux a et b tels que 0 b est négatif, remplacer ô par +a; y- x. 8 (mod a); X= y. b + X,. Lorsque les facteurs premiers sont rangés dans l'ordre croissant, du plus petit p. au plus grand p,, les paramètres des restes chinois peuvent être les suivants (il y en af-il, c'est-à-dire, un de moins que de facteurs premiers). Le premier paramètre des restes chinois est x {P2 (modp,)}1-' (modp,). Le second paramètre des restes chinois est - {P.P2 (modp3)}-' (modp3). Le i ième paramètre des restes chinois est X - p.p2.... Pi_, (modp1)}-I (modp, ). Et ainsi de suite. Ensuite, enf-1 opérations des restes chinois, on établit un premier résultat (modp2 fois p.) avec le premier paramètre, puis, un second résultat (modp.p2 fois p3) avec le second paramètre, et ainsi de suite, jusqu'à un résultat (modp,... pf, foisp), c'est-à-dire, (mod n). Il y a plusieurs représentations possibles de la clé privé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 signe 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 classique en technologie GQ consiste à stocker m valeurs privées Q, 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 charges de travail consiste à stocker l'exposant public v, lesf facteurs premiers pj, m.f composantes privées QJ et f-l 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 g, et lesf facteurs premiers pj, puis, à commencer chaque utilisation en établissant ou bien m valeurs privées Q, et le module n pour se ramener à la première représentation, ou bien mf composantes privées QJ 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; sauf contre indication, les m nombres de base de g, à g,, 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 utilisant le même module. Généralement, chaque entité qui s'authentifie ou signe dispose de son propre module GQ2. Toutefois, on peut spécifier des modules GQ2 à quatre facteurs premiers dont deux sont connus d'une entité et les deux autres d'une autre. Voici un premier 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 à trois 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). pl = 03CD2F4F21EOEAD60266D5CFCEBB6954683493E2E833 P2 = 0583B097E8D8D777BAB3874F2E76659BB614F985EC 1B p3 = 0C363CD93D6B3FEC78EE13D7BE9D84354B8FDD6DA 1 FD n = pl.P2. P3 = FFFF81CEA149DCF2F72EB449C5724742FE2A3630D9 02CCOOEAFEE 1 B957F3BDC49BE9CBD4D94467B72AF28CFBB26144 CDF4BBDBA3C97578E29CC9BBEE8FB6DDDD Qij = 0279C60D216696CD6F7526E23512DAE09OCFF879FDDE Q2,1 = 7C977FC38F8413A284E9CE4EDEF4AEF35BF7793B89 Q3,1 = 6FB3B9C05A03D7CADA9A3425571EF5ECC54D7A7B6F Q,2 = 0388EC6AA1E87613D832E2B80E5AE8C1DF2E74BFF502 Q2,2 =04792CE70284D 16E9A158C688A7B3FEAF9C40056469E Q32 =FDC4A8E53E185A4BA793E93BEE5C636DA731BDCA4E Q.,3 = 07BC1AB048A2EAFDAB59BD40CCF2F657AD8A6B573BDE Q2,3 = 0AE8551E 116A3AC089566DFDB3AE003CF174FC4E4877 Q3= 01682D490041913A4EA5B80D16B685E4A6DD88070501 Q = D7E ICAF28192CED6549FF457708D50A7481572DD5F2C335D8 C69E22521 B51O0B64454FB7A19AEC8D06985558E764C6991B05FC2A C74D9743435AB4D7CFOFF6557 Q2 = CB IED6B 1DD649B89B9638DC33876C98AC7AF689E9D 1359E4 DB17563B9B3DC582D5271949F3DBA5A70C108F561A274405A5CB8 82288273ADE67353A5BC316C093 Q3= 09AA6F4930E51A70CCDFA77442B I0770DD ICD77490E3398A AD9DC50249C34312915E55917AIED4D83AA3D607E3EB5C8B 197 697238537FE7A0195C5E8373EB74D Voici un second jeu de clés GQ2, avec k = 9, soit v = 512, m = 2, soit deux nombres de base: g. = 2 et g2 = 3, etf = 3, soit un module à trois facteurs premiers congrus à 3 (mod 4). pl = 03852103E40CD4FO6FA7BAA9CC8D5BCE96E3984570CB p2 = 062AC9EC42AA3E688DC2BC871 C8315CB939089B61DD7 p3 = OBCADEC219F1DFBB8AB5FE808AOFFCB53458284ED8E3 n =p.P2. P3 = FFFF5401ECD9E537Fl67A80COA9111986F7A8EBA4D 6698AD68FF670DE5D9D77DFF00716DC7539F7CBBCF969E73AOC49 761B276A8E6B6977A21D51669D039FID7 Q" = 0260BC7243C22450D566B5C6EF74AA29F2B927AF68E 1 Q2,1 = 0326Cl12FC7991ECDC9BB8D7C1C4501BE1BAE9485300E Q.2 = 02DOB4CC95A2DD435DOE22BFBB29C59418306F6CD00A Q22 = 045ECB881387582E7C556887784D2671CA118E22FCF2 Q13 = BOC2B IF808D24F6376E3A534EB555EF54E6AEF5982 Q2,3 = OAB9F81 DF462F58A52D937E6D8 IF48FFA4A87A9935AB QI = 27F7B9FC82C 19ACAE47F3FE9560C3536A7E90F8C3C51 E 13C F32FD8C6823DF753685DD63555D2146FCDB9B28DA367327DD6 EDDA092DOCF 108DOAB708405DA46 Q2 = 230DOB9595E5AD388F 1F447A69918905EBFB05910582E5BA64 9C94BOB2661 E49DF3 C9B42FEF 1 F37A7909B 1 C2DD54113ACF87C6 F 1F19874DE7DC5D 1DF2A9252D Authentification dynamique Le mécanisme d'authentification dynamique est destiné à prouver à une entité appelée contrôleur 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 lui et le démonstrateur parlent bien du même message M. Le message associé Mest optionnel, ce qui signifie qu'il peut être vide. Le mécanisme d'authentification dynamique est une séquence de quatre actes: un 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ôleurjoue les actes de défi 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 représentations évoquées ci-dessus: * les f facteurs premiers et les m nombres de base, * les mf 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 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 sein du signataire. A chaque exécution du mécanisme, le témoin produit un ou plusieurs engagements R, puis, autant de réponses D à autant de défis d. Chaque ensemble {R, d, D} constitue un triplet GQ2. Outre qu'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, il dispose également de la même fonction 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ètres k et m renseignent le contrôleur. Faute d'indication contraire, les m nombres de base de g, à g, 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 à 2-'-1 (les valeurs de v/2 à v- 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 transmis 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-1).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éfinition, ne connaît pas la factorisation du module n a exactement une chance de succès sur 2(k-)'. Lorsque (k-l).m vaut de 15 à 20, un triplet suffit à 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. 1) L'acte d'engagement comprend les opérations suivantes. Lorsque le témoin dispose des m valeurs privées de Q, à Qm et du module n, il tire au hasard et en privé un ou plusieurs aléas r (0 Voici un exemple avec le premier jeu de clés avec k = 6. r = B8AD426C IAC0165E94B894AC2437C 1B 1797EF562CFA53A4AF8 43131FF1C89CFDA131207194710EF9C010E8F09C60D9815121981260 919967C3E2FB4B4566088E R = FFDD736B666F41FB771776D9D50DB7CDF03F3D976471B25C56 D3AF07BE692CB lFE4EE70FA77032BECD841 1B813B4C21210C6B04 49CC4292E5DD2BDB00828AF 18 Lorsque le témoin dispose des f facteurs premiers de p, à Pr et des m.f composantes privées Q,, il tire au hasard et en privé une ou plusieurs collections de f aléas: chaque collection comporte un aléa r, par facteur premier p, (0 il transforme chaque aléa ri en une composante d'engagement Ri. Ri -- riv (mod Pi) Voici un exemple avec le secondjeu de clés avec k= 9. ri = B0418EABEBADF0553A28903F74472CD49EE8C82D86 R. = 022B365FOBEA8E157E94A9DEB0512827FFD5149880F 1 r2 = 75A8DA8FEOE60BD55D28A218E31347732339F 1D667 R2 = 057E43A242C485FC20DEEF291 C774CF 1B30F0163DEC2 r3 = 0D74D2BDA5302CF8BE2F6D406249D148C6960A7D27 R3 = 06E 14C8FC4DD312BA3B475F 1 F40CF01 IACE2A88D5BB3C 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,... R) R = 28AA7F 12259BFBA81368EB49C93EEAB3F3EC6BF73BOEBD7 D3FC8395CFAIAD7FCOF9DAC 169A4F6F 1 C46FB4C3458DiE37C9 9123B56446F6C928736B 17B4BA4A529 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 d, d2... dm; chaque défi élémentaire d, prend l'une des valeurs de O à v/2-l. d=d, d2... dM Voici un exemple pour le premier jeu de clés avec k= 6 et m = 3. d,= 10110=22='16';d2= 00111 =7;d3=OOO10=2, d=O | d, I d2 1 1 d3=O011 looo 11100010=58E2 Voici un exemple pour le second jeu de clés avec k = 9 et m = 2. d= d, | i d2 = 58 E2 = soit en décimal, 88 et 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 calcule 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- Q Qd2... Qdm (mod n) D = r.X (mod n) Voici un exemple pour le premier jeu de clés. D = FF257422ECD3C7A03706B9A7B28EE3FC3A4E974AEDCDF386 EEF38760B859FDB5333E904BBDD37B097A989F69085FE8EF6480 A2C6A290273479FEC9171990A17 Lorsque le témoin dispose des f facteurs premiers de p, à pf et des mf composantes privées Q,1, il calcule une ou plusieurs collections de f 42 2788908 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-Q1J.Q2d...Qma, (mod pi) Di -ri.Xi (mod Pi) Voici un exemple pour le second jeu de clés. Di = r. Q"l. Q2,2 (modp,) = 02660ADF3C73B6DC 15E 196152322DDE8EB5B35775E38 * 1dl Qda(modp2 D2 =r2. À Q2 Q2.2 (m dP2)= 04C15028E5FD1175724376C1 1BE77052205F7C62AE3B D3 =r3. Q13dl. Q2.3 (mod P3)= 0903D20DOC306C8EDA9D8FB5B3BEB55E061AB39CCF52 Pour chaque collection de composantes de réponse, le témoin établit une réponse selon la technique des restes chinois. Il y a autant de réponses que de défis. D = Restes Chinois(D1, D2,... Df) D = 85C3B00296426E97897F73C7DC6341FB8FFE6E879AE12EF 1 F36 4CBB55BC44DEC437208CF530F8402BD9C511 F5FB3B3A309257A00 A7305C6FF3323F72DC 1AB 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, m k k mn R 'IG/i = D2 (mod n) ou bien R - D2.rGi (mod n) i=1 i=1 ou bien, à rétablir chaque engagement: aucun ne doit être nul. m k m R'-D2 /IiG/ (mod n) oubien R'=- D2 'G: (mod n) i=1 i=1 Eventuellement, le contrôleur calcule ensuite un code de hachage H' en 43 2788908 hachant chaque engagement rétabli R' et un message M'. L'authentification 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 partie de chaque engagement R, ou bien, le code de hachage H. Par 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 multiplication, qui s'effectue 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 g, 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 d qui indique s'il faut utiliser g,,. Voici un exemple pour le premier jeu de clés. D2 (mod n) = FD12E8E IF1370AEC9C7BA2E05C80AD2B692D341D46F3 2B93948715491FOEB09iB7606CA IE744E0688367D7BB998F7B73D5F7 FDA95D5BD6347DC8B978CA217733 3. D2 (mod n) = F739B708911166DFE715800D8A9D78FC3F332FF622D 3EAB8E7977C68AD44962BEE4DAE3C0345D i CB34526D3B67EBE8BF 987041B4852890D83FC6B48D3EF6A9DF 32.D4 (mod n) = 682A7AF280C49FE230BEE354BF6FFB30B7519E3C8 92DD07E5A781225BBD33920E5ADABBCD7284966D71141lEAA17AF 8826635790743EA7D9A 15A33ACC7491D4A7 34. D8 (mod n) = BE9D828989A2C184E34BA8FEOF384811642B7B548F 870699E7869F8ED85iFC3DB3830B2400C516511AOC28AFDD210EC3 939E69D413FOBABC6DEC441974B 1A291 35'. 5 D8 (mod n) = 2B40122E225CD858B26D27B768632923F2BBE5 DB15CA9EFA77EFA667E554A02AD IAi E4F6B59BD9E 1AE4A537D 4ACl1E89C2235C363830EBF4DB42CEA3DA98CFEOO 310. 52. D'6 (mod n) = BDD3B34C90ABBC870C604E27E7F2E9DB2D383 68EA46C931C66F6C7509B 118E3C162811A98169C30D4DEF768397DD 44 2788908 B8F6526B6714218DEB627E llFACA4B9DB268 3". 53. 7. D'6 (mod n) = DBFA7F40D338DE4FBA73D42DBF427BBF195 C13D02ABOFA5F8C8DDB5025E34282311CEF80BACDCE5DOC433444 A2AF2B 15318C36FE2AE02F3C8CB25637C9AD712F 322. 56. 72 D32 (mod n) = C60CA9C4A 1IF8AA89D9242CE717E3DC6C 1 A95D5D09A2278F8FEE 1DFD94EE84D09DOOOEA8633B53C4AOE7FOA EECB70509667A3CB052029C94EDF27611FAE286A7 322.57.72. D32 (mod n)= DE40CB6B41CO 1E722E4F312AE7205F 1 8CDD 0303EA52261CBOEA9FOC7EOCD5EC53D42E5CB645B6BB 1A3B00C77 886F4AC5222F9C863DACA440CF5F1 A8E374807AC 344 514 74. DM (mod n), c'est-à-dire, 32C. 5E. 74. D40 (mod n) avec les exposants en hexa = FFDD736B666F41FB771776D9D50DB7CDF03F3D9 76471B25C56D3AF07BE692CBIFE4EE70FA77032BECD841 lB813B4C 21210C6B0449CC4292E5DD2BDB00828AF1 8 On retrouve bien l'engagement R. L'authentification est réussie. Voici un exemple pour le second jeu de clés. D2 (mod n) = C66E5 85D8F 132F7067617BC6DOOBA699ABD74FB9D 13E 24E6A6692CC8D2FC7B57352D66D34F5273C 13F20E3FAA228D70AEC 693F8395ACEF9206B 172A8A2C2CCBB 3. D2 (mod n) = 534C6114D385C3E15355233C5B00D09C2490D1B8D8E D3D59213CB83EAD41 C309A187519E5F501C4A45C37EB2FF38FBF20 1D6D138F3999FClD06A2B2647D48283 32 D4 (mod n) = A9DC8DEA867697E76B4C18527DFFC49F4658473D03 4EC l DDEOEB21F6F65978BE477C423 1AC9B 1EBD93D5D49422408E47 15919023B 16BC3C6C46A92BBD326AADF 2.33. D4 (mod n) = FB2D57796039DFC4AF9199CAD44B66F257A1FF 3F2BA4C12BOA8496A0148B4DFBAFE838EOB5A7D9FB4394379D72A 107E45C5 1FCDB7462D03A35002D29823A2BB5 22. 36. D8 (mod n) = 4C210F96FF6C77541910623B 1E49533206DFB9E91 6521F305F 12C5DB054D4E1BF3A37FA293854DF02B49283B6DE5E5D 82ACB23DAF 1AOD5A721A1890D03A00BD8 22. 37. D8 (modn) = E4632EC4FE4565FC4B3126B15ADBF996149F2D BB42F65D91lD3851910OFE7EA53DAEA7EE7BA8FE9D081DB78B249 BlB18880616B90D4E280F564E49B270AE02388 24. 314. D'6 (mod n) = ED3DDC716AE3D1EA74C5AF935DE814BCC 2C78B 12A6BB29FA542F9981C5D954F53D 153B9F01I98BA82690EF 665C 17C399607DEA54E218C2C0iA890D422EDA16FA3 25. 314. D'6 (mod n) = DA7C64EOE8EDBE9CF823B71AB13F17E1 161487 6BOOOFBB473F5FCBF5A5D8D26C7B2A05D03BDDD588164E562DOF5 7AE94AEOAD3F35C61C0892F4C91DCOB08ED6F 2l . 32 D32 (mod n) = 6ED6AFCSA87D2DD117BOD89072C99FB9DC9 D558F65B6A 1967E6207D4ADBBA32001 D3828A35069B256A07C3D 722F17DA30088E6E739FBC419FD7282D16CD6542 2'. 328. D32 (mod n) = DDAD5F8B50FA5BA22F61B120E5933F73B92 BAAB1ECB6D432CFCC40FA95B77464003A705146AOD364AD40F8 7AE45E2FB46011 1CDCE73F78833FAE505A2D9ACA84 222. 356. D64 (mod n) = A466DOCB 17614EFD961000BD9EABF4F021 36F8307101882BC1764DBAACB715EFBF5D8309AEOO1EB5DEDA 8F000E44B3D4578E5CA55797FD4BD 1 F8E919BE787BD0 244. 3112. D128 (mod n) = 925BOEDF5047EFEC5AFABDC03A830919761 B8FBDD2BF934E2A8A31 E29B976274D513007EF1269E4638B4F65F 8FDEC740778BDC178AD7AF2968689B930D5A2359 244. 3113. D128 (mod n) = B71 1D89C03FDEA8D1F889134A4F809B3F2D 8207F2AD8213D169F2E99ECEC4FE08038900FOC203B55EE4F4C803 BFB912A04F 1D9DB9D076021764BC4F57D47834 288. 3226 D256 (mod n) = 41A83F 119FFE4A2F4AC7E5597A5DOBEB4D4C 08D 19E597FD034FE720235894363A19D6BC5AF323D24B IB7FCFD8D FCC628021B4648D7EF757A3E461EFOCFFOEA13 46 2788908 2176 3452 D512 (mod n), soit 4s. 9226 D512 (mod n) = 28AA7F12259BFBA8 1368EB49C93EEAB3F3EC6BF73BOEBD7D3FC8395CFA 1 AD7FCOF9D AC 169A4F6F 1 C46FB4C3458D 1 E37C99123B56446F6C928736B 17B4BA 4A529 On retrouve bien l'engagement R. L'authentification est réussie. Signature numérique Le mécanisme de signature numérique permet à une entité appelée signataire de produire 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 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 part, chaque défi élémentaire, de d, à dm, doit prendre une valeur de O à 2-'- 1 (les valeurs de v/2 à v-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, à g,,, sont les m premiers nombres premiers. Avec (k-1).m valant de 15 à 20, on peut signer avec quatre triplets GQ2 produits en parallèle; avec (k-l).m valant 60 ou plus, on peut signer avec un seul 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 d'engagement, un acte de défi et un acte de réponse. Chaque acte 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 (É O). Le signataire dispose d'une fonction de hachage, 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. 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 réalisation particulière, par exemple, e une carte à puce reliée à un PC formant ensemble le signataire, ou 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. 1) L'acte d'engagement comprend les opérations suivantes. Lorsque le témoin dispose des m valeurs privées de Q, à Qm et du module n, il tire au hasard et en privé un ou plusieurs aléas r (0 il transforme chaque aléa r, en une composante d'engagement R,. Ri - riv (mod Pi) Pour chaque collection def composantes d'engagement, le témoin établit un engagement selon la technique des restes chinois. Il y a autant d'engagements que de collections d'aléas. R = Restes Chinois(R1, R2,... Rf) 2) L'acte de défi consiste à hacher tous les engagements R et le message à 48 2788908 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; chaque défi élémentaire prend une valeur de 0 à v/2-1; par exemple, avec k = 9 et m = 8, chaque défi comporte huit octets. Il y a autant de défis 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 privées de Q. à Q,, et du module n, il calcule 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-QI.Q2a...Qam (mod n) D _ r.X (mod n) Lorsque le témoin dispose des f facteurs premiers de pl à p1 et des mf composantes privées QJ, il calcule une ou plusieurs collections de f 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 '}d Q od rQmi (mod Pi) Di - ri.Xi (mod Pi) Pour chaque collection de composantes de réponse, le témoin établit une réponse selon la technique des restes chinois. Il y a autant de réponses que de défis. D = Restes Chinois(D1, D2,... Df) 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éfi d et chaque réponse D correspondante. Le déroulement de l'opération de vérification dépend du contenu de l'appendice de signature. On distingue 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 indifférente. Le contrôleur accepte le message signé si et seulement si les deux conditions suivantes sont remplies. D'une part, chaque triplet doit être cohérent (une relation appropriée du type suivant doit être vérifiée) et recevable (la comparaison doit se faire sur une valeur non nulle). m k k o o R.[Gf - -D2 (mod n) oubien R D2 dG (mod n) i=1 i=1 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-l multiplications ou divisions (mod n) par des nombres de base. Pour la i ième multiplication ou division, qui s'effectue entre le i ième carré et le i+l ième carré, le i ième bit du défi élémentaire di indique s'il faut utiliser g, 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 g,. 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éfi, l'opération de contrôle commence par la reconstitution de un ou plusieurs défis 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érifiée) et recevable (la comparaison se fait sur une valeur non nulle). R.f-Gi/ D2k (mod n) u bien R -D2.f G'i (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' selon une des deux formules suivantes, celle qui est appropriée. Aucun engagement rétabli ne doit être nul. km k m R'-D2 /fG/d (mod n) ou bien R'-D2. rGd (mod n) i=1 i=1 Ensuite, le contrôleur doit hacher tous les engagements R' et le message M de façon à reconstituer chaque défis d. d= dl d2... d, identiques à ceux extraits du résultat Hash(M, R) Le contrôleur accepte le message signé si et seulement si chaque défi 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 oeuvre le procédé, le système et le dispositif selon l'invention destiné à prouver l'authenticité d'une entité et/ou l'intégrité et/ou l'authenticité d'un message. Dans la demande pendante déposée le même jour que la présente demande par France 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. Cette description détaillée de l'invention dans le cas o v = 2k est susceptible d'être généralisée à d'autres valeurs de v. C'est d'ailleurs ce qui a été exposé, en contrepoint aux revendications, dans les premières pages de la description concernant le cas o v est différent de 2k. Pour autant que cela soit nécessaire, notamment pour des raisons ressortant des règles d'écriture d'une demande de brevet, et qu'il faille également dans cette partie de la description expliciter l'invention dans le cas o v est différent de 2k, les premières pages de la description seront également supposées avoir été insérées à la suite de ce paragraphe. Revendications 1. 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é, au moyen de tout ou partie des paramètres suivants ou dérivés de ceux-ci: - m couples de valeurs privées QI, 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 public v; ledit module, ledit exposant et lesdites valeurs étant liés par des relations du type: Gi. Qiv 1. mod n ou Gi - Qv mod n ledit procédé met en ceuvre selon les étapes suivantes une entité appelée témoin disposant des f facteurs premiers p; et/ou des paramètres des restes chinois des facteurs premiers et/ou du module public n et/ou des m valeurs privées Q1 et/ou des f.m composantes Qi j (Q4 j - Q; mod p1) 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 étant calculé en effectuant des opérations du type Ri. _ rivmod pi o ri est un aléa associé au nombre premier pi tel que 0 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 - à 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écifié 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 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' - G dl. G2 d2... G dm. Dv mod n ou à 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 partie de chaque engagement R qui lui a été transmis, cas o le démonstrateur a transmis l'intégralité de chaque engagement..CLMF: 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,... Gam, vérifie que chaque engagement R satisfait à une relation du type: R = G1 dl G2 d2... Gm dm. Dvmod n ou à une relation du type, R- Dv /G G dl. G2....m 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'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 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 - le témoin calcule des réponses D à partir des défis d en appliquant 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 Gl, 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 dl. G2 d2... Gm dm. Dv mod n ou à une relation du type: R' - Dv / G1 dl. G2 d2.... Gm m. 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 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; ladite entité signataire exécute une opération de signature en vue d'obtenir 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 - à 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é selon la revendication 1. 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é; ladite entité contrôleur disposant du message signé exécute une opération de contrôle en procédant comme suit: * cas o le contrôl81eur 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érifie 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 mod n ou à des relations du type: R - Dv / G1 dl G2 d2.... Gm dm. mod n * le contrôleur vérifie que le message M, les défis d et les engagements R satisfont à la fonction de hachage d=h(M,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 d.... G dm m. Dv modn 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éfis d satisfont à la fonction de hachage d = h (MNI, 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 (MNI, 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 Gd2 2....Gm d'm. Dv mod n ou à des relations du type: R- Dv / Gl d'l. G2 d'2....Gm d'm mod n 6. Procédé selon l'une quelconque des revendications 1 à 5 tel que les composantes Qi, 1, Qi 2... Qi, f des valeurs privées Qi, sont des nombres tirés au hasard à raison d'une composante Qi,j (Q, j - Qi mod pj) pour chacun desdits facteurs premiers pj, lesdites valeurs privées Q5 pouvant être calculées à partir desdites composantes Qi, Qi, 2... Q,, 2 par la méthode des restes chinois, lesdites valeurs publiques G;, étant calculées * en effectuant des opérations du type Gi, j - Qi,j modpj * puis en appliquant la méthode des restes chinois pour établir G, tel que Gi. QV - 1. mod n ou G - Qivmod n; 7. Procédé selon la revendication 6 tel que l'exposant public de vérification v est un nombre premier, 8. Procédé selon l'une quelconque des revendications 1 à 5 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 g, inférieur aux f facteurs premiers p1, P2,... Pi; 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 xv = gi2 mod n a des solutions en x dans l'anneau des entiers modulo n 9. 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 partie des paramètres suivants ou dérivés de ceux-ci: - m couples de valeurs privées Q1, 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 public v; ledit module, ledit exposant et lesdites valeurs étant liés par des relations du type: Gi. Qiv= 1. mod nou Gi Qivmod 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 a microprocesseur, le dispositif témoin comporte une zone mémoire contenant les 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 (Qi, j =_ Qi mod pj) des valeurs privées Q; et de l'exposant public v; le 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é en effectuant des opérations du type Ri. -- riv mod pi o ri est un aléa associé au nombre premier pi tel que 0 groupe de nombres R, d, D constituant un triplet noté {R, d, D}. 10. Système selon la revendication 9 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 microcircuits logiques dans un objet nomade par exemple sous la forme d'un microprocesseur dans une carte 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 informatique, au dispositif démonstrateur; 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 témoin calculent chaque engagement R en appliquant le processus spécifié selon la revendication 9, - 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é les moyens de transmission du dispositif démonstrateur, pour transmettre tout ou partie de chaque engagement R au dispositif contrôleur, via les moyens de connexion; * étape 2: acte de défi d le dispositif contrôleur comporte des moyens de productions 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, ci-après désignés les moyens de transmission du contrôleur, pour transmettre les défis d au démonstrateur, é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é selon la revendication 9, * é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, - 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 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 d G2..... Gm DV mod n ou à une relation du type, R' _ Dv / G dG2 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çus, cas o 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 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 Gl G2 d2 Gm dmo Dv mod n ou à une relation du type, R-= Dv/ G1 dl. G2 d2 *.. Gm dm rmod n. 11. Système selon la revendication 9 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 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, - 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 informatique, au dispositif démonstrateur; 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 témoin calculent chaque engagement R en appliquant le processus spécifié selon la revendication 9, - 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; é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 dispositif démonstrateur, appliquant 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 démonstrateur, pour transmettre chaque jeton T, via les moyens de connexion, au dispositif au contrôleur, le dispositif contrôleur comporte aussi des moyens de productions de défis pour produire, après avoir reçu le jeton T, les 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 dispositif contrôleur, pour transmettre les défis d au démonstrateur, * é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é selon la revendication 9, * é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 G1, 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 G1 dl G2d2...Gm dm.Dvmodn ou à une relation du type: R' Dv / Gl d. 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 comparaison du dispositif contrôleur, pour comparer le jeton T' au jeton T reçu. 12. Système selon la revendication 9 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 système étant tel qu'il comporte un dispositif signataire associé à l'entité signataire, ledit dispositif signataire étant interconnecté 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 témoin calculent chaque engagement R en appliquant le processus spécifié selon la revendication 9, 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 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 d hachage h ayant comme arguments le message M et 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, 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 9, 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 signataire, via les moyens d'interconnexion. 13. Système selon la revendication 11 destiné à prouver l'authenticité du message M en contrôlant, par une entité appelée contrôleur, le message signé; 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, électromagnétiquement, optiquement ou de manière acoustique, notamment via un réseau de communication informatique, au dispositif démonstrateur; ledit 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éponse 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 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érifient que les engagements R, les défis d et les réponses D satisfont à des relations du type R-G dl. G2d2....Gmdm Dvmodn ou à des relations du type: R _ Dv / G1 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éfis d et les engagements R satisfont à la fonction de hachage d=h (M,R) * cas o le contrôleur dispose des défis 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' = G1 dl G2 d2.. . Gm dm. Dv mod n ou à des relations du type: R' Dv / G1 dl... G2 dm mod n les moyens de calcul et de comparaison du dispositif contrôleur vérifie que le message M et les défis d satisfont à la fonction de hachage d = h (M, R') * cas o le contrôl61eur 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 (M, 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- Gl d'l. G d'2....Gm d'm.Dvmodn ou à des relations du type: R-DvI G d'l G 2 d'2.... Gm d'm mod n 14. Système selon l'une quelconque des revendications 9 à 13 tel que les composantes Qi, Qi, 2... Q; f des valeurs privées Q;, sont des nombres tirés au hasard à raison d'une composante Q; j (Q; j - Qi mod pj) pour chacun desdits facteurs premiers pj, lesdites valeurs privées Qi pouvant être calculées à partir desdites composantes Qi, 1, Q 2... Q;, f par la méthode des restes chinois, lesdites valeurs publiques Gi, étant calculées * en effectuant des opérations du type Gi, j Qi, v modpj * puis en appliquant la méthode des restes chinois pour établir Gi tel que Gi. QiV - 1. mod n ou G =- Qiv mod n; 15. Système selon la revendication 14 tel que l'exposant public de vérification v est un nombre premier, 16. Système selon l'une quelconque des revendications 9 à 13 ledit exposant v étant tel que v =2k 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 g1 inférieur aux f facteurs premiers pl, P2,... pf; le nombre de base gi étant tel que: les deux équations: x2 = gi mod 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 - gi mod n a des solutions en x dans l'anneau des entiers modulo n 17. Dispositif terminal 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 à dispositif contrôleur, - l'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é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 Pl, 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. Qiv _1.mod n ou Gi = Qivmod n; ledit dispositif terminal comprend un dispositif témoin comportant une zone mémoire contenant les 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 Q1, j (Qi, _ Qi mod pj) des valeurs privées Q1 et de l'exposant public v; le 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é en effectuant des opérations du type R1 _ riv mod pi o ri est un aléa associé au nombre premier pi tel que 0 À- -- 2788908 D =-r- Qi, dl Q 2d2.... Qim dm mod Pi puis, en appliquant la méthode desrestes chinois; - des moyens de transmission pour 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}. 18. Dispositif terminal selon la revendication 17 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 interconnecté 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, à 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 terminal permettant d'exécuter les étapes suivantes a é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 17, - 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 dispositif contrôleur, via les moyens de connexion, étape 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é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 17, * étape 4: acte de contrôle les moyens de transmission du démonstrateur transmettent chaque réponse D au dispositif contrôleur qui procède au contrôle. 19. Dispositif terminal selon la revendication 17 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 é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 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, à 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 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 17, - 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; * étape 2 et 3: acte de défi d, acte de réponse le dispositif démonstrateur comporte des moyens de calcul, ci-après désignés les moyens de calcul du dispositif démonstrateur, appliquant 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 démonstrateur, pour transmettre chaque jeton T, via les moyens de connexion, au dispositif au contrôleur, 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é selon la revendication 17, * étape 4: acte de contrôle les moyens de transmission du démonstrateur transmettent chaque réponse D au dispositif contrôleur qui procède au contrôle. 20. Dispositif terminal selon la revendication 17 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é signataire, ledit dispositif signataire étant interconnecté 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 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, à 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 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 17, 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 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 d hachage h ayant comme arguments le message M et 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, e étape 3: acte de réponse D les moyens de réception des défis d reçoivent les défis 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 9, 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 signataire, via les moyens d'interconnexion. 22. Dispositif contrôleur, se présentant notamment sous la forme d'un terminal ou d'un serveur distant, associé à une entité contrôleur, 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 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 public v; ledit module, ledit exposant et lesdites valeurs étant liés par des relations du type: Gi. Qiv - 1. mod n ou Gi _ Qiv mod n; o Q1 désigne une valeur privée, inconnue du dispositif contrôleur, associée à la valeur publique GO. 23. Dispositif contrôleur selon la revendication 22 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 acoustique, notamment via un réseau de communication informatique, à un dispositif démonstrateur associé à l'entité démonstrateur; ledit dispositif contrôleur permettant d'exécuter les étapes suivantes: e étape 1 et 2: acte d'engagement R, acte de défi 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 productions 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 dispositif contrôleur, pour transmettre les défis d au démonstrateur, via les moyens de connexion, * étapes 3 et 4: acte de réponse, acte de contrôle le dispositif contrôleur comporte aussi - 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, - 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 reçus 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' - Gl dl. G2 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çus, 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'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 - G dl G d.... Gm dm. Dv mod n ou à une relation du type, R - Dv / G dl. G2 d2....Gm m'. mod n. 24. Dispositif contrôleur selon la revendication 22 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é à 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éfi ledit dispositif contrôleur comporte aussi des moyens de réception de jetons T provenant du démonstrateur, via les moyens de connexion, le dispositif contrôleur comporte aussi des moyens de productions 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, ci-après appelés les 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 dispositif 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 le dispositif contrôleur comporte aussi: - des moyens de réception des réponses D provenant du dispositif démonstrateur, via les moyens de connexion, 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 G1, 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 2.... G.dm DVmodn 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 T' au jeton T reçu. 25. Dispositif contrôleur selon la revendication 22 destiné à prouver l'authenticité du message M en contrôlant, par une entité appelée contrôleur, le message signé; le message signé, émis par un dispositif signataire associé à une entité signataire disposant d'une fonction de hachage h (M, R); comprenant: - le message M, - les défis d et/ou les engagements R, - les réponse D; 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é à l'entité signataire; ledit dispositif contrôleur ayant reçu 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 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érifient que les engagements R, les défis d et les réponses D satisfont à des relations du type R -G dl G 2.... Gm di. 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éfis d et les engagements R satisfont à la fonction de hachage d=h (M,R) cas o le contrôleur dispose des défis 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 dl. G2.... Gm dm DV mod n ou à des relations du type: R-Dv' /Gd G2 d....Gm dm. modn * les moyens de calcul et de comparaison du dispositif contrôleur vérifie que le message M et les défis d satisfont à la fonction de hachage d = h (M, R') * cas o le 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 (M,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 d' G '2... Gm d'm DVmod n ou à des relations du type: R- Dv / G d'. G '2.... Gm d'm mod n