Brevet FR2773231A1 — publié le 19990702

Procédé de production amélioré d'un paramètre JO associé à la mise en oeuvre d'opérations modulaires selon la méthode de Montgomerv. L'invention concerne un procédé de production d'un paramètre de calcul intervenant dans la mise en oeuvre d'opérations modulaires selon la méthode de Montgomery. Les opérations modulaires selon la méthode de Montgomery permettent d'effectuer des calculs modulaires dans un corps fini de Galois GF(2n) à 2n éléments, sans effectuer de division. Ces opérations ont une application en cryptographie, pour l'authentification de messages, l'identification d'un utilisateur et l'échange de clés. De tels exemples d'applications sont décrits, par exemple, dans la demande de brevet français publiée sous le numéro 2 679 054. On peut trouver dans le commerce des circuits intégrés dédiés à de telles applications, par exemple le produit ST16CF54 de la société SGS- THOMSON Microelectronics. Pour réaliser des calculs modulaires, on utilise un coprocesseur arithmétique dédié, décrit dans la demande de brevet européen 0 601 907. Dans la mise en oeuvre des opérations modulaires par le coprocesseur dédié, il est nécessaire de produire un paramètre binaire J0, codé sur un nombre entier Bt de bits, et tel que [(J0 + NO) + 1] mod 2Bt = 0, avec NO un nombre entier impair codé sur Bt bits et mod représentant le modulo. L'inventeur a déjà proposé des procédés permettant de produire ledit 2 0 paramètre J0 en utilisant un circuit dédié, ce qui permet de réaliser rapidement, dans un circuit intégré, le calcul de ce paramètre. Ces procédés sont décrits dans la demande de brevet européen 0 778 518 publiée le 11 Juin 1996 (demande à laquelle correspond la demande de brevet déposée le 3 Décembre 1996 aux Etats-Unis sous le numéro 08/759,892). 2 5 Un facteur important dans la réalisation d'opérations modulaires est le temps de calcul nécessaire pour produire le résultat recherché. L'inventeur a cherché à améliorer les procédés antérieurs et la présente demande propose un nouveau procédé de calcul, permettant de réaliser plus rapidement le calcul du paramètre JO. 3 0 Ainsi l'invention propose un procédé de production dans un circuit intégré d'un paramètre J0 associé à la mise en oeuvre d'opérations modulaires selon la méthode de Montgomery, avec J0 codé sur Q * L bits tels que J0 = JOL_1... J00, avec Q et L des nombres entier. Le procédé comprend les étapes suivantes: Etape I: chargement d'une donnée binaire NO, codée sur Q * L bits, le bit de poids faible de NO étant égal à 1, dans un premier registre, chargement de Q * L zéros dans des deuxième et troisième registre et de L zéros dans un quatrième registre; Etape 2: réalisation d'une boucle de Q itérations comprenant les étapes suivantes, indicée par j, avec j variant de O à Q - 1: Etape 2.1: réalisation d'une boucle de L itérations, indicée par i avec i variant de O à L - 1, comprenant les étapes suivantes: - décalage du contenu du quatrième registre de une unité vers la droite, cette opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste. - test du bit issu de ce décalage dans un circuit de test Si le bit contrôlé est à 1: décalage à droite du contenu du troisième registre de une unité vers la droite et chargement d'un 0, sur le bit de poids fort de ce registre 1 1 et dans un cinquième registre; addition bit à bit du contenu du quatrième registre avec un zéro dans un premier additionneur, une sortie de ce premier additionneur étant reliée à l'entrée du quatrième registre, et test du deuxième bit de poids faible en sortie du premier additionneur; Sinon: décalage à droite du contenu du troisième registre de une unité vers 2 0 la droite; chargement d'un 1 sur le bit de poids fort du troisième registre et dans le cinquième registre; addition bit à bit du contenu du quatrième registre et des L derniers bits du premier registre, dans le premier additionneur, la sortie de ce premier additionneur étant reliée à l'entrée du quatrième registre, le premier registre formant un registre de L bits dont 2 5 l'entrée et la sortie sont reliées, et test du deuxième bit de poids faible en sortie du premier additionneur; Etape 2.2: décalage du contenu de l'ensemble du premier registre et réalisation, dans un circuit de multiplication, de la multiplication du contenu du premier 3 0 registre par le contenu du cinquième registre, celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un deuxième additionneur; stockage, dans le deuxième registre, des Q * L bits de poids fort de la donnée binaire produite par le deuxième additionneur, et stockage des L bits de poids les plus faibles de ces Q * L bits dans le quatrième registre. Selon un mode de réalisation l'étape 2.2 est la suivante lors des Q - 1 premières itérations: décalage du contenu de l'ensemble du premier registre et réalisation, dans un circuit de multiplication, de la multiplication du contenu du premier registre par le contenu du cinquième registre, celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un deuxième additionneur; stockage, dans le deuxième registre, des Q * L bits de poids fort de la donnée binaire produite par le deuxième additionneur, et stockage des L bits de poids les plus faibles de ces Q * L bits dans le quatrième registre. Selon un mode de réalisation, l'étape 2.2 est la suivante: décalage du contenu de l'ensemble du premier registre et réalisation, dans un circuit de multiplication, de la multiplication du contenu du premier registre par le contenu du cinquième registre, celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un deuxième additionneur; stockage, dans le deuxième registre, des [Q - j] * L bits de poids fort de la donnée binaire produite par le deuxième additionneur, et stockage des L bits de poids les plus faibles de ces [Q - j] * L bits dans le quatrième registre. Selon un mode de réalisation, l'étape 2.2 est la suivante lors des Q - 1 premières itérations: 2 5 décalage du contenu de l'ensemble du premier registre et réalisation, dans un circuit de multiplication, de la multiplication du contenu du premier registre par le contenu du cinquième registre, celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre et addition de ce contenu avec le résultat de la 3 0 multiplication, codé sur Q * L + L bits, dans un deuxième additionneur; stockage, dans le deuxième registre, des [Q - j] * L bits de poids fort de la donnée binaire produite par le deuxième additionneur, et stockage des L bits de poids les plus faibles de ces [Q j] * L bits dans le quatrième registre. 3 5 Selon un mode de réalisation, l'étape 2.1 est la suivante: -pouri=j =0: - décalage du contenu du troisième registre de une unité vers la droite et chargement d'un 1 sur le bit de poids fort de ce troisième registre et dans un cinquième registre; addition bit à bit du contenu du quatrième registre avec un zéro dans un premier additionneur, la sortie de ce premier additionneur étant reliée à l'entrée du quatrième registre; test du deuxième bit de poids faible à la sortie du premier additionneur, à l'aide d'un circuit de test; réalisation d'une boucle de L itérations, indicée par i avec i variant de 0 à L - 1, si j est différent de 0 et de 1 à L - 1 sinon, la boucle comprenant les étapes suivantes: - décalage du contenu du quatrième registre de une unité vers la droite, cette opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste. - test du bit issu de ce décalage dans le circuit de test: Si le bit contrôlé est égal à 1: décalage à droite du contenu du troisième registre de une unité vers la droite; chargement d'un 0 sur le bit de poids fort du troisième registre et dans le cinquième registre; addition bit à bit du contenu du quatrième registre avec un zéro dans le premier additionneur, la sortie du premier additionneur étant reliée à l'entrée du quatrième registre, et test du deuxième bit de poids faible en sortie du premier additionneur; Sinon: décalage à droite du contenu du troisième registre de une unité vers la droite; chargement d'un 1 sur le bit de poids fort du troisième registre et dans le cinquième registre; addition bit à bit du contenu du quatrième registre et des L derniers bits du premier registre, dans le premier additionneur, la sortie du premier additionneur étant reliée à l'entrée du quatrième registre, le premier registre formant un registre de L bits dont l'entrée et la sortie sont reliées, et test du deuxième bit de poids faible en sortie du premier additionneur. D'autres avantages et particularités apparaîtront à la lecture de la description qui suit d'un exemple de réalisation de l'invention, à lire conjointement aux dessins annexés dans lesquels: - la figure 1 représente un circuit de cryptage dans lequel intervient le 3 5 paramètre de calcul J0, - la figure 2 représente schématiquement un circuit permettant de mettre en oeuvre des opérations modulaires selon la méthode de Montgomery, - la figure 3 représente un circuit mis en oeuvre dans la production du paramètre de calcul JO, selon l'état de la technique, - la figure 4 représente le circuit de la figure 2, modifié pour mettre en oeuvre l'invention. La figure I représente un circuit de cryptage dans lequel intervient le paramètre de calcul JO. Ladite figure I correspond à la figure 1 de la demande de brevet O 778 518, décrite colonne 4 - ligne 54 à colonne 5 ligne 31 de cette demande à laquelle on peut se référer. La figure 2 représente schématiquement un circuit permettant de mettre en oeuvre des opérations modulaires selon la méthode de Montgomerv. Ladite figure 2 correspond à la figure 2 de la demande de brevet O 778 518, décrite colonne 5 - ligne 32 à colonne 6 - ligne 57 de cette demande à laquelle on peut se référer. Tel qu'il est indiqué dans la demande O 778 518, le paramètre JO était habituellement calculé de manière logiciel et externe au coprocesseur illustré sur la figure 2. Afin de diminuer le temps de calcul de ce paramètre, la demande O 778 518 propose d'utiliser le circuit 5 de la figure 3. Ladite figure 3 correspond à la figure 3 de la demande de brevet O 778 518, décrite colonne 7 - ligne 9 à ligne 42 de cette 2 0 demande à laquelle on peut se référer. La demande O 778 518 décrit plusieurs procédés permettant de calculer le paramètre JO en utilisant le circuit de la figure 3. Les dits procédés sont basés sur l'algorithme suivant, en notant JO(i) le i-ième 2 5 bit de la donnée recherchée JO: X, codé sur Bt bits tel que X = O K=X= O Pour i = Oà Bt-I Si K mod 2 = O, JO(i) = I; 3 0 Sinon JO(i) = O; K = K +NO * JO(i) K= K/2 X = X + NO * JO(i) 3 5 A titre d'exemple, le procédé suivant est proposé: Etape 1: chargement de la donnée binaire NO, codée sur Bt bits, le bit de poids faible étant égal à 1, dans les registres 40 et 42 de Bt bits, par l'intermédiaire de bornes d'entrées et des multiplexeurs 43 et 44, Etape 2: décalage du contenu du deuxième registre 41 de une unité vers la droite; chargement d'un 1 sur le bit de poids fort de ce registre 41; addition bit à bit du contenu du registre 40 avec un zéro dans l'additionneur série 46, la sortie de l'additionneur étant reliée à l'entrée du registre 40, et test du deuxième bit du deuxième bit de poids faible à la sortie de l'additionneur 46 à l'aide du circuit de test 47; Etape 3: mise en oeuvre d'une boucle de calcul itérative, indicée par i, avec i variant de 1 à Bt - 1, chaque itération de la boucle comprenant les étapes suivantes: i - décalage du contenu du registre 40 de une unité vers la droite, cette opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste; 2 - suivant le résultat du dernier test effectué: Si le bit contrôlé est égal à I: décalage à droite du contenu du registre 41 2 0 de une unité vers la droite; chargement d'un 0. avec le circuit de test, sur le bit de poids fort du registre 41; addition bit à bit du contenu du registre 40 avec un O dans l'additionneur 46, la sortie de l'additionneur 46 étant reliée à l'entrée du registre 40, et test du deuxième bit de poids faible en sortie de l'additionneur 46; 2 5 Sinon: - décalage à droite du contenu du registre 41 de une unité vers la droite; chargement d'un 1, avec le circuit de test, sur le bit de poids fort du registre 41; addition bit à bit du contenu des registres 40 et 42 dans l'additionneur 46, la sortie de l'additionneur 46 étant reliée à l'entrée du registre 40, la 3 0 sortie du registre 42 étant bouclée sur son entrée, et test du deuxième bit de poids faible en sortie de l'additionneur 46. Une fois la boucle terminée, le paramètre JO est disponible dans le registre 42. Au total, tel que mentionné à la colonne 9 - ligne 7 de la demande 0 778 518, 3 5 le procédé décrit utilise Bt2 + 3 * Bt - I cycles d'horloge. Il est susceptible de diverses variantes, décrites dans ladite demande, le temps de calcul nécessaire pour ces variantes étant donné par une formule générale du type xl * Bt2 + yl * Bt - zl, avec xl, yl et zl des entiers et, en pratique, xl = 1. En utilisant des registres de taille variable (voir colonne 13 ligne 29 à colonne 14 ligne 2 de la demande 0 778 518, incorporées par référence dans la présente demande), on peut diminuer le nombre de cycles nécessaires et obtenir un temps de calcul de formule générale Bt2/2 + y2 * Bt - z2, avec y2 et z2 des entiers. L'inventeur à cherché à améliorer les procédés décrits dans la demande 0 778 518, de sorte à réduire le temps de calcul du paramètre J0. Pour ce faire, il propose d'opérer différemment, en calculant des sous - ensembles de bits de J0. On supprime ainsi la recherche des Bt bits de J0 en opérant Bt additions bit à bit de données de Bt bits, ce qui induit un temps de calcul proportionnel à Bt2 dans les procédés de l'état de la technique. On suppose que la donnée NO et le résultat J0 sont subdivisées en un nombre entier Q de données binaires NOQ..1... NO0O et JOQ 1... J00 codées sur L bits, avec L entier tel que L Un algorithme proposé par l'inventeur pour calculer J0 = JOQ 1... J00 est le suivant, en notant JOj(i) le i-ième bit de la donnée de L bits JÀ 2 0 X, donnée binaire codée sur L * P bits, avec X = XQ 1... XO = 0 K. donnée binaire codée sur L bits, avec K = = X mod 2L = 0 Pourj =0 à Q-l, Pour i = 0 à L-1 Si K mod 2 = 0, J0j(i)= 1; Sinon JOj(i) = 0; K = K + No00 * Jq (i) K = K/2 X=X+N0 * J0j X = (X/2L) mod 2LQ Pour mettre en oeuvre ledit algorithme, l'inventeur propose de procéder de la manière suivante: - on réalise les boucles de calcul des bits des données binaires J0j selon l'un des procédés décrits dans la demande 0 778 518, le procédé utilisé étant adapté pour 3 5 produire des sous - opérandes de L bits au lieu d'opérandes de Bt bits, et - on utilise des ressources du coprocesseur pour actualiser, par multiplication, la valeur de la donnée binaire X. La figure 4 illustre le coprocesseur de la figure 2, ledit processeur étant adapté pour mettre en oeuvre l'algorithme défini ci-dessus. Cette adaptation comprend l'ajout d'éléments permettant de former un circuit du type de celui illustré sur la figure 3 de la demande 0 778 518. Elle comprendra également une modification de son programme de séquencement, celui-ci n'étant pas décrit en détails et ne devant pas poser de problème à l'homme du métier disposant de la description des procédés à mettre en oeuvre. Le circuit de la figure 4 comprend, outre les différents éléments décrits dans la demande de brevet 0 778 518 (colonne 5 - ligne 32 à colonne 6 - ligne 57 de cette demande, tel que mentionné auparavant): - un registre à décalage 60 de L bits, comprenant une entrée et une sortie, un additionneur série 61, comprenant deux entrées et une sortie série, un multiplexeur 62 comprenant deux entrées et une sortie, - un circuit de test 63, comprenant une entrée et une sortie, - un multiplexeur 64 comprenant deux entrées et une sortie, - un multiplexeur 65 comprenant deux entrées et une sortie Par ailleurs, les éléments suivants ont été modifiés: 2 0 - le multiplexeur 14 comprend une troisième entrée, - le multiplexeur 25 comprend une troisième entrée, et - le multiplexeur 24 comprend une troisième et une quatrième entrées. L'entrée et la sortie du registre 60 sont reliées, respectivement, à la sortie du multiplexeur 62 et à une entrée de l'additionneur 61. L'autre entrée de l'additionneur 61 est reliée à la sortie du multiplexeur 64. Une des entrées du multiplexeur 64 est reliée à la sortie du registre 12. Son autre entrée reçoit un zéro logique. La sortie de l'additionneur 61 est reliée à une première entrée du multiplexeur 62 et à l'entrée du circuit de test 63. La sortie de ce circuit de test 63 est reliée, d'une 3 0 part, à la troisième entrée du multiplexeur 24 et, d'autre part, à la troisième entrée du multiplexeur 14. La quatrième entrée du multiplexeur 24 reçoit un zéro logique. La deuxième entrée du multiplexeur 62 est reliée à la sortie du multiplexeur , cette sortie remplaçant la sortie de l'additionneur 31 vis-à-vis des registres 10, 11 et 12. Les entrées du multiplexeur 65 sont reliées, respectivement, aux sorties des 3 5 additionneurs 30 et 31. La sortie du multiplexeur 38 est reliée à la troisième entrée du multiplexeur 25. On suppose par ailleurs que le registre 12 comprend des moyens pour former un registre circulaire de L bits. Ces moyens, non représentés, seront par exemple formés d'un multiplexeur permettant de relier sa sortie à l'entrée de la L-ième cellule, en numérotant les cellules à partir de la sortie. On supposera que les registres 10, 11 et 12 sont formés de Q * L bits. Si ces registres ont une taille supérieure à celle de NO et J0, on pourra les ramener à la taille souhaitée, par exemple en procédant tel qu'illustré sur la figure 4 de la demande de brevet 0 778 518. Pour mettre en oeuvre l'algorithme décrit, les registres 10, 11, 12 et 60 permettent de stocker, respectivement, les données binaires X, J0, NO et K. L'inventeur propose le procédé suivant: Etape I: chargement de la donnée binaire NO, codée sur Q * L bits, dans le registre 12, le bit de poids faible de NO étant à 1, chargement de Q * L zéros logiques dans les registre 10 et 11, et de L zéros logiques dans le registre 60. Etape 2: réalisation d'une boucle de Q itérations comprenant les étapes suivantes, indicée par j, avec j variant de 0 à Q - 1: Etape 2.1: réalisation d'une boucle de L itérations, indicée par i avec i variant de 0 à L - 1, comprenant les étapes suivantes: - décalage du contenu du registre 60 de une unité vers la droite, cette opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste. - test du bit issu de ce décalage dans le circuit de test 63 Si le bit contrôlé est égal à 1: - décalage à droite du contenu du registre 1 1 de une unité vers la droite, - chargement d'un 0, avec le circuit de test 63, sur le bit de poids fort 3 0 du registre 11 et dans le registre 16, addition bit à bit du contenu du registre 60 avec un zéro dans l'additionneur 61, la sortie de l'additionneur 61 étant reliée à l'entrée du registre 60, et test du deuxième bit de poids faible en sortie de l'additionneur 61, Sinon: - décalage à droite du contenu du registre 11 de une unité vers la droite; - chargement d'un 1, avec le circuit de test, sur le bit de poids fort du registre 1 1 et dans le registre 16, addition bit à bit du contenu du registre 60 et des L derniers bits du registre 12, dans l'additionneur 61, la sortie de l'additionneur 61 étant reliée à l'entrée du registre 60, le registre 12 formant un registre de L bits dont l'entrée et la sortie sont reliées, et test du deuxième bit de poids faible en sortie de l'additionneur 61, Etape 2.2: - décalage du contenu de l'ensemble du registre 12 et réalisation, dans le circuit de multiplication 19, de la multiplication du contenu du registre 12 par le contenu du registre 16, celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L, - décalage du contenu du registre 10 et addition de ce contenu avec le résultat de la multiplication, codé sur (Q * L + P) bits, dans l'additionneur , - stockage, dans le registre 10, des Q * L bits de poids fort de la donnée binaire produite par l'additionneur 30, et stockage des L bits de poids les plus faibles de ces Q * L bits dans le registre 60. A la fin de ce procédé, la donnée recherchée est dans le registre 11. La réalisation du chargement initial des registres, des calculs des données J0j et des multiplications nécessite (Q * L) + Q * (x * L2 + y * p - z) + Q * L * (Q + 1) temps de cycle, c'est-à-dire Q * [L + L * (Q + 1) + (x * L2 + y * P - z)] temps de cycle, en supposant que le registre 16 a une taille L (dans ce cas, il n'est pas nécessaire de rajouter, sur le multiplexeur 24, une entrée recevant un zéro). Avec NO et J0 codés sur Q * L = 128 bits, x = 1, y = 3 et z = 1, le procédé de l'état de l'art nécessite 16 767 temps de cycle (en considérant la formule Bt2 + 3 * Bt - 1). Avec L = 8 et Q = 16, le procédé ci-dessus ne nécessite que 3 584 temps de cycle, c'est-à-dire qu'on a une très importante réduction du temps de calcul. On remarquera que l'on peut améliorer ledit procédé en remarquant que - le bit J00(0) est nécessairement égal à 1, et - la Q-ième multiplication n'est pas nécessaire, le registre 11 ayant reçu les L 3 5 bits de poids fort de la donnée J0 du circuit de test 63 lors de l'étape 2.1 de la Q-ième itération. Pour minimiser le temps de calcul, on peut ainsi modifier les étapes du procédé de la manière suivante: - pour ce qui concerne l'étape 2.1 Etape 2.1 -pouri=j =0: - décalage du contenu du registre 11 de une unité vers la droite et chargement d'un 1 sur le bit de poids fort de ce registre et dans le registre 16 (on pourra par exemple rajouter une entrée sur le multiplexeur 24, cette entrée recevant un 1 logique), - addition bit à bit du contenu du registre 60 avec un zéro dans l'additionneur 61, la sortie de cet additionneur étant reliée à l'entrée du registre 60, - test du deuxième bit de poids faible à la sortie de l'additionneur 61, à l'aide du circuit de test 63, - réalisation d'une boucle de L itérations, indicée par i avec i variant de 0 à L - 1, si j est différent de 0 et de 1 à L - 1 sinon, la boucle comprenant les étapes suivantes: - décalage du contenu du registre 60 de une unité vers la droite, cette 2 0 opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste. - test du bit issu de ce décalage Si le bit contrôlé est égal à 1: décalage à droite du contenu du registre 11 de une unité vers la droite; 2 5 - chargement d'un 0, avec le circuit de test 63, sur le bit de poids fort du registre 11 et dans le registre 16, - addition bit à bit du contenu du registre 60 avec un zéro dans l'additionneur 61, la sortie de l'additionneur 61 étant reliée à l'entrée du registre 60, et test du deuxième bit de poids faible en sortie de l'additionneur 61, Sinon: décalage à droite du contenu du registre 11 de une unité vers la droite; chargement d'un 1, avec le circuit de test, sur le bit de poids fort du registre 11 et dans le registre 16, - addition bit à bit du contenu du registre 60 et des L derniers bits du registre 12, dans l'additionneur 61, la sortie de l'additionneur 61 étant reliée à l'entrée du registre 60, le registre 12 formant un registre de L bits dont l'entrée et la sortie sont reliées, et test du deuxième bit de poids faible en sortie de l'additionneur 61, - pour ce qui concerne l'étape 2.2 Etape 2.2: lors des Q - I premières itérations - décalage du contenu de l'ensemble du registre 12 et réalisation, dans le circuit de multiplication 19, de la multiplication du contenu du registre 12 par le contenu du registre 16, celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L, - décalage du contenu du registre 10 et addition de ce contenu avec le résultat de la multiplication, codé sur (Q * L + P) bits, dans l'additionneur 30. - stockage, dans le registre 10, des Q * L bits de poids fort de la donnée binaire produite par l'additionneur 30, et stockage des L bits de poids les plus faibles de ces Q * L bits dans le registre 60. Selon une variante, un algorithme proposé par l'inventeur pour calculer JO = JOQ_... J est le suivant: x=0 K = XO = X mod 2L = 0 Pourj = O à Q-1, Pour i = 0 à L-l Si K mod 2 = 0, Jj (i) = 1; Sinon J0j(i) = 0; K=K+No00 * J(i) K = K/2 X = X + NO * Jji X = (X/2L) mod 2L(Q-j) 3 0 Pour mettre en oeuvre cet algorithme, il suffira d'utiliser un registre 10 de taille variable pour stocker X, et ne stocker que les L * (Q - j) bits de poids fort de la donnée produite par le circuit de multiplication 19. Un exemple d'un tel registre est décrit figure 4 et colonne 13 - lignes 14 à 28 de la demande 0 778 518 à laquelle on peut se référer. 3 5 Dans ce cas, on pourra montrer que le temps de calcul est donné par la formule suivante: Q * [L + L * (Q + 4)/2 + (x * L2 + y * L + z)], ce qui réduit le nombre de temps de cycle nécessaires à 2800. Pour implémenter l'algorithme ci-dessus, il suffit de modifier l'étape 2. 2 telle que définie dans le premier procédé: Etape 2.2: - décalage du contenu de l'ensemble du registre 12 et réalisation, dans le circuit de multiplication 19, de la multiplication du contenu du registre 12 par le contenu du registre 16, - décalage du contenu du registre 10 et addition de ce contenu avec le résultat de la multiplication, codé sur (Q * L + P) bits, dans l'additionneur 30, - stockage, dans le registre 10, des (Q - j) * L bits de poids fort de la donnée binaire produite par l'additionneur 30, et stockage des L bits de poids les plus faibles de ces Q * L bits dans le registre 60. On pourra, de même que dans le premier procédé illustré, diminuer le temps de calcul en modifiant les étapes 2.1 et 2.2 pour tenir compte du fait que J00(0) = 1 et que la dernière multiplication n'est pas nécessaire. Bien entendu, on pourra, sans sortir du cadre de l'invention, utiliser un coprocesseur modifié différemment que dans l'exemple illustré sur la figure 4. Ainsi, on pourra choisir d'utiliser des registres dédiés pour stocker les données X, J0 et NO. 2 o On pourra également utiliser le circuit de multiplication 20 et le circuit d'addition 31 pour le calcul de X. Il suffira d'adapter les moyens de multiplexage et d'ajouter les connexions nécessaires pour relier entre eux les éléments intervenant dans les calculs, ces adaptations ne posant pas de problème à l'homme du métier. REVENDICATIONS I - Procédé de production dans un circuit intégré d'un paramètre J0 associé à la mise en oeuvre d'opérations modulaires selon la méthode de Montgomery, avec J0 codé sur Q * L bits tels que J0 = JOL-1... J00, avec Q et L des nombres entier, caractérisé en ce qu'il comprend les étapes suivantes: Etape 1: chargement d'une donnée binaire NO, codée sur Q * L bits, le bit de poids faible de NO étant égal à 1, dans un premier registre (12), chargement de Q * L zéros dans des deuxième et troisième registre (10, 11) et de L zéros dans un quatrième registre (60); Etape 2: réalisation d'une boucle de Q itérations comprenant les étapes suivantes, indicée par j, avec j variant de 0 à Q - 1: Etape 2.1: réalisation d'une boucle de L itérations, indicée par i avec i variant de 0 à L - 1, comprenant les étapes suivantes: - décalage du contenu du quatrième registre (60) de une unité vers la droite, cette opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste. - test du bit issu de ce décalage dans un circuit de test (63) Si le bit contrôlé est à 1: décalage à droite du contenu du troisième registre (11) de une unité vers la droite et chargement d'un 0, sur le bit de poids fort de ce registre 11 et dans un cinquième registre (16); addition bit à bit du contenu du quatrième registre (60) avec un zéro dans un premier additionneur (61), une sortie de ce premier additionneur étant reliée à l'entrée du quatrième registre (60), et test du deuxième bit de poids faible en sortie du premier additionneur; 2 5 Sinon: décalage à droite du contenu du troisième registre ( 11) de une unité vers la droite; chargement d'un 1 sur le bit de poids fort du troisième registre et dans le cinquième registre (16); addition bit à bit du contenu du quatrième registre (60) et des L derniers bits du premier registre (12), dans le premier additionneur (61), la sortie de ce premier 3 0 additionneur étant reliée à l'entrée du quatrième registre (60), le premier registre (12) formant un registre de L bits dont l'entrée et la sortie sont reliées, et test du deuxième bit de poids faible en sortie du premier additionneur; Etape 2.2: décalage du contenu de l'ensemble du premier registre (12) et réalisation, dans un circuit de multiplication (19), de la multiplication du contenu du premier registre (12) par le contenu du cinquième registre (16), celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre (10) et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un deuxième additionneur (30); stockage, dans le deuxième registre (10), des Q * L bits de poids fort de la donnée binaire produite par le deuxième additionneur (31), et stockage des L bits de poids les plus faibles de ces Q * L bits dans le quatrième registre (60). 2 - Procédé selon la revendication 1, caractérisé en ce que l'étape 2.2 est la suivante: lors des Q - 1 premières itérations décalage du contenu de l'ensemble du premier registre (12) et réalisation, dans un circuit de multiplication (19), de la multiplication du contenu du premier registre (12) par le contenu du cinquième registre (16), celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre (10) et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un 2 0 deuxième additionneur (30); stockage, dans le deuxième registre (10), des Q * L bits de poids fort de la donnée binaire produite par le deuxième additionneur (31), et stockage des L bits de poids les plus faibles de ces Q * L bits dans le quatrième registre (60). 3 - Procédé selon la revendication 1, caractérisé en ce que l'étape 2.2 est la suivante: décalage du contenu de l'ensemble du premier registre (12) et réalisation, dans un circuit de multiplication (19), de la multiplication du contenu du premier registre (12) par le contenu du cinquième registre (16), celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre (10) et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un deuxième additionneur (30); stockage, dans le deuxième registre (10), des [Q - j] * L bits de poids fort de la donnée binaire produite par le deuxième additionneur (31), et stockage des L bits de poids les plus faibles de ces [Q - j] * L bits dans le quatrième registre (60). 4 - Procédé selon la revendication 3, caractérisé en ce que l'étape 2.2 est la suivante: lors des Q - 1 premières itérations décalage du contenu de l'ensemble du premier registre (12) et réalisation, dans un circuit de multiplication (19), de la multiplication du contenu du premier registre (12) par le contenu du cinquième registre (16), celui-ci ayant été complété de zéros logiques si sa taille est supérieure à L; décalage du contenu du deuxième registre (10) et addition de ce contenu avec le résultat de la multiplication, codé sur Q * L + L bits, dans un deuxième additionneur (30); stockage, dans le deuxième registre (10), des [Q - j] * L bits de poids fort de la donnée binaire produite par le deuxième additionneur (31), et stockage des L bits de poids les plus faibles de ces [Q - j] * L bits dans le quatrième registre (60). - Procédé selon l'une des revendications 1 à 4, caractérisé en ce que l'étape 2.1 est la suivante: - pour i = j = 0: - décalage du contenu du troisième registre (11) de une unité vers la droite 2 0 et chargement d'un 1 sur le bit de poids fort de ce troisième registre et dans un cinquième registre (16); addition bit à bit du contenu du quatrième registre (60) avec un zéro dans un premier additionneur (61), la sortie de ce premier additionneur étant reliée à l'entrée du quatrième registre; test du deuxième bit de poids faible à la sortie du premier additionneur, à l'aide 2 5 d'un circuit de test (63); - réalisation d'une boucle de L itérations, indicée par i avec i variant de 0 à L - 1, si j est différent de 0 et de 1 à L - 1 sinon, la boucle comprenant les étapes suivantes: - décalage du contenu du quatrième registre (60) de une unité vers la 3 0 droite, cette opération correspondant à une division par deux du contenu de ce registre, en oubliant le reste. - test du bit issu de ce décalage dans le circuit de test (63): Si le bit contrôlé est égal à 1: décalage à droite du contenu du troisième registre (11) de une unité vers la droite; chargement d'un 0 sur le bit de poids fort du troisième registre et dans le cinquième registre (16); addition bit à bit du contenu du quatrième registre (60) avec un zéro dans le premier additionneur (61), la sortie du premier additionneur étant reliée à l'entrée du quatrième registre, et test du deuxième bit de poids faible en sortie du premier additionneur; Sinon: décalage à droite du contenu du troisième registre (11) de une unité vers la droite; chargement d'un 1 sur le bit de poids fort du troisième registre et dans le cinquième registre (16); addition bit à bit du contenu du quatrième registre (60) et des L derniers bits du premier registre (12), dans le premier additionneur (61), la sortie du premier additionneur étant reliée à l'entrée du quatrième registre, le premier registre formant un registre de L bits dont l'entrée et la sortie sont reliées, et test du deuxième bit de poids faible en sortie du premier additionneur.