Brevet FR2774783A1 — publié le 19990813

Procédé de mise en oeuvre d'une opération modulaire élémentaire selon la méthode de Montqomery L'invention concerne un procédé de mise en oeuvre d'une opération modulaire élémentaire selon la méthode de Montgomery. Cette méthode permet d'effectuer des calculs modulaires dans un corps fini GF(2n) (corps de Gallois) sans effectuer de divisions. Classiquement, les opérations modulaires sur GF(2n) sont utilisées en cryptographie pour des applications telles que 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 FR-A-2 679 054 (document D1). On trouve dans le commerce des circuits intégrés dédiés à de telles applications, par exemple le produit fabriqué par SGS-THOMSON MICROELECTRONICS S.A. et référencé ST16CF54, bâti autour d'une association de type unité centrale - coprocesseur arithmétique, et dédié à la mise en oeuvre de calculs modulaires. Le coprocesseur utilisé permet de traiter des multiplications modulaires, en utilisant la méthode de Montgomery. I1 fait l'objet de la demande de brevet EP-A-0 601 907 (document D2). L'opération de base, dite Pfield, consiste, à partir de trois données binaires, A (multiplicande), B (multiplieur inférieur à N) et N (modulo), codées sur un nombre entier n de bits, à produire une donnée binaire notée P(A, B)N codée sur n bits, telle que P(A, B)N = A * B * I mod N, avec I = 2-n mod N. Pour cela, on considère que les données sont codées sur m mots de k bits, avec m * k = n, et on fournit les mots de A et B à un circuit de multiplication ayant une entrée série, une entrée parallèle et une sortie série. Pour le coprocesseur décrit dans D2, on a k = 32 et m = 8 ou 16. La figure 1 représente le coprocesseur d'ar thmétique modulaire dévoilé par D2. Ce coprocesseur comprend les éléments suivants: - trois registres à décalage 10, 11, et 12, de m * k bits, ayant une entrée et une sortie série, destinés à recevoir respectivement le multiplieur B, le résultat S, et le modulo N, - un multiplexeur 13 à trois entrées série dont une sortie série est reliée à l'entrée du registre 10, une première entrée étant reliée à une première borne d'entrée, une deuxième entrée étant reliée à la sortie du registre 10, - un multiplexeur 14 à deux entrées série dont une sortie série est reliée à l'entrée du registre 11, une première entrée est reliée à un "0" logique, - un multiplexeur 15 à trois entrées série dont une sortie série est reliée à l'entrée du registre 12, une première entrée étant reliée à une deuxième borne d'entrée, une deuxième entrée étant reliée à la sortie du registre 12, - trois registres à décalage 16, 17, et 18, de k bits, ayant une entrée série et une sortie parallèle, destinés à recevoir respectivement k bits du multiplicande A, un paramètre de calcul noté J0, un résultat intermédiaire noté Y0, l'entrée du registre 17 étant reliée à une troisième borne d'entrée, - deux circuits de multiplication 19 et 20 ayant chacun une entrée série, une entrée parallèle de k bits et une sortie série, - deux registres 21 et 22 de k bits ayant une entrée et une sortie parallèle, l'entrée du registre 21 étant relié à la sortie du registre 16, la sortie du registre 21 étant reliée à l'entrée du circuit de multiplication 19, la sortie du registre 22 étant reliée à l'entrée du circuit de multiplication 20, - un multiplexeur 23 à deux entrées parallèles et une sortie parallèle, une première entrée du multiplexeur 23 étant reliée à la sortie du registre 17, une deuxième entrée du multiplexeur 23 étant reliée à la sortie du registre 18, la sortie du multiplexeur 23 étant reliée à l'entrée du registre 22, - deux multiplexeurs 24, 25, ayant chacun deux entrées séries et une sortie série, la sortie du multiplexeur 24 étant reliée à l'entrée du registre 16, une première entrée du multiplexeur 24 étant reliée à une quatrième borne d'entrée, la sortie du multiplexeur 25 étant reliée à l'entrée série du circuit de multiplication 19, une première entrée du multiplexeur 25 étant reliée à un "0" logique, - un multiplexeur 26 comportant trois entrées série et une sortie, la sortie étant reliée à l'entrée série du circuit de multiplication 20, une première entrée étant reliée à un "0" logique, - trois circuits de soustraction 27, 28, et 29 comportant chacun deux entrées séries et une sortie série, la première entrée du circuit 27 étant reliée à la sortie du registre 10, la sortie du circuit 27 étant reliée à chacune des deuxièmes entrées des multiplexeurs 24 et 25 et également à une borne de sortie, la première entrée du circuit 28 étant reliée à la sortie du registre 11, - deux circuits d'addition 30 et 31, ayant chacun deux entrée séries et une sortie série, la première entrée du circuit 30 étant reliée à la sortie du circuit 28, la deuxième entrée du circuit 30 étant reliée à la sortie du circuit 19, la sortie du circuit 30 étant reliée à une deuxième entrée du multiplexeur 26, la sortie du circuit étant reliée à une première entrée du circuit 29 mais aussi à une deuxième entrée du multiplexeur 14 et également à chacune des troisièmes entrées des multiplexeurs 13 et 15, - trois cellules à retard 32, 33 et 34 qui sont en fait des registres à décalage de k bits, ayant une entrée et une sortie série, la sortie de la cellule 32 étant reliée d'une part à une troisième entrée du multiplexeur 26 et d'autre part à l'entrée de la cellule 33, la sortie de la cellule 33 étant reliée à une deuxième entrée du circuit 29, l'entrée de la cellule 34 étant reliée à la sortie du circuit 30, la sortie de la cellule 34 étant reliée à une première entrée du circuit 31, - un circuit de comparaison 35 ayant deux entrées série et deux sorties, une première entrée étant reliée à la sortie du circuit 31, une deuxième entrée étant reliée à la sortie du circuit 29, - deux multiplexeurs 36 et 37, chacun ayant deux entrées séries, une entrée de sélection, une sortie, chacune des premières entrées séries étant reliée à un "0" logique, chacune des entrées de sélection étant reliée à l'une des sorties du circuit 35, la sortie du multiplexeur 36 étant reliée à une deuxième entrée du circuit 27, la sortie du multiplexeur 37 étant reliée à une deuxième entrée du circuit 28, - un multiplexeur 38 ayant deux entrées et une sortie, une première entrée étant reliée à un "1" logique, une deuxième entrée étant reliée à la sortie du registre 12, la sortie étant reliée d'une part à l'entrée de la cellule 32 et d'autre part aux deuxièmes entrées des multiplexeurs 36 et 37, - un démultiplexeur 39 ayant une entrée et deux sorties, l'entrée étant reliée à la sortie du circuit 20, une première sortie étant reliée à l'entrée du registre 18, une deuxième sortie étant reliée à une deuxième entrée du circuit 31. Pour plus de détails sur la réalisation de certains éléments on peut se référer à D2. Pour réaliser une opération élémentaire dite PField du type PField(A, B)N = A * B * I mod N, A et B étant codés sur m mots de k bits, et I étant une erreur égale à 2-m*k, on réalise m fois l'itération de boucle suivante avec i un indice variant de 1 à m: X = S(i) + Ai-l * B, Yo = (X * J0) mod 2k, Z = X + (N * Yg) S(i) = Z \ 2k, \ étant une division entière, si S(i) est supérieur à N alors on soustrait N à S(i) avant la prochaine itération, avec S(0) = 0, Ai étant le mot de k bits de poids i, J0 étant un mot de k bits défini par l'équation ((N * J0) + 1) mod 2k = 0. Le coprocesseur de la figure 1 permet d'effectuer une itération complète par un décalage simultané de m * k bits des registres 10 à 12 contenant respectivement B, S(i-l) et N suivit d'un décalage de 2 * k bits du registre 12 pour mémoriser S(i), le mot Ai étant chargé dans le registre 21, et le mot J0 étant chargé dans le registre 17. Pour réaliser le calcul complet de PField(A, B)N, il suffit de répéter m fois chaque itération en changeant le mot Ai contenu dans le registre 21 lors de chaque itération. L'opération "X = S(i-l) + Ai * B" se fait à l'aide des circuits de multiplication 19 et d'addition 30. L'opération "Y0 = (X * J0) mod 2k" se fait, lors des k premier décalage, dans le circuit de multiplication 20, en ayant pris soin de mémoriser J0 dans registre 22, le résultat Y0 étant mémoriser dans le registre 18. L'opération "Z = X + (N * Y0)", N et X ayant été retardé de k bits dans les cellules à retard 32 et 34 et Yo ayant été mis dans le registre 22, s'effectue à l'aide des circuits de multiplication 20 et d'addition 31. L'opération "S(i) = Z \ 2k" est réalisée par décalage de k bits. La comparaison de S(i) avec N s'effectue par la soustraction de N à S(i) dans le circuit de soustraction 29, N étant retardé de k bits dans la cellule 33, un éventuel débordement étant détecté et mémorisé dans le circuit de comparaison 35 pour connaître le résultat de la comparaison. La soustraction de N à S(i) se faisant lors de l'itération suivante dans le circuit de soustraction 28. Le coprocesseur décrit dans D2 présente comme inconvénient de réaliser des calculs de manière figée sur des nombre soit de 256 bits soit de 512 bits. Une première amélioration dévoilée dans la demande de brevet EP-A-0 712 071 (document D3) vise à apporter un plus grande souplesse d'utilisation en permettant de réaliser des opérations Pfield(A, B)N avec A de taille variable. Une deuxième amélioration, dévoilée dans la demande de brevet EP-A-0 784 262 (document D4) vise à diminuer les échanges de données entre le coprocesseur et l'extérieur durant la réalisation d'opérations modulaires par l'ajout d'un registre supplémentaire de m * k bits pour mémoriser A de manière intégrale lorsque A est de taille inférieure à m * k bits. Par ailleurs, on connaît des registres à décalage de m * k bits organisés en banque de m sous-registres de k bits qui permettent afin de diminuer la consommation desdits registres. La consommation est réduite car au plus 2 * k cellules de mémorisation sont utilisées simultanément. L'homme du métier connaît de tels registres par la demande de brevet faite en France le 4 juillet 1997 qui a reçu le numéro de dépôt 97-08516. Un inconvénient des registres organisés en banque de sousregistres est qu'ils occupent une surface de silicium plus importante que des registres classiques. Un but de l'invention est de réduire la taille du circuit tout en utilisant des registres organisés en banque de sous-registres. L'invention propose de supprimer les cellules à retard 32 et 34 afin de gagner en surface d'occupation grâce à un nouveau séquencement du coprocesseur. L'invention a pour objet un procédé de mise en oeuvre d'une opération élémentaire, dite Pfield, définie par la méthode de Montgomery par Pfield(A, B)N = A * B * I mod N, A, B et N étant des entiers codés sur respectivement a, b et n mots de k bits, N étant impair, b et n étant des entiers non-nuls inférieurs ou égaux à un entier m, a et m étant des entiers non nuls, le procédé mettant en oeuvre un premier registre de k bits destiné à recevoir de manière successive des mots Ail de k bits de A, un deuxième registre à décalage de m * k bits destiné à mémoriser B, un troisième registre à décalage de m * k bits destiné à mémoriser un résultat actualisé noté S(i), un quatrième registre à décalage de m * k bits destiné à mémoriser N, les deuxième à quatrième registres étant organisés en banque de m sousregistres permettant des décalages par mot de k bits, caractérisé en ce que l'on effectue un premier décalage de k bits des mots de poids le plus faible des deuxième à quatrième registres dans des moyens de calcul pour produire en série une donnée intermédiaire Y0 = ((-No~lmod 2k) * (B * Ai~l + S(i-l))) mod 2k que l'on ((-N0 mod 2k) Aiî S(i-l))) que mémorise dans un cinquième registre de k bits; puis l'on effectue un deuxième décalage de n * k bits de la totalité des mots B, S(i-l) et N contenus dans les deuxième à quatrième registres vers les moyens de calcul pour produire en série la donnée actualisé S(i). Préférentiellement, on répète a fois des étapes El à E3 suivantes, i étant un indice entier variant de 1 à a qui est incrémenté à l'issue de chaque répétition d'étapes: Etape El: calcul de Y0 : on décale de k bits les mots de poids le plus faible de respectivement B, S(i-l) et N contenu dans les deuxième à troisième registres, chacun des registres ayant son entrée reliée à sa sortie afin de conserver le mot de k bits dans un même sousregistre après l'avoir fourni; pendant les décalages; on produit Ai-l * Bo dans un premier circuit de multiplication; on soustrait Ng à S(i-l)0 dans un premier circuit de soustraction si S(i-l) est supérieur à N; on produit les k bits de poids faible de X = S(i-l) + Ai * B dans un premier circuit d'addition en additionnant le résultat sortant du premier circuit de multiplication avec le résultat sortant du premier circuit de soustraction; on produit Y0 en multipliant les k bits de poids faible de X par -N0~1mod 2k dans un deuxième circuit de multiplication, le résultat sortant du circuit de multiplication étant stocké dans le cinquième registre; Etape E2: calcul de S(i): on décale simultanément de n * k bits les contenus des deuxième à quatrième registres; le premier circuit de multiplication réalisant la multiplication B * Ai~l; on soustrait N à S(i-l) dans le premier circuit de soustraction si S(i-l) est supérieur à N; on produit X = S(i-l) + Ai * B dans le premier circuit d'addition en additionnant le résultat sortant du premier circuit de multiplication avec le résultat sortant du premier circuit de soustraction; on produit X * Y0 dans le deuxième circuit de multiplication; on produit Z = X + (N * Yg) dans un deuxième circuit d'addition en additionnant le résultat sortant du deuxième circuit de multiplication avec le résultat sortant du premier circuit d'addition les k premiers bits sortant du deuxième circuit d'addition étant ignorés, on stocke le nouveau résultat actualisé S(i) dans le troisième registre 11, le mot Z1 de k bits correspondant au deuxième mot de poids faible de Z devenant le mot de poids le plus faible du résultat actualisé S(i); Etape E3: comparaison de S(i) avec N: on compare S(i) avec N et on mémorise le résultat de la comparaison à l'aide de moyens de comparaison, le résultat de la comparaison de N avec S(i) étant à prendre en compte lors de la prochaine répétition des étapes A et B; L'invention sera mieux comprise et d'autres particularités et avantages apparaîtront à la lecture de la description qui va suivre, la description faisant référence aux dessins annexés parmi lesquels: la figure 1 représente un coprocesseur selon l'art antérieur, les figures 2 et 3 représentent des coprocesseurs selon l'invention. Le schéma de la figure 2 comporte - trois registres à décalage 10, 11, et 12, de m * k bits, ayant une entrée et une sortie série, destinés à recevoir respectivement le multiplieur B, le résultat S, et le modulo N, chacun des registres étant organisé en banque de m sous-registres de k bits 10-1 à 10-m, 11-1 à ll-m et 12-1 à 12-m à décalage dont les entrées sont groupées ensemble pour former l'entrée respectivement des registres 10, 11 et 12, et les sorties des sous-registres 10-1 à 10-m, 11-1 à ll-m et 12-1 à 12-m étant connectées respectivement à trois multiplexeurs à m entrées 100, 110 et 120 respectivement, la sortie de chaque multiplexeur 100, 110, et 120 formant la sortie de chacun des registres 10, 11 et 12, - trois multiplexeurs 13, 14 et 15 à quatre entrées série et une sortie série, une première entrée de chacun des multiplexeurs 13, 14 et 15 étant connectée à une borne d'entrée Din, une deuxième entrée de chacun des multiplexeurs 13, 14 et 15 recevant un "0" logique, une troisième entrée de chacun des multiplexeurs 13, 14 et 15 étant connectée respectivement à la sortie de chacun des registres 10, 11 et 12, la sortie de chacun des multiplexeurs 13, 14 et 15 étant connectée respectivement à l'entrée de chacun des registres 10, 11 et 12, - trois registres à décalage 16, 17, et 18, de k bits, ayant une entrée série et une sortie parallèle, destinés à recevoir respectivement k bits du multiplicande A, un paramètre de calcul noté Jo, un résultat intermédiaire noté Y0, l'entrée du registre 17 étant reliée à une troisième borne d'entrée, - deux circuits de multiplication 19 et 20 ayant chacun une entrée série, une entrée parallèle de k bits et une sortie série, - deux registres 21 et 22 de k bits ayant une entrée parallèle et une sortie parallèle, l'entrée du registre 21 étant relié à la sortie du registre 16, la sortie du registre 21 étant reliée à l'entrée du circuit de multiplication 19, la sortie du registre 22 étant reliée à l'entrée du circuit de multiplication 20, - un multiplexeur 23 à deux entrées parallèles et une sortie parallèle, une première entrée du multiplexeur 23 étant reliée à la sortie du registre 17, une deuxième entrée du multiplexeur 23 étant reliée à la sortie du registre 18, la sortie du multiplexeur 23 étant reliée à l'entrée du registre 22, - deux multiplexeurs 24, 25, ayant chacun deux entrées séries et une sortie série, la sortie du multiplexeur 24 étant reliée à l'entrée du registre 16, une première entrée du multiplexeur 24 étant reliée à une borne d'entrée Din, la sortie du multiplexeur 25 étant reliée à l'entrée série du circuit de multiplication 19, une première entrée du multiplexeur 25 recevant un "0" logique, - un multiplexeur 26 comportant trois entrées série et une sortie, la sortie étant reliée à l'entrée série du circuit de multiplication 20, une première entrée recevant un "0" logique, - trois circuits de soustraction 27, 28, et 29 comportant chacun deux entrées séries et une sortie série, la première entrée du circuit 27 étant reliée à la sortie du registre 10, la sortie du circuit 27 étant reliée aux deuxièmes entrées des multiplexeurs 24 et 25 et également à une borne de sortie Dout, la première entrée du circuit 28 étant reliée à la sortie du registre 11, - deux circuits d'addition 30 et 31, ayant chacun deux entrée séries et une sortie série, la première entrée du circuit 30 étant reliée à la sortie du circuit 28, la deuxième entrée du circuit 30 étant reliée à la sortie du circuit 19, la sortie du circuit 30 étant reliée à une deuxième entrée du multiplexeur 26 et à une première entrée du circuit 31, la sortie du circuit 31 étant reliée à une première entrée du circuit 29 mais aussi aux quatrièmes entrées des multiplexeurs 13, 14 et 15, - une cellule à retard 33 qui est en fait un registre à décalage de k bits, ayant une entrée et une sortie série, la sortie de la cellule 33 étant reliée à une deuxième entrée du circuit 29, - un circuit de comparaison 35 ayant deux entrées série et deux sorties, une première entrée étant reliée à la sortie du circuit 31, une deuxième entrée étant reliée à la sortie du circuit 29, - deux multiplexeurs 36 et 37, chacun ayant deux entrées séries, une sortie, chacune des premières entrées séries étant reliée à un "0" logique, chacun multiplexeurs 36 et 37 étant commandé par l'une des sorties du circuit 35 (non représenté sur le schéma), la sortie du multiplexeur 36 étant reliée à une deuxième entrée du circuit 27, la sortie du multiplexeur 37 étant reliée à une deuxième entrée du circuit 28, - un multiplexeur 38 ayant deux entrées série et une sortie série, une première entrée étant reliée à un "1" logique, une deuxième entrée étant reliée à la sortie du registre 12, la sortie étant reliée d'une part à l'entrée de la cellule 33 et d'autre part aux deuxièmes entrées des multiplexeurs 36 et 37 et à une troisième entrée du multiplexeur 26, - un démultiplexeur 39 ayant une entrée série et deux sorties série, l'entrée étant reliée à la sortie du circuit 20, une première sortie étant reliée à l'entrée du registre 18, une deuxième sortie étant reliée à une deuxième entrée du circuit 31. Pour le coprocesseur de la figure 2, on utilise une unique borne d'entrée pour charger les données dans les registres 10, 11, 12, 16 et 17. Il est tout à fait possible d'utiliser cinq bornes d'entrée si l'on désire effectuer le chargement simultané de toutes les données dans tous les registres 10, 11, 12, 16 et 17. Pour expliquer le fonctionnement d'un tel circuit lors de la mise en oeuvre d'une opération de type PField(A, B)N = A * B * I mod N, il convient de poser A un entier codé sur a mots de k bits, B un entier codé sur b mots de k bits, N un entier impair codé sur n mots de k bits, a, b et n étant des entiers positifs, b et n étant inférieurs ou égaux à m. De plus, b est forcément inférieur ou égal à n. Le circuit doit d'abord être initialise: - on charge B dans le registre 10, le mot de poids le plus faible de B étant par exemple dans le sousregistre 10-1; - on charge N dans le registre 12, le mot de poids le plus faible de N étant par exemple dans le sousregistre 12-1; - on initialise à "0" le registre 11, le contenu étant appelé S(0) et étant codé sur n mots de k bits; - on charge un paramètre de calcul J0 dans le registre 17, Jg étant calculé au préalable et étant égal à -No - lmod 2k - on initialise le circuit de comparaison afin que les multiplexeurs 36 et 37 aient leurs sorties qui fournissent un "0" logique; - on charge le mot Ag, correspondant au mot de k bits de poids le plus faible de A, dans le registre 16. L'initialisation du circuit peut être à faire uniquement partiellement. En effet, à l'issue d'un calcul, le coprocesseur contient des données qui peuvent être réutilisée en étant déjà dans le bon registre. Pour mettre en oeuvre l'opération élémentaire PFieldl on répète a fois les étapes 1 à 6 suivantes, i étant un indice entier variant de 1 à a qui est incrémenté à l'issue de chaque répétition d'étapes: Etape 1: on charge Ail dans le registre 21, et on charge Jo dans le registre 22; on initialise les circuits d'addition 30 et 31, de soustraction 27 à 29 et de multiplication 19 et 20; Etape 2: calcul de Yo : - on décale de k bits les contenus des sousregitres 10-1, 11-1 et 12-1, correspondant au mot de poids le plus faible de respectivement B, S(i-l) et N, chacun des registres ayant son entrée reliée à sa sortie afin de conserver le mot de k bits dans le même sousregistre 10-1, 11-1 et 12-1 après l'avoir fourni; - pendant les décalages; on produit Ail * Bg dans le circuit de multiplication 19; on soustrait Ng à S(i-l)0 dans le circuit de soustraction 28 si S(i-l) est supérieur à N; on produit les k bits de poids faible de X = S(i-l) + Ai * B dans le circuit d'addition 30 en additionnant le résultat sortant du circuit de multiplication 19 avec le résultat sortant du circuit de soustraction 28; on produit Y0 en multipliant les k bits de poids faible de X par J0 dans le circuit de multiplication 20, le résultat sortant du circuit de multiplication 20 étant stocké dans le registre 18; Etape 3: on charge Y0 dans le registre 22; on initialise les circuits d'addition 30 et 31, de soustraction 27 à 29 et de multiplication 19 et 20; Etape 4: calcul de S(i): - on décale simultanément de n * k bits les contenus des registres 10, 11 et 12; le circuit de multiplication 19 réalisant la multiplication B * Ai~l; on soustrait N à S(i-l) dans le circuit de soustraction 28 si S(i-l) est supérieur à N; on produit X = S(i-l) + Ai * B dans le circuit d'addition 30 en additionnant le résultat sortant du circuit de multiplication 19 avec le résultat sortant du circuit de soustraction 28; on produit X * Yo dans le circuit de multiplication 20; on produit Z = X + (N * Y0) dans le circuit d'addition 31 en additionnant le résultat sortant du circuit de multiplication 20 avec le résultat sortant du circuit d'addition 30 les k premiers bits sortant du circuit d'addition 31 étant ignorés, on stocke S(i) dans le registre 11, le mot Z1 de k bits correspondant au deuxième mot de poids faible de Z devenant le mot de poids le plus faible de S(i) stocké dans le sous-registre 11-1; Etape 5: comparaison de S(i) avec N: - on soustrait N retardé de k bits au résultat sortant du circuit d'addition 31 dans le circuit de soustraction 29; le circuit de comparaison 35 contrôle mémorise l'état de la retenu du circuit de soustraction 29, la retenu correspondant au résultat de la comparaison de N avec S(i) étant à prendre en compte lors de la prochaine répétition des étapes 2 et 4; Etape 6: pendant le déroulement des étapes 2 à 5, on charge le mot Ai dans le registre 16. Pour obtenir le résultat final, on décale le contenu des registres 11 et 12 et l'on soustrait N à S(a) si S(a) est supérieur ou égal à N, le résultat étant ensuite stocké dans le registre 10 si on désire le sortir du coprocesseur ou dans un autre registre 10 à 12 si l'on désire l'utiliser dans un prochain calcul. Il est à noter que pour le procédé décrit, l'erreur I est égale à 2-a*k On peut remarquer que, dans le procédé de l'invention, on produit deux fois le mot X0 de manière consécutive. La double production du mot X0 permet de supprimer la cellule de retard qui avait pour fonction de retarder X pendant une durée égale au calcul de Y0 soit une première économie de k cellules élémentaires de registre. I1 en est de même pour la double sortie du mot Ng qui sert la première fois au calcul de X0 et Y0 et la deuxième fois au calcul de X et Z. La double sortie du mot Ng permet de supprimer la cellule de retard qui avait pour fonction de retarder N pendant une durée égale au calcul de Yo soit une deuxième économie de k cellules élémentaires de registre. Des variantes sont possibles sur le coprocesseur. Le schéma de la figure 3 met en oeuvre quelques améliorations possibles. Sur le coprocesseur de la figure 3, la sortie du circuit de soustraction 28 n'est plus connectée directement à la première entrée du circuit d'addition 30, les autres éléments du coprocesseur de la figure 2 restant inchangés. Le coprocesseur de la figure 3 comporte en outre: - un registre à décalage 40 de m * k bits, ayant une entrée et une sortie série, destinés à recevoir la donnée A, le registre étant organisé en banque de m sousregistres de k bits 40-1 à 40-m à décalage dont les entrées sont groupées ensemble pour former l'entrée du, et les sorties des sous-registres 40-1 à 40-m étant connectées à un multiplexeur à m entrées 400, la sortie du multiplexeur 400 formant la sortie du registre 40, - un multiplexeur 41 à quatre entrées série et une sortie série, une première entrée étant connectée à une borne d'entrée Din, une deuxième entrée recevant un "0" logique, une troisième entrée étant connectée à la sortie du registre 40, la quatrième entrée étant connectée à la sortie du circuit d'addition 31, et la sortie étant connectée à l'entrée du registre 40, - un multiplexeur 42 à deux entrées série et une sortie série, une première entrée étant connectée à la sortie du circuit de soustraction 28, une deuxième entrée recevant un "0" logique, et la sortie étant connectée à la première entrée du circuit d'addition 30. Le registre 40 sert à stocker A afin d'éviter des échanges de données avec l'extérieur lorsque a est inférieur ou égal à m. Il va de soi que l'ajout ne change pas le déroulement des étapes mises en oeuvre précédemment mais il faut prévoir le chargement de ce registre de manière préalable. Le multiplexeur 42 sert à envoyer des "0" logiques lors de la première mise en oeuvre des étapes 1 à 6. L'utilisation de ce multiplexeur 42 permet d'éviter d'avoir à initialiser le registre 11. Par ailleurs, d'autres fonctionnalités peuvent être implémentées sur le coprocesseur des figures 2 ou 3. L'implémentation peut se traduire par l'ajout de circuits supplémentaires sur les chemins de données représentés. L'invention n'est pas remise en cause dans la mesure où les éléments ajoutés permettent de mettre en oeuvre le procédé décrit précédemment. D'autre part, l'homme du métier sait que les circuits d'addition 30 et 31 et de soustraction 27 à 29 entraînent des retards dont il n'a pas été tenus compte dans la présente demande. Des cellules élémentaires de retard sont donc à prévoir, comme pour les circuits de l'art antérieur, afin d'assurer une bonne synchronisation des chemins de données entre eux. Des variantes sont possibles au niveau du formats des données. Les registres 11, 12, 13 et 40 sont des registres de m * k bits configurables en registres de taille multiple de k bits. Il est possible de figer la taille de ces registres à la taille maximum ce qui entraîne une perte de temps mais permet de simplifier le séquencement à effectuer. Si l'on utilise une taille figée, on prendra soin de REVENDICATIONS 1. Procédé de mise en oeuvre d'une opération élémentaire, dite Pfield, définie par la méthode de Montgomery par Pfield(A, B)N = A * B * I mod N, A, B et N étant des entiers codés sur respectivement a, b et n mots de k bits, N étant impair, b et n étant des entiers nonnuls inférieurs ou égaux à un entier m, a et m étant des entiers non nuls, le procédé mettant en oeuvre un premier registre (21) de k bits destiné à recevoir de manière successive des mots Ail de k bits de A, un deuxième registre (10) à décalage de m * k bits destiné à mémoriser B, un troisième registre (11) à décalage de m * k bits destiné à mémoriser un résultat actualisé noté S(i), un quatrième registre (12) à décalage de m * k bits destiné à mémoriser N, les deuxième à quatrième registres (10 à 12) étant organisés en banque de m sous-registres (10-1 à 10-m, 11-1 à 1l-m, 12-1 à 12-m) permettant des décalages par mot de k bits, caractérisé en ce que - on effectue un premier décalage de k bits des mots de poids le plus faible des deuxième à quatrième registres (10 à 12) dans des moyens de calcul (19, 20, 28, 30) pour produire en série une donnée intermédiaire Y0 = ((-N0-1mod 2k) * (B * Ail + S(i-l))) mod 2k que l'on mémorise dans un cinquième registre (18) de k bits; - on effectue un deuxième décalage de n * k bits de la totalité des mots B, S(i-l) et N contenus dans les deuxième à quatrième registres (10 à 12) vers les moyens de calcul pour produire en série la donnée actualisé S(i) 2. Procédé selon la revendication 1, caractérisé en ce que on répète a fois des étapes El à E3 suivantes, i étant un indice entier variant de 1 à a qui est incrémenté à l'issue de chaque répétition d'étapes: Etape El: calcul de Yo - on décale de k bits les mots de poids le plus faible de respectivement B, S(i-l) et N contenu dans les deuxième à troisième registres (10 à 12), chacun des registres ayant son entrée reliée à sa sortie afin de conserver le mot de k bits dans un même sous-registre (10-1, 11-1 et 12-1) après l'avoir fourni; - pendant les décalages; on produit Ail * Bg dans un premier circuit de multiplication (19); on soustrait Ng à S(i-l)0 dans un premier circuit de soustraction (28) si S(i-l) est supérieur à N; on produit les k bits de poids faible de X = S(i-l) + Ai * B dans un premier circuit d'addition (30) en additionnant le résultat sortant du premier circuit de multiplication (19) avec le résultat sortant du premier circuit de soustraction (28); on produit Y0 en multipliant les k bits de poids faible de X par -Ng-lmod 2k dans un deuxième circuit de multiplication (20) , le résultat sortant du circuit de multiplication (20) étant stocké dans le cinquième registre (18); Etape E2: calcul de S(i): - on décale simultanément de n * k bits les contenus des deuxième à quatrième registres (10, 11 et 12); le premier circuit de multiplication (19) réalisant la multiplication B * Ai~l; on soustrait N à S(i-l) dans le premier circuit de soustraction (28) si S(i-l) est supérieur à N; on produit X = S(i-l) + Ai * B dans le premier circuit d'addition (30) en additionnant le résultat sortant du premier circuit de multiplication (19) avec le résultat sortant du premier circuit de soustraction (28); on produit X * Y0 dans le deuxième circuit de multiplication (20); on produit Z = X + (N * Y0) dans un deuxième circuit d'addition (31) en additionnant le résultat sortant du deuxième circuit de multiplication (20) avec le résultat sortant du premier circuit d'addition (30) les k premiers bits sortant du deuxième circuit d'addition (31) étant ignorés, on stocke le nouveau résultat actualisé S(i) dans le troisième registre 11, le mot Z1 de k bits correspondant au deuxième mot de poids faible de Z devenant le mot de poids le plus faible du résultat actualisé S(i); Etape E3: comparaison de S(i) avec N: - on compare S(i) avec N et on mémorise le résultat de la comparaison à l'aide de moyens de comparaison (29, 33, 35), le résultat de la comparaison de N avec S(i) étant à prendre en compte lors de la prochaine répétition des étapes A et B;