FR 2791156 A1 20000922 FR 9903409 A 19990317 Dispositif et procédé de mise en oeuvre d'une opération modulaire élémentaire selon la méthode de Montgomery. L'invention concerne un dispositif et un procédé de mise en oeuvre d'une opération modulaire élémentaire selon la méthode de Montgomery. La méthode de Montgomery permet d'effectuer des calculs modulaires dans un corps fini (ou corps de Galois) sans effectuer de divisions. Classiquement, les opérations modulaires dans les corps finis sont utilisées en cryptographie pour des applications telles que l'authentification de messages, l'identification d'un utilisateur ou 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 (ci-après D1). On trouve dans le commerce des circuits intégrés dédiés à de telles applications, par exemple le produit fabriqué par STMicroelectronics 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. Il fait l'objet de la demande de brevet EP-A-0 601 907 (ci-après 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 et k des entiers tels que 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'arithmé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, destinés à recevoir respectivement le multiplieur B, le résultat S, et le modulo N, - des multiplexeurs 13 à 15 qui dont les sorties sont reliées respectivement aux entrées des registres 10 à 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, - 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 bascules parallèles 21 et 22 de k bits qui servent de tampon aux circuits de multiplication 19 et , - un multiplexeur 23 qui sert à relier la bascule 22 soit au registre 17, soit au registre 18, - trois multiplexeurs 24, 25 et 26 servant à aiguiller les données sur les entrées des circuits de multiplication 19 et 20, - trois circuits de soustraction 27, 28, et 29 comportant chacun deux entrées séries et une sortie série, deux circuits d'addition 30 et 31, ayant chacun deux entrées séries et une sortie série, - trois cellules à retard 32, 33 et 34 qui sont en fait des registres à décalage de k bits, et qui servent à retarder les données de k cycles d'horloge pour masquer le temps de calcul des circuits de multiplication 19 et , - un circuit de comparaison 35, - deux multiplexeurs 36 et 37 qui permettent le contrôle des circuits de soustraction 27 et 28, - un multiplexeur 38, et - un démultiplexeur 39. Pour plus de détails sur la réalisation de ces é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-mik, on réalise m fois l'itération de boucle suivante avec i un indice variant de 0 à m-1: X = S(i-1) + Ai * B, Y0 = (X * J0) mod 2k, Z = X + (N * Y0) 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(-l) = 0, Ai étant le i-ième mot de k bits de A, 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 qui contiennent respectivement B, S(i-1) et N suivi 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-1) + 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 premiers décalages, dans le circuit de multiplication 20, en ayant pris soin de mémoriser J0 dans la bascule 22, le résultat Y0 étant mémorisé dans le registre 18. L'opération " Z = X + (N * Y0) ", N et X ayant été retardés 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. De nombreuses améliorations ont été réalisées sur ce circuit, les améliorations ayant pour but d'aller plus vite et/ou de réduire la taille du circuit et/ou de réduire la consommation du circuit et/ou d'apporter des fonctionnalités supplémentaires sans augmenter la taille du circuit de manière considérable. L'homme du métier peut se reporter entre autre aux publications des demandes de brevets européens EP - 0 712 070, EP - 0 712 071, EP - 0 712 072, EP - 0 778 518, EP - 0 784 262, EP - 0 785 502, EP - 0 785 503, EP - 0 793 165, EP - 0 853 275, et également à la publication de la demande de brevet internationale WO/97 25668. Il est également connu, de la publication de la demande de brevet européen EP - 0 566 498 (ci-après D3), un autre circuit permettant de calculer l'opération élémentaire P(A, B)N = A * B * I mod N, avec I = 2-n et n la taille de A, B ou N. Le circuit de D3 utilise un unique circuit de multiplication parallèle/série, représenté dans D3 sous la forme d'un additionneur parallèle couplé à un registre à décalage. Le circuit de D3 ne reproduit pas exactement l'algorithme de Montgomery et utilise une donnée intermédiaire égale à (N-1)/2+1. Le circuit de D3 utilise un circuit de multiplication disposant d'une entrée parallèle de n bits et se limite à des opérandes de calcul de taille figée. Par ailleurs, la taille du circuit de D3 est proportionnelle à la taille des opérandes utilisés, la surface ainsi occupée étant considérable. La présente invention a pour but d'améliorer l'état de la technique en proposant un coprocesseur utilisant un unique circuit de multiplication couplé à un circuit de calcul dédié au calcul de Y0, avec Y0 = (X * J0) mod 2k, J0 étant défini par l'équation ((N * J0) + 1) mod 2k = 0. Le calcul de Y0 s'effectue selon l'invention bit par bit, un demi-cycle d'horloge avant l'utilisation de chaque bit. L'invention propose également un procédé de calcul d'une opération modulaire utilisant le circuit de calcul de Y0. L'invention a pour objet un circuit intégré comprenant un coprocesseur (200) d'arithmétique modulaire comportant des moyens de mémorisation (201 à 204) pour Is mémoriser et fournir en série des premier et deuxième opérandes A et B, un modulo N et un résultat S, avec A un entier codé sur a * k bits, a étant un entier non nul au plus égal à m, et avec B, N et S des entiers codés sur au plus m * k bits, m et k étant des entiers supérieurs à 1 ; des moyens de calcul pour effectuer des opérations modulaires selon la méthode de Montgomery, caractérisé en ce que les moyens de calcul comportent une première sortie pour fournir bit à bit un résultat actualisé S(i) et une deuxième sortie pour fournir un résultat anticipé, et en ce que ledit coprocesseur comporte en outre un circuit de calcul qui reçoit le résultat anticipé et qui produit une donnée intermédiaire Y0 qui est réinjectée dans les moyens de calcul pour produire le résultat actualisé S(i). Préférentiellement, le circuit pour calculer la donnée Y0 comporte une bascule synchronisée sur les fronts inutilisés par les moyens de calcul, ladite bascule servant à mémoriser un bit de Y0; des moyens pour fournir zéro pendant un premier demi-cycle d'un signal d'horloge et pour fournir le bit mémorisé par la bascule pendant un deuxième demi-cycle du signal d'horloge. L'invention a également pour objet un procédé pour effectuer une opération modulaire selon la méthode de Montgomery par décalage en série de premier et deuxième opérandes A et B, d'un modulo N et d'un résultat actualisé à travers des moyens de calcul, avec A un entier codé sur a * k bits, a étant un entier non nul au plus égal à m, et avec B, N et S des entiers codés sur au plus m * k bits, m et k étant des entiers supérieurs à 1, dans lequel on calcule une donnée intermédiaire Y0 telle que Y0 = ((S(i-1) + (Ai * B)) * J0) mod 2k dans une boucle itérative indicée par i, i variant de 0 à a-1, avec S(i-1) qui correspond au (i-1)-ième résultat actualisé, S(-1) étant égal à 0, Ai étant le i-ième mot de k bits de A, et J0 étant un mot de k bits résolvant l'équation ((J0 * N) + 1) mod 2k = 0 caractérisé en ce que Y0 est fourni par un circuit de calcul (240) qui calcule chaque bit de Y0 pendant un demi-cycle d'une période d'horloge qui précède l'utilisation dudit chaque bit de Y0. Préférentiellement, ledit procédé comporte en outre la répétition des étapes suivantes, i étant un indice variant de 0 à a-1: - mémorisation d'un mot Ai de k bits correspondant à un mot de poids i de A dans une première bascule (226) de k bits; - mémorisation du mot de k bits de poids faible de N puis de Y0 dans une deuxième bascule (226) de k bits; addition dans un circuit parallèle d'addition (227) des mots contenus dans les première et deuxième bascules (225, 226); - sélection et fourniture soit du mot contenu dans la première bascule (225), soit du mot contenu dans la deuxième bascule (226), soit de la somme des mots contenus dans les première et deuxième bascules (225, 226), ou soit du mot zéro, en fonction d'une part d'un bit de B, et d'autre part soit d'un bit de Y0 soit d'un bit de N; - additions successives dans un circuit accumulateur (231) des mots fournis par le dispositif de sélection (228) pour chaque paire de bits de B et de N, le résultat de chaque addition étant additionné à un bit du précédent résultat actualisé S(i-1) puis décalé d'un bit et mémorisé entre chaque addition, le bit sortant de l'accumulateur (231) lors du décalage correspondant à un nouveau résultat actualisé S(i). 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 d'arithmétique modulaire selon l'état de la technique, la figure 2 représente un coprocesseur d'arithmétique modulaire selon l'invention, et les figures 3 à 7 représentent de manière détaillée différents éléments du coprocesseur de la figure 2. La figure 1 ayant été décrite précédemment et représentant l'état de la technique, elle ne sera pas décrite plus en détail. La figure 2 représente le coprocesseur 200 d'arithmétique modulaire, selon un mode préféré de réalisation. Afin de ne pas surcharger le schéma, seul le cheminement des données a été représenté sur cette figure 2. Une machine d'état (non représentée) envoie les signaux de commande nécessaires aux différents éléments fonctionnels du coprocesseur 200. Le coprocesseur 200 comporte les éléments suivants: - Des premier à quatrième dispositifs de mémorisation 201 à 204 contiennent respectivement des données A, B, N et S. Les données A, B, N et S sont des données codées sur au plus m mots de k bits. Les dispositifs de mémorisation 201 à 204 permettent de fournir de manière indépendante n'importe quel mot de k bits de la donnée mémorisée. Chaque dispositif de mémorisation 201 à 204 dispose de première et deuxième entrées séries et d'une sortie de donnée de type série. La première entrée de chaque dispositif de mémorisation 201 à 204 est connectée à une borne d'entrée Din. - Des premier et deuxième circuits de soustraction 205 et 206 de type série disposent de première et deuxième entrées et d'une sortie de type série. La première entrée du premier circuit de soustraction 205 est connectée à la sortie du deuxième dispositif de I0 mémorisation 202. La première entrée du deuxième circuit de soustraction 206 est connectée à la sortie du quatrième dispositif de mémorisation 204. - Des premier et deuxième multiplexeurs 207 et 208 sont couplés respectivement aux deuxièmes entrées des premier et deuxième circuits de soustraction 205 et 206. Les premier et deuxième multiplexeurs 207 et 208 disposent de deux entrées chacun, l'une des entrées recevant un "zéro" logique, et l'autre des entrées étant connectée à la sortie du troisième dispositif de mémorisation 203. L'association des premier et deuxième circuits de soustraction 205 et 206 avec les premier et deuxième multiplexeurs 207 et 208 permet de soustraire soit "zéro" soit la donnée sortante du troisième dispositif de mémorisation 203 aux données sortantes des deuxième et quatrième dispositifs de mémorisation 202 et 204. - Des premier à quatrième circuits de retard 211 à 214 servent à synchroniser les données en les retardant d'un cycle du signal d'une horloge de cadencement. Chacun des circuits de retard 211 à 214 dispose d'une entrée et d'une sortie, chaque circuit de retard étant par exemple constitué d'une simple bascule synchrone de type D. L'entrée du premier circuit de retard 211 est connectée à la sortie du premier circuit de soustraction 205. L'entrée du deuxième circuit de retard 212 est connectée à la sortie du troisième dispositif de mémorisation 203. L'entrée du troisième circuit de retard 213 est connectée à la sortie du deuxième circuit de retard 212. L'entrée du quatrième circuit de retard 214 est connectée à la sortie du deuxième circuit de soustraction 206. - Un premier registre 221 à décalage de k bits dispose d'une entrée série, d'une sortie série et d'une sortie parallèle. Ce premier registre 221 sert d'une part de registre tampon pour les mots de A et d'autre part de retardateur de k cycles d'horloge pour N. - Un deuxième registre 222 à décalage de k bits dispose d'une entrée série et d'une sortie parallèle. Ce deuxième registre 222 sert d'une part de registre tampon pour le mot No de poids le plus faible de N et d'autre part pour une donnée intermédiaire Y0. - Un troisième multiplexeur 223 est associé au premier registre 221. Le troisième multiplexeur 223 dispose de trois entrées et d'une sortie, la sortie étant connectée à l'entrée du premier registre 221. L'une des entrées du troisième multiplexeur 223 est connectée à la sortie du premier dispositif de mémorisation 201. Une autre des entrées du troisième multiplexeur est connectée à la sortie du premier circuit de soustraction 205. La dernière des entrées du troisième multiplexeur 223 est connectée à la sortie du troisième circuit de retard 213. - Un quatrième multiplexeur 224 est associé au deuxième registre 222. Le quatrième multiplexeur 224 dispose de première et deuxième entrées et d'une sortie, la sortie étant connectée à l'entrée du deuxième registre 222. La première entrée du quatrième multiplexeur 224 est connectée à la sortie du troisième circuit de retard 213. - Des première et deuxième bascules 225 et 226 à verrouillage de k bits servent à mémoriser, pendant le calcul, d'une part un mot de A et d'autre part le mot No de poids le plus faible de N ou la donnée intermédiaire Y0. Chacune des bascules 225 et 226 comporte une entrée parallèle et une sortie parallèle, les entrées des première et deuxième bascules 225 et 226 étant respectivement connectées aux sorties parallèles des premier et deuxième registres 221 et 222. - Un circuit d'addition 227, disposant de deux entrées parallèles et d'une sortie parallèle, a ses deux entrées connectées respectivement aux sorties des première et deuxième bascules 225 et 226. La sortie du circuit d'addition 227 fournit ainsi la somme des contenus des première et deuxième bascules 225 et 226. - Un dispositif de sélection 228 est connecté aux sorties des première et deuxième bascules 225 et 226 et à la sortie du circuit d'addition 227 afin de pouvoir fournir sur une sortie parallèle soit le contenu de la première bascule 225, soit le contenu de la deuxième bascule 226, soit la somme des contenus des première et deuxième bascules 225 et 226, soit " zéro ". Le dispositif de sélection 228 dispose en outre de première et deuxième entrées de sélection qui reçoivent respectivement un premier signal de sélection SELA et un deuxième signal de sélection SELY. Lorsque les premier et deuxième signaux SELA et SELY de sélection sont tous deux à un niveau logique "zéro", alors la sortie du dispositif de sélection 228 fournit sur sa sortie le nombre zéro codé sur k + 1 bits. Lorsque le premier signal de sélection SELA est à un niveau logique " un " et que le deuxième signal de sélection SELY est à un niveau logique " zéro ", alors la sortie du dispositif de sélection 228 fournit sur sa sortie le contenu de la première bascule 225. Lorsque le premier signal de sélection SELA est à un niveau logique " zéro " et que le deuxième signal de sélection SELY est à un niveau logique " un ", alors la sortie du dispositif de sélection 228 fournit sur sa sortie le contenu de la deuxième bascule 226. Lorsque les premier et deuxième signaux SELA et SELY de sélection sont tous deux à un niveau logique " un ", alors la sortie du dispositif de sélection 228 fournit sur sa Il sortie la somme des contenus des première et deuxième bascules 225 et 226. - Un cinquième multiplexeur 229, disposant de deux entrées et d'une sortie, a sa sortie connectée à la première entrée de sélection du dispositif de sélection 228. L'une des entrées du cinquième multiplexeur 229 est connectée à la sortie du premier circuit de retard 211. L'autre des entrées du cinquième multiplexeur 229 reçoit un " zéro " logique. - Un sixième multiplexeur 230, disposant de première à troisième entrées et d'une sortie, a sa sortie connectée à la deuxième entrée de sélection du dispositif de sélection 228. La première entrée du sixième multiplexeur 230 reçoit un " zéro " logique. La deuxième entrée du sixième multiplexeur 230 est connectée à la sortie du troisième circuit de retard 213. Un circuit accumulateur 231 effectue une double multiplication par addition successive des mots sortant du dispositif de sélection 228. Le circuit accumulateur 231 comporte une entrée parallèle connectée à la sortie du dispositif de sélection 228, une entrée série connectée à la sortie du quatrième circuit de retard 214, une sortie de résultat et une sortie de résultat anticipé. Lors de chaque cycle de l'horloge de séquencement du coprocesseur 200, le circuit accumulateur additionne un bit présent à l'entrée série avec un mot présent à l'entrée parallèle et avec un résultat interne. Le nouveau résultat est ensuite décalé pour devenir un nouveau résultat interne. - Un septième multiplexeur 233 dispose de deux entrées et d'une sortie. L'une des entrées du septième multiplexeur 233 est connectée à la sortie de résultat du circuit accumulateur 231. La sortie du septième multiplexeur 233 est connectée aux deuxièmes entrées des dispositifs de mémorisation 201 à 204. - Un huitième multiplexeur 236 dispose de deux entrées et d'une sortie. L'une des entrées du huitième multiplexeur 236 est connectée à la sortie série du premier registre 221. L'autre des entrées du huitième multiplexeur 236 est connectée à la sortie série du premier circuit de retard 211. La sortie du huitième multiplexeur 236 est connectée à l'autre des entrées du septième multiplexeur 233. - Un circuit de comparaison 232 disposant de deux entrées compare bit à bit le résultat sortant du circuit accumulateur 231 avec la donnée qui sort en série du huitième multiplexeur 236. Le résultat de la comparaison est ensuite transmis à un circuit de gestion (non représenté) du coprocesseur 200. - Un circuit de calcul 240 réalise le calcul de la variable intermédiaire Y0. Le circuit de calcul 240 est constitué d'une bascule 241, d'une porte ET 242 à deux entrées et d'un inverseur 243. La bascule 241 est une bascule de type D qui comporte une entrée de donnée, une entrée d'horloge et une sortie. L'entrée de donnée de la bascule 241 est connectée à la sortie de résultat anticipé de l'accumulateur 231. L'une des entrées de la porte ET 242 est connectée à la sortie de la bascule 241, et l'autre des entrées de la porte ET 242 est connectée à la sortie de l'inverseur 243. L'entrée d'horloge de la bascule 241 est connectée à la sortie de l'inverseur 243. L'entrée de l'inverseur 243 reçoit le signal d'horloge CLK qui synchronise les différents éléments du coprocesseur 200. La sortie de la porte ET 242 est connectée d'une part à la troisième entrée du sixième multiplexeur 230 et d'autre part à la deuxième entrée du quatrième multiplexeur 224. Le principe de fonctionnement de ce circuit de calcul 240 consiste à effectuer deux opérations pendant un même cycle d'horloge. La bascule 241 sert à travailler sur des fronts (par exemple descendants) du signal d'horloge CLK différents des fronts (par exemple montants) du signal d'horloge CLK utilisés par les autres éléments du coprocesseur 200. Par ailleurs, la porte ET 242 a pour effet de fournir en sortie zéro lors d'un premier demi-cycle du signal d'horloge CLK et le bit mémorisé dans la bascule 241 lors d'un deuxième demi- cycle du signal d'horloge CLK. Le coprocesseur 200 permet d'effectuer à l'aide du dispositif de sélection 228 et de l'accumulateur 231 une opération du type RES = LATCHA * SELA + LATCHY * SELY + ES, LATCHA et LATCHY étant les données mémorisées dans les première et deuxième bascules 225 et 226, SELA, SELY et ES étant des données synchronisées qui sont fournies en série. On peut ainsi calculer directement les k bits de poids faibles de Z = S(i- 1) + (Ai * B) + (N* Y0) en posant SELA = B, LATCHA = Ai, SELY = Y0, LATCHY = No (No étant le mot de k bit de poids le plus faible de N), et ES = S(i-1). Or, comme le sait l'homme du métier les k bits de poids faible de Z sont tous à zéro. Pour le calcul de Y0, On va donc fournir lors d'un premier demi- cycle du signal d'horloge un bit à zéro à la place du bit de poids i (k > i 2 0), ce qui a pour effet de calculer le bit de poids i de Z en ayant un zéro à la place du bit de poids i de Y0. A l'issue du premier demi- cycle, le résultat anticipé est mémorisé dans la bascule 241 et correspond au bit de poids i de Y0. Le demi-cycle suivant sert recalculer le bit de poids i de manière exacte. A l'issue de k cycles du signal d'horloge CLK, Y0 est calculé en entier et le calcul de Z est déjà commencé. La figure 2 représente un cheminement de données entre différents éléments fonctionnels. Le cheminement représenté à l'aide des fils de liaisons et des différents multiplexeurs peut présenter de nombreuses variantes, l'important étant d'assurer des échanges de données entre les différents éléments de calcul et de mémorisation. Certains éléments de la figure 2 ne correspondent pas exactement à des éléments standards couramment utilisés par l'homme du métier. Les figures 3 à 7 précisent la structure de ces différents éléments. La figure 3 correspond à l'un des dispositifs de mémorisation 201 à 204. Le dispositif de mémorisation 201 comporte deux multiplexeurs 301 et 302 et des premier à m-ième registres à décalage 303 notés également Rl à Rm. Le multiplexeur 301 comporte des première à quatrième entrées et une sortie. Les première et deuxième entrées du multiplexeur 301 constituent les première et deuxième entrées du dispositif de mémorisation 201. La troisième entrée du multiplexeur 301 reçoit un "zéro" logique. Les premier à m-ième registres 303 sont des registres de k bits, à décalage, qui disposent d'une entrée série et d'une sortie série. Les entrées des premier à m-ième registres 303 sont connectées ensembles à la sortie du multiplexeur 301. Le multiplexeur 302 comporte des première à m-ième entrées et une sortie. Les premières à m-ième entrées du multiplexeur 302 sont respectivement connectées aux sorties des premier à m-ième registres 303. La sortie du multiplexeur 302 est connectée à la quatrième entrée du multiplexeur 301. Des signaux de commande (non représentés) servent à sélectionner les entrées des multiplexeurs 301 et 302 et à valider le décalage de manière indépendante dans chacun des registres 303. Lorsque l'on désire mémoriser une donnée de m * k bits dans le dispositif de mémorisation 201, ladite donnée est rangée par mot de k bits dans chacun des registres 303. Pour mémoriser la donnée, il suffit d'effectuer k décalages du premier registre 303, puis k décalages du deuxième registre 303 et ainsi de suite jusqu'au m-ième registre 303, le multiplexeur 301 sélectionnant la source de la donnée. Pour fournir une donnée codée sur m * k bits, il suffit de décaler les uns après les autres les registres 303 dans l'ordre de mémorisation de la donnée. Le bouclage de la sortie du multiplexeur 302 sur la quatrième entrée du multiplexeur 301 permet de faire entrer dans l'un des registres 303 le mot de k bits qui est sorti simultanément. Ce bouclage assure la mémorisation des données permettant d'effectuer de multiples sorties d'une même donnée. Comme on peut le remarquer, il est possible d'utiliser de manière indépendante n'importe quel mot de k bits d'une donnée comportant plusieurs mots de k bits. Il est également possible de faire entrer un mot de k bits dans l'un des registres 303 pendant que l'on sort un mot de k bits d'un autre des registres 303. La figure 4 représente le premier (ou le deuxième) circuit de soustraction 205 (ou 206). Le circuit de soustraction 205 comporte deux inverseurs 401 et 402, un additionneur élémentaire 403 et deux bascules 404 et 405 de mémorisation de type D. Tous les éléments représentés sur la figure 4 sont connectés selon une technique connue de l'homme du métier. Ce circuit de soustraction 205 produit un retard systématique d'un cycled'horloge sur les données le traversant. Le deuxième circuit de retard 212 sert à compenser les retards produits sur les données qui sortent du troisième dispositif de mémorisation 203. De même, on pourrait également compenser les retards sur la sortie du premier dispositif de mémorisation 201. Cependant, les données sortant du premier dispositif de mémorisation 201 n'ont pas besoin d'être synchronisées avec les autres données. L'utilisation d'un circuit de soustraction 205 tel que représenté sur la figure 4 permet également de s'affranchir des premier, troisième et quatrième circuits de retard 211, 213 et 214. En effet, la bascule 404 produit un retard identique. Il suffit d'extraire le signal à l'entrée de la bascule 404 et de l'inverser pour obtenir le prochain bit sortant. Un inconvénient est de ne pas avoir un signal stable dès le front actif du signal d'horloge. Pour les systèmes fonctionnant avec une fréquence d'horloge peu élevée, cela permet d'économiser trois bascules D. Le circuit de la figure 5 représente le circuit de comparaison 232 de manière détaillée. Le circuit de comparaison 232 correspond à un circuit de soustraction sur lequel on extrait la retenue mémorisée et la donnée qui arrive sur la première entrée du circuit de soustraction, le circuit de soustraction étant bien évidemment simplifié. La retenue mémorisée est inversée puis rentre dans un OU logique avec la donnée présente sur la première entrée. Le résultat sortant du OU logique lorsque la totalité des données est rentrée dans le circuit de comparaison 232 permet de savoir laquelle des deux données est supérieure à l'autre. Le résultat est mémorisé dans une bascule D 501. La bascule D 501 dispose d'une entrée de donnée, d'une entrée d'horloge, d'une entrée de forçage à " un ", d'une entrée de forçage à " zéro ", et d'une sortie. L'entrée de donnée reçoit la donnée sortant du OU logique, l'entrée d'horloge reçoit un signal de chargement LD dont le front montant correspond à l'instant ou l'on désire obtenir le résultat de la comparaison. Les entrées de forçage à " un " et à " zéro ", reçoivent des signaux de prépositionnement ST et RST pour initialiser le circuit de comparaison 232. La sortie de la bascule 501 est connectée à un dispositif de séquencement (non représenté) du coprocesseur 200. La figure 6 représente un élément du dispositif de sélection 228. Le dispositif de sélection comporte k + 1 éléments de ce type. Cet élément est constitué de trois portes ET 601 à 603 à trois entrées, deux portes 601 et 603 ayant une entrée inverseuse, et d'une porte OU 604 à trois entrées. Le rôle de cet élément est le même que celui d'un multiplexeur à quatre entrées dont la quatrième entrée reçoit un zéro logique. Dans le dispositif de sélection 228, l'élément correspondant au bit de poids le plus fort ne comporte que la porte ET centrale 602 car les première et deuxième bascules 224 et 225 ne disposent que de k bits. La figure 7 représente un ensemble constitué par le circuit accumulateur 231 et le dispositif de sélection 228. L'ensemble ainsi constitué réalise deux multiplications avec addition des deux produits et addition d'une autre donnée en série. Si on appelle LATCHA la donnée présente dans la première bascule 225, LATCHY la donnée présente dans la deuxième bascule 226, SELA la donnée arrivant en série sur la première entrée de sélection du dispositif de sélection 228, SELY la donnée arrivant en série sur la deuxième entrée de sélection du dispositif de sélection 228, ES la donnée arrivant en série sur l'entrée série de l'accumulateur 231, et RES la donnée sortant en série de l'accumulateur 231 alors on effectue l'opération suivante: RES = (SELY * LATCHY) + (SELA * LATCHA) + ES La structure du circuit accumulateur 231 correspond à une structure standard d'accumulateur. Ledit circuit 231 comporte: - des première à k-ième bascules d'accumulation 701 à 704, par exemple de type D, disposant chacune d'une entrée de donnée et d'une sortie, l'entrée de donnée de la première bascule 701 étant connectée au conducteur de poids le plus fort (c'est à dire de poids k) de la sortie parallèle du dispositif de sélection 228; - des première à (k+l)-ième bascules de retenue 705 à 709, par exemple de type D, disposant chacune d'une entrée de donnée et d'une sortie; - une bascule de résultat 710, par exemple de type D, disposant d'une entrée de donnée et d'une sortie, la sortie de cette bascule de résultat correspondant à la sortie de l'accumulateur 231; - des premier à (k+1)-ième additionneurs 711 à 715 standards (ou additionneurs complets) disposant chacun de première à troisième entrées, d'une sortie de résultat, et d'une sortie de retenue, les premières entrées des premier à k-ième additionneurs 711 à 714 étant connectées au dispositif de sélection 228 pour recevoir respectivement les bits de poids k-1 à 0, les deuxièmes entrées des premier à k-ième additionneurs 711 à 714 étant connectées respectivement aux sorties des première à k-ième bascules d'accumulation 701 à 704, la première entrée du (k+1)-ième additionneur 715 étant connectée à la sortie de résultat du k-ième additionneur 714, la deuxième entrée du (k+l)-ième additionneur 715 correspondant à l'entrée série de l'accumulateur 231 qui reçoit la donnée ES, les troisièmes entrées des premier à (k+1)-ième additionneurs 711 à 715 étant respectivement connectées aux sorties des première à (k+1)-ième bascules de retenue 705 à 709, les sorties de résultat des premier à (k- 1)-ième additionneurs 711 à 713 étant respectivement connectées aux entrées de données des deuxième à k-ième bascules d'accumulation 702 à 704, la sortie de résultat du (k+l)-ième additionneur 715 étant connectée à l'entrée de la bascule de résultat 710, la sortie de résultat du (k+l)-ième additionneur 715 correspondant également à la sortie de résultat anticipé de l'accumulateur 231, les sorties de retenue des premier à (k+l)-ième additionneurs 711 à 715 étant respectivement connectées aux entrées de données des première à (k+l)- ième bascules de retenue 705 à 709. Dans la pratique, les bascules de retenue, d'accumulation et de résultat 701 à 710 comportent également des entrées d'horloge et de forçage à zéro. Toutes les entrées d'horloge desdites bascules 701 à 710 sont connectées ensembles et reçoivent un même signal d'horloge CLK. De même, toutes les entrées de forçage à zéro sont connectées ensemble pour être remises à zéro simultanément avant chaque calcul. Ces entrées ne sont pas représentées pour ne pas surcharger inutilement les dessins. Le fonctionnement du dispositif décrit sur cette figure 7 est relativement simple. Lors de chaque cycle du signal d'horloge qui synchronise le coprocesseur, on additionne successivement soit LATCHA, soit LATCHY, soit LACHA + LATCHY, soit zéro avec le contenu des bascules de retenue 705 à 709 et avec le bit arrivant de la donnée ES au contenu des bascules d'accumulation 701 à 704, le mot contenu dans les bascules d'accumulation 701 à 704 étant décalé successivement, de sorte que le bit contenu dans la bascule de résultat 710 corresponde au bit qui sort de l'accumulateur 231. Avant de commencer un calcul, on effectue une remise à zéro de toutes les bascules d'accumulation, de retenue et de résultat 701 à 710. Puis, la double multiplication s'effectue ensuite par décalage simultané des données SELA, SELY et ES, à chaque cycle du signal d'horloge. Les bits de SELA et de SELY déterminent quelle(s) donnée(s) parmi LATCHA et LATCHY doivent être accumulées (voir le fonctionnement du dispositif de sélection 228). Lorsque la totalité des bits des données SELA et SELY a été décalée (soit après m * k cycles d'horloge), on fournit des "0" (pendant k+l cycles d'horloge) à la place des données SELA, SELY et ES afin de sortir la fin du résultat encore contenu dans les bascules d'accumulation 701 à 704. Si lesdites données sont codées sur des nombres de bits différents, il convient de compléter chaque donnée à l'aide de " 0 ". La sortie anticipée de l'accumulateur permet de récupérer le bit de poids faible du résultat avant qu'il soit mémorisé dans la bascule de résultat 710 lors d'un front actif (par exemple montant). Ainsi, pendant un premier demi-cycle, il est possible d'effectuer un premier calcul (éventuellement faux) dont seul le bit de poids le plus faible est mémorisé dans la bascule 241 lors d'un front (par exemple descendant) inactif pour le reste du coprocesseur 200. Lors d'un deuxième demi-cycle, un deuxième calcul peut alors être effectué et mémorisé dans la bascule lors du prochain front actif. A présent que la description structurelle et fonctionnelle des éléments composant le coprocesseur a été faite, il convient d'expliquer à présent le fonctionnement global du coprocesseur. Les explications qui vont suivrent permettront à l'homme du métier de synchroniser de manière globale le coprocesseur afin d'obtenir les opérations désirées. Par la suite, on utilise les données A, B et N qui sont des entiers non nuls, la donnée N étant impaire, codés sur respectivement a*k, b*k et n*k bits, avec a, b et n des entiers non nuls inférieurs à m. Opération élémentaire Pfield(A, B)N = A*B*I mod N: A) Initialisation du coprocesseur: - On charge les données A, B, N respectivement dans les premier à troisième dispositifs de mémorisation 201 à 203; - On charge des zéros dans le quatrième dispositif de mémorisation 204, la donnée étant appelée S(-1); - On initialise le dispositif de comparaison 232 pour que la dernière comparaison indique que N est supérieur à S(-1). B) Répétition a fois de la boucle de calcul suivante, avec i un indice variant de 0 à a-1: B-1) On charge simultanément le i-ième mot Ai de poids faible de A dans le premier registre 221 et le mot No de poids le plus faible de N dans le deuxième registre 222. B-2) Puis, on charge simultanément les mots Ai et No respectivement dans les première et deuxième bascules 225 et 226. B-3) On initialise à zéro les circuits de soustraction 205 et 206, les circuits de retard 211 à 214, le premier registre 221, toutes les bascules 701 à 710 de l'accumulateur 231 et de la bascule 241. B-4) On décale simultanément de deux unités les mots B et S(i-1) contenus dans les deuxième et quatrième dispositifs de mémorisation 202 et 204, des zéros étant fournis sur les première et deuxième entrées du dispositif de sélection 228. B-5) On effectue k décalages successifs sur les deuxième et quatrième dispositifs de mémorisation 202 et 204, et sur le deuxième registre 222, la sortie du circuit de calcul 240 étant reliée à l'entrée du deuxième registre 222 par l'intermédiaire du multiplexeur 224 et à la deuxième entrée de sélection du dispositif de sélection 228 par l'intermédiaire du multiplexeur 230. La donnée B est fournie à la première entrée de sélection du dispositif de sélection 228. La donnée N est fournie à l'entrée de premier registre 221. L'entrée série de l'accumulateur 231 reçoit S(i-1) si la dernière comparaison indique que S(i-1) inactive pour les autre éléments du coprocesseur 200. Pendant un deuxième demi-cycle du signal d'horloge CLK (correspondant par exemple à l'état bas), la sortie de l'accumulateur 231 fournit bit à bit les k bits de poids faible de Z = S(i-1) + Ai * B + N * Y0. B- 6) On transfert le contenu du deuxième registre 222, égal à Y0, dans la deuxième bascule 226. B-7) On effectue (n-l) * k décalages successifs sur les deuxième à quatrième dispositifs de mémorisation 202 à 204 et sur le premier registre 221. La donnée B est fournie à la première entrée de sélection du dispositif de sélection 228. La donnée N est fournie bit à bit d'une part à l'entrée du premier registre 221 et d'autre part à la deuxième entrée de sélection du dispositif de sélection 228. L'entrée série de l'accumulateur 231 reçoit S(i-1) si la dernière comparaison indique que S(i-1) de poids faible de N sortant du premier registre 221. B-8) On effectue k+l décalages successifs sur le quatrième dispositif de mémorisation 204 et sur le premier registre 221. Les première et deuxième entrées de sélection du dispositif de sélection 228 reçoivent des zéros pour pouvoir fournir les k bits de poids fort de S(i) et finir la comparaison de S(i) avec N. Le résultat de la comparaison est mémorisé pour la prochaine itération. C) A l'issue de la dernière itération, le résultat S(a-1) mémorisé dans le quatrième dispositif de mémorisation doit subir une nouvelle soustraction de N si S(a-1) > N. La soustraction s'effectue par décalage simultané de S(a-1) et N dans le deuxième circuit de soustraction 206. Pour récupérer le résultat de la soustraction, on fournit des zéros aux entrées de sélection du dispositif de sélection 228 afin de rendre transparent l'accumulateur 231. L'homme du métier peut remarquer qu'il est possible de réaliser cette opération élémentaire selon différentes variantes. Les étapes d'initialisation et de chargement de données (étapes A, B-1, B-2, B-3) peuvent être supprimées si le coprocesseur se trouve dans une configuration qui correspond à la situation obtenue à l'issue de l'une des étapes. De même, l'étape de synchronisation B-4 peut être modifiée en fonction des retards induits par les circuits de soustraction 205 et 206 et en fonction du nombre de circuits de retard 211 à 214 utilisés. D'autres étapes peuvent se chevaucher, notamment les étapes concernant le transfert de données entre différents éléments lorsque aucun calcul n'est effectué en même temps. Il est également possible d'utiliser des fronts actifs différents du moment que l'on conserve une désynchronisation d'un demi-cycle d'horloge entre la bascule 241 et les autres éléments du coprocesseur 200. Multiplication modulaire: Pour effectuer une multiplication modulaire, il suffit d'effectuer deux opérations élémentaires Pfield en introduisant un paramètre H de correction d'erreur. On effectue ainsi soit Pfield(H, Pfield(A, B)N)N, soit Pfield(A, Pfield(H, B) N)N, avec H = 2(a+n)*k mod N. Calcul de Ac mod N On pose C un entier codé sur c bits et dont le bit de poids 2c-l est égal à 1. On considère que A et N sont codés sur un même nombre de bits égal à n*k bits. Si A est de taille inférieure à N, alors on complète A avec des zéros en bits de poids fort. a) on calcule H = 22*n*k mod N. b) on calcule R(1) = Pfield (H, A), et on mémorise R(1) dans les premier et deuxième dispositifs de mémorisation 201 et 202, le contenu du premier dispositif 201 étant appelé A, et le contenu de deuxième dispositif 202 étant appelé B. c) on effectue une boucle indexée par un indice i variant de 2 à c: c-1) On effectue une opération Pfield(B, B)N, en chargeant les mots de B à la place des mots de A lors de l'étape B-1. Le résultat est stocké dans le deuxième dispositif de mémorisation 202. c-2) Si le bit de poids 2'c-i de C est égal à 1 alors on effectue également une opération Pfield(A, B)N, et on stocke le résultat dans le deuxième dispositif de mémorisation 202. d) On charge " 1 " codé sur n*k bits dans le premier dispositif de mémorisation 201. e) On effectue une opération Pfield(l, B)N pour obtenir le résultat final. Calcul de H = 2(n+p)*k mod N, p étant un entier Pour effectuer le calcul de H, on neutralise une partie des éléments du coprocesseur 200. Le cinquième multiplexeur 229 est positionné pour fournir des " zéro " sur sa sortie. On charge une donnée égale à " 1 " codée sur k bits dans la deuxième bascule 226. Le sixième multiplexeur 230 est positionné pour relier la sortie du troisième circuit de retard 213 à la deuxième entrée de sélection du dispositif de sélection 228. Le huitième multiplexeur 236 est positionné pour relier l'entrée du comparateur 232 à la sortie du premier circuit de retard 211. L'ensemble résultant de ces différentes neutralisations transforme le coprocesseur 200 en circuit de calcul de H par soustractions successives. Un tel circuit est décrit dans la demande européenne n 0O 601 907. REVENDICATIONS 1. Circuit intégré comprenant un coprocesseur (200) d'arithmétique modulaire comportant: - des moyens de mémorisation (201 à 204) pour mémoriser et fournir en série des premier et deuxième opérandes A et B, un modulo N et un résultat S, avec A un entier codé sur a * k bits, a étant un entier non nul au plus égal à m, et avec B, N et S des entiers codés sur au plus m * k bits, m et k étant des entiers supérieurs à 1 - des moyens de calcul pour effectuer des opérations modulaires selon la méthode de Montgomery, caractérisé en ce que les moyens de calcul comportent une première sortie pour fournir bit à bit un résultat actualisé S(i) et une deuxième sortie pour fournir un résultat anticipé, et en ce que ledit coprocesseur comporte en outre un circuit de calcul (240) qui reçoit le résultat anticipé et qui produit une donnée intermédiaire Y0 qui est réinjectée dans les moyens de calcul pour produire le résultat actualisé S(i). 2. Circuit selon la revendication 1, caractérisé en ce que le circuit (240) pour calculer la donnée Y0 comporte: - une bascule (241) synchronisée sur les fronts inutilisés par les moyens de calcul, ladite bascule servant à mémoriser un bit de Y0; - des moyens pour fournir zéro pendant un premier demi- cycle d'un signal d'horloge et pour fournir le bit mémorisé par la bascule pendant un deuxième demi-cycle du signal d'horloge. 3. Circuit selon l'une des revendications 1 ou 2, caractérisé en ce que les moyens de calcul comportent un premier registre (221) à décalage de k bits pour recevoir d'une part un mot Ai de k bits de A et transmettre ledit mot en parallèle à une première bascule (225) et d'autre part N afin de retarder N de k cycles d'un signal d'horloge. 4. Circuit selon l'une des revendications 1 à 3, caractérisé en ce que le moyen d'addition est un circuit parallèle d'addition (227). 5. Procédé pour effectuer une opération modulaire selon la méthode de Montgomery par décalage en série de premier et deuxième opérandes A et B, d'un modulo N et d'un résultat actualisé à travers des moyens de calcul, avec A un entier codé sur a * k bits, a étant un entier non nul au plus égal à m, et avec B, N et S des entiers codés sur au plus m * k bits, m et k étant des entiers supérieurs à 1, dans lequel on calcule une donnée intermédiaire Y0 telle que Y0 = ((S(i- 1) + (Ai * B)) * J0) mod 2k dans une boucle itérative indicée par i, i variant de 0 à a-l, avec S(i-1) qui correspond au (i-1)-ième résultat actualisé, S(-1) étant égal à 0, Ai étant le i-ième mot de k bits de A, et J0 étant un mot de k bits résolvant l'équation ((J0 * N) + 1) mod 2k = 0 caractérisé en ce que Y0 est fourni par un circuit de calcul (240) qui calcule chaque bit de Y0 pendant un demi-cycle d'une période d'horloge qui précède l'utilisation dudit chaque bit de Y0. 6. Procédé selon la revendication 5, caractérisé en ce qu'il comporte en outre la répétition des étapes suivantes, i étant un indice variant de 0 à a-1: - mémorisation d'un mot Ai de k bits correspondant à un mot de poids i de A dans une première bascule (226) de k bits; - mémorisation du mot de k bits de poids faible de N puis de Y0 dans une deuxième bascule (226) de k bits; - addition dans un circuit parallèle d'addition (227) des mots contenus dans les première et deuxième bascules (225, 226); - sélection et fourniture soit du mot contenu dans la première bascule (225), soit du mot contenu dans la deuxième bascule (226), soit de la somme des mots contenus dans les première et deuxième bascules (225, 226), ou soit zéro, en fonction d'une part d'un bit de B, et d'autre part soit d'un bit de Y0 soit d'un bit de N; - additions successives dans un circuit accumulateur (231) des mots fournis par le dispositif de sélection (228) pour chaque paire de bits de B et de N, le résultat de chaque addition étant additionné à un bit du précédent résultat actualisé S(i-1) puis décalé d'un bit et mémorisé entre chaque addition, le bit sortant de l'accumulateur (231) lors du décalage correspondant à un nouveau résultat actualisé S(i). 7. Procédé selon la revendication 6, caractérisé en ce que la mémorisation d'un mot Ai dans la première bascule (225) s'effectue par k décalages du mot Ai dans le premier registre (221) puis chargement parallèle dans la première bascule (225) après que le mot Ai ait été chargé en entier dans le premier registre (221). 8. Procédé selon la revendication 7, dans lequel on effectue les étapes suivantes A) initialisation du coprocesseur: - chargement des données A, B, N respectivement dans les premier à troisième dispositifs de mémorisation (201 à 203); - chargement de zéros dans le quatrième dispositif de mémorisation (204), la donnée étant appelée S(-1); - initialisation du dispositif de comparaison 232 pour que la dernière comparaison indique que N est supérieur à S(-1); B) répétition a fois de la boucle de calcul suivante, avec i un indice variant de 0 à a-1: B-1) chargement simultané du i-ième mot Ai de poids faible de A dans un premier registre (221) et du mot No de poids le plus faible de N dans un deuxième registre (222); B-2) chargement simultané des mots Ai et No respectivement dans les première et deuxième bascules (225 et 226); B-3) initialisation des circuits de soustraction (205 et 206), des circuits de retard (211 à 214), du premier registre (221), des bascules (701 à 710) de l'accumulateur (231) et d'une bascule (241) du circuit de calcul (240); B-4) réalisation de k décalages successifs sur les deuxième et quatrième dispositifs de mémorisation (202, 204), et sur le deuxième registre (222), la sortie du circuit de calcul (240) étant reliée à l'entrée du deuxième registre (222) et à la deuxième entrée de sélection du dispositif de sélection (228), la donnée B étant fournie à une première entrée de sélection d'un dispositif de sélection (228), la donnée N étant fournie à l'entrée de premier registre (221), l'entrée série de l'accumulateur 231 recevant S(i-1) si la dernière comparaison indique que S(i-1) N, pendant un premier demi-cycle du signal d'horloge CLK, la sortie du circuit (240) fournissant un zéro, ce qui a pour résultat de produire un bit de Y0 sur une sortie de résultat anticipé de l'accumulateur (231), ledit bit de Y0 étant mémorisé dans la bascule (241) lors d'une transition inactive pour les autres éléments du coprocesseur (200), pendant un deuxième demi- cycle du signal d'horloge CLK, la sortie de l'accumulateur 231 fournissant bit à bit les k bits de poids faible d'une donnée Z = S(i-1) + Ai * B + N * Y0; B-5) transfert du contenu du deuxième registre (222), égal à Y0, dans la deuxième bascule (226); B- 6) réalisation de (n-l) * k décalages successifs sur les deuxième à quatrième dispositifs de mémorisation (202 à 204) et sur le premier registre (221), la donnée B étant fournie à la première entrée de sélection du dispositif de sélection (228), la donnée N étant fournie bit à bit d'une part à l'entrée du premier registre (221) et d'autre part à la deuxième entrée de sélection du dispositif de sélection (228), l'entrée série de l'accumulateur 231 recevant S(i-1) si la dernière comparaison indique que S(i-1) (221); B-7) réalisation de k+l décalages successifs sur le quatrième dispositif de mémorisation (204) et sur le premier registre (221), les première et deuxième entrées de sélection du dispositif de sélection (228) recevant des zéros pour pouvoir fournir les k bits de poids fort de S(i) et finir la comparaison de S(i) avec N, le résultat de la comparaison étant mémorisé pour la prochaine itération; C) à l'issue de la dernière itération, si S(a-1)ÄN, soustraction éventuelle de N au résultat S(a-1) mémorisé dans le quatrième dispositif de mémorisation.