Brevet FR2867580A1 — publié le 20050916

FR 2867580 A1 20050916 FR 0403488 D 20040402 La présente invention concerne un système cryptographique à clé publique, et plus particulièrement un multiplieur modulaire du type Montgomery. Des systèmes cryptographiques sont utilisés dans des communications effectuées au moyen de cartes à microprocesseur, de cartes à circuit intégré, et autres, et ont été développés en passant de systèmes cryptographiques à clé secrète à des systèmes cryptographiques à clé publique. Dans un système cryptographique à clé secrète, deux utilisateurs doivent partager une clé secrète identique pour communiquer l'un avec l'autre. Par conséquent, la gestion de clés et la signature numérique qui sont basées sur un système cryptographique à clé secrète sont difficiles. D'autre part, dans un système cryptographique à clé publique, chaque utilisateur conserve une clé secrète, et tout utilisateur qui. connaît la clé publique d'un autre participant peut communiquer avec celui-ci, ce qui facilite un processus pour accomplir commodément des communications secrètes. Des exemples d'un système cryptographique à clé publique comprennent les suivants: Ron Rivest, Adi Shamir et Len Adleman (RSA), Diffie-Hellman, un algorithme de signature numérique ou DSA (Digital Signature Algorithm), un cryptosystème à courbe elliptique ou ECC (Elliptic Curve Cryptosystem), et autres. Du fait qu'un système cryptographique à clé publique effectue une multiplication modulaire pour accomplir une opération d'exponentiation modulaire, le système doit adopter un multiplieur modulaire. Un algorithme de multiplication modulaire de Montgomery, connu comme étant l'algorithme de multiplication modulaire le plus efficace, peut être exprimé en pseudo-code sous la forme de l'Algorithme 1 ci-dessous. [Algorithme 1] Stimulus: A = (an_i an_2... a1 ap) 2, et A Réponse: S = (Sn Sn-1 S n-2 S1 S0) 2 = ABR-1 (mod M) Méthode S: = 0 For i = 0 to n-1 do qi: = sp OU-EX (bi ET a0) S: = (S + biA + qiM) /2 endfor Ainsi, dans l'algorithme 1, un terme S (somme) final (dans l'Algorithme 1, le report est exprimé par Sn) qui est calculé dans une boucle "for" est congru à ABR-1 (mod M). Ici, "R-1" est un nombre inverse de R dans la multiplication modulaire "mod M". Lorsque R est égal à 2n, "(R*R-1)mod M" est égal à 1. L'algorithme de multiplication modulaire de Montgomery effectue seulement des multiplications sur des nombres donnés A, B et M, sans utiliser de divisions, et est plus rapide que d'autres algorithmes. Par conséquent, l'algorithme de multiplication modulaire de Montgomery est largement utilisé dans la réalisation de systèmes cryptographiques à clé publique qui exigent une opération d'exponentiation modulaire. Des multiplieurs modulaires de Montgomery classiques basés sur un algorithme de multiplication modulaire de Montgomery sont classés comme un multiplieur parallèle, qui utilise un additionneur à propagation de report comme un accumulateur de base, ou comme un multiplieur série, qui utilise un compression 3-2 (3 entrées à 2 sorties) (c'est-à-dire un additionneur sans propagation de report constitué d'additionneurs complets) comme un accumulateur de base. Un additionneur à propagation de report exige un temps de retard de propagation de report sur la base de chaque cycle d'horloge, pour la propagation d'un report à chaque addition de multiples bits. Du fait que l'additionneur à propagation de report ne peut pas augmenter sans limite le temps de retard de propagation de report, la multiplication de nombres représentés par 32 bits est difficile. En d'autres termes, l'additionneur à propagation de report a un produit puissance-retard qui est plus grand que dans un additionneur sans propagation de report. La multiplication d'un nombre à 32 bits par un nombre à 32 bits doit être répétée pour effectuer une multiplication de nombres représentés par 32 bits ou plus. Du fait qu'un multiplieur série qui utilise un additionneur sans propagation de report utilise un compresseur 3-2 (c'est-à-dire des additionneurs complets), il n'y a pas de problèmes d'un temps de retard de propagation, mais le multiplieur série avec l'additionneur à propagation de report ne peut pas être réalisé aisément par matériel. Le compresseur 3-2 supprime le temps de retard de propagation en effectuant toutes les additions sur chaque bit pour un nombre d'impulsions d'horloge égal au nombre de bits. En d'autres termes, dans un algorithme de multiplication modulaire de Montgomery tel que l'Algorithme 1, il est nécessaire de sommer les quatre mots: report, S, biA et qiM. Cependant, le compresseur 3-2 ne peut recevoir que 3 mots, et par conséquent il apparaît un problème consistant en ce que les deux mots d'entrée principaux biA et qiM doivent être sommés à l'avance. De plus, lorsque le compresseur 3-2 effectue une addition, il doit recevoir: report, S et l'un des quatre mots (c'est-à-dire report, S, biA et qiM) et par conséquent, il exige un multiplexeur 4:1 pour sélectionner l'un des quatre mots. Des modes de réalisation de la présente invention procurent un multiplieur modulaire de Montgomery qui supprime et/ou réduit le temps de retard de propagation en utilisant une structure d'additionneur sans propagation de report (ou CSA pour "Carry Save Adder"), dans laquelle toutes les additions exigées pour chaque bit sont effectuées sur quatre mots (par exemple, report, S, biA et qiM), et des additions dans une structure d'additionneur à propagation de report (ou CPA pour "Carry Propagation Adder") sont effectuées à un étage de sortie, ce qui permet d'obtenir une vitesse de fonctionnement élevée et un produit puissance- retard de faible valeur. Des modes de réalisation de la présente invention procurent également un procédé de multiplication modulaire de Montgomery dans lequel un temps de retard de propagation est supprimé et/ou réduit en utilisant une structure d'additionneur sans propagation de report (CSA), qui effectue toutes les additions exigées pour chaque bit sur quatre mots (par exemple, report, S, biA et q1M), et effectue des additions dans une structure d'additionneur à propagation de report (CPA) dans un étage de sortie, pour parvenir ainsi à une vitesse de fonctionnement élevée et un produit puissance-retard de faible valeur. Un autre exemple de mode de réalisation de la présente invention procure un multiplieur modulaire de Montgomery qui calcule une valeur congrue à "ABR-1" (mod M), dans laquelle A et B sont des nombres d'entrée à n bits, R-1 est un nombre inverse de R en multiplication modulaire "mod M", et M est un modulo. Le multiplieur modulaire de Mongtomery comprend un registre A, un registre B, un registre M, un circuit logique de calcul de biA, un circuit logique de calcul de qi, un circuit logique de calcul de qiM, un compresseur 4-2, un registre S et un registre C. Le registre A stocke une valeur de bit ai (i étant un entier compris dans une plage allant de 0 à n-1) du nombre A, qui est inférieur au modulo M. Le registre B stocke une valeur de bit bi (i étant 35 un entier compris dans une plage allant de 0 à n-1) du nombre B, qui inférieur au modulo M. Le registre M stocke une valeur de bit mi (i étant un entier compris dans une plage allant de 0 à n-1) du modulo M, qui est un nombre impair. Le circuit logique de calcul de biA multiplie le 5 nombre A par une valeur de bit bi pour obtenir chaque bit de biA. Le circuit logique de calcul de qi résout une équation logique booléenne "so OU-EX co OU-EX (bi ET ao)", dans laquelle so est le bit le moins significatif (LSB) d'une somme S, co est le LSB d'un report C, bi est la valeur de bit du nombre B, et ao est le LSB du nombre A, pour obtenir une valeur de bit qi (en désignant par i un entier compris dans la plage de 0 à n-1). Le circuit logique de calcul de qiM multiplie le 15 modulo M par la valeur de bit qi pour obtenir chaque bit de qiM. Dans un exemple de mode de réalisation de la présente invention, le compresseur 4-2 effectue tout d'abord n additions sur le report C, la somme S, le terme biA et le terme qiM, pour obtenir des valeurs intermédiaires pour chaque bit de la somme S et du report C dans une structure d'additionneur sans propagation de report, et fait ensuite la somme des valeurs intermédiaires pour obtenir des résultats finals pour S et C dans une structure d'additionneur à propagation de report, en réponse à un signal d'additionneur à propagation de report. Le registre S actualise une valeur de bit si (i étant un entier compris dans la plage allant de 0 à n-1) de la somme S et stocke la valeur de bit actualisée. Le registre C actualise une valeur de bit si (i étant un entier compris dans la plage allant de 0 à n-1) du report C et stocke la valeur de bit actualisée. Dans un exemple de mode de réalisation de la présente invention, le compresseur 4-2 comprend une première unité d'additionneur complet, une unité de multiplexeurs (MUX), et une seconde unité d'additionneur complet. La première unité d'additionneur complet fait la somme d'une valeur de bit biai du terme biA, d'une valeur de bit si+1 de la somme S et de la valeur de bit ci du report C, pour obtenir un report cAi et une somme sAi. Dans un exemple de mode de réalisation de la présente invention, l'unité de multiplexeurs fournit sélectivement en sortie soit une valeur de bit gimi du terme qiM, le report cAi_1, et la somme sAi, soit la valeur de bit si+1 de la somme S, la valeur de bit ci du report C et la valeur de bit ci_1 du report C, en réponse au signal d'additionneur à propagation de report. La seconde unité d'additionneur complet effectue n additions sur la valeur de bit gimi du terme qiM, le report cAi_1, et la somme sAi, pour calculer des valeurs de bit intermédiaires si et ci de la somme S et du report C, lorsque le signal d'additionneur à propagation de report est dans un état inactif, et fait ensuite la somme de la valeur de bit report C, et si+1 de la somme S, la valeur de bit ci du la valeur de bit ci_1 du report C, pour obtenir des lorsque le est dans un Dans résultats finals de la somme S et du report C, signal d'additionneur à propagation de report état actif. un exemple de mode de réalisation de la présente invention, la structure d'additionneur sans propagation de report est une structure à 4 entrées, 2 sorties, dans laquelle les première et seconde unités d'additionneur complet fonctionnent lorsque le signal d'additionneur à propagation de report est dans un état inactif. Dans un exemple de mode de réalisation de la présente invention, la structure d'additionneur à propagation de sorties, dans d'additionneur d'additionneur actif. report est une structure à 3 entrées, 2 laquelle seule la seconde unité complet fonctionne lorsque le signal à propagation de report est dans un état Le LSB du report cAi_1 et le LSB du report ci_1 sont dans un premier état logique. Le bit le plus significatif, ou MSB, de la somme sil' est égal au report cAn_1 une impulsion d'horloge avant 5 que le signal d'additionneur à propagation de report soit activé. Un autre exemple de mode de réalisation de la présente invention procure un procédé pour accomplir une multiplication modulaire de Montgomery dans un multiplieur modulaire de Montgomery, qui comprend des registres pour stocker des valeurs de bit ai, bi, mi, ci et si (dans lesquelles i désigne un entier compris dans la plage de 0 à n-1) respectivement d'un mot A, un mot B, un modulo M, un report C et une somme S, et calcule une valeur congrue à "ABR-1i (mod M), dans laquelle A et B sont des nombres à n bits d'entrée, R-1 est un nombre inverse de R en multiplication modulaire "mod M", et M est un modulo. Dans le procédé, le nombre A, le nombre B et le modulo M sont reçus. Le nombre A est multiplié par une valeur de bit bi pour obtenir chaque bit de biA. Une équation logique booléenne "s0 OU-EX co OU- EX (bi ET ao) ", dans laquelle sp est le bit le moins significatif (LSB) d'une somme S, co est le LSB d'un report C, bi est la valeur de bit du nombre B, et ap est le LSB du nombre A, est obtenue pour obtenir une valeur de bit qi (en désignant par i un entier compris dans la plage de 0 à n-1). Le nombre M est multiplié par la valeur de bit qi pour obtenir chaque bit de qiM. Ensuite, n additions sont effectuées sur le report C, la somme S, le terme biA et le terme qiM, pour obtenir des valeurs intermédiaires pour chaque bit de la somme S et du report C dans une structure d'additionneur sans propagation de report, en réponse à un signal d'additionneur à propagation de report. Les valeurs intermédiaires sont sommées pour obtenir les résultats finals de la somme S et du report C dans une structure d'additionneur à propagation de report, en réponse au signal d'additionneur à propagation de report. Dans un exemple de mode de réalisation, le nombre A est inférieur au modulo M. Dans un exemple de mode de réalisation, le nombre B est inférieur au modulo M. Dans un exemple de mode de réalisation, le modulo M est un nombre impair. Dans un exemple de mode de réalisation, les valeurs intermédiaire et finale de la somme S et les valeurs intermédiaire et finale du report C sont calculées de la façon suivante: on fait la somme d'une valeur de bit biAi du terme biA, d'une valeur de bit si+1 de la somme S, et de la valeur de bit ci du report C, pour obtenir un report cAi et une somme sAi; on fournit sélectivement en sortie soit une valeur de bit giMi du terme qiM, le report cAi_1, et la somme sAi, soit la valeur de bit si+1 de la somme S, la valeur de bit ci du report C, et une valeur de bit ci_1 du report C, en réponse au signal d'additionneur à propagation de report; on effectue n additions sur la valeur de bit gimi du terme qiM, le report cAi_1, et la somme sAi pour calculer des valeurs de bit intermédiaires si et ci de la somme S et du report C, lorsque le signal d'additionneur à propagation de report est dans un état inactif; et fait la somme de la valeur de bit si+1 de la somme S, de la valeur de bit ci du report C, et de la valeur de bit ci_1 du report C, pour obtenir des résultats finals de la somme S et du report C, lorsque le signal d'additionneur à propagation de report est dans un état actif. Dans un exemple de mode de réalisation, la structure d'additionneur sans propagation de report est une structure à 4 entrées, 2 sorties, dans laquelle les valeurs intermédiaires de la somme S et du report C sont obtenues à partir de biA et qiM lorsque le signal d'additionneur à propagation de report est dans un état inactif. Cependant, l'additionneur sans propagation de report peut avoir une multiplicité de structures d'entrées et de sorties. La structure d'additionneur à propagation de report est une structure à 3 entrées, 2 sorties dans laquelle les valeurs finales de la somme S et du report C sont obtenues à partir des valeurs intermédiaires de la somme S et du report C lorsque le signal d'additionneur à propagation de report est dans un état actif. Cependant, l'additionneur à propagation de report peut avoir une multiplicité de structures d'entrées et de sorties. Le LSB du report cAi_1 et le LSB du report ci_1 sont 10 dans un premier état logique. La valeur du MSB de la somme si+1 est égale à la valeur de bit cAn_1 une impulsion d'horloge avant que le signal d'additionneur à propagation de report soit activé. D'autres caractéristiques et avantages de l'invention seront mieux compris à la lecture de la description détaillée qui va suivre d'un mode de réalisation, donné à titre d'exemple non limitatif. La suite de la description se réfère aux dessins annexés, dans lesquels: la figure 1 est un schéma synoptique d'un multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention; la figure 2 est un schéma synoptique plus détaillé du compresseur 4-2 de la figure 1 et de ses circuits périphériques, dans un exemple de mode de réalisation de la présente invention; la figure 3 est un organigramme pour illustrer le fonctionnement du multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention, dans un exemple de mode de réalisation de la présente invention; la figure 4 est un schéma synoptique pour expliquer le fonctionnement d'un additionneur sans propagation de report dans le multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention, dans un exemple de réalisation de la présente invention; et la figure 5 est un schéma synoptique pour expliquer le fonctionnement d'un additionneur à propagation de report dans le multiplieur modulaire de Montgomery conforme à un exemple de mode de réalisation de la présente invention. En se référant à la figure 1, on note qu'un multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention calcule une valeur congrue à "ABR-1i (mod M). Ici, A et B sont des nombres à n bits d'entrée, et R-1 est le nombre inverse de R en multiplication modulaire "mod M". Pour réaliser ceci, le multiplieur modulaire de Montgomery comprend un registre A 110, un registre B 120, un registre M 120, un circuit logique de calcul de biA 140, un circuit logique de calcul de qi 150, un circuit logique de calcul de qiM 160, un compresseur 4-2 170, un registre S 180 et un registre C 190. Le registre A 110 stocke la valeur de bit ai (i désignant un entier compris dans la plage de 0 à n-1) du nombre A, qui est inférieur au modulo M. Le nombre A désigne un mot représentant un nombre à n bits d'entrée, et ai est la valeur de chacun des bits a0 à an_1 qui constituent le nombre A. Le registre B 120 stocke la valeur de bit bi (i désignant un entier compris dans la plage de 0 à n-1) du nombre B, qui est inférieur au modulo M. Le nombre b désigne un mot représentant un nombre à n bits d'entrée, et bi est la valeur de chacun des bits b0 à bn_1 qui constituent le nombre B. Le registre M 130 stocke la valeur de bit mi (i désignant un entier compris dans la plage de 0 à n-1) du modulo M, qui est un nombre impair. Le modulo M désigne un mot représentant un nombre à n bits d'entrée, et mi est la valeur de chacun des bits m0 à mn_1 qui constituent le modulo M. Le circuit logique de calcul de biA 140 calcule chaque bit de biA en multipliant le nombre A par la valeur de bit bi. Par conséquent, les valeurs des n bits bia0 à bian_1 sont fournies en sortie. A ce moment, du fait que i varie de 0 à n-1 dans la boucle "for" incluse dans l'Algorithme 1, la valeur bi est obtenue à partir de la position du bit le moins significatif (LSB) du registre B 120, qui est décalée d'un bit vers la droite chaque fois qu'un algorithme dans la boucle "for" est accompli, comme représenté sur la figure 1. Le circuit logique de calcul de qi 150 calcule la valeur qi (i désignant un entier compris dans la plage de 0 à n-1) utilisée dans la boucle "for" de l'Algorithme 1, en résolvant l'équation logique booléenne "s0 OU-EX co OU-EX (bi ET a0)". Ici, s0 est le LSB d'une somme S, co est le LSB d'un report C, bi est une valeur de bit du nombre B, et a0 est le LSB du nombre A. A ce moment, du fait que i varie de 0 à n-1 dans la boucle "for" incluse dans l'Algorithme 1, une valeur bi est obtenue partir de la position du LSB du registre B 120, qui est décalée d'un bit vers la droite chaque fois qu'un algorithme dans la boucle "for" est accompli, comme représenté sur la figure 1. Le circuit logique de calcul de qiM 160 calcule chaque bit de qi en multipliant le modulo M par la valeur de bit qi. Par conséquent, les valeurs des n bits gim0 à gimn_1 sont fournies en sortie. A ce moment, du fait que i varie de 0 à n-1 dans la boucle "for" incluse dans l'Algorithme 1, i augmente d'une unité chaque fois qu'un algorithme dans la boucle "for" est accompli, comme représenté sur la figure 1. Par conséquent, les valeurs des n bits q0 à qn_1 sont fournies en sortie. Dans un exemple de mode de réalisation de la présente invention, en réponse à un signal d'additionneur à propagation de report ONCPA, le compresseur 4-2, 170, effectue n additions sur les termes C, S, biA et qiM, pour obtenir des valeurs calculées intermédiaires pour chaque bit des termes S et C, dans une structure d'additionneur sans propagation de report. Ensuite, le compresseur 4-2 170 fait la somme des valeurs calculées intermédiaires pour obtenir les résultats finals pour S et C, dans une structure d'additionneur à propagation de report. Lorsque le signal d'additionneur à propagation de report ONCPA est dans un état inactif, c'est-à-dire dans un premier état logique ("0"), des premiers et seconds additionneurs complets fonctionnent en même temps dans la structure d'additionneur sans propagation de report, pour former ainsi une structure à 4 entrées, 2 sorties. Lorsque le signal d'additionneur à propagation de report ONCPA est dans un état actif, c'est-à-dire qu'il est dans un second état logique ("1"), seulement les seconds additionneurs complets fonctionnent dans la structure d'additionneur à propagation de report, en formant ainsi une structure à 3 entrées, 2 sorties. Le registre S 180 actualise et stocke la valeur de bit si de S (i désignant un entier dans la plage allant de 0 à n-1). En d'autres termes, S désigne un mot représentant un nombre à n bits qui est fourni en sortie en tant que somme, et si désigne la valeur de chacun des bits sp à sn_1 qui constituent le mot S. Le mot S est actualisé chaque fois qu'une addition est effectuée dans l'additionneur sans propagation de report ou dans l'additionneur à propagation de report inclus dans le compresseur 42 170. Le registre C 190 actualise et stocke la valeur de bit ci de C (i désignant un entier dans la plage de 0 à n-1). En d'autres termes, C désigne un mot représentant un nombre à n bits qui est fourni en sortie en tant que report, et ci désigne la valeur de chacun des bits co à cn_ 1 qui constituent le mot C. Le mot C est actualisé chaque fois qu'une addition est effectuée dans l'additionneur sans propagation de report ou dans l'additionneur à propagation de report inclus dans le compresseur 4- 2 170. La figure 2 est un schéma synoptique plus détaillé du compresseur 4-2 170 de la figure 1 et de ses circuits périphériques. En se référant à la figure 2, on note que le compresseur 4-2 170 comprend des première et seconde unités d'additionneurs complets 171 et 175 et une unité de multiplexeurs (MUX) 173, qui forment un additionneur avec une structure à 4 entrées, 2 sorties. Chacun des premiers additionneurs complets de la première unité d'additionneurs complets 171 fait la somme de sa valeur de bit correspondante de biA, de la valeur de bit si+1 de S, et de la valeur de bit ci de C, pour obtenir un report cAi et une somme sAi. La valeur de bit correspondante de biA est biai. Chacun des multiplexeurs dans l'unité de multiplexeurs 173 fournit sélectivement en sortie soit sa valeur de bit correspondante de qiM, le report cAi_1 et la somme sAi, soit la valeur de bit si+1 de S, la valeur de bit ci de C, et la valeur de bit ci_1 de C, en réponse au signal d'additionneur à propagation de report ONCPA. La valeur de bit correspondante de qiM est gimi. Lorsque le signal d'additionneur à propagation de report ONCPA est dans un état inactif, c'est-à-dire dans un premier état logique "0", chacun des seconds additionneurs complets de la seconde unité d'additionneurs complets 175 effectue n additions sur la valeur de bit gimi de qiM, le report cAi_1, et la somme sAi, pour calculer des valeurs de bit intermédiaires si et ci de S et de C. Lorsque le signal d'additionneur à propagation de report ONCPA est dans un état actif, c'est-à-dire qu'il est dans un second état logique "1", chacun des seconds additionneurs complets de la seconde unité d'additionneurs complets 175 fait la somme de la valeur de bit si+1 de S, de la valeur de bit ci de C, et de la valeur de bit ci_1 de C, pour obtenir les résultats finals de S et C. Le report cAi_1 désigne le report d'un bit dont la position est inférieure d'un bit à celle du bit du report cAi, qui est fourni en sortie de la première unité d'additionneurs complets 171. La valeur de bit sin. de S désigne la somme d'un bit dont la position est supérieure d'un bit à celle de la valeur de bit intermédiaire si, qui est fournie en sortie par la seconde unité d'additionneurs complets 175. La valeur de bit ci_1 de C désigne le report d'un bit dont la position est inférieure d'un bit à celle de la valeur de bit ci, qui est fournie en sortie par la seconde unité d'additionneurs complets 175. Comme représenté sur la figure 2, les LSB du report cAi_1 et du report ci_1 sont dans le premier état logique, et le bit le plus significatif (MSB) de la somme si+1 est égal à la valeur de bit cAn_1 une impulsion d'horloge avant que le signal d'additionneur à propagation de report ONCPA soit activé. La valeur de bit cAn_1 est le MSB du report cAi, c'est-à-dire qu'elle est fournie en sortie de la première unité d'additionneurs complets 171. On va maintenant décrire en détail, en référence à la figure 3, le fonctionnement du multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention des figures 1 et 2. Le multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention comprend des registres, qui stockent des valeurs de bit ai, bi, mi, ci et si (i désignant un entier dans la plage allant de 0 à n-1) respectivement d'un mot A, d'un mot B, d'un modulo M, d'un report C et d'une somme S, et calcule une valeur congrue à "ABR-1" (mod M) . Ici, A et B sont des nombres à n bits d'entrée, et R-1 est un nombre inverse de R en multiplication modulaire "mod M". Dans le fonctionnement du multiplieur modulaire de Montgomery, premièrement, les nombres A et B et le modulo M sont reçus à l'étape S311. A l'étape S313, des registres qui stockent un paramètre i et la somme S sont remis à 0 et initialisés. Les nombres A et B sont inférieurs au modulo M, et M est un nombre impair. Ensuite, aux étapes S315 à S319, le circuit logique de calcul de qi 150 du multiplieur modulaire de Montgomery obtient une valeur qi (i désignant un entier dans la plage allant de 0 à n-1) utilisée pour la boucle "for" de l'Algorithme 1, en résolvant l'équation logique booléenne "se OU-EX co OU-EX ()Di ET a0)". Ici, s0 est le LSB d'une somme S, co est le LSB d'un report C, bi est une valeur de bit du nombre B, et a0 est le LSB du nombre A. De plus, aux étapes S315 à S319, le circuit logique de calcul de biA 140 multiplie le nombre A par la valeur de bit bi pour obtenir chaque bit de biA, et le circuit logique de calcul de qiM 160 calcule chaque bit de qiM en multipliant le modulo M par la valeur de bit qi. De plus, aux étapes S315 à S319, le compresseur 4-2 170 effectue n additions sur C, S, biA et qiM, pour obtenir des valeurs intermédiaires pour chaque bit de S et de C, dans une structure d'additionneur sans propagation de report, qui est formée lorsque le signal d'additionneur à propagation de report ONCPA est dans un état inactif, c'est-à-dire qu'il est dans un premier état logique ("0"). La figure 4 est un schéma synoptique pour expliquer le fonctionnement d'un additionneur sans propagation de report dans le multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention. En se référant aux figures 3 et 4, on note qu'aux étapes S315 à S317 chaque additionneur complet dans l'unité d'additionneurs complets 171 fait la somme de sa valeur de bit correspondante.de biA, de la valeur de bit si+1 de S, et de la valeur de bit ci de C, pour obtenir un report cAi et une somme sAi. Chaque second additionneur complet de la seconde unité d'additionneurs complets 175 effectue n additions sur sa valeur de bit correspondante de qiM, de la somme sAi et du report cAi_1, dont lasélection est effectuée par l'unité de multiplexeurs 173, pour calculer ainsi les valeurs intermédiaires si et ci de la somme S et du report C. Comme représenté sur la figure 2, le bit de sortie du report C est appliqué à l'entrée d'un premier additionneur complet correspondant au bit, le bit de sortie de la somme S est appliqué à l'entrée d'un premier additionneur complet correspondant au bit dont la position est inférieure d'un bit à celle du bit de sortie, et une opération de division dans le rapport 1/2 incluse dans la boucle "for" de l'Algorithme 1 est effectuée, à l'étape S315. Le LSB du report cAi_1 est dans le premier état logique "0". En d'autres termes, lorsque le signal d'additionneur à propagation de report ONCPA est dans un état inactif, le compresseur 4-2 170 produit la structure d'additionneur sans propagation de report, qui est une structure à 4 entrées, 2 sorties, et calcule les valeurs intermédiaires de S et C en utilisant le terme biA et le terme qiM. Après que les valeurs intermédiaires de S et C ont été calculées pour chaque bit, le signal d'additionneur à propagation de report ONCPA est activé et passe au second état logique "1", à l'étape S321. Aux étapes S323 à S327, le compresseur 4-2 170 fait la somme des valeurs intermédiaires calculées pour S et C, pour obtenir les valeurs finales de S et C, dans la structure d'additionneur à propagation de report. La figure 5 est un schéma synoptique pour expliquer le fonctionnement de l'additionneur à propagation de report dans le multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention. En se référant aux figures 3 et 5, on note qu'à l'étape S323, la seconde unité d'additionneurs complets 175 fait la somme de la valeur de bit si+1 de S, de la valeur de bit ci de C, et de la valeur de bit ci_1 de C, qui sont sélectionnées par l'unité de multiplexeurs 173, pour calculer les résultats finals de S et C. Comme représenté sur la figure 2, le MSB de la somme si+1 est égal à la valeur de bit cAn_1 une impulsion d'horloge avant que le signal d'additionneur à propagation de report ONCPA soit activé. Le LSB du report ci_1 est dans le premier état logique "0". A l'étape S325, la valeur de bit si+1 de S, la valeur de bit ci de C, et la valeur de bit ci_1 de C sont sommées pendant un intervalle de temps (un temps de retard de propagation pour un bit)* (n bits), dans la structure d'additionneur à propagation de report. Le temps de retard de propagation pour un bit comprend le temps de retard de propagation de la seconde unité d'additionneurs complets 175 et le temps de retard de chacun des multiplexeurs 2:1 de l'unité de multiplexeurs 173. En d'autres termes, lorsque le signal d'additionneur à propagation de report ONCPA est dans un état actif, une structure d'additionneur à propagation de report à 3 entrées, 2 sorties est établie, et les valeurs intermédiaire de S et C sont sommées dans la structure à 3 entrées, 2 sorties pour calculer les valeurs finales de S et C. Comme décrit ci-dessus, le multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention comprend des registres qui stockent des valeurs de bit ai, bi, mi, ci et si (i désignant un entier dans la plage allant de 0 à n-1) respectivement d'un mot A, d'un mot B, d'un modulo M, d'un report C et d'une somme S, et calcule une valeur congrue à "ABR-1" (mod M). Ici, A et B sont des nombres à n bits d'entrée, et R-1 est un nombre inverse de R en multiplication modulaire "mod M". Le circuit logique de calcul de biA 140 calcule chaque bit de biA en multipliant le nombre A par la valeur de bit bi. A ce moment, le circuit logique de calcul de qi 150 calcule une valeur qi (i désignant un entier compris dans la plage allant de 0 à n-1) en résolvant une équation logique booléenne "s0 OU-EX co OU- EX (bi ET a0)" Ici, sp est le LSB d'une somme S, co est le LSB d'un report C, bi est une valeur de bit du nombre B, et ae est le LSB du nombre A. Le circuit logique de calcul de qiM 160 calcule chaque bit de qiM en multipliant le modulo M par la valeur de bit qi. En réponse au signal d'additionneur à propagation de report ONCPA, le compresseur 4-2 170 effectue n additions sur C, S, biA et qiM, pour obtenir des valeurs calculées intermédiaires pour chaque bit de S et de C, dans une structure d'additionneur sans propagation de report. Ensuite, le compresseur 4-2 170 fait la somme des valeurs calculées intermédiaires pour obtenir les résultats finals de S et de C dans une structure d'additionneur à propagation de report. Les résultats de S et C sont respectivement émis vers les registres S et C, 180 et 190. Comme décrit ci-dessus, le multiplieur modulaire de Montgomery conforme à un mode de réalisation de la présente invention élimine un temps de retard de propagation en utilisant une structure d'additionneur sans propagation de report (CSA), dans laquelle toutes les additions nécessaires pour chaque bit sont effectuées en premier sur quatre mots (par exemple C, S, biA et qiM), et il effectue ensuite des additions dans une structure d'additionneur à propagation de report (CPA) seulement dans un étage de sortie final. Par conséquent, on obtient une vitesse de fonctionnement élevée et un produit puissance-retard de faible valeur, ce qui améliore les performances d'un algorithme de multiplication modulaire de Montgomery. Bien que des modes de réalisation de la présente invention aient été décrits en référence à diverses figures, les détails des figures ne doivent pas être interprétés d'une manière qui limite le cadre des modes de réalisation de la présente invention. Par exemple, la figure 1 illustre l'utilisation d'un compresseur 4-2. Le cadre de la présente invention n'est pas limité à un compresseur 4-2, et divers modes de réalisation peuvent utiliser une multiplicité de compresseurs d'entrée et de sortie. De façon similaire, le cadre des modes de réalisation de la présente invention n'est pas limité à trois registres, A, M et B. D'autres registres peuvent être incorporés en combinaison avec une compresseur ayant une multiplicité d'entrées et de sorties. En outre, les bases des exemples des divers modes de réalisation ne sont pas limitées à une valeur de base particulière. Il va de soi que de nombreuses autres modifications peuvent être apportées au dispositif et au procédé décrits et représentés, sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé pour effectuer une multiplication de Montgomery à base 2N, avec N 1, caractérisé en ce qu'il comprend les étapes suivantes: on reçoit un multiplicande (A), un modulo (M) et un multiplicateur (B); on effectue une addition sans propagation de report sur au moins quatre grandeurs d'entrée liées au multiplicande, au modulo et au multiplicateur, pour générer un résultat en représentation redondante; et on effectue une addition avec propagation de report pour générer un résultat en représentation normale, en réponse à un signal d'additionneur à propagation de report (ONCPA).