FR 2850502 A1 20040730 FR 0300759 A 20030124 i La présente invention se rapporte à des procédés de cryptographie à clé publique et, plus précisément, à un procédé de signature numérique pour permettre à un système vérifieur B pouvant échanger des données numériques avec un système A d'éprouver 5 l'authenticité d'un message de données numériques m échangé avec ledit système A et un procédé d'authentification ou d'identification numérique pour permettre au système vérifieur B d'éprouver l'authenticité du système A. La présente invention se rapporte également à un système signataire. Pour la sécurisation des échanges de données sur les réseaux, les procédés de cryptographie à clé publique sont connus pour offrir un niveau de sreté élevé. Leur simplicité et leur faible cot vaut à des applications comme SSL d'être largement utilisées pour la protection des données échangées sur la Toile. Lorsqu'un système A et un système B échangent des données numériques par un réseau, il se pose le problème de vérifier l'authenticité de l'émetteur ou du destinataire des données échangées, pour détecter les cas o l'interlocuteur est un imposteur. Pour cela, on connaît des procédés d'authentification ou d'identification numérique 20 par lesquels un système vérifieur B peut éprouver l'authenticité d'un système A avec lequel il communique. Dans ces procédés, le système A est muni d'une clé secrète qu'il est le seul à connaître et il apporte au système vérifieur B une preuve, construite par le calcul, qu'il possède cette clé secrète. Outre la protection contre la falsification, une 25 propriété fondamentale d'un tel procédé est l'absence de transfert de connaissance, c'est-à-dire que la preuve apportée par le système A au système B ne doit pas permettre au système B de retrouver la clé secrète du système A, même après un grand nombre d'itérations du procédé. On connaît également des procédés de signature numérique qui résolvent en outre le problème de vérifier l'authenticité d'un message de données échangé, c'est-à-dire de détecter également les cas o le message est modifié au cours du transport entre les deux systèmes. Dans ces procédés, le système signataire A fournit par le calcul une signature 35 numérique qui dépend à la fois de la clé secrète et du message, et qui permet au système vérifieur B d'éprouver l'authenticité du message. Une caractéristique supplémentaire de la signature numérique est de fournir une preuve transférable par laquelle tout système muni de la clé publique du système signataire A peut éprouver l'authenticité du message. Une signature numérique est indépendante du destinataire et vérifiable par 5 n'importe quel destinataire recevant le message accompagné de sa signature. Cette caractéristique de la signature numérique, qui la distingue notamment des procédés d'authentification, est aussi appelée propriété de non-répudiation. On notera que la signature numérique est un procédé 10 cryptographique séparé et indépendant des procédés de chiffrement qui peuvent être utilisés pour garantir la confidentialité du message. D'une part, le message signé peut très bien être envoyé en clair pour être lisible par tout destinataire, d'autre part, si l'on souhaite chiffrer le message envoyé, tout procédé de chiffrement connu peut être utilisé. En outre, il 15 est possible de chiffrer un message préalablement signé ou de signer un message préalablement chiffré sans interférences entre ces opérations successives. Ceci s'applique de manière analogue à l'authentification numérique. Le cot calculatoire requis par les techniques de 20 cryptographie à clé publique connues gêne leur application à certains domaines. Il en découle des inconvénients importants, comme l'impossibilité de produire une réelle signature numérique à l'aide d'une carte de crédit ou l'impossibilité d'effectuer l'authentification d'une carte de crédit hors connexion avec un serveur central. En effet, dans ce 25 cas, le système vérifieur est un lecteur de carte bancaire, dans lequel on ne peut stocker que des données publiques pour des raisons de sécurité évidentes. De ce fait, la sécurisation des cartes de crédit et des radiotéléphones repose presque exclusivement sur la cryptographie à clé symétrique à l'heure actuelle. De nombreuses applications de ce type 30 gagneraient donc en sécurité si un procédé d'authentification ou de signature numérique était exécutable par une carte à puce de faible cot ou, mieux encore, par une simple carte à mémoire sans processeur. Pour résoudre ce problème, il a été proposé de décomposer la production d'une signature numérique en deux étapes: - une étape de pré-traitement, dans laquelle on engendre des données préparatoires indépendantes du message devant être signé et - une étape de terminaison de signature, qui est effectuée " à la volée " lorsque le message est prêt. En outre, des étapes ont été franchies dans l'effort de réduire au minimum la quantité de calculs restant à effectuer " à la 5 volée. " Ainsi, C. P. Schnorr, " Efficient Signature Generation by Smart Cards " Journal of Cryptology, 4, 1991, pp. 161 - 174 propose un procédé dans lequel les opérations restant à effectuer " à la volée " consistent en une addition modulaire et une seule multiplication modulaire. Ces opérations sont réduites à une seule multiplication régulière dans le 10 procédé proposé par G. Poupard et J. Stern, " Security analysis of a practical 'on the fly' authentication and signature generation >>, Proceedings of Eurocrypt 96, Lecture Notes in Computer Science 1403, Springer-Verlag, pp. 422-436 (1998). Dans ce dernier procédé, dénommé procédé GPS ci-dessous, la suppression des multiplications 15 modulaires s'avère également avantageuse en termes de longueur de clé et de longueur de signature. Pour obtenir un niveau de sécurité correspondant à 280 opérations élémentaires, une clé secrète de 160 bits et une signature de 420 bits suffisent. L'article " An Improved Signature Scheme without on line 20 Multiplication " de Takeshi Okamoto, Mitsuru Tada et Atsuko Miyaji dans Pre-proceedings of Financial Cryptography 02, décrit un procédé d'authentification et un procédé de signature numérique, dans lesquels un système signataire A est muni d'une clé publique (n,g) incluant un module entier n vérifiant n=pq, o p et q sont des nombres premiers 25 choisis tels que le problème du logarithme discret dans l'ensemble Zn soit insoluble en pratique, et une base entière g choisie dans le groupe Zn* de manière à présenter un ordre s qui vérifie gS=1 modulo n et 2k-'1 S, et le système vérifieur B calcule le nombre entier x,=gY-e modulo n à partir du nombre y reçu. Le système A est reconnu authentique lorsque y Le procédé de signature numérique est dérivé de ce procédé d'authentification numérique à l'aide de la technique décrite par A. Fiat, A. Shamir, "How to prove yourself: practical solutions of identification and signature problems", in Proceedings of Crypto 86, Lecture Notes in Computer Science 263, Springer-Verlag, pp. 181-187 (1987). La sécurité de ce type de signature numérique est fondée sur le caractère réputé non inversible d'une opération mathématique, c'est-àdire ici de l'opération d'exponentiation discrète dans l'ensemble Zn, qui peut également être noté Z/nZ. Au sens de l'invention, une opération mathématique est réputée non inversible lorsque le calcul consistant à 20 l'inverser présente une extrême difficulté, compte-tenu des moyens de calcul existants. En d'autres termes, il s'agit ici de l'extrême difficulté de calculer l'entier r lorsque l'on connaît l'entier x. Ceci assure le caractère secret de la clé privée x du système signataire A. En fait, il est impossible en pratique de résoudre ce problème, dit du logarithme 25 discret, pour des nombres p et q assez grands. Dans ces procédés, qui seront appelés procédés OTM cidessous d'après le nom des auteurs, aucune multiplication n'est nécessaire dans l'étape de terminaison de la signature ou de la preuve d'authenticité. En revanche, cette étape requiert une réduction modulaire 30 du nombre e, un entier de longueur b bits, par la clé secrète s, un entier de longueur k bits. Le cot calculatoire de cette opération dépend évidemment de la valeur des paramètres b et k. Le procédé ci-dessus a été proposé avec les valeurs suivantes des paramètres: k=160, a=224, b=a+t o f=24. Avec ces 35 valeurs, le cot calculatoire est petit et une taille de signature réduite à 304 bits est revendiquée, ce qui prendrait l'avantage sur le procédé GPS. Cependant, ce procédé présente une faille de sécurité qui rend inadmissible la valeur f=24. Cette faille découle du fait qu'il suffit à un imposteur voulant être authentifié par le système vérifieur B à la place d'un système A de deviner les (C+l) bits de poids le plus fort de e pour réussir. Plus précisément, du point de vue de l'authentification, l'imposteur peut procéder de la manière suivante: - choisir, avant de connaître le nombre e, un nombre e' de la forme e'=e12a-'+e0 avec el Dès que, par chance, el est obtenu égal aux (f+1) bits de poids le plus fort de e, l'imposteur est correctement authentifié en retournant le nombre y=r+e0 car les deux équations y De manière similaire, pour un imposteur voulant contrefaire la signature d'un message m, une possibilité est de: - choisir un nombre entier el représenté sur (f+1) bits - choisir aléatoirement un nombre r pour calculer ensuite un nombre x (modulo n) en élevant g à la puissance (r-e,2al), - calculer le nombre e=H(x,m), H étant une fonction de hachage cryptographique, - comparer les (f+1) bits de poids le plus fort de e avec el et recommencer avec un autre el s'ils ne sont pas égaux. Dès que el est égal aux (f+I) bits de poids le plus fort de e, la signature (x,e,y) est reconnue 30 authentique en retournant le nombre y=r+e0. Contrefaire une signature ou une preuve d'authenticité selon les procédés OTM requiert donc 2t+î opérations, soit quelques minutes de calcul pour la valeur f=24. De ce fait, la sécurité des procédés OTM ne peut être rendue acceptable qu'en élevant la valeur de t jusqu'au 35 moins 80. En effet, la borne de sécurité 1/2b devrait être remplacée par 1/2e dans le théorème 4 de l'article OTM. Par ailleurs, le paramètre a, qui définit la borne 2s/2a du théorème 5 concernant l'absence de transfert de connaissance dans l'article OTM, devrait être élevé jusqu'à k+80, car la borne 2s/2a concerne une seule exécution du procédé et devrait donc être multipliée 5 par le nombre de signatures ou d'authentifications autorisées. Dans ces conditions, l'opération de terminaison de signature dans le procédé OTM comprend la réduction modulaire d'un nombre de 320 bits par un nombre de 160 bits. D'après les performances des fonctions de réduction modulaire décrites par A. Bosselaers et ai. "Comparison of three 10 modular réduction fonctions ", Proceedings of Crypto 93, Lecture Notes in Computer Science 773, Springer-Verlag (1994), cette opération est finalement estimée deux fois plus coteuse que l'opération de terminaison de signature dans le procédé GPS, à niveau de sécurité égal. L'opération de vérification de signature du procédé OTM devient 15 également extrêmement coteuse dans ces conditions. L'invention a pour but de fournir des procédés d'authentification et de signature numérique qui offrent, pour un niveau de sécurité donné, des propriétés avantageuses en termes de cot calculatoire, de vitesse d'exécution, notamment pour la terminaison de 20 signature, et de longueur de signature ou de preuve d'authenticité. L'invention vise également à fournir des procédés d'authentification et de signature numérique exécutables par des dispositifs de faible puissance calculatoire, comme les cartes à puce, les radiotéléphones, les assistants numériques personnels et analogues. L'invention vise 25 également à fournir des procédés d'authentification et de signature numérique exécutables par une carte à mémoire. Pour cela, l'invention fournit un procédé d'authentification numérique pour permettre à un système vérifieur B pouvant échanger des données numériques avec un système A d'éprouver l'authenticité 30 dudit système A, dans lequel ledit système A est muni d'une clé publique (n,g) incluant un module entier n vérifiant n=pq, o p et q sont des nombres premiers choisis tels que le problème du logarithme discret dans l'ensemble Zn soit insoluble en pratique, et une base entière g choisie dans le groupe 35 Z,,* de manière à présenter un ordre s qui vérifie gs=l modulo n, ledit système A étant muni de la valeur de l'ordre s en tant que clé secrète associée à ladite clé publique (n,g), ladite clé publique (n,g) étant mise à la disposition du système vérifieur B, caractérisé par le fait que le nombre s est choisi de manière à ne pas être divisible par 2j+ 1 pour au moins un entier j tel que 0 L'invention fournit également un procédé de signature numérique pour permettre à un système vérifieur B pouvant échanger des données numériques avec un système signataire A d'éprouver 35 l'authenticité d'un message de données numériques m échangé avec ledit système signataire A, dans lequel ledit système signataire A est muni d'une clé publique (n,g) incluant un module entier n vérifiant n=pq, o p et q sont des nombres premiers choisis tels que le problème du logarithme discret dans l'ensemble Zn soit insoluble en pratique, et une base entière g choisie 5 dans le groupe Z"'* de manière à présenter un ordre s qui vérifie gs=l modulo n, ledit système signataire A étant muni de la valeur de l'ordre s en tant que clé secrète associée à ladite clé publique (n,g), ladite clé publique (n,g) étant mise à disposition du système vérifieur B, caractérisé par le fait que le nombre s est choisi de manière à ne pas être 10 divisible par 2i ', pour au moins un entier j tel que 0 L'idée directrice de ces procédés est de remplacer 5 l'opération de réduction modulaire prévue dans les procédés OTM par une opération de mise en concordance ou " dovetailing", qui sera décrite plus bas, ou une opération analogue. Un avantage essentiel de ces procédés réside dans le faible cot calculatoire et, de manière surprenante, dans l'aptitude d'une telle opération à être exécutée de 10 manière très efficace au moyen d'un programme d'ordinateur ou à l'aide d'une logique câblée sans processeur. L'étape de terminaison de signature ou de preuve d'authenticité est ainsi rendue plus rapide et mise à la portée de systèmes peu coteux, tels que les cartes à mémoire. Pour un niveau de sécurité donné, les contraintes en terme de longueur des 15 clés sont semblables à celles du procédé OTM, mais le nombre d'opérations requises pour former une signature ou une preuve d'authenticité est plus petit, et même inférieur à celui du procédé GPS. Enfin, le procédé selon l'invention permet d'obtenir des signatures numériques plus courtes que les procédés connus OTM et GPS. Au sens de l'invention, un système désigne un système de traitement de données muni de moyens de calcul, programmables ou non, de moyens de mémorisation et d'une interface de communication pour échanger des données. Toute personne voulant appliquer un procédé de signature ou d'authentification numérique, en tant que 25 signataire/fournisseur de preuve ou en tant que destinataire/vérifieur, doit évidemment utiliser un tel système. On assimile donc l'entité signataire, par exemple une personne physique ou morale, et l'entité destinataire, par exemple une personne physique ou morale, aux systèmes qu'elles utilisent, désignés respectivement par les expressions " système 30 signataire A " et " système vérifieur B. " Au sens de l'invention, un nombre entier est un nombre qui peut être représenté de manière exacte sous une forme binaire. Dans la représentation binaire des nombres entiers, on rappelle que le poids d'un bit est l'entier i tel que ledit bit représente l'entier 2'. En d'autres termes, 35 un bit présente un poids plus fort qu'un autre bit s'il représente un nombre entier plus grand que cet autre bit. Il existe plusieurs conventions pour la représentation binaire des entiers, par exemple quant à l'écriture de gauche à droite ou de droite à gauche, et quant à la manière de représenter le signe. Les procédés selon l'invention s'appliquent quelle que soit la convention choisie. Selon une réalisation particulière de l'invention, la signature numérique transmise par le système signataire A au système vérifieur B est constituée uniquement du nombre y, et le système vérifieur B calcule le nombre x' à partir du nombre y reçu et de la clé publique-(n,g) de manière que x'=gY modulo n. Selon une autre réalisation particulière de l'invention, la signature numérique transmise par le système signataire A au système vérifieur B comprend également le nombre x, lequel est reçu par le système vérifieur B en tant que nombre x', et le système vérifieur B calcule le nombre z=gy modulo n et le compare au nombre x' reçu pour 15 reconnaître le message m échangé comme non authentique lorsque z#x'. De préférence, dans le procédé d'authentification ou dans le procédé de signature numérique, ladite portion prédéterminée est constituée des f bits consécutifs ayant des poids i tels que M Avantageusement, dans le procédé d'authentification ou 20 dans le procédé de signature numérique, l'ordre s est choisi tel que O ú+M, de préférence k>2t+M. Avantageusement, le nombre r est choisi tel que O Avantageusement, le nombre e est calculé tel que O De préférence, dans le procédé d'authentification ou dans le procédé de signature numérique, le système vérifieur B compare le nombre y reçu à une borne supérieure S vérifiant S=2a+2k+t+M pour reconnaître le message m échangé, respectivement l'identité du système 30 A, comme non authentique lorsque y>S, le message m échangé, respectivement l'identité du système A, étant reconnu comme authentique par le système vérifieur B sous la condition supplémentaire que y Avantageusement, les paramètres , a et k vérifient a=4C et k=2C. Ces valeurs offrent un compromis optimal entre, d'une part, la 5 sécurité des procédés selon l'invention et, d'autre part, leur cot calculatoire et la compacité des données échangées. De préférence, le système A calcule le nombre y par un procédé itératif comprenant les étapes consistant à: (EO) choisir initialement une variable de résultat y égale au nombre r et 10 un incrément s' égal au nombre 2M-*sj: (El) effectuer un test d'égalité entre deux bits e1 et yi ayant le même poids dans les représentations binaires respectives du nombre e et de la variable de résultat y, en commençant par les bits de poids M, (E2) ajouter ou non ledit incrément s' à la variable de résultat y, en 15 fonction d'un résultat dudit test d'égalité, (E3) recalculer l'incrément s' en décalant sa représentation binaire d'un nombre positif de positions dans le sens des poids de bit croissants (E4) recommencer les étapes (El) à (E3) pour des bits de poids supérieur dans les représentations binaires du nombre e et de la variable de résultat 20 y, jusqu'à atteindre les bits de poids i+M. De cette manière, il n'est pas nécessaire de déterminer explicitement le nombre S. Selon un mode de réalisation particulier de l'invention: dans l'étape (E2), on ajoute l'incrément s' à la variable de résultat y si les bits e, et yI comparés dans l'étape (El) sont inégaux et on ne modifie 25 pas la variable de résultat y si les bits ei et y; comparés dans l'étape (El) sont égaux, dans l'étape (E3), on décale à chaque itération la représentation binaire de l'incrément s' d'une position dans le sens des poids de bit croissants, dans l'étape (E4), on recommence les étapes (El) à (E3) pour les deux bits de poids immédiatement supérieur dans les représentations binaires du nombre e et du nombre y. Selon un mode de réalisation particulier de l'invention, ladite transformation non inversible T comporte au moins la formation 35 d'un nombre entier w dépendant du message m et du nombre x, le calcul de l'image dudit nombre w par une fonction de hachage cryptographique H prenant des valeurs entre 0 et 2h avec h>E+M, et une opération de troncature à C+M bits d'un résultat de ladite fonction de hachage cryptographique H. Les nombres e et e' vérifient ainsi O L'invention fournit également un système signataire 10 convenant pour la mise en oeuvre du procédé de signature numérique susmentionné, caractérisé par le fait qu'il consiste en un circuit logique imprimé incluant: un premier registre de mémoire et un deuxième registre de mémoire pour stocker respectivement un nombre e et un nombre r, un troisième registre de mémoire pour stocker un nombre s, un comparateur de bits ayant deux entrées reliées respectivement au premier registre de mémoire et au deuxième registre de mémoire pour comparer deux à deux des bits de même poids dans lesdits registres de mémoire, un multiplexeur ayant deux entrées de données reliées respectivement audit troisième registre de mémoire et à un registre de mémoire stockant une valeur nulle et une ligne de commutation reliée à une sortie dudit comparateur de bits pour sélectionner l'un desdits registres de mémoire en fonction d'un bit de résultat produit par ledit comparateur de bits et 25 pour placer le contenu du registre de mémoire sélectionné dans un registre de sortie dudit multiplexeur, un circuit additionneur ayant deux entrées d'opérandes reliées respectivement audit registre de sortie et audit deuxième registre de mémoire et une sortie reliée audit deuxième registre de mémoire pour 30 sommer un contenu respectif desdits registres et remplacer un contenu dudit deuxième registre de mémoire par un résultat de ladite somme, un composant de décalage pour décaler d'un bit dans le sens des poids croissants un contenu dudit troisième registre de mémoire, et une interface reliée au moins audit deuxième registre de mémoire pour 35 transmettre le contenu dudit registre à un système vérifieur. Un tel circuit peut être réalisé sous la forme d'une carte à mémoire àfaible cot, sans microprocesseur. Le système vérifieur inclut alors un lecteur de carte correspondant, de type connu. L'invention sera mieux comprise, et d'autres buts, détails, 5 caractéristiques et avantages de celle-ci apparaîtront plus clairement au cours de la description suivante de plusieurs modes de réalisation particuliers de l'invention, donnés uniquement à titre illustratif et non limitatif en référence aux dessins annexés. Sur ces dessins: - la figure 1 est une représentation fonctionnelle 10 schématique d'un dispositif pour la mise en oeuvre d'un procédé de signature ou d'authentification numérique selon l'invention, - la figure 2 est une représentation fonctionnelle schématique d'un circuit imprimé convenant pour 15 la mise en oeuvre du procédé de signature numérique selon l'invention. La figure 1 représente de manière très simplifiée un réseau de transport de données R, par exemple l'Internet, par l'intermédiaire duquel communiquent un système A, un système B et un système C. Le 20 système A est utilisé par une entité qui doit prouver son authenticité, c'est-àdire son identité, ou prouver l'authenticité d'un message de données numériques m à une autre entité utilisant le système B. Le système B est utilisé par l'entité devant vérifier l'authenticité du système A ou l'authenticité du message m. Le système C est utilisé par une 25 autorité de certification, c'est-à-dire un tiers à qui tous les utilisateurs font confiance. Phase préliminaire Dans une phase préliminaire, des paramètres de sécurité entiers L, k, a et f sont fixés et connus des systèmes A et B. Leurs 30 valeurs sont choisies en fonction d'un niveau de sécurité souhaité. Par exemple L=1024, a-320, k=160 et f=80 correspondent à un niveau de sécurité reconnu comme satisfaisant à l'heure actuelle. Le système A se procure une paire de clés comportant une clé secrète s et une clé publique (n, g) incluant un module entier n et une 35 base entière g. Ces nombres vérifient les propriétés suivantes O En d'autres termes, n est un entier RSA. g est un élément de l'ensemble Zn*. O s est l'ordre de l'élément g dans le groupe Zn*, c'est-à-dire que gs=1 modulo n. s est choisi impair. Le nombre s doit être connu exclusivement par le système 10 A. La manière la plus sre d'atteindre ce but est d'engendrer la paire de clés dans le système A et de mémoriser la clé secrète s dans une mémoire protégée du système A. Un procédé pour engendrer une telle paire de clés sera décrit plus bas. La clé publique (n,g) du système A est ensuite certifiée par 15 l'autorité de certification possédant le serveur C relié au réseau R. Cette clé est ensuite envoyée au système vérifieur B sous la forme d'un certificat numérique, cet échange pouvant avoir lieu à un instant quelconque avant que le système vérifieur B n'entame les opérations de vérification. Un tel certificat est connu de l'homme du métier et permet 20 au système vérifieur B de vérifier que la clé publique (n,g) appartient au système A. Par exemple, le certificat est formé par l'autorité de certification en concaténant la clé publique (n,g) et des données identifiant de manière discriminante le système A (nom, adresse, etc.) Tout système vérifieur doit bien sr connaître la clé publique de 25 l'autorité de certification pour lire le certificat numérique. Couramment, la clé publique de l'autorité de certification est publiée dans un annuaire accessible à tout utilisateur. Procédé d'authentification numérique Pour que le système B éprouve l'authenticité du système A, 30 ces systèmes effectuent les étapes suivantes: Le système A choisit aléatoirement un nombre entier r tel que 0 2al. Le système A calcule l'entier x vérifiant x=gr modulo n. Le système A transmet le nombre x au système B. Le système B choisit aléatoirement un nombre entier e tel que O Le système B transmet le nombre e au système A en réponse au nombre x. Le système A calcule à partir des nombres entiers s, e et r un nombre entier y vérifiant y=r+Xs, o X est un nombre entier choisi de manière que les représentations binaires respectives des nombrese et y soient identiques sur la portion constituée des t bits ayant les poids les 10 plus faibles, c'est-à-dire les poids i tels que O Le système A transmet le nombre y au système B. Puis le système B effectue les étapes de vérification suivantes. Le système B compare le nombre y reçu à la borne S=2a+2k+E. Si yÄS, le système A est reconnu comme non authentique et le procédé d'authentification se termine par un échec. Cette étape n'est cependant pas obligatoire. Puis le système B compare la portion constituée des f bits 20 ayant les poids les plus faibles de la représentation binaire du nombre y reçu avec le nombre e préalablement choisi. Le système A est reconnu comme non authentique lorsqu'un bit yi ayant un poids i tel que O Puis le système B calcule le nombre entier x'=gy modulo n à partir du nombre y reçu et de la clé publique (n,g) et compare le nombre x' avec le nombre x préalablement reçu. Le système A est reconnu comme non authentique lorsque x'#x et le procédé d'authentification se termine par un échec. Finalement, le système A est reconnu authentique par le système B lorsque x=x'. Si l'étape de comparaison avec la borne S est effectuée, la condition supplémentaire y Procédé de signature numérique Le procédé de signature numérique est dérivé du procédé 35 d'authentification par la technique connue. La phase préliminaire est identique à celle du procédé d'authentification et comporte en outre le choix d'une transformation non inversible T qui sera utilisée par le système signataire A et le système vérifieur B. On suppose que le système A et le système B ont échangé ou vont échanger un message de données numériques m et que le 5 système A doit produire une signature numérique associée au message m. Par exemple, le message m accompagné de la signature est émis par le système A à destination du système B, lequel doit vérifier si le message qu'il reçoit est authentique. Inversement, le message m peut avoir été émis par le système B à destination du système A, lequel doit 10 accuser réception du message au moyen d'une signature numérique. Pour produire la signature, le système signataire A effectue les étapes suivantes: - choisir un nombre entier r tel que O 2. - calculer le nombre entier x=gr modulo n, - calculer un nombre entier e en appliquant la 20 transformation non inversible T au message m et au nombre x, soit e=T(x,m). La transformation T est une fonction à valeurs dans l'intervalle [0, 2c[, c'est-à-dire que l'entier e est représenté sur t bits. - et calculer un nombre entier y vérifiant y=r+Xs, o X. est un nombre entier choisi de manière que, dans la représentation binaire du 25 nombre y, la portion constituée des E bits ayant les poids les plus faibles, c'est-à-dire les poids i tels que 0 Pour éprouver l'authenticité du message m reçu par le système A ou le système B, le système B effectue les étapes de vérification suivantes: comparer le nombre y reçu à la borne S=24+2. Si yÄdS, le message m est reconnu comme non authentique et la vérification se 35 termine par un échec. Cette étape n'est cependant pas obligatoire. - calculer le nombre entier x'=gy modulo n, - calculer le nombre entier e'=T(x',m) à partir du message m reçu ou envoyé par le système B, du nombre x' calculé par le système B et de la transformation non inversible T, - et comparer la portion constituée des t bits ayant les poids 5 les plus faibles de la représentation binaire du nombre y reçu avec le nombre e'. Le message m échangé est reconnu comme non authentique lorsqu'un bit yj ayant un poids i tel que O Finalement, le message m échangé est reconnu comme 1o authentique par le système vérifieur B sous la condition que ej'=yi pour tous les bits de poids i tels que O Dans la transformation non inversible T, on utilise une 15 fonction de hachage cryptographique H, qui est par exemple l'une de celles définies par les standards MD5 et SHA-1, dont le résultat fait h bits, avec h=128, respectivement h=160. Il existe plusieurs manières de construire une transformation T appropriée. Par exemple, on applique la fonction de hachage H à un nombre w obtenu en concaténant le nombre 20 x et le message m, noté w=xllm, et l'on tronque le résultat à f bits, par exemple en gardant les C bits de poids le plus faible du résultat. En variante, on peut aussi calculer H(H(x),m) ou H(mllxllm) ou encore H(H(x),H(m)), etc., et tronquer le résultat à f bits à chaque fois. La troncature peut être effectuée en gardant d'autres bits que ceux ayant le 25 poids le plus faible. A chaque fois, la transformation non inversible T est connue des systèmes A et B et rend impossible de calculer x en partant de e et m. Dans une variante de réalisation, le nombre x est inclus dans la signature numérique transmise par le système A au système B. Dans 30 ce cas, le système vérifieur B compare le nombre x qu'il reçoit au nombre x'=gy modulo n qu'il calcule et il reconnaît le message m comme non authentique lorsque x#&x'. Dans cette variante, le message m échangé est reconnu comme authentique par le système vérifieur B sous la condition supplémentaire x'=x. Toutefois, cette variante présente 35 l'inconvénient d'allonger la signature numérique de L bits, soit par exemple de 1024 bits. De préférence, le calcul du nombre x par le système A est effectué en tâche de fond, dans une étape de pré-traitement, de manière à conserver en mémoire un couple (r,x) disponible pour la prochaine signature ou la prochaine authentification requise. Il est également 5 possible de stocker une réserve de couples (r,x) dans le système A, par exemple comme il est décrit dans le document FR2716058. Dans une variante de réalisation, le calcul du nombre x n'est pas entièrement effectué par le système A, mais est sous-traité, au moins partiellement, par un ou plusieurs système(s) d'assistance avec 10 le(s) quel(s) le système A communique. Cette variante est particulièrement avantageuse lorsque le système A possède une puissance de calcul réduite, par exemple dans le cas d'une carte à puce ou d'un radiotéléphone. De préférence, une telle sous-traitance doit être effectuée sans divulguer le nombre r aux tiers. Le nombre r peut être 15 choisi par le système A ou calculé par le système A à partir d'une pluralité d'antécédents qui sont transmis au système A par le ou les système(s) d'assistance. Pour cela, on peut se référer aux modalités décrites dans la demande de brevet français enregistrée sous le n'02 02596. Sur le plan de la sécurité, la probabilité de contrefaire la preuve d'authenticité ou la signature y sans connaître la clé secrète s est de l'ordre de 2-t et le facteur statistique de transfert de connaissance pour une exécution du procédé d'authentification est contrôlé par 2s/2 -k- . Les valeurs de paramètre susmentionnées offrent donc un 25 niveau de sécurité, mesuré par la probabilité de réussir à être authentifié sans connaître la clé secrète s, de l'ordre de 2-80. Par rapport aux procédés OTM, pour ce même niveau de sécurité, les procédés susmentionnés autorisent l'utilisation d'un nombre e beaucoup plus court, de l'ordre de 80 bits, de sorte que le nombre total de bits échangés 30 est réduit. Avec les valeurs de paramètre susmentionnées, la longueur de la preuve d'authenticité ou de la signature y est de l'ordre de a bits, car a> > k+ f, soit environ 320 bits. Dans le procédé d'authentification, cette longueur peut être encore réduite de t bits en omettant de 35 transmettre les f bits ayant les poids les plus faibles dans le nombre y. Dans ce cas, le système B commence par concaténer la partie du nombre y reçue avec le nombre e, pour reconstituer le nombre y complet. Dans le procédé de signature, il est inutile d'inclure le nombre e dans la signature numérique, puisque le nombre e est déductible de la structure de y, ce qui est également avantageux par rapport au procédé OTM. Si un niveau de sécurité légèrement plus faible est admis, les valeurs a=256, k=128 et t=64 peuvent aussi être adoptées. Ces valeurs sont des exemples jugés raisonnables à l'heure actuelle, mais des valeurs plus. élevées pourraient être nécessaires à l'avenir, compte -tenu de l'accroissement des performances des ordinateurs. Par exemple, il est 10 aussi possible de choisir L=2048 pour accroître la sécurité. Cependant, il en résulte un accroissement du cot des calculs modulo n. Le choix des paramètres de sécurité L, a, k, et t résulte donc forcément d'un compromis entre un niveau de sécurité et un cot calculatoire. Un choix vérifiant a=4 e et k=2- semble toujours avantageux à cet égard. 15 Opération de " dovetailing " Au sens de l'invention, on définit l'opération de mise en concordance ou " dovetailing " de la manière suivante. Soit s un nombre entier impair. Soit e un nombre entier représenté sur t bits. Soit r un nombre entier représenté sur a bits, axe. Le résultat de la mise en 20 concordance ou du " dovetailing " du couple (re) par rapport au nombre s, noté D,(r,e), est égal à la somme du nombre r et d'un petit multiple du nombre s, somme dans laquelle les t bits de point le plus faible concident avec le nombre e. Cette opération est utilisée dans le procédé d'authentification et le procédé de signature numérique décrits ci-dessus, 25 pour calculer le nombre y=D,(r,e). Une manière d'effectuer cette opération est de déterminer d'abord une valeur correcte du nombre S. Il existe une unique solution modulo t, à savoir 1=(e-r)s-' modulo t. Toutefois, il existe des algorithmes permettant d'effectuer 30 cette opération de manière plus efficace, sans nécessairement déterminer explicitement le nombre S. L'annexe 1 décrit un algorithme itératif simple dans un langage informatique simplifié. La notation s"1 signifie que la représentation binaire du nombre s est décalée d'une position dans le sens des poids de bits croissants, c'est-à-dire que le nombre s est 35 multiplié par 2. Cet algorithme nécessite en moyenne t/2 additions d'un nombre de k bits à un nombre d'environ a bits. Si l'on néglige les quelques additions supplémentaires dues à la propagation de la retenue dans certains cas pathologiques, le nombre d'additions à 8 bits est le même que dans le procédé GPS. Comme il est presque aussi rapide de soustraire deux entiers 5 que de les ajouter, le temps d'exécution de l'opération peut être encore réduit en optimisant " à la volée ", à chaque itération, le nombre de bits du résultat intermédiaire r qui sont rendus égaux aux bits correspondants de e. L'annexe 2 décrit un algorithme itératif correspondant, dans un langage informatique simplifié, convenant pour le cas o s=l modulo 4. 10 Le cas o s=3 modulo 4 se traite de manière similaire. Dans l'algorithme de l'annexe 2, lorsqu'un bit ri du résultat temporaire r concide avec le bit correspondant ei du nombre e, la seule opération est de décaler le nombre s de 1 bit dans le sens des poids de bits croissants. Lorsque ces deux bits ri et es ne concident pas, il se 15 produit une addition ou une soustraction qui fait concider ces deux bits et deux bits supplémentaires, ainsi qu'une opération de décalage du nombre s de 2 bits dans le sens des poids de bits croissants. Ainsi, le nombre moyen d'additions ou de soustractions entre un nombre de a bits et un nombre de k bits permettant d'exécuter complètement l'algorithme 20 est f/3, ce qui signifie que kt/24 additions d'entiers sur 8 bits sont nécessaires, soit environ 540. En comparaison, le procédé GPS nécessite 800 additions d'entiers sur 8 bits. Même s'il est possible d'optimiser de manière similaire l'opération de multiplication du procédé GPS, en introduisant 25 des soustractions dans l'algorithme de multiplication classique, il ne sera pas possible d'atteindre la même efficacité que dans l'opération de " dovetailing ", à cause de l'existence de retenues qui sont inutiles dans l'opération de " dovetailing ". Etape de création des clés Pour engendrer sa paire de clé personnelle, le système A peut procéder de la manière suivante: - choisir au hasard deux nombres premiers p et q représentés chacun sur environ L/2 bits, et tels que les nombres (p-1) et (q-i) soient respectivement divisibles par des facteurs premiers respectifs p' et q' 35 représentés sur environ k/2 bits. De préférence, on impose p>2L/2-1, q2L/2-,1p 2-1 et q'>2 k/2- - choisir n=pq, ainsi (p(n)=(p-1)(q-1), o (p désigne l'indicatrice d'Euler. - choisir s=p'q', ainsi s est forcément impair. Comme s divise (p(n), il existe nécessairement un sous-groupe d'ordre s dans Zn. - choisir au hasard un élément go dans Zn,* et vérifier si ord(go)=p(n), ce qui est probable. Dans la négative, choisir un autre élément go - dans la positive, choisir g=go(p(n)/s* De même que la clé secrète s, les nombres p et q ne doivent 10 être connus que par le système A. Le système A peut stocker les nombres p et q dans une mémoire protégée, par exemple pour pouvoir optimiser le calcul du nombre x par la technique des restes chinois. En variante, le système A peut aussi effacer les nombres p et q après la création des clés (n, g) et s. Il existe aussi d'autres techniques permettant de générer un triplet (n,g, s) convenable. De préférence, on impose s>2k-i. Par ailleurs, si l'on utilise une technique qui ne permet pas d'obtenir toujours un nombre s impair, il est possible d'affaiblir cette contrainte en modifiant très légèrement le procédé de signature et le procédé d'authentification 20 décrits ci-dessus. Un mode de réalisation correspondant à ce cas est décrit ci-dessous. Mode de réalisation avec M>O Par rapport aux modes de réalisation cidessus, on ajoute un paramètre entier M>0 qui est fixé et connu des systèmes A et B. Au lieu 25 d'être impair, on exige seulement que le nombre s ne soit pas divisible par 2j+1, pour au moins un entier j tel que Oj Les procédés décrits plus haut sont modifiés de la manière suivante. Les nombres e et e' sont représentés sur E+M bits et l'on 30 choisit a.>+M. Dans le calcul du nombre y, le système A effectue une opération de mise en concordance modifiée, par laquelle ce sont les bits du nombre y ayant un poids i tel que M Dans l'étape de vérification du nombre y, le système vérifieur B effectue alors la comparaison des nombres y et e sur la portion constituée des bits de poids i tel que M Cette variante présente l'avantage de donner aux tiers moins d'informations sur le nombre s. Mais cet avantage est compensé par un inconvénient, qui est l'accroissement de la longueur des nombres y et e. Mode de réalisation avec bits non consécutifs Avec M=O ou M>O, il est également possible de modifier 15 l'opération de mise en concordance ou " dovetailing " pour faire concider les représentations binaires des nombres e et y sur une portion constituée de f bits non consécutifs. Pour cela, en plus du paramètre Y, les systèmes A et B doivent connaître un lot prédéterminé de t poids distincts supérieurs ou égaux à M. Le poids le plus élevé du lot est alors 20 forcément supérieur ou égal à M+L. Les nombres e et e' doivent être allongés de manière correspondante, pour présenter des bits ayant le poids le plus élevé du lot prédéterminé. Les opérations de calcul du nombre y par le système A et de vérification du nombre y par le système B sont modifiées de manière correspondante, pour respectivement créer 25 et vérifier la concordance des bits du nombre y et du nombre e pour chaque poids i du lot prédéterminé. Pour le calcul du nombre y, il faut alors modifier l'algorithme de l'annexe 1 pour faire balayer par l'indice i tout le lot prédéterminé, toujours en progressant vers les poids de bits croissants, et 30 pour décaler à chaque fois l'incrément s d'un nombre de positions correspondant à l'écart entre deux poids successifs dans le lot prédéterminé. Implantation matérielle Les différents modes de réalisation de procédés décrits 35 peuvent être mis en oeuvre de manière automatisée par une programmation correspondante des systèmes A et B. La réalisation d'une telle programmation relève des compétences de l'homme du métier. Par exemple, les valeurs des paramètres L, k, a, E et M ainsi que le choix de la transformation non inversible T sont fixés dans la programmation des systèmes A et B. En variante, ces valeurs et ce choix peuvent être communiquées aux systèmes A et B par l'autorité de certification. Cependant, l'opération de " dovetailing " peut aussi être exécutée de manière efficace par une logique câblée. En référence à l'algorithme de l'annexe 1, une telle logique câblée est réalisée en suivant, pour effectuer chaque itération de la boucle, les principes 10 généraux suivants: - les bits des nombres r et e sont comparés pour déterminer s'il faut ajouter 0 ou s au nombre r. - les additions sont réalisées au moyen d'additionneurs à trois entrées d'une taille donnée, par exemple 8 bits. - Chaque addition entre r et s est effectuée en parallèle sur tous les d'additionneurs à trois entrées de taille 8 bits, mais les retenues ne sont propagées qu'une seule fois entre les additionneurs à trois entrées. Les retenues qui subsistent sont réintroduites dans les additionneurs à trois entrées lors de l'itération suivante. Ceci est rendu 20 possible par le fait que, lorsque l'on effectue l'itération de rang i dans la boucle, il suffit que le bit de poids i soit correct dans le nombre r. Les calculs restant pour terminer les additions peuvent donc être différés jusqu'à l'itération suivante. - le nombre s est décalé d'une position à l'aide d'un 25 composant classique. Du fait que les retenues ne se propagent qu'une seule fois à chaque itération, chaque addition entre les nombres r et s ne demande que deux cycles d'horloge. La propagation des retenues restantes ne doit être effectuée qu'une seule fois après la boucle principale " while-end 30 while ". En fait, lorsqu'on utilise des additionneurs de taille 8 bits, il est nécessaire d'effectuer l'étape de propagation des retenues restantes qu'une fois tous les 8 cycles d'horloge. On obtient quand même la valeur correcte de r à la fin du calcul. De ce fait, au prix d'un algorithme d'horloge plus complexe, il doit être possible d'effectuer l'opération de 35 " dovetailing " à l'aide d'une logique câblée sensiblement au même cot que l'opération de multiplication du procédé GPS. La figure 2 représente schématiquement un mode de réalisation du système signataire A, réalisé sous la forme d'un circuit imprimé en suivant les principes susmentionnés. Un premier registre 1 sert à stocker le nombre e. Un second registre 2 sert à stocker le nombre 5 r. Les registres 1 et 2 sont reliés à un comparateur de bits 3 servant à comparer les bits de poids i dans les registres 1 et 2. La sortie du comparateur de bits 3 transmet un bit de résultat 0 ou. 1 sur la ligne de commutation 11 d'un multiplexeur Mux ayant deux entrées, pour sélectionner l'une de ces deux entrées. La première entrée est reliée à un 10 registre 4 servant à stocker le nombre s et la seconde entrée est reliée à un registre 5 stockant le nombre 0. En fonction du bit de résultat sortant du comparateur de bits 3, le registre de sortie 6 du multiplexeur Mux reçoit le nombre s ou 0. Le circuit additionneur 7 est constitué d'une série d'additionneurs à trois entrées dont les branchements relatifs à la 15 propagation des retenues ne sont pas représentés. Les deux entrées d'opérandes du circuit additionneur 7 sont reliées respectivement aux registres 2 et 6. La sortie circuit additionneur 7 est reliée au registre 2 pour remplacer le contenu du registre 2 par le résultat de l'addition. Comme mentionné ci-dessus, ce résultat peut être plus ou moins achevé 20 quant à ses bits de poids fort, selon la manière dont les retenues sont propagées à chaque itération. Le composant de décalage 8 sert à décaler d'un bit le contenu du registre 4 à chaque itération. Après le calcul du nombre y, qui remplace le nombre r dans le registre 2 à la fin de la boucle principale, le contenu du registre 4 est réinitialisé à la valeur s par 25 des opérations de décalage appropriées ou en chargeant le nombre s à partir d'une mémoire permanente 12. Il est également prévu une interface 10 reliée au registre 2 pour transmettre le contenu final de ce registre, à savoir la signature numérique, au système vérifieur B. Le calcul du nombre e placé dans le registre 1 est effectué 30 par un circuit imprimé connu en soi réalisant le hachage de deux opérandes, à savoir le nombre x et le message m, qui sont stockées dans des registres de mémoire correspondants, non représentés. Un tel circuit imprimé est placé dans un support pour former une carte à mémoire de format classique. L'interface 10 comporte des 35 contacts électriques pour coopérer avec la tête de lecture d'un lecteur de carte correspondant, pouvant par exemple être inclus dans le système vérifieur B. Selon un mode de réalisation particulièrement simple, une pluralité de couples de nombres (r, x) sont chargées à l'avance dans les registres de mémoire de la carte pour pouvoir effectuer un nombre correspondant de signatures. s Bien que l'invention ait été décrite en liaison avec plusieurs modes de réalisation particuliers, il est bien évident qu'elle n'y est nullement limitée et qu'elle comprend tous les équivalents techniques des moyensdécrits ainsi que leurs combinaisons si celles-ci entrent dans le.-cadre de l'invention. Annexe 1: algorithme de " dovetailing " sur un bit Entrées r, e, s Sorties Ds(r,e) remplace r i REVENDICATIONS 1. Procédé de signature numérique pour permettre à un système vérifieur B pouvant échanger des données numériques avec un système signataire A d'éprouver l'authenticité d'un message de données numériques m échangé avec ledit système signataire A, dans lequel ledit système signataire A est muni d'une clé publique (n,g) incluant un module entier n vérifiant n=pq, o p et q sont des nombres premiers choisis tels que le problème du logarithme; discret dans l'ensemble Zn soit insoluble en pratique, et une base entière g choisie 10 dans le groupe Zn* de manière à présenter un ordre s qui vérifie gs=1 modulo n, ledit système signataire A étant muni de la valeur de l'ordre s en tant que clé secrète associée à ladite clé publique (n,g), ladite clé publique (n,g) étant mise à disposition du système vérifieur B, caractérisé par le fait que le nombre s est choisi de manière à ne pas être 15 divisible par 2i+', pour au moins un entier j tel que 05j 2. Procédé selon la revendication 1, caractérisé par le fait que la signature numérique transmise par le système signataire A au système vérifieur B est constituée uniquement du nombre y, et que le système vérifieur B calcule le nombre x' à partir du nombre y reçu et de la clé publique (n,g) de manière que x'=gy modulo n. 3. Procédé selon la revendication 1, caractérisé par le fait que la signature numérique transmise par le système signataire A au système vérifieur B comprend également le nombre x, lequel est reçu par le système vérifieur B en tant que nombre x', et que ledit système vérifieur B calcule le nombre z=gy modulo n et le compare au nombre x' 20 reçu pour reconnaître le message m échangé comme non authentique lorsque z#x'. 4. Procédé selon l'une des revendications 1 à 3, caractérisé par le fait que ladite portion prédéterminée est constituée des t bits consécutifs ayant des poids i tels que M 5. Procédé selon la revendication 4, caractérisé par le fait que l'ordre s est choisi tel que 0 t+M, que le nombre r est choisi tel que O k+t+M, et que le nombre e est calculé tel que O 6. Procédé selon la revendication 5, caractérisé par le fait que le système vérifieur B compare le nombre y reçu à une borne supérieure S vérifiant S=2a+2k+t+M pour reconnaître le message m échangé comme non authentique lorsque y>S, le message m échangé étant reconnu comme authentique par le système vérifieur B sous la 35 condition supplémentaire que y 7. Procédé selon la revendication 5 ou 6, caractérisé par le fait que les paramètres ô, a et k vérifient a=4f et k=2f. 8. Procédé selon l'une des revendications 4 à 7, caractérisé par le fait que le système signataire A calcule le nombre y par un procédé itératif comprenant les étapes consistant à: (E0) choisir initialement une variable de résultat y égale au nombre r et un incrément s' égal au nombre 2M-is: (El) effectuer un test d'égalité entre deux bits ei et yi ayant le même poids dans les représentations binaires respectives du nombre e et de la 10 variable de résultat y, en commençant par les bits de poids M, (E2) ajouter ou non ledit incrément s' à la variable de résultat y, en fonction d'un résultat dudit test d'égalité, (E3) recalculer l'incrément s' en décalant sa représentation binaire d'un nombre positif de positions dans le sens des poids de bit croissants (E4) recommencer les étapes (El) à (E3) pour des bits de poids supérieur dans les représentations binaires du nombre e et de la variable de résultat y, jusqu'à atteindre les bits de poids &+M. 9. Procédé selon la revendication 8, caractérisé par le fait que: dans l'étape (E2), on ajoute l'incrément s' à la variable de résultat y si les bits ei et yi comparés dans l'étape (El) sont inégaux et on ne modifie pas la variable de résultat y si les bits ei et y; comparés dans l'étape (El) sont égaux, dans l'étape (E3), on décale à chaque itération la représentation binaire 25 de l'incrément s' d'une position dans le sens des poids de bit croissants, dans l'étape (E4), on recommence les étapes (El) à (E3) pour les deux bits de poids immédiatement supérieur dans les représentations binaires du nombre e et du nombre y. 10. Procédé selon l'une des revendications 1 à 9, caractérisé par le fait que M=O. 11. Procédé d'authentification numérique pour permettre à un système vérifieur B pouvant échanger des données numériques avec un système A d'éprouver l'authenticité dudit système A, dans lequel ledit système A est muni d'une clé publique (n,g) incluant un module entier n vérifiant n=pq, o p et q sont des nombres premiers choisis tels que le problème du logarithme discret dans l'ensemble Zn, soit insoluble en pratique, et une base entière g choisie dans le groupe Zn* de manière à présenter un ordre s qui vérifie gS=l modulo n, ledit système A étant muni de la valeur de l'ordre s en tant que clé secrète 5 associée à ladite clé publique (n,g), ladite clé publique (n,g) étant mise à la disposition du système vérifieur B, caractérisé par le fait que le nombre s est choisi de manière à ne pas être divisible par 2J+, pour au moins un entier j tel que 0 12. Procédé selon la revendication 11, caractérisé par le fait que ladite portion prédéterminée est constituée des bits consécutifs ayant des poids i tels que M 13. Procédé selon la revendication 12, caractérisé par le 5 fait que l'ordre s est choisi tel que O t+M, que le nombre r est choisi tel que O k+E+M, et que le nombre e est choisi tel que O 14. Procédé selon la revendication 13, caractérisé par le 10 fait que le système vérifieur B compare le nombre y reçu à une borne supérieure S vérifiant S=2a+2k+e+m pour reconnaître le système A comme non authentique lorsque y>S, le système A étant reconnu comme authentique par le système vérifieur B sous la condition supplémentaire que y 15. Procédé selon la revendication 13 ou 14, caractérisé par le fait que les paramètres f, a et k vérifient a=4f et k=2ú. 16. Procédé selon l'une des revendications 12 à 15, caractérisé par le fait que le système A calcule le nombre y par un procédé itératif comprenant les étapes consistant à: (EO) choisir initialement une variable de résultat y égale au nombre r et un incrément s' égal au nombre 2M-sj: (El) effectuer un test d'égalité entre deux bits e, et y; ayant le même poids dans les représentations binaires respectives du nombre e et de la variable de résultat y, en commençant par les bits de poids M, (E2) ajouter ou non ledit incrément s' à la variable de résultat y, en fonction d'un résultat dudit test d'égalité, (E3) recalculer l'incrément s' en décalant sa représentation binaire d'un nombre positif de positions dans le sens des poids de bit croissants (E4) recommencer les étapes (El) à (E3) pour des bits de poids supérieur 30 dans les représentations binaires du nombre e et de la variable de résultat y, jusqu'à atteindre les bits de poids ú+M. 17. Procédé selon la revendication 16, caractérisé par le fait que: dans l'étape (E2), on ajoute l'incrément s' à la variable de résultat y si 35 les bits e1 et yi comparés dans l'étape (El) sont inégaux et on ne modifie pas la variable de résultat y si les bits ei et yi comparés dans l'étape (El) sont égaux, dans l'étape (E3), on décale à chaque itération la représentation binaire de l'incrément s' d'une position dans le sens des poids de bit croissants, dans l'étape (E4), on recommence les étapes (El) à (E3) pour les deux 5 bits de poids immédiatement supérieur dans les représentations binaires du nombre e et du nombre y. 18. Système signataire (A) pour la mise en oeuvre du procédé selon la revendication 1, caractérisé par le fait qu'il consiste en un circuit logique imprimé incluant: un premier registre de mémoire (1) et un deuxième registre de mémoire (2) pour stocker respectivement un nombre e et un nombre r, un troisième registre de mémoire (4) pour stocker un nombre s, un comparateur de bits (3) ayant deux entrées reliées respectivement au premier registre de mémoire (1) et au deuxième registre de mémoire (2) 15 pour comparer deux à deux des bits de même poids dans lesdits registres de mémoire, un multiplexeur (Mux) ayant deux entrées de données reliées respectivement audit troisième registre de mémoire (4) et à un registre de mémoire (5) stockant une valeur nulle et une ligne de commutation (11) 20 reliée à une sortie dudit comparateur de bits (3) pour sélectionner l'un desdits registres de mémoire (4, 5) en fonction d'un bit de résultat produit par ledit comparateur de bits (3) et pour placer le contenu du registre de mémoire sélectionné dans un registre de sortie (6) dudit multiplexeur, un circuit additionneur (7) ayant deux entrées d'opérandes reliées respectivement audit registre de sortie (6) et audit deuxième registre de mémoire (2) et une sortie reliée audit deuxième registre de mémoire (2) pour sommer un contenu respectif desdits registres (2, 6) et remplacer un contenu dudit deuxième registre de mémoire (2) par un résultat de ladite 30 somme, un composant de décalage (8) pour décaler d'un bit dans le sens des poids croissants un contenu dudit troisième registre de mémoire (4), une interface (10) reliée audit deuxième registre de mémoire (2) pour transmettre le contenu dudit registre à un système vérifieur (B).