WO2006103288A1 - Dispositif implementant la multiplication modulaire de montgomery - Google Patents

Dispositif implementant la multiplication modulaire de montgomery Download PDF

Info

Publication number
WO2006103288A1
WO2006103288A1 PCT/EP2006/061235 EP2006061235W WO2006103288A1 WO 2006103288 A1 WO2006103288 A1 WO 2006103288A1 EP 2006061235 W EP2006061235 W EP 2006061235W WO 2006103288 A1 WO2006103288 A1 WO 2006103288A1
Authority
WO
WIPO (PCT)
Prior art keywords
adder
multiplier
multiplication
clock
register
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/EP2006/061235
Other languages
English (en)
Inventor
Florent Bernard
Alain Sauzet
Eric Garrido
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Thales SA
Original Assignee
Thales SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Thales SA filed Critical Thales SA
Priority to JP2008503528A priority Critical patent/JP2008535011A/ja
Priority to US11/910,443 priority patent/US8073891B2/en
Priority to DE602006021558T priority patent/DE602006021558D1/de
Priority to EP06725481A priority patent/EP1869545B1/fr
Publication of WO2006103288A1 publication Critical patent/WO2006103288A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3867—Concurrent instruction execution, e.g. pipeline or look ahead using instruction pipelines
    • G06F9/3869—Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/5443—Sum of products
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/728—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic using Montgomery reduction
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
    • G06F2207/3804—Details
    • G06F2207/386—Special constructional features
    • G06F2207/3884—Pipelining

