Brevet FR2917198A1 — publié le 20081212

Opérateur de réduction modulaire amélioré La présente invention concerne un dispositif de réduction modulaire amélioré. Elle s'applique notamment aux composants de calcul utilisés en cryptographie asymétrique. Généralement, les procédés de cryptage à clé publique s'appuient sur des calculs opérés dans un anneau modulaire de nombres algébriques. Les opérations cryptographiques étant donc effectuées en arithmétique modulaire, l'opération de réduction modulaire est très fréquemment requise. En effet, dans un anneau Zn, cette opération permet de transformer un premier nombre supérieur à n en un nombre inférieur à n et congru au premier. Un enjeu important lié aux performances des composants de calculs cryptographiques concerne cette opération. Une méthode naturelle pour effectuer une réduction modulaire est de calculer une division euclidienne, le résultat étant égal au reste de cette division. Cependant, les performances d'une telle opération sont très médiocres et le calcul de division nécessite généralement l'utilisation d'un microprocesseur. Actuellement, certains procédés de réduction modulaire permettent d'obtenir de faibles temps de calcul, mais ils sont généralement limités par la taille des nombres à traiter. D'autres procédés sont flexibles, c'est à dire qu'ils permettent, au contraire, de traiter des nombres de tailles quelconques, mais ils nécessitent souvent un temps de calcul très important. Un brevet publié sous le numéro EP0712071 propose également un procédé de réduction modulaire selon la méthode de Montgomery. Cependant, ce procédé implique le calcul d'un paramètre H, calcul inutile pour certaines applications. De plus, aucune solution de l'art antérieur n'est aisément intégrable au sein d'un composant cryptographique comportant d'autres modules de calculs. Un but de l'invention est de réaliser un dispositif de mise en oeuvre d'un procédé de réduction modulaire permettant de traiter, dans un temps de calcul réduit, des nombres de taille non déterminée à l'avance, ledit dispositif pouvant être intégré, par exemple, aisément dans un composant de calcul cryptographique. A cet effet, l'invention a pour objet un dispositif de réduction modulaire, caractérisé en ce qu'il comporte un multiplieur mettant en oeuvre une opération de multiplication de Montgomery utilisant une base de numération r élevée, supérieure ou égale à 4. Le multiplieur peut mettre en oeuvre l'algorithme suivant : SFpo•q pour i allant de 0 à tn-1, faire : m;E-So.n' mod r SFp;.q + (m;n+S)/r mt,FSo.n' mod r SF(mtn.n+S)/r où tä désigne la taille du module n en nombre de mots-machine, p et q les opérandes à multiplier, m; des coefficients intermédiaires, S le résultat de la multiplication, et la valeur n' étant égale à ùn"1 mod r. Selon un mode de réalisation, le multiplieur comporte un multiplieur-additionneur comporte p couples logique-registre pipeliné, recevant plusieurs chiffres à additionner et à multiplier, au moins deux sorties correspondant au poids faible et au poids fort, un additionneur recevant les deux sorties du multiplieur-additionneur, le nombre p étant choisi de façon telle que la fréquence maximale F1 max du multiplieur-additionneur soit supérieure ou égale à la fréquence maximale F2max de l'additionneur. Le dispositif de réduction modulaire peut comporter également un séquenceur, un bloc additionneur et un module mémoire, une sortie du séquenceur étant reliée à une entrée de commande du multiplieur, une sortie du séquenceur étant reliée à une entrée de commande du bloc additionneur, et le module mémoire étant relié au multiplieur et à l'additionneur pour échanger des données. L'invention a également pour objet un composant cryptographique comportant un dispositif de réduction modulaire selon l'une des revendications précédentes. D'autres caractéristiques apparaîtront à la lecture de la description détaillée donnée à titre d'exemple et non limitative qui suit faite en regard de dessins annexés qui représentent : la figure 1, un synoptique de dispositif de réduction modulaire selon l'invention, la figure 2, un exemple de cellule de multiplication-addition utilisée par le dispositif de réduction modulaire selon l'invention, la figure 3, un exemple de multiplieur modulaire de Montgomery utilisé par le dispositif de réduction modulaire selon l'invention. La figure 1 présente un synoptique de dispositif de réduction modulaire selon l'invention. Le dispositif de réduction modulaire 1 comporte un séquenceur 11, un bloc multiplieur 12, un bloc additionneur 13, un module mémoire 14. Le bloc multiplieur 12 et le bloc additionneur 13 reçoivent des commandes du séquenceur 11 et échangent chacun des données avec le module mémoire 14. Une application utilisatrice 15 envoie des commandes au séquenceur 11 et échange des données avec le module mémoire 14. Les données manipulées sont enregistrées sur des mots-machine chacun composés de b bits. La dimension b des mots-machines est généralement une puissance de 2. La base de numération r est définie comme étant égale à 2b. Le module n est un nombre impair enregistré sur tn mots machine. On définit R comme une puissance de la base de numération r, R étant supérieur au module n. Un nombre x peut se décomposer dans la base r en t+1 chiffres x; comme suit : x=xo+xt.r+x2.r2+ ... +xt.rt, où chaque chiffre x; est de la taille d'un mot-machine. Enfin, un ensemble de nombres g; est défini comme suit : g; = R2+' mod n, i variant de 0 à k-1, k étant une valeur maximale, déterminée par exemple par l'application utilisatrice 15 de l'invention. Les valeurs g;, sont précalculées, par exemple par l'application utilisatrice 15 de l'invention, par une autre méthode de réduction modulaire. En effet, les valeurs g; ne peuvent pas être précalculées par le dispositif de réduction modulaire 1 puisque ces mêmes valeurs g; sont nécessaires au fonctionnement du dispositif. Une fois ces valeurs g; calculées, le dispositif de réduction modulaire 1 est alors en mesure de calculer x mod n pour des valeurs de x au plus égales à Rk+'-1. Le dispositif de réduction modulaire 1 selon l'invention met en oeuvre le procédé suivant pour réduire le nombre x : Poser s=0, u=0 Pour i variant de 0 à k-1, faire les opérations suivantes : uFMMul(x;, g;) sFMAdd(s, u) retourner MMuI(s, 1). où u et s sont des variables temporaires, MMuI() un algorithme de multiplication modulaire mis en oeuvre dans le bloc multiplieur 12 et explicité ci-après, et MAdd() un algorithme d'addition modulaire mis en oeuvre dans le bloc additionneur 13. Le module mémoire 14 mémorise les nombres n, gi, les chiffres x; de x et les valeurs u et s. Le séquenceur 11 commande le bloc multiplieur 12 et le bloc additionneur 13 pour exécuter l'algorithme de réduction modulaire, en utilisant les données enregistrées dans le module mémoire 14. Le bloc multiplieur 12 met en oeuvre une variante de l'algorithme de Montgomery opérant sur une base de numération r élevée (r>=4). Il travaille avec une valeur de R=rt"+' Les chiffres de x, utilisés par le séquenceur 11, ont donc une taille de t"+1 mots. Une autre valeur notée n' et égale à ùn"' mod r, doit être précalculée, par exemple par l'application utilisatrice 15 de l'invention. Le bloc multiplieur 12 dispose, par exemple, d'un premier registre mémorisant la valeur t" et d'un second registre mémorisant la valeur n'. Ces deux registres sont chargés à l'initialisation du bloc. Le bloc multiplieur 12 est interfacé avec le module mémoire 14, duquel il prend ses paramètres et place le résultat du calcul. II prend en entrée deux nombres de taille t"+1 mots et le résultat est un nombre de t"+1 mots. Le module n ayant une taille de t" mots, on peut écrire que les entrées p et q sous la forme p=p'+ep.n et q=q'+eq.n, ou p' et q' sont inférieur à n, et ep et eq ont une taille binaire gk_1 occupe les mots-machine d'adresses k.tn+1 à (k+1).tn x occupe les mots-machine d'adresses (k+1).tn+1 à 2 k.tä . 35 u occupe les mots-machine d'adresses (2k)tn+1 à (2k+1)tn s occupe les mots-machine d'adresses (2k+1)tä+1 à (2k+2)tä Les variables temporaires u et s sont initialisées à zéro et un emplacement est réservé pour enregistrer le résultat aux adresses (2k+2)tä+1 à (2k+3)tn. Trois paramètres sont passés au bloc multiplieur 12 lors de chaque appel. Le premier paramètre et l'adresse en mémoire 14 de la première opérande, le deuxième paramètre est l'adresse en mémoire 14 de la seconde opérande, et le troisième paramètre est l'adresse en mémoire 14 de l'emplacement prévu pour enregistrer le résultat de la multiplication. Deux paramètres sont passés au bloc additionneur 13, les deux paramètres correspondant aux adresses en mémoire 14 des deux opérandes. Le résultat de l'addition est placé à l'adresse de la deuxième opérande. Le séquenceur 11 peut alors dérouler le procédé de réduction modulaire avec les données en mémoire de la façon suivante : MMul((k+1)tä+1, tn+1, (2k)tn+1) (adresses de xo, go et u) MAdd((2k)tn+1, (2k+1)tä+1) (adresses de u et s) MMuI((2k-.1)tä+1, tn+1, (2k)tä+1) (adresses de xk, go et u) MAdd ((2k)tn+1, (2k+1)tn+1) (adresses de u et s) MMul((2k-r-1)tn+1, adresse(1), (2k+3)tn+1)) (le deuxième paramètre est forcé à la valeur 1). Les paramètres d'entrée du bloc multiplieur 12 étant des adresses en mémoire, le calcul MMuI(s,1) peut être réalisé, soit en plaçant la valeur 1 à une adresse particulière en mémoire 14, soit par un séquencement particulier du bloc où le second paramètre est forcé à la valeur 1. Le procédé de Montgomery mis en oeuvre par le bloc multiplieur 12 produit un résultat compris entre 0 et 2n-1, congru au résultat classique modulo n. L'opération MMul(s, 1) permet de retrouver le résultat classique. Le bloc multiplieur 12 manipulant des données modulo 2n, le bloc additionneur 13 doit donc effectuer des additions modulo 2n. II réalise ces additions en utilisant un additionneur multiprécision, un soustracteur multiprécision, et un comparateur multiprécision. Ainsi, l'opération d'addition modulaire a+b mod 2n de deux nombres a et b est réalisée comme suit : calculer t=a+ b si t>=2n, calculer t=t-2n retourner t t étant une variable contenant le résultat de l'addition. La figure 2 est un exemple de cellule de multiplication-addition utilisée par le bloc multiplieur 12 pour effectuer l'opération SFp;.q+(m;n+S)/r du procédé présenté plus haut. La cellule est pipelinée pour améliorer ses performances. Le pipeline consiste à rajouter des barrières de registres entre les phases logiques afin de réduire le chemin critique, et ainsi d'augmenter la fréquence maximale de fonctionnement (théoriquement celle d'un 1 o additionneur en base r). On définit la profondeur de pipeline d'un composant élémentaire par son nombre de registres internes. On ne compte pas le registre de sortie. L'exemple donné à la figure 2 suppose que l'on dispose d'un multiplieur- additionneur 1 pipeliné, de profondeur p. 15 Il comporte notamment un ensemble de couples logique-registre (Ii, ri). Le nombre p de ces couples est notamment choisi pour que la fréquence maximale F1 max du multiplieur-additionneur pipeliné soit supérieure ou égale à la fréquence maximale F2max de l'additionneur, les valeurs de ces deux fréquences étant les plus proches possibles. 20 La fréquence maximale de fonctionnement du multiplieur-additionneur est donnée par l'inverse du temps d'exécution de l'opération de multiplication-addition, alors que la fréquence maximale de fonctionnement du multiplieur-additionneur pipeliné est donné par l'inverse du temps d'exécution d'un seul des p étages. Pour un fonctionnement optimal, on 25 détermine la fréquence maximale de l'additionneur, ce qui donne le temps d'exécution de l'additionneur et on découpe le multiplieur-additionneur en p étages de temps de traversée inférieur ou égal, mais le plus proche possible, au temps d'exécution de l'additionneur. Les entrées du multiplieur-additionneur 21 correspondent à trois 30 chiffres : p;, q; et vj et la sortie est un couple de chiffres correspondant à LSB(p;qj+vj) et MSB(p;qj+vj). La sortie tient sur deux chiffres. Les résultats du multiplieur-additionneur sont transmis à un additionneur trois entrées, référencé 22 : chiffre+chiffre+carry --+ chiffre+carry, fonctionnant en 1 cycle (pipeline 0) à la fréquence F2max. 8 Le registre Temp correspond au stockage de c nécessaire au calcul suivant : addition de c avec le LSB suivant et la retenue précédente. Les données (chiffres de pxQ +V) sortent donc en série à chaque cycle, chiffre de poids faible en tête, dans le même sens que la propagation 5 de la retenue. La figure 3 décrit un exemple de bloc multiplieur 12, avec un dispositif 3 adapté à la partie basse de la multiplication, et un dispositif 5 composé de registres et de multiplexeurs. 10 Dans cet exemple, les principaux composants du circuit sont : un multiplieur-additionneur 21 pipeliné, un additionneur 3 entrées, référencé 22, un multiplieur partie basse 23 et un additionneur 2 bits + 1 bit vers 2 bits, désigné 24. Une barrière de nreg_max-1 registres et de multiplexeurs, désigné 25. 15 Le nombre de multiplexeurs et de registres dépend notamment des données intrinsèques au circuit, les profondeurs de pipeline p et k, ainsi que du nombre de chiffres des données. Dans l'exemple de la figure 3, la barrière de nreg-max-1 registres et de multiplexeurs (composant référencé 25) a notamment pour fonction de 20 retarder l'arrivée des données dans le multiplieur-additionneur 1. Multiplication partie basse ù composant 3 Dans la boucle principale de l'algorithme, à chaque itération, on détermine m;, le chiffre qui rend la quantité S+m;N divisible par r. m; est déterminé en effectuant une multiplication partielle du chiffre de poids 25 faible de S avec une constante N', précalculée une fois pour toute pour un module N donné. Dans cette multiplication, seule la partie basse nous intéresse : on effectue cette opération modulo r. Cette opération étant plus lente qu'une addition, elle est également pipeliné. On appelle k la profondeur de pipeline de cet opérateur 30 et on suppose k Rebouclage, latence et registres supplémentaires Deux cas sont distingués, le passage de la multiplication classique a;B+T S, (1), à la multiplication et décalage (m;xN+S)/r -* T , (2), et le 35 passage de (2) à (1), le retard n'étant pas le même. Ce retard détermine notamment le nombre de registres à utiliser : n'Ceg ou nregk selon les cas. Ainsi par exemple, dans le passage de (2) à (1), et dans le cas où p+2 n (cas où n'feg est défini), le nombre de registres à utiliser est n'feg. Comme il y en a nreg_m1X -1, il faut en sauter nreg-mex -1- n'reg• Ceci est fait grâce aux multiplexeurs, placés en conséquence. Passage de (1) à (2) Pour pouvoir chaîner sans perte de temps (ie : sans rajouter de latence) les multiplications-additions (1) et (2), il convient de déterminer m; avant d'avoir parcouru la totalité des chiffres de la multiplication en cours. II est donc souhaitable de réaliser la condition : p+k+2 5 n. En effet, le chiffre de poids faible du résultat de la multiplication-addition est disponible lorsque le chiffre d'indice p+1 se présente à l'entrée du multiplieur-additionneur. Au cycle suivant, l'addition est réalisée. So est disponible, le calcul 15 de m; peut donc débuter. Après k+1 coups d'horloge supplémentaires, m; est disponible en sortie du multiplieur partie basse. Il peut donc être utilisé comme entrée du multiplieur-additionneur au coup d'horloge suivant. Ceci explique la condition p+k+2 n. Rebouclage 20 Si on veut chaîner les multiplications-additions (1) et (2), sans perte de temps, on choisit p+k+2 n. Dans ce cas, la donnée m; est disponible avant la fin de parcours des chiffres de la multiplication-addition en cours. On reboucle donc cette valeur, afin de retarder son entrée dans le multiplieur-additionneur. On définit 25 alors nrebk=n-p-k-2 qui correspond au nombre de rebouclage nécessaire de cette valeur. Dans le cas particulier où nrebk=O, la donnée m; est synchrone avec les nouvelles entrées du multiplieur-additionneur. Cependant, dans tous les cas on reboucle la valeur m; n fois afin 30 que l'entrée soit la même pour tous les chiffres de N. Si en revanche n-p-k-2 est négatif, ceci correspond à un retard du calcul de m;, on rajoute donc de la latence. Latence Lorsque la condition p+k+2 n n'est pas réalisée, ceci signifie que les sorties ont du retard sur les entrées, des coups d'attente (latence) pour synchroniser les données sont rajoutés. Pendant les coups de latence, les entrées sont bloquées (au sens où on prend comme nouvelle entrée 0 (pour tenir compte de la dernière retenue de S)), le calcul se poursuivant pour les données déjà entrées. Dans ce cas (p+k+2>n), on définit nlatk=p+k+2-n. Cette grandeur représente le nombre de coups de latence à effectuer avant de présenter de io nouvelles entrées au multiplieur-additionneur. Dès que m; est déterminé, il est utilisé comme entrée de la multiplication-addition. So quant à lui est forcément déterminé avant m; et doit être stocké (ainsi que S,, S2...) jusqu'à ce que m; soit calculé. Pour cette raison, on rajoute des registres afin de retarder l'arrivée 15 des résultats à l'entrée du multiplieur-additionneur. Registres supplémentaires Deux cas sont distingués. En effet, selon que p+k+2 est plus grand ou plus petit que n, le nombre et l'utilisation des registres ajoutés ne sont cependant pas les mêmes. 20 Cas 1 : p+k+2 n Dans ce cas, l'ensemble So et m; est déterminé avant la fin de parcours des chiffres des données. Pour m;, voir la section sur le rebouclage, on utilise la méthode décrite ci-dessus dans la section de rebouclage. 25 Pour So, on retarde son arrivée à l'entrée du multiplieur additionneur par le rajout de registres à décalage. On définit alors nfe9 par nfe9=n-p-1. Cette quantité correspond au nombre de registres à rajouter pour synchroniser l'arrivée du chiffre de poids faible du résultat d'une multiplication-addition avec les données de poids 30 faible de la suivante. Cas 2 : p+k+2 > n Deux sous cas selon que p est ou non plus grand que n, sont distingués. En fait, quelque soit la valeur de p, m; sera déterminé après So. On retarde donc l'arrivée de So à l'entrée du multiplieur par le rajout de registres. Ce nombre de registres ne dépendra donc que de k, la profondeur du pipeline de l'opérateur multiplication partie basse. On définit donc dans ce cas, nfegk=k+1 le nombre de registres à 5 rajouter pour retarder l'arrivée de So à l'entrée du multiplieur. Passage de (2) à (1) On s'intéresse ici au passage de (2) à (1). Si il n'y a pas de m; à déterminer, il faut en revanche tenir compte du décalage (division par r). Comme précédemment, on synchronise l'arrivée des résultats 1 o avec l'entrée de nouvelles données. Ici, seule la quantité p est importante, m; n'ayant pas besoin d'être déterminé, k n'intervient pas. En revanche, on prend en compte le décalage (ie : considérer to comme chiffre de poids faible et non pas t_1 qui est nul). Ceci peut être vu comme un niveau de pipeline supplémentaire. 15 Registres supplémentaires et latence On distingue donc comme précédemment, deux cas, selon que p+2 est plus grand que n ou pas. Cas 1:p+2n Dans ce cas, to est disponible avant la fin de parcours des chiffres 20 des données. On rajoute donc des registres pour prendre en compte le retard. On définit alors, n'reg=n-p-2 qui indique le nombre de registre à rajouter pour prendre en compte le retard. Cas 2 : p+2> n Dans ce cas, to est disponible après le parcours des chiffres des 25 données. On retarde donc l'entrée des nouvelles données. Ceci se fait comme précédemment en rajoutant des coups d'attente (latence). On définit n'iat=p+2-n qui représente le nombre de coups d'attente à réaliser. Additionneur supplémentaire et rebouclage La détermination de tn se fait par une addition de sn+1 avec c, Sn+1 30 2 et c Tableau 1 p+k+2 n p+k+2 > n p+2 n) p+2 n p+2>n n'req n-p-2 n-p-2 0 n'iat 0 0 p+2-n nfeq n-p-1 k+1 nlatk 0 p+k+2-n nrebk n-p-k-2 0 nreb n+nlatk-1 =n-1 n+nlatk-l=p+k+1 En pratique le nombre de registres à rajouter est défini par nreg-15 max=max(nregk,nreg) et est égal à n-p-1 si p+k+2 n et k+1 sinon. En particulier, nreg-max > 1. Les étapes nécessitant moins de registres sont effectuées en raccourcissant la chaîne des registres par le rajout de multiplexeurs. Séquencement décrit à la figure 3 20 Un exemple de séquencement des opérations est décrit en relation avec la figure 3. On adopte comme convention de fixer les états des multiplexeurs à la fin du coup d'horloge en cours pour commander le coup d'horloge suivant. Comportement général des multiplexeurs 25 La latence intervient ici. En effet, selon qu'il y a de la latence ou non, les changements d'état ne se font pas aux même moments. II est cependant possible d'utiliser les paramètres de correction de latence du circuit (n'lat et nlatk) pour définir un comportement général des multiplexeurs. En effet, on peut supposer que IBI=n+1+ n'lat avec les n'lat premiers chiffres de B nuls. (Sauf évidemment pour le calcul de aoB). De même, on peut supposer que INI=n+1+ nlatk avec les nlatk premiers chiffres de N nuls. De plus, on isole le cas particulier du premier calcul aoB pour lequel on ne prend pas en compte la latence (les n'lat premiers chiffres nuls 1 o de B). Enfin, passé ce cas particulier, on remarque que les données présentées successivement en entrée du multiplieur-additionneur peuvent être regroupées par tranches de 2n+2+ n'lat + nlatk données. Les nlatk +n+1 premières correspondent aux données m; et Ni. Les n'lat +n+1 dernières 15 correspondent aux données a, et loi. On aura donc un comportement cyclique des multiplexeurs, de période 2 n+2+n'lat+nlatk mux 1 muxl est un multiplexeur à deux états symbolisant quel type d'entrées doit 20 être pris en compte au niveau du multiplieur-additionneur. Les deux états sont : 0 : x=a1 et y=bi sont pris comme entrées du multiplieur-additionneur. - 1 : x=m; et y=Ni sont pris comme entrées du multiplieur-25 additionneur. L'utilisation des constantes n'lat et nlatk permet notamment de vérifier que le changement d'état intervient lorsque tous les chiffres de B (ou de N) ont été parcourus. Pour ao on ne prend pas en compte les n'lat premiers chiffres nuls. 30 Le calcul commence directement par les données aobn'lat . Ainsi mux1, initialement à 0 (reset), reste dans cet état pendant les n premiers coups d'horloge, et passe dans l'état 1 au n+1 ème coup. A la fin de ce n+l ème coup, les données présentées en entrée du multiplieur-additionneur sont ao et bn, tous les chiffres de B auront donc été 35 parcourus. muxl est à 1 à la fin de ce même coup d'horloge, donc à la fin du coup d'horloge suivant, m1 et No seront présentés en entrée du multiplieur-additionneur. Le comportement général de muxl en fonction du coup d'horloge 5 clock peut être résumé par les étapes suivantes : Si clock Or l'addition doit être réalisée lorsque tn_1 se trouve dans le registrede sortie de l'additionneur puisqu'à ce moment on dispose de la bonne valeur de carry à ajouter à sn+1 pour déterminer tn. mux2 doit donc être dans l'état 1 lorsque tn_1 se trouve dans le registre de sortie de l'additionneur, c'est à dire au coup d'horloge p+3+n+n,atk+n+l =p+2n+n,atk+4. (Il ne faut pas oublier qu'avec le décalage, tn_1 correspond au calcul de m1xNn ). Par périodicité, on peut décrire le comportement général de mux2. Si clock = p+2n+4+n,atk mod 2n+2+ n,atk + n',at , alors mux2=1 10 Sinon mux2=0 mux3 Lors de la boucle sur les chiffres de N, un décalage à droite doit être effectué sur les chiffres de la sortie pour tenir compte de la division par r. mux3 est un multiplexeur à deux états symbolisant à quel moment on 15 effectue le décalage (modélisé par un saut de registre). Les deux états sont : - 0 : Le décalage n'est pas effectué. 1 : Le décalage est effectué. Ce décalage d'indice est réalisé en hardware par le saut d'un registre. Le décalage intervient lorsque la donnée sn+1 est présente dans le 20 registre Stab1. En effet, à cet instant, le registre S de l'additionneur contient, suivant la valeur de n,atk, soit 0 (résultat d'un coup de latence), soit la valeur de to. to ayant un temps de retard par rapport à la multiplication classique (so), il doit alors sauter un registre pour rattraper ce temps de retard. Ce décalage doit donc être effectué jusqu'à ce que tous les chiffres (latence 25 comprise) de T, jusqu'à tn_1 , soient déterminés. En effet, lorsque tn_1 est déterminé (ie : dans le registre S de l'additionneur), au coup d'horloge suivant, tn est déterminé dans Stab1 par addition de c avec sn+1, et tn_1 se trouve dans le registre Stab2. Le décalage prend alors fin, les données tn_1 et tn étant de nouveau dans deux registres successifs. mux3 reste donc dans 30 l'état 1 durant n+ n,atk =nreb +1 coups. Comme nous l'avons dit précédemment, le décalage correspond au saut du registre Stab1 qui est alors utilisé pour le rebouclage de sn+1. Le rebouclage de sn+1 intervient donc au même moment que le décalage. Donc le changement d'état de mux3 de 0 à 1 indique également qu'il faut reboucler la valeur sä+1 dans le registre Stabl. Ce rebouclage à lieu nfeb fois. Initialement, mux3 est dans l'état 0 (multiplication classique). Il passe à 1 lorsque est dans le registre Stabl. Or sr, est dans S au coup d'horloge p+3+n (cf : comportement de mux2). Donc sr,+1 est dans ce même registre au coup p+n+4, et dans Stabl au coup suivant : p+n+5. Par périodicité, on déduit le comportement général de mux3 : Si clock La remarque précédente permet de définir et de décrire la commande reb. Commande reb Cette commande représente les instants pour lesquels sr+l doit être rebouclé dans le registre Stabl . Les deux états sont : - 0 : pas de rebouclage 1 : rebouclage Le comportement de reb est décrit en même temps que celui de mux3. On en déduit donc : Si clock Le dispositif de réduction modulaire bénéficie des très bonnes performances et de la flexibilité du multiplieur utilisé. Un autre avantage du dispositif de réduction modulaire selon l'invention est de proposer une solution aisément intégrable dans un composant cryptographique proposant d'autres fonctions de calcul.20 REVENDICATIONS 1. Dispositif de réduction modulaire, caractérisé en ce qu'il comporte un multiplieur (12) mettant en oeuvre une opération de multiplication de Montgomery utilisant une base de numération r élevée, supérieure ou égale à 4. 2. Dispositif de réduction modulaire selon la revendication 1, caractérisé en ce que le multiplieur (12) met en oeuvre l'algorithme suivant : i. SE-po.q pour i allant de 0 à tn-1, faire : a. rn;E-So.n' mod r b. SE-p;.q + (m;n+S)/r iii. mtnE-So.n' mod r iv. SE-(mtn.n+S)/r 15 où tn désigne la taille du module n en nombre de mots-machine, p et q les opérandes à multiplier, m; des coefficients intermédiaires, S le résultat de la multiplication, et la valeur n' étant égale à ùn-' mod r. 20 3. Dispositif de réduction modulaire selon l'une des revendications précédentes, caractérisé en ce qu'il comporte un multiplieur-additionneur comportant p couples logique-registre pipeliné, recevant plusieurs chiffres à additionner et à multiplier, au moins deux sorties correspondant au poids faible et au poids fort, un additionneur 25 recevant les deux sorties du multiplieur-additionneur, le nombre p étant choisi de façon telle que la fréquence maximale F1 max du multiplieur-additionneur soit supérieure ou égale à la fréquence maximale F2max de l'additionneur. 30 4. Dispositif de réduction modulaire selon l'une des revendications précédentes, caractérisé en ce qu'il comporte également un séquenceur (11), un bloc additionneur (13) et un module mémoire (14), une sortie du séquenceur étant reliée à une entrée de commande du multiplieur, une sortie du séquenceur étant reliée à uneentrée de commande du bloc additionneur, et le module mémoire étant relié au multiplieur et à l'additionneur pour échanger des données. 5. Composant cryptographique comportant un dispositif de réduction modulaire selon l'une des revendications précédentes.