FR 2788911 A1 20000728 FR 9903770 A 19990323 Procédé, système, dispositif pour diminuer la charge de travail pendant une session destinée à prouver l'authenticité d'une entité et/ou l'origine et l'intégrité 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'origine et l' intégrité d'un message. Le brevet EP 0 311470 B1 dont les inventeurs sont Louis Guillou et JeanJacques 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 . 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. La sécurité du procédé GQ est au mieux équivalente à la connaissance de la signature RSA de l'identité. Il y a équivalence lorsque l'exposant public de vérification RSA est un nombre premier. Le procédé GQ met en #uvre des calculs modulo des nombres de 512 bits ou davantage. Ces calculs concernent des nombres ayant sensiblement la même taille élevés à des puissances de l'ordre de 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, entraîne 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. L'invention a pour objet d'apporter une solution à ce problème tout en renforçant la sécurité. Plus particulièrement, l'invention concerne un procédé pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m. Procédé Le procédé selon l' invention, met en #uvre les trois entités ci-après définies. I. Une première entité, appelée témoin, dispose des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p1.p2. p3.... Le témoin dispose aussi * des composantes QA,, à,,... (QA,, ...), et QB,, QB2, ... (QB,, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GA2, ... (GA,...) et GB,, GB2, ... (GBi 1...) * des exposants publics de vérification vx, vy, ... Les clés privées et les clés publiques sont liées par des relations du type : GA.QA" mod n = 1 ou GA =- QA'mod n Les exposants publics de vérification vx, vy,... sont utilisés par le témoin pour calculer des engagements R en effectuant des opérations du type : R = rivx mod p, ou r est un aléa tel que 0 Ainsi, selon le nouveau procédé, les rôles de témoin et d'autorité de confiance fusionnent. Chaque témoin utilise la factorisation p,, p2, ... (pi, ...) de son propre module public n. De sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des R; pour chacun des pi est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. L'usage de la factorisation du module n réduit significativement la charge de travail du témoin. Par rapport au procédé GQ, et a fortiori par rapport à d'autres procédés tel que le procédé RSA de signature, le procédé selon l'invention permet de substantielles économies de calcul, en particulier pour l'authentification. II. Le procédé selon l' invention met en #uvre une deuxième entité pilote dudit témoin. Cette entité pilote est appelée * démonstrateur dans le cas de la preuve de l'authenticité d'une entité ou de l'authenticité d'un message, * signataire dans les cas de la preuve de l'origine et de l'intégrité d'un message. On verra ci-après quel est son rôle. III. La troisième entité, appelée contrôleur, vérifie l'authentification ou l'origine et l'intégrité d'un message. Selon l'invention, le témoin reçoit de la deuxième entité pilote ou du contrôleur un ou plusieurs défis d tel que 0 # d # vx - 1 et calcule à partir de ce défi une ou plusieurs réponses D en effectuant des opérations du type : Di = ri.QAi d mod p, ou r. est un aléa tel que 0 Le contrôleur reçoit, selon le cas, une ou plusieurs réponses D. Il calcule, à partir desdites réponses D, les engagements R' en effectuant des opérations du type : R', = GA d. D"X mod n ou du type : R'.. GA d --~ D"mod n Le contrôleur peut alors vérifier que les triplets {R', d, D} sont cohérents. Dans le cas général qui vient d'être exposé, il y a plusieurs exposants de vérifications vx, vy,.... On va maintenant exposer l'invention dans le cas où l'exposant de vérification v est unique. Cas où l'exposant de vérification v est unique De même que précédemment, le procédé selon l' invention met en #uvre trois entités : I. Une première entité, appelée témoin, dispose des facteurs premiers p,, p2, ... (pi, ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p.p2. p3..... Le témoin dispose aussi * des composantes QA,, QA2, ... (QA, , ou), et QBI, QB2, ... (QB, , ou), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA,...) et GB,, GB2, ... (GBi5 ...) * de l'exposant public de vérification v Dans ce cas comme dans le précédent, il est prévu plusieurs paires de clés référencées A, B, ... Les paires de clés privées et publiques sont liées par des relations du type : GA.QA" mod n = 1 ou GA QA'mod n L'exposant public unique de vérification v est utilisé par le témoin pour calculer des engagements R. A cet effet : * il effectue des opérations du type : Ri # r1v mod p, où r est un entier, tiré au hasard, associé au nombre premier p,, tel que 0 r Il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, Bien entendu, dans ce cas comme dans le cas général précédent, le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. II. La deuxième entité pilote dudit témoin est appelée : * démonstrateur dans le cas de la preuve de l'authenticité d'une entité ou de l'authenticité d'un message, * signataire dans les cas de la preuve de l'origine et de l'intégrité d'un message, III. La troisième entité, appelée contrôleur, vérifie l'authentification ou l'origine et l'intégrité d'un message. Plus particulièrement, dans le cas de cette variante de réalisation le témoin reçoit de la deuxième entité ou du contrôleur, des collections de défis d {dA, dB, ...}tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...} comprend un nombre de défis égal au nombre de paires de clés. Le témoin calcule à partir de chacune desdites collections de défis {dA, dB, ...} des réponses D. A cet effet : . il effectue des opérations du type : D = ri. QAdA. QB dB .... mod p. puis il applique la méthode des restes chinois. Il y a autant de réponses D que d'engagements R et de défis d. Il convient de souligner, ici aussi, que le nombre d'opérations arithmétiques modulo p1 à effectuer pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le contrôleur reçoit une réponse D. Il calcule à partir de cette réponse un engagement R' en effectuant des opérations du type : R'= GA dA. GB dB. ...Dv mod n ou du type : R'. GA dA. GB dB. ... # Dv mod n Le contrôleur vérifie que les triplets {R', d, D} sont cohérents. Ainsi, grâce à la présente invention, le témoin qui proclame : Voici une clé publique de vérification (v, n) et une clé publique GA ; je connais la factorisation de n et la clé privée QA prouve sans la révéler qu'il connaît la clé privée QA. Le contrôleur vérifie la clé privée QA sans en prendre connaissance. Les mécanismes se déroulent sans transfert de connaissance . On le verra ci-après, que le procédé selon l'invention autorise certaines paires de clés telles que la connaissance de la clé privée QA est équivalente à la connaissance de la factorisation du module n. On va maintenant exposer les variantes de réalisation de l'invention concernant : - le cas d'une authentification d'entité, - le cas d'une authentification de message, - le cas d'une signature numérique de message. Cas d'une authentification d'entité Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur l'authenticité d'une entité. Comme dans le cas général, la session met en #uvre trois entités. I. Une première entité, appelée témoin, dispose des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = PI*P2* p3.... , Le témoin dispose aussi : * des composantes QA,, Qu 21 ... (QAI, ...), et QB,, QB2, ... (QB , ou), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA(, ...) et GB,, GBz, ... (GB ...) * de l' exposant public de vérification v Les paires de clés privées et publiques sont liées par des relations du type : GA.QAv mod n = 1 ou GA = QA'mod n II. La deuxième entité, pilote dudit témoin, est appelée démonstrateur. III. La troisième entité, appelée contrôleur, vérifie l'authentification. Pour prouver l'authenticité d'une entité, le témoin, le démonstrateur et le contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : A chaque appel, le témoin tire au hasard et en privé au moins une collection de nombres entiers {r,, r2, r3, ...},telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r positif et plus petit que p, Pour chaque facteur premier p1, le témoin élève chaque aléa r@ à la puissance v ième modulo p@ R@ # riv mod p, On notera que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Puis, le témoin établit chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, # étape 2. défi d destiné au témoin : Le démonstrateur transmet tout ou partie de chaque engagement R au contrôleur. Le contrôleur, après avoir reçu tout ou partie de chaque engagement R, produit au moins une collection de défis d {dA, dB, ...} tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...} comprend un nombre de défis égal au nombre de paires de clés. # étape 3. réponse du témoin au défi d : Le témoin calcule des réponses D à partir des collections de défis d {dA, dB, ...} reçues du contrôleur. A cet effet : il effectue des opérations du type : D 1 == r.. 1 QA 1 dA . QB 1 dB .... mod P puis, il applique la méthode des restes chinois. Le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au contrôleur : Le démonstrateur transmet au contrôleur chaque réponse D. # étape 5. vérification par le contrôleur : Le contrôleur calcule à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'=GA d" . GB "B .... Dv mod n ou du type : R'.GAdA.GBdB....=D"modn Le contrôleur vérifie que chaque engagement reconstruit R' reproduit tout ou partie de chaque engagement R transmis à l' étape 2 par le démonstrateur. Cas d'une authentification de message cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur l'authenticité d'un message m. Comme dans le cas général, la session met en #uvre trois entités. I. Une première entité, appelée témoin, dispose des facteurs premiers p,, p2, ... (pi,...) (i étant supérieur ou égal à 2) d'un module public n tel que n = PL-PI' p3.... , Le témoin dispose aussi : * des composantes QA,, QA,, ... (QA, , ou), et QB., QB2 ... (QB, ou), ..., représentant des clés privées QA, QB, * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAz, .h (GA, ...) et GB,, GB2, ... (GD" ...) * de l'exposant public de vérification v Les paires de clés privées et publiques sont liées par des relations du type : GA.QA" mod n = 1 ou GA =- QAvmod n II. Une deuxième entité, pilote du témoin, est appelée démonstrateur. III. Une troisième entité, appelée contrôleur, vérifie l'authenticité d'un message. Pour prouver l'authenticité d'un message le témoin, le démonstrateur et le contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : A chaque appel, le témoin tire au hasard et en privé au moins une collection de nombres entiers {r,, r2, r3, ...}, telle que pour chaque facteur premier p,, chaque collection comporte un aléa r. positif et plus petit que p, . Pour chaque facteur premier p1, le témoin élève chaque aléa r, à la puissance v ième modulo p, R = r@v mod p, (de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des R1 pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n) Puis, le témoin établit chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, # étape 2. défi d destiné au témoin : Le démonstrateur applique une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour obtenir un jeton T. Le démonstrateur transmet le jeton T au contrôleur, Le contrôleur, après avoir reçu le jeton T, produit au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...}comprend un nombre de défis égal au nombre de paires de clés. # étape 3. réponse du témoin au défi d : Le témoin calcule les réponses D à partir des collections de défis d {dA, dB, ...}reçues du contrôleur. A cet effet, il effectue des opérations du type : D 1 == r . 1 QA 1 dA . QB 1 dB .... mod P. puis, il applique la méthode des restes chinois. Le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au contrôleur : Le démonstrateur transmet au contrôleur chaque réponse D. # étape 5. vérification par le contrôleur : Le contrôleur calcule à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' = GA dA. GB dB .... D" mod n ou du type : R'. GA dA . GB dB....= Dv mod n Le contrôleur applique la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R' pour reconstruire le jeton T'. Le contrôleur vérifie que le jeton T' est identique au jeton T transmis à l'étape 2 par le démonstrateur. Cas d'une signature numérique de message Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur la signature numérique d'un message m. Comme dans le cas général, la session met en oeuvre trois entités. I. Une première entité appelée témoin dispose des facteurs premiers p,, p2, ... (p@,...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p1.p2.p3. ... Le témoin dispose aussi * des composantes QA,, QA,, ... (QA,, ...), et QB,, QBz, ... (QB,, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA,,...) et GB,, GB2, ... (GB,, ...) * de l'exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QAV mod n =- 1 ou GA =- QAvmod n II. Une deuxième entité, pilote dudit témoin, est appelée signataire. III. Une troisième entité, appelée contrôleur, vérifie la signature du message m. Pour prouver la signature d'un message le témoin, le démonstrateur et le contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : A chaque appel, le témoin tire au hasard et en privé au moins une collection de nombres entiers {ri, r., r, ...},telle que, pour chaque facteur premier p., chaque collection comporte un aléa r, positif et plus petit que p, . Pour chaque facteur premier p , le témoin élève chaque aléa r, à la puissance v ième modulo p, R, = riv mod p@ (de sorte que le nombre d'opérations arithmétiques modulo p1 à effectuer pour calculer chacun des R1 pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n) Puis, le témoin établit chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d'aléas {r,, r2, r3, ...}. # étape 2. défi d destiné au témoin : Le signataire applique une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour obtenir au moins une collection de défis d {dA, dB, ...}tels que 0 Le signataire transmet les collections de défis d au témoin. # étape 3. réponse du témoin au défi d : Le témoin calcule des réponses D à partir desdites collections de défis d {dA, dB, ...}reçues du contrôleur. A cet effet, il effectue des opérations du type : D 1 == r . 1 QA 1 dA . QB 1 dB .... mod P (de sorte que le nombre d'opérations arithmétiques modulo p1 à effectuer pour calculer chacun des D1 pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n) puis, il applique la méthode des restes chinois. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. Le témoin transmet les réponses D au signataire et/ou au contrôleur. # étape 4. données destinées au contrôleur : Le signataire transmet un message signé au contrôleur comprenant : - le message m, - les collections de défis d ou les engagements R, - chaque réponse D # étape 5. vérification par le contrôleur : Cas où le contrôleur reçoit la collection des défis d, Dans le cas où le contrôleur reçoit la collection des défis d et des réponses D, ledit contrôleur calcule à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' - GA d" . GB dB .... D" mod n ou du type : R' . GA dA. GB dB. no:::: D' mod n Le contrôleur applique la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R' pour reconstruire chaque défi d'. Le contrôleur vérifie que chaque défi d' reconstruit est identique au défi d figurant dans le message signé. Cas où le contrôleur reçoit la collection des engagements R Dans le cas où le contrôleur reçoit la collection des engagements R et des réponses D, ledit contrôleur applique la fonction de hachage f ayant comme arguments le message m et chaque engagement R pour reconstruire chaque défi d'. Le contrôleur reconstruit alors la collection des engagements R' en effectuant des opération du type R' - GA d'A GR d'B Dv mod n ou du type : R'. GA d'A GB dB .... --~ D" mod n Le contrôleur vérifie que chaque engagement R' reconstruit est identique à l'engagement R figurant dans le message signé. Paire de clés selon la présente invention conférant une sécurité équivalente à la connaissance de la clé privée Q La paire de clés GA, QA, ... n'a plus de raison d'être systématiquement déduite de l'identité du témoin, comme dans le cas du procédé GQ. Selon une variante de réalisation, un grand nombre de témoins utilisent le même ensemble de clés publiques très courtes GA, GB, GC, GD... par exemple, 4,9, 25 et 49. Dans le cas de la variante de réalisation ci-après exposée les composantes QA,, Qat, ... (QA, , ...), et QB,, QB,, ... (QB, , ...), ... des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA, , QB;, ... pour chacun desdits facteurs premiers p1. Lesdites clés privées QA, QB, peuvent être calculées à partir desdites composantes QA,, QA2, ... (QA" ou), et QBI, QB29 ... (QB" ...), ... par la méthode des restes chinois. Les clés publiques GA, GB, ... sont calculées en effectuant des opérations du type : GA.= QAiv mod p, puis en appliquant la méthode des restes chinois pour établir GA tel que GA =- QAv mod n ou bien tel que GA.QA" mod n = 1 Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des GA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. De préférence l'exposant public de vérification v est un nombre premier. Dans ce cas la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. Paire de clés selon la présente invention conférant une sécurité équivalente à la connaissance de la factorisation de n De préférence, l'exposant public de vérification v est du type k v=a où k est un paramètre de sécurité plus grand que 1. De préférence, également l'exposant public de vérification v est du type v = 2k où k est un paramètre de sécurité plus grand que 1. Dans ce cas, la clé publique GA est un carré gA2 inférieur à n choisi de sorte que les deux équations x = gA mod n et x2 --~ - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n. Les composantes QA,, QA2, ... (QA@, ...) de la clé privée QA sont alors telles que : GA QA2exp(k) mod p, ou bien telles que : GA QAI 2 ex p(k) mod p,=- 1 On les obtient en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p,), Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des QAi pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. On démontre que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. De préférence, pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p,), on utilise les méthodes suivantes : - dans le cas où le facteur premier p, est congru à 3 modulo 4, on applique notamment un algorithme du type : x = (p+I)/4 ; y xk mod (p-1) ; z = y ; QA@ GAZ mod p - dans le cas où le facteur premier p, est congru à 1 modulo 4, on emploie les suites de Lucas. Système La présente invention concerne également un système permettant de mettre en #uvre le procédé ci-dessus exposé. Le système selon l'invention permet de diminuer la charge de travail pendant une session destinée à prouver à un serveur contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m. Le système met en #uvre trois entités : I. Une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présente par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = PI'PZ' p3..... Le dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QA,, QAz, ... (QA,, on), et QBI, QB2' ... (QB,, on), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (gaz, ...) et GB,, Go 21 ... (GB,, ...) * des exposants publics de vérification vx, vy, ... lesdites clés privées et clés publiques étant liées par des relations du type : GA.QA" mod n = 1 ou GA QA"mod n Le dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R en effectuant des opérations du type : R, - r," mod p, ou r, est un aléa tel que 0 Le dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur un ou plusieurs défis d tel que 0 # d # vx - 1. Il comporte des deuxièmes moyens de calcul pour calculer à partir des défis d une ou plusieurs réponses D en effectuant des opérations du type : D,---r.QA,dmodp; ou r est un aléa tel que 0 Le dispositif contrôleur, reçoit une ou plusieurs réponses D. Il comporte des troisièmes moyens de calcul pour calculer à partir desdites réponses D des engagements R' en effectuant des opérations du type : R'--~GAd.D"x modn ou du type : R'.GAd--~D"zmodn Le dispositif contrôleur comporte des quatrièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents. Cas où l'exposant de vérification v est unique De même que précédemment, le système selon l'invention met en #uvre trois entités. I. Une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, ,...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ..., Le dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QA,, QA2, ... (QA" ...), et QB,l QB2, on (QB , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GA2, ... (GA,,on) et GB,, GB2, ... (GB1,...), * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA" mod n = 1 ou GA QA'mod n Le dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R. A cet effet, # il effectue des opérations du type : R, - r/ mod p, où r est un entier, tiré au hasard, associé au nombre premier p,, tel que 0 II y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, Le nombre d'opérations arithmétiques modulo p, à effectuer par lesdits premiers moyens de calcul pour calculer chacun des R, pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. II. La deuxième entité, appelée dispositif pilote dudit dispositif témoin, peut être contenue notamment dans ledit objet nomade. Le dispositif pilote est appelé : * dispositif démonstrateur dans le cas de la preuve de l'authenticité d'une entité ou de l'authenticité d'un message, * dispositif de signature dans les cas de la preuve de l'origine et de l' intégrité d'un message, III. La troisième entité, appelée dispositif contrôleur, se présente notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. Le dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin. Le dispositif contrôleur vérifie l'authentification ou l'origine et l'intégrité d'un message, Plus particulièrement, dans le cas de cette variante de réalisation, le dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur, des collections de défis d {dA, dB, ...} tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...} comprend un nombre de défis égal au nombre de paires de clés. Le dispositif témoin comporte des deuxièmes moyens de calcul pour calculer à partir de chacune desdites collections de défis {dA, dB, ...}des réponses D. A cet effet, # il effectue des opérations du type : D r,. QAI dA . QB, '".... mod p, # puis, il applique la méthode des restes chinois. Il y a autant de réponses D que d'engagements R et de défis d. Il convient de souligner, ici aussi, que le nombre d'opérations arithmétiques modulo p, à effectuer par lesdits deuxièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Le dispositif contrôleur reçoit une ou plusieurs réponses D. Il comporte des troisièmes moyens de calcul pour calculer à partir desdites réponses D un engagement R' en effectuant des opérations du type : R' = GA dA. GB dB. ... Dv mod n ou du type : R'. GA dA. GB dB. ... # Dv mod n Le dispositif contrôleur comporte des quatrièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents. On va maintenant exposer les variantes de réalisation du système selon l'invention concernant : - le cas d'une authentification d'entité, - le cas d'une authentification de message, - le cas d'une signature numérique de message. Cas d'une authentification d'entité Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur l'authenticité d'une entité. Comme dans le cas général, le session met en #uvre trois entités du système selon l'invention. I. Une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p.p2. p3..... Le dispositif témoin dispose aussi d'une deuxième zone mémoire contenant : * des composantes QAI, QA2, ... (QA , ...), et QBI, QB2, ... (QB,, ou), ..., représentant des clés privées QA, QB, .... * des clés publiques GA, GB,... ayant respectivement pour composantes GAI, GAZ, ... (GA., ...) et GB,, GB2, ... (GB,, ...) * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA mod n = 1 ou GA - QA'mod n II. La deuxième entité, appelée dispositif démonstrateur dudit dispositif témoin, peut être contenue notamment dans ledit objet nomade. III. Une troisième entité, appelée dispositif contrôleur, se présente sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. Le dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin, Pour prouver l'authenticité d'une entité, ledit dispositif témoin, ledit dispositif démonstrateur et ledit dispositif contrôleur exécutent les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {ruz, r29 r3, ...}, telle que, pour chaque facteur premier P" chaque collection comporte un aléa r positif et plus petit que p, . Le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r, à la puissance v ième modulo p; , pour chaque facteur premier p , R@ # r@v mod p, On notera que le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Puis, lesdits deuxièmes moyens de calcul du dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, # étape 2. défi d destiné au dispositif témoin : Le dispositif démonstrateur comporte des moyens de transmission pour transmettre tout ou partie de chaque engagement R au dispositif contrôleur. Le dispositif contrôleur comporte des troisièmes moyens de calcul pour calculer, après avoir reçu tout ou partie de chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...}comprend un nombre de défis égal au nombre de paires de clés. # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. A cet effet, il effectue des opérations du type : D. 1 == r . 1 QA 1 dA . QB 1 dB .... mod P puis, il applique la méthode des restes chinois. Le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au dispositif contrôleur : Le démonstrateur comporte des moyens de transmission pour transmettre au dispositif contrôleur chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'= GA dA . Gg dB .... D" mod n ou du type : R'. GA dA. GB "\ ...= DY mod n Le dispositif contrôleur comporte des sixièmes moyens de calcul pour comparer et vérifier que chaque engagement reconstruit R' reproduit tout ou partie de chaque engagement R transmis à l'étape 2 par le dispositif démonstrateur. Cas d'une authentification de message Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur l'authenticité d'un message m. Comme dans le cas général, la session met en #uvre trois entités du système. I. Une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présente par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (pi, ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = PI.P2. p3.... ,.Le dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QA,, QA2, ... (QA,, ...), et QB,, QB2, ... (QB, ...), ..., représentant des clés privées QA, QB, ... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA, ...) et GBI, GB2, ... (GB, ...) * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA mod n = 1 ou GA # QA'mod n II. Une deuxième entité, appelée dispositif démonstrateur dudit dispositif témoin, peut être contenue notamment dans ledit objet nomade. III. Une troisième entité, appelée dispositif contrôleur, se présente sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. Le dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin. Pour prouver l'authenticité d'un message ledit dispositif témoin, ledit dispositif démonstrateur et ledit dispositif contrôleur exécutent les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r,, r2, r3, ...}, telle que pour chaque facteur premier p,, chaque collection comporte un aléa r positif et plus petit que p, . Le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa ri à la puissance v ième modulo p, , pour chaque facteur premier p, , Ri # riv mod p, Le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d' aléas {r1, r2, r3, ...}. # étape 2. défi d destiné au dispositif témoin : Le dispositif démonstrateur comporte des premiers moyens de calcul pour calculer un jeton T, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R. Le dispositif démonstrateur comporte des moyens de transmission pour transmettre le jeton T au dispositif contrôleur. Le dispositif contrôleur comporte des troisièmes moyens de calcul pour calculer, après avoir reçu le jeton T, au moins une collection de défis d {dA, dB, ...} tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...} comprend un nombre de défis égal au nombre de paires de clés. # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. A cet effet, il effectue des opérations du type : D --~ ruz . QA d" . QBI dll mod p puis, il appliquant la méthode des restes chinois. Le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au dispositif contrôleur : Le démonstrateur comporte des moyens de transmission pour transmettre au dispositif contrôleur chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' --~ GA d" . GB dB .... D" mod n ou du type : R'. GA dA. GB dB....= DV mod n Le dispositif contrôleur comporte des sixièmes moyens de calcul pour calculer, en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R', le jeton T'. Le dispositif contrôleur comporte des septièmes moyens de calcul pour comparer et vérifier que le jeton T' est identique au jeton T transmis à l'étape 2 par le dispositif démonstrateur. Cas d'une signature numérique de message Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur la signature numérique d'un message m. Comme dans le cas général, la session met en #uvre trois entités du système : I. Une première entité, appelée dispositif témoin, contenues notamment dans un objet nomade se présente par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p,, p2, ... (p1, ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p..p,. P3. m . Le dispositif témoin comporte également une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA,, ...), et QBI, QB2, ... (QB. ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GA2, ... (GA, ...) et GB,, GB2, ... (GB,, m) * un exposant publique de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA" mod n = 1 ou GA = QA'mod n II. Une deuxième entité, pouvant être contenue notamment dans ledit objet nomade, est appelée dispositif de signature. III. Une troisième entité, appelée dispositif contrôleur se présente sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. Le dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique au dispositif témoin. Pour prouver la signature d'un message, ledit dispositif témoin, ledit dispositif démonstrateur et ledit dispositif contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : Le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r1, r2, r3, ...}, telle que pour chaque facteur premier p,, chaque collection comporte un aléa r, positif et plus petit que p, . Le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r, à la puissance v ième modulo p, , pour chaque facteur premier p , Ri =- r1v mod p, Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Puis, lesdits deuxièmes moyens de calcul du dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d' aléas {r1, r2, r3, ...}, # étape 2. défi d destiné au dispositif témoin : Le dispositif de signature comporte des troisièmes moyens de calcul pour calculer, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA Le dispositif de signature transmet les collections de défis d au dispositif témoin, # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. A cet effet, il effectue des opérations du type : D ri . QAT dA . QB, dB .... mod p, puis, il applique la méthode des restes chinois. Le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. Le dispositif témoin comporte des moyens de transmission pour transmettre les réponses D au dispositif de signature et/ou au dispositif contrôleur. # étape 4. données destinées au dispositif contrôleur : Le dispositif de signature transmet au dispositif contrôleur un message signé comprenant : - le message m, - les collections de défis d ou les engagements R, - chaque réponse D # étape 5. vérification par le dispositif contrôleur : Cas où le dispositif contrôleur reçoit la collection des défis d, Dans le cas où le dispositif contrôleur reçoit les collections des défis d et des réponses D, ledit dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'=GA d" . GB de ....Dv mod n ou du type : R'. GA dA. GB d$ .... = D" mod n Le dispositif contrôleur comporte des sixièmes moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R'. Le dispositif contrôleur comporte des septièmes moyens de calcul pour comparer et vérifier que chaque défi d' est identique au défid figurant dans le message signé. Cas où le dispositif contrôleur reçoit la collection des engagements R Dans le cas où le dispositif contrôleur reçoit la collection des engagements R et des réponses D, ledit dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R. Le dispositif contrôleur comporte des sixièmes moyens de calcul pour calculer alors la collection des engagements R' en effectuant des opération du type R'= GA d'A GB d'$ .... Du mod n ou du type : R'.GAd'".GBd'B....--~D"modn Le dispositif contrôleur comporte des septièmes moyens de calcul pour comparer et vérifier que chaque engagement R' reconstruit est identique à l'engagement R figurant dans le message signé. Paire de clés conférant une sécurité équivalente à la connaissance de la clé privée Q Dans le cas de la variante de réalisation ci-après exposée les composantes QA,, QA2, ... (QA...), et QB,, QB2, ... (QB,...), ... des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA, , QB, , ... pour chacun desdits facteurs premiers p1, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA,, QA2, ... (qat, ...), et QB,, QB2, ... (QB" ...), ... par la méthode des restes chinois. Dans le cas de cette variante, le dispositif témoin comporte des huitièmes moyens de calcul pour calculer lesdites clés publiques GA, GB, ..., # en effectuant des opérations du type : GA = QA 1 v mod P #puis en appliquant la méthode des restes chinois pour établir GA tel que GA --~ QA" mod n ou bien tel que GA.QA mod n = 1 Le nombre d'opérations arithmétiques modulo p, àeffectuer par les huitièmes moyens de calcul dudit dispositif témoin pour calculer chacun des GA, pour chacun des p, est réduit par rapport par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. De préférence dans ce cas, l'exposant public de vérification v est un nombre premier. Il en résulte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. Paire de clés conférant une sécurité équivalente à la connaissance de la factorisation de n De préférence, l'exposant public de vérification v est du type v = a où k est un paramètre de sécurité plus grand que 1. De préférence également, l'exposant public de vérification v est du type v = 2" où k est un paramètre de sécurité plus grand que 1, Dans ce cas, la clé publique GA est un carré gA2 inférieur à n choisi de sorte que les deux équations x2= gA mod n et x2 # - gA mod n n'ont pas de solution en x dans l' anneau des entiers modulo n. Le dispositif témoin comporte des neuvièmes moyens de calcul pour calculer les dites composantes QA,, QA2, ... (QA,, ...) de la clé privée QA en appliquant des formules telles que : GA =- QA2exp(k) mod p, ou bien telles que : GA .QA 2.exp(k)mod P,= 1 et en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p,). Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les neuvièmes moyens de calcul du dispositif témoin pour calculer chacun des QA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. On démontre que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. De préférence, pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p), on utilise les méthodes suivantes : - dans le cas où le facteur premier p, est congru à 3 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme du type : x = (p+l)/4 ;y # xk mod (p-1) ; z = y ;QA@ GAZ mod p, - dans le cas où le facteur premier p, est congru à 1 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme basé sur les suites de Lucas. Objet nomade. Carte bancaire La présenté invention concerne également un objet nomade permettant de mettre en #uvre le procédé ci-dessus exposé. L'objet nomade selon l'invention se présente, par exemple, sous la forme d'une carte bancaire à microprocesseur. Il permet de diminuer la charge de travail pendant une session destinée à prouver à un serveur contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m, L'objet nomade fait intervenir trois entités : I. Une première entité, appelée dispositif témoin, est contenue dans ledit objet nomade. Le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p,. p3..... Le dispositif témoin dispose aussi d'une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA,,ou), et QB,, QB2, ... (QB,,ou), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA,, ou) et GB,, GB2, ... (GB,, ...) * des exposants publics de vérification vx, vy, ... Les clés privées et les clés publiques sont liées par des relations du type : GA.QA" mod n = 1 ou GA -= QAvx mod n Le dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R en effectuant des opérations du type : R = r1vx mod p, ou r est un aléa tel que 0 Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par lesdits premiers moyens de calcul pour calculer chacun des R pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. II. Une deuxième entité est appelée dispositif pilote dudit dispositif témoin. Elle peut être également contenue dans ledit objet nomade. Le dispositif pilote est appelé : * dispositif démonstrateur dans le cas de la preuve de l' authenticité d'une entité ou de l'authenticité d'un message, * dispositif de signature dans les cas de la preuve de l'origine et de l'intégrité d'un message, III. Une troisième entité, appelée dispositif contrôleur, se présente notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. Le dispositif contrôleur vérifie l'authentification ou l'origine et l'intégrité d'un message, L'objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif pilote audit dispositif contrôleur. Le dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur un ou plusieurs défis d tel que 0 # d # vx - 1 et comporte des deuxièmes moyens de calcul pour calculer à partir dudit défi d une ou plusieurs réponses D en effectuant des opérations du type : D 1 == r . 1 QA 1 d mod P ou r, est un aléa tel que 0 Ainsi, le nombre d'opérations arithmétiques modulo p à effectuer par lesdits deuxièmes moyens de calcul pour calculer chacune des réponses D, pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n. L'objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur la ou les dites réponses D. Cas où l'exposant de vérification v est unique De même que précédemment, l'objet nomade fait intervenir trois entités : I. Une première entité, appelée dispositif témoin, est contenue dans ledit objet nomade. Le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p., p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un.module public n tel que n = p,.p2. p3..... Le dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QAI, QA2, (QA ...), et QB1, QB2, ... (QB" ou), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, Go 21 ... (GA, ...) et GB1, GB2, ou (GB,, ou) * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA mod n = 1 ou GA = QAv mod n Le dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R, * en effectuant des opérations du type : R = r1v mod p. où r, est un entier, tiré au hasard, associé au nombre premier p@, tel que 0 ru lesdits premiers moyens de calcul pour calculer chacun des R, pour chacun des pi est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n. II. Une deuxième entité est appelée dispositif pilote dudit dispositif témoin. Elle peut être également contenue dans ledit objet nomade. Le dispositif pilote est appelé : * dispositif démonstrateur dans le cas de la preuve de l'authenticité d'une entité ou de l'authenticité d'un message, * dispositif de signature dans les cas de la preuve de l'origine et de l'intégrité d'un message. III. Une troisième entité, appelée dispositif contrôleur, se présente notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. Le dispositif contrôleur vérifie l' authentification ou l'origine et l' intégrité d'un message. L'objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif pilote audit dispositif contrôleur. Le dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur, des collections de défis d {dA, dB, ...}tels que 0 # dA # v - 1. Le nombre des collections de défis d étant égal au nombre d'engagements R. Chaque collection {dA, dB, ...} comprend un nombre de défis égal au nombre de paires de clés. Le dispositif témoin comporte des deuxièmes moyens de calcul pour calculer à partir de chacune desdites collections de défis {dA, dB, ...}des réponses D. A cet effet, # il effectue des opérations du type : D = r . QA, d" . QB 1 dB .... mod p, # puis, il appliquant la méthode des restes chinois. Il y a autant de réponses D que d'engagements R et de défis d. Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par lesdits deuxièmes moyens de calcul pour calculer chacun des Di pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. L'objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur la ou lesdites réponses D. On va maintenant exposer des variantes de réalisation de l'objet nomade selon l'invention concernant : - le cas d'une authentification d'entité, - le cas d'une authentification de message, - le cas d'une signature numérique de message. Cas d'une authentification d'entité Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un dispositif contrôleur l'authenticité d'une entité. Comme dans le cas général, la session fait intervenir trois entités. I. Une première entité, appelée dispositif témoin, est contenue dans ledit objet nomade. Le dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ou) (i étant supérieur ou égal à 2) d'un module public n tel que n = p1.p2. p3..... Le dispositif témoin comporte aussi une deuxième zone mémoire contenant : * des composantes QAI, QA 29 *** (QA ...), et QBI, QB2, ... (QB, , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GA2, ... (GA, ...) et GBI, GBz, ... (GB ...) * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QAv mod n 1 ou GA = QAvmod n II. Une deuxième entité est appelée dispositif démonstrateur du dispositif témoin. Elle peut être également contenue dans ledit objet nomade. III. Une troisième entité, appelée dispositif contrôleur, se présente notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. L'objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif démonstrateur audit dispositif contrôleur. Pour prouver l'authenticité d'une entité, ledit objet nomade exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {roi, r25 r3, ...}, telle que, pour chaque facteur premier P" chaque collection comporte un aléa r, positif et plus petit que p, . Le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa ri à la puissance v ième modulo p, , pour chaque facteur premier p,, R = r1v mod p, Ainsi, le nombre d'opérations arithmétiques modulo p@ à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n) Puis, lesdits deuxièmes moyens de calcul du dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}. # étape 2. transmission des engagements R et réception des défis d destinés au dispositif témoin : L'objet nomade comporte des moyens de transmission pour transmettre au dispositif contrôleur tout ou partie de chaque engagement R. L'objet nomade comporte des moyens de réception pour recevoir des collections de défis d {dA, dB,...}produits par ledit dispositif contrôleur. # étape 3. réponse du dispositif témoin aux défis d : Le dispositif témoin comporte des troisièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. A cet effet, il effectue des opérations du type : Di--~r.QAd".QBdB....modp, puis, il applique la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les troisièmes moyens de calcul pour calculer chacun des Di pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au dispositif contrôleur : L'objet nomade comporte des moyens de transmission pour transmettre au dispositif contrôleur tout ou partie de chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur vérifie la cohérence des triplets {R, d, D} et l'authenticité de l'entité contrôlée. Cas d'une authentification de message Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur l'authenticité d'un message m. Comme dans le cas général, l'objet nomade fait intervenir trois entités : I. Une première entité, appelée dispositif témoin, est contenue dans ledit objet nomade,. Le dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p., p2, ... (p1, ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p..p,. p3..... Le dispositif témoin comporte aussi une deuxième zone mémoire contenant * des composantes QA,, QAz, ... (QA ...), et QB,, QB2, ... (QB,, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA, ...) et GB,, GB2, ... (GB, ...) * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA' mod n = 1 ou GA = QA'mod n II. Une deuxième entité, est appelée démonstrateur dudit dispositif témoin. Elle peut être également contenue dans ledit objet nomade. III. Une troisième entité appelée dispositif contrôleur se présente sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. L'objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif démonstrateur audit dispositif contrôleur. Pour prouver l'authenticité d'un message ledit objet nomade exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r,, r2, r3, ...}, telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r positif et plus petit que p, . Le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa ri à la puissance v ième modulo p, , pour chaque facteur premier p , Ri # r1v mod p, Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n. Puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois. Il y a autant d'engagements R que de collections d'aléas {r,, r2, r3, ...}. # étape 2. réception des défis d destinés au dispositif témoin: Le dispositif démonstrateur comporte des premiers moyens de calcul pour calculer un jeton T, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R. L'objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur le jeton T. L'objet nomade comporte des moyens de réception pour recevoir des collections de défis d {dA, dB, ...}produits par ledit dispositif contrôleur au moyen du jeton T. # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des troisièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. A cet effet, il effectuant des opérations du type : D, =- r.. QA @ dA . QBid]3 mod p, puis, il applique la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au dispositif contrôleur : L'objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur vérifie la cohérence des triplets {R, d, D) et l'authenticité du message m. Cas d'une signature numérique de message Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à prouver à un contrôleur la signature numérique d'un message m. Comme dans le cas général, l' objet nomade fait intervenir trois entités : I. Une première entité, appelée dispositif témoin, est contenue dans ledit objet nomade. Le dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p1, p2, ... (p, ,...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ... Le dispositif témoin comporte aussi une deuxième zone mémoire contenant : * des composantes QA,, à,,... (QA,, ...), et QBI, QB2, ... (QB,, ...), ..., représentant des clés privées QA, QB,... * * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA,, ...) et GB,, GB2, ... (GB,,...) * un exposant public de vérification v. Les paires de clés privées et publiques sont liées par des relations du type : GA.QA mod n =- 1 ou Ga # QA'mod n II. Une deuxième entité est appelée dispositif de signature. Elle peut être également contenue dans ledit objet nomade. III. Une troisième entité appelée dispositif contrôleur se présente sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique. L'objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et ledit dispositif de signature audit dispositif contrôleur. Pour prouver la signature d'un message ledit objet nomade exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r1, r2, r3, ...}, telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r, positif et plus petit que p1. Le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r1 à la puissance v ième modulo p, , pour chaque facteur premier p , R 1 == r 1 v mod P Puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n. Il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}. # étape 2. défi d destiné au dispositif témoin : Le dispositif de signature comporte des troisièmes moyens de calcul pour calculer, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1. Le nombre des collections de défis d étant égal au nombre d'engagements R. Chaque collection {dA, dB, ...} comprend un nombre de défis égal au nombre de paires de clés. Le dispositif de signature transmet les collections de défis d au dispositif témoin. # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. A cet effet, il effectue des opérations du type : D 1 == r . 1 QA 1 dA . QB 1 dB .... mod P puis, il appliquant la méthode des restes chinois. Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. L'objet nomade comporte des moyens de transmission pour transmettre les réponses D au dispositif de signature et/ou au dispositif contrôleur. # étape 4. données destinées au dispositif contrôleur : L'objet nomade comporte des moyens de transmission pour transmettre au dispositif contrôleur un message signé comprenant : - le message m, - les collections de défis d ou les engagements R, - chaque réponse D # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur vérifie la cohérence des triplets {R, d, D} et la signature numérique du message m. Paire de clés conférant une sécurité équivalente à la connaissance de la clé privée Q La paire de clés GA, QA,... n'a plus de raison d'être systématiquement déduite de l'identité du témoin, comme dans le cas du procédé GQ. Dans le cas de la variante ci-après exposée les composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB, , ...),... des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA, , QB,... pour chacun desdits facteurs premiers p,, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA1, QA2, ... (QA,, ...), et QB,, Qu29 ... (QB, ...), par la méthode des restes chinois. Le dispositif témoin comporte des huitièmes moyens de calcul pour calculer lesdites clés publiques GA, GB, ..., # en effectuant des opérations du type : GA = QA@v mod p1 # puis en appliquant la méthode des restes chinois pour établir GA tel que GA =- QAv mod n ou bien tel que GA.QAv mod n = 1 Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les huitièmes moyens de calcul dudit dispositif témoin pour calculer chacun des GA, pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n. De préférence, l'exposant public de vérification v est un nombre premier. Il en résulte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. Paire de clés conférant une sécurité équivalente à la connaissance de la factorisation de n De préférence, l'exposant public de vérification v est du type k v=a où k est un paramètre de sécurité plus grand que 1. De préférence également, l'exposant public de vérification v est du type v = 2k où k est un paramètre de sécurité plus grand que 1. Dans ce cas, la clé publique GA est un carré gA2 inférieur à n choisi de sorte que les deux équations x2 = gA mod n et x2 = - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n. Le dispositif témoin comportant des neuvièmes moyens de calcul pour calculer lesdites composantes QA1, QA2, ... (QA, , ...) de la clé privée QA en appliquant des formules telles que : GA= QA i 2exp(k) mod p, ou bien telles que : GA.QA 1 2.exp(k) mod p.=- 1 et en extrayant la k ième racine carrée de GA dans le corps de Galois CG (p@). Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les neuvièmes moyens de calcul du dispositif témoin pour calculer chacun des QA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. On démontre que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. De préférence, pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p,), on utilise les méthodes suivantes : * dans le cas où le facteur premier p, est congru à 3 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme du type : x = (p+l)/4 ; y = xk mod (p- 1) ; z = y ; QA, GA' mod p, * dans le cas où le facteur premier p, est congru à 1 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme basé sur les suites de Lucas. Terminal ou Serveur distant Concept général GQ2 La présente invention concerne également un dispositif de contrôle, se présentant sous la forme d'un terminal ou d'un serveur distant connecté à un réseau de communication informatique. Le terminal ou le serveur selon l'invention permet de mettre en #uvre le procédé ci-dessus exposé et de diminuer la charge de travail pendant une session destinée à vérifier : - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m. Le dispositif de contrôle met en #uvre : - un module public n tel que n soit le produit de facteurs premiers secrets p,, pz, ... (p,, ...) (i étant supérieur ou égal à 2) n = p.p2. P3- ### ' - des clés publiques GA, GB,... - des exposants publics de vérification vx, vy, ... lesdites clés privées GA et les clés publiques associées QA étant liées par des relations du type : @ GA.QA" mod n 1 ou GA = GAvx mod n Le dispositif de contrôle fait intervenir trois entités. I. Une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin produit des engagements R et des réponses D à des défis d. II. Une deuxième entité est appelée dispositif pilote dudit dispositif témoin. Elle peut être contenue notamment dans ledit objet nomade. III. Une troisième entité, appelée dispositif contrôleur, est contenue dans ledit dispositif de contrôle. Le dispositif de contrôle comporte : - des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif contrôleur audit dispositif témoin et/ou audit dispositif pilote, - des moyens de transmission pour transmettre les données produites par ledit dispositif contrôleur vers ledit dispositif témoin et/ou ledit dispositif pilote, - des moyens de réception pour recevoir les données provenant dudit dispositif témoin et/ou dudit dispositif pilote. Le dispositif contrôleur comporte : - des premiers moyens de calcul pour produire un ou plusieurs défis d telque0 R' = GA d. D"x mod n ou du type : R'1.GA Cas où l'exposant de vérification v est unique De même que précédemment, ledit dispositif de contrôle se présente sous la forme d'un terminal ou d'un serveur distant connecté à un réseau de communication informatique. Il met en #uvre : - un module public n tel que n soit le produit de facteurs premiers secrets p,, p2, ... (p,, ...) (i étant supérieur ou égal à 2) n = pl.pZ. p3.... , - des clés publiques GA, GB,... - un exposant public de vérification v Les clés privées GA et les clés publiques associées QA sont liées par des relations du type : GA.QA" mod n = 1 ou GA QA'mod n ledit dispositif de contrôle fait intervenir trois entités : I. Une première entité, appelée dispositif témoin, est contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur. Le dispositif témoin produit des engagements R et des réponses D à des défis d. II. Une deuxième entité est appelée dispositif pilote dudit dispositif témoin Elle peut être contenue notamment dans ledit objet nomade. III. Une troisième entité, appelée dispositif contrôleur, est contenue dans ledit dispositif de contrôle. Le dispositif de contrôle comporte : - des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif contrôleur audit dispositif témoin et/ou audit dispositif pilote, - des moyens de transmission pour transmettre les données produites par ledit dispositif contrôleur vers ledit dispositif témoin et/ou ledit dispositif pilote, - des moyens de réception pour recevoir les données provenant dudit dispositif témoin et/ou dudit dispositif pilote, Le dispositif contrôleur comporte : - des premiers moyens de calcul pour produire un ou plusieurs défis d {dA, dB, ...}tels que 0 # dA # v -1, - des deuxièmes moyens de calcul pour calculer, en fonction des réponses D reçues du dudit dispositif témoin et/ou dudit dispositif pilote, des engagements R' en effectuant des opérations du type : R'=- GA dA. GB dR .... D" mod n ou du type : R'. GA dA. GBdb. ... # Dv mod n - des troisièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents. Cas d'une authentification d'entité Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation, la session est destinée à vérifier l'authenticité d'une entité. Dans le cas d'une authentification d'entité, le dispositif pilote est appelé dispositif démonstrateur. Pour prouver l'authenticité d'une entité ledit dispositif de contrôle exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin produit au moins un engagement R à partir d'au moins une collection d'aléas {r1, r2, r3, ...}, telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r@ entier positif et plus petit que p, . Il y a autant d'engagements R que de collections d'aléas. # étape 2. défis produits par le dispositif contrôleur et destinés au dispositif témoin : Les moyens de réception du dispositif de contrôle reçoivent tout ou partie de chaque engagement R, transmis par le dispositif démonstrateur, et le transmettent au dispositif contrôleur. Le dispositif contrôleur comporte des premiers moyens de calcul pour calculer, après avoir reçu tout ou partie de chaque engagement R, au moins une collection de défis d {dA, dB, ...} tels que 0 # dA # étape 3. réponse du dispositif témoin aux défis d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...} reçues du dispositif contrôleur. Il y a autant de réponses D que d'engagements R et de défis d. # étape 4. données destinées au dispositif contrôleur : Les moyens de réception du dispositif de contrôle reçoivent du dispositif démonstrateur chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur comporte des deuxièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' --~ GA dA. GB dB .... Dv mod n ou du type : R' . GA d" . GB d$ .... --- D" mod n Le dispositif contrôleur comporte des troisièmes moyens de calcul pour comparer et vérifier que chaque engagement reconstruit R' reproduit tout ou partie de chaque engagement R transmis à l'étape 2 par le dispositif démonstrateur. Cas d'une authentification de message Cas où l'exposant de vérification v est unique. Dans le cas de cette variante de réalisation particulière, la session est destinée à vérifier l'authenticité d'un message m. Dans le cas d'une authentification d'un message m, le dispositif pilote est appelé dispositif démonstrateur. Pour prouver l'authenticité d'un message m, ledit dispositif de contrôle exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : Le dispositif témoin produit au moins un engagement R à partir d'au moins une collection d'aléas {r1, r2, r3, ...}, telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r, entier positif et plus petit que p, . Il y a autant d'engagements R que de collections d'aléas. # étape 2. défis d produits par ledit dispositif contrôleur et destinés au dispositif témoin : Les moyens de réception du dispositif de contrôle reçoivent un jeton T calculé et transmis par le dispositif démonstrateur en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R. Le dispositif contrôleur comporte des premiers moyens de calcul pour calculer, après avoir reçu le jeton T, au moins une collection de défis d {dA, dB, ...} tels que 0 # dA # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collection de défis d {dA, dB, ...} reçues du dispositif contrôleur. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. # étape 4. données destinées au dispositif contrôleur : Les moyens de réception du dispositif de contrôle reçoivent du dispositif démonstrateur chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Le dispositif contrôleur comporte des deuxièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'= GA dia. GB de .... D" mod n ou du type : R'. GA dA. GB dB....= Dv mod n Le dispositif contrôleur comporte des troisièmes moyens de calcul pour calculer un jeton T', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R'. Le dispositif contrôleur comporte des quatrièmes moyens de calcul pour comparer et vérifier que le jeton T' est identique au jeton T transmis à l'étape 2 par le dispositif démonstrateur. Cas d'une signature numérique de message Cas où l'exposant de vérification v est unique Dans le cas de cette variante de réalisation particulière, la session est destinée à vérifier la signature numérique d'un message m. Dans le cas d'une authentification d'un message m, le dispositif pilote est appelé dispositif de signature. Pour prouver la signature numérique du message m, ledit dispositif de contrôle exécute les étapes suivantes : # étape 1. engagement R du témoin : Le dispositif témoin produit au moins un engagement R à partir d'au moins une collection d'aléas {r,, r2, r3, ...}, telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r, entier positif et plus petit que p, . Il y a autant d'engagements R que de collections d'aléas. # étape 2. défis d destinés au dispositif témoin : Le dispositif de signature calcule, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1. Le nombre des collections de défis d est égal au nombre d'engagements R. Chaque collection {dA, dB, ...}comprend un nombre de défis égal au nombre de paires de clés. Le dispositif de signature transmet les collections de défis d au dispositif témoin. # étape 3. réponse du dispositif témoin au défi d : Le dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...}. Il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d. Le dispositif témoin comporte des moyens de transmission pour transmettre les réponses D au dispositif de signature et/ou au dispositif contrôleur. # étape 4. données destinées au dispositif contrôleur : Les moyens de réception du dispositif de contrôle reçoivent du dispositif de signature un message signé comprenant : - le message m, - les collections de défis d ou les engagements R, - chaque réponse D. # étape 5. vérification par le dispositif contrôleur : Cas où le dispositif contrôleur reçoit la collection des défis d Dans ce cas, le dispositif contrôleur reçoit les collections des défis d et des réponses D. Le dispositif contrôleur comporte : * des premiers moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'= GA dA. GB dB....DY mod n ou du type : R'. GA dA. GB dB. ... # Dv mod n * des deuxièmes moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R', * des troisièmes moyens de calcul pour comparer et vérifier que chaque défi d' est identique au défi d figurant dans le message signé. Cas où le dispositif contrôleur reçoit la collection des engagements R Dans ce cas, le dispositif contrôleur reçoit la collection des engagements R et des réponses D, Le dispositif contrôleur comporte : * des premiers moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R, * des deuxièmes moyens de calcul pour calculer, alors, la collection des engagements R' en effectuant des opération du type R'=: GA d'A. GB d'B....Dv mod n ou du type : R'. GA d'A. GB d'B....=: DV rnod n * des troisièmes moyens de calcul pour comparer et vérifier que chaque engagement R' reconstruit est identique à l'engagement R figurant dans le message signé. Paire de clés conférant une sécurité équivalente à la connaissance de la clé privée Q La paire des clés GA, QA,... n'a plus raison d'être systématiquement déduite de l'identité du témoin, comme dans le cas du procédé GQ. Dans le cas de la variante de réalisation ci-après exposée les composantes QA,, QA,, ... (QA , ...), et QBI, QB2, ... (QB, , ...), des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA1, QB,, ... pour chacun desdits facteurs premiers p,, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA,, QA2, ... (QA,, ...), et QB,, Qu,,... (QB" ...), ... par la méthode des restes chinois, Le dispositif témoin comporte des moyens de calcul pour calculer les clés publiques GA, GB, ..., # en effectuant des opérations du type : GA = QA1v mod p, # puis, en appliquant la méthode des restes chinois pour établir GA tel que GA =- QAv mod n ou bien tel que GA.QAv mod n = 1 Le nombre d'opérations arithmétiques modulo p, à effectuer par les huitièmes moyens de calcul dudit dispositif témoin pour calculer chacun des GA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. De préférence, l'exposant public de vérification v est un nombre premier. On peut démontrer que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. Paire de clés conférant une sécurité équivalente à la connaissance de la factorisation de n De préférence, l'exposant public de vérification v est du type k v=a où k est un paramètre de sécurité plus grand que 1. De préférence également, l'exposant public de vérification v est du type v = 2k où k est un paramètre de sécurité plus grand que 1, Dans ce cas clé publique GA est un carré gA2 inférieur à n choisi de sorte que les deux équations x2= gA mod n et x2 = - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n. Le dispositif témoin comporte des neuvièmes moyens de calcul pour calculer les dites composantes QA,, QA2, ... (QA,, ...) de la clé privée QA en appliquant des formules telles que : GA = QA, 2exp(k) mod p@ ou bien telles que : GA.QA2ep(l0modp=l 1 et en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p.) Ainsi, le nombre d'opérations arithmétiques modulo p, à effectuer par les neuvièmes moyens de calcul du dispositif témoin pour calculer chacun des QA, pour chacun des p est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. On peut démontrer que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. De préférence, pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p,), * dans le cas où le facteur premier pi est congru à 3 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme du type : x = (p+l)/4 ; y xk mod (p-1) ; z = y ; QA = GAZ mod p, * dans le cas où le facteur premier p, est congru à 1 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme basé sur les suites de Lucas. On va maintenant décrire de manière détaillée la présente invention en présentant dans une première partie les éléments mathématiques utilisés, puis, en développant dans une deuxième partie le procédé selon l' invention appelé nouveau procédé. Première partie : mathématiques 1. Congruences Dans ce paragraphe, x, y et z sont des entiers naturels.z n' est pas nul. La notation x y (mod z) se lit x est congru à y (mod z) ; elle est équivalente à z divise x-y . 1. 1. Propriétés de base des congruences Les quatre lois suivantes sont utiles. (Loi A) { a = b (mod m); x y (mod m) } 1 a x =- b y (mod m); a.x -- b.y (mod m) } (Loi B) { a.x b. y (mod m); a = b (mod m); pgcd(a, m) = 1 } - = x = y (mod m) (Loi C) bzz (mod m) ≤> { a.n b.n (mod m.n) } (Loi D) { a == b (mod r.s); pgcd(r, s) = 1 } r a = b (mod r); a = b (mod s) } 1. 2. Théorème de Fermat Lorsque p est un nombre premier, ap # a (mod p). Démonstration. La relation est triviale lorsque a est un multiple de p. Définissons la suite {X} pour un nombre entier a quelconque appartenant à {1, 2, 3, ...p-1}. lx 1= lx, = a. Puis, pour i >-1, x,+ = a + x, (mod p)l Calculons le terme pour l' indice i+p : xi+ p = xi + p.a # xi (mod p) Par conséquent, la suite {X} est périodique et sa période est p. Les p-1 premiers termes sont distincts et non nuls ; on y retrouve une fois et une seule fois chacun des entiers de 1 à p-1 ; les p-1 premiers termes forment donc une permutation des entiers de 1 à p-1. Calculons le produit des p-1 premiers termes de la suite {X}. Selon la loi A, a.2a.3a.... ( p -1)a =1.2.3.... ( p -1) (mod p) Selon la loi B, ap-1 =1 (mod p) Selon la loi A, ap # a (mod p) 1. 3. Théorème d'Euler La fonction d'Euler est notée par (p(n). C'est le nombre d'entiers positifs inférieurs à n et premiers avec n. => Lorsque a et n sont premiers entre eux, a#(n) =1 (mod n). => Lorsque n est un nombre premier p, #(p) = p-1. =*Lorsque n est le produit de deux nombres premiers distincts p, et P2. :::::> Lorsque la factorisation de n est p,x. p2' . p31...., (p(n)ln = (1-1/P,) . (l-l/P2) . (l-l/P3) 1. 4. Rang des éléments dans le corps de Galois CG(p) Soit un nombre premier impair p. Soit un nombre entier positif a inférieur à p. Définissons la suite {X}. lx 1 = 1 x, = a. Puis, pour i >-1, x, +1 a.xl (mod p)l Calculons le terme pour l'indice i+p et utilisons le théorème de Fermat. xt+p = aP .x = a.x, = xc+1 (mod p) Par conséquent, la période de la suite {X} est égale à p-1 ou à un diviseur de p-1. Cette période dépend de la valeur de a. Par définition, cette période est appelée le rang de a (mod p) . Xrang(a, p) 1 (mod p) Les éléments de CG(p) ayant pour rang p-1 sont appelés les éléments générateurs de CG(p). La dénomination est due au fait que leurs puissances successives dans CG(p), c'est-à-dire, les termes de la suite {X} pour les indices de 1 à p-1, forment une permutation de tous les éléments non nuls de CG(p). Soit un élément générateur a de CG (p). le rang de l'élément a' (mod p) : ce rang s'exprime simplement en fonction dei et de p-1. => Lorsque i est premier avec p-1, c'est p-l . # Lorsque i divisep-1, c'est (p-1)/i. # Dans tous les cas, c'est (p-l)/pgcd(p-l, i). Par conséquent, dans le corps CG (p), y a Par conséquent, dans le corps de Galois CG(p) où (p-l)/2 est un nombre premier impair noté par p', => il y a un seul élément de rang 1 : c'est 1, =* il y a un seul élément de rang 2 : c'est -1, # il y a p'-1éléments de rang p', # il y a p'-1 éléments de rang 2.p' ; sont les éléments générateurs. 1. 5. Fonction de Carmichael La fonction de Carmichael de n est notée par #(n). C'est la valeur maximale du rang (mod n). =*Lorsque n est le produit de deux nombres premiers impairs p, et pz, ,(n) = PPcm,~1 Pz~1). =} Lorsque a et b sont premiers entre eux, X(a.b) = ppcm(X(a), #(b)). =} Pour les puissances d'un nombre premier impair p, k(pe) pe-1. =} Pour les puissances de 2, ,(2) - 1; ,(4) - 2; ,(2) - 2'~z. =} Dans tous les cas, #(n) divise (p(n). L'égalité n'intervient que lorsque n est premier. 1. 6. Résidus quadratiques Considérons l'équation x2= c (mod n) où l'entier positif c est inférieur à n et premier avec n. # Lorsque l'équation a des solutions en x, on dit que c est un résidu quadratique (mod n). # Lorsque l'équation n'a pas de solution en x, on dit que c est un résidu non quadratique (mod n). L'ensemble des résidus quadratiques (mod n) forme un groupe (mod n) pour la multiplication. En effet, le produit de deux résidus quadratiques (mod n) est un résidu quadratique (mod n). En outre, le produit d'un résidu quadratique (mod n) par un résidu non quadratique (mod n) est un résidu non quadratique (mod n). 1. 7. Structure du corps de Galois CG(p) Pour tout nombre premier impair p, il y a (p-1)/2 résidus quadratiques (mod p) et (p-l)/2 résidus non quadratiques (mod p). De plus, 1\ 2\ ((p-I )/2)Z forment un ensemble complet de résidus quadratiques (mod p). Pour tout nombre premier impair p, chaque résidu quadratique (mod p) a exactement deux racines carrées dans CG (p). effet, pour tout un élément générateur a de CG(p), a' (mod p) est un résidu quadratique si et seulement si i est pair ; ses racines carrées sont alors ~a1/2 (mod p). Les éléments x et p-x ont le même carré dans CG(p). Pour tout nombre premier p congru à 3 (mod 4), pour tout nombre x positif et plus petit que p, l'un des deux nombres x ou p-x est un résidu quadratique (mod p) et l'autre un résidu non quadratique (mod p). Alors, la transformation élever au carré (mod p) permute l'ensemble des résidus quadratiques (mod p). L'ensemble des résidus quadratiques (mod p) est souvent noté par Q . Dans l'ensemble Q , les deux transformations élever au carré (mod p) et prendre la racine carrée (mod p) sont définies et inverses l'une de l'autre. Remarque. Dans CG(p), lorsque (p-1)/2 est un nombre premier impair p', les résidus quadratiques (mod p) sont les p'-1 éléments de rang p' complétés par l'élément de rang 1, c'est-à-dire, 1. Lorsque p est un nombre premier congru à 1 (mod 4), la propriété précédente peut se généraliser comme suit : si p-1 = z.2' oùz est impair et e plus grand que 1, alors la transformation élever au carré (mod p) permute l'ensemble des nombres c de rang impair, c'est-à-dire, dont le rang divise z (c'est z lui-même ou bien un diviseur de z), c'est-à-dire, l'ensemble des nombres c tels qu'il y a des solutions en x à l'équation suivante : x 2e # c (mod p) D'une manière plus générale, dans l'ensemble des éléments de rang impair de CG(p), l' opération élever au carré (mod p) est une permutation. La permutation inverse peut légitimement s'appeler prendre la racine carrée (mod p). 1. 7.1. Fonction exponentielle sur CG(p) Lorsque p est un nombre premier impair et que a est un élément générateur de CG (p), transformation élever a à la puissance x ième (mod p) permute les éléments non nuls de CG (p). permutation inverse est définie par prendre le logarithme discret de y en base a dans CG (p) Lorsque a est un élément générateur de CG(p), x H y = ax (mod p) t-* yf--7 x=loga(y) dans CG( p) 1. 7.2. Fonction puissance sur CG(p) Lorsque p est un nombre premier impair et que v est premier avec p-1, la transformation élever x à la puissance v ième (mod p) respecte le rang des éléments. Elle permute les éléments de CG (p). permutation inverse est définie par une autre transformation élever y à une puissance s ième (mod p) où p-1 divise v.s-1. On dit que l'exposant s est inverse de l'exposant v (mod p-1 ). x f--7 y == XV (mod p) ≤> y f--7 x == yS (mod p) 1. 8. Symboles de Legendre et,de Jacobi Lorsque p est un nombre premier, on peut classer les entiers positifs en deux catégories : les multiples de p et les nombres premiers avec p. En outre, les nombres premiers avec p se classent eux-mêmes en deux catégories : les résidus quadratiques (mod p) et les résidus non quadratiques (mod p). Legendre a introduit un symbole spécial noté par (c p). Le symbole de Legendre de l'entier positif c par rapport au nombre premier p prend les valeurs +1, -1et 0. # (cp) = 0 lorsque c est un multiple de p. # (cp) = +1lorsque c est un résidu quadratique (mod p). # (c p) # -1 lorsque c est un résidu non quadratique (mod p). La formule suivante établie par Euler permet de calculer le symbole de Legendre (en assimilant tout naturellement les valeurs-1 et p-1) ; cette formule est encore appelée le critère d'Euler. (c 1 p) ccp m (mod p) Le symbole de Jacobi généralise le symbole de Legendre. Les deux symboles sont notés de la même manière. Connaissant la factorisation de l'entier impair n, la formule suivante définit le symbole de Jacobi par rapport à n à partir du symbole de Legendre par rapport à chaque facteur premier de n. Si n= pxa. p2p... , alors (c 1 n) = (c 1 p,)a.(c p2)p ... En d'autres termes, si a et b sont des entiers positifs impairs premiers avec c et c', (c 1 a. b) = (c 1 a). (c 1 b) et (c a) . (c' 1 a)= (c'. c 1 a) Attention, résidus quadratiques et éléments avec symbole de Jacobi égal à +1 ne coïncident pas. * Tous les résidus quadratiques (mod n) ont un symbole de Jacobi égal à +1. * La valeur-1 du symbole de Jacobi caractérise exclusivement des résidus non quadratiques (mod n). * Lorsque n n'est pas premier, il y a des résidus non quadratiques dont le symbole de Jacobi vaut +1. Voici la base de la loi de réciprocité quadratique, la reine de la théorie des nombres aux dires de Gauss. Lorsque m et n sont deux nombres premiers impairs distincts, deux cas se présentent : - Ou bien, ils sont tous deux congrus à 3 (mod 4) ; ce cas, une seule des deux équations suivantes, x2 == m (mod n) et x2 = n (mod m), a deux solutions en x. - Ou bien, ils ne sont pas tous deux congrus à 3 (mod 4) ; ce cas, les deux équations ont des solutions ou bien aucune des deux n'a de solution. La loi de réciprocité quadratique lie les symboles de Jacobi (m # n) et (nm) où m et n sont deux entiers positifs impairs : Legendre et Euler connaissaient cette loi ; Gauss l'a démontrée. (m 1 n). (n 1 m) = (- 1 t 1) (n 1)/4 En d'autres termes, le signe change quand m et n sont tous deux congrus à 3 (mod 4). Notons la relation : (-1 n) ~ (-1 )" bzz En d'autres termes, -1 est un résidu quadratique mod n lorsque n est congru à 1 mod 4 ; -1 est un résidu non quadratique mod n lorsque n est congru à 3 mod 4 ; Notons enfin la relation : (2 1 n) = (-1)(112~1)/8 En d'autres termes, 2 sont des résidus non quadratiques (mod n) lorsque n est congru à 3 ou 5 (mod 8) ; 2 sont des résidus quadratiques (mod n) lorsque n est congru à 1 ou 7 (mod8). 1. 9. Suites de Lucas Considérons l'équation du second degré : les coefficients S et P sont respectivement la somme et le produit des racines a et ss, lesquelles racines sont distinctes lorsque le discriminant A n'est pas nul. (x-a).(x - fJ) = x2 - (a + P).x + a.0 = x2 - S.x+ P S P =S2-4.P=(a-/3)2 0 Les suites de Lucas {U} et {V} sont définies comme suit : les paramètres S et P sont deux entiers non nuls tels que S 2 soit différent de 4.P ; chaque terme est entier parce que les valeurs initiales sont entières. U= u p = 0; u =1. Puis, pour i >- 0, u+2 = S.ul+1 - P.u {v}= {va = 2; vI = S. Puis, pour i >- 0, vi+2 = S,vi+l - P.v,} Les deux suites admettent la même équation caractéristique évoquée cidessus : x2- S.x + P = 0. Supposons les expressions suivantes vraies pour les indices i et i+1. Ui et v(=a'+/3' On vérifie alors simplement que les expressions sont encore vraies pour l'indice i+2. Or, elles sont vraies pour les indices 0 et 1. Par récurrence, . elles sont donc vraies pour tout indice i positif ou nul. Par la suite, on utilisera également les relations suivantes. Leur démonstration est triviale. v2 - .u2 = 4.P Pour doubler l' indice, u2.t = u .v, ; v2i=vf-2.Pl Pour retrancher un à l' indice, ut~ ~ (S.u; - v ) I 2.P et v~ ~ (S.vt - .u ) l 2.P Pour ajouter un à l'indice, Ui+i = (S.ui + v; ) l 2 et vi+l = (S.vi + t1,ui)/ l 2 Par ailleurs, les racines a et z3 s'expriment facilement en fonction de S =a+ {3 etde =a-3. à=(S+)/2 et 3=(S-)/2 Les expressions deu u@ et v, en fonction des racines a et 0 s'écrivent encore : (sWÂÏ fs-VÂÏ (s+JÂl (s-JÂÏ ui = ±,/À 11 -j=- 't = ( S + J:i Ji + ( S - J:i Ji 2.J:i 2.J:i 2 2 Développons les polynômes (S + ) zk+1 et (S - )2k+I et combinons leurs développements. 2.k 1 2.k z3 2.k-2.A+ c2.k-1 . 2 k-l -M2.+]--2.+!- ''2.+i- -±--2.+!- - '' k ~ C2.k+1.S 2.(k-i) .Li i=O 22.k.v2.k+1 = S2.k+I 2 k+l S2.k-t,+ ... CZ.k+1 . S3.Ok 2.k+I..Li k = "C2.i S2.(k-i)+1 Ai L., C2.k+l 2.(k-i i=O Les coefficients du binôme sont notés par C qui vaut il (n # '# i)\ i ! (n-i)!@ 1. 9.1. Suites de Lucas sur le corps CG(p) Lorsque p est un nombre premier impair, p divise les coefficients du binôme Cpi pour i allant de 1 à p-1. En d'autres termes, il ne reste alors qu'un seul terme dans chacune des deux précédents développements de polynômes. On obtient donc : 2p-I.u p - 0(p-lOz (mod p), c'est-à-dire, up =(D.I p) (mod p) 2P-l.vp =SP (mod p), c'est-à-dire, v p = S (mod p) Lorsque (0 1 p) = +1, u p = 1 (mod p) et v p = S (mod p) Dans ce cas, en retranchant un à l'indice, on obtient : up~ =(S.up-vp)I2.P---0 (mod p) vp~]=(S.vp-A.up)/2.P = 2 (mod p) Lorsque A est un résidu quadratique par rapport à un nombre premier impair p ne divisant ni P, ni S, ni #, les suites de Lucas pour les indices p-1 et p sur le corps CG(p) sont exactement dans l'état initial, c'est-à-dire, l'état pour les indices 0 et 1. La période des suites de Lucas sur CG(p) divise alors p-1. Lorsque (# #p) = -1, up = -1 (mod p) et v p = S (mod p) Dans ce cas, en ajoutant un à l'indice une première fois, on obtient : u p+ ~ (S.u p + v ) l 2 = 0 (mod p) vp+ ~ (S.vp + .u p ) l 2 = 2.P (mod p) Puis, en ajoutant un à l'indice une deuxième fois, on obtient : u p+2 = (S.u p+1 + v p+1 ) l 2 = P (mod p) v p+2 = (S.Vp+l + A.up+i )/2 = S.P (mod p) Lorsque # est un résidu non quadratique par rapport à un nombre premier impair p ne divisant ni P, ni S, ni #, les suites de Lucas pour les indices p+1 et p+2 sur le corps CG(p) sont dans l'état initial multiplié par P. Lorsque P est égal à 1, la période des suites de Lucas sur CG(p) divise alors p+1. C'est ainsi que Lucas a découvert et établit le théorème suivant : Lorsque p est un nombre premier impair ne divisant ni P, ni S, ni #, p divise up (0 p) et M,-,A ! I P. 2. Quelques méthodes pratiques de calcul 2. 1. Racines carrées dans CG(p) Lorsque C(P-I)12 (mod p) vaut +1, l'équation x2 = c (mod p) a deux solutions dans le corps de Galois CG(p) ; ces deux solutions sont appelées racines carrées de c (mod p) . 2. 1.1. Cas où p est congru à 3 (mod 4) Selon le critère d'Euler, on a : c(H)/2-sl (mod p), ce qui donne, bzz z - c (mod p). Lorsque le nombre premierp est congru à 3 (mod 4), le nombre (p+l)/4 est un entier ; par conséquent, les deux racines carrées de c dans CG (p) alors :!:cCp+l)/4 (modp). 2. 1.2. Cas où p est congru à 1 (mod 4) Lorsque p est congru à 1 (mod 4), on utilise les suites de Lucas pour calculer une racine carrée de c (mod p). On affecte la valeur c au paramètre P. Puis, on cherche une valeur du paramètre S telle que le discriminant # = S2- 4. c soit un résidu non quadratique (mod p). On procède par essais successifs. En pratique, on part de S = 1, puis, on fait croître la valeur de S. Lorsque A est un résidu non quadratique par rapport à un nombre premier p impair ne divisant ni c, ni S, ni #, les suites de Lucas pour les indices p+1 et p+2 sur le corps CG (p) dans l' état initial multiplié par c. Or, on connaît les relations suivantes : v,2 - A.u,2 = 4.P' et m2. On obtient donc, p+D/2 - 4.c('+) z (mod p) Or, - c(p+l)l2==c (mod p) Par conséquent, le nombre: x == - v (p+l) /2 2 (mod p) est alors une solution à l'équation : x --- c (mod p). Les relations suivantes sont utilisées pour calculer les suites {U} et {V} ensemble. Pour doubler l' indice, u2, = ul .v ; v2.i = Vi 2 2.ci Pour ajouter 1 à l'indice, u+1 = (S.u + v )I2; vi+l = (.1.u + S.vt )/2 La procédure suivante utilise trois variables : x pour u@, y pour v et z pour c. L'indice cible est (p+l)/2 ; il est codé par une séquence de j bits. Cette séquence est examinée du bit de poids fort au bit de poids faible. 1. Donner à x la valeur 0 ; à y la valeur 2 ; donnerà z la valeur 1. 2. Répétera fois la séquence suivante. Remplacer x par x.y (mod p). Remplacer y par y2- 2. z (mod p) Remplacer z par z2(mod p). Si le j ième bit codant l'indice cible vaut 1, exécuter la séquence suivante. Remplacer t par x. Remplacer x par (S.t+ y)/2 (mod p). Remplacer y par (S.t+ #.y)/2 (mod p) Remplacer z par z.c (mod p). 3. Remplacer y par y/2 (mod p). Le résultat cherché est y. 2. 2. Algorithme d'Euclide L'algorithme d'Euclide opère la division des entiers. Soient deux entiers positifs x et y tels que x soit plus grand que y. Divisons x par y pour obtenir un quotient q positif et plus petit que ou égal à x et un reste r positif ou nul et plus petit que y. Soit, 0 Par conséquent, x = q. y + r avec 0 Par définition, les coefficients de Bezout de deux entiers positifs x et y sont deux entiers k et l définis de manière unique par : 0 A partir des valeurs initiales Co = x et C1 = y, considérons les divisions successives : Co = q .C + C2 ; Cl = 92 C2 + C3 ; ... jusqu' à : CL-1 = qL.CL + CL+l où CL+1 = 0. Les restes successifs forment la suite {C} qui est ainsi définie pour les indices i allant de 0 à CL+1. Les quotients successifs forment la suite {q}qui est ainsi définie pour les indices i allant de 1 à L. La suite {C} peut encore se définir de la manière suivante. C= Cp = x; Cl = y; puis, pour i allant de 1 à L, Ci+, = C,~ - ql .C, => La suite {C} est strictement décroissante de Co jusqu'à CL+I qui est nul. Définissons maintenant deux autres suites appelées {A} et { B } . IAI= 1 Ao = 1; A1 = 0; puis, pour i allant de 1 à L, A(+1 A~ + {B}= {Bo = 0; BI = 1; puis, pour i allant de 1 à L, B+l = B~] + La suite {A} est strictement croissante de A3 à Al+l' Les premiers termes suivants de la suite {B} sont Bo=O,B=l,Bz=q,B3=1+q.q2,... La suite {B} est strictement croissante de B2 à BL+1. En éliminant q, entre les définitions des suites {A}et {C}, nous obtenons : A.C+1 + A+lCi = Ai-lCc + A.C~ Par conséquent, la valeur de A,.Ci+l + Ai+,.Ci est constante pour i allant de OàL. Puisque Ao.C + A1.C = y, nous obtenons : .4] .C y, Et, de la même manière, BL+1 1 .C L = x. Par ailleurs, remarquons les égalités : jc.o # y.Bo = x (-1)0 ,Co x.A - y.B ~ -y = (-1) .C Supposons la relation vraie pour les indices i-1 et i ; puis, vérifions qu'elle est encore vraie pour l'indice i+1. x.A,+ - yBl+ =x.(A-1 +qi.Al)-y.(Bl~] + q Bi ) ~ (x.At~ - y.Bl~ ) + 9 (x.At - y.B ) ~ (-1)- .(C~ - 9 Cr ) ~ (-I)+t .Ci+ Par récurrence, pour i allant de 1 à L, x.A; - y.Bt (-1)' ,Ci En particulier, on obtient finalement : x.AL - y.BL = (-1)L.CL Les coefficients de Bezout de x et y sont égaux à AL et BL. Le plus grand commun diviseur de x et y est égal à CL. Exemple. Calculer les coefficients de Bezout de 10 103 et 63 659. k A B C q 0 1 0 63 659 = x - 1 0 1 10 103 = y 6 2 1 6 3 041 3 3 3 19 980 3 4 10 63 101 9 5 93 586 71 1 6 103 649 30 2 7 299 1 884 11 2 8 701 4 417 8 1 9 1 000 6 301 3 2 10 2 701 17 019 2 1 11 =L 3 701 = AL 23 320 = BL 1 = CL 2 12 10 103 = y 63 359 = x 0 Les calculs sont plus simples que les explications. 23 320 . 10 103 = 235 601 960 3 701 . 63 659 = 235 601 959 23 320 . 10 103 - 3 701 . 63 659 = 1 2. 2.2. Inversion (mod n) L'algorithme d'Euclide calcule aussi l'inverse (mod x). Lorsque y est positif, que x est plus grand que y et que x et y sont premiers entre eux, c'est-à-dire, CL= pgcd(x, y) = 1, les notations y-' (mod x) et 1/y (mod x) ont un sens. Bien entendu, la suite {A}est alors inutile. Lorsque L est impair, l'inverse de y (mod x) est égal à BL. Lorsque L est pair, l' inverse de y (mod x) est égal à x - BL. Dans l'exemple ci-dessus, 23 320 est l'inverse de 10 103 (mod 63 659). 2. 2.3. Méthode des restes chinois Lorsque x et y sont deux entiers positifs premiers entre eux, les calculs suivants transforment une représentation à une composante (mod x.y) en une représentation à deux composantes (mod x) et (mod y). as z (mod x) et ay y == a X) (mod y) Voyons maintenant comment réaliser l'opération inverse, c'est-à-dire, comment calculer la représentation à une composante (mod x.y) connaissant la représentation à deux composantes (mod x) et (mod y). La technique décrite ci-dessous est connue comme la méthode des restes chinois. Supposons x plus grand que y. Tout d'abord, réduisons x (mod y), puis, inversons le résultat (mod y). Ce calcul est généralement fait à l'avance et le nombre # est stocké dans le dispositif de calcul. Le nombre # est un paramètre des restes chinois. Vil = {x (mod y) }-' (mod y) Ensuite, réduisons la composante ax (mod y). a'z = ax (mod y) Le résultat cherché s'obtient alors par l'une des deux formules suivantes. Lorsque ay est supérieur ou égal à a'x, axy = IÂ. (a - a's) (mod y) } . x + a;r Lorsque a est inférieur à a'x, az, {/L (ay + y - a'x) (mod y) } . x + ax 2. 3. Calcul du symbole de Jacobi Le calcul du symbole de Jacobi d'un entier positif k par rapport à un entier positif impair n plus grand que k se déroule selon la procédure suivante qui utilise cinq variables appelée x, y, z, e et J. Cette procédure n'utilise pas la décomposition de n en facteurs premiers. # La variable x est positive et impaire, strictement décroissante à partir de la valeur initiale n. # La variable y est positive et inférieure à x, strictement décroissante à partir de la valeur initiale k. # La variable z est positive, impaire et inférieure à y. # La variable e est l'exposant du facteur 2 extrait de y. Seule sa parité doit être évaluée. # La variable J vaut +1 ou -1 en partant de la valeur initiale +1. Calcul pratique de (k # n) avec k positif et n impair et plus grand que k 1. Donner à x la valeur n ; donner à y la valeur k ; donner à J la valeur +1. 2. Décomposer y en z.2e oùz est impair et positif et e positif ou nul. (y 1 x) = (z. 2' 1 x) = (z # x). (2 # x)e => Si e est impair et si x = 3 ou 5 (mod 8), changer le signe de J. 3. Appliquer la loi de réciprocité quadratique sur z et x qui sont tous deux impairs. (z 1 x)=(x 1 z).(-I)(;r\)(")14 Si x et z = 3 (mod 4), changer le signe de J. 4. Réduire x qui est toujours plus grand que z. Remplacer y par x (mod z). Remplacer x par z. 5. Si x est plus grand que 1, revenir à l'étape 2. Si x est égal à 1, alors le symbole de Jacobi vaut J et les deux nombres k et n sont premiers entre eux. Si x est nul, alors le symbole de Jacobi est nul et le pgcd de k et n est égal à z. Exemple. Calculer (10 103 63 659), c'est-à-dire, (2777 1 F8AB) en notation hexadécimale. On retrouve les divisions successives de l'algorithme d'Euclide et le calcul du pgcd. Le décalage de ligne matérialise l'extraction du facteur 2. Le symbole * matérialise le changement de signe de J. q C C (mod 8) J change 63 659 = x 3 6 10 103 = y 7 * 3 3 041 1 980 4 12 245 5 2 101 5 2 43 3 2 15 7 * 1 13 5 22 13 1 1 Par conséquent, (10 10363 659) =-1. 2. 4. Carré et racine carrée dans Qn Dans ce paragraphe, le module n est le produit de deux facteurs premiers p1 et p2 congrus à 3 (mod 4). Dans ce cas, (p,+l)/4 et (p,+1)14 sont des nombres entiers. Définissons la notation (mod* n) . Cette opération consiste à calculer normalement le résultat x (mod n), puis, à garder x ou n-x, le plus petit des deux, comme résultat final. Lorsque le module n est le produit de deux facteurs premiers /?, et p2 congrus à 3 (mod 4), définissons la notation Qn . C'est l'ensemble des éléments de l'anneau des entiers (mod n) qui sont plus petits que n/2 et dont le symbole de Jacobi par rapport à n vaut +1. L'ensemble Qn a une structure d'anneau. Considérons une première transformation définie par élever un élément x de Qn au carré (mod* n) . Le résultat y appartient également à Qn. y=x2 (mod*n) Considérons une deuxième transformation définie par élever y à la puissance (p,+1)/4 (mod p,) , puis, élever y à la puissance (p2+1)/4 (mod p2) , avant d'utiliser la méthode des restes chinois pour établir le résultat z (mod* n). Lorsque p, est plus petit que p2, les calculs sont très précisément les suivants. y, = y (mod p1 ) z, == yiPl +1)/4 (mod) y2 = y (mod p2) Z2 --- y2+)ia (mod P2) z' = Z2 (mod pl ); Si Z] z', z"= zl - z'; Sinon, z"= z] + Pl - Z' A={/?2 (modp,)}"1 (mod/7]); ZI,2 = ,.Z" (mod p1 )I p2 + Z2; Z = Z,2 (mod * n) Ces deux transformations sont inverses l' une de l'autre. Leur produit est l'identité parce que le résultatz rétablit le nombre x de départ. Ce sont deux permutations, inverses l'une de l'autre, des éléments de Qn. La première permutation calcule le carré y dans Qn de l'élément x de Q . La deuxième transformation calcule donc la racine carrée x dans Q de l'élément y de Qn . Par la suite, on aura besoin de la k ième racine carrée de y dans Qn, c'est-à-dire, de la solution x dans Qn à l'équation : y # x2k (mod * n) Plutôt que d'extraire k racines carrées de rang dans Qn, il vaut mieux procéder globalement de la manière suivante. Cette remarque fut faite en son temps par Oded Goldreich. Yt = Y (mod pl ); z=(i+l)/4; t - zk k (mod Pl -1); x = Yi t (mod Pl) Y2 = Y (mod p2); z = (P2 +1)/4; t - Zk (mod p2 -1); x2 = Yt2 (mod P2) X' = x2 (mod/?j); Si ]>', "=-'; Sinon, x"=xl +pl -x' =2 (modp!)}"1 (modpl); x\2={X.x" (mod Pl)}P2 + X2; x = x,2 (mod * n) 2. 5. Nombres de Williams et racine carrée de 4 dans Qn Hugh C. Williams a découvert l'intérêt cryptographique des modules n, produits de deux facteurs premiers p1 et p2 tels que p1 soit congru à 3 (mod 8) et P2 à 7 (mod 8). Lorsque le module n est le produit de deux facteurs premiers p, et p2 tels que/7, soit congru à 3 (mod 8) et P2 à 7 (mod 8), on obtient (2 1 p.) = -1 et (2 # p2) = +1, c'est-à-dire que 2 est un résidu non quadratique (mod p,) et un résidu quadratique (mod p2) ; donc, ni 2 (mod n), ni-2 (mod n) n'appartiennent à Qn. Par la suite, a dénotera la racine carrée de 4 dans Qn. Cette racine est représentée par les composantes : al = -2 (mod ,) et a2= 2 (mod P2) ou bien par a, = 2 (mod p, ) et a2= -2 (mod P2) ; c'est l'élément dont la représentation (mod n) est plus petite que n/2. Il y a alors équivalence entre la connaissance du nombre a et la connaissance de la factorisation du module n. Démonstration. D'une part, étant donné a, le module n divise [alpha]2-4 ; mais le symbole de Jacobi de a par rapport à n vaut +1 alors que celui de 2 vaut-1 ; le module n ne divise donc ni a-2, ni a+2. Par conséquent, le facteur premier p2 est le plus grand commun diviseur de n et a-2 ; le facteur premier p1 est le plus grand commun diviseur de n et a+2. D'autre part, étant donnés les facteurs premiers p, et pz, la racine carrée de 4 dans Qn est représentée par les composantes : ai= -2 (mod /?,) et a2 = 2 (mod pz), ou bien, at 2 (mod ,) et a2 -2 (modp2). Selon les restes chinois, on reconstruit a. Shafi Goldwasser, Silvio Micali et Ronald Rivest ont introduit la paire de fonctions {F0; F1}sur Qn. F,)(x) =- x' (mod* n) et F,(x) 4.xz (mod* n) Cette paire de fonctions permute les éléments de Q . Une collision est définie par deux éléments x et y de Qn tels que F0(jc) = F, (y). Connaître une collision équivaut à connaître les facteurs premiers du module n. La démonstration est semblable à la démonstration ci-dessus. Par conséquent, cette paire de permutations résiste aux collisions pour qui ne connaît pas les facteurs premiers p1 et p2 du module n. Nous disposons donc de tous les ingrédients nécessaires à une démonstration de la connaissance de la factorisation d'un module public n sans en transférer la connaissance. 3. Charges de travail La charge de travail pour élever x à la puissance v ième (mod n) dépend de la valeur et de la forme binaire de l'exposant v, de la taille de l'argument x et de la taille du module n. Dans le cadre de ce mémoire, l'exposant v est plus petit que le plus petit facteur premier du module n. L'utilisation des facteurs premiers p,, p2, ... d'un module n diminue la charge de travail pour calculer (mod n). Plutôt que l'opération directe élever x à la puissance v ième (mod n) , on peut avantageusement élever x à la puissance v ième dans chacun des corps CG(p,), CG(p2), ... c'est-à- dire, (mod p,), (modp2), ... puis, établir le résultat dans l'anneau Z n, c'est-à- dire, (mod n = p, fois p2 fois ...). Cette manière de procéder est appelée la méthode des restes chinois. 3. 1. Multiplication et carré (mod n) En pratique, avec des programmes optimisés, le rapport entre la charge de travail pour un carré modulo et la charge de travail pour une multiplication modulo est environ 0,75. Par exemple, sur le composant ST 16601 pour carte à puce, avec une horloge normalisée à 3,579545 MHz, le carré modulo pour 512 bits se fait en 150 ms et la multiplication modulo en 200 ms. Pour effectuer une opération multiplication modulo , on peut multiplier, puis, réduire : l'opération de multiplication demande à peu près autant d'effort que l'opération de réduction modulo. La multiplication de deux nombres de 512 bits peut se ramener à des multiplications de nombres de 256 bits. Chaque nombre de 512 bits s'écrit alors a+b.2256 où a et b sont des nombres de 256 bits. La multiplication de a+b.2256 par c+d.2256 amène à calculer les quatre produits a.c, a.d, b.c et b.d. En doublant la longueur, on multiplie par quatre la charge de travail pour multiplier. Le carré de a+b.2256 amène à calculer les deux carrés a2, b 2 et le produit a.b. En doublant la longueur, on multiplie par trois la charge de travail pour élever au carré. De même, la multiplication de deux nombres de 512 bits peut se ramener à des multiplications de nombres de 171 bits. Chaque nombre de 512 bits s'écrit alors a+2"'.b+2'Z.c où a, b et c sont des nombres de 171 bits. La multiplication de a+27'.b+2'4'.c par d+2"'.e+2"Z.f amène à calculer neuf. En doublant la longueur, on multiplie par neuf la charge de travail pour multiplier. Le carré de a+2"'.b+2"z.c amène à calculer trois carrés et trois produits. En doublant la longueur, on multiplie par six la charge de travail pour élever au carré. 3. 2. Elever x à la puissance v ième (mod n) Prenons en exemple la valeur v = 3, puis, la valeur v = 65537. Pour v = 3, c'est-à-dire, 2+1, il faut élever l'argument au carré (mod n), puis, multiplier le résultat par l'argument (mod n). Pour v = 65 537, c'est-à-dire, 216+1, il faut élever l'argument au carré (mod n) seize fois de rang, puis, multiplier le résultat par l'argument (mod n). Dans le cadre de ce mémoire, l'exposant v est plus petit que le plus petit facteur premier du module n. Il n'y a donc pas donc de réduction de l'exposant v en fonction des différents facteurs premiers du module n. Par rapport au calcul direct de élever x à la puissance v ième (mod n) où l'argument x et le module n ont la même taille, la méthode des restes chinois divise la charge de travail - par deux lorsque le module n a deux facteurs premiers p, et p2 de même taille, - par trois lorsque le module n a trois facteurs premiers p,, p2 et p3 de même taille, et ainsi de suite. On peut généraliser la méthode précédente ; ainsi, la procédure suivante calcule x' (mod n) pour un exposant v = 2' + v ~I .2-I + ... v .2 + vp où chaque bit de v@-@ à v0 vaut 0 ou 1.., 1. Donner à y la valeur x. 2. Répéter la séquence suivante pour k allant de i-1à 0. Remplacer y par y2(mod n). Si le bit vk vaut 1, remplacer y par x.y (mod n). 3. Le résultat cherché est y. Selon la procédure précédente, le calcul peut se faire par log2(v) carrés (mod n) entrelacés avec h (v) (mod n). La notation h(v) représente un de moins que le poids de Hamming de v, c'est-à-dire, que l'écriture de v en binaire comporte h(v)+l bits à 1. Pour un module n de 512 bits, cela signifie log2(v) carrés (mod n sur 512 bits) et h(v) multiplications (mod n sur 512 bits). Pour un module n de 256 bits, cela signifie log2(v) carrés (mod n sur 256 bits) et h(v) multiplications (mod n sur 256 bits). Pour un module n de 171 bits, cela signifie log2(v) carrés (mod n sur 171 bits) et h(v) multiplications (mod n sur 171 bits). Deuxième partie : procédé 1. Exposé du nouveau procédé Le procédé est destiné à prouver l' origine et l' intégrité d'un message numérique m, lequel message peut être vide. Ce procédé permet l'authentification d'entité, l'authentification de message ou la signature de message. 1. 1. Paramètres Le procédé met en #uvre un premier ensemble de nombres entiers, à savoir au moins deux facteurs premiers notés part, p2 P3 ... Certains facteurs premiers peuvent apparaître plusieurs fois. Le produit des facteurs premiers forme un module public n = p1. p2 (. p3 ...). un jeu de paramètres des restes chinois notés.A. A, Ac .... Il y a un paramètre de moins que de facteurs premiers. Attention, il y a plusieurs jeux de paramètres équivalents. Supposons que les grands nombres premiers sont rangés dans l'ordre croissant, s'il y a trois nombres premiers, p, est plus petit que PI fois p2, s'il y a quatre nombres premiers, p, est plus petit que PI fois pz fois p3, et ainsi de suite. Dans ce cas, voici un exemple de jeu de paramètres des restes chinois. Àa = (P2 (mod P\ )-1 (mod P\ ) 6 = ((Pt P2 (mod P3 -' (mod P3 ) c = ((Pt P2 P3 (mod P4 -1 (mod P4 ) Et ainsi de suite. Le procédé met en #uvre un deuxième ensemble de nombres entiers, à savoir, au moins un exposant public de vérification noté par v, et, pour chaque exposant v, au moins une paire de clés selon la présente invention comprenant une clé privée notée par Q et une clé publique notée par G. Une des deux relations suivantes lie chaque paire de clés selon la présente invention par les nombres v et n. G.QV = 1 (mod n) ou bien G --- QV (mod n) En l'absence de toute ambiguïté, en particulier, s'il y a un seul exposant public de vérification v, on utilise la notation (G, Q), puis, si besoin est, (GA, QA), (GB, QB), (GC, QC), ... Avec plusieurs exposants publics de vérification vx vy vz ..., on utilise en outre la notation (Gx, Qx), (Gy, Qy), ..., puis, si besoins est, (GxA, QxA), (GxB, QxB), ... (GyA, QyA), (GyB, QyB), ... En pratique, chaque clé privée Q n'est jamais utilisée telle quelle. On utilise uniquement un jeu de composantes Q1 Q2 Q3 ..., une composante par facteur premier. * Par la méthode des restes chinois, on pourrait rétablir chaque clé privée Q à partir du jeu de composantes Q1 Q2 Q3 ...,. En pratique, il n'y a jamais lieu de rétablir les clés privées Q. Qa = Q2 (mod p1); ; Si 6)>6 6=6)- Q1,2 - a Qa (mod Pl)}P2 ' Q2 Qb C),2 (mod P3); Si Q3 Q, Qb = Q3 - Qb Sinon, =63+3-6 Qt,2,3 =bQb (mod p3)pt.P2+Q1,2 Et ainsi de suite. Q est égal à Q1,2,3,... 1. 1.1. Paire de clés selon la présente invention conférant une sécurité équivalente à la connaissance de la clé privée Q Les composantes Q1 Q2 Q3 ... sont des nombres pris au hasard tels que 0 Note. L'ensemble de ces composantes représente une clé privée Q. La clé privée Q n'est jamais utilisée telle quelle. Qa # Q2 (mod/?,); ; Si 6)>6 -6)- Sinon, Qa = Qt + P1 -Qa Q1,2 =aQa (mod P)]P2 +Q2; Qb = Q1,2 (mod p3 ) Si Q3 Qb, Qb = Q3 - Qb; Sinon, Qb = Q3 + P3 - Qb; Q1,2,3 - b Qb (mod P3 )P1 P2 + Q1,2 Et ainsi de suite. Q est égal à QI,2,3, .0. La clé publique G est la puissance v ième de Q (mod n) ou bien son inverse (mod n). G = Q (mod n) ou bien G { Q" (mod n) 1 -' (mod n) Note. En pratique, pour calculer le nombre G, on élève chaque nombre Q, à la puissance v ième (mod p@), ... , puis, on utilise la méthode des restes chinois pour établir le résultat (mod n) ou son inverse (mod n). Gl == Qr (mod p ); G2 = Q2 (modp2); Ga = G2 (mode); Si Gt aga, Ga =G-Ga; Sinon, Ga =Gl + Pl-Ga; Gt,2 --~ .a .Ga (mod pt )P2 + G2 G, = Gl>2 (mod P3); G3 = Q3 (mod p3 ) Il il Si G3>Gb, Gg = G3 -Gb; Sinon, Gb = G3 + p3 -Gb; G1,2,3 = 6.G6 (mod P3)}Pl-P2+G\t2\ Et ainsi de suite. G est égal à G1,2,3,... ou bien, à son inverse (mod n). Lorsque le nombre entier v est premier, on assure la propriété de sécurité annoncée. 1. 1.2. Paire de clés selon la présente invention conférant une sécurité équivalente à la connaissance de la factorisation de n L'exposant public de vérification v est égal à wk Le nombre entier k est un paramètre de sécurité plus grand que 1. La valeur k = 1 est interdite. Chaque nombre g est un entier inférieur au plus petit facteur premier. En outre, pour au moins un facteur premier p, l'équation xz --~ g (mod p) n'a pas de solution en x dans CG (p) pour au moins un facteur q l'équation x 2 = -g (mod q) n'a pas de solution en x dans CG(q). Cette construction assure que les deux équations x 2= g (mod n) et x2= -g (mod n) n'ont pas de solution en x dans l'anneau des entiers modulo n, c'est-à-dire que les nombres g et-g sont deux résidus non quadratiques (mod n). Note. En pratique, on utilise pour g les nombres 2,3, 5,6, ... en éliminant bien sûr les carrés tels que 4,9, ... Note. Il n'est pas recommandé d'utiliser 6 comme nombre de base en même temps que 2 et 3 parce qu'ils se combinent par multiplication. On dit qu'ils ne sont pas indépendants. Il vaut mieux utiliser 2 et 3 comme nombres de base et retrouver 6 comme le produit de 2 et 3. Pour chaque nombre g, la clé publique G est égale à g2. Pour chaque nombre g, chaque composante Q1 Q2 Q3 ... est la k ième racine carrée de G dans CG (p) est un résidu quadratique dans CG(p). Il y a une composante par facteur premier. Exemple de calcul de la k ième racine carrée quadratique de G dans CG(p) On pourra utilement consulter l'appendice 3, Quadratic Residues , pp. 278-288, dans l' ouvrage Prime Numbers and Computer Methods for Factorization , Hans Riesel, Birkhauser, Boston, Basel, Stuttgart, 1985. Pour chaque facteur premier p congru à 3 (mod 4), on élève k fois de rang G à la puissance (p+1)/4 pour obtenir la k ième racine carrée quadratique de G dans le corps CG (p) ; on inverse ou non le résultat (mod p) pour obtenir la composante Q, pour le facteur premier/?. Note. Plutôt que d'extraire k racines carrées successivement, on peut procéder de manière globale. x=(p+1)14; y=xk (modp-I); z=p-I-y; Qp =G (mod p); par conséquent, p divise G.Qp2K-1. ou bien, x=(p+1)I4; y=xk (mod p-1); z= y; Qp =- G (mod p); par conséquent, p divise Qp2@-G. Pour chaque facteur premier p congru à 1 (mod 4), on utilise les suites de Lucas pour extraire les racines carrées successives, jusqu'à obtenir la k ième racine carrée de G dans le corps CG(p), avant d'inverser ou non le résultat (mod p) pour obtenir la composante Q, pour le facteur premier p@. Par conséquent, p divise G.Q -1 ou bien, Qp # G. Les clés G et Q sont deux résidus quadratiques (mod n). La paire de clés selon la présente invention vérifie l'une des deux relations suivantes. G.Q2k =1 (mod n) ou bien, Q2 k == G (mod n) Par conséquent, dans l'anneau des entiers modulo n, le k-1 ième carré de chaque clé privée Q ou son inverse (mod n) est une racine carrée non triviale de la clé publique G = g2. Appelons q cette racine carrée de G (mod n) qui n'est ni g ni -g. Par conséquent, n qui divise q2-g2 ne divise ni q-g ni q+g. Ainsi, le module n se scinde en deux facteurs non triviaux : le pgcd de n et de q-g et le pgcd de n et de q+g. Par conséquent, pour n'importe quelle clé privée Q, la connaissance de n'importe laquelle des k valeurs {Q, Q2, Q4, ... jusqu'au k-1 ième carré de Q (mod n)} révèle une factorisation non triviale du module n. Contraintes induites par les nombres de base sur les facteurs premiers On peut utilement consulter le chapitre 3, Quadratic Residues , pp. 35- 46, dans l'ouvrage Introduction to Number Theory , Hua Loo Keng, Springer Verlag, Berlin, Heidelberg, 1982. # (2 p) = +1lorsque p est congru à 1 (mod 8). (2 p) = -1 lorsque p est congru à 3 (mod 8). Pour utiliser g = 2, c'est-à-dire, la clé publique G = 4, il suffit qu'un facteur premier soit congru à 3 (mod 8). Alors, le nombre 2 est un résidu non quadratique modulo n. #(3 1 p) = +1 lorsque p est congru à 1 (mod 12). (3 p) = -1 lorsque p est congru à 5 (mod 12). Pour utiliser g = 3, c'est-à-dire, la clé publique G = 9, il suffit qu'un facteur premier soit congru à 5 (mod 12). Alors, le nombre 3 est un résidu non quadratique modulo n. # Le nombre g 4 est un carré ; il n'est donc pas utilisé. # (5 p) = +1 lorsque p est congru à 1 (mod 5). (5p) = -1 lorsque p est congru à 2 (mod 5). Pour utiliser g = 5, c'est-à-dire, la clé publique G = 25, il suffit qu'un facteur premier soit congru à 2 (mod 5). Alors, le nombre 5 est un résidu non quadratique modulo n. # (6p) = +1 lorsque p est congru à 1 ou 5 (mod 24). (6 1 p) = -1 lorsque p est congru à 7 ou +1 (mod 24). Pour utiliser g = 6, c'est-à-dire, la clé publique G 36, il suffit qu'un facteur premier soit congru à 7 ou ~11 (mod 24). Alors, le nombre 6 est un résidu non quadratique modulo n. # (7p) = +1 lorsque p est congru à 1, 3 ou 9 (mod 28). (7 | p) = -1 lorsque p est congru à 5, 11 ou 13 (mod 28). Pour utiliser g = 7, c'est-à-dire, la clé publique G = 49, il suffit qu'un facteur premier soit congru à 2 (mod 5). Alors, le nombre 7 est un résidu non quadratique modulo n. Note. Tous les témoins peuvent utiliser le même jeu de clés publiques GA, GB, GC, GD, ... , par exemple, 4,9, 25 et 49, moyennant des contraintes élémentaires sur la sélection des facteurs premiers. Ces contraintes sont pratiquement gratuites lorsqu'elles sont intégrées aux procédures de production des facteurs premiers. 1. 1.3. Généralisation de la structure précédente Le nombre a est un nombre impair. Il doit diviser au moins un facteur premier moins un. Note. En pratique, on donne au nombre a les valeurs des nombres premiers à partir de 3, soit : 3,5, 7, 11, ... L'exposant public de vérification v est égal à ak. Le nombre entier k est un paramètre de sécurité plus grand que 1. La valeur k = 1 est interdite. Chaque nombre g est un entier inférieur au plus petit facteur premier. En outre, pour au moins un facteur premier p tel que a divise p-1, l'équation xa = g (mod p) n'a pas de racine en x dans CG(p). Note. Cette construction généralise les résidus non quadratiques (mod n). Par exemple, dans le cas a = 3, on dit que le nombre g est un résidu non cubique (mod n). Dans le cas général, on parle de résidu non a dique (mod n). Note. En pratique, on donne au nombre g les valeurs 2,3, 4,5, ... en éliminant les puissances a ièmes. Pour chaque nombre g, la clé publique G est égale à 8a. Pour chaque nombre g, chaque composante Q1 Q2 Q3 ... est la k ième racine a ième de G dans CG(p) qui est un résidu a dique dans CG(p). II y a une composante par facteur premier. Exemple de calcul de la k ième racine troisième de G dans CG(p) qui est un résidu cubique dans CG(p). Pour chaque facteur premier p congru à 2 (mod 3), on élève k fois de rang G à la puissance (p-2)/3 pour obtenir la k ième racine a ième de G dans le corps CG (p) ; on inverse ou non le résultat (mod p) pour obtenir la composante Q, pour le facteur premier p1. Note. On peut procéder de manière globale pour accéder directement au résultat cherché. x = ( p - 2) l 3; y = xk (mod p -1 ); z = y; Q p = G (mod p); par conséquent, pdivise Qp 3* -G. x=(p-2)/3; y=xk (modp-l); z=p-1-y; Qp =Gz (mod p); par conséquent, p divise G.Qp3k - 1. Pour chaque facteur premier p congru à 1 (mod 3), p divise G.Q -1 ou bien Qp - G. 1. 2. Entités Le procédé met en #uvre les trois entités suivantes. Une première entité témoigne ; c'est le témoin. Il dispose d'un exposant public de vérification v = 2k. En fonction des compromis retenus entre charge de travail et volume de données à stocker, le témoin stocke encore d'autres nombres : - ou bien les j facteurs premiers p, P2 P3 ... et les 1 clés publiques GA GB ... ; à chaque appel, le témoin doit alors reconstituer les l clés privées QA QB ... selon le paramètre k à partir des 1 clés publiques GA GB ... et des j facteurs premiers p, p2 P3 ... ; - ou bien, le module n et les1 clés privées QA QB... ; le témoin ne fait alors appel ni aux facteurs premiers ni aux restes chinois ; - ou bien un ensemble de j.(l+2)-1 nombres privés de tailles voisines pour utiliser les facteurs premiers et les restes chinois : - j facteurs premiers p1 p2 p3 - j-1 paramètres des restes chinois A a A, - j.1 composantes de clés privées : QA, QA2 ... QB( QB2 ... Une deuxième entité pilote le témoin ; c'est le pilote. Il dispose d'un certificat Cert(Id, n) liant le module n à une identité Id. Il connaît un message m. S'il s'agit d'une authentification dynamique, c'est-à-dire, d'une preuve interactive de connaissance, il est encore appelé démonstrateur. En cas d'authentification d'entité, le démonstrateur n'a pratiquement rien à faire. En cas d'authentification de message, le démonstrateur dispose d'une fonction de hachage f. S'il s'agit d'une signature numérique de message, c'est-à-dire, d'une preuve non interactive de connaissance, le pilote est encore appelé signataire ; signataire dispose de l'exposant public de vérification v et d'une fonction de hachage f. Une troisième entité vérifie ; c'ést le contrôleur. Selon le cas, le contrôleur vérifie l'authentification ou la signature ; il dispose d'un module public N pour ouvrir les certificats afin d' établir une identité Id et un module n, de l'exposant public de vérification v = 2k, des l clés publiques GA, GB, ... et de la fonction de hachage f. Note. Chaque jeu de composantes Q1 Q2 Q3 ... représente une clé privée Q. Chaque paire de clés selon la présente invention est liée aux nombres v et n par l' une des deux relations suivantes. G.Qv =1 (mod n) ou bien G Qv (mod n) En termes de charge de travail du témoin, la solution optimale consiste à utiliser les facteurs premiers, les paramètres des restes chinois et les composantes des clés- privées. Chaque clé privée Q est construite, puis, stockée et utilisée sous la forme de composantes, Q1 Q2... une composante par facteur premier, Pl P2 ... Les clés privées Q n'apparaissent alors jamais et le témoin n'utilise pas non plus les clés publiques G. En termes de charge de travail du contrôleur, la solution optimale consiste à utiliser pour G une valeur qui soit la plus petite possible. Les valeurs sur un seul quartet ou un seul octet sont particulièrement conseillées. En pratique, on utilise pour ga gb ... les premiers nombres premiers : 2,3, 5,7, 11, .... Dans la présentation qui suit le témoin utilise les facteurs premiers et les restes chinois. Le témoin peut s'en abstenir, ce qui affecte simplement et seulement les actions du témoin. Le protocole GQ2 déroule les étapes suivantes permettant au contrôleur de vérifier l'origine et l'intégrité d'un message m. - L'authentification dynamique est une preuve interactive. - La signature numérique est une preuve non interactive. 1. 3. Etapes Le procédé comporte les étapes suivantes. Etape 1. Engagement du témoin # A chaque appel, pour chaque exposant public de vérification vx vy vz ..., le témoin tire au hasard et en privé au moins un jeu de nombres entiers : pour chaque facteur premier p,, chaque jeu comporte un nombre entier r, positif et plus petit que p@. Ces nombres entiers sont ensuite appelés les aléas r, r2 r3 ... 0 RI rlv (mod p1 ); RZ --- r2 (mod p2 ); R3 == r3' (mod P3); # Puis, le témoin établit chaque engagement R (mod n) selon la méthode des restes chinois. Ra' = R2 (mode); Si 1 - a' a - 1 a' Sinon, a - 1 + Pl a ' Rl,2 =.{Àa.Ra" (mod pt )Î P2 + R2; Rb RI 2 (mod P3); Si R3 >- Rb , Rb = R3 - Rb ; Sinon, Rb = R3 + p3 - Rb ; Rt,2,3 = î.b.Rb (mod P3 )pt P2 + Rt,2; Et ainsi de suite. R est égal à R1,2,3... Pour chaque exposant public de vérification vx vy vz ..., il y a autant d' engagements R que de jeux'd' aléas r, r2 r3 ... Etape 2. Défi au témoin En cas d'authentification d'entité, le démonstrateur transmet tout ou partie de chaque engagement R au contrôleur ; après avoir reçu tout ou partie de chaque engagement R, le contrôleur produit au moins une séquence de nombres de 0 à v-1 pris au hasard. En cas d'authentification de message, le démonstrateur applique une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour obtenir un jeton T à transmettre au contrôleur, après avoir reçu le jeton T, le contrôleur produit au moins une séquence de nombres de 0 à v-1 pris au hasard. En cas de signature numérique de message, le signataire applique une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour obtenir au moins une séquence de nombres de 0 à v-1. Dans les trois cas, pour chaque exposant public de vérification vx vy vz..., chaque séquence comporte autant de nombres de 0 à v-1 qu'il y a de paires de clés selon la présente invention ; dans chaque séquence, les nombres sont notés par dA, dB, ... Chaque séquence de nombres de 0 à v-1 est ensuite appelée défi d. Pour chaque exposant public de vérification vx vy vz ..., il y a autant de défis d que d'engagements R. Etape 3. Réponse du témoin au défi # Pour chaque exposant public de vérification vx vy vz pour chaque facteur premier p@, le témoin calcule la puissance dA ième de la composante QA, (mod p), la puissance dB ième de la composante QB, (mod p@), le produit des résultats précédents par l'aléa r, (mod p#); Dl -rl,QAdA.QBdB... (mod PI); D2 - = r2.QA2A.QB2B... (mod p2); D3 --- r3 .QA3 A .QB dB ... (mod p3 ); # Puis, pour chaque exposant public de vérification vx vy vz ..., le témoin établit au moins une réponse D (mod n) selon la méthode des restes chinois. Da = D2 (modp,); Si D, >Da, Du =Dl -DQ; Sinon, Da =Dl + pl -Da; D1,2 ==a.D (mod pl )p2 +' D2 Db - D1,2 (mod p3 ); Si D3 >- Db, Db D3 - Db; Sinon, Db = D3 + p3 - Db; Dl,2,3 == b .D (mod p3 )p .p2 + Di,2 Et ainsi de suite. D est égal à D1,2,3... Pour chaque exposant public de vérification vx vy vz il y a autant de réponses D que de défis d. Note. Chaque appel au témoin se traduit à l'interface par autant de triplets {R, d, D} que de jeux d'aléas r, r2 r3 Remarquons qu'en élevant la réponse D à la puissance v ième (mod n), on doit retrouver l'engagement R divisé ou multiplié, selon l'équation retenue pour lier les paires de clés selon la présente invention aux nombres v et n, par la puissance dA ième de GA, la puissance dB ième de GB, ... Par conséquent, chaque triplet {R, d, D} doit vérifier l'une des deux relations suivantes. R = GAdA .GB dB .... D'' (mod n); ou bien R GA dA .GBdB.... == D v (mod 11); Etape 4. Données destinées au contrôleur En cas d'authentification d'entité ou de message, le démonstrateur transmet chaque réponse D au contrôleur. En cas de signature numérique de message, le signataire transmet un message signé au contrôleur. Le message signé comprend le message m, ainsi que : * chaque défi d ou chaque engagement R, * chaque réponse D. Etape 5. Vérification exercée par le contrôleur Note. On aurait pu tester ici le symbole de Jacobi de chaque réponse, à condition d'avoir forcé le symbole de l'aléa à l'étape 1. Cependant, il vaut mieux laisser tomber les symboles . Il est bien plus économique d'accepter de perdre un bit de défi. Note. L'une des deux relations suivantes reconstruit un engagement noté par R'. R'=.(GAdA.GBdB....)Dv (mod n); ou bien R' --~ D'' l (GAdA.GBB.... ) (mod n); En cas d'authentification d'entité, le contrôleur doit appliquer la formule appropriée pour reconstruire chaque engagement R' : aucun ne doit être nul. Chaque engagement reconstruit R' doit reproduire l'intégralité des données transmises à l'étape 2, c'est-à-dire, tout ou partie de chaque engagement R. Lorsque toutes les conditions sont remplies, l'authentification d'entité est réussie. En cas d'authentification de message, le contrôleur doit appliquer la formule appropriée pour reconstruire chaque engagement R' : aucun ne doit être nul. Puis, il doit appliquer la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R' pour reconstruire le jeton T'. Le jeton reconstruit T' doit être identique au jeton T de l'étape 2. Lorsque toutes les conditions sont remplies, l'authentification de message est réussie. En cas de signature numérique de message, selon le cas, # le contrôleur doit appliquer la formule appropriée pour reconstruire chaque engagement R' : aucun ne doit être nul. Puis, il doit appliquer la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R' pour reconstruire chaque défi d'. Chaque défi reconstruit d' doit être identique au défi d figurant dans le message signé. Lorsque toutes les conditions sont remplies, la signature est correcte. # le contrôleur doit appliquer la fonction de hachage f ayant comme arguments le message m et chaque engagement R figurant dans le message signé pour reconstruire chaque défi d'. Puis, il doit appliquer la formule appropriée pour contrôler la cohérence de chaque triplet {R, d', D}. Chaque triplet doit être cohérent. Lorsque toutes les conditions sont remplies, la signature numérique est correcte. 2. Triplets Chaque appel au témoin se traduit par une collection de triplets à l'interface du témoin. Chaque triplet {R, d, D} comprend un engagement R, un défi d et une réponse D. Il y a deux manières de produire des triplets : une manière de produire en privé et une manière de produire en public. # Le témoin produit en privé selon la chronologie suivante : à chaque appel, il fixe d'abord un nouveau jeu d'aléas qu'il transforme en un engagement R, puis, il produit la réponse D à n'importe quel défi d de 0 à v-1. # N'importe qui peut produire en public selon la chronologie suivante : quel que soit le défi d de 0 à v-1, n'importe qui peut compléter le triplet à partir de n'importe quelle réponse D en établissant l'engagement R grâce aux nombres publics G, v et n. 3. Tenailles Par définition, deux triplets sont en tenaille lorsqu' ils sont constitués des deux réponses D et E à deux défis d et e pour le même engagement R, c'est-à-dire, {R, d, D} et {R, e, E}. A chaque appel, le témoin est en position de produire des triplets en tenaille : il lui suffirait de réutiliser un jeu d'aléas. Mais il se garde bien des tenailles : en tirant au hasard un jeu d'aléas à chaque appel, il utilise en pratique chaque fois un nouveau jeu d'aléas. 3. 1. Paire de clés selon la présente invention conférant une sécurité équivalente à la connaissance de la clé privée Q La connaissance de deux triplets en tenaille équivaut à la connaissance de la clé privée Q. Démonstration. D'une part, le témoin se configure à partir des facteurs premiers PI P2 p3 ...,de la clé privée Q et de l'exposant public de vérification v. Une fois configuré, le témoin peut produire une tenaille : il lui suffit d'utiliser deux fois le même jeu d'aléas. D'autre part, deux triplets en tenaille se traduisent par les équations suivantes : D --- r.Qd (mod n) et E --- r.Qe (mod n) avec 0 Par conséquent, ED = Qe-d (mod n), avec 0 vaut Q'~d (mod n), c'est-à-dire l'une des v-1 valeurs { , Qu, Q', ... Qv- (mod n)}, sachant que Qv (mod n) est la clé publique G ou son inverse modulo n. La solution fait appel à l'identité de Bezout. Par définition, les coefficients de Bezout de v et de e-d sont les deux entiers k et l vérifiant les relations suivantes ; l'algorithme de division d'Euclide permet de les calculer efficacement. 0 Qk.v-l.(e-d) = Q1 (mod n) C'est-à-dire, (Q" kl(Q e-d )1 = Q (mod n) #Lorsque G =6" (mod n) est utilisée, G kl(EID)l (mod n) vaut Q (mod n) ou son inverse modulo n. #Lorsque G.Qv =1 (mod n) est utilisée, Gk.(E / D)l (mod n) vaut Q (mod n) ou son inverse modulo n. 3. 2. Jeux de clés selon la présente invention conférant une sécurité équivalente à la connaissance de la factorisation de n Les nombres GQ2 sont des produits de l+1 facteurs premiers distincts congrus à 3 (mod 4) avec la contrainte suivante : pour chacun de 1 petits nombres distincts, appelés nombres de base et notés par ga, gb, ainsi que pour chacune de leurs combinaisons multiplicatives ga.gb, ..., soit en tout 2i-1 nombres représentés de façon générique par g, les deux équations x2 # g (mod n) et x2 = -g (mod n) n'ont pas de solution en x dans l'anneau des entiers modulo n. On dit alors que les nombres g et -g sont deux résidus non quadratiques modulo n. Note. Petit signifie plus petit que le plus petit des facteurs premiers. De préférence, les nombres de base sont les l premiers nombres premiers ga = 2, gb = 3,... Les plus simples des nombres GQ2 sont les nombres de Williams avec un seul nombre de base ga = 2 et deux facteurs premiers, l'un congru à 3 (mod 8) et l'autre à 7 (mod 8). Rappelons que pour chaque nombre g qui n'est pas un carré, chaque nombre premier congru à 3 (mod 4) et plus grand que g se classe dans l'une des deux catégories suivantes : - la catégorie où g est un résidu non quadratique (et donc -g un résidu quadratique), - la catégorie où -g est un résidu non quadratique (et donc g un résidu quadratique). Définition. Deux facteurs premiers sont équivalents ou complémentaires au regard d'un nombre g selon qu'ils appartiennent ou pas à la même catégorie au regard du nombre g. Définition. Au regard de chaque nombre g, le profil dej facteurs est défini par une séquence de l bits en attribuant le symbole 1 au premier facteur ainsi que à tous les facteurs qui lui sont équivalents, c'est-à-dire qui ont le même symbole de Legendre, et le symbole 0 à tous les facteurs qui lui sont complémentaires, c'est-à-dire, qui ont l'autre symbole de Legendre. Pour obtenir le profil au regard du produit de plusieurs nombres de base ga, gb, ..., on calcule le produit des symboles de Legendre, puis, on code le profil résultant en attribuant le symbole 1 au premier facteur ainsi que à tous les facteurs qui lui sont équivalents, c'est-à-dire, qui ont le même symbole de Legendre, et le symbole 0 à tous les facteurs complémentaires, c'est-à-dire, qui ont l'autre symbole de Legendre. Pour pouvoir comparer des profils, il faut ranger les facteurs dans le même ordre, par exemple, dans l'ordre croissant. 3. 2.1. Méthode systématique de construction des nombres GQ2 Voyons comment construire les nombres GQ2 de manière systématique, de façon à pouvoir intégrer simplement la méthode de construction dans un générateur de modules n. Le premier facteur doit simplement être congru à 3 (mod 4). On notera toutefois son symbole de Legendre par rapport aux l nombres de base ga, gb, ... Le deuxième facteur doit être complémentaire au regard du premier nombre de base ga. Par exemple, lorsque ga = 2, un facteur doit être congru à 3 (mod 8) et l'autre à 7 (mod 8) : un nombre de Williams. Par exemple encore, lorsque ga = 3, un facteur doit être congru à 1 (mod 3) et l'autre à 2 (mod 3), sachant qu'ils sont bien sûr tous deux congrus à 3 (mod 4). On notera également le symbole de Legendre du deuxième facteur par rapport aux l nombres de base ga, gb, ... et on commencera à établir les 2'-1 profils. Le troisième facteur doit prendre en compte le deuxième nombre de base gb (par exemple, gb = 3 après ga = 2). Deux cas se présentent, selon que les deux premiers facteurs premiers sont équivalents ou complémentaires au regard du nombre gb. - Lorsque les deux premiers facteurs premiers sont équivalents au regard du nombre gb, le nouveau facteur doit être complémentaire au regard du nombre gb. - S'ils sont complémentaires, alors par rapport au premier facteur, le nouveau facteur doit être équivalent au regard de l'un des deux nombres ga ou gb et complémentaire au regard de l'autre. On notera encore le symbole de Legendre du troisième facteur par rapport aux l nombres de base ga, gb, ... et on commencera à établir les 2'-1 profils. Ainsi, avec trois facteurs, pour les deux nombres de base, il y a trois profils possibles : 100, 110 et 101. La construction assure un profil différent pour chacun des trois nombres ga, gb et ga fois gb. Le quatrième facteur doit prendre en compte le troisième nombre de base gc (par exemple, gc = 5 après gb = 3 et ga = 2). Deux cas se présentent, selon que les trois premiers facteurs sont équivalents ou pas au regard du nombre gc. - Lorsque les trois premiers facteurs premiers sont équivalents au regard du nombre gc, le nouveau facteur doit être complémentaire au regard du nombre gc. - S'ils ne sont pas équivalents, ils reproduisent le profil de l'un des trois nombres ga, gb ou ga fois gb (par exemple, 2,3 ou 6), soit g ce nombre. Par rapport au premier facteur, le nouveau facteur doit être équivalent au regard de l'un des deux nombres g ou gc et complémentaire au regard de l' autre. On notera encore le symbole de Legendre du quatrième facteur par rapport aux nombres de base ga, gb, ... et on continuera à établir les 2'-1 profils. Ainsi, avec quatre facteurs premiers, pour trois nombres de base, il y a sept profils possibles: 1000,1100, 1010,1001, 1110,1101 et 1011. La construction assure un profil différent pour chacun des sept nombres suivants : les trois nombres de base : ga, gb, gc et leurs quatre combinaisons multiplicatives ga.gb, ga.gc, gb.gc et ga.gb.gc. Ensuite, la procédure se généralise aisément de la manière suivante. Lorsque j facteurs sont déjà construits, le 7+1 ième facteur doit prendre en compte un j ième nombre de base ; appelons g' ce nombre, par exemple, le j ième nombre premier après les j-1 premiers nombres premiers. Deux cas se présentent, selon que les j premiers facteurs sont équivalents ou pas au regard du nombre g'. - Lorsque les j premiers facteurs premiers sont équivalents au regard du nombre g', le nouveau facteur doit être complémentaire au regard du nombre g'. - S'ils ne sont pas équivalents, ils reproduisent le profil de l'un des j-1 nombres ga, gb, ... ou de l'une de leurs combinaisons multiplicatives ga fois gb, ... ; appelons g ce nombre. Par rapport au premier facteur, le nouveau facteur doit être équivalent au regard de l'un des deux nombres g ou g' et complémentaire au regard de l'autre. On notera encore le symbole de Legendre du j+1 ième facteur par rapport aux l nombres de base ga, gb, ... et on continuera à établir les 2'-1 profils. 3. 2.2. Utilisation cryptographique des nombres GQ2 Voici deux motifs d'intérêt cryptographique pour les nombres GQ2. - Produire des paires de clés pour des schémas de signature numérique qui étendent l'usage de l'exposant 2 à des modules n ayant plus de deux facteurs premiers. - Produire des jeux de clés pour des schémas GQ2 d'authentification dynamique ou de signature numérique. 3. 2.2.1 Dans l'annexe A de ISO/CEI 9796, extension de l'usage des exposants pairs à des modules ayant plus de deux facteurs premiers, chaque facteur étant congru à 3 (mod 4). => Pour éviter de divulguer la factorisation du module n en appliquant la fonction privée de signature à un argument, c'est-à-dire, en calculant une racine carrée (mod n), il faut égaliser les symboles de Legendre de l'argument par rapport à l'ensemble des facteurs premiers du module n. Cette égalisation se fait en divisant par un égaliseur approprié. A la vérification, il faut décoder le résultat, c'est-à-dire, déduire la valeur de l'égaliseur mis en #uvre à la signature. Il faut d'abord choisir et normaliser un ou plusieurs petits nombres. Ces nombres sont de préférence les l premiers nombres premiers. Nous les nommerons les égaliseurs de base et les noterons par ga, gb ... Les l égaliseurs de base complétés par leurs combinaisons multiplicatives, soit 2-1 nombres en tout, constituent l'ensemble des égaliseurs. Voyons comment utiliser les égaliseurs. # Deux facteurs - On choisit d'abord un égaliseur de base ga (par exemple, ga = 2 ; pourrait aussi bien prendre 3, 5 ou 7 ...). Puis, on choisit deux facteurs premiers complémentaires au regard de l'égaliseur ga (par exemple, lorsque ga = 2, un facteur est congru à 3 (mod 8) et l'autre à 7 (mod 8)). Lorsqu'un argument est soumis à la fonction privée de signature, on calcule le symbole de Jacobi de l'argument par rapport au module n. S'il vaut +1, on garde l'argument tel quel. S'il vaut-1, on remplace l'argument par l' argument divisé par l' égaliseur ga pour mettre le symbole de Jacobi à +1 ; suite à cette opération, le symbole de Jacobi de l'argument vaut +1, c'est-à-dire que les symboles de Legendre de l'argument sont alors tous les deux égaux à-1 ou bien tous les deux égaux à +1. Cette méthode figure dans l'annexe A de la norme ISO/CEI 9796. # Trois facteurs - On choisit d'abord deux égaliseurs de base, par exemple, ga = 2 et gb = 3. Puis, on choisit les trois facteurs premiers de sorte que ga = 2, gb = 3 et ga.gb = 6 soient tous les trois des résidus non quadratiques (mod n). Lorsque les trois symboles de Legendre de l'argument sont inégaux, on les égalise en divisant l' argument selon le cas par ga = 2, gb = 3 ou ga.gb = 6, c'est-à-dire, par l'égaliseur qui présente le même profil que l'argument. # Quatre facteurs - On choisit d'abord trois égaliseurs de base, par exemple, ga = 2, gb = 3 et gc = 5. Puis, on choisit les quatre facteurs premiers de sorte que les sept nombres 2,3, 5,6, 10,15 et 30 soient des résidus non quadratiques (mod n). Lorsque les quatre symboles de Legendre de l'argument sont inégaux, on les égalise en divisant l'argument par l' égaliseur approprié : 2,3, 5,6, 10,15 ou 30, c' est-à- dire, celui qui présente le même profil que l'argument. # Cinq facteurs - On choisit d'abord quatre égaliseurs de base, par exemple, ga = 2, gb = 3, gc = 5 et gd = 7. Puis, on choisit les cinq facteurs premiers de sorte que les quinze nombres 2,3, 5,6, 7,10, 14, 15,21, 30,35, 42,70, 105,210 soient des résidus non quadratiques (mod n). Lorsque les symboles de l'argument sont inégaux, on les égalise en divisant l'argument par l'égaliseur approprié : 2,3, 5,6, 7, 10,14, 15,21, 30,35, 42,70, 105,210, c'est-à-dire celui qui a le même profil que l'argument. # Et ainsi de suite. 3. 2.2.2. GQ2 - Le module est le produit de facteurs premiers congrus à 3 (mod 4). # La propriété à assurer est que toute paire de triplets GQ2 en tenaille révèle une factorisation non triviale du module. Il faut d'abord choisir un ou plusieurs petits nombres. Ce sont de préférence les l premiers nombres premiers. Nous les appellerons les racines triviales de base et les noterons par ga, gb, gc ... Les racines triviales de base complétées par leurs combinaisons multiplicatives, soit, en tout, 2'-1 nombres, constituent l'ensemble des racines triviales. # Deux facteurs - Il faut d'abord sélectionner une seule racine triviale de base ga (par exemple, ga = 2 ; pourrait aussi bien prendre 3,5 ou 7 ...). Il faut ensuite choisir les deux facteurs de sorte que la racine triviale ga soit un résidu non quadratique (mod n), c'est-à-dire que les facteurs soient complémentaires au regard de la racine triviale ga. # Trois facteurs - II faut d'abord sélectionner deux racines triviales de base, par exemple, ga = 2 et gb = 3. Il faut ensuite choisir les trois facteurs de sorte que les trois (2 puissance 2 moins 1) racines triviales ga gb et ga.gb, par exemple, 2,3 et 6, soient des résidus non quadratiques (mod n). # Quatre facteurs - Il faut d'abord sélectionner trois racines triviales de base, par exemple, ga = 2, gb = 3 et gc = 5. Il faut choisir ensuite les quatre facteurs premiers de sorte que les nombres 2,3 et 5, ainsi que leurs combinaisons multiplicatives, c'est-à-dire, 6,10, 15 et 30, soient tous les sept (2 puissance 3 moins 1) des résidus non quadratiques (mod n). Ces sept nombres sont les racines triviales. # Cinq facteurs - Il faut d'abord sélectionner quatre racines triviales de base, par exemple, ga = 2, gb = 3, gc = 5 et gd = 7. Il faut choisir ensuite les cinq facteurs premiers de sorte que les nombres 2,3, 5 et 7, ainsi que leurs combinaisons multiplicatives, c'est-à-dire, 6,10, 14,15, 21,30, 35,42, 70,105 et 210, soient tous les quinze (2 puissance 4 moins 1) des résidus non quadratiques (mod n). Ces quinze nombres sont les racines triviales. # Et ainsi de suite. Dans les mécanismes GQ2 d'authentification dynamique et de signature numérique, toute paire de triplets GQ2 en tenaille révèle une des k valeurs {6. Q2, Q4, ... jusqu'au k-1 ième carré de Q (mod n) où Q est une des 2'-' combinaisons multiplicatives des l clés privées de base QA, QB, ... Ceci revient à connaître le k-1 ième carré d'un nombre Q (mod n) ; nombre ou son inverse (mod n) est une racine carrée (mod n) de la combinaison correspondante des clés publiques, combinaison que nous notons par G = g2. Nommons q ce nombre. La mise en #uvre de nombres GQ2, c'est-à-dire, de modules n construits selon la méthode précédentes à partir de l+1 facteurs premiers et de l racines de base ga gb ..., assurent que, pour toute paire de triplets en tenaille, le nombre q obtenu ci-dessus est une racine carrée non triviale de G = g2 dans l'anneau des entiers modulo n. Le module n divise q2-gz, alors qu'il ne divise ni q-g ni q+g. Ainsi, avec des nombres GQ2, toute paire de triplets GQ2 en tenaille révèle une factorisation non triviale du module n. Sur l'ensemble des paires de triplets en tenaille, toutes les factorisations non triviales sont possibles : la factorisation est déterminée par le profil du nombre g concerné : d'une côté, tous les facteurs premiers équivalents au premier facteur premier, de l'autre tous les autres facteurs premiers, c'est-àdire, ceux qui sont complémentaires au premier facteur premier. 4. Sécurité du nouveau procédé D'une manière générale, la sécurité des protocoles sans transfert de connaissance s'analyse selon trois notions de base définies dans l'article de base de Shafi Goldwasser, Silvio Micali et Charles Rackoff. Dans le cas qui nous intéresse, une entité proclame : - Voici un module n, un exposant de vérification v et une clé publique G ; j'utilise la factorisation de n et je connais la clé privée Q. Par définition, lorsque l'entité connaît les facteurs premiers, c'est un témoin. A chaque appel, le témoin produit de manière privée un triplet que le contrôleur accepte. Par conséquent, la procédure est complète. Par définition, lorsque l'entité ne connaît pas les facteurs premiers, c'est un tricheur. A chaque appel, le tricheur a une chance sur v de deviner le défi d (si les v défis sont équiprobables) ; peut donc anticiper un défi, n'importe lequel, et ainsi tromper le contrôleur ; s'il pouvait anticiper un deuxième défi après avoir produit l' engagement, il connaîtrait une paire de triplets en tenaille, ce qui contredit la définition du tricheur. Par conséquent, la procédure est robuste. Note. La présente version fait fi du symbole de Jacobi ; prix à payer est la perte d'un bit de défi par paire de clés selon la présente invention. Le procédé ne marche pas pour k = 1 ; tricheur a une stratégie gagnante totale. A partir de k = 2, le tricheur n'a plus qu'une stratégie gagnante partielle : il peut anticiper deux défis mais pas trois. Quelle que soit la manière dont se comporte le monde extérieur, il reçoit seulement l'information que le témoin connaît les facteurs premiers. Plus précisément, quelle que soit l'information émise par le témoin, n'importe qui aurait pu la constituer sans interaction avec le témoin ; n'importe qui peut simuler les transmissions et produire un enregistrement qui reproduit les caractéristiques statistiques des informations recueillies lors d'une interaction avec le témoin. Durant l' interaction, un observateur ne peut pas distinguer un honnête témoin d'un faux témoin utilisant une liste de défis convenue à l'avance. Après l' interaction, un juge ne peut pas distinguer les deux types d'enregistrements. En effet, on ne peut pas distinguer un enregistrement de triplets produits de manière publique et un enregistrement de triplets produits de manière privée. Par conséquent, la procédure utilisée par le témoin ne laisse filtrer aucune information sur la valeur des facteurs premiers. L'entité qui prouve pilote toujours le même témoin fonctionnant toujours de la même manière : le témoin utilise les facteurs premiers et la clé privée Q sans les révéler ; le témoin assure la protection des facteurs premiers et de la clé privée Q. Le contrôleur vérifie la clé privée Q sans en prendre connaissance. La procédure se déroule sans transfert de connaissance . Certaines paires de clés selon la présente invention sont telles que la connaissance de la clé privée Q implique la connaissance de la factorisation du module n. Avec le nouveau procédé, la factorisation et la clé privée Q ne s'usent pas, même quand on s'en sert. 5. Performances du nouveau procédé avec v = 2k Dans cette évaluation, on fait l'hypothèse que la valeur de G est petite, par exemple, G = 4. La charge de travail du témoin et la charge de travail du contrôleur dépendent du niveau de sécurité recherché, c'est-à-dire du produit de deux nombres : le nombre j de triplets produits à chaque appel au témoin et la valeur donnée au paramètre de sécurité k moins un (en effet, on perd un bit de défi en laissant tomber le symbole de Jacobi). Pour une authentification avec j.(k-1) = 16 avec j = l, le témoin doit effectuer 17 carrés pour calculer l'engagement R, puis, en moyenne 16 carrés et 8 multiplications plus une multiplication pour calculer la réponse D, soit 41 opérations (mod n) ; cette charge est divisée par deux avec deux facteurs premiers, soit 20 opérations (mod n) ; cette charge est divisée par trois avec trois facteurs premiers, soit environ 14 opérations (mod n) ; et ainsi de suite. le contrôleur doit effectuer 17 carrés (mod n). Pour une signature avec j. (k-1 ) = 80 avec j = 1, le témoin doit effectuer 81 carrés pour calculer l'engagement R, puis, en moyenne 80 carrés et 40 multiplications plus une multiplication pour calculer la réponse D, soit 202 opérations (mod n) ; cette charge est divisée par deux avec deux facteurs premiers, soit 100 opérations (mod n) ; cette charge est divisée par trois avec trois facteurs premiers, soit 67 opérations (mod n) ; et ainsi de suite. le contrôleur doit effectuer 81 carrés (mod n). Remarque. Pour une valeur donnée du niveau de sécurité j.k, le choix j = 1 ne change pratiquement pas la charge de travail du témoin, ni celle du contrôleur ; elle minimise toutefois le nombre de triplets produits, c'est-àdire, la charge de transmission pour mener à bien l'opération, que cette opération soit une authentification ou une signature. Utilisons plusieurs paires de clés selon la présente invention, toutes avec le même exposant public de vérification v. Cela fait apparaître un niveau de sécurité j. (k-1 ).l où l est le nombre de paires de clés selon la présente invention. Le fait d'utiliser plusieurs paires de clés selon la présente invention diminue la charge de travail du témoin, ainsi que la charge de travail du contrôleur. Dans le tableau ci-dessous, M représente une multiplication (mod n) et X un carré (mod n). Rappelons que sur le composant ST 16601 pour carte à puce, avec une horloge normalisée à 3,579545 MHz, le carré modulo pour 512 bits se fait en 150 ms et la multiplication modulo en 200 ms. (k-1).l= 16 1=1 1 = 2 1 = 4 1 = l= 16 Engagement 17 X 9 X 5 X 3 X 2 X Réponse 1 M + 1 M + 1M + 4X+ 1 M + 1 M + 16X+ 8X+ 8M 2X+ 1 X + 8M 8X 8M 8M Total du 33 X + 17 X + 9 X + 5 X + 3 X + témoin 9M 9M 9M 9M 9M Trois 11 X + 6X+ 3X+ 2X+ 1 X + facteurs 3 M 3 M 3 M 3 M 3 M Vérification 17 X 9 X 5 X 3 X 2 X Le compromis pour l = 4 est très attrayant parce que, compte tenu des restes chinois avec un module à trois facteurs premiers, le terminal et la carte ont à peu près la même charge de travail. Il est préconisé d'utiliser les clés publiques GA = 4, GB = 9, GC = 25, GD = 49. Revendications 1. Procédé pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur, - l'authenticité d'une entité et/ou - l'origine et l' intégrité d'un message m, ledit procédé met en #uvre trois entités : - une première entité appelée témoin dispose des facteurs premiers p,, p2, ... (p1,...) (i étant supérieur ou égal à 2) d'un module public n tel que n = Pl'P2' P3.... , ledit témoin dispose aussi * des composantes QAI, QA 21 ... (QA,, ...), et Qui, QB2, ... (QB, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB, ... ayant respectivement pour composantes GA,, GA2, ... (GA,, ...) et GBI, GB2' ... (GB, ...) * des exposants publics de vérification vx, vy,... lesdites clés privées et clés publiques étant liées par des relations du type : GA.QAvx mod n 1 ou GA QAvxmod n lesdits exposants publics de vérification vx, vy,... étant utilisés par le témoin pour calculer des engagements R en effectuant des opérations du type: R, r1vx mod p, où r; est un entier, associé au nombre premier p,, tel que 0 * appelée signataire dans les cas de la preuve de l'origine et de l'intégrité d'un message, - une troisième entité appelée contrôleur vérifie l'authentification ou l'origine et l' intégrité d'un message, ledit témoin reçoit de la deuxième entité ou du contrôleur un ou plusieurs défis d tel que 0 # d D, = ri, QA; . QB, .... mod p. où r, est un aléa tel que 0 R'== GA dA. GB dB....DV mod n ou du type : R'. GA dA. GB dB.... == DV mod n ledit contrôleur vérifie que les triplets {R', d, D} sont cohérents. 2. Procédé pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m, ledit procédé met en #uvre trois entités : - une première entité appelée témoin dispose des facteurs premiers Pl, P2, ... (P; ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = Pi'P2' P3' "' ledit témoin dispose aussi * des composantes QA,, QA2, ... (QA, , ...), et QB1, QB2, ... (QB, , ...), ..., représentant des clés privées QA, QB, * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA@, ...) et GB,, GB2, ... (GB,,...) * d'un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QA' mod n = 1 ou GA = QA'mod n ledit exposant public de vérification v étant utilisé par le témoin pour calculer des engagements R, # en effectuant des opérations du type : Ri = riv mod p où r est un entier, tiré au hasard, associé au nombre premier p,, tel que 0 r, qu'il y a autant d'engagements R que de collections d'aléas { ruz, rz, r3, ... }, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - une deuxième entité pilote dudit témoin, * appelée démonstrateur dans le cas de la preuve de l'authenticité d'une entité ou de l' authenticité d'un message, * appelée signataire dans les cas de la preuve de l'origine et de l'intégrité d'un message, - une troisième entité appelée contrôleur vérifie l' authentification ou l' origine et l' intégrité d'un message, ledit témoin reçoit de la deuxième entité ou du contrôleur, des collections de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égalu nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, ledit témoin calcule à partir de chacune desdites collections de défis {dA, dB, ...}des réponses D # en effectuant des opérations du type : D -r.QA 1 dA . QB 1 dB .... mod P # puis en appliquant la méthode des restes chinois, de telle sorte qu' il y a autant de réponses D que d'engagements R et de défis d, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des D pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n ledit contrôleur recevant une réponse D calcule à partir de cette réponse un engagement R' en effectuant des opérations du type : R'=== GA dA. GB dB.... DV mod n ou du type : R' . GA dia. GB dll Dv mod n ledit contrôleur vérifie que les triplets {R', d, D} sont cohérents. 3. Procédé selon la revendication 2 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur l'authenticité d'une entité ; ledit procédé met en #uvre trois entités : 1 - une première entité appelée témoin dispose des facteurs premiers p1, p2, ...(p., ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.pz. p3.... , ledit témoin dispose aussi * des composantes QA,, QA2, ... (QA,, ...), et QB,, QB2, ... (QB, , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB, ... ayant respectivement pour composantes GA,, GA2, ... (GA,, ...) et GB,, Gaz, ... (GB,, ...) * d'un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QA' mod n = 1 ou GA --- QA'mod n 2 - une deuxième entité pilote dudit témoin appelée démonstrateur 3 - une troisième entité appelée contrôleur vérifie l'authentification, pour prouver l'authenticité d'une entité, ledit témoin, ledit démonstrateur et ledit contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : - à chaque appel, le témoin tire au hasard et en privé au moins une collection de nombres entiers {r,, r2, r3, ...},telle que, pour chaque facteur premier P" chaque collection comporte un aléa rpositif et plus petit que p, , - pour chaque facteur premier p, , le témoin élève chaque aléa r, à la puissance v ième modulo p, R; --- r mod p, de sorte que le nombre d'opérations arithmétiques modulo p1, à effectuer pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - puis, le témoin établit chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas 1 1"1? r2, r3, ...}, # étape 2. défi d destiné au témoin : - le démonstrateur transmet tout ou partie de chaque engagement R au contrôleur, - le contrôleur, après avoir reçu tout ou partie de chaque engagement R, produit au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, # étape 3. réponse du témoin au défi d : - ledit témoin calcule des réponses D à partir desdites collections de défis d {dA, dB, ...}reçues du contrôleur en effectuant des opérations du type : D, = r, . QA, QBI dB mod p, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des D, pour chacun des p. est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, puis en appliquant la méthode des restes chinois, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au contrôleur : - le démonstrateur transmet au contrôleur chaque réponse D, # étape 5. vérification par le contrôleur : ledit contrôleur calcule à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'== GA dA. GR dB....DV mod n ou du type : R' . GA dA. GB dB .... --- Dv mod n ledit contrôleur vérifie que chaque engagement reconstruit R' reproduit tout ou partie de chaque engagement R transmis à l'étape 2 par le démonstrateur. 4. Procédé selon la revendication 2 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur l'authenticité d'un message m, ledit procédé met en #uvre trois entités : 1 - une première entité appelée témoin dispose des facteurs premiers p,, p2, ... (p, ,...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ..., ledit témoin dispose aussi * des composantes QA,, QA2, ... (QA,...), et QB,, QB2, ... (QB,, ...), ..., représentant des clés privées QA, QB, ... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, à,,... (GA, ...) et GB,, GB2, ... (GBi * d'un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QA" mod n = 1 ou GA QA'mod n 2 - une deuxième entité pilote dudit témoin appelée démonstrateur, 3 - une troisième entité appelée contrôleur vérifie l'authentification, pour prouver l'authenticité d'un message ledit témoin, ledit démonstrateur et ledit contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : - à chaque appel, le témoin tire au hasard et en privé au moins une collection de nombres entiers {r,, r2, r3, ...},telle que pour chaque facteur premier p, chaque collection comporte un aléa r positif et plus petit que p, , - pour chaque facteur premier p, , le témoin élève chaque aléa r, à la puissance v ième modulo p, R@ # R1v mod p, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des R, pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - puis, le témoin établit chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu' il y a autant d'engagements R que de collections d'aléas {rJ, r2, r3, ... }, # étape 2. défi d destiné au témoin : - le démonstrateur applique une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour un jeton T, - le démonstrateur transmet le jeton T au contrôleur, - le contrôleur, après avoir reçu le jeton T, produit au moins une collection de défis d {dA, dB, ...}tels que 0 D --~ ri . QAi dA QB .... mod p, puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p1 à effectuer pour calculer chacun des D pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au contrôleur : - le démonstrateur transmet au contrôleur chaque réponse D, # étape 5. vérification par le contrôleur : ledit contrôleur calcule à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' == GA dA. GB dB.... DV mod n ou du type : R'. GA dA.GB dB....= Dv mod n ledit contrôleur applique la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R' pour reconstruire le jeton T', ledit contrôleur vérifie que le jeton T' est identique au jeton T transmis à l'étape 2 par le démonstrateur. 5. Procédé selon la revendication 2 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur la signature numérique d'un message m, ledit procédé met en #uvre trois entités : 1 - une première entité appelée témoin dispose des facteurs premiers Pt, p2g ... (p , ..0) (i étant supérieur ou égal à 2) d'un module public n tel que n = Pl 'P2' P3' - ledit témoin dispose aussi * des composantes QA1, QA., ... (QA , ...), et QB,, QB2, (QB , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAx, ... (GA, ...) et GB,, GBx, ... (GB, ...) * d'un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GAoQAv mod n == 1 ou GA = QA'mod n 2 - une deuxième entité pilote dudit témoin appelée signataire, 3 - une troisième entité appelée contrôleur vérifie l'authentification, pour prouver la signature d'un message ledit témoin, ledit démonstrateur et ledit contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : - à chaque appel, le témoin tire au hasard et en privé au moins une collection de nombres entiers {r1, r2, r3, ...},telle que, pour chaque facteur premier p,, chaque collection comporte un aléa r positif et plus petit que p, , - pour chaque facteur premier p1, le témoin élève chaque aléa r, à la puissance v ième modulo p1 Ri = r@v mod p, de sorte que le nombre d'opérations arithmétiques modulo p@ à effectuer pour calculer chacun des R pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - puis, le témoin établit chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas { r, rz, r3, ... }, # étape 2. défi d destiné au témoin : - le signataire applique une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour obtenir au moins une collection de défis d {dA, dB, ...} tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...} comprenant un nombre de défis égal au nombre de paires de clés, - le signataire transmet les collections de défis d au témoin, * étape 3. réponse du témoin au défi d : - ledit témoin calcule des réponses D à partir desdites collections de défis d {dA, dB, ...}reçues du contrôleur en effectuant des opérations du type : D 1 == r . 1 QA 1 dA . QB 1 dB .... mod P puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des Di pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, - ledit témoin transmet les réponses D au signataire et/ou au contrôleur, # étape 4. données destinées au contrôleur : - le signataire transmet un message signé au contrôleur comprenant : / le message m, / les collections de défis d ou les engagements R, / chaque réponse D # étape 5. vérification par le contrôleur : cas où le contrôleur reçoit la collection des défis d, dans le cas où le contrôleur reçoit la collection des défis d et des réponses D, ledit contrôleur calcule à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'=GA d" . GB dB .... Dv mod n ou du type : R'. GA dA. GB dB Dv mod n ledit contrôleur applique la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R' pour reconstruire chaque défi d', ledit contrôleur vérifie que chaque défi d' reconstruit est identique au défi d figurant dans le message signé, cas où le contrôleur reçoit la collection des engagements R dans le cas où le contrôleur reçoit la collection des engagements R et des réponses D, ledit contrôleur applique la fonction de hachage f ayant comme arguments le message m et chaque engagement R pour reconstruire chaque défi d', ledit contrôleur reconstruit alors la collection des engagements R' en effectuant des opération du type R9 =- GA d'A GB d'R D' mod n ou du type : R\GAd'".GBd'B....---D"modn ledit contrôleur vérifie que chaque engagement R' reconstruit est identique à l'engagement R figurant dans le message signé, 6. Procédé selon l'une quelconque des revendications 1 à 5 tel que les composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB, ,...), ... des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA , QB1, ... pour chacun desdits facteurs premiers p,, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA,, QA2, ... (QA,,...), et QB,, QB2, ... (QB,,...), ... par la méthode des restes chinois, lesdites clés publiques GA, GB, ... étant calculée # en effectuant des opérations du type : GA, QA1v mod p # puis en appliquant la méthode des restes chinois pour établir GA tel que GA QAv mod n ou bien tel que GA.QAv mod n = 1 de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des GA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n. 7. Procédé selon la revendication 6 tel que l'exposant public de vérification v est un nombre premier, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. 8. Procédé selon l'une quelconque des revendications 1 à 5 tel que l'exposant public de vérification v est du type k v = a ou k est un paramètre de sécurité plus grand que 1. 9. Procédé selon la revendication 8 tel que : - l' exposant public de vérification v est du type v = 2" ou k est un paramètre de sécurité plus grand que 1, - la clé publique GA est un carré gA2inférieur à n choisi de telle sorte que les deux équations x2= gA mod n et x2 # - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n, - lesdites composantes QAt' QA2, ... (QA, ...) de la clé privée QA sont telles que : GA= QA 2expc) mod p, ou bien telles que : GA.QA, 2.exp(k) mod p,=- 1 on les obtient en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p.) de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer pour calculer chacun des QA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. 10. Procédé selon la revendication 9 tel que pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p,), * dans le cas où le facteur premier p, est congru à 3 modulo 4, on applique notamment un algorithme du type : x = (p+l)/4 ; y # xkmod (p-1) ; z = y ; QA, = GAZ mod p, * dans le cas où le facteur premier p est congru à 1 modulo 4, on utilise les suites de Lucas. 11. Système pour diminuer la charge de travail pendant une session destinée à prouver à un serveur contrôleur, - l'authenticité d'une entité et/ou - l' origine et l'intégrité d'un message m, ledit procédé met en #uvre trois entités : - une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, le dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p1, ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ..., ledit dispositif témoin dispose aussi d'une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB; , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB, ... ayant respectivement pour composantes GA,, GA2, ... (GA,, ...) et GBI, GB2, ... (GB, ...) * des exposants publics de vérification vx, vy, ... lesdites clés privées et clés publiques étant liées par des relations du type : GA.QA" mod n = 1 ou GA --- QAvx mod n ledit dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R en effectuant des opérations du type : R = r1vx mod p, où r est un aléa tel que 0 - une troisième entité appelée dispositif contrôleur se présentant notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin, ledit dispositif contrôleur vérifie l'authentification ou l'origine et l'intégrité d'un message, ledit dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur un ou plusieurs défis d tel que 0 Di = r . QA, dA . QBi dB .... mod p. où r, est un entier, associé au nombre premier p,, tel que 0 R' = GA d" . GB dB .... D" mod n ou du type : R' . GA dA. GB dB .... --~ Du mod n ledit dispositif contrôleur comporte des quatrièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents. 12. Système pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m, ledit procédé met en #uvre trois entités : - une première entité appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, ledit dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = Pl'P2' p3 , ledit dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QA,, QA2, ... (QA, ...), et QB,, QB2' ... (QB,, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, Go 21 ... (GA,, ... ) et GB,, GB2, ... (GB|5 ...) * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type : GA.QA" mod n =- 1 ou GA --- QA'mod n ledit dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R, # en effectuant des opérations du type : R,---r"modp, où r est un entier, tiré au hasard, associé au nombre premier p,, tel que 0 le témoin tire au hasard une ou plusieurs collections d'aléas de telle sorte qu'il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ... }, de sorte que le nombre d'opérations arithmétiques modulo p1 à effectuer par lesdits premiers moyens de calcul pour calculer chacun des R, pour chacun des p1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - une deuxième entité, appelée dispositif pilote dudit dispositif témoin, pouvant être également contenue notamment dans ledit objet nomade, ledit dispositif pilote est appelé * dispositif démonstrateur dans le cas de la preuve de l'authenticité d'une entité ou de l'authenticité d'un message, * dispositif de signature dans les cas de la preuve de l'origine et de l'intégrité d'un message, - une troisième entité, appelée dispositif contrôleur, se présentant notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin, ledit dispositif contrôleur vérifie l'authentification ou l' origine et l'intégrité d'un message, ledit dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur, des collections de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...} comprenant un nombre de défis égal au nombre de paires de clés, ledit dispositif témoin comporte des deuxièmes moyens de calcul pour calculer à partir de chacune desdites collections de défis {dA, dB, ...}des réponses D # en effectuant des opérations du type : Di r,. QA, dA . QB, dB.... mod p, # puis en appliquant la méthode des restes chinois, de telle sorte qu' il y a autant de réponses D que d'engagements R et de défis d, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par lesdits deuxièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, ledit dispositif contrôleur, recevant une ou plusieurs réponses D, comporte des troisièmes moyens de calcul pour calculer à partir desdites réponses D un engagement R' en effectuant des opérations du type : R' --- GA d" . GB dB .... D" mod n ou du type : R'. GA dA. GB dB....::::: DV mod n ledit dispositif contrôleur comporte des quatrièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents. 13. Système selon la revendication 12 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur l'authenticité d'une entité ; ledit procédé met en #uvre trois entités : 1- une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, ledit dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p; , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ... , ledit dispositif témoin dispose aussi d'une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA , ...), et QB,, QB2, ... (QB, , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GA, ... (GA,, ...) et GB,, GB2, ... (GB,, ...) * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QA" mod n == 1 ou GA QAvmod n 2 - une deuxième entité appelée dispositif démonstrateur dudit dispositif témoin, pouvant être également contenue notamment dans ledit objet nomade, 3 - une troisième entité appelée dispositif contrôleur se présentant sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin, pour prouver l'authenticité d'une entité, ledit dispositif témoin, ledit dispositif démonstrateur et ledit dispositif contrôleur exécutent les étapes suivantes : # étape 1. engagement R du dispositif témoin : - le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r1, r2, r3, ... },telle que pour chaque facteur premier p,, chaque collection comporte un aléa r, positif et plus petit que p, , - le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r; à la puissance v ième modulo p, , pour chaque facteur premier p, , R. = r' mod p, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R; pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n, - puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas r 1, r2, r3, ... }, # étape 2. défi d destiné au dispositif témoin : - le dispositif démonstrateur comporte des moyens de transmission pour transmettre tout ou partie de chaque engagement R au dispositif contrôleur, - le dispositif contrôleur comporte des troisièmes moyens de calcul pour calculer, après avoir reçu tout ou partie de chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, # étape 3. réponse du dispositif témoin au défi d : - ledit dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D ,à partir desdites collections de défis d {dA, dB, ...}reçues du dispositif contrôleur, en effectuant des opérations du type : D 1 == r . 1 QA 1 dA . QB. 1 dB .... mod P puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au dispositif contrôleur : - le démonstrateur comporte des moyens de transmission pour transmettre au dispositif contrôleur chaque réponse D, # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'=GA d" . GB dB .... Dv mod n ou du type : R'. GA dA . GB dB .... # Dv mod n ledit dispositif contrôleur comporte des sixièmes moyens de calcul pour comparer et vérifier que chaque engagement reconstruit R' reproduit tout ou partie de chaque engagement R transmis à l'étape 2 par le dispositif démonstrateur. 14. Système selon la revendication 12 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur l' authenticité d'un message m, ledit procédé met en #uvre trois entités : 1- une première entité appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, ledit dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p1, ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p,. p3.... , ledit dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QA,, QA 21 ... (QA , ...), et QBII QBz, ... (QB , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA,, ...) et GB,, GB2, ... (GB,, ...) * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type : GA.QA mod n = 1 ou GA QAvmod n 2 - une deuxième entité, appelée démonstrateur dudit dispositif témoin, pouvant être également contenue notamment dans ledit objet nomade, 3 - une troisième entité appelée dispositif contrôleur se présentant sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin, pour prouver l'authenticité d'un message ledit dispositif témoin, ledit dispositif démonstrateur et ledit dispositif contrôleur exécutent les étapes suivantes : # étape 1. engagement R du dispositif témoin : - ledit dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {ruz, rz, r31 ...},telle que pour chaque facteur premier P" chaque collection comporte un aléa r, positif et plus petit que p1, - ledit dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r à la puissance v ième modulo p@, pour chaque facteur premier p, , Ri # riv mod p, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des Ri pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n, - puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas { r,, r2, r3, ... }, # étape 2. défi d destiné au dispositif témoin : - le dispositif démonstrateur comporte des premiers moyens de calcul pour calculer, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour un jeton T, - ledit dispositif démonstrateur comporte des moyens de transmission pour transmettre le jeton T au dispositif contrôleur - ledit dispositif contrôleur comporte des troisièmes moyens de calcul pour calculer, après avoir reçu le jeton T, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...} comprenant un nombre de défis égal au nombre de paires de clés, . étape 3. réponse du dispositif témoin au défi d : - ledit dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collection de défis d {dA, dB, ...} reçues du dispositif contrôleur en effectuant des opérations du type : Di = r, . QAidA. QB, dB.... mod pi puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D. pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au dispositif contrôleur : - le démonstrateur comporte des moyens de transmission pour transmettre au dispositif contrôleur chaque réponse D, # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' ~~ GA d" . GB dB ....Dv mod n ou du type : R' . GA dA. GR dB.... == DV mod n ledit dispositif contrôleur comporte des sixièmes moyens de calcul pour calculer, en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R', le jeton T', ledit dispositif contrôleur comporte des septièmes moyens de calcul pour comparer et vérifier que le jeton T' est identique au jeton T transmis à l' étape 2 par le dispositif démonstrateur. 15. Système selon la revendication 12 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur la signature numérique d'un message m, ledit procédé met en #uvre trois entités : 1- une première entité, appelée dispositif témoin, contenues notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, ledit dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ... , ledit dispositif témoin comporte aussi une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA, ...), et QB,, QB2, ... (QB, , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB, ... ayant respectivement pour composantes GA,, GAZ, ... (GA,, ...) et GB,, GB2, ... (GB,,...) * un exposant publique de vérification v lesdites paires de clés privées et publiques étant liés par des relations du type: GA.QAV mod n = 1 ou GA QA'mod n 2 - une deuxième entité appelée dispositif de signature, pouvant être également contenue notamment dans ledit objet nomade, 3 - une troisième entité appelée dispositif contrôleur se présentant sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif contrôleur comporte des moyens de connexion pour le connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique audit dispositif témoin, pour prouver la signature d'un message ledit dispositif témoin, ledit dispositif démonstrateur et ledit dispositif contrôleur exécutent les étapes suivantes : # étape 1. engagement R du témoin : - le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r,, r2, r3, ...},telle que pour chaque facteur premier p,, chaque collection comporte un aléa r positif et plus petit que p, , - le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r, à la puissance v ième modulo p,, pour chaque facteur premier Pi' r1 = r1v mod p, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu' il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, # étape 2. défi d destiné au dispositif témoin : - ledit dispositif de signature comporte des troisièmes moyens de calcul pour calculer, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, - ledit dispositif témoin comporte des moyens de transmission pour transmettre les réponses D au dispositif de signature et/ou au dispositif contrôleur, # étape 4. données destinées au dispositif contrôleur : - le dispositif de signature transmet au dispositif contrôleur un message signé comprenant : / le message m, / les collections de défis d ou les engagements R, / chaque réponse D # étape 5. vérification par le dispositif contrôleur : cas où le dispositif contrôleur reçoit la collection des défis d, dans le cas où le dispositif contrôleur reçoit les collections des défis d et des réponses D, ledit dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' -~- GA d" . GB dB .... D" mod n ou du type : R' . GA dA. GB dB. 'H === DV mod n ledit dispositif contrôleur comporte des sixièmes moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R', ledit dispositif contrôleur comporte des septièmes moyens de calcul pour comparer et vérifier que chaque défi d' est identique au défi d figurant dans le message signé, cas où le dispositif contrôleur reçoit la collection des engagements R dans le cas où le dispositif contrôleur reçoit la collection des engagements R et des réponses D, ledit dispositif contrôleur comporte des cinquièmes moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R, ledit dispositif contrôleur comporte des sixièmes moyens de calcul pour calculer alors la collection des engagements R' en effectuant des opérations du type R' --- GA d'" . GB d'B .... D" mod n ou du type : R'. GA d'A. GB d'B. ... # Dv mod n ledit dispositif contrôleur comporte des septièmes moyens de calcul pour comparer et vérifier que chaque engagement R' reconstruit est identique à l'engagement R figurant dans le message signé. 16. Système selon l'une quelconque des revendications 11 à 15 tel que les composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB,...), ... des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA,, QB, , ... pour chacun desdits facteurs premiers p,, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA,, QA2, ... (QA,, ...), et QB,, QB2, ... (QB, ,...), ... par la méthode des restes chinois, ledit dispositif témoin comportant des huitièmes moyens de calcul pour calculer lesdites clés publiques GA, GB, ..., # en effectuant des opérations du type : GAi QA@v mod p, # puis en appliquant la méthode des restes chinois pour établir GA tel que GA =- QAv mod n ou bien tel que GA.QA' mod n - 1 de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les huitièmes moyens de calcul dudit dispositif témoin pour calculer chacun des GA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, 17. Système selon la revendication 16 tel que l'exposant public de vérification v est un nombre premier, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. 18. Système selon l'une quelconque des revendications 11 à 15 tel que l'exposant public de vérification v est du type k v=a où k est un paramètre de sécurité plus grand que 1. 19. Système selon la revendication 18 tel que : - l'exposant public de vérification v est du type v = 2k où k est un paramètre de sécurité plus grand que 1, - la clé publique GA est un carré gA2inférieur à n choisi de telle sorte que les deux équations x2= gA mod n et x2 # - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n - ledit dispositif témoin comportant des neuvièmes moyens de calcul pour calculer les dites composantes QA,, QA2, ... (QA, , ...) de la clé privée QA en appliquant des formules telles que : GA= QA2exp(k) mod pi ou bien telles que : A ,QAi 2.exp(k) mod p,=1 et en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p) de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les neuvièmes moyens de calcul du dispositif témoin pour calculer chacun des QA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. 20. Système selon la revendication 19 tel que pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p,), * dans le cas où le facteur premier p, est congru à 3 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme du type : x = (p+l)/4 ; y --- xk mod (p-1) ; z = y ; QA, GAZ mod p, * dans le cas où le facteur premier p, est congru à 1 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme basé sur les suites de Lucas. 21. Objet nomade, se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, pour diminuer la charge de travail pendant une session destinée à prouver à un serveur contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m, ledit objet nomade faisant intervenir trois entités : - une première entité, appelée dispositif témoin, contenue dans ledit objet nomade, ledit dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p1.p2. p3. ... , ledit dispositif témoin dispose aussi d'une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA,, ...), et QB,, QB2, ... (QB,, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB, ... ayant respectivement pour composantes GA,, GAZ, ... (GA;, ...) et GB,, GB2, ... (GB,, ...) * des exposants publics de vérification vx, vy, ... lesdites clés privées et clés publiques étant liées par des relations du type : GA.QA" mod n =- 1 ou GA =- QAvxmod n ledit dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R en.effectuant des opérations du type : Ri = r1vx mod p, où r est un aléa tel que 0 ledit dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur un ou plusieurs défis d tel que 0 # d D. = r1. QA, dA . QBi dB .... mod p, où r, est un entier, associé au nombre premier p,, tel que 0 22. Objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur, - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m, ledit objet nomade faisant intervenir trois entités: - une première entité, appelée dispositif témoin, contenue dans ledit objet nomade, ledit dispositif témoin dispose d'une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ... , ledit dispositif témoin dispose aussi d'une deuxième zone mémoire contenant * des composantes QA,, QA2, ... (QA., ...), et QB,, QB2, ... (QB,, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAZ, ... (GA., ... ) et GB,, Gaz, ... (GBI * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QA mod n = 1 ou GA = QA'mod n ledit dispositif témoin comporte aussi des premiers moyens de calcul pour calculer des engagements R, # en effectuant des opérations du type : Ri = riv mod p, où r est un entier, tiré au hasard, associé au nombre premier p,, tel que 0 r notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif contrôleur vérifie l'authentification ou l'origine et l'intégrité d'un message, ledit objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif pilote audit dispositif contrôleur, ledit dispositif témoin reçoit du dispositif pilote ou du dispositif contrôleur, des collections de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, ledit dispositif témoin comporte des deuxièmes moyens de calcul pour calculer à partir de chacune desdites collections de défis {dA, dB, ...}des réponses D # en effectuant des opérations du type : D@ # r . QAdA QBdB .... mod p, # puis en appliquant la méthode des restes chinois, de telle sorte qu' il y a autant de réponses D que d'engagements R et de défis d, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par lesdits deuxièmes moyens de calcul pour calculer chacun des D, pour chacun des p. est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, ledit objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur la ou lesdites réponses D. 23. Objet nomade selon la revendication 22 pour diminuer la charge de travail pendant une session destinée à prouver à un dispositif contrôleur l' authenticité d'une entité ; ledit objet nomade faisant intervenir trois entités : 1 - une première entité, appelée dispositif témoin, contenue dans ledit objet nomade, ledit dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p1.p2. p3. ... , ledit dispositif témoin comporte aussi une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA , ...), et QB,, QB2, ... (QB1, ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GAz, ... (GA,,...) et GB,, GBz, ... (GB,, ...) * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QAV mod n = 1 ou GA = QAv mod n 2 - une deuxième entité, appelée dispositif démonstrateur dudit dispositif témoin, pouvant être également contenue dans ledit objet nomade, 3 - une troisième entité appelée dispositif contrôleur se présentant notamment sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif démonstrateur audit dispositif contrôleur, pour prouver l'authenticité d'une entité, ledit objet nomade exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : - le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r1, r2, r3, ...},telle que pour chaque facteur premier p1, chaque collection comporte un aléa r positif et plus petit que p, , - le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r, à la puissance v ième modulo p, , pour chaque facteur premier p, , R, r1v mod p de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas {rI, rz, r3, ... }, # étape 2. transmission des engagements R et réception des défis d destinés au dispositif témoin : - ledit objet nomade comporte des moyens de transmission pour transmettre au dispositif contrôleur tout ou partie de chaque engagement R, - ledit objet nomade comporte des moyens de réception pour recevoir des collections de défis d {dA, dB, ...}produits par ledit dispositif contrôleur, # étape 3. réponse du dispositif témoin aux défis d : - ledit dispositif témoin comporte des troisièmes moyens de calcul pour calculer des réponses D , à partir desdites collections de défis d {dA, dB, ...}reçues du dispositif contrôleur, en effectuant des opérations du type : D, = r1. QA,dA. QB, dB .... mod p, puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p. à effectuer par les troisièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au dispositif contrôleur : - ledit objet nomade comporte des moyens de transmission pour transmettre au dispositif contrôleur chaque réponse D, # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur vérifie la cohérence des triplets {R, d, D} et l'authenticité de l'entité contrôlée. 24. Objet nomade selon la revendication 22 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur l'authenticité d'un message m, ledit objet nomade faisant intervenir trois entités : 1 - une première entité, appelée dispositif témoin, contenue dans ledit objet nomade, ledit dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p1, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p,.p2. p3. ... , ledit dispositif témoin comporte aussi une deuxième zone mémoire contenant * des composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB,... ayant respectivement pour composantes GA,, GA2, ... (GA., ...) et GB,, GB2' ... (GB,,...) * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QA' mod n -~-1 ou GA -= QAvmod n 2 - une deuxième entité, appelée démonstrateur dudit dispositif témoin, pouvant être également contenue dans ledit objet nomade, 3 - une troisième entité appelée dispositif contrôleur se présentant sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et/ou ledit dispositif démonstrateur audit dispositif contrôleur, pour prouver l'authenticité d'un message ledit objet nomade exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : - ledit dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r,, F2, r3, ...},telle que, pour chaque facteur premier p1, chaque collection comporte un aléa r positif et plus petit que p, , - ledit dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r, à la puissance v ième modulo p, , pour chaque facteur premier p, , R. = r1v mod p, (de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, - puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas { r, r2, r3, ... }, # étape 2. réception des défis d destinés au dispositif témoin: - le dispositif démonstrateur comporte des premiers moyens de calcul pour calculer, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R pour un jeton T, - ledit objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur le jeton T, - ledit objet nomade comporte des moyens de réception pour recevoir des collections de défis d {dA, dB, ...}produits par ledit dispositif contrôleur au moyen du jeton T, # étape 3. réponse du dispositif témoin au défi d : - ledit dispositif témoin comporte des troisièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...}reçues du dispositif contrôleur en effectuant des opérations du type : Dj - r . QA dA . QBi dB .... mod p, puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p. à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D pour chacun des p@ est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au dispositif contrôleur : - l'objet nomade comporte des moyens de transmission pour transmettre audit dispositif contrôleur chaque réponse D # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur vérifie la cohérence des triplets {R, d, D) et l'authenticité du message m. 25. Objet nomade selon la revendication 22 pour diminuer la charge de travail pendant une session destinée à prouver à un contrôleur la signature numérique d'un message m, ledit objet nomade faisant intervenir trois entités : 1- une première entité, appelée dispositif témoin, contenue dans ledit objet nomade, ledit dispositif témoin comporte une première zone mémoire contenant des facteurs premiers p,, p2, ... (p, , ...) (i étant supérieur ou égal à 2) d'un module public n tel que n = p1.p2. p3. ... , ledit dispositif témoin comporte aussi une deuxième zone mémoire contenant : * des composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB, , ...), ..., représentant des clés privées QA, QB,... * des clés publiques GA, GB, ... ayant respectivement pour composantes GA,, GAZ, ... (GA,, ...) et GB,, GB2, ... (GB,, ...) * un exposant public de vérification v lesdites paires de clés privées et publiques étant liées par des relations du type: GA.QAv mod n = 1 ou GA = QAvmod n 2 - une deuxième entité appelée dispositif de signature, pouvant être également contenue dans ledit objet nomade, 3 - une troisième entité appelée dispositif contrôleur se présentant sous la forme d'un terminal et/ou d'un serveur distant connecté à un réseau de communication informatique, ledit objet nomade comporte des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif témoin et ledit dispositif de signature audit dispositif contrôleur, pour prouver la signature d'un message ledit objet nomade exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : - le dispositif témoin comporte des premiers moyens de calcul pour tirer au hasard et en privé, à chaque appel, au moins une collection de nombres entiers {r1, r2, r3, ...},telle que pour chaque facteur premier p1, chaque collection comporte un aléa r, positif et plus petit que p1, - le dispositif témoin comporte des deuxièmes moyens de calcul pour élever chaque aléa r à la puissance v ième modulo p1, pour chaque facteur premier p,, R = r1v mod p, de sorte que le nombre d'opérations arithmétiques modulo p1 à effectuer par les deuxièmes moyens de calcul pour calculer chacun des R, pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n, - puis, lesdits deuxièmes moyens de calcul dudit dispositif témoin établissent chaque engagement R modulo n selon la méthode des restes chinois, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas {r1, r2, r3, ...}, # étape 2. défi d destiné au dispositif témoin : - ledit dispositif de signature comporte des troisièmes moyens de calcul pour calculer, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, - le dispositif de signature transmet les collections de défis d au témoin, # étape 3. réponse du dispositif témoin au défi d : - ledit dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...}reçues du dispositif contrôleur, en effectuant des opérations du type : Di # r . QA, dA . QBidB mod p, puis en appliquant la méthode des restes chinois, de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les quatrièmes moyens de calcul pour calculer chacun des D, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, - l'objet nomade comporte des moyens de transmission pour transmettre les réponses D au dispositif de signature et/ou au dispositif contrôleur, # étape 4. données destinées au dispositif contrôleur : - l'objet nomade comporte des moyens de transmission pour transmettre au dispositif contrôleur un message signé comprenant : / le message m, / les collections de défis d ou les engagements R, / chaque réponse D # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur vérifie la cohérence des triplets {R, d, D} et la signature numérique du message m. 26. Objet nomade selon l'une quelconque des revendications 21 à 25 tel que les composantes QA,, QA2, ... (QA, , ...), et QB1, QB2, ... (QB, , ...), ... des clés privées QA, QB,... sont des nombres tirés au hasard à raison d'une composante QA, , QB , ... pour chacun desdits facteurs premiers p@, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA,, QA2, ... (QAi, ...), et QB,, QB2, ... (QB; , ...), par la méthode des restes chinois, ledit dispositif témoin comportant des huitièmes moyens de calcul pour calculer lesdites clés publiques GA, GB, ..., # en effectuant des opérations du type : GA, QAiv mod p, # puis en appliquant la méthode des restes chinois pour établir GA tel que GA QAv mod n ou bien tel que GA.QAv mod n 1 de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les huitièmes moyens de calcul dudit dispositif témoin pour calculer chacun des GA; pour chacun des P1 est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, 27. Objet nomade selon la revendication 26 tel que l'exposant public de vérification v est un nombre premier, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. 28. Objet nomade selon l'une quelconque des revendications 21 à 25 tel que l'exposant public de vérification v est du type k v=a où k est un paramètre de sécurité plus grand que 1. 29. Objet nomade selon la revendication 28 tel que : - l'exposant public de vérification v est du type v = 2k où k est un paramètre de sécurité plus grand que 1, - la clé publique GA est un carré gA2inférieur à n choisi de telle sorte que les deux équations x2= gA mod n et x2 # - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n - ledit dispositif témoin comportant des neuvièmes moyens de calcul pour calculer lesdites composantes QA,, QA2, ... (QA, , ...) de la clé privée QA en appliquant des formules telles que : GA= QAi2exp(k) mod p, ou bien telles que : GA .QA,2exp(k) mod p,= 1 et en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p,), de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les neuvièmes moyens de calcul du dispositif témoin pour calculer chacun des QA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la factorisation de n. 30. Objet nomade selon la revendication 29 tel que pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p), * dans le cas où le facteur premier p, est congru à 3 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme du type : x = (p+l)/4 ; y xk mod (p-1) ; z = y ; QA, GA' mod p, * dans le cas où le facteur premier p, est congru à 1 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme basé sur les suites de Lucas. 31. Dispositif de contrôle permettant de diminuer la charge de travail pendant une session destinée à vérifier : - l'authenticité d'une entité et/ou - l'origine et l'intégrité d'un message m, ledit dispositif de contrôle se présentant sous la forme d'un terminal ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif de contrôle mettant en #uvre : - un module public n tel que n soit le produit de facteurs premiers secrets p,, p2, ... (p,,...) (i étant supérieur ou égal à 2) n = p,.pz. p3.... , - des clés publiques GA, GB, ... - des exposants publics de vérification vx, vy, ... lesdites clés privées GA et les clés publiques associées QA étant liées par des relations du type : GA.QA" mod n = 1 ou GA # QAvx mod n ledit dispositif de contrôle faisant intervenir trois entités : - une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, ledit dispositif témoin produisant des engagements R, - une deuxième entité appelée dispositif pilote dudit dispositif~témoin pouvant être contenue notamment dans ledit objet nomade, - une troisième entité, appelée dispositif contrôleur, contenue dans ledit dispositif de contrôle, ledit dispositif de contrôle comporte : - des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif contrôleur audit dispositif témoin et/ou audit dispositif pilote, - des moyens de transmission pour transmettre les données produites par ledit dispositif contrôleur vers ledit dispositif témoin et/ou ledit dispositif pilote, - des moyens de réception pour recevoir les données provenant dudit dispositif témoin et/ou dudit dispositif pilote, ledit dispositif contrôleur comporte : - des premiers moyens de calcul pour produire un ou plusieurs défis d tel que 0 R' == GA d. DV. modn ou du type : R'@. Cad # Dva mod n - des troisièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents 32. Dispositif de contrôle permettant de diminuer la charge de travail pendant une session destinée à vérifier, - l'authenticité d'une entité et/ou - l' origine et l'intégrité d'un message m, ledit dispositif de contrôle se présentant sous la forme d'un terminal ou d'un serveur distant connecté à un réseau de communication informatique, ledit dispositif de contrôle mettant en #uvre : - un module public n tel que n soit le produit de facteurs premiers secrets p,, p2, ... (p,,...) (i étant supérieur ou égal à 2) n = p1.p2.p3. ... , - des clés publiques GA, GB,... - un exposant public de vérification v lesdites clés privées GA et les clés publiques associées QA étant liées par des relations du type : GA.QA" mod n == 1 ou GA = QAvrnod n ledit dispositif de contrôle faisant intervenir trois entités : - une première entité, appelée dispositif témoin, contenue notamment dans un objet nomade se présentant par exemple sous la forme d'une carte bancaire à microprocesseur, ledit dispositif témoin produisant des engagements R, - une deuxième entité, appelée dispositif pilote dudit dispositif témoin, pouvant être contenue notamment dans ledit objet nomade, - une troisième entité, appelée dispositif contrôleur, contenue dans ledit dispositif de contrôle, ledit dispositif de contrôle comporte : - des moyens de connexion pour connecter électriquement, électromagnétiquement, optiquement ou de manière acoustique ledit dispositif contrôleur audit dispositif témoin et/ou audit dispositif pilote, - des moyens de transmission pour transmettre les données produites par ledit dispositif contrôleur vers ledit dispositif témoin et/ou ledit dispositif pilote, - des moyens de réception pour recevoir les données provenant dudit dispositif témoin et/ou dudit dispositif pilote, ledit dispositif contrôleur comporte : - des premiers moyens de calcul pour produire un ou plusieurs défis d {dA, dB, ...}tels que 0 # dA # v - 1, - des deuxièmes moyens de calcul pour calculer, en fonction des réponses D reçues du dudit dispositif témoin et/ou dudit dispositif pilote, des engagements R' , en effectuant des opérations du type : R' --~ GA d" . GB dB .... Dv mod n ou du type : R'. GA dA. GB dB. ... # Dv mod n - des troisièmes moyens de calcul pour vérifier que les triplets {R', d, D} sont cohérents. 33. Dispositif de contrôle selon la revendication 32 permettant de diminuer la charge de travail pendant une session destinée à vérifier l'authenticité d'une entité ; dans le cas d'une authentification d'entité, le dispositif pilote est appelé dispositif démonstrateur, pour prouver l'authenticité d'une entité ledit dispositif de contrôle exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : - le dispositif témoin produit au moins un engagement R à partir d'au moins une collection d'aléas {1 r2, r3, ...},telle que, pour chaque facteur premier p, chaque collection comporte un aléa r entier positif et plus petit que p@, de telle sorte qu'il y a autant d'engagements R que de collections d'aléas , # étape 2. défis produits par le dispositif contrôleur et destinés au dispositif témoin : - lesdits moyens de réception du dispositif de contrôle reçoivent tout ou partie de chaque engagement R, transmis par le dispositif démonstrateur, et le transmet au dispositif contrôleur, - le dispositif contrôleur comporte des premiers moyens de calcul pour calculer, après avoir reçu tout ou partie de chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, # étape 3. réponse du dispositif témoin aux défis d : - ledit dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D , à partir desdites collections de défis d {dA, dB, ...}reçues du dispositif contrôleur, de telle sorte qu'il y a autant de réponses D que d'engagements R et de défis d, # étape 4. données destinées au dispositif contrôleur : - les moyens de réception du dispositif de contrôle reçoivent du dispositif démonstrateur chaque réponse D, # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur comporte des deuxièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R'=GA d" . GB dB .... Dv mod n ou du type : R'. GA dA. GR dB.... == DV mod n ledit dispositif contrôleur comporte des troisièmes moyens de calcul pour comparer et vérifier que chaque engagement reconstruit R' reproduit tout ou partie de chaque engagement R transmis à l'étape 2 par le dispositif démonstrateur 34. Dispositif de contrôle selon la revendication 32 permettant de diminuer la charge de travail pendant une session destinée à vérifier l'authenticité d'un message m, dans le cas d'une authentification d'un message m, le dispositif pilote est appelé dispositif démonstrateur, pour prouver l'authenticité d'un message m, ledit dispositif de contrôle exécute les étapes suivantes : # étape 1. engagement R du dispositif témoin : - le dispositif témoin produit au moins un engagement R à partir d'au moins une collection d'aléas {r1, r2, r3, ...},telle que, pour chaque facteur premier p@, chaque collection comporte un aléa r entier positif et plus petit que p@, de telle sorte qu' il y a autant d'engagements R que de collections d'aléas , # étape 2. défis d produits par ledit dispositif contrôleur et destinés au dispositif témoin : - lesdits moyens de réception du dispositif de contrôle reçoivent au moins un jeton T calculé et transmis par le dispositif démonstrateur en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, - ledit dispositif contrôleur comporte des premiers moyens de calcul pour calculer, après avoir reçu le jeton T, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...} comprenant un nombre de défis égal au nombre de paires de clés, # étape 3. réponse du dispositif témoin au défi d : - ledit dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...}reçues du dispositif contrôleur, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, # étape 4. données destinées au dispositif contrôleur : - les moyens de réception du dispositif de contrôle reçoivent du dispositif démonstrateur chaque réponse D, # étape 5. vérification par le dispositif contrôleur : ledit dispositif contrôleur comporte des deuxièmes moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' --- GA d" . GB dB .... D" mod n ou du type : R'. GA dA. GB dB .... - Dv mod n ledit dispositif contrôleur comporte des troisièmes moyens de calcul pour calculer, en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R', le jeton T', ledit dispositif contrôleur comporte des quatrièmes moyens de calcul pour comparer et vérifier que le jeton T' est identique au jeton T transmis à l'étape 2 par le dispositif démonstrateur. 35. Dispositif de contrôle selon la revendication 32 permettant de diminuer la charge de travail pendant une session destinée à vérifier la signature numérique d'un message m, dans le cas d'une authentification d'un message m, le dispositif pilote est appelé dispositif de signature, pour prouver la signature numérique du message m, ledit dispositif de contrôle exécute les étapes suivantes : # étape 1. engagement R du témoin : - le dispositif témoin produit au moins un engagement R à partir d'au moins une collection d'aléas {r1, r2, r3, ...},telle que pour chaque facteur premier p,, chaque collection comporte un aléa r, entier positif et plus petit que p, , de telle sorte qu'il y a autant d'engagements R que de collections d'aléas , # étape 2. défis d destinés au dispositif témoin : - ledit dispositif de signature calcule, en appliquant une fonction de hachage f ayant comme arguments le message m et chaque engagement R, au moins une collection de défis d {dA, dB, ...}tels que 0 # dA # v - 1, le nombre des collections de défis d étant égal au nombre d'engagements R, chaque collection {dA, dB, ...}comprenant un nombre de défis égal au nombre de paires de clés, - le dispositif de signature transmet les collections de défis d au témoin, # étape 3. réponse du dispositif témoin au défi d : - ledit dispositif témoin comporte des quatrièmes moyens de calcul pour calculer des réponses D, à partir desdites collections de défis d {dA, dB, ...}, de telle sorte qu'il y a autant de réponses D calculées par le témoin que d'engagements R et de défis d, - ledit dispositif témoin comporte des moyens de transmission pour transmettre les réponses D au dispositif de signature et/ou au dispositif contrôleur, # étape 4. données destinées au dispositif contrôleur : - les moyens de réception du dispositif de contrôle reçoivent du dispositif de signature un message signé comprenant : / le message m, / les collections de défis d ou les engagements R, / chaque réponse D # étape 5. vérification par le dispositif contrôleur : cas où le dispositif contrôleur reçoit la collection des défis d, dans le cas où le dispositif contrôleur reçoit les collections des défis d et des réponses D, ledit dispositif contrôleur comporte * des premiers moyens de calcul pour calculer à partir de chaque réponse D un engagement R' en effectuant des opérations du type : R' - GA d" . GB d$ .... D" mod n ou du type : R' . GA dA. GR dB....: DV mod n * des deuxièmes moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement reconstruit R', * des troisièmes moyens de calcul pour comparer et vérifier que chaque défi d' est identique au défi d figurant dans le message signé, cas où le dispositif contrôleur reçoit la collection des engagements R dans le cas où le dispositif contrôleur reçoit la collection des engagements R et des réponses D, ledit dispositif contrôleur comporte * des premiers moyens de calcul pour calculer chaque défi d', en appliquant la fonction de hachage f ayant comme arguments le message m et chaque engagement R, * des deuxièmes moyens de calcul pour calculer alors la collection des engagements R' en-effectuant des opération du type R': GA . GR .... D mod n ou du type : R'. GA d'A. GB d'Il. Dv mod n * des troisièmes moyens de calcul pour comparer et vérifier que chaque engagement R' reconstruit est identique à l'engagement R figurant dans le message signé. 36. Dispositif de contrôle selon l'une quelconque des revendications 31 à 35 tel que les composantes QA,, QA2, ... (QA, , ...), et QB,, QB2, ... (QB, , ...), des clés privées QA, QB, sont des nombres tirés au hasard à raison d'une composante QA, , QB, , ... pour chacun desdits facteurs premiers p,, lesdites clés privées QA, QB, pouvant être calculées à partir desdites composantes QA,, QA2, ... (QA,, ...), et QB1, QB2, ... (QB,, ...), ... par la méthode des restes chinois, ledit dispositif témoin comportant des moyens de calcul pour calculer lesdites clés publiques GA, GB,..., # en effectuant des opérations du type : GAi --- QA" mod p, # puis en appliquant la méthode des restes chinois pour établir GA tel que GA QA'mod n ou bien tel que Ga.QAv mod n = 1 de sorte que le nombre d'opérations arithmétiques modulo p, à effectuer par les huitièmes moyens de calcul dudit dispositif témoin pour calculer chacun des GA, pour chacun des p, est réduit par rapport à ce qu' il serait si les opérations étaient effectuées modulo n, 37. Dispositif de contrôle selon la revendication 36 tel que l'exposant public de vérification v est un nombre premier, de sorte que la paire de clés GA, QA confère une sécurité équivalente à la connaissance de la clé privée QA. 38. Dispositif de contrôle selon l' une quelconque des revendications 31 à 35 tel que l'exposant public de vérification v est du type k v=a où k est un paramètre de sécurité plus grand que 1. 39. Dispositif de contrôle selon la revendication 38 tel que : - l'exposant public de vérification v est du type v = 2k où k est un paramètre de sécurité plus grand que 1, - la clé publique GA est un carré gA2 inférieur à n choisi de telle sorte que les deux équations x2 # gA mod n et x2 = - gA mod n n'ont pas de solution en x dans l'anneau des entiers modulo n - ledit dispositif témoin comportant des neuvièmes moyens de calcul pour calculer les dites composantes QA,, QA2, ... (QA , ...) de la clé privée QA en appliquant des formules telles que : GA= QA, 2exp(k) mod p, ou bien telles que : GA .QA, 2..p(k)mod P,= 1 et en extrayant la k ième racine carrée de GA dans le corps de Galois CG(p,) de sorte que le nombre d'opérations arithmétiques modulo p@ à effectuer par les neuvièmes moyens de calcul du dispositif témoin pour calculer chacun des QA, pour chacun des p, est réduit par rapport à ce qu'il serait si les opérations étaient effectuées modulo n, de sorte que la paire de clés GA, QA confére une sécurité équivalente à la connaissance de la factorisation de n. 40. Dispositif de contrôle selon la revendication 39 tel que pour extraire la k ième racine carrée de GA dans le corps de Galois CG(p,), * dans le cas où le facteur premier p, est congru à 3 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme du type : x = (p+ 1 )/4 ; y = xk mod (p-1 ) ; z = y ; Qa, = GAZ mod p@ * dans le cas où le facteur premier p@ est congru à 1 modulo 4, les neuvièmes moyens de calcul du dispositif témoin appliquent notamment un algorithme basé sur les suites de Lucas.