Brevet FR2822260A1 — publié le 20020920

L'invention concerne des procédés et des dispositifs pour accélérer le temps d'exécution sur des moyens de calcul d'opérations d'arithmétique modulaire et plus particulièrement d'une exponentiation modulaire, d'une multiplication modulaire et d'un produit de Montgomery. Une opération de multiplication modulaire consiste à réaliser l'opération suivante : a. b mod n ; où a, b et n sont des entiers, n étant appelé le modulus. De façon classique, pour effectuer une multiplication modulaire, les moyens de calcul exécutent d'abord une multiplication de a par b, suivie d'une réduction modulo n. Le temps d'exécution de cette opération est proportionnel à k2, où k est le nombre de bits nécessaires pour coder respectivement a, b et n en binaire. De façon également connue des mathématiciens, une multiplication modulaire peut être réalisée par la méthode de Montgomery. Cette méthode fait intervenir des produits de Montgomery comme décrit dans le document de Cetin Kaya Koç, High Speed RSA Implementation qui peut être obtenu à l'adresse suivante : RSA Laboratories RSA Data Security, Inc. 100, Marine Parkway, Suite 500 Redwood City, CA 94065-1031 U. S. A. Dans la suite de la description, ce document sera noté D1. Une opération d'exponentiation modulaire consiste à réaliser l'opération suivante : xc mod n ; Où x, c et n sont des entiers, n étant le modulus. Le calcul de cette exponentiation par des méthodes connues, telles que par exemple la méthode Square and multiple)}, fait intervenir k multiplications modulaires, k étant le nombre de bits nécessaires pour coder respectivement x, c et n en binaire. Ainsi il est admis que le temps d'exécution de cette opération est proportionnel à k3. Les opérations d'exponentiation modulaire constituent les opérations de base de dispositifs de cryptage/décryptage d'informations. Par exemple les dispositifs de cryptage/décryptage mettant en oeuvre l'algorithme RSA (RivestShamir-Adleman) utilisent des exponentiations modulaires. Ces dispositifs se présentent actuellement sous des formes diverses telles que des composants électroniques ou des cartes électroniques destinés à être associés à des moyens de calcul pour exécuter et/ou accélérer les opérations de cryptage/décryptage. Le commerce électronique, notamment sur Internet, utilise un grand nombre de ces dispositifs de cryptage/décryptage pour crypter et décrypter des opérations commerciales telles que des paiements. Le chiffre d'affaire des sociétés effectuant du commerce électronique est donc limité par le nombre d'opérations de cryptage et de décryptage qui peuvent être effectuées par seconde. On conçoit dès lors qu'il est important d'accélérer le temps d'exécution d'un produit de Montgomery, d'une multiplication et d'une exponentiation modulaires sur une machine équipée de moyens de calcul. L'invention vise donc à proposer un procédé et un dispositif pour accélérer le temps d'exécution du calcul d'un produit de Montgomery, d'une multiplication et d'une exponentiation modulaires sur une machine équipée de moyens de calcul. Elle a donc pour objet un procédé pour accélérer le temps d'exécution du calcul d'un produit de Montgomery en appliquant la méthode de Montgomery à radix élevé sur des moyens matériels de calcul, ladite méthode comprenant une boucle d'opérations consistant à réitérer des opérations successives dont notamment : - une première opération d'addition entre une valeur d'un de plusieurs premiers produits, notés al. b, et une valeur d'une variable, notée u, selon une première relation u : =u+a !. b ; - une seconde opération d'addition entre une valeur d'un de plusieurs seconds produits, notés m. n, et une valeur de la variable u selon une deuxième relation u : = u + m. n ; caractérisé en ce qu'au moins lesdites première et seconde opérations d'addition sont des opérations d'addition de Carry-Save pour accélérer le temps d'exécution d'une addition. Suivant d'autres caractéristiques et avantages de l'invention, le procédé comporte : - dans la boucle d'opérations une troisième opération de division de la variable u par une puissance de 2, notée 2'où û) est le radix, selon une troisième relation u caractérisé en ce que la variable u est enregistrée 20) sous la forme d'un couple de Carry-Save formé par deux variables, notées C et S, pour l'exécution des opérations de la boucle et en ce que la troisième opération de division de la variable u sous la forme d'un couple de Carry-Save est réalisée en deux étapes, à savoir : - une étape préliminaire de calcul et de stockage d'une retenue, notée Re, qui risque d'être perdue par la division de chaque variable C et S par la puissance de 2 ; - une étape de division de chaque variable C et S par la puissance de 2 ; - l'étape préliminaire de calcul de la retenue Re comprend l'opération d'additionner de façon classique co bits de poids faible de la variable C, notés Co à m bits de poids faible de la variable S, notés So selon une quatrième relation Re : =Co + So, - une recombinaison de u à partir des variables C et S du couple de Carry-Save et de la retenue Re comprend l'opération de décaler à droite de (o bits la retenue Re et d'additionner de façon conventionnelle le résultat obtenu aux variables C et S selon une cinquième relation u : = C+S+Re/2 ; - il comporte à l'issue de l'exécution de la boucle d'opérations : - une étape de recombinaison (84) de la variable u à partir au moins des valeurs des variables C et S du couple de Carry-Save calculées pendant l'exécution de la boucle d'opérations, et - une étape de réduction (86) de la variable u selon une sixième relation u u-n, où n est un modulus, lesdites étapes de recombinaison et de réduction de la variable u se chevauchant de manière à accélérer leur temps d'exécution ; - le radix w est égal à 4 bits pour optimiser le temps d'exécution du calcul d'un produit Montgomery sur des variables d'entrée du produit de Montgomery codées sur 512 ou 1024 bits ; - les premiers produits ai. b sont pré-calculés avant d'exécuter la boucle d'opérations ; et - les seconds produits m. n sont pré-calculés avant d'exécuter la boucle d'opérations. L'invention a également pour objet un procédé pour accélérer le temps d'exécution du calcul d'un premier et d'un second produits de Montgomery en appliquant pour chaque produit comportant au moins une première étape pendant laquelle la première opération d'addition pour le premier produit est réalisée en même temps que la seconde opération d'addition pour le second produit. Suivant d'autres caractéristiques et avantages de ce procédé pour accélérer le temps d'exécution du calcul d'un premier et d'un second produits de Montgomery : - il comporte au moins une seconde étape décalée dans le temps par rapport à la première, pendant laquelle la seconde opération d'addition pour le premier produit est réalisée en même temps que la première opération d'addition pour le second produit ; - il comporte à l'issue de l'exécution de la boucle d'opérations : - une étape de recombinaison puis de réduction pour le premier produit exécuté en premier ; et ensuite, - une étape de recombinaison puis de réduction pour le second produit exécuté en second ; - une des variables d'entrée du premier produit de Montgomery exécuté en premier se compose des poids faibles d'une variable, et une des variables d'entrée du second produit de Montgomery exécuté en second se compose des poids forts de cette même variable ; L'invention a également pour objet un procédé pour accélérer le temps d'exécution du calcul d'une multiplication modulaire en appliquant une méthode mettant en oeuvre des produits de Montgomery, caractérisé en ce que le calcul des produits de Montgomery est réalisé en appliquant au moins l'un des procédés conforme à l'invention. Suivant d'autres caractéristiques et avantages de ce procédé pour accélérer le temps d'exécution du calcul d'une multiplication modulaire : - ladite méthode mettant en oeuvre des produits de Montgomery est la méthode de Montgomery ; L'invention a également pour objet un procédé pour accélérer le temps d'exécution du calcul d'une exponentiation modulaire en appliquant une méthode mettant en oeuvre des multiplications modulaires, le calcul des multiplications modulaires est réalisé en appliquant un procédé conforme à l'invention. Suivant d'autres caractéristiques et avantages de ce procédé pour accélérer le temps d'exécution du calcul d'une exponentiation modulaire : - ladite méthode mettant en oeuvre des multiplications modulaires est la méthode m-ary avec une taille de mots de r bits ; - la taille de mots r de la méthode m-ary est égale à 5 bits pour accélérer le temps d'exécution de la méthode m-ary lorsque des variables d'entrée du calcul de l'exponentiation modulaire sont codées sur 512 ou 1024 bits ; - les seconds produits m. n sont pré-calculés avant d'appliquer la méthode m-ary ; - ladite méthode mettant en oeuvre des multiplications modulaires est la méthode des restes chinois ; L'invention a également pour objet un procédé pour accélérer le temps d'exécution du calcul d'une première exponentiation modulaire en appliquant une méthode mettant en oeuvre des secondes exponentiations modulaires, les secondes exponentiations modulaires sont réalisées en appliquant un procédé conforme à l'invention. Suivant d'autres caractéristiques et avantages de ce procédé pour accélérer le temps d'exécution du calcul d'une première exponentiation ; - ladite méthode mettant en oeuvre des secondes exponentiations modulaires est la méthode des restes chinois ; - il est appliqué à des nombres codés sur plus de 320 bits ; et L'invention a également pour objet un programme d'ordinateur comprenant des instructions de code de programme pour l'exécution de certaines étapes du procédé conforme à l'invention lorsque ledit programme est exécuté sur des moyens principaux de calcul associés audits moyens matériels de calcul. L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'un produit de Montgomery par la méthode de Montgomery à radix élevé sur des moyens matériels de calcul, ledit système comprenant : - des moyens pour effectuer une première opération d'addition entre une valeur d'un de plusieurs premiers produits, notés al. b, et une valeur d'une variable, notée u, selon une première relation u : = u+al. b ; - des moyens pour effectuer une seconde opération d'addition entre une valeur d'un de plusieurs seconds produits, notés m. n, et une valeur de la variable u selon une deuxième relation u : = u + m. n, caractérisé en ce que les moyens pour effectuer la première et la seconde opérations d'addition comportent au moins un additionneur de Carry-Save ; Suivant d'autres caractéristiques et avantages de ce système : - les moyens pour effectuer la première et la seconde opérations d'addition comportent au moins un premier additionneur de Carry-Save adapté pour réaliser la première opération d'addition et un second additionneur de Carry-Save (158 ; 232) adapté pour réaliser la seconde opération d'addition. - il comporte des moyens classiques pour réaliser une troisième opération de division de la variable u par une puissance de 2, notée 2"où Co est le radix, selon une troisième relation u : = u, il comporte des moyens de 2 stockage de la variable u sous la forme d'un couple de Carry-Save formé par deux variables, notées C et S et des moyens pour réaliser la troisième opération de division de la variable u sous la forme d'un couple de Carry-Save comprenant : - des moyens de calcul et de stockage d'une retenue, notée Re, qui risque d'être perdue par la division de chaque variable C et S par la puissance de 2 ; - des moyens de division de chaque variable C et S par la puissance de 2 ; - les moyens de calcul et de stockage de la retenue Re comportent des moyens d'addition conventionnelle des m bits de poids faible de la variable C, notés Co, aux cobits de poids faible de la variable S, notés Sa, selon une quatrième relation Re : = Co + So ; - il comprend : - des moyens de recombinaison de la variable u au moins à partir des valeurs des variables C et S du couple de Carry-Save ; - des moyens de réduction de la variable u, lesdits moyens de recombinaison de la variable u et lesdits moyens de réduction étant raccordés l'un à l'autre de manière à chevaucher leur fonctionnement sous le contrôle de moyens de commande ; - le radix o est égal à 4 bits pour optimiser le temps d'exécution du calcul d'un produit Montgomery sur des variables d'entrée du produit de Montgomery codées sur 512 ou 1024 bits ; - il comporte des moyens de pré-calculs des premiers produits al. b ; - il comporte des moyens de pré-calculs des seconds produits m. n. ; - lesdits moyens de pré-calculs des premiers et/ou des seconds produits comportent un additionneur conventionnel ; L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'un premier et d'un second produits de Montgomery, caractérisé en ce qu'il comporte deux additionneurs de CarrySave activés simultanément ; Suivant une autre caractéristique du système d'acélération du temps d'exécution du calcul d'un premier et d'un second produits de Montgomery, il comporte un seul moyen pour recombiner la variable u à partir au moins des valeurs de variables C et S du couple de Carry-Save, relié en entrée d'un seul moyen de réduction de la variable u ; L'invention a également pour objet un un système d'accélération du temps d'exécution du calcul d'une multiplication modulaire par une méthode mettant en oeuvre des produits de Montgomery lesdits produits Montgomery étant exécutés sur des moyens matériels de calcul, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des produits de Montgomery conforme à l'invention. L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'une multiplication modulaire par la méthode de Montgomery mettant en oeuvre des produits de Montgomery sur des moyens matériels de calcul, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des produits de Montgomery selon l'une des revendications 24 à 34. L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par une méthode mettant en oeuvre des multiplications modulaires, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des multiplications modulaires conforme à l'invention. L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par la méthode mary avec une taille de mots de r bits mettant en oeuvre des multiplications modulaires, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des multiplications modulaires conforme à l'invention. Suivant une autre caractéristique du système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par la méthode de m-ary, il comporte au moins un registre à décalage à gauche de 5 bits pour accélérer l'exécution de la méthode m-ary avec une taille de mots r bits de la méthode m-ary égale à 5 bits. L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par la méthode des restes chinois mettant en oeuvre des multiplications modulaires, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des multiplications modulaires conforme à l'invention. L'invention a également pour objet un Système d'accélération du temps d'exécution du calcul d'une première exponentiation modulaire par une méthode mettant en oeuvre des secondes exponentiations modulaires, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des secondes exponentiations modulaires conforme à l'invention. L'invention a également pour objet un système d'accélération du temps d'exécution du calcul d'au moins une première exponentiation modulaire par la méthode des restes chinois mettant elle-même en oeuvre des secondes exponentiations modulaires, caractérisé en ce qu'il comporte au moins un système d'accélération du temps d'exécution du calcul des secondes exponentiations modulaires conforme à l'invention. L'invention a également pour objet un composant électronique qui comporte au moins un système conforme à l'invention. Suivant une autre caractéristique de ce composant, il est formé avec au moins un FPGA. L'invention a également pour objet une carte électronique qui comporte au moins un système conforme à l'invention. Suivant une autre caractéristique de cette carte électronique, elle est conforme au standard PCI. L'invention a également pour objet une machine caractérisée en ce qu'elle est associée à au moins un système conforme à l'invention. L'invention a également pour objet un procédé pour accélérer le temps d'exécution du calcul d'une première exponentiation modulaire, notée ME mod n où M est le message d'entrée, E est l'exposant et n est le modulus, sur des moyens principaux de calcul, caractérisé en ce qu'il comprend en outre : - une première étape de séparation du calcul de la première exponentiation modulaire en deux secondes exponentiations modulaires, en appliquant la méthode des restes chinois, - une seconde étape consistant à calculer chacune des secondes exponentiations modulaires en appliquant la méthode m-ary, laquelle met en oeuvre des multiplications modulaires, - des étapes consistant à effectuer les multiplications modulaires en appliquant une méthode mettant en oeuvre des produits de Montgomery. Suivant d'autres caractéristiques et avantages de ce procédé pour accélérer le temps d'exécution du calcul d'une première exponentiation modulaire : - les variables d'entrée sont des nombres entiers naturels codés sur plus de 320 bits ; - la taille de mots r de la méthode m-ary est égale à 5 bits pour accélérer le temps d'exécution de la méthode m-ary lorsque les variables d'entrée du calcul de l'exponentiation modulaire sont codées sur 512 ou 1024 bits ; - les calculs des secondes exponentiations modulaires sont effectués sensiblement en parallèle ; et - les produits de Montgomery sont calculés en utilisant la méthode de Montgomery à radix élevé. - la méthode de Montgomery à radix élevé est mise en oeuvre conformément à l'un des procédés conforme à l'invention. L'invention a également pour objet un programme d'ordinateur comprenant des instructions de code de programme pour l'exécution de certaines étapes d'un procédé conforme à l'invention lorsque ledit programme est exécuté sur les moyens principaux de calcul. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés, sur lesquels : - la figure 1 représente le procédé de Montgomery pour effectuer une multiplication modulaire ; - la figure 2 représente une méthode pour calculer un produit de Montgomery sous sa forme à radix élevé ; - la figure 3A est. un schéma électronique d'un additionneur de Carry-Save ; - la figure 3B est un schéma électronique d'un additionneur conventionnel ; - la figure 4 est un exemple de division d'un nombre représenté sous la forme d'un couple Carry-Save ; - la figure 5 représente un procédé pour calculer un produit de Montgomery conforme à l'invention ; - la figure 6 représente un procédé d'exponentiation modulaire selon la méthode m-ary ; - la figure 7 représente un procédé d'exponentiation modulaire conforme à l'invention ; - la figure 8 représente la méthode des restes chinois ; - la figure 9 est une vue schématique d'un multiplier de Montgomery conforme à l'invention ; et - la figure 10 est une vue schématique d'un exponentiateur modulaire conforme à l'invention. Dans la suite de la description on utilise les notations suivantes : - on note D2 le document suivant : Cetin Kaya Koç, RSA Hardware Implementation , qui peut être obtenu à la même adresse que le document D1 précédemment cité ; - : = est le symbole d'affectation, ainsi X : =M signifie qu'on affecte la valeur d'une variable notée M à une variable notée X ; déc. indique que le chiffre qui le précède est en notation décimale. Composant FPGA fait référence au composant programmable connu du type FPGA (Field Programmable Gate Array). La figure 1 représente le procédé de Montgomery pour effectuer une multiplication modulaire entre une première variable d'entrée notée a et une seconde variable d'entrée notée b selon la relation suivante : a. b mod n ; où a, b et n sont des entiers naturels, n étant le moduls. La description qui va suivre de ce procédé ne présente que les informations nécessaires à la. compréhension de l'invention. Pour plus d'informations le lecteur peut se référer, par exemple, au document D1 chapitre 3.8 Montgomery's method . La multiplication modulaire selon le procédé de Montgomery s'effectue en cinq étapes successives numérotées 2, 4, 6, 8 et 10 sur la figure 1. L'étape 2 consiste à calculer la variable n'o selon la relation suivante : n'0 = - n0-1; où : - le signe-représente l'opération de complément à 1 ; - no représente les ú) bits de poids faible du modulus n, co étant appelé le radix ; - n0-1 représente l'inverse de no et est défini par la relation no. n0-1 = 1 mod (2"), cette équation étant résolue par des méthodes connues telle que l'algorithme d'Euclide étendu L'intérêt du calcul de n'o dans cette étape apparaîtra à la lecture de la description de la figure 2. Dans la deuxième étape 4 le résidu de Montgomery de la variable d'entrée a, noté a, est calculé selon la relation suivante : a := a.p mod n où : - a est la première variable d'entrée du produit modulaire ; - n est le modulus du produit modulaire, - p est défini par la relation suivante : p = 2\ où k est l'entier naturel tel que : 2 n Dans la troisième étape 6 le résidu de Montgomery de la variable d'entrée b, noté b, est calculé selon la relation suivante : b : = b. p mod n ; où : - b est la seconde variable d'entrée du produit modulaire ; - n est le modulus ; - p est identique à la variable p définie dans la deuxième étape 4. Dans la quatrième étape 8 le produit de Montgomery entre le résidu a et le résidu b est calculé et le résultat est affecté à une variable x selon la relation suivante : x : = MonPro (a, b) ; où : -a et b sont les résidus calculés respectivement aux étapes 4 et 6 ; - MonPro représente l'opération produit de Montgomery entre les variables a et b. Cette opération sera décrite par la suite en regard de la figure 2. Dans la cinquième étape 10 le produit de Montgomery entre la variable x et l'unité est calculé et le résultat est affecté à une variable x selon la relation suivante : x : = MonPro (x, 1) ; où : - x est la variable calculée à la quatrième étape 8 ; - 1 représente l'unité ; - MonPro représente l'opération produit de Montgomery. A l'issue de ces cinq étapes 2,4, 6,8 et 10 le résultat de la multiplication de la première variable a par la seconde variable b modulo n est obtenu dans la variable x. La figure 2 représente la méthode de Montgomery sous sa forme à radix élevé pour calculer un produit de Montgomery, également appelée ici la méthode de Montgomery à radix élevé. La description qui va suivre de cette méthode ne présente que les informations nécessaires à la compréhension de l'invention. Pour plus d'informations le lecteur peut se référer, par exemple, au document D2 chapitre 7.5 High radix Montogmery's method . Le calcul d'un produit de Montgomery correspond aux opérations MonPro de la figure 1. Cette opération va être présentée dans le cas particulier de l'étape 8 de la figure 1, c'est-à-dire qu'on décrit ici le-calcul suivant : MonPro (a, b) a. b. p. 1 mod n ; Où : -- - a et b sont les résidus de Montgomery respectifs des variables a et b calculées aux étapes 4 et 6 de la figure 1 ; - p. 1 est l'inverse modulo-n de la variable p définie lors de la description de l'étape 4 de sorte que p-1 satisfait la relation suivante : p. p' =1 mod n. Ce procédé comporte trois étapes principales 16,18 et 20. La première étape 16 consiste à initialiser une variable u et un indice i selon les relations suivantes : u : = 0 ; i : = 0. Elle consiste également à pré-calculer des premiers produits al. b qui seront définis en regard de l'opération 24 de ce procédé. La deuxième étape 18 consiste réitérer une boucle d'opérations tant que l'indice i n'est pas inférieur ou égal à une variable s-1, l'indice i étant incrémenté à l'issue de chaque itération de la boucle. Cette boucle d'opérations est notée de façon conventionnelle for i=0 to s-1 . La variable s qui détermine le nombre d'itérations est ici définie par la relation suivante : k = sro ; où : - k représente le nombre de bits nécessaires pour coder le modulus n, c'est-à-dire que k satisfait la relation : 2 ' Ainsi, si par exemple k = 512 bits et si le radix m = 4 bits, s = 128. Par ailleurs si la division de k par le radix co ne donne pas un entier naturel, il est possible de rajouter à la représentation binaire du modulus n des bits de poids fort égaux à 0 de manière à ce que la représentation binaire du modulus n ainsi obtenue'contienne un nombre de bits k'qui soit un multiple du radix co. La boucle d'opérations 18 comporte quatre opérations 24,26, 28 et 30 successives. La première opération 24 de la boucle d'opérations 18 consiste à effectuer une première opération d'addition et à affecter le résultat à la variable u selon la relation suivante : u : =u+ . b ; où : - al représente les Cû bits de poids faible de la variable a après un iéme décalage à droite de cm bits de la représentation binaire de a, i correspondant à l'indice i de la variable al ; - b représente le résidu de Montgomery de la variable d'entrée b ; - u est la variable initialisée lors de l'étape 16. On appellera par la suite les premiers produits l'ensemble des valeurs des produits a,. b lorsque la valeur de l'indice i varie de 0 à s-1. L'opération 26 suivante consiste à affecter à une variable m le résultat de la multiplication d'une variable uo par n'o modulo 2# selon la relation suivante : m : = Uo. n'omod 2 où : - Uo représente les Cû bits de poids faible de la variable u précédemment calculée lors de l'opération 24 ; - n'a est la variable calculée lors de l'étape 2 du procédé de la figure 1 ; - Cû est le radix. L'opération 28 consiste à effectuer une seconde opération d'addition puis à affecter le résultat dans la variable u selon la relation suivante : u : = u + m. n où : - u est la variable précédemment définie ; - m est la variable calculée lors de l'opération 26 ; - n est le modulus de la multiplication modulaire de la figure 1. On appellera par la suite les seconds produits l'ensemble des valeurs des produits m. n possibles lorsque la valeur de m varie de 0 à 2"-1. L'opération 30 consiste à effectuer une opération de division de la variable u par une puissance de 2 puis à affecter le résultat de la division à la variable u selon la relation suivante : u : = u/2" où : - u est la variable précédemment calculée ; - est la puissance de 2, co étant le radix. A l'issue de la boucle d'opérations 18, l'étape 20 est exécutée. Cette étape consiste à effectuer une opération de réduction si la valeur de la variable u obtenue à l'issue de la boucle d'opérations 18 est supérieure à n, n étant le moduls. L'opération de réduction consiste à affecter à la variable u le résultat de la soustraction u moins n selon la relation suivante : u : = u-n où u et n sont respectivement la variable calculée lors de la boucle d'opérations 18 et le modulus de la multiplication modulaire de la figure 1. On notera que le procédé de Montgomery décrit aux figures 1 et 2 transforme des multiplications modulo n, en des multiplications modulo 20). Or les multiplications moduls 2"s'exécutent beaucoup plus rapidement sur des moyens de calcul conventionnels. Toutefois, il est connu que ce gain de rapidité au niveau des multiplications modulaires est contrebalancé par la -lenteur du calcul des résidus a et b lors des étapes 4 et 6 de la figure 1. La méthode de Montgomery à radix élevée est couramment utilisée avec une valeur du radix égale à 8, cette valeur correspondant à un octet (mot de 8 bits). De façon surprenante il a été déterminé par des tests que cette valeur du radix n'était pas l'optimum pour accélérer le temps d'exécution du calcul d'un produit de Montgomery à radix élevé dans les conditions suivantes : - le calcul est effectué sur des grands nombres. Par grands nombres on désigne des entiers naturels codés en binaire sur au moins 320 bits. - le calcul est effectué par des moyens matériels de calcul. Par moyens matériels de calcul on désigne ici des composants électroniques, ou des ensembles de composants électroniques spécialement conçus pour réaliser ce calcul. On exclue effectivement de ces moyens matériels spécifiques, des moyens polyvalents de calcul, tel qu'un ordinateur classique associé à un programme permettant de réaliser ce-calcul. Les tests suivants ont été réalisés pour des variables a, b et n codées en binaire sur 512 bits, c'est-à-dire pour une valeur de la variable k, précédemment définie, égale à 512 bits. Les tests consistent dans une première étape à concevoir des moyens matériels de calcul d'un produit de Montgomery selon le procédé de la figure 2. Dans une seconde étape les tests consistent à déterminer le temps d'exécution du calcul d'un produit de Montgomery selon le procédé de la figure 2 sur les moyens matériels de calcul conçus lors de la première étape et pour la fréquence de fonctionnement maximale de ces moyens matériels. On notera ainsi dans les exemples numériques suivants que la fréquence maximale de fonctionnement des moyens matériels de calcul diminue au fur et à mesure que la valeur du radix m augmente. Pour les résultats numériques suivants les moyens matériels de calcul sont formés avec un composant FPGA (Field Programmable Gate Array) dont la référence est 10K200E-1. Dans ces conditions les résultats obtenus sont les suivants : - Pour un radix o égal à 2 bits, la fréquence de fonctionnement maximale des moyens matériels de calcul est de 66 MHz. Le temps d'exécution d'un produit de Montgomery selon le procédé de la figure 2 est de 8280 nano-secondes. - Pour un radix o égal à 3 bits, la fréquence de fonctionnement maximale des moyens matériels de calcul est de 60 MHz. Le temps d'exécution d'un produit de Montgomery selon le procédé de la figure 2 est de 6447 nano-secondes. - Pour un radix eo égal à 4 bits, la fréquence de fonctionnement maximale des moyens matériels de calcul est de 50 MHz. Le temps d'exécution d'un produit de Montgomery selon le procédé de la figure 2 est de 5940 nano-secondes. - Pour un radix o égal à 5 bits, la fréquence de fonctionnement maximale des moyens matériels de calcul est de 40 MHz. Le temps d'exécution d'un produit de Montgomery selon le procédé de la figure 2 est de 6475 nano-secondes. On conçoit donc à la lecture des résultats de ces tests que pour optimiser le temps d'exécution d'un produit de Montgomery selon le procédé de la figure 2 pour des grands nombres codés sur 512 bits ! e radix doit être choisi égal à 4 bits. De façon similaire il a été déterminé qu'une valeur du radix égale à 4 bits permet également d'optimiser le temps d'exécution du calcul d'un produit de Montgomery selon le procédé de la figure 2 pour des grands nombres codés sur 1024 bits. Il existe une autre méthode pour calculer des produits de Montgomery connue sous le nom de Méthode de Montgomery sous sa forme simple . Cette méthode correspond à la méthode de Montgomery à radix élevé dans le cas où le radix est égal à 1 bit. Par conséquent on ne décrira pas ici cette méthode plus en détail, on considéra simplement que le la méthode de Montgomery à radix élevé inclus également le cas où le radix est égal à 1 bit. Les figures 3A et 3B représentent un schéma électronique d'un additionneur de Carry-Save et un schéma électronique d'un additionneur conventionnel. Sur ces schémas on note A, B, DI, CI et S, respectivement les i éme bits en partant de la droite de la représentation binaire de variables A, B, D, C, et S, le bit le plus à droite de chaque représentation binaire ayant un indice i égal à zéro. L'additionneur de Carry-Save de la figure 3A comporte trois cellules 40,42 et 44. Ces cellules 40,42 et 44 sont respectivement raccordées en entrée à des premiers moyens de stockage (non représentés) des bits Ao, Bo et Do, des bits A,, B, et D1 et des bits A2, B2 et D2 des variables d'entrée A, B et D. Elles sont également raccordées en sortie respectivement à des seconds moyens de stockage (non représentés) des bits C 1 et So, C2 et S1, et C3 et S2 des variables de sortie C et S. La cellule 40 est adaptée pour calculer la valeur du bit So selon la relation suivante : So : = Ao C Bo &commat; Do où : - Ao, Bo et Do sont les bits d'entrée de la cellule ; (D représente l'opération logique ou exclusif La cellule 40 est également adaptée pour calculer la valeur du bit C1 selon la relation suivante : C1 : = Ao. Bo + Ao Do + Bo. Do où : Ao, Bo et Do ont été définis ci-dessus ; - + représente l'opération logique ou -. représente l'opération logique et . De façon similaire à la cellule 40, la cellule 42 est adaptée pour calculer les bits de sortie C2 et S1 selon les deux relations suivantes ; S1 : = A, 9 B, 9 Dl, C2 : = A1 .B1 + A1.D1 + B1.D1; De façon similaire aux cellules 40 et 42, la cellule 44 est adaptée pour calculer les bits de sortie S2 et C3 selon les deux relations suivantes : S2 : = A2 EB B2 C D2 ; C3 : = A2.B2 + A2 D2 + B2 D2 ; L'opération qui consiste à calculer les bits de sortie des variables S et C en fonction des bits d'entrée selon les relations précédentes s'appelle une addition de Carry-Save. On remarquera qu'en sortie de l'additionneur de Carry-Save, le résultat de l'addition des trois variables d'entrée A, B et D est enregistré dans les deux variables de sortie C et S, C et S formant ce que l'on appelle un couple de Carry-Save, noté (C, S). Pour obtenir le résultat de l'addition des trois variables d'entrée A, B et D dans une seule variable U, les variables C et S doivent être recombinées selon la relation suivante : U : =C+S Où : - C et S sont les variables du couple du Carry-Save obtenues en sortie de l'additionneur de Carry-Save ; - + représente l'opération d'addition conventionnelle. La méthode consistant à additionner les bits des variables d'entrée selon les relations précédentes pour obtenir un couple de Carry-Save, puis à recombiner les variables du couple de Carry-Save pour obtenir le résultat final de l'addition des variables d'entrée est connue sous le nom de la méthode de Carry-save . Ainsi la méthode de Carry-Save se-compose d'une opération d'addition de Carry-Save suivie d'une opération de recombinaison du couple de Carry-Save. On note , le temps d'exécution du calcul de C 1 et So par la cellule 40. On suppose que le temps d'exécution du calcul de C2 et S, et de C3 et S2 par leurs cellules respectives 42 et 44 est également égal à À. Dans ces conditions, le temps d'exécution de l'addition de Carry-Save entre les trois variables d'entrée A, B et D est égal à À. En effet les bits des représentations binaires des variables A, B et D sont traités en parallèle par les cellules 40,42 et 44. Ce résultat peut être généralisé à des additionneurs de Carry-Save comportant de nombreuses cellules, de manière à pouvoir réaliser des additions de Carry-Save sur des grands nombres comme définit précédemment. On notera qu'un additionneur de Carry-Save peut également être réalisé par des moyens logiciels tels qu'un programme permettant de mettre en oeuvre des traitements en parallèle des opérations d'addition de Carry-Save. La figure 3B représente un additionneur conventionnel adapté pour réaliser l'addition conventionnelle de deux variables d'entrée A et B et pour stocker le résultat dans une variable de sortie S. Cet additionneur conventionnel comporte trois cellules 48,50, 52. La cellule 48 est raccordée à la sortie de premiers moyens de stockage (non représentés) des bits Ao et Bo et à l'entrée de seconds moyens de stockage (non représentés) du bit So. Elle est également raccordée à une entrée de la cellule 50. Cette cellule 48 est adaptée pour additionner de façon conventionnelle les bits Ao et Bo et pour transmettre la retenue de cette addition à la cellule 50. Le résultat de cette addition est stocké dans les seconds moyens de stockage du bit So. La cellule 50 est raccordée à la sortie de premier moyens de stockage (non représentés) des bits A1 et B, et à l'entrée de seconds moyens de stockage (non représentés) du bit S.,. Elle est également raccordée à une entrée de la cellule 52. Cette cellule 50 est adaptée pour additionner les bits A1 et B, et pour transmettre la retenue de cette addition à la cellule 52. Le résultat de cette addition est stocké dans les seconds moyens de stockage du bit S,. La cellule 52 est raccordée à la sortie de premiers moyens de stockage (non représentés) des bits A2 et B2 et à l'entrée de second moyens de stockage (non représentés) des bits S2 et Sg. Cette cellule 52 est adaptée pour additionner les bits A2 et B2, le résultat et la retenue de cette addition étant stockés dans les seconds moyens de stockage, respectivement dans les bits SetS. On note À le temps d'exécution du calcul de So par la cellule 48 et l'on suppose que le temps d'exécution du calcul de S, et de S2, S3 respectivement par les cellules 50 et 52 est identique à celui de la cellule 48. On remarque à la lecture de la description de cet additionneur conventionnel que l'exécution du calcul de S1 par la cellule 50 ne peut commencer que lorsque la cellule 48 a transmis la retenue de l'addition des bits Ao et Bo, c'est- à-dire lorsque le calcul de So est terminé. De même l'exécution du calcul deS2, S3 par la cellule 52 ne peut commencer que lorsque la cellule 50 a fini le calcul de S1'Par conséquent l'addition des deux variables d'entrée A, B par l'additionneur de la figure 3B, nécessite un temps d'exécution de 3. On conçoit dès lors que pour additionner trois variables d'entrée A, B et D à l'aide de l'additionneur conventionnel de la figure 3B, le temps d'exécution du calcul est de 3S pour une première addition de A à B auquel il convient de rajouter 3X, correspondant au temps d'exécution d'une seconde addition entre le résultat de la première addition et la variable D. Ainsi la réalisation d'une addition entre trois variables d'entrée A, B et D à l'aide de cet additionneur conventionnel nécessitent un temps de 6X. On vérifie bien à l'aide de cet exemple simplifié que le temps d'exécution d'une addition conventionnelle est proportionnel aux nombres de bits des variables d'entrée. A titre de comparaison on suppose que le temps d'exécution À est le même pour les cellules 40,42, 44,48, 50 et 52 des figures 3A et 3B. Ainsi, une addition de Carry-Save entre les variables A, B et D à l'aide de l'additionneur de Carry-Save s'exécute en un temps de À, Pour obtenir le résultat de l'addition dans une seule variable, les variables C et S doivent être recombinées en effectuant une opération d'addition conventionnelle entre celles-ci qui s'exécute en un temps de 3,. Le temps total pour exécuter l'addition des variables A, B et D en mettant un oeuvre un additionneur de Carry-Save est alors-égal à 41, contre 61 dans le cas où l'on n'utilise que des additionneurs conventionnels. On réalise également à la lecture de la description précédente que le gain de temps réalisé grâce à la mise en oeuvre d'additionneurs de CarrySave est d'autant plus important que les additions sont réalisées sur des grands nombres. En effet, le temps d'exécution d'une addition conventionnelle est proportionnel au nombre de bits des variables d'entrée, ce qui n'est pas le cas pour une addition de Carry-Save. Toutefois il est connu que l'utilisation d'additionneurs de Carry-Save ne présente d'intérêt que pour réaliser des additions entre trois variables d'entrée. De plus le résultat obtenu en sortie d'un additionneur de Carry-Save se présente sous la forme d'un couple de Carry-Save ce qui nécessite de recombiner les variables de sortie C et S par une addition conventionnelle, limitant ainsi l'intérêt d'un additionneur de Carry-Save. Il a également été réalisé qu'il est difficile d'effectuer des opérations arithmétiques sur une variable représentée sous la forme d'un couple de Carry-Save. Par exemple on ne peut pas simplement effectuer une opération de division par une puissance de 2, notée 2", d'un couple de Carry-Save selon la relation suivante : (C, S)/2 : = (C/2" > , S/2"') où C et S sont les variables du couple de Carry-Save. Cette difficulté est illustrée sur l'exemple de la figure 4 où : C= 0110 0000 0010 ; et S =01001001 1110. En recombinant les variables C et S selon la relation C+S on obtient le résultat suivant : C+S= 10101010 0000 (= 680 déc.) En divisant le couple de Carry-Save recombiné C+S par une puissance de deux, ici 16, on obtient alors le résultat suivant : (C+S) /16 = 10101010 (= 170 déc.) Maintenant si l'on effectue le même calcul mais en-inversant l'ordre des opérations, c'est-à-dire que l'on réalise d'abord'l'opération'de division et ensuite l'opération de recombinaison, on obtient alors successivement les résultats numériques suivants : C/16 = 0110 0000 ; 3/16=01001001 ; C/16 + S/16 = 1010 1001 (= 169 déc.) On remarque donc que la simple division de chaque variable C et S par une puissance de deux ne permet pas d'obtenir le résultat exakt Il est donc nécessaire de recombiner le couple de Carry-Save (C, S) avant d'exécuter une division d'une variable stockée sous la forme d'un couple de Carry-Save. Il n'existe pas dans l'état de la technique actuel de solution connue à ce problème. A la lecture des inconvénients connus des additionneurs de CarrySave, on conçoit qu'il n'est pas évident de mettre en oeuvre ces additionneurs dans le cadre du calcul d'un produit de Montgomery. En effet les procédés connus de calcul d'un produit de Montgomery ne font intervenir que des opérations d'additions entre deux variables et non pas trois. De plus ces procédés connus comportent, notamment dans la cas de la méthode à radix élevé, des opérations arithmétiques qui ne peuvent pas être réalisées sur des couples de Carry-Save, telles que l'opération 30 de la figure 2. La figure 5 représente un procédé conforme à l'invention pour calculer un produit de Montgomery entre deux variables d'entrée, notées Ci et b, correspondant aux résidus calculés lors des étapes 4 et 6 du procédé de la figure 1. On utilise pour présenter ce procédé les mêmes notations que celles définies en regard de la figure 2. La figure 5 comporte trois étapes principales 70,72 et 74 successives, l'étape 70 étant une étape d'initialisation, l'étape 72 étant une étape d'itération d'une boucle d'opérations, et l'étape 74 étant une étape de recombinaison et de réduction de résultat. L'étape 70 d'initialisation consiste à initialiser les variables nécessaires pour le calcul du produit de Montgomery selon les relations suivantes : C1 : =0 ; S1 : =0' ;C2 : = 0 ; S2 : = 0 ; R : =0 ; Où : - C1 et S1 sont les variables d'un premier couple de Carry-Save noté (C1, S1) ; - C2 et S2 sont les variables d'un second couple de Carry-Save noté (C2, S2) ; - R est une variable de stockage et de cumul de retenue dont l'intérêt apparaîtra à la lecture de la suite de la description. L'étape 70 consiste également à pré-calculer les premiers produits al. b définis en regard de l'opération 24 de la figure 2. Pour cela on multiplie b par toutes les valeurs possibles de al, c'est-à-dire les entiers naturels compris entre 0 et 2# - 1. La deuxième étape 72 consiste à réitérer une boucle d'opérations tant qu'un indice, noté i, n'est pas supérieur ou égal à une variable s-1, l'indice i étant incrémenté à l'issue de chaque itération de la boucle. Cette boucle d'opérations est notée de façon conventionnelle for i=0 to s-1 . La variable s qui détermine le nombre d'itérations est définie de façon analogue à celle de l'étape 18 de la figure 2. La boucle d'opérations 72 comporte quatre opérations 76,78, 80 et 82 successives. L'opération 76 consiste à effectuer une première opération d'addition de Carry-Save entre les variables C2 divisée par 2#, S2 divisée par 200 et un des premiers produits . b définis en regard de l'opération 24 de la figure 2. Cette opération d'addition est réalisée à l'aide d'un additionneur de Carry-Save selon la relation suivante : (C1, S1) : = C2/2"+S2/2"+ . b où : - o est le radix ; - (C1, S1) est le premier couple de Carry-Save formé par les variables C1 etc1 ;'' - . b est un des premiers produits ; - C2 et S2 sont les variables du second couple de Carry-Save (C2, S2). On remarquera que cette opération 76 remplit la même fonction que les opérations 24 et 30 de la figure 2 mais la première opération d'addition est réalisée à l'aide d'un additionneur de Carry-Save. L'opération 78 consiste à réaliser l'addition conventionnelle des variables CIO, Slo et (R2/#) o puis à affecter le résultat de cette opération à une variable m, selon la relation suivante : m : = (C10 + S10 + (R/2#)0). n'0 où : - C10 et S10 représentent les co bits de poids faible respectivement des variables C1 et S1, co étant le radix. - (R/2") o représente les # bits de poids faible du résultat de la division de R par 2#, o étant le radix ; - n'o est la variable calculée lors de l'étape 2 du procédé de la figure 1 ; - m est une variable dans laquelle le résultat est stocké. L'opération 80 consiste à effectuer une seconde opération d'addition entre les variables C1, S1 et un des seconds produits m. n définis en regard de l'opération 28 de la figure 2. Cette addition est réalisée par un additionneur de Carry-Save et le résultat est affecté aux variables C2, S2 du second couple de Carry-Save selon la relation suivante : (C2, S2) : = C1+S1+m. n où : - C1 et S1 sont les variables précédemment calculées ; - m. n est l'un des seconds produits ; - S2 et C2 sont les variables du second couple de Carry-Save. On notera que l'opération 80 remplit la même fonction que la seconde opération d'addition 28 de la figure 2 mais elle est réalisée à l'aide d'un additionneur de Carry-Save. L'opération 82 consiste à calculer la variable R en additionnant de façon conventionnelle les variables C2o 820. et la valeur de la variable R. Le résultat est affecté à la variable R selon la relation suivante : R : = C2o+S2o+ R Où : - C2o S20 sont respectivement les o bits de poids faible des variables C2 et S2, # étant le radix ; - R est la variable de stockage et de cumul de retenues. En effet, il a été découvert que la différence de résultat entre l'opération (C2+S2)/2"et l'opération (C2/2# + S2/2#), telle qu'illustrée par l'exemple de la figure 4, est égale à la retenue de l'opération C20 + S2o. On appelle donc ici la retenue qui risque d'être perdue par la division de chaque variable C2 et S2 par une puissance de 2, notée 20) # la retenue de l'opération C2o + S2o. Cette opération 82 calcule donc la retenue qui risque d'être perdue par la division de chaque variable C2 et S2 du second couple du Carry-Save par la puissance 2# lors de l'opération 76. De plus, ici, l'opération 82 cumule la retenue de l'addition de C2o + S20 à chaque itération de la boucle d'opérations 72 pour un usage ultérieur lors de l'étape 74. L'étape 74 de recombinaison et de réduction se compose d'une opération 84 de recombinaison suivie d'une opération 86 de réduction. L'opération 84 consiste à réaliser une addition conventionnelle entre la variable C2 divisée par 2ro, la variable S2 divisée par 2# et la variable R divisée par 2 le résultat étant affecté à une variable u selon la relation suivante : u : = C2 /2# + S2 /2# + R /2 # Où : - # est le radix ; - C2, S2 et R sont les variables précédemment calculées lors de la boucle d'opérations 72 ; - u est une variable de stockage du résultat de l'opération. On notera que cette opération est une combinaison des opérations suivantes : - Une division par 2"de chaque variable du couple du Carry-Save (C2, S2). - Une opération d'extraction du cumul des retenues calculées pendant l'exécution de la boucle d'opérations 72, cette opération étant réalisée en décalant à droite de m bits la variable R. - Une opération de recombinaison du second couple du Carry-Save (C2, S2), calculé pendant l'exécution de la boucle d'opérations 72. - Une opération d'addition au second couple de Carry-Save précédemment recombiné du cumul des retenues qui auraient été perdues si elles n'avaient pas été stockées et cumulées dans la variable R lors de l'exécution de la boucle d'opérations 72. Cette opération permet ainsi de restituer la véritable valeur du résultat à l'issue de la boucle d'opérations 72 malgré des opérations de division de chaque variable d'un couple de CarrySave. L'opération 86 consiste à réaliser une opération de réduction si la variable u est supérieure au modulus n selon la relation suivante : u : = u-n où u est le résultat du produit de Montgomery. Cette opération est notée de façon conventionnelle : If u n then u : = u-n. Le procédé de calcul d'un produit de Montgomery conforme à l'invention est nettement plus rapide que le procédé connu de la figure 2. En effet la première et la seconde opérations d'addition 76 et 80 sont réalisées à l'aide d'additionneurs de Carry-Save alors que dans le procédé connu les première et seconde opérations d'addition 24 et 28 sont réalisées à l'aide d'au moins un additionneur conventionnel. De plus le procédé de la figure 5 dévoile une méthode pour réaliser une division d'une variable représentée sous la forme d'un couple de Carry-Save par une puissance de 2, ce qui évite une étape de recombinaison du couple de Carry-Save avant d'exécuter cette division. Cette accélération du temps d'exécution du produit de Montgomery est d'autant plus sensible que les variables d'entrée a, b et n sont grandes c. a. d. codées sur un nombre de bits importants. (supérieur à 320 bits) On notera que les opérations 78 et 82 comportent des additions sur des petits nombres codés sur co bits et qu'une optimisation du temps d'exécution de ces deux opérations n'a pas d'effet sensible. Par ailleurs les opérations 84 et 86 sont exécutées moins fréquemment que les opérations de la boucle 72, par conséquent une optimisation de leur temps d'exécution, bien que possible, n'a pas autant d'effet que celle des opérations de la boucle 72. Toutefois, en variante ces opérations sont accélérées. Un mode de réalisation de cette variante sera présenté en regard de la figure 9. Dans une autre variante l'ensemble des seconds produits m. n sont calculés avant d'exécuter la boucle d'opérations 72 et stockés dans une mémoire. Ainsi les opérations de calcul des premiers produits ag et des seconds produits m. n pendant la boucle d'opérations 72 sont remplacées par des opérations de sélection des résultats de ces calculs dans ladite mémoire. En variante le radix co est choisi égal à 4 bits de manière à optimiser le temps d'exécution du produit de Montgomery entre des variables d'entrée codées sur 512 ou 1024 bits sur des moyens matériels de calcul. En effet, il a été déterminé de façon similaire à ce qui a été décrit en regard du procédé de la figure 2 que pour de telles variables d'entrée une valeur du radix co égale à 4 bits accélère le temps d'exécution du calcul du produit de Montgomery. De préférence le mode de réalisation sera une combinaison du procédé de la figure 5 et des deux variantes décrites ci-dessus. La figure 6 représente un procédé de calcul d'une exponentiation modulaire selon la méthode m-ary, pour effectuer le calcul suivant : MEmod n Où : - M, E et n sont des entiers naturels codés en binaire sur k bits au maximum, -M est le message ; E est l'exposant ; et n est le moduls. La méthode m-ary pour calculer une exponentiation modulaire étant connue, la description qui suit n'a pour but que d'introduire les éléments nécessaires à la compréhension de l'invention. Le lecteur se référa au document D1 chapitre 2.4 The m-ary Method pour des informations plus détaillées. La figure 6 comporte quatre étapes successives 90, 92,94 et 96. L'étape 90 consiste à calculer et à enregistrer dans une mémoire les exponentiations de la variable M suivantes : M a mod n ; Où : - M est le message ; - a est un exposant ; - n est le modulus. L'exponentiation précédente est calculée pour toutes les valeurs de l'exposant a comprises entre 2 et m-1, m étant égal à 2', où r est un paramètre prédéfini par l'utilisateur. Cette étape est représentée de façon conventionnelle sur la figure 6 par le symbole M'mod n for all a = 2, 4,.... m-1 . L'étape 92 consiste à découper la représentation binaire de l'exposant E en s'mots de r bits, notés chacun F,, où i est un indice du mot et varie de 0 pour le mot le plus à droite de la représentation binaire de E à s'-1 pour le mot le plus à gauche de cette même représentation binaire. s'est calculé selon la relation suivante : k = s'. r Où : - k est le nombre de bits de la représentation binaire de E ; - r est le paramètre prédéfini. Si k n'est pas divisible par r, des bits égaux à 0 sont ajoutés à gauche de la représentation binaire de l'exposant E pour obtenir une représentation binaire comportant un nombre de bits divisible par le paramètre r. Par exemple, si r et k sont respectivement égaux à 5 et 512 bits alors 3 bits de valeur nulle sont ajoutés sur la gauche de la représentation binaire de l'exposant E pour obtenir une représentation binaire comportant 515 bits ce qui permet d'obtenir s'égale 103. On obtient les différents mots F,, par exemple, par des opérations successives de décalage à gauche de l'exposant E de r bits dans un registre à décalage à gauche. L'étape 94 consiste à calculer MFs-1 mod n et à affecter le résultat à une variable C selon la relation suivante : C : = ! vt-' modn ; Où : - n est le modulus ; - FS'-1 est le (s'-1) énième mot déterminé lors de l'étape 92 ; - M est le message ; - C est la variable dans laquelle est stocké le résultat de l'opération 94. L'étape 96 consiste à réitérer une boucle d'opérations tant que l'indice i initialisé à la valeur de s'-2 n'est pas inférieur ou égal à 0, l'indice i étant décrémenté à l'issue de chaque itération de la boucle. Cette boucle d'opérations est notée de façon conventionnelle for i=s'-2 downto 0 . La variable s'qui détermine le nombre d'itérations a été définie précédemment. Cette boucle d'opérations comporte deux opérations 98,100 successives. L'opération 98 consiste à calculer une exponentiation modulaire de la variable C puis à affecter le résultat dans la variable C selon la relation suivante : C : =C2'mod n Où : - C est la variable initialisée lors de l'étape 94 ; - r est le paramètre prédéfini ; - n est le modulus. L'opération 100 consiste à calculer une multiplication modulaire de la variable C, précédemment obtenue lors de l'opération 98, par la variable M si le mot F, est différent de 0 selon la relation suivante : C : = C. M F, mod n Où : - n est le modulus ; - F, est le mot d'indice i déterminé lors de l'étape 92 ; - C est la variable précédemment calculée lors de l'opération 98. Cette opération est représentée de façon classique sur la figure 6 par le symbole If F, 0 Then C : = C. MF, mod n . A l'issue de l'exécution de la boucle d'opérations 96, la variable C contient le résultat de l'exponentiation modulaire du message M. La méthode de m-ary décrite ci-dessus pour calculer une exponentiation modulaire met en oeuvre approximativement 8 opérations de multiplication modulaire, 8 étant calculé par la relation suivante : 5=2r-2 + k-r + (k/r-1) (1-1/2r) Où : - k est le nombre de bits de l'exposant E ; - r est le paramètre prédéfini. Ceci représente une réduction du nombre d'opérations par rapport à d'autres procédés connus tels que l'algorithme binaire LR, de 17 à 18 % lorsque l'exponentiation porte sur des grands nombres codés sur 512 ou 1024 bits. Toutefois certaines méthodes sont connues pour être encore plus rapides, telles que par exemple l'algorithme binaire RL qui permet un parallélisme des opérations. Cependant il a été déterminé de façon expérimentale que la méthode m-ary pour un paramètre r choisi égal à 5 bits est un compromis optimal entre le nombre d'opérations de multiplication modulaire effectuées et les ressources nécessaires pour mettre en oeuvre cette méthode. Par ressources on désigne par exemple le nombre de cellules d'un composant FPGA. La figure 7 illustre un procédé de calcul d'une exponentiation modulaire conforme à l'invention illustré dans le cas du calcul de l'exponentiation suivante : ME mod n Où : - M, E et n sont des entiers naturels codés en binaire sur 512 bits au maximum ; -M est le message : - E est l'exposant ; et - n est le modulus Le procédé d'exponentiation modulaire conforme à l'invention met en oeuvre la méthode m-ary dans laquelle les multiplications modulaires sont réalisées selon le procédé de Montgomery décrit en regard de la figure 1. Les produits de Montgomery mis en oeuvre par le procédé de Montgomery sont, par exemple, calculés selon le procédé de la figure 5 avec un radix égal à 4 bits. De plus dans le cas particulier décrit ici le paramètre r de la méthode de m-ary est choisi égal à 5 bits de manière à accélérer le temps d'exécution du calcul de l'exponentiation pour des variables d'entrée codées sur 512 ou 1024 bits. Ce procédé comporte sept étapes 110, 112, 114, 116, 118, 120 et 122 successives. L'étape 110 consiste à calculer le résidu de Montgomery du message M selon la relation suivante : M : = M. p mod n où : - M est le message ; - p est le paramètre de la méthode de Montgomery défini lors de l'étape 4 du procédé de la figure 1 selon la relation suivante : p = 2k, où k est le nombre de bits du modulus n ; - n est le modulus ; - M est la variable dans lequel est enregistré le résidu du message M. Le calcul du résidu de M s'effectue par des méthodes classiques telles que l'algorithme d'Euclide étendu. L'étape 112 consiste à calculer la variable n'o selon la relation suivante n'o =-nu-1. Ce calcul ayant déjà été décrit en regard de l'étape 2 de la figure 1 il ne sera pas décrit ici plus en détail. Ce calcul s'effectue également par des méthodes classiques telles que l'algorithme d'Euclide étendu. L'étape 114 consiste à calculer l'ensemble des seconds produits m. n. Pour cela le produit m. n est calculé pour chaque valeur de m comprise entre 0 et 15. En effet, l'examen de l'opération 26 de la figure 2 montre que m est congru à u n'o modulo 2', de sorte que la valeur de m ne peut être comprise qu'entre 0 et 15 lorsque le radix co est égal à 4 bits. L'étape 116 consiste à élever à la puissance a le résidu M au sens de Montgomery, pour l'ensemble des différentes valeurs de a comprises entre 2 et 31. En effet le paramètre r de la méthode m-ary est ici égal à 5 bits, il découle de l'étape 90 du procédé de la figure 6 qu'il n'est pas nécessaire de calculer les puissances M supérieures à 31. Cette étape 116 est par exemple réalisée par trente et un produits de Montgomery successifs selon la relation suivante : M MonPro (M, M où MonPro désigne un produit de Montgomery calculé par exemple selon le procédé de la figure 5. Lors de cette étape, les opérations suivantes sont successivement effectuées : M 2 : = MonPro (M, M), où M a été calculé lors de l'étape 110 ; M 3 : = MonPro (M, M 2), où M 2 a été calculé lors de l'opération précédente ; etc... Ainsi on obtient successivement #2 jusqu'à #31. L'étape 118 consiste à découper l'exposant E en une succession de mots de 5 bits appelés F, conformément à l'étape 92 de la méthode m-ary décrite en regard de la figure 6. Ensuite, toujours dans l'étape 118, la valeur de - 102 M F 102 est affectée à une variable C selon la relation suivante : -- F 102 C M Où F102 est le 102 énième mot F, tel que défini en regard de l'étape 94 de la figure 6. On notera que lors de cette étape, F 102 n'a pas besoin d'être calculé puisque ce calcul a déjà été effectué lors de l'étape 116. L'étape 120 consiste à réitérer une boucle d'opérations-tant qu'un indice i initialisé à la valeur 101 n'est pas strictement inférieur à 0, l'indice i étant décrémenté de 1 à chaque itération de la boucle d'opérations. La valeur initial de l'indice i est calculée conformément à l'étape 96 de la figure 6 pour un paramètre r de la méthode m-ary égal à 5 bits et une valeur de la variable k égale à 515 bits. La boucle d'opérations se compose de deux opérations successives 126 et 128. L'opération 126 consiste à calculer et à stocker l'élévation à la puissance 32 de la variable C selon la relation suivante : C : C32 Où : - C est la variable initialisée à l'étape 118 ; 32 est calculé conformément à l'opération 98 de la méthode m-ary 5 de la figure 6, selon la relation 32= 25, où 5 est la valeur du paramètre r de la méthode m-ary. L'opération 128 consiste à calculer le produit de Montgomery de la F variable C par la variable M i et à stocker ce résultat selon la relation suivante : C MonPro (C, M où : - #F1 est sélectionné parmi les puissances de M calculées à l'étape 116 connaissant la valeur de F, ; - MonPro désigne l'opération produit de Montgomery, par exemple exécutée conformément au procédé de la figure 5. On notera que cette opération 128 comporte également un test de la valeur de F1 de manière à exécuter le produit de Montgomery que si la valeur de F, est différente de 0. En variante le produit de Montgomery est systématiquement exécuté pour éviter le test de la valeur de F,. A l'issue de l'étape 120, l'étape 122 est exécutée. Cette étape consiste à calculer le produit de Montgomery entre la variable C et. l'unité 1 et à stocker ce résultat, selon la relation suivante C : =MonPro (C, 1) Où : - C est la variable calculée à l'étape 120 ; 1 représente l'unité ; C est une variable dans laquelle est enregistrée le résultat de l'exponentiation modulaire du message d'entrée M. On remarque que la combinaison de la méthode m-ary et du procédé de Montgomery pour calculer des multiplications modulaires est particulièrement intéressant dans le cas du calcul d'une exponentiation puisque le résidu de Montgomery du message d'entrée M n'est calculé qu'une seule fois. L'inconvénient du procédé de Montgomery, c'est-à-dire la nécessité de calculer les résidus des variables d'entrée avant d'effectuer des produits de Montgomery est ainsi limité. Cette combinaison de la méthode m-ary et du procédé de Montgomery permet donc d'accélérer le temps d'exécution du calcul d'une exponentiation modulaire. En variante on peut également combiner le procédé de la figure 7 à la méthode des restes chinois (également appelée méthode CRT). La méthode des restes chinois est succinctement décrite à la figure 8. Cette méthode étant connue, le lecteur se référera pour plus de détail au chapitre 4.1 : Fast Decryption using CRT du document D1. La méthode des restes chinois permet de décomposer une première opération d'exponentiation modulaire en deux secondes opérations d'exponentiation modulaire avec des exposants et des modulus plus petits. La première exponentiation modulaire est notée comme suit : ME mod n où : - M est un message d'entrée ; - E est un exposant ; - n est un modulus se décomposant sous la forme d'un produit tel que n=P. Q, où P et Q sont des entiers naturels premiers. Dans une première étape 130, cette première exponentiation est décomposée en deux secondes exponentiations respectivement modulo El et E2 que l'on calcule séparément, selon les relations suivantes : M1 : = ME1 mod P M2 : = be2 mod Q où : - M est le message d'entrée ; -E1 = E mod (P-1) ; - E2 = E mod (Q-1) ; - M1 et M2 sont des variables de stockage des résultats intermédiaires. Dans une étape 134 suivante, le résultat de la première exponentiation modulaire est obtenu en combinant les variables M1 et M2 précédemment calculées, selon la relation suivante : M : = M2 + [ (M1-M2). (Q-1 mod P) mod P]. Q Où : - M1 et M2 sont les variables calculées à l'étape 130 ; - Q et P sont les nombres premiers tels que n = P. Q. k étant le nombre de bits nécessaires pour coder le modulus n, il est possible de choisir P et Q tel que P et Q aient un nombre de bits sensiblement égal à k/2. Dans ces conditions, on estime que la méthode des restes chinois permet de réduire d'un facteur 4 le nombre d'opérations requises pour calculer la première exponentiation, lorsque celle-ci est mise en oeuvre par des moyens logiciels de calcul. Ce facteur est de l'ordre de 2 lorsque la méthode des restes chinois est mise en oeuvre par des moyens matériels de calcul tels qu'un composant FPGA. De plus, pour accélérer le temps d'exécution du calcul de la première exponentiation, les calculs des variables M1 et M2 peuvent être effectués en parallèle. On notera que cette méthode permet ainsi de décomposer une première exponentiation modulaire portant sur des grands nombres codés sur 1024 bits en deux secondes exponentiations modulaires portant sur des grands nombres codés sur 512 bits. Des estimations de temps de calcul d'une première exponentiation modulaire ont été effectuées dans les conditions suivantes : - la première exponentiation modulaire portant sur des grands nombres de 1024 bits est décomposée en deux secondes exponentiations modulaires de 512 bits chacune. - chacune des secondes exponentiations modulaires est calculée selon le procédé de la figure 7 dans lequel les produits de Montgomery sont calculées selon le procédé de la figure 5. Dans ces conditions lorsque le procédé est mis en oeuvre par un composant FPGA travaillant à 40 MHz le temps d'exécution du calcul de la première exponentiation est sensiblement égal à 4.71 milli secondes. Dans les mêmes conditions mais pour des grands nombres codés sur 1024 bits il a été déterminé que le temps d'exécution du calcul d'une première exponentiation est sensiblement égal à 17.8 milli secondes La figure 9 représente schématiquement des moyens matériels de calcul 150 conforme à l'invention. Ces moyens matériels sont appelés ici multiplier de Montgomery . Sur cette figure seuls les éléments spécifiques à l'invention ont été représentés. Les autres composants non représentés mais nécessaires à la mise en oeuvre du procédé de la figure 5 peuvent être aisément déterminés, de façon classique à partir des éléments décrits précédemment. Ainsi les composants nécessaires pour mettre en oeuvre les opérations 78 et 82 de la figure 5 ainsi que les opérations de divisions n'ont pas été représentés. De même les tampons de stockage des variables C1, S1, C2, S2, R et u ne sont pas représentés. Ce multiplier 150 comporte une mémoire 152 raccordée à l'entrée et à la sortie de moyens 154 de calculs spécifiques, sous le contrôle de moyens de commande 156. Le multiplier de Montgomery 150 décrit ici à titre d'exemple est adapté pour coopérer avec des moyens principaux de calcul (non représentés). Ces moyens principaux de calcul exécutent par exemple une exponentiation modulaire selon le procédé de la figure 7. Dans une telle situation le multiplier de Montgomery 50 est un coprocesseur permettant d'accélérer le temps d'exécution des produits de Montgomery. La mémoire 152 est raccordée par l'intermédiaire de bus d'entrée/ sortie de données aux moyens principaux de calcul (non représentés). La mémoire 152 est adaptée pour stocker les variables suivantes : la variable M calculée lors de l'étape 110 du procédé de la figure 7 ; la variable n'o calculée lors de l'étape 112 du procédé de la figure 7 ; les seconds produits m. n calculés lors de l'étape 114 du procédé de la figure 7 ; les variables M a calculées lors de l'étape 116 de la figure 7 ; la variable C initialisée lors de l'étape 118 et calculée lors des opérations 126 et 128 du procédé de la figure 7 ; l'unité 1 nécessaire pour la réalisation de l'étape 122 du procédé de la figure 7 ; et les premiers produits ai. b pré-calculés lors de l'étape 70 du procédé de la figure 5. Les moyens 154 de calculs spécifiques comportent un premier et un second additionneurs de Carry-Save 157,158, un premier et un second additionneurs conventionnels 160 et 162, un registre à décalage à droite 164 et un soustracteur conventionnel 166. Le premier additionneur de Carry-Save 157 est raccordé à une sortie de la mémoire 152 et à une sortie du second additionneur du Carry-Save 158. Il est également raccordé à l'entrée du second additionneur de Carry- Save 158. Cet additionneur de Carry-Save est ici destiné à réaliser la première opération d'addition 76 du procédé de la figure 5. Sa structure est classique et découle de celle décrite en regard de la figure 3A. Le second additionneur de Carry-Save 158 est raccordé à la sortie de la mémoire 152 et à une sortie du premier additionneur de Carry-Save 157. Il est également raccordé à une entrée du premier additionneur de Carry-Save 157. Cet additionneur 158 est, ici, destiné à réaliser la seconde opération d'addition 80 du procédé de la figure 5. Sa structure est similaire à celle du premier additionneur de Carry-Save 157. Le premier additionneur conventionnel 160 est raccordé à une entrée et à la sortie de la mémoire 152. Cet additionneur est destiné à réaliser le pré-calcul des premiers produits ai. b et des seconds produits m. n. Par exemple le calcul des seconds produits m. n est réalisé selon la succession de calculs suivant : 2. N : = N+N 3. N : = N+2. N 4. N : = N+ 3. N etc... Les résultats des calculs des premiers et des seconds produits sont ensuite stockés dans la mémoire 152 aux emplacements prévus à cet effet. Le second additionneur conventionnel 162 est raccordé à la sortie du second additionneur de Carry-Save 158 et à une entrée du soustracteur 166. Ce second additionneur 162 est destiné à réaliser l'opération de recombinaison 84 de la figure 5. Sa structure découle de celle décrite en regard de la figure 3B. Toutefois les cellules qui le composent telles que la cellule 48 de la figure 3B, sont regroupées en étages de 32 cellules. La sortie de chaque étage est directement raccordée à un étage correspondant dans le soustracteur 166 de manière à ce que, dès que le calcul de l'addition dans un des étages est fini, le résultat est directement transmis à l'étage correspondant du soustracteur 166 sans attendre. Ainsi le soustracteur 166 exécute l'opération de soustraction avec seulement un cycle d'horloge de retard sur l'opération d'addition. Cette structure est connue sous le nom de Pipe line , et permet d'accélérer le temps d'exécution des opérations. Le soustracteur 166 est adapté pour réaliser l'opération 86 de la figure 5. Il est donc par exemple raccordé aux sorties du second additionneur conventionnel 162 et de la mémoire 152. Il est également raccordé à une entrée de la mémoire 152, par exemple, pour stocker le résultat de l'opération de réduction 86. Le registre à décalage à droite164 est adapté pour décaler à droite de m bits, co étant le radix de la méthode de Montgomery à radix élevé. Ce registre 164 est destiné à réaliser les opérations calcul des ai, le résultat étant alors utilisé pour sélectionner l'un des premiers produits ai. b correspondant dans la mémoire 152. Les connexions du registre à décalage 164 avec les autres composants de la figure 9 n'ont pas été représentées pour simplifier la représentation schématique, de telles connexions pouvant aisément être déterminées. Les moyens de commande 156 sont adaptés pour commander le fonctionnement des moyens de calculs spécifiques 154 et de la mémoire 152 conformément au procédé de la figure 5. Ces moyens de commande sont réalisés de façon classique. L'ensemble des éléments de la figure 9 sont, par exemple, implantés dans un composant FPGA ou dans un composant ASIC. En variante ce composant est associé à d'autres composants électroniques sur une carte électronique de manière à réaliser une carte électronique conforme au standard PCI. Une carte conforme au standard PCI est enfichable dans des ordinateurs classiques, ces derniers étant alors adaptés pour former les moyens principaux de calcul. Dans le cas d'un composant FPGA dont la référence est XILINX XCV1600E-6 fonctionnant à 45 MHz, les estimations du nombre de cycles d'horloge requis pour exécuter chaque étape du procédé de la figure 5 sont les suivantes : 35 cycles d'horloge pour l'étape 70 ; 260 cycles d'horloge pour l'étape 72 ; 39 cycles d'horloge pour l'étape 74 de recombinaison et de réduction. Ainsi l'estimation du nombre de cycles d'horloge total pour calculer un produit de Montgomery selon le procédé de la figure 5 est de 334 cycles d'horloge pour des variables d'entrée codées sur 512 bits. Dans ces conditions il a également été estimé que le procédé de la figure 7 met en oeuvre 643 produits de Montgomery et que l'étape 114 de la figure 7 de pré-calcul des seconds produits m. n nécessite 38 cycles d'horloge. On obtient ainsi une estimation du nombre de cycles d'horloge nécessaires pour calculer une exponentiation modulaire portant sur des grands nombres de 512 bits égale à 214223 cycles d'horloge. Ceci correspond pour une fréquence de fonctionnement du composant FPGA de 45 MHz à un nombre d'exponentiations 512 bits sensiblement supérieur à 200 par seconde. On notera que pour cette estimation on considère que les étapes 110 et 112 du procédé de la figure 7 sont exécutées par les moyens principaux de calcul associés au multiplier de Montgomery 150. Par conséquent le nombre de cycles d'horloge requis pour exécuter ces deux opérations n'est pas pris en compte dans cette estimation. On admet toutefois que leur temps d'exécution est approximativement 10 fois inférieur à celui des étapes 114 à 122. En variante les moyens de calculs spécifiques 154 comportent un seul additionneur de Carry-Save. En effet lors de l'exécution du procédé de la figure 5, la première opération d'addition 76 précède toujours la seconde opération d'addition 80 puisque le résultat de la première addition 76 est utilisé dans cette seconde opération d'addition 80. Par conséquent le premier et le second additionneurs de Carry-Save 157,158 ne sont jamais actifs en même temps, il est donc possible de les remplacer par un seul additionneur de CarrySave réalisant alternativement la première opération d'addition 76 et la seconde opération d'addition 80. La figure 10 représente schématiquement des moyens matériels de calcul 200 conforme à l'invention associés à des moyens principaux de calcul 201. Sur ce schéma seuls les composants électroniques principaux ont été représentés, les autres composants pouvant être aisément déterminé. Les moyens principaux de calcul 201 sont adaptés pour réaliser des exponentiations modulaires selon le procédé de la figure 7 en coopérant avec les moyens matériels de calcul 200. Ils sont, par exemple, formés avec un ordinateur. Dans le cas particulier décrit ici, les moyens 201 sont adaptés pour réaliser une première et une seconde exponentiations modulaires. La première et la seconde exponentiations modulaires sont chacune réalisées selon le procédé de la figure 7 et par conséquent mettent en oeuvre respectivement des premiers et des seconds produits de Montgomery. Les moyens matériels de calcul 200 sont adaptés pour former un coprocesseur pour les moyens principaux de calcul 201. Il comporte un multiplier de Montgomery 202 associé à des moyens de décalage à gauche 204, sous la commande de premiers moyens de commande 206. Le multiplier de Montgomery 202 est une variante du multiplier de Montgomery 150 de la figure 9 dans lequel l'utilisation des ressources est optimisée. En effet il est adapté pour exécuter sensiblement en parallèle les premiers et les seconds produits de Montgomery sans pour autant dédoubler les ressources à mettre en oeuvre. Il permet ainsi de diviser par deux le temps d'exécution de deux produits de Montgomery. Ce multiplier de Montgomery 202 comporte une mémoire 210 associée à des moyens de calculs spécifiques 212, sous le contrôle de seconds moyens de commande 214. De même que sur la figure 9, seuls les composants principaux ont été représentés, les autres composants sont aisément déterminables. La mémoire 210 est adaptée pour stocker les variables suivantes : le résidu M d'un message d'entrée M de la première exponentiation, calculé lors de l'étape 110 du procédé de la figure 7 par les moyens de calcul 201. le résidu M'd'un message d'entrée M'de la seconde exponentiation, calculé lors de l'étape 110 du procédé de la figure 7 par les moyens de calcul 201. - les variables n'o et n"a calculées lors des étapes 112 du procédé de la figure 7 respectivement pour la première et la seconde exponentiations modulaires ; les seconds produits m. n et m'. n' calculés lors des étapes 114 du procédé de la figure 7 respectivement pour la première et la seconde exponentiations modulaires ; les variables M est M'calculées lors des étapes 116 du procédé de la figure 7 respectivement pour la première et la seconde exponentiations modulaires ; les variables C et C'calculées lors de l'étape 118 et lors des opérations 126 et 128 du procédé de la figure 7 respectivement pour la première et la seconde exponentiations modulaires ; l'unité 1 nécessaire pour exécuter l'étape 122 du procédé de la figure 7 ; les modulus n et n'respectivement de la première et de la seconde exponentiations modulaires. La mémoire 210 comporte un premier et un second tampons d'entrée de données de manière à enregistrer simultanément deux données différentes. Elle comporte également un premier et un second tampons de sortie de données de manière à mettre simultanément à disposition des moyens de calculs spécifiques 212 deux données différentes, une dans chaque tampon de données. Les moyens 212 de calculs spécifiques comportent un premier et un second registres à décalage à droite 216,218, un premier et un second additionneurs conventionnels 220,222, un bloc d'additionneurs de Carry-Save 224 et un bloc 226 de recombinaison et de réduction. Le premier registre à décalage à droite 216 est raccordé au premier tampon de sortie de données de la mémoire 210 et à l'entrée du premier additionneur conventionnel 220. Ce premier registre à décalage 216 est destiné à être utilisé lors des opérations de calcul de la première exponentiation modulaire. Ainsi ce registre est utilisé de façon similaire au registre 164 de la figure 8 pour calculer les a,. Le second registre à décalage 218 est similaire au premier registre à décalage 216. Toutefois celui-ci est raccordé au second tampon de sortie de données de la mémoire 210 et à l'entrée du second additionneur conventionnel 222. Ce registre à décalage est destiné à être utilisé lors des opérations de calcul de la seconde exponentiation modulaire. Le premier additionneur conventionnel 220 est raccordé au premier tampon d'entrée de données de la mémoire 210. Cet additionneur conventionnel 220 est destiné à être utilisé pour le calcul de la première exponentiation modulaire. Sa structure et son fonctionnement sont similaires à l'additionneur conventionnel 160 de la figure 8. Le second additionneur conventionnel 222 est raccordé en sortie du second registre à décalage 118 et au second tampon d'entrée de la mémoire 210. Sa structure et son fonctionnement sont similaires à l'additionneur conventionnel 160 de la figure 8. Le bloc 224 d'additionneurs de Carry-Save est raccordé au premier et au second tampons de sortie de données de la mémoire 210, et à l'entrée du bloc 226 de recombinaison et de réduction. Ce bloc 224 comporte deux additionneurs de Carry-Save 230 et 232. Le premier et le second additionneurs de Carry-Save 230,232 sont respectivement adaptés pour réaliser la première opération d'addition 76 et la seconde opération d'addition 80 du procédé de la figure 5. Ces deux additionneurs de Carry-Save 230,232 sont commandés par les seconds moyens de commande 214 pour que les opérations de calcul du premier et du second produits de Montgomery soient entrelacées. Ainsi après une phase d'initialisation, la première opération d'addition 76 pour le premier produit de Montgomery est exécutée par le premier additionneur de Carry-Save 230 tandis que, dans le même temps, la seconde opération d'addition 80 pour le second produit de Montgomery est exécutée par le second additionneur de Carry-Save 232. Ensuite lors des opérations suivantes d'exécution de la boucle d'opérations 72, la situation s'inverse, c'est-à-dire que l'additionneur de CarrySave 230 exécute la première opération d'addition 76 pour le calcul du second produit de Montgomery tandis que, dans le même temps, le second additionneur de Carry-Save 232 exécute la seconde opération d'addition 80 pour le calcul du premier produit de Montgomery. Les seconds moyens de commande 214 mettent à profit le fait que dans le procédé de la figure 5 appliqué au calcul d'un seul produit de Montgomery, la première et la seconde opérations d'addition sont toujours successives et ne peuvent pas être réalisées en même temps. Par conséquent lors du calcul d'un seul produit de Montgomery il existe toujours un additionneur de Carry-Save inactif. Ainsi les seconds moyens de commande décrits ici, commandent l'additionneur de Carry-Save inactif pour exécuter une opération d'addition destinée à un second produit de Montgomery exécuté en parallèle avec le premier. Le bloc 226 de recombinaison et de réduction se compose d'un additionneur conventionnel 236 raccordé à l'entrée d'un soustracteur conventionnel 238. L'additionneur conventionnel 236 est raccordé à la sortie du bloc 224 d'additionneurs de Carry-Save. Cet additionneur conventionnel 236 est adapté pour réaliser l'opération 84 de recombinaison du procédé de la figure 5. Le soustracteur 238 est raccordé par exemple à l'entrée des moyens principaux de calcul 201 apte à utiliser le résultat du produit de Montgomery. Le soustracteur 238 est adapté pour réaliser l'opération de réduction 86 du procédé de la figure 5. Les seconds moyens de commande 214 sont réalisés de façon conventionnelle et sont raccordés à l'ensemble des composants du multiplier de Montgomery 202. Ils sont également adaptés pour commander les différentes opérations de calcul du premier et du second produits de Montgomery réalisées par le multiplier de Montgomery 202. Le multiplier de Montgomery 202 est réalisé, par exemple, à l'aide d'un composant FPGA ou ASIC. Les moyens 204 de décalage à gauche sont raccordés à l'entrée et à la sortie des moyens principaux de calcul 201 sous la commande des premiers moyens de commande 206. Les moyens 204 pour effectuer un décalage à gauche comportent une mémoire 240 de type RAM (Random Access Memory) dans laquelle sont stockés un premier et un second exposants correspondant respectivement à ceux de la première et de la seconde exponentiations modulaires. Le premier et le second exposants sont notés respectivement E1 et E2. Cette mémoire 240 est raccordée à l'entrée d'un premier et d'un second registres à décalage à gauche 242,244 de r bits, r étant le paramètre de la méthode m-ary. Le registre à décalage à gauche 242 est adapté pour déterminer et fournir les variables F, issues de l'exposant E1 conformément à l'étape 118 du procédé de la figure 7. Ce registre à décalage comporte un nombre de bits inférieur à celui de l'exposant E1, par exemple 32 bits alors que l'exposant E1 est codé sur 512 bits. Ainsi dès que l'ensemble des bits contenus dans ce registre ont été décalés, le registre est immédiatement rechargé avec les 32 bits suivants de l'exposant E1 extrait de la mémoire 240. Ceci permet d'utiliser un registre à décalage de 32 bits pour décaler des nombres codés sur un nombre de bits supérieurs. Le registre à décalage à gauche 244 est similaire au registre à décalage 242, toutefois il est destiné à fournir les variables F', issues de l'exposant E2. Les premiers moyens de commande 206 sont raccordés aux moyens 204 de décalage à gauche et aux seconds moyens de commande 214. Ils sont adaptés pour commander les moyens 204 de décalage à gauche et le multiplier de Montgomery 202 par l'intermédiaire des seconds moyens de commande 214. Ils sont également raccordés aux moyens principaux de calcul 201 et adaptés pour coopérer avec ces derniers pour mettre en oeuvre le procédé de la figure 7. Ainsi les étapes 110 et 112 du procédé de la figure 7 sont, par exemple, réalisées par les moyens de calcul 201 tandis que les étapes 114 à 122 mettent en oeuvre les moyens matériels de calcul 200 pour accélérer le temps de calcul. L'ensemble des éléments de la figure 10 sont, par exemple, implantés dans un composant FPGA ou dans un composant ASIC. En variante ce composant est associé à d'autres composants électroniques sur une carte électronique de manière à réaliser une carte électronique conforme au standard PCI. Une carte conforme au standard PCI est enfichable dans des ordinateurs classiques, ces derniers étant alors adaptés pour former les moyens principaux de calcul. En variante, la première exponentiation modulaire est réalisée sur les poids faibles du message d'entrée tandis ce que la seconde exponentiation modulaire est réalisée sur les poids forts de ce même message, les résultats des exponentiations sur les poids faibles et les poids forts étant ensuite recombiner pour obtenir le résultat final. Le fonctionnement des composants des moyens matériels de calcul représentés aux figures 9 et 10 est classique en lui-même. Le fonctionnement de la coopération de ces différents composants entre eux découle directement des procédés décrits en regard des figures 5 et 7. Par conséquent la coopération des différents composants entre eux ne sera pas décrite ici plus en détail. Le fonctionnement du procédé de la figure 7 va maintenant être illustré à l'aide d'un exemple simple consistant à calculer l'exponentiation modulaire suivante : 149100 mod 165 où : - 149 est la valeur du message d'entrée en décimale, noté M dans cet exemple ; - 100 est la valeur de l'exposant en décimale, noté E dans cet exemple ; - 165 est la valeur du modulus en décimale, noté n dans cet exemple. Dans la suite de cet exemple, et pour simplifier la présentation, les produits de Montgomery sont calculés selon le procédé de Montgomery à radix élevé de la figure 2 et non pas suivant le procédé de la figure 5. Le radix est ici choisi égal à 4 bits. * Par ailleurs, le paramètre r de la méthode m-ary est choisi ici égal à 5 bits. Les représentations binaires de M, n et E sont les suivantes : M = 1001 0101 (= 149 déc.) E = 0110 0100 (= 100 déc.) N= 10100101 (= 165 déc.) On déduit de ces représentations binaires que les variables d'entrée sont codées sur 8 bits et que par conséquent le paramètre p de l'étape 110 de la figure 7 nécessaire pour calculer le résidu de M, noté M, est égal à 28, c'est- à-dire à 256. L'étape 110 du procédé de la figure 7 consiste donc à réaliser le calcul suivant : M = 149 X 256 mod 165. On obtient par une méthode classique, telle que l'algorithme d'Euclide étendu : M = 29 déc. L'étape 112 de la figure 7 consiste à calculer n'o selon la relation définie à l'étape 2 de la figure 1. Pour cela on détermine d'abord no, c'est-à-dire les 4 bits de poids faible du modulus n. On a donc no égal 5. Ensuite, nest calculé à l'aide de la relation suivante : no. n0-1= 1 mod 16 Pour calculer la valeur de la variable n0-1 on exploite le fait que cette valeur est un entier naturel compris entre 0 et 15. Par conséquent pour chaque valeur possible de la variable no' le produit suivant est calculé : no. no. 1 mod 16 Ensuite, on sélectionne la valeur de no. 1 satisfaisant la relation précédemment définie. Par cette méthode on détermine que no. 1 est égal à 13. On calcule ensuite son complément à 1 et l'on obtient n'o = 3. L'étape 114 du procédé de la figure 7 consiste à pré-calculer les 16 valeurs possibles des seconds produits m. n. Etant donné la simplicité de l'exemple décrit ici, ceci sera fait non pas dans cette étape mais directement au moment où la valeur de l'un des seconds produits est requise. L'étape 116 consiste à calculer Mo. pour les valeurs successives de a comprises entre 2 et 31. Toutefois, dans l'exemple particulier décrit ici, t'exposant E se décompose en seulement deux mots de 5 bits Fo et F1 dont les valeurs sont les suivantes : Fo=00100 (=4déc.) F, =00011 (=3déc.) Par conséquent seuls les variables M 3 et M4 sont nécessaires pour l'exécution des étapes suivantes. On ne calculera donc ici que ces deux variables M3et M4. Pour calculer M 3 et M 4 les opérations suivantes sont successivement effectuées : M 2 = MonPro (M, M) #3 = MonPro (#, #2) #4 = MonPro (#, #3) Le calcul de ces différents produits de Montgomery est effectué selon le procédé décrit en regard de la figure 2. Le procédé étant identique pour le calcul de tvt, tvP et M 4 J on ne décrit ci-dessous que le calcul de M 2. A l'étape 16 du procédé de la figure 2 appliqué au calcul de M 2, les premiers produits M,. M sont pré-calculés, où la variable tvt, prend successivement les deux valeurs suivantes : Mo =1101 (=13déc.) #1 = 0001 (= 1 déc. ) Après calcul, on obtient : #0. # = 377 ; et tVti. M =29. La boucle 18 d'opérations de la figure 2 est ensuite exécutée successivement pour les indices i = 0 et i=1. Pour i = 0, les opérations 24 à 30 de la boucle 18 sont donc les suivantes : u : =Mo. M= 1 0111 1001 (= 377 déc.) m : = Uo. n'o mod 2ob = 93 mod 16 = 11 u : = u + m. n = 377 + 11 X 165 = 2192 u : = u/2#= 2192 / 16 = 137. Pour l'incide i = 1, les opérations 24 à 30 de la boucle 18 sont donc les suivantes : u : = u + #1.# = 137 + 1 29 = 166 m : = u0.n'0 mod 2# = 3 6 mod 16 = 2 u : = u + m.n = 166 + 2 165 = 496 u : = u / 2# = 496 / 16 = 31 On obtient donc M 2= 31. De façon similaire on détermine #3 = 164 ; et M4= 16. On remarque que M 4 à l'issue de la boucle d'opérations 18 est égal à 181, ce qui est supérieur au modulus, par conséquent l'étape 20 de réduction doit être exécutée. Lors de l'opération 118 du procédé de la figure 7, la valeur de la variable #Fs-1, c'est-à-dire ici M F1, est affectée à la variable C. Les opérations 126 et 128 de la boucle d'opérations 120 du procédé de la figure 7 sont ensuite exécutées pour la valeur de l'indice i = 0. L'opération 126 consiste à calculer la variable #32, c'est-à-dire ici à calculer (M 3) 32. Les opérations successives suivantes sont donc exécutées : #8 = MonPro (#4, #4). M 16 =MonPro (M 8 M 8) Mj 32 = MOnpro (M 16, Mj 16) M 32 =MonPro (M 16, M) M'= MonPro (M 32&commat; M 32) M 64 = MonPro (M 32, M 32) Ces produits de Montgomery sont calculés selon le procédé décrit 32-64en regard de la figure 2. Les calculs des variables M, , M) , M, M étant similaires à celui de M ils ne seront pas décrits ici en détail. Le calcul de M 8 est effectué selon la relation suivante : #8 = MonPro (#4, #4) = MonPro (16,16) Lors de l'étape 16 du procédé de la figure 2, les premiers produits de Montgomery ai. b, c. a. d. ici #04 #4 et #14. #4 sont pré-calculés. Les valeurs de #04 et #14 sont les suivantes : #04 = 0000 (= 0 déc) M 14 = 0001 (= 1 déc. ) On en déduit donc les valeurs des premiers produits suivantes : Mo M4=OX16=0 Ml iv)"= 1 X16=16 La boucle d'opérations 18 de la figure 2 est ensuite exécutée successivement pour i = 0 et i=1. Pour i = 0, les opérations 24 à 30 de la boucle 18 sont donc les suivantes : u : =u+ai. b=0 m : = Uo. n'o mod 2"= 0 X 3 mod 16=0 u : = u + m. n 0 X 165 = 0 u : =u/2"=00 16=0 Pour i = 1, les opérations 24 à 30 de la boucle 18 sont donc les suivantes : u : =u+ai. b=0+16=16 m : = n'0 mod 2# = 0 X 3 mod 16 = 0 u : = u + m.n = 16 + 0 X 165 = 16 u : = u / 2# = 16 / 16 = 1 De façon similaire on obtient les résultats numériques suivants : # 16 = 136 ; # 32 = 31 ; M64=16' M96= 136. Lors de l'exécution de l'opération 128 du procédé de la figure 7, Fo étant différent de 0, le produit de Montgomery entre la variable C 32 M F0 est calculé selon la relation suivante : C :=MonPro((M96, M') où : - Mm'= 136 - ! 16. A l'issue du calcul de ce produit de Montgomery selon le procédé de la figure 2 on obtient le résultat suivant : C : =MonPro (136,16) = 91 La boucle d'opérations 120 du procédé de la figure 7 n'est exécutée qu'une seule fois puisque la valeur initiale de l'indice i est 0. A l'issue de l'exécution de la boucle d'opération 120, l'étape 122 est exécutée. Elle consiste à effectuer l'opération suivante : C : = MonPro (C, 1) où : - C = 91 ; - 1 est l'unité. A l'issue du calcul de ce produit de Montgomery selon le procédé de la figure 2 on obtient le résultat numérique suivant : C : = MonPro (91, 1) =1 Ainsi le résultat final de l'exponentiation modulaire 149100 mod 165 est égal à 1. On conçoit donc à la lecture de la description qui précède que l'invention permet d'accélérer le temps d'exécution du calcul d'un produit de Montgomery sur des moyens matériels de calcul. La description précédente décrit également l'application de l'invention à des procédés de cacul de multiplications et d'exponentiations modulaires, les procédés de calcul des multiplications et des exponentiations modulaires décrits étant eux-mêmes optimisés pour accélérer encore plus leur temps d'exécution. Les multiplications modulaires ou les exponentiations modulaires sont, comme on l'a déjà indiqué, utilisées dans de nombreux procédés et systèmes de cryptage/décryptage d'informations. Toutefois, les applications de l'invention ne se limitent pas à ce domaine d'application mais s'étendent à tous les domaines techniques où des produits de Montgomery, des multiplication modulaires ou des exponentiations modulaires sont utilisés, tels que par exemple le domaine des télécommunications ou autres. REVENDICATIONS 1. Procédé pour accélérer le temps d'exécution du calcul d'un produit de Montgomery en appliquant la méthode de Montgomery à radix élevé sur des moyens matériels de calcul (150 ; 200), ladite méthode comprenant une boucle d'opérations (18 ; 72) consistant à réitérer des opérations successives dont notamment : - une première opération d'addition (24 ; 76) entre une valeur d'un de plusieurs premiers produits, notés al. b, et une valeur d'une variable, notée u, selon une première relation u : =u+a !. b ; - une seconde opération d'addition (28 ; 80) entre une valeur d'un de plusieurs seconds produits, notés m. n, et une valeur de la variable u selon une deuxième relation u : = u + m. n, caractérisé en ce qu'au moins lesdites première et seconde opérations d'addition sont des opérations d'addition de Carry-Save pour accélérer le temps d'exécution d'une addition. 2. Procédé selon la revendication 1 comportant, dans la boucle d'opérations une troisième opération de division (30 ; 76) de la variable u par une puissance de 2, notée 200 où ro est le radix, selon une troisième relation u : =--, caractérisé en ce que la variable u est enregistrée sous la forme d'un 2 couple de Carry-Save formé par deux variables, notées C et S, pour l'exécution des opérations de la boucle (72) et en ce que la troisième opération de division de la variable u sous la forme d'un couple de CarrySave est réalisée en deux étapes, à savoir : - une étape préliminaire (82) de calcul et de stockage d'une retenue, notée Re, qui risque d'être perdue par la division de chaque variable C et S par la puissance de 2 ; - une étape de division (76) de chaque variable C et S par la puissance de 2. 3. Procédé selon la revendication 2, caractérisé en ce que l'étape préliminaire (82) de calcul de la retenue Re comprend l'opération d'additionner ..-de façon classique m bits de poids faible de la variable C, notés Co à cobits de poids faible de la variable S, notés So selon une quatrième relation Re : =Co +so 4. Procédé selon la revendication 3, caractérisé en ce qu'une recombinaison (78, 84) de u à partir des variables C et S du couple de CarrySave et de la retenue Re comprend l'opération de décaler à droite de co bits la retenue Re et d'additionner de façon conventionnelle le résultat obtenu aux variables C et S selon une cinquième relation u : = C+S+Re/20. 5. Procédé selon l'une quelconque des revendications 2 à 4, caractérisé en ce qu'il comporte à l'issue de l'exécution de la boucle d'opérations (72) : - une étape de recombinaison (84) de la variable u à partir au moins des valeurs des variables C et S du couple de Carry-Save calculées pendant l'exécution de la boucle d'opérations, et - une étape de réduction (86) de la variable u selon une sixième relation u : = u-n, où n est un modulus, lesdites étapes de recombinaison et de réduction de la variable u se chevauchant de manière à accélérer leur temps d'exécution. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le radix CD est égal à 4 bits pour optimiser le temps d'exécution du calcul d'un produit Montgomery sur des variables d'entrée du produit de Montgomery codées sur 512 ou 1024 bits. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les premiers produits al. b sont précalculés avant d'exécuter la boucle d'opérations (72). 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les seconds produits m. n sont précalculés avant d'exécuter la boucle d'opérations (72). 9. Procédé pour accélérer le temps d'exécution du calcul d'un premier et d'un second produits de Montgomery en appliquant pour chaque produit un procédé selon l'une quelconque des revendications 1 à 8, caractérisé en ce qu'il comporte au moins une première étape pendant laquelle. la première opération d'addition (76) pour le premier produit est réalisée en même temps que la seconde opération d'addition (80) pour le second produit. 10. Procédé selon la revendication 9, caractérisé en ce qu'il comporte au moins une seconde étape décalée dans le temps par rapport à la première, pendant laquelle la seconde opération d'addition (80) pour le premier produit est réalisée en même temps que la première opération d'addition (76) pour le second produit. 11. Procédé selon la revendication 9 ou 10, caractérisé en ce qu'il comporte à l'issue de l'exécution de la boucle d'opérations (72) : - une étape de recombinaison (84) puis de réduction (86) pour le premier produit exécuté en premier ; et ensuite, - une étape de recombinaison (84) puis de réduction (86) pour le second produit exécuté en second. 12. Procédé selon l'une des revendications 9 à 11, caractérisé en ce qu'une des variables d'entrée du premier produit de Montgomery exécuté en premier se compose des poids faibles d'une variable, et une des variables d'entrée du second produit de Montgomery exécuté en second se compose des poids forts de cette même variable. 13. Procédé pour accélérer le temps d'exécution du calcul d'une multiplication modulaire en appliquant une méthode mettant en oeuvre des produits de Montgomery, caractérisé en ce que le calcul des produits de Montgomery est réalisé en appliquant au moins l'un des procédés selon au moins l'une des revendications 1 à 12. 14. Procédé selon la revendication 13, caractérisé en ce que ladite méthode mettant en oeuvre des produits de Montgomery est la méthode de Montgomery. 15. Procédé pour accélérer le temps d'exécution du calcul d'une exponentiation modulaire en appliquant une méthode mettant en oeuvre des multiplications modulaires, caractérisé en ce que le calcul des multiplications modulaires est réalisé en appliquant un procédé selon la revendication 13 ou 14. 16. Procédé selon la revendication 15, caractérisé en ce que ladite méthode mettant en oeuvre des multiplications modulaires est la méthode mary avec une taille de mots de r bits. 17. Procédé selon la revendication 16, caractérisé en ce que la taille de mots r de la méthode m-ary est égale à 5 bits pour accélérer le temps d'exécution de la méthode m-ary lorsque des variables d'entrée du calcul de l'exponentiation modulaire sont codées sur 512 ou 1024 bits. 18. Procédé selon la revendication 16 ou 17, caractérisé en ce que les seconds produits m. n sont pré-calculés avant d'appliquer la méthode mary. 19. Procédé selon la revendication 15, caractérisé en ce que ladite méthode mettant en oeuvre des multiplications modulaires est la méthode des restes chinois. 20. Procédé pour accélérer le temps d'exécution du calcul d'une première exponentiation modulaire en appliquant une méthode mettant en oeuvre des secondes exponentiations modulaires, caractérisé en ce que les secondes exponentiations modulaires sont réalisées en appliquant un procédé selon l'une des revendications 15 à 19. 21. Procédé selon la revendication 20, caractérisé en ce que ladite méthode mettant en oeuvre des secondes exponentiations modulaires est la méthode des restes chinois. 22. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il est appliqué à des nombres codés sur plus de 320 bits. 23. Programme d'ordinateur comprenant des instructions de code de programme pour l'exécution de certaines étapes du procédé selon l'une quelconque des revendications 13 à 21 lorsque ledit programme est exécuté sur des moyens principaux de calcul (201) associés audits moyens matériels de calcul (150 ; 200). 24. Système d'accélération du temps d'exécution du calcul d'un produit de Montgomery par la méthode de Montgomery à radix élevé sur des moyens matériels de calcul (150 ; 200), ledit système comprenant : - des moyens (157 ; 230) pour effectuer une première opération d'addition entre une valeur d'un de plusieurs premiers produits, notés ai. b, et une valeur d'une variable, notée u, selon une première relation u : = u+a. b ; - des moyens (158 ; 232) pour effectuer une seconde opération d'addition entre une valeur d'un de plusieurs seconds produits, notés m. n, et une valeur de la variable u selon une deuxième relation u : = u + m. n, caractérisé en ce que les moyens pour effectuer la première et la seconde opérations d'addition comportent au moins un additionneur de Carry-Save (157,158 ; 230,232) 25. Système selon la revendication 24, caractérisé en ce que les moyens pour effectuer la première et la seconde opérations d'addition comportent au moins un premier additionneur de Carry-Save (157 ; 230) adapté pour réaliser la première opération d'addition et un second additionneur de Carry-Save (158 ; 232) adapté pour réaliser la seconde opération d'addition. 26. Système selon l'une des revendications 24 à 25, comportant des moyens classiques pour réaliser une troisième opération de division de la variable u par une puissance de 2, notée 2 où CD est le radix, selon une troisième relation u : =-, caractérisé en ce qu'il comporte des moyens de 20) stockage de la variable u sous la forme d'un couple de Carry-Save formé par deux variables, notées C et S et des moyens pour réaliser la troisième opération de division de la variable u sous la forme d'un couple de CarrySave comprenant : - des moyens de calcul et de stockage d'une retenue, notée Re, qui risque d'être perdue par la division de chaque variable C et S par la puissance de 2 ; - des moyens de division de chaque variable C et S par la puissance de 2. 27. Système selon la revendication 26, caractérisé en ce que les moyens de calcul et de stockage de la retenue Re comportent des moyens d'addition conventionnelle des co bits de poids faible de la variable C, notés Co, aux CD bits de poids faible de la variable S, notés So selon une quatrième relation Re : = Co + So 28. Système selon l'une quelconque des revendications 24 à 29, caractérisé en ce qu'il comprend : - des moyens (162 ; 236) de recombinaison de la variable u au moins à partir des valeurs des variables C et S du couple de Carry-Save, - des moyens (166 ; 238) de réduction de la variable u, lesdits moyens de recombinaison de la variable u et lesdits moyens de réduction étant raccordés l'un à l'autre de manière à chevaucher leur fonctionnement sous le contrôle de moyens de commande (156 ; 214). 29. Système selon l'une quelconque des revendications 24 à 30, caractérisé en ce que le radix o est égal à 4 bits pour optimiser le temps d'exécution du calcul d'un produit Montgomery sur des variables d'entrée du produit de Montgomery codées sur 512 ou 1024 bits. 30. Système selon l'une quelconque des revendications 24 à 31, caractérisé en ce qu'il comporte des moyens (164,160 ; 216,214, 218,222) de pré-calculs des premiers produits ai. b. 31. Système selon l'une quelconque des revendications 24 à 31, caractérisé en ce qu'il comporte des moyens (164,160 ; 216,214, 218,222) de pré-calculs des seconds produits m. n. 32. Système selon la revendication 30 ou 31 caractérisé en ce que lesdits moyens de pré-calculs des premiers et/ou des seconds produits comportent un additionneur conventionnel (160 ; 220,222). 33. Système d'accélération du temps d'exécution du calcul d'un premier et d'un second produits de Montgomery, caractérisé en ce qu'il comporte deux additionneurs de Carry-Save (230,232) activés simultanément. 34. Système selon la revendication 33, caractérisé en ce qu'il comporte un seul moyen (162) pour recombiner la variable u à partir au moins des valeurs de variables C et S du couple de Carry-Save, relié en entrée d'un seul moyen (166) de réduction de la variable u. 35. Système d'accélération du temps d'exécution du calcul d'une multiplication modulaire par une méthode mettant en oeuvre des produits de Montgomery, lesdits produits de Montgomery étant exécutés sur des moyens matériels de calcul (150 ; 200), caractérisé en ce qu'il comporte au moins un système (150 ; 202) d'accélération du temps d'exécution du calcul des produits de Montgomeryselon l'une des revendications 24 à 34. 36. Système d'accélération du temps d'exécution du calcul d'une multiplication modulaire par la méthode de Montgomery mettant en oeuvre des produits de Montgomery sur des moyens matériels de calcul (150 ; 200), caractérisé en ce qu'il comporte au moins un système (150 ; 202) d'accélération du temps d'exécution du calcul des produits de Montgomery selon l'une des revendications 24 à 34. 37. Système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par une méthode mettant en oeuvre des multiplications modulaires, caractérisé en ce qu'il comporte au moins un système (150 ; 200) d'accélération du temps d'exécution du calcul des multiplications modulaires selon la revendication 35 ou 36. 38. Système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par la méthode m-ary avec une taille de mots de r bits mettant en oeuvre des multiplications modulaires, caractérisé en ce qu'il comporte au moins un système (150 ; 200) d'accélération du temps d'exécution du calcul des multiplications modulaires selon la revendication 35 ou 36. 39. Système selon la revendication 38, caractérisé en ce qu'il comporte au moins un registre (242,244) à décalage à gauche de 5 bits pour accélérer l'exécution de la méthode m-ary avec une taille de mots r bits de la méthode m-ary égale à 5 bits. 40. Système d'accélération du temps d'exécution du calcul d'une exponentiation modulaire par la méthode des restes chinois mettant en oeuvre des multiplications modulaires, caractérisé en ce qu'il comporte au moins un système (150 ; 200) d'accélération du temps d'exécution du calcul des multiplications modulaires selon la revendication 37 ou 39. 41. Système d'accélération du temps d'exécution du calcul d'une première exponentiation modulaire par une méthode mettant en oeuvre des secondes exponentiations modulaires, caractérisé en ce qu'il comporte au moins un système (150 ; 200) d'accélération du temps d'exécution du calcul des secondes exponentiations modulaires selon l'une quelconque des revendications 37 à 40. 42. Système d'accéiération du temps d'exécution du calcul d'au moins une première exponentiation modulaire par la méthode des restes chinois mettant elle-même en oeuvre des secondes exponentiations modulaires, caractérisé en ce qu'il comporte au moins un système (150 ; 200) d'accélération du temps d'exécution du calcul des secondes exponentiations modulaires selon l'une quelconque des revendications 39 à 41. 43. Composant électronique caractérisé en ce qu'il comporte au moins un système selon l'une des revendications 24 à 42. 44. Composant électronique selon la revendication 45, caractérisé en ce qu'il est formé avec au moins un FPGA. 45. Carte électronique caractérisée en ce qu'elle comporte au moins un système selon l'une des revendications 24 à 44. 46. Carte électronique selon la revendication 45, caractérisée en ce qu'elle est conforme au standard PCI. 47. Machine caractérisée en ce qu'elle est associé à au moins un système selon l'une des revendications 24 à 46. 48. Procédé pour accélérer le temps d'exécution du calcul d'une première exponentiation modulaire, notée ME mod n où M est le message d'entrée, E est l'exposant et n est le modulus, sur des moyens principaux de calcul (201), caractérisé en ce qu'il comprend en outre : - une première étape de séparation du calcul de la première exponentiation modulaire en deux secondes exponentiations modulaires, en appliquant la méthode des restes chinois ; - une seconde étape consistant à calculer chacune des secondes exponentiations modulaires en appliquant la méthode m-ary, laquelle met en oeuvre des multiplications modulaires ; - des étapes consistant à effectuer les multiplications modulaires en appliquant une méthode mettant en ceuvre des produits de Montgomery. 49. Procédé selon la revendication 48, caractérisé en ce que les variables d'entrée sont des nombres entiers naturels codés sur plus de 320 bits. 50. Procédé selon la revendication 48 ou 49, caractérisé en ce que la taille de mots r de la méthode m-ary est égale à 5 bits pour accélérer le temps d'exécution de la méthode m-ary lorsque les variables d'entrée du calcul de l'exponentratiorr modulaire sont codées sur 512 ou 1024 bits. 51. Procédé selon l'une quelconque des revendications 48 à 50, caractérisé en ce que les calculs des secondes exponentiations modulaires sont effectués sensiblement en parallèle. 52. Procédé selon l'une quelconque des revendications 48 à 51, caractérisé en que les produits de Montgomery sont calculés en utilisant la méthode de Montgomery à radix élevé. 53. Procédé selon la revendication 52, caractérisé en ce que la méthode de Montgomery à radix élevé est mise en oeuvre conformément à l'un des procédés selon l'une quelconque des revendications 1 à 9. 54. Programme d'ordinateur comprenant des instructions de code de programme pour l'exécution de certaines étapes du procédé selon l'une quelconque des revendications 48 à 52 lorsque ledit programme est exécuté sur les moyens principaux de calcul (201).