Definitions

  • the invention relates to a method and a device for executing modular Montgomery multiplication.
  • Modular multiplication is processed on a modular ring (ZJNZ) or on a body (ZJpZ) with p prime number.
  • the operating frequency of a p-stage pipeline multiplier-adder given by the inverse of the crossing time of a threshold of the stages of the multiplier-adder is defined.
  • pipeline is defined as an operation of adding register barriers between the logical phases and the resulting architecture.
  • Modular multiplication is at the heart of many public key cryptosystems (RSA, ECDSA).
  • the first level is before the synthesis of the architecture.
  • the design of the architecture must have enough degrees of freedom to satisfy given hardware / time constraints.
  • the second level is after the synthesis of the architecture.
  • the architecture must be able to handle different data sizes in order to perform both ECDSA type operations (Elliptical Curve Digital Signature Algorithm) 256-512 bit size as RSA type operations (named after its inventors: Rivest, Shamir, Adleman) size 1024-4096 bits.
  • ECDSA Electronic Curve Digital Signature Algorithm
  • RSA Rivest, Shamir, Adleman
  • the product time * surface is used.
  • the time is given in number of clock cycles.
  • the surface is estimated in terms of the number of equivalent Nand gates (ASIC) or in terms of elementary cells (LC (Logic CeII) or CLB (Logic Block Configuration), sequential combinatorial blocks, for FPGA or field-programmable gate arrays).
  • ASIC equivalent Nand gates
  • LC Logical CeII
  • CLB Logical Block Configuration
  • Exotic ie unconventional number representations, such as the Residue Number System (RNS) representation, are also used to parallelize the implementation of the modular multiplication, for example, LS Didier, JC Bajard and P. Komerup, An RNS Montgomery Multiplication Algorithm, Proceedings of ARITH13, IEEE Computer Society, 1997, pp. 234-239.
  • RNS Residue Number System
  • this solution requires significant hardware resources and does not solve the problem of flexibility.
  • the first publication of such an architecture is due to Alexandre F. Tenca and Cetin K. Koç, A scalable architecture for Montgomery multiplication, CHES'99, 1999.
  • Other more recent publications take up the idea developed in this article and propose improvements and extensions. This is the case of :
  • Step S ⁇ -aiB + (mjN + S) / r is the most expensive from a computational point of view. It can be noticed that this step is obtained by doing twice the same operation: longxx + longxx ⁇ xxxx. This step is performed by looping over the digits of the two long integers (Y and Z).
  • T is well represented by n + 1 digits.
  • the present invention is based on a new approach which notably considers, in normal operation, a single cell of larger size than the cells considered in the prior art and an iteration process on itself using a Montgomery algorithm based on high. That is, in the following, the base r is assumed to be greater than or equal to 4. In practice, the base r is most often 2 32 or 264 , which justifies the high base naming.
  • the invention relates to a device for implementing modular multiplication, characterized in that it comprises at least one calculation cell comprising a multiplier-adder comprising p logical-pipeline register pairs, receiving several digits to be added and multiply, at least two outputs corresponding to the low weight and the high weight, an adder receiving the two outputs of the multiplier-adder, the number p being chosen such that the maximum frequency of the multiplier-adder is greater than or equal to the maximum frequency of the adder.
  • the device may comprise a lower part multiplier whose inputs correspond to the output LSB of the adder and to a precalculated constant, said multiplier being pipeline over a depth k.
  • the invention particularly has the following advantages: the use of a higher base reduces the number of cycles required to calculate a modular multiplication. Only one elementary cell is then used. The surface time product of this architecture is thus improved.
  • Figure 1 an example of arrangement of the elementary components of a multiplier-adder cell according to the invention
  • Figure 2 an example of arrangement of components constituting the heart of the Montgomery modular multiplier.
  • the idea implemented in the multiplier according to the invention consists in particular of splitting the operation xxy + z + c into (x ⁇ y + z) + c, by pipelinating the multiplication-addition operation (xxy + z) and by adding, as the results are obtained, the variable c, where x, y and z are the data, where c is the most significant digit from the previous iteration.
  • the pipeline consists of adding register barriers between the logical phases in order to reduce the critical path, and thus increase the maximum operating frequency (theoretically that of an adder in base r).
  • the pipeline depth of an elementary component is defined by its number of internal registers. We do not count the output register.
  • FIG. 1 assumes that there is a multiplier-adder 1 pipeline, of depth p.
  • the number p of these pairs is chosen so that the maximum frequency F1 max of the pipeline multiplier-adder is greater than or equal to the maximum frequency F2max of the adder, the values of these two frequencies being as close as possible.
  • the maximum operating frequency of the multiplier-adder is given by the reciprocal of the execution time of the multiplication-addition operation, whereas the maximum operating frequency of the pipeline multiplier-adder is given by the inverse of the time of addition. execution of only one of the p floors.
  • the maximum frequency of the adder is determined, which gives the execution time of the adder and the multiplier-adder is divided into p stages of crossing time less than or equal to, but as close as possible , at the execution time of the adder.
  • the inputs of the multiplier-adder 1 correspond to three digits: x, y and z and the output is a pair of digits corresponding to
  • the Temp register corresponds to the storage of c necessary for the following calculation: addition of c with the next LSB and the previous hold.
  • the data (digits of xxY + Z) therefore come out in series at each cycle, a figure of low weight at the head, in the same direction as the propagation of the reservoir.
  • FIG. 2 depicts an exemplary arrangement of the component of FIG. 1, with a device 3 adapted to the lower part of the multiplication, and a device 5 composed of registers and multiplexers.
  • the main components of the circuit are: a multiplier-adder 1 pipeline, a 3-input adder, referenced 2, a low-part multiplier 3 and a 2-bit adder + 1 bit to 2-bit, designated
  • the number of multiplexers and registers depends in particular on the intrinsic circuit data, the pipeline depths p and k, as well as the number of digits of the data.
  • the barrier of n reg -ma ⁇ -1 registers and multiplexers serves in particular to delay the arrival of data in the multiplier-adder 1.
  • nrii the number that makes the quantity S + nriiN divisible by r.
  • mj is determined by performing a partial multiplication of the least significant digit of S with a constant N ', precomputed once and for all for a given module N. In this multiplication, only the lower part interests us: we perform this operation modulo r. This operation being slower than an addition, it is also pipeline.
  • the low-order number of the multiplication-addition result is available when the index number p + 1 is present at the input of the multiplier-adder.
  • nrij is available at the output of the lower part multiplier. It can therefore be used as the input of the multiplier-adder at the next clock stroke. This explains the condition p + k + 2 ⁇ n. Rebouclage If we want to chain the multiplications-additions (1) and (2), without loss of time, we choose p + k + 2 ⁇ n.
  • nrii is available before the end of the digits of the multiplication-addition in progress. This value is looped back so as to delay its entry into the multiplier-adder.
  • n rebk npk-2 which corresponds to the necessary number of loopbacks of this value.
  • the So and nrii set is determined before the end of the digits of the data.
  • the So and nrii set is determined before the end of the digits of the data.
  • n reg np-1. This quantity corresponds to the number of registers to add to synchronize the arrival of the weight figure weak of the result of a multiplication-addition with the low-weight data of the next.
  • nrij Two sub-cases, depending on whether or not p is greater than n, are distinguished. In fact, whatever the value of p, nrij will be determined after S 0 .
  • t 0 is available after the data digits run. We therefore delay the entry of new data. This is done as before by adding wait times (latency).
  • t n The determination of t n is done by adding s n + i with c, s n + i ⁇ 2 and c ⁇ 1. For this, a 2-bit + 1 bit to 2-bit (logic) adder is provided (t n ⁇ 3) (designated component 4).
  • the offset saves the use of a register. This one is used for the storage of s n + - ⁇ . This value is stored until c is determined, then the addition of the two is made thus releasing the storage register of s n + i.
  • n re b n + niatk-1 which is the number of loopbacks necessary to
  • the final design of the component depends in particular on the depths of pipeline p and k as well as the number of digits n of the long integers for which it is initially intended.
  • the number of registers to be added is a delicate point since it is not the same one as one is in the case of the passage from (1) to (2) or in the passage of (2) at (1).
  • the following synthesis table 1 binds the quantities p, k and n to the previously defined correction parameters.
  • nreg-ma ⁇ max (n r egk, nreg) and is equal to n- P -1 if P + k + 2 ⁇ n and if not k + 1.
  • n r e g- ma ⁇ is greater than or equal to 1.
  • Latency comes here. Indeed, according to whether there is latency or not, changes of state are not made at the same time.
  • circuit latency correction parameters (n' ⁇ has been and has n ⁇ tk) to define a general behavior of multiplexers.
  • the data presented successively multiplier-adder input can be grouped by 2n slices + 2 + t + n' ⁇ has n ⁇ has tk data.
  • the n ⁇ tk + n + 1 correspond to the first data m, and Nj.
  • the n' ⁇ at + n + 1 correspond to recent data have and bj.
  • n' ⁇ at n ⁇ ATK Using constant n' ⁇ at n ⁇ ATK and notably allows to verify that the change of state occurs when all the digits of B (or N) were driven.
  • mux1 initially at 0 (reset), remains in this state during the first n clock ticks, and goes into state 1 at n + 1 th stroke.
  • mux1 1 at the end of this same clock stroke, so at the end of the next clock stroke, mi and N 0 will be presented at the input of the multiplier-adder.
  • s n + 2 is stored in Stab-i.
  • the retention of the three-input adder must be initialized to 0 since a new addition begins.
  • the two states are:
  • this addition relates to the values of the register Stabi, so the depth of pipeline p intervenes to determine the behavior of mux2.
  • mux3 is a two-state multiplexer symbolizing when the offset is performed (modeled by a register jump). The two states are:
  • This index shift is made in hardware by the jump of a register.
  • the offset occurs when the data s n + i is present in the register Stabi. Indeed, at this moment, the register S of the adder contains, according to the value of n ⁇ at k, either 0 (result of a latent stroke), or the value of t 0 . t 0 having a delay time compared to the conventional multiplication (S 0 ), it must then skip a register to catch up this delay time. This offset must therefore be carried out until all the figures (latency included) of T, up to t n- i, are determined.
  • mux3 is in state 0 (classic multiplication). It goes to 1 when s n + i is in the Stabi register. Now S n is in S at the clock p + 3 + n (cf: behavior of mux2). So s n + i is in this same register at the stroke p + n + 4, and in Stabi at the following stroke: p + n + 5.
  • cf behavior of mux2
  • This command represents the instants for which s n + i must be looped back into the Stabi register.
  • the two states are:
  • the reb k command indicates when to loop the value of nrij in the output register of the lower part multiplier.
  • the two states are: - 0: no loopback
  • n r ⁇ bk is the number of necessary loopbacks of Pn 1 in the case where Pn 1 is determined before the course of all the digits of B.
  • the total number of loopbacks of mi is therefore: n + 1 + n r ⁇ bk-
  • reb k O Otherwise:

Landscapes

  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Software Systems (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Complex Calculations (AREA)

Abstract

Dispositif de mise en oeuvre de la multiplication modulaire, caractérisé en ce qu'il comporte au moins une cellule de calcul comportant 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 recevant les deux sorties du multiplieur-additionneur, le nombre p étant choisi de façon telle que la fréquence maximale du multiplieur-additionneur soit supérieure ou égale à la fréquence maximale de l'additionneur.

Description

DISPOSITIF IMPLEMENTAWT LA MULTIPLICATION MODULAIRE DE MONTGOMERY
L'invention concerne une méthode et un dispositif pour exécuter une multiplication modulaire de Montgomery.
Elle est notamment utilisée dans le domaine de la cryptologie, dans des circuits intégrés de type FPGA (Field Programmable Gâte Array) ou ASIC (Application Spécifie Integrated Circuit). La multiplication modulaire est traitée sur un anneau modulaire (ZJNZ) ou sur un corps (ZJpZ) avec p nombre premier.
Dans la description, on définit la fréquence de fonctionnement d'un multiplieur-additionneur pipeline à p étages donnée par l'inverse du temps de traversée d'un seuil des étages du multiplieur-additionneur.
Dans la description, on définit le terme « pipeline » comme une opération consistant à rajouter des barrières de registres entre les phases logiques et l'architecture en résultant.
La multiplication modulaire est au cœur de nombreux crypto systèmes à clé publique (RSA, ECDSA).
Les opérations de chiffrement et de signature présentent des contraintes différentes qui requièrent notamment une architecture rapide, flexible et peu coûteuse en ressources matérielles. Deux niveaux de flexibilité sont ainsi définis :
• Le premier niveau se situe avant la synthèse de l'architecture. La conception de l'architecture doit comporter suffisamment de degrés de liberté pour pouvoir satisfaire des contraintes matérielles/temporelles données.
• Le deuxième niveau se situe après la synthèse de l'architecture.
L'architecture doit être capable de traiter différentes tailles de données afin de pouvoir effectuer aussi bien des opérations de type ECDSA (Elliptique Curve Digital Signature Algorithm) taille 256-512 bits que des opérations de type RSA (du nom de ses inventeurs : Rivest, Shamir, Adleman) taille 1024-4096 bits.
Pour évaluer les performances d'une architecture, le produit temps*surface est utilisé. Le temps est donné en nombre de cycle horloge. La surface est estimée en terme de nombre de portes Nand équivalentes (ASIC) ou en terme de cellules élémentaires (LC (Logic CeII) ou CLB (Configuration Logic Bloc), blocs combinatoires séquentiels, pour FPGA ou field-programmable gâte arrays). L'art antérieur décrit différents exemples de dispositif et de méthode utilisant la multiplication modulaire en cryptographie asymétrique.
Les implémentations les plus fréquentes de la multiplication modulaire sont de type systolique et utilisent l'algorithme de Montgomery. De nombreuses publications traitent de ces implémentations. La référence dans ce domaine étant due à Peter Komerup, A systolic, linear-array for a class of right-shift algorithms, IEEE Transactions on Computers 43 (1994), no. 8, 892-898.
L'implémentation de la multiplication modulaire peut aussi se faire selon l'algorithme de Barret , Johann Groβschàdl, High speed RSA Hardware based on Barret's modular réduction method, CHES'00, 2000.
Ce dernier type d'implémentation, bien que performant, présente l'inconvénient de ne pas être flexible, car elle est définie sur une taille donnée et ne peut traiter des opérations de tailles supérieures.
Des représentations de nombre « exotiques » (c'est-à-dire non conventionnelles, comme par exemple la représentation RNS (Residue Number System)) sont également utilisées pour paralléliser l'implémentation de la multiplication modulaire, par exemple, L-S Didier, J-C Bajard and P. Komerup, An RNS Montgomery multiplication Algorithm, Proceedings of ARITH13, IEEE Computer Society, 1997, pp. 234-239. Cette solution requiert toutefois d'importantes ressources matérielles et ne résout pas le problème de flexibilité. II est aussi connu des dispositifs présentant des architectures flexibles, ou « scalable hardware ». La première publication d'une telle architecture est due à Alexandre F. Tenca and Cetin K. Koç, A scalable architecture for Montgomery multiplication, CHES'99, 1999. D'autres publications plus récentes, reprennent l'idée développée dans cet article et proposent des améliorations et des extensions. C'est le cas de :
• Alexandre F. Tenca and Cetin K. Koç, A scalable architecture for Modular Multiplication based on Montgomery's Algorithm, IEEE Transactions on computers 52 (2003), no 9.
• Alexandre F. Tenca, Cetin K. Koç and Erkay Savas, A scalable and unified multiplier architecture for finite field GF(p) and GF(2n), CHES'OO, 2000.
• Alexandre F. Tenca, Georgi Todorov and Cetin K. Koç, High-Radix Design of a scalable modular multiplier, CHES'01 , vol. LNCS 2162,
2001 , pp. 185-201.
• Gunnar Gaubatz, Versatile Montgomery Multiplier Architectures, Ph. D. thesis, Worcester Polytechnic Institute, April 2002.
Ces architectures sont basées sur le câblage de petites cellules élémentaires composées d'un additionneur et d'un multiplieur. Ces dispositifs répondent au problème de flexibilité. Toutefois, ces structures impliquent le choix d'une taille de bus interne faible. Le nombre de cycles pour réaliser une multiplication modulaire est donc élevé.
Avant d'expliciter le dispositif et les étapes de la méthode selon l'invention quelques rappels concernant l'algorithme de Montgomery sont donnés. L'algorithme de Montgomery utilisé est le suivant :
MMnS(A1B1N) S^- a0B
Pour i de 1 à n faire
Figure imgf000006_0001
Retourne S
L'étape S <-aiB+(mjN+S)/r est la plus coûteuse d'un point de vu temps de calcul. On peut remarquer que cette étape est obtenue en faisant deux fois la même opération : chiffrexentier long+entier long → entier long (XjY+Z → Z). Cette étape est réalisée en faisant une boucle sur les chiffres des deux entiers longs (Y et Z).
On distingue cependant deux cas, selon que le décalage est effectué ou non. La multiplication classique : a,B+T → S (1) Cette multiplication-addition est réalisée par la boucle suivante :
c=0
Pour j allant de 0 à n faire :
Figure imgf000006_0002
Sj <- LSB(P) c <- MSB(P)
Sn+1=C
Pour l'itération j=n, bj <1 , donc P < 3(r-1) = 2r+r-3, ce qui implique MSB(P) <
2. On en déduit que sn+i < 2.
Remarque : L'opération de base est xxy+z+c avec x, y, z et c compris entre 0 et r-1. Le résultat est donc compris entre 0 et r2-1 , représentable par deux chiffres.
La multiplication et décalage : (m,N+S/r) → T (2)
Dans le cas particulier de la division par r (décalage à droite), la boucle est la même que ci-dessus, avec un décalage d'indice au niveau de la sortie T. En effet, la détermination de nrii rend la quantité P=miχNo+So divisible par r. Dans ce cas là, on est assuré que LSB(P) est nul. On "perd" donc volontairement cette première valeur (indice -1 ) la première valeur significative (t0) étant obtenue à l'itération suivante 0=1 ). Du fait du décalage d'indice, la dernière itération (j=n) donnera accès à la valeur tn-i. La valeur tn sera donc obtenue en ajoutant C=MSB(P) de l'itération j=n avec sn+i. La boucle est donc la suivante : c=0 Pour j allant de O à n faire :
P <- nriiNj+Sj+c
Figure imgf000007_0001
c <- MSB(P)
Pour l'itération j=n, Nj=O, donc P < 2(r-1 ) = r+r-2, ce qui implique MSB(P) < 1.
On en déduit que tn < 3.
Comme r > 4, on en déduit que T est bien représenté par n+1 chiffres.
La présente invention repose sur une nouvelle approche qui considère notamment, en fonctionnement normal, une cellule unique de taille plus importante que les cellules considérées dans l'art antérieur et un processus d'itération sur elle-même en utilisant un algorithme de Montgomery en base élevée. C'est-à-dire que dans la suite, la base r est supposée plus grande ou égale à 4. En pratique la base r correspond le plus souvent à 232 ou à 264, ce qui justifie la dénomination de base élevée.
L'invention concerne un dispositif de mise en œuvre de la multiplication modulaire caractérisé en ce qu'il comporte au moins une cellule de calcul comportant un multiplieur-additionneur comportant p couples logique-registre pipeline, 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 du multiplieur-additionneur soit supérieure ou égale à la fréquence maximale de l'additionneur.
Le dispositif peut comporter un multiplieur partie basse dont les entrées correspondent à la sortie LSB de l'additionneur et à une constante précalculée, ledit multiplieur étant pipeline sur une profondeur k.
L'invention présente notamment les avantages suivants : l'utilisation d'une base plus élevée réduit le nombre de cycles nécessaires au calcul d'une multiplication modulaire. Une seule cellule élémentaire est alors utilisée. Le produit temps surface de cette architecture est donc amélioré.
D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description qui suit d'un exemple de réalisation donné à titre illustratif et nullement limitatif annexé des figures qui représentent :
• La figure 1 un exemple d'agencement des composants élémentaires d'une cellule multiplieur-additionneur selon l'invention, • La figure 2 un exemple d'agencement des composants constituant le cœur du multiplieur modulaire de Montgomery.
L'idée mise en œuvre dans le multiplieur selon l'invention consiste notamment à scinder l'opération xxy+z+c en (xχy+z)+c, en pipelinant l'opération de multiplication-addition (xxy+z) et en ajoutant, à mesure que les résultats sont obtenus, la variable c, où x,y et z sont les données, c étant le chiffre de poids fort provenant de l'itération précédente. Pipeline
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 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. Implémentation de la mu ltiplication-addition
L'exemple donné à la figure 1 suppose que l'on dispose d'un multiplieur-additionneur 1 pipeline, de profondeur p.
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 pipeline 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.
La fréquence maximale de fonctionnement du mulplieur- 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 pipeline est donné par l'inverse du temps d'exécution d'un seul des p étages. Pour un fonctionnement optimal, on 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 1 correspondent à trois chiffres : x,y et z et la sortie est un couple de chiffres correspondant à
LSB(xχy+z) et MSB(xχy+z). La sortie tient sur deux chiffres. Les résultats du multiplieur-additionneur sont transmis à un additionneur trois entrées, référencé 2 : chiffre+chiffre+carry → chiffre+carry, fonctionnant en 1 cycle (pipeline 0) à la fréquence F2max.
Dans la suite on désignera par b la taille du bus interne (l'hypothèse qui est faite est : b > 2 pour satisfaire r > 4), (r=2b). 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 xxY +Z) sortent donc en série à chaque cycle, chiffre de poids faible en tête, dans le même sens que la propagation de la retenue.
La figure 2 décrit un exemple d'agencement du composant de la figure 1 , avec un dispositif 3 adapté à la partie basse de la multiplication, et un dispositif 5 composé de registres et de multiplexeurs.
Dans cet exemple, les principaux composants du circuit sont : un multiplieur-additionneur 1 pipeline, un additionneur 3 entrées, référencé 2, un multiplieur partie basse 3 et un additionneur 2 bits + 1 bit vers 2 bits, désigné
4. Une barrière de nreg-maχ-1 registres et de multiplexeurs, désigné 5.
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 2, la barrière de nreg-maχ-1 registres et de multiplexeurs (composant référencé 5) a notamment pour fonction de 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 nrii, le chiffre qui rend la quantité S+nriiN divisible par r. mj est déterminé en effectuant une multiplication partielle du chiffre de poids 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 pipeline.
On appelle k la profondeur de pipeline de cet opérateur et on suppose k<p.
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 (nrijχN+S)/r → T , (2), et le passage de (2) à (1 ), le retard n'étant pas le même. Ce retard détermine notamment le nombre de registres à utiliser : nVeg 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'reg est défini), le nombre de registres à utiliser est nVeg- Comme il y en a nreg-maχ -1 , il faut en sauter nreg-maχ -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 < 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. S0 est disponible, le calcul de mi peut donc débuter.
Après k+1 coups d'horloge supplémentaires, nrij 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 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 nrii 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 alors nrebk=n-p-k-2 qui correspond au nombre de rebouclage nécessaire de cette valeur.
Dans le cas particulier où nrΘbk=0, la donnée nrij est synchrone avec les nouvelles entrées du multiplieur-additionneur.
Cependant, dans tous les cas, on reboucle la valeur nrii, n fois afin 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 rrii, 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ées.
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 nιatk=P+k+2-n. Cette grandeur représente le nombre de coups de latence à effectuer avant de présenter de nouvelles entrées au multiplieur-additionneur.
Dès que m, est déterminé, il est utilisé comme entrée de la multiplication-addition. S0 quant à lui est forcément déterminé avant m, et doit être stocké (ainsi que Si, S2 ...) jusqu'à ce que nrij soit calculé.
Pour cette raison, on rajoute des registres afin de retarder l'arrivée des résultats à l'entrée du multiplieur-additionneur. Registres supplémentai res
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. Cas 1 : p+k+2 ≤ n
Dans ce cas, l'ensemble So et nrii est déterminé avant la fin de parcours des chiffres des données. Pour mi, voir la section sur le rebouclage, on utilise la méthode décrite ci-dessus dans la section de rebouclage.
Pour So, on retarde son arrivée à l'entrée du multiplieur additionneur par le rajout de registres à décalage.
On définit alors nreg par nreg=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 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, nrij sera déterminé après S0.
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, nregk=k+1 le nombre de registres à rajouter pour retarder l'arrivée de S0 à 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 avec l'entrée de nouvelles données. Ici, seule la quantité p est importante, nrii 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 ti qui est nul). Ceci peut être vu comme un niveau de pipeline supplémentaire. 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+2 ≤ n
Dans ce cas, to est disponible avant la fin de parcours des chiffres 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, t0 est disponible après le parcours des chiffres des 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+i avec c, sn+i < 2 et c < 1. Pour cela on prévoit un additionneur (de la logique) 2 bits + 1 bit vers 2 bits (tn < 3) (composant désigné 4).
Dans le calcul de T, le décalage permet d'économiser l'utilisation d'un registre. Celui-ci est utilisé pour le stockage de sn+-ι. Cette valeur est stockée jusqu'à ce que c soit déterminé, puis l'addition des deux est réalisée libérant ainsi le registre de stockage de sn+i.
On définit donc nreb=n+niatk-1 qui est le nombre de rebouclage nécessaire de
Sn+1 -
Paramètres de correction
Le dessin final du composant dépend notamment des profondeurs de pipeline p et k ainsi que du nombre de chiffres n des entiers longs pour lequel il est initialement prévu. En particulier, le nombre de registres à rajouter est un point délicat puisqu'il n'est pas le même suivant que l'on se trouve dans le cas du passage de (1 ) à (2) ou dans le passage de (2) à (1 ).
Le tableau 1 de synthèse qui suit lie les quantités p, k et n aux paramètres de correction précédemment définis.
Tableau 1
Figure imgf000015_0003
En pratique le nombre de registres à rajouter est défini par : nreg-maχ=max(nregk,nreg) et est é9al a n-P-1 si P+k+2 < n et sinon k+1. En particulier, nreg-maχ est supérieur ou égal à 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 2
Un exemple de séquencement des opérations est décrit en relation avec la figure 2. 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
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.
Il est cependant possible d'utiliser les paramètres de correction de latence du circuit (n'ιat et nιatk) pour définir un comportement général des multiplexeurs.
En effet, on peut supposer que |B|=n+1+
Figure imgf000015_0001
avec les
Figure imgf000015_0002
premiers chiffres de B nuls. (Sauf évidemment pour le calcul de aoB).
De même, on peut supposer que |N|=n+1+ nιatk avec les nιatk premiers chiffres de N nuls. De plus, on isole le cas particulier du premier calcul a0B pour lequel on ne prend pas en compte la latence (les n'ιat premiers chiffres nuls 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'ιat + nιatk données. Les nιatk +n+1 premières correspondent aux données m, et Nj. Les n'ιat +n+1 dernières correspondent aux données ai et bj.
On aura donc un comportement cyclique des multiplexeurs, de période 2n+2+n'ιat+nιatk mux 1 mux1 est un multiplexeur à deux états symbolisant quel type d'entrées doit être pris en compte au niveau du multiplieur-additionneur. Les deux états sont : - 0 :
Figure imgf000016_0001
et y=bj sont pris comme entrées du multiplieur- additionneur.
- 1 : X=PHj et y=Nj sont pris comme entrées du multiplieur- additionneur.
L'utilisation des constantes n'ιat et nιatk 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 rïιat premiers chiffres nuls. Le calcul commence directement par les données aobn'iat .
Ainsi mux1 , initialement à 0 (reset), reste dans cet état pendant les n premiers coups d'horloge, et passe dans l'état 1 au n+1eme coup.
A la fin de ce n+1eme coup, les données présentées en entrée du multiplieur-additionneur sont a0 et bn, tous les chiffres de B auront donc été parcourus. mux1 est à 1 à la fin de ce même coup d'horloge, donc à la fin du coup d'horloge suivant, m-i et N0 seront présentés en entrée du multiplieur- additionneur. Le comportement général de mux1 en fonction du coup d'horloge dock peut être résumé par les étapes suivantes : Si clock<n+1 , alors mux1=0 Sinon : Si (clock-(n+1 ) mod (2n+2+ niatk + n'ιat ))<n+1+ niatk, alors mux1=1
Sinon mux1=0 mux2 mux2 est un multiplexeur à deux états symbolisant à quel moment doit être fait l'addition sn+2 +c. On rappelle que sn+2 est stocké dans Stab-i. De plus, lorsque cette addition est réalisée, la retenue de l'additionneur trois entrées doit être initialisée à 0 puisque une nouvelle addition commence. Les deux états sont :
- 0 : L'addition sn+i+c ne peut être effectuée, c n'est pas encore déterminé.
- 1 : Les entrées sn+i et c sont positionnées pour être ajoutées au coup d'horloge suivant, la retenue de l'additionneur trois entrées est initialisée à 0.
Cette addition est réalisée une seule fois par itération principale (boucle sur i), elle se situe dans la deuxième boucle sur les chiffres de N.
Ceci signifie que mux2 n'est jamais deux fois de suite dans l'état 1.
De plus, cette addition porte sur les valeurs du registre Stabi , donc la profondeur de pipeline p intervient pour déterminer le comportement de mux2. Le chiffre de poids faible (s0) du produit aoχbo est dans le registre de sortie de l'additionneur à dock p+3 (=1 (load)+(p+1 )(so dans LSB)+1 (so dans registre de sortie de l'additionneur)).
Sn est donc dans ce même registre à dock p+3+n. Comme Sn correspond au chiffre de poids faible de a0 x bn, les entrées suivantes sont donc les chiffres de N et mi. Or l'addition doit être réalisée lorsque tn-i se trouve dans le registre de sortie de l'additionneur puisqu'à ce moment on dispose de la bonne valeur de carry à ajouter à sn+i pour déterminer tn. mux2 doit donc être dans l'état 1 lorsque tn-i se trouve dans le registre de sortie de l'additionneur, c'est à dire au coup d'horloge p+3+n+niatk+n+1=p+2n+niatk+4. Il ne faut pas oublier qu'avec le décalage, tn-i correspond au calcul de miχNn.
Par périodicité, on peut décrire le comportement général de mux2. Si dock = p+2n+4+niatk mod 2n+2+ nιatk + n'ιat > alors mux2=1 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 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+i est présente dans le registre Stabi . 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 t0. t0 ayant un temps de retard par rapport à la multiplication classique (S0), 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 comprise) de T, jusqu'à tn-i , soient déterminés. En effet, lorsque tn-i est déterminé (ie : dans le registre S de l'additionneur), au coup d'horloge suivant, tn est déterminé dans Stabi par addition de c avec sn+i, et tn-i se trouve dans le registre Stab2. Le décalage prend alors fin, les données tn-i et tn étant de nouveau dans deux registres successifs, mux3 reste donc dans l'état 1 durant n+ niatk =nreb +1 coup. Comme nous l'avons dit précédemment, le décalage correspond au saut du registre Stabi qui est alors utilisé pour le rebouclage de sn+i. Le rebouclage de sn+i 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 sn+i dans le registre Stabi . Ce rebouclage a lieu nrβb fois.
Initialement, mux3 est dans l'état 0 (multiplication classique). Il passe à 1 lorsque sn+i est dans le registre Stabi . Or Sn est dans S au coup d'horloge p+3+n (cf : comportement de mux2). Donc sn+i est dans ce même registre au coup p+n+4, et dans Stabi au coup suivant : p+n+5. Par périodicité, on déduit le comportement général de mux3 : Si clock<p+n+5, alors mux3=0 Sinon :
Si (clock-(p+n+5) mod (2n+2+ niatk + n'ιat ))<nreb +1 > alors mux3=1 Sinon mux3=0
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 sn+i doit être rebouclé dans le registre Stabi . 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<p+n+5, alors reb=O Sinon :
Si (clock-(p+n+5) mod (2n+2+ nιatk + n'ιatk ))<nreb, alors reb=1 Sinon reb=O mux4 mux4 est un multiplexeur à deux états qui fait parti de la barrière de registres. Dans les cas où ce multiplexeur est présent, il indique s'il faut utiliser n'reg ou nregk registres. Les deux états sont :
- 0 : Utilisation de la totalité des registres (correspond à la multiplication (2)). - 1 : Utilisation de rïreg registres (correspond à la multiplication (1 )). mux4 doit être dans l'état 1 lorsque to est déterminé dans S. On a vu (cf : mux3) que sn+i est présent dans S à clock=p+n+4, donc nιatk +1 coups d'horloge après, c'est à dire à clock=p+n+5+ niatk , to est dans S. mux4 doit rester à 1 jusqu'à ce que tn se trouve dans Stabi soit durant n+1 coups d'horloge.
Par périodicité, on déduit un comportement général de mux4 : Si clock<p+n+5+ nιatk, alors mux4=0 Sinon :
Si (clock-(p+n+5+ nιatk ) mod (2n+2+ nιatk +n'ιat))<n+1 , alors mux4=1 Sinon mux4=0
Commande rebk
La commande rebk indique à quel moment il faut reboucler la valeur de nrij dans le registre de sortie du multiplieur partie basse. Les deux états sont : - 0 : pas de rebouclage
- 1 : rebouclage Initialement, rebk =0. mi est déterminé (ie : présent dans le registre de sortie du multiplieur partie basse) à la fin du coup d'horloge clock=p+k+4. En effet, mi est déterminé à l'aide de S0 qui est lui même présent dans le registre S à la fin du coup d'horloge clock=p+3 (cf : mux2). Il sert donc d'entrée au multiplieur partie basse qui donne le résultat k+1 coups d'horloge après, soit à clock=p+k+4. Il faut donc reboucler cette valeur à partir de ce moment là, au moins n+1 fois afin que cette entrée soit la même pour tous les chiffres de N. Il faut également tenir compte de la valeur de nrΘbk qui est le nombre de rebouclages nécessaires de Pn1 dans le cas où Pn1 est déterminé avant le parcours de tous les chiffres de B. Le nombre de rebouclage total de mi est donc : n+1+nrΘbk- Par périodicité, on en déduit le comportement général de rebk : Si clock<p+n+4, alors rebk=O Sinon :
Si (clock-(p+n+4) mod (2n+2+ nιatk + n'ιat
Figure imgf000021_0001
alors rebk =1 Sinon rebk=O.

Claims

REVENDICATIONS
1 - Dispositif de mise en œuvre de la multiplication modulaire, caractérisé en ce qu'il comporte au moins une cellule de calcul comportant un multiplieur- additionneur (1 ) comportant p couples logique-registre pipeline, recevant plusieurs chiffres à additionner et à multiplier, au moins deux sorties correspondant au poids faible et au poids fort, un additionneur (2) recevant les deux sorties du multiplieur-additionneur, le nombre p étant choisi de façon telle que la fréquence maximale F1max du multiplieur-additionneur soit supérieure ou égale à la fréquence maximale F2max de l'additionneur.
2 - Dispositif selon la revendication 1 , caractérisé en ce que la fréquence maximale F1 max du multiplieur-additionneur est sensiblement égale à la fréquence maximale F2max de l'additionneur.
3 - Dispositif selon la revendication 1 , caractérisé en ce qu'il comporte un multiplieur (3) partie basse dont les entrées correspondent à la sortie LSB de l'additionneur et à une constante précalculée, ledit multiplieur étant pipeline sur une profondeur k.
4 - Dispositif selon l'une des revendications 1 ou 2, caractérisé en ce qu'il comporte un ensemble de registres et de multiplexeurs, adapté à retarder l'arrivée des données dans le multiplieur-additionneur.
5 - Dispositif selon l'une des revendications 1 à 2, caractérisé en ce qu'il comporte un additionneur complémentaire 2 bits + 1 bit vers 2 bits.
PCT/EP2006/061235 2005-04-01 2006-03-31 Dispositif implementant la multiplication modulaire de montgomery Ceased WO2006103288A1 (fr)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP2008503528A JP2008535011A (ja) 2005-04-01 2006-03-31 モンゴメリーのモジュラー乗算を実行する方法及びそのための装置
US11/910,443 US8073891B2 (en) 2005-04-01 2006-03-31 Method for implementing montgomery modular multiplication and device therefore
DE602006021558T DE602006021558D1 (en) 2005-04-01 2006-03-31 Modulare montgomery-multiplikationseinrichtung
EP06725481A EP1869545B1 (fr) 2005-04-01 2006-03-31 Dispositif implementant la multiplication modulaire de montgomery

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0503178A FR2884005B1 (fr) 2005-04-01 2005-04-01 Methode d'implementation de la multiplication modulaire de montgomery et son dispositif
FR0503178 2005-04-01

Publications (1)

Publication Number Publication Date
WO2006103288A1 true WO2006103288A1 (fr) 2006-10-05

Family

ID=35169460

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2006/061235 Ceased WO2006103288A1 (fr) 2005-04-01 2006-03-31 Dispositif implementant la multiplication modulaire de montgomery

Country Status (6)

Country Link
US (1) US8073891B2 (fr)
EP (1) EP1869545B1 (fr)
JP (1) JP2008535011A (fr)
DE (1) DE602006021558D1 (fr)
FR (1) FR2884005B1 (fr)
WO (1) WO2006103288A1 (fr)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2000904A1 (fr) 2007-06-07 2008-12-10 Thales Procédé de multiplication modulaire de Montgomery masquée et dispositif associé
FR2917198A1 (fr) * 2007-06-07 2008-12-12 Thales Sa Operateur de reduction modulaire ameliore.
CN104598199A (zh) * 2015-01-07 2015-05-06 大唐微电子技术有限公司 一种用于智能卡的Montgomery模乘器的数据处理方法及系统

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8073892B2 (en) * 2005-12-30 2011-12-06 Intel Corporation Cryptographic system, method and multiplier
EP2015171A1 (fr) * 2007-06-29 2009-01-14 Gemplus Procédé cryptographique comprenant une exponentiation modulaire sécurisée contre les attaques à canaux cachés sans la connaissance de l'exposant public, cryptoprocesseur pour la mise en oeuvre du procédé et carte à puce associée
US10545727B2 (en) * 2018-01-08 2020-01-28 International Business Machines Corporation Arithmetic logic unit for single-cycle fusion operations
US12500736B2 (en) * 2023-08-14 2025-12-16 Microsoft Technology Licensing, Llc Montgomery multiplier architecture

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5133069A (en) * 1989-01-13 1992-07-21 Vlsi Technology, Inc. Technique for placement of pipelining stages in multi-stage datapath elements with an automated circuit design system
US20020194237A1 (en) * 2001-06-13 2002-12-19 Takahashi Richard J. Circuit and method for performing multiple modulo mathematic operations
US20050033790A1 (en) * 2001-12-14 2005-02-10 Hubert Gerardus Tarcisius Maria Pipeline core in montgomery multiplier

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3616897B2 (ja) * 1998-01-27 2005-02-02 富士通株式会社 モンゴメリ法による乗算剰余計算装置
US7240204B1 (en) * 2000-03-31 2007-07-03 State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Oregon State University Scalable and unified multiplication methods and apparatus
US6804696B2 (en) * 2000-12-19 2004-10-12 International Business Machines Corporation Pipelining operations in a system for performing modular multiplication
JP2004280036A (ja) * 2002-05-20 2004-10-07 Toshiba Corp 剰余演算装置、剰余演算方法、及びべき乗剰余演算装置
JP4223819B2 (ja) * 2003-01-21 2009-02-12 株式会社日立製作所 べき乗剰余演算装置及びそのプログラム
JP4177125B2 (ja) * 2003-01-22 2008-11-05 三菱電機株式会社 演算装置及び演算装置の演算方法
US8194855B2 (en) * 2003-06-30 2012-06-05 Oracle America, Inc. Method and apparatus for implementing processor instructions for accelerating public-key cryptography
US7805479B2 (en) * 2006-03-28 2010-09-28 Michael Andrew Moshier Scalable, faster method and apparatus for montgomery multiplication
FR2917197B1 (fr) * 2007-06-07 2009-11-06 Thales Sa Procede de masquage du resultat d'une operation de multiplication modulaire et dispositif associe.
FR2917198B1 (fr) * 2007-06-07 2010-01-29 Thales Sa Operateur de reduction modulaire ameliore.
US8433736B2 (en) * 2009-02-27 2013-04-30 George Mason Intellectual Properties, Inc. Scalable Montgomery multiplication architecture

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5133069A (en) * 1989-01-13 1992-07-21 Vlsi Technology, Inc. Technique for placement of pipelining stages in multi-stage datapath elements with an automated circuit design system
US20020194237A1 (en) * 2001-06-13 2002-12-19 Takahashi Richard J. Circuit and method for performing multiple modulo mathematic operations
US20050033790A1 (en) * 2001-12-14 2005-02-10 Hubert Gerardus Tarcisius Maria Pipeline core in montgomery multiplier

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2000904A1 (fr) 2007-06-07 2008-12-10 Thales Procédé de multiplication modulaire de Montgomery masquée et dispositif associé
FR2917198A1 (fr) * 2007-06-07 2008-12-12 Thales Sa Operateur de reduction modulaire ameliore.
EP2003547A1 (fr) * 2007-06-07 2008-12-17 Thales Operateur de reduction modulaire amélioré
JP2008304920A (ja) * 2007-06-07 2008-12-18 Thales マスキングされたモンゴメリーのモジュラー乗算方法及び関連装置
CN104598199A (zh) * 2015-01-07 2015-05-06 大唐微电子技术有限公司 一种用于智能卡的Montgomery模乘器的数据处理方法及系统

Also Published As

Publication number Publication date
FR2884005B1 (fr) 2007-06-01
US8073891B2 (en) 2011-12-06
US20090037508A1 (en) 2009-02-05
DE602006021558D1 (en) 2011-06-09
EP1869545B1 (fr) 2011-04-27
FR2884005A1 (fr) 2006-10-06
EP1869545A1 (fr) 2007-12-26
JP2008535011A (ja) 2008-08-28

Similar Documents

Publication Publication Date Title
EP0853275B1 (fr) Coprocesseur comprenant deux circuits de multiplication opérant en parallèle
EP2515228B1 (fr) Procédé de multiplication de Montgomery
EP2515227B1 (fr) Circuit de multiplication de Montgomery
FR2867579A1 (fr) Multiplieur modulaire de montgomery
FR2788867A1 (fr) Procede arithmetique, appareil arithmetique et appareil de traitement cryptographique
EP2003547A1 (fr) Operateur de reduction modulaire amélioré
EP2000904B1 (fr) Procédé de multiplication modulaire de Montgomery masquée
WO2015121324A1 (fr) Procédé de contremesure pour un composant électronique mettant en oeuvre un algorithme de cryptographie sur une courbe elliptique
FR2859290A1 (fr) Generateur de nombres pseudoaleatoires
EP1869545B1 (fr) Dispositif implementant la multiplication modulaire de montgomery
FR2822260A1 (fr) Procedes et dispositifs pour accelerer le temps de calcul d&#39;un produit de montgomery d&#39;un multiplication et d&#39;une exponentiation modulaire
CN102122241A (zh) 一种适用于素域和多项式域的模乘模除器
Issad et al. Software/hardware co-design of modular exponentiation for efficient RSA cryptosystem
EP0939362A1 (fr) Coprocesseur d&#39;arithmétique modulaire permettant de réaliser des opérations non modulaires rapidement
FR3083885A1 (fr) Circuit de generation de facteurs de rotation pour processeur ntt
FR3101980A1 (fr) Processeur
EP0939363A1 (fr) Procédé de mise en oeuvre d&#39;une multiplication modulaire selon la méthode de Montgoméry
FR2818765A1 (fr) Multiplicateur modulaire et processeur de cryptage/decryptage utilisant le multiplicateur modulaire
FR2990781A1 (fr) Multiplieur serie numerique
EP0784262B1 (fr) Dispositif et procédé améliorant la vitesse de traitement d&#39;un coprocesseur d&#39;arithmétique modulaire
EP0778518B1 (fr) Procédé de production d&#39;un paramètre J0 associé à la mise en oeuvre d&#39;opérations modulaires selon la méthode de Montgomery
KR100946256B1 (ko) 다정도 캐리 세이브 가산기를 이용한 듀얼필드상의확장성있는 몽고매리 곱셈기
EP0927928A1 (fr) Procédé de production amélioré d&#39;un paramètre JO associé à la mise en oeuvre d&#39;opérations modulaires selon la méthode de Montgomery
FR3129262A1 (fr) Réduction et conversion d&#39;un scalaire en une représentation tau-adique
FR2974916A1 (fr) Dispositif et procede de multiplication rapide

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application
DPE1 Request for preliminary examination filed after expiration of 19th month from priority date (pct application filed from 20040101)
WWE Wipo information: entry into national phase

Ref document number: 2008503528

Country of ref document: JP

NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Country of ref document: DE

WWE Wipo information: entry into national phase

Ref document number: 2006725481

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: RU

WWW Wipo information: withdrawn in national office

Country of ref document: RU

WWP Wipo information: published in national office

Ref document number: 2006725481

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11910443

Country of ref document: US