WO2004015559A2 - Procede pour accelerer des calculs en arithmetique modulaire - Google Patents

Procede pour accelerer des calculs en arithmetique modulaire Download PDF

Info

Publication number
WO2004015559A2
WO2004015559A2 PCT/FR2003/050022 FR0350022W WO2004015559A2 WO 2004015559 A2 WO2004015559 A2 WO 2004015559A2 FR 0350022 W FR0350022 W FR 0350022W WO 2004015559 A2 WO2004015559 A2 WO 2004015559A2
Authority
WO
WIPO (PCT)
Prior art keywords
words
result
memory
significant
operator
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/FR2003/050022
Other languages
English (en)
Other versions
WO2004015559A3 (fr
Inventor
Jean-Luc Stehle
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.)
Everbee Networks SA
Original Assignee
Everbee Networks 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 Everbee Networks SA filed Critical Everbee Networks SA
Priority to EP03755658A priority Critical patent/EP1532519A2/fr
Priority to CA002494769A priority patent/CA2494769A1/fr
Priority to AU2003273500A priority patent/AU2003273500A1/en
Publication of WO2004015559A2 publication Critical patent/WO2004015559A2/fr
Publication of WO2004015559A3 publication Critical patent/WO2004015559A3/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
    • 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

Definitions

  • the invention presented here is a method for accelerating calculations in modular arithmetic, which makes it possible inter alia to accelerate certain operations used in cryptographic protocols.
  • Modulo N arithmetic is a technique which consists in considering that two whole numbers represent the same mathematical entity as soon as their difference is an integer multiple of a number N, called the module. We will then say that these two numbers are congruent modulo N.
  • this module N is generally very large (several hundred decimal digits). Numbers of 512 or 1024 bits or more are commonly used.
  • the mathematical entities on which we are working are called the integers modulo N (integers defined by the addition near an integer multiple of the module N).
  • the set of integers modulo N can be assimilated to the set of integers between 0 and N-l.
  • the addition and the multiplication are defined there in a similar way to their definition in classical arithmetic, except that when a result exceeds Nl, it is replaced by the rest of its division by N (we will write thereafter “remain modulo NOT ”) .
  • the set of integers modulo N from which we have removed the elements not prime to N, forms a group for the multiplication operation, which we will call the multiplicative group of integers modulo N.
  • Modulo N additions and multiplications can be made in a reasonable time.
  • the addition calculation time is approximately proportional to the number of digits necessary to represent N.
  • the multiplication calculation time is approximately proportional to the square of this number of numbers.
  • modulo N in practice these will be integers between 0 and Nl
  • the multiplication of a by b gives, in general, a number much larger than N. It will then be necessary to calculate the modulo N rest in order to obtain a number between 0 and Nl. This operation will be called "modulo N reduction”. It implies to make a division by N. Now a division is, in general, much longer to calculate than a multiplication, and this calculation time increases with the order of magnitude of N. The final result of these operations will be noted ab [mod N] and will read "multiplied by b modulo N".
  • the calculation of a multiplication in modulo N arithmetic is reduced, as we said, to a multiplication of two large whole numbers, (time proportional to the square of the number of digits of N), followed by a modulo N reduction consisting of calculate the remainder of a division into whole numbers by N.
  • the calculation time for this reduction is equivalent to that of several multiplication in large numbers.
  • the invention more particularly relates to a method for accelerating the calculation of multiplications in arithmetic modulo N, N designating an integer comprising in particular several hundred decimal digits.
  • the invention also relates to a method making it possible to accelerate the calculation of exponentiations in modulo N arithmetic. Multiplication and modular exponentiations occur in particular in cryptography protocols implemented using computer resources.
  • the method is more particularly designed to save computer resources, such as computing power and / or memory space.
  • the method is more particularly designed to make it possible to accelerate the calculation of multiplications in modulo N arithmetic.
  • the method comprises the following preliminary steps:
  • the number R is the first power of 2 that cannot be stored over q words.
  • the method further comprises the preliminary step of storing the number d in a memory of the computer resource.
  • the number d must be much smaller than N, in order to speed up the calculations and save computer resources.
  • the appropriate values of N are such as the number d holds on few words, and ideally on a single word.
  • the method comprises a first operator taking as input two numbers El, E2 each stored on q words and supplying as an output a number W such that the product by R of the number W is congruent modulo N to the product of the inputs El, and E2.
  • Said inputs El, E2 are hereinafter called the inputs of the first operator, and the number W is hereinafter referred to as the result of the first operator.
  • the method comprises a first algorithm having for object to replace an argument, stored on 2q words, by a result which is congruent modulo N to the argument and whose q words of least significant are zero.
  • This argument is hereinafter referred to as the argument of the first algorithm.
  • the result is hereinafter referred to as the result of the first algorithm.
  • the method further comprises the following main steps for multiplying between them modulo N two numbers A and
  • the step of storing in memory the modulo N remains of the product by R of the numbers A and B, the remains stored in memory are respectively called the number F and the number G,
  • this number H is equal to the modulo N rest of the product of the numbers A, B and R.
  • the method further comprises the following main steps: the step of implementing the first algorithm with as argument the number H, stored over 2q words, to provide a number V congruent modulo N to the number H and whose q least significant words are zero,
  • the number C or the number C-N is equal to the modulo N remainder of the product of the numbers A and B.
  • the first algorithm consists in iterating q times an operation having the effect of replacing the number obtained at the end of the preceding iteration by a number which is congruent to it modulo N and such that the number obtained at the end of the ith iteration has all its least significant words zero until the ith.
  • the ith operation comprises the following four stages:
  • step (d) at the end of step (b), a result, called y, is obtained which is shifted by i notches in the direction of the most significant and then subtracted from the number resulting from the result of the addition carried out at l 'step (c) above.
  • the first operator comprises the following steps:
  • the first operator comprises the following preliminary steps:
  • the first operator comprises a main step consisting in iterating the following substeps: - (a) the sub-step of multiplying the word thus selected by the entry E2 of the first operator, the entry E2 having taken as value the number G, the result of this multiplication is a number stored on q + 1 words and is called
  • the least significant word of the memory Z contains the value zero.
  • the main step also consists of iterating the following other sub-steps:
  • the first operator also includes another main step.
  • This other main step is to read the word following the entry El, in the direction of increasing weights and to repeat the preceding sub-steps (a) to (j), as many times as necessary.
  • the memory Z contains a number, between zero and 2N, of which the product by R is equal, modulo N, to the product of the inputs El and E2.
  • the first operator further comprises the following two final steps:
  • the result W of the first operator is equal to the content of the memory Z.
  • the first operator comprises the preliminary step next :
  • the first operator comprises a main step consisting in iterating the following substeps:
  • the main step also consists of iterating the following sub-steps:
  • the first operator further comprises the main step of reading the following word from the entry El, in the direction of increasing weights and repeating the preceding substeps (a) to (j) as many times as necessary.
  • the memory Z contains a number H whose product by R is equal , modulo N, to the product of the numbers El and E2.
  • the first operator further comprises the following two final steps:
  • the result W of the first operator is equal to the content of memory Z.
  • the number F is then the number with q words formed from the q most significant words of the number V A , respectively of the number V B.
  • the invention also relates to a second alternative embodiment making it possible to accelerate the calculation of exponentiations in modulo N arithmetic.
  • the object of the method is to raise a number A, hereinafter called the base , at a power p modulo N.
  • p being an integer greater than or equal to 2, hereinafter referred to as the exponent, and being represented in binary form.
  • the process includes the following preliminary steps:
  • the number R is the first power of 2 that cannot be stored over q words.
  • the method includes the preliminary step of storing the number d in a memory of the computer resource.
  • the method further comprises the following preliminary steps:
  • the method comprises a first algorithm having for object to replace an argument, stored on 2q words, by a result which is congruent modulo N to this argument and whose q words of least significant are zero.
  • This argument is hereinafter referred to as the argument of the first algorithm.
  • the result is hereinafter referred to as the result of the first algorithm.
  • the first algorithm implemented in the case of the present second variant embodiment is the same as that which has been described, in particular in a particular embodiment, during the presentation of the. first variant. We can therefore also refer, as necessary, to the previous description of the first algorithm.
  • the process includes the following main steps:
  • the method further comprises the following main step:
  • the memory Y contains a number which is congruent modulo N to the product of the number R by the result of the exponentiation A power p.
  • the method further comprises the step of implementing the first algorithm with as argument the content of the memory Y to obtain a number S congruent modulo N to this argument and whose q least significant words are zero.
  • the method further comprises the following final steps:
  • the method comprises a first operator.
  • the process includes the following preliminary steps:
  • the first operator takes as input two numbers El, E2 each stored on q words and providing as output a number W, stored on q words, such that the product by R of the number W is congruent modulo N to the product of the inputs El, and E2 .
  • Say inputs El, E2 are hereinafter called the inputs of the first operator and the number W is hereinafter referred to as the result of the first operator.
  • the process includes the following main steps:
  • the method further comprises the following main step:
  • the memory Y contains a number which is congruent modulo N to the product of the number R by the result of the exponentiation A power p.
  • the method further comprises the final step of implementing the first algorithm with as argument the content of the memory Y to obtain a number S congruent modulo N to this argument and whose q least significant words are zero.
  • the method further comprises the following final steps:
  • the first algorithm consists in iterating q times an operation having the effect of replacing the number obtained at the end of the previous iteration by a number which is given to it congruent modulo N and such that the number obtained at the end of the ith iteration has all its weight words the weakest draws to the ith.
  • the ith operation comprises the following four stages:
  • step (d) at the end of step (b), a result, called y, is obtained which is shifted by i notches in the direction of the most significant and then subtracted from the number resulting from the result of the addition carried out at l 'step (c) above.
  • the first operator comprises the following steps:
  • the first operator comprises the following preliminary steps:
  • the first operator comprises the main step consisting of iterating the following substeps:
  • the least significant word in memory Z contains the value zero.
  • the main step also includes the following sub-steps:
  • the first operator also comprises the main step of reading the next word from the entry El, in the direction of increasing weights and repeating the preceding sub-steps (a) to (j), as many times as necessary.
  • the memory Z contains a number, between zero and 2N, whose product by R is equal, modulo N, to the product of the numbers El and E2.
  • the first operator also comprises the following two final stages:
  • the step of comparing to the number N the content of the memory Z the step, when this content is greater than N, to subtract the number N from it, the result of the subtraction is stored in the memory Z.
  • the result W of the first operator is equal to the content of memory Z.
  • the first operator comprises the following preliminary steps:
  • the first operator comprises the main step consisting of iterating the following substeps:
  • the least significant word in memory Z contains the value zero.
  • the main step also consists of iterating the following sub-steps:
  • the first operator further comprises the main step of reading the following word from the entry El, in the direction of increasing weights and repeating the preceding substeps (a) to (j) as many times as necessary.
  • the memory Z contains a number H whose product by R is equal , modulo N, to the product of the numbers El and E2.
  • Final main stage the first operator also comprises the following two final stages:
  • the step of comparing to the number N the content of the memory Z the step, when this content greater than N, to subtract from it the number N, the result of the subtraction is stored in the memory Z.
  • the result W of the first operator is equal to the content of memory Z.
  • step (f) storing the number Q (see step (f)) requires one word more than the number of words required to store d. consequently, one saves all the more time of computation and memory that d holds on few words, ideally only one word.
  • the method is such that to calculate the modulo N rest of the product by R of the base A, called the number F:
  • the first algorithm is applied with the number T as an argument, to obtain as a result a number V, which is congruent to it modulo N and whose q least significant words are zero.
  • the number F is then the number with q words formed from the q most significant words of the number V.
  • An elementary multiplication takes two scalars, therefore two words of w bits, multiplies them between them and stores the result, which then occupies 2w bits, on two words of w bits, by separating the w most significant bits and the w bits least significant.
  • T [0], T [l] ,. .., T [r-1] a series of r words of w bits, denoted T [0], T [l] ,. .., T [r-1], agreeing that T is equal to the sum products T [i].
  • B i where the point designates the multiplication and the expression B A i represents B power i, the number i varying between 0 and rl > and B being equal to 2 A w.
  • This representation will be called the standard binary representation of the number T.
  • T [r-1], ..., T [l], T [0] to designate the number T in this representation computer science.
  • T is a number with r words, a scalar being by definition a number with only one word.
  • the words T [j] with a high index will be called “most significant words” or “most significant words” and those with a low index j will be called “low weight words” or “least significant words” .
  • a simple and natural method to carry out the multiplication between a number T of r words and a number U of s words consists in using a memory area V of r + s words, memory which will function as an accumulator and which, at the end of the calculation , will contain the final result.
  • This zone V will be initialized to zero beforehand. Then, for any couple formed by a word of T and a word of U, therefore in total rs times, we multiply these two words between them, elementary multiplication, result on two words, the two result words being added to the appropriate words of the memory area V.
  • a multiplication between two numbers each represented on r words of w bits (or the squared of a word of w bits) in the general case represents r A 2 (r squared) elementary multiplications and 2r. (rl) elementary additions.
  • N is a large odd number, whose binary writing requires for example 512 or 1024 bits, which corresponds to about 150 or 300 decimal digits.
  • R is the first power of 2 which cannot be stored on q words. This number is equal to 2 to the power of the product qw, i.e. to B power q, i.e. 2 power 512 or 2 power 1024 in the examples above. This number is, by construction, greater than N.
  • r d the minimum number of words necessary for computer storage of the value of d, in standard binary representation. This number r d is always less than or equal to q.
  • f the rest modulo N of the square of d. Note that when d is small, and in particular when r d is less than q / 2, the number f is simply equal to the square of the number d.
  • the numbers d, e and f are calculated in advance and stored in the memory of the processor used to perform the calculations.
  • the method thus described composed of a series of iterations, constitutes a first algorithm which makes it possible to pass from a number T to number V multiple of R and congruent to T modulo N.
  • This first algorithm is all the faster when the number r d of words necessary to store d is low.
  • This first algorithm is one of the basic elements of the present invention.
  • the method described here takes all its interest when r d is small because the first algorithm is then fast, as well as the products by f which is then a number with 2 r d words. The only long operation remains the calculation of the FG product.
  • the method can be further improved if we nest the calculation of the product FG and the application of the first algorithm to the result of this multiplication.
  • This operation will be carried out by considering one of the factor numbers, for example G, as a whole, but using word after word the words forming the other factor, for example F, starting with the least significant words.
  • a memory area Y formed of q + 1 words and a carry bit is initialized to 0. This memory area will function on the one hand as a shift register and on the other hand as an accumulator in which the intermediate calculation results will be added.
  • index i we multiply the word of index i of F by the number G to obtain a result P, on q + 1 words, which will be added to the content of memory Y.
  • the addition operation in an accumulator can be carried out in the same elementary instruction as the multiplication. This is the case for example when using an ARM type processor. All of these operations, multiplying a number with q words by a scalar and adding the result to the content of a memory area can then be carried out in q elementary instructions of the processor.
  • the memory Y contains a number less than 2N and whose product by R is congruent modulo N to the product FG. If Y is greater than or equal to N, we subtract N from it. The memory Y now contains the final result of all these operations, namely the remainder by N of a number whose product by R is equal to the product FG.
  • the set of operations described here constitutes an operator which takes as arguments the two numbers F and G and provides as result the remainder by N of a number whose product by R is equal to the product F.G.
  • An indirect method nevertheless makes it possible to calculate A A p [mod N] in an acceptable time.
  • the principle of this method consists in calculating, by successive square elevations, multiplication of a number by itself, modulo N, the list of powers of A, modulo N, whose exponent is a power of 2, c 'is to say (A, A 2 [mod N], A A 4 [mod N], A A 8 [mod N], A 16 [mod N], A 2 [mod N], A A 64 [ mod N], and so on ).
  • We then examine the binary development of the exponent p it is in this form that p is stored in machine.
  • an exponentiation in modulo N arithmetic can be reduced to approximately 3/2 times r modulo N multiplications, where r is the number of bits necessary for the binary representation of the exponent p of the exponential, ie 768 or 1536 multiplication modulo N if we work with exponents at 512 or 1024 bits.
  • r is the number of bits necessary for the binary representation of the exponent p of the exponential, ie 768 or 1536 multiplication modulo N if we work with exponents at 512 or 1024 bits.
  • Each of these modulo N multiplications boils down to a multiplication in large numbers, calculation time proportional to the square of the number of words necessary to represent N in the calculation processor, followed by a modulo N reduction. If this reduction is carried out in a classic, you have to divide into large numbers, which, in computation time, is equivalent to several multiplications in large numbers.
  • the number A the number intended to be raised to the power p modulo N is stored on q words.
  • the exponent p is simply stored in memory by its binary expansion, using f as many bits or words as necessary.
  • the q most significant words in the memory area Y contain the value 0. This memory therefore represents a number stored in q words, therefore a number less than R.
  • V 0 be the result of this calculation.
  • V 0 the algorithm described above under the name of the first algorithm, which has the effect of calculating a number U 0 congruent modulo N to V 0 and whose q least significant words are zero.
  • U 0 congruent modulo N
  • Y the q most significant words of U 0 and the most significant words of Y are set to zero. The content of Y is therefore obtained by exchanging the q most significant words and the q least significant words of U 0 .
  • the q most significant words of the memory area Y therefore contain the value 0, and the sequence is repeated from the beginning after having selected the next bit in p, in the direction of the weights decreasing.
  • the memory Y contains a number which is congruent modulo N to the product of R by A power p.
  • D the number with q words formed by the most significant words of S. This number is positive, is less than 2N and is congruent modulo N to the number A power p. If it is less than N, this is the number we wanted to calculate, the remainder of the division by N of the number A power p. If it is greater than or equal to N, simply subtract N from it to find the desired result.
  • the method of calculating the modular exponentiation described above applies several times a series of operations consisting in first performing a multiplication between two large numbers, squared of Y, or multiplication of Y by F, then to apply to the result of this multiplication the first algorithm described above and consisting in replacing said result by a number which is congruent to it modulo N and whose q least significant words are zero, and finally to extract the number formed from q words of high weights of the result of the first algorithm.

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Power Sources (AREA)
  • Complex Calculations (AREA)

Abstract

L'invention concerne un procédé permettant d'accélérer les calculs d'exponentiation en arithmétique modulo un nombre N stocké sur q mots. Les exponentiations interviennent notamment dans des protocoles de cryptographie mis en œuvre à l'aide de ressources informatiques. Le procédé comporte : un premier algorithme ayant pour objet de remplacer un argument, stocké sur 2q mots, par un résultat qui est congru modulo N audit argument et dont les q mots de poids faibles sont nuls, un premier opérateur prenant deux entrées stockées chacune sur q mots et fournissant en sortie un nombre W, stocké sur q mots, dont le produit par R est congru modulo N au produit des deux entrées. R est une puissance de deux supérieure à N. Le procédé permet d'économiser de la puissance de calcul et de l'espace mémoire.

Description

PROCEDE POUR ACCELERER DES CALCULS EN ARITHMETIQUE MODULAIRE
Préambule de la description
Domaine concerné, problème pose
L' invention présentée ici est un procédé permettant d'accélérer les calculs en arithmétique modulaire, ce qui permet entre autres d'accélérer certaines opérations utilisées dans des protocoles cryptographiques .
Le problème du logarithme discret en arithmétique modulaire est utilisé aussi bien pour des protocoles d'authentification et d'échanges de clés que pour des systèmes de cryptographie asymétriques (comportant une clé publique et une clé privée) .
Les principes de ces protocoles sont bien décrits par exemple dans le brevet US # 4 200 770 « Cryptographie Apparatus and Method » de Hellman, Diffie et Merkle du 29 avril 1980 ou dans le brevet US # 4 405 829 « Cryptographie Communication System and Method » de Rivest, Shamir et Adleman du 20 septembre 1983. Le système décrit dans ce second brevet est appelé système RSA de cryptographie à clé publique ou tout simplement RSA. Ces brevets sont tous deux aujourd'hui du domaine public.
La sécurité des dits protocoles repose sur l'impossibilité de résoudre en un temps raisonnable le problème du logarithme discret en arithmétique modulaire, dont nous rappelons ici le principe.
L'arithmétique modulo N est une technique qui consiste à considérer que deux nombres entiers représentent la même entité mathématique dès que leur différence est un multiple entier d'un nombre N, appelé le module. On dira alors que ces deux nombres sont congrus modulo N.
Dans les applications cryptographiques, ce module N est en général très grand (plusieurs centaines de chiffres décimaux) . On utilise couramment des nombres à 512 ou 1024 bits ou plus.
Les entités mathématiques sur lesquelles on travaille sont appelées les entiers modulo N (entiers définis à l'addition près d'un multiple entier du module N) . L'ensemble des entiers modulo N peut être assimilé à l'ensemble des entiers compris entre 0 et N-l. L'addition et la multiplication y sont définies de façon similaire à leur définition en arithmétique classique, à ceci près que lorsqu'un résultat dépasse N-l, il est remplacé par le reste de sa division par N (nous écrirons par la suite « reste modulo N ») . Nous ne considérerons ici que la multiplication. L'ensemble des entiers modulo N, dont on aura enlevé les éléments non premiers à N, forme un groupe pour l'opération de multiplication, qu'on appellera groupe multiplicatif des entiers modulo N.
On peut réaliser en un temps raisonnable des additions et des multiplications modulo N. Le temps de calcul d'une addition est approximativement proportionnel au nombre de chiffres nécessaires pour représenter N. Le temps de calcul de la multiplication est approximativement proportionnel au carré de ce nombre de chiffres.
Notons cependant que, partant de deux nombres a et b définis modulo N (en pratique ce seront des entiers compris entre 0 et N-l) , la multiplication de a par b donne, en général, un nombre bien plus grand que N . Il faudra alors en calculer le reste modulo N en vue d' obtenir un nombre compris entre 0 et N-l. Cette opération sera appelée la « réduction modulo N ». Elle implique de faire une division par N. Or une division est, en général, bien plus longue à calculer qu'une multiplication, et ce temps de calcul augmente avec l'ordre de grandeur de N. Le résultat final de ces opérations sera noté a.b.[mod N] et se lira « a multiplié par b modulo N » .
Étant donne un nombre X, on appellera inverse de X modulo N un nombre Y tel que le produit X.Y [mod N] soit égal à 1. Le calcul de l'inverse d'un nombre en arithmétique modulo N se fait par l'algorithme d'Euclide généralisé et nécessite en général un temps de calcul significativement plus élevé que celui d'une multiplication. Cet algorithme est présenté en détail par exemple dans « Introduction à l'algorithmique » de Cormen, Leiserson, Rivest dont la traduction française est parue en 1994 chez Dunod. L'édition originale est parue en 1990 chez « The MIT Press, Cambridge Massachusetts » sous le titre « Introduction to Algorithme ».
L'exponentiation, pour une base a et un exposant b est la multiplication entre eux de b nombres égaux chacun à a. On réservera le nom d'exponentiation modulaire à l'exponentiation réalisée dans le groupe multiplicatif des entiers modulo N. Le résultat de cette opération est sera noté ci-après aΛb [mod N] et sera appelé « a puissance b modulo N ».
Le calcul de a^b [mod N] est plus complexe qu'une simple addition ou multiplication, mais il peut s'effectuer en un temps raisonnable, et l'objet de la présente invention est un procédé permettant d'accélérer ce calcul.
En revanche, si on connaît la base a et le résultat de l'exponentiation modulaire aΛb [mod N] , il est en général impossible (pour un module N assez grand) , de retrouver en un temps raisonnable l'exposant b. Ce problème est connu sous le nom de « problème du logarithme discret ».
Le nom provient de ce que, si on travaillait sur des nombres réels classiques, connaissant a et c = aΛb, l'exposant b serait simplement donne par la relation b = Log c / Log a Malheureusement (et heureusement pour les cryptographes) , il n'existe pas d'équivalent du logarithme dans les groupes utilisés en cryptographie et en particulier en arithmétique modulo N .
L' impossibilité de résoudre le problème du logarithme discret en un temps raisonnable fait que l'exponentiation modulaire est une excellente fonction « à sens unique ». Le calcul direct (calculer a^b [mod N] connaissant a et b) est très rapide, quelques fractions de secondes sur les micro-ordinateurs du commerce, pour un module N de plusieurs centaines de bits. Le temps nécessaire au calcul inverse (calculer b connaissant a et aΛb [mod N] ) peut se chiffrer en milliard d'années, même avec des moyens de calculs importants.
C'est cette fonction d'exponentiation modulaire qui est utilisée dans certaines applications cryptographiques. On bâtit un protocole dans lequel l'utilisateur normal ne fait que les calculs d'exponentiation, calculs raisonnablement rapides sur des machines peu puissantes . Un pirate souhaitant accéder frauduleusement aux informations devra, quant à lui, résoudre le problème inverse, celui du logarithme discret ce qui lui est impossible, même avec les moyens très importants dont pourrait par exemple disposer une organisation criminelle puissante.
En particulier, en ce qui concerne le système à clés publiques RSA, si on disposait d'une technique efficace pour résoudre le problème du logarithme discret, on pourrait retrouver les clés privées à partir des clés publiques, ce qui réduirait à néant la sécurité fournie par ce système.
Le calcul d'une multiplication en arithmétique modulo N se ramène, nous l'avons dit, à une multiplication de deux grands nombres entiers, (temps proportionnel au carré du nombre de chiffres de N) , suivi d'une réduction modulo N consistant à calculer le reste d'une division en nombres entiers par N. Le temps de calcul de cette réduction est équivalent à celui de plusieurs multiplication en grands nombres. L'invention a plus particulièrement pour objet un procédé permettant d'accélérer le calcul de multiplications en arithmétique modulo N, N désignant un entier comportant notamment plusieurs centaines de chiffres décimaux. L'invention concerne également un procédé permettant d'accélérer le calcul des exponentiations en arithmétique modulo N. Les multiplications et les exponentiations modulaires interviennent notamment dans des protocoles de cryptographie mis en œuvre à l'aide de ressources informatiques. Le procédé est plus particulièrement conçu pour économiser les ressources informatiques, telles que puissance de calcul et/ou espace mémoire .
Solution
Première variante de réalisation : Multiplication modulaire
Dans le cas d'une première variante de réalisation le procédé est plus particulièrement conçu pour permettre d' accélérer le calcul de multiplications en arithmétique modulo N.
Étapes préliminaires
Dans le cas de cette première variante de réalisation le procédé comprend les étapes préliminaires suivantes :
- l'étape de stocker le nombre N sur q mots,
- l'étape de soustraire le nombre N d'une puissance de 2 supérieure à N, notée R, pour obtenir un nombre, noté d.
Le nombre R est la première puissance de 2 ne pouvant pas être stockée sur q mots . Le procédé comprend en outre l'étape préliminaire de stocker le nombre d dans une mémoire de la ressource informatique.
De préférence, le nombre d doit être beaucoup plus petit que N, afin d'accélérer les calculs et d'économiser les ressources informatiques . De préférence les valeurs de N appropriées sont telles le nombre d tienne sur peu de mots, et de manière idéale sur un seul mot .
Premier opérateur Le procédé comporte un premier opérateur prenant en entrée deux nombres El, E2 stockés chacun sur q mots et fournissant en sortie un nombre W tel que le produit par R du nombre W soit congru modulo N au produit des entrées El , et E2. Les dites entrées El, E2 sont ci-après dénommées les entrées du premier opérateur, et le nombre W est ci-après dénommé le résultat du premier opérateur.
Forme de réalisation du premier algorithme
Le procédé comporte un premier algorithme ayant pour objet de remplacer un argument, stocké sur 2q mots, par un résultat qui est congru modulo N à l'argument et dont les q mots de poids faibles sont nuls. Cet argument est ci-après dénommé l'argument du premier algorithme. Le résultat est ci-après dénommé le résultat du premier algorithme.
Il résulte de la combinaison des traits techniques que le résultat du premier algorithme est un multiple de R.
Étapes principales
Le procédé comprend en outre les étapes principales suivantes pour multiplier entre eux modulo N deux nombres A et
B,
- l'étape de stocker en mémoire les restes modulo N du produit par R des nombres A et B, les restes stockés en mémoire sont respectivement dénommés le nombre F et le nombre G,
- l'étape de mettre en œuvre le premier opérateur, les entrées El et E2 prenant respectivement comme valeur les nombres F et G,
1 ' étape de stocker le résultat W du premier opérateur sous la forme d'un nombre à 2q mots, ci-après dénommé H.
Il résulte de la combinaison des traits techniques que ce nombre H est égal au reste modulo N du produit des nombres A, B et R.
Le procédé comprend en outre les étapes principales suivantes : - l'étape de mettre en oeuvre le premier algorithme avec comme argument le nombre H, stocké sur 2q mots, pour fournir un nombre V congru modulo N au nombre H et dont les q mots de poids faibles sont nuls,
- l'étape de lire le nombre à q mots C constitué par les q mots de poids fort du nombre V.
Le nombre C ou le nombre C-N est égal au reste modulo N du produit des nombres A et B.
Forme de réalisation du premier algorithme De préférence selon l'invention, le premier algorithme consiste à itérer q fois une opération ayant pour effet de remplacer le nombre obtenu au terme de 1 ' itération précédente par un nombre qui lui est congru modulo N et tel que le nombre obtenu au terme de la ième itération ait tous ses mots de poids les plus faibles nuls jusqu'au iè e. La ième opération comprend les quatre étapes suivantes :
(a) on multiplie le ième mot, dans l'ordre des poids croissants, du nombre issu de l'itération précédente, ou, lors de la première itération, le mot de poids faible de l'argument du premier algorithme, par une constante prédéfinie de manière à obtenir un résultat dont on ne conserve que le mot de poids faible,
(b) on obtient au terme de l'étape précédente (a) un résultat, dénommé x, qu'on multiplie par le nombre d,
(c) on décale le résultat x de la première étape (a) de q+i crans vers les poids forts et on ajoute le nombre ainsi décalé au nombre issu de l'itération précédente ou lors de la première itération à l'argument du premier algorithme,
(d) on obtient au terme de l'étape (b) un résultat, dénommé y, qu'on décale de i crans dans le sens des poids forts puis qu'on soustrait au nombre issu du résultat de l'addition effectuée à l'étape (c) précédente.
Le résultat de cette soustraction constitue le résultat de l'itération en cours. On obtient au terme des quatre étapes de la ième itération un nombre qui est congru modulo N à l'argument du premier algorithme et dont tous les mots de poids les plus faibles sont nuls jusqu'au ième.
Forme de réalisation du premier opérateur De préférence selon l'invention, le premier opérateur comprend les étapes suivantes :
- l'étape de multiplier entre elles les entrées El et E2 du premier opérateur, les entrées El et E2 ayant pris pour valeurs les nombres F et G, le résultat de cette multiplication est un nombre T stocké sur 2q mots,
- l'étape de mettre en œuvre le premier algorithme avec comme argument le nombre T pour fournir comme résultat un nombre dénommé U, stocké sur 2q mots,
- l'étape de lire le nombre à q mots constitué par les q mots de poids fort du nombre U, le nombre à q mots constitue le résultat W du premier opérateur.
Il résulte de la combinaison des traits techniques que les q mots de poids faible de U sont nuls. Il résulte également de la combinaison des traits techniques que le résultat W multiplié par R est congru modulo N au produit des entrées El et E2.
Autre forme de réalisation du premier opérateur De préférence selon une autre forme de réalisation du premier opérateur, le premier opérateur comprend les étapes préliminaires suivantes :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El du premier opérateur, l'entrée El ayant pris pour valeur le nombre F.
Dans le cas de cette forme de réalisation le premier opérateur comprend une étape principale consistant à itérer les sous-étapes suivantes : - (a) la sous-étape de multiplier le mot ainsi sélectionné par l'entrée E2 du premier opérateur, l'entrée E2 ayant pris pour valeur le nombre G, le résultat de cette multiplication est un nombre stocké sur q+1 mots et est dénommé
P,
- (b) la sous-étape d'additionner le nombre P, calculé à l'étape précédente, au contenu de la mémoire Z, le bit de retenue est positionné à 1 ou a 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans la mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de la mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre N, le résultat de cette multiplication est un nombre dénommé Q stocké sur q+1 mots,
- (f) la sous-étape d'additionner le nombre Q, calculé à l'étape (e) précédente, au contenu de la mémoire Z,
- (g) la sous-étape de stocker dans la mémoire Z le résultat de l'addition effectuée dans l'étape précédente.
A la suite de ces sous étapes, le mot de poids faible de la mémoire Z contient la valeur zéro.
L'étape principale consistant également à itérer les autres sous-étapes suivantes :
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de la mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de la mémoire Z le contenu du bit de retenue,
- (j) la sous-étape de mettre à zéro le bit de retenue .
Le premier opérateur comprend en outre une autre étape principale. Cette autre étape principale consiste lire le mot suivant de l'entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j ) , autant de fois que nécessaire.
Il résulte de la combinaison des traits techniques qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, la mémoire Z contient un nombre, compris entre zéro et 2N, dont le produit par R est égal, modulo N, au produit des entrées El et E2.
Dans le cas de cette forme de réalisation du premier opérateur, le premier opérateur comprend en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de la mémoire Z,
- l'étape, lorsque ce contenu est supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction est stocké dans la mémoire Z .
Le résultat W du premier opérateur, au sens de la présente invention, est égal au contenu de la mémoire Z. Autre forme de réalisation du premier opérateur De préférence selon une autre forme de réalisation du premier opérateur, le premier opérateur comprend l'étape préliminaire suivante :
- l'étape d'initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El du premier opérateur, l'entrée El ayant pris pour valeur le nombre F.
Dans le cas de cette autre forme de réalisation du premier opérateur, le premier opérateur comprend une étape principale consistant à itérer les sous-étapes suivantes :
- (a) la sous-étape de multiplier le mot ainsi sélectionné par l'entrée E2 du premier opérateur, l'entrée E2 ayant pris pour valeur le nombre G, le résultat de cette multiplication est un nombre stocké sur q+1 mots et est dénommé
P,
- (b) la sous-étape d'additionner le nombre P, calculé à l'étape précédente, au contenu de la mémoire Z, le bit de retenue est positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans la mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de la mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) les sous-étapes :
• d'additionner le résultat m de l'étape précédente au contenu du mot de poids fort de la mémoire Z,
• de stocker le résultat de cette addition dans le même mot de poids fort,
• en cas de dépassement de capacité de cette addition, de mettre à 1 le bit de retenue,
- (f) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre d, le résultat de cette multiplication est un nombre dénommé Q,
- (g) la sous-étape de soustraire le nombre Q, calculé à l'étape précédente, au contenu de la mémoire Z, puis de stocker dans la mémoire Z le résultat de cette soustraction.
Il résulte de la combinaison de ces traits techniques que le mot de poids faible de la mémoire Z contient la valeur zéro.
L'étape principale consiste également à itérer les sous-étapes suivantes :
- (h) la sous-étape de décaler d'un mot, dans la direction des mots de poids faibles, le contenu des mots de la mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de la mémoire Z le contenu du bit de retenue, - (j) la sous-étape de mettre à zéro le bit de retenue .
Le premier opérateur comprend en outre l'étape principale de lire le mot suivant de l'entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j) autant de fois que nécessaire.
Il résulte de la combinaison des traits techniques qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, la mémoire Z contient un nombre H dont le produit par R est égal, modulo N, au produit des nombres El et E2.
Dans le cas cette autre forme de réalisation, le premier opérateur comprend en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de la mémoire Z,
- l'étape, lorsque ce contenu supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction est stocké dans la mémoire Z.
Le résultat W du premier opérateur est égal au contenu de la mémoire Z.
On notera que le stockage du nombre Q (voir sous-étape
(f) ) nécessite un mot de plus que le nombre de mots nécessaire pour stocker d. Par conséquent on économise d'autant plus de temps de calcul et de mémoire que d tient sur peu de mots, à l'idéal sur un mot.
De préférence, selon l'invention, pour calculer le reste modulo N, dénommé le nombre F, respectivement dénommé le nombre G , du produit par R d'un nombre donné A, respectivement B :
- on multiplie le nombre A, respectivement le nombre B, par le reste modulo N du carré de R, pour obtenir un nombre dénommé TA, respectivement TB, stocké sur 2q mots,
- on applique le premier algorithme avec comme argument le nombre TA, respectivement le nombre TB, pour obtenir comme résultat un nombre VA, respectivement un nombre VE, qui lui est congru modulo N et dont les q mots de poids faibles sont nuls.
Le nombre F, respectivement le nombre G, est alors le nombre à q mots formés des q mots de poids forts du nombre VA, respectivement du nombre VB.
Exponentiation modulaire
L'invention concerne également une seconde variante de réalisation permettant d'accélérer le calcul des exponentiations en arithmétique modulo N. Dans le cas de cette seconde variante de réalisation, le procédé a pour objet d'élever un nombre A, ci après dénommé la base, à une puissance p modulo N. p étant un nombre entier supérieur ou égal à 2, ci-après dénommé l'exposant, et étant représenté sous forme binaire.
Variante de réalisation mettant en œuvre un premier algorithme
Étapes préliminaires
Le procédé comprend les étapes préliminaires suivantes :
- l'étape de stocker le nombre N sur q mots,
- l'étape de soustraire le nombre N d'une puissance de 2 supérieure à N, notée R, pour obtenir un nombre, noté d.
Le nombre R est la première puissance de 2 ne pouvant pas être stockée sur q mots .
Le procédé comprend l'étape préliminaire de stocker le nombre d dans une mémoire de la ressource informatique.
On notera que les étapes préliminaires ci-dessus sont exécutées une fois pour toutes, une fois la valeur de N fixée : elles ne dépendent ni de la base A ni de l'exposant p
Le procédé comprend en outre les étapes préliminaires suivantes :
- l'étape de stocker en mémoire le reste modulo N du produit par R de la base A, le reste stocké en mémoire est dénommé le nombre F, - l'étape d' initialiser une zone mémoire de 2q mots, ci-après dénommée la zone mémoire Y, avec une copie nombre F.
On notera que les étapes préliminaires ci-dessus dépendent de la base A.
Le procédé comporte un premier algorithme ayant pour objet de remplacer un argument, stocké sur 2q mots, par un résultat qui est congru modulo N à cet argument et dont les q mots de poids faibles sont nuls. Cet argument est ci-après dénommé l'argument du premier algorithme. Le résultat est ci- après dénommé le résultat du premier algorithme.
Il résulte de la combinaison des traits techniques que le résultat du premier algorithme est un multiple de R
Le premier algorithme mis en œuvre dans le cas de la présente deuxième variante réalisation est le même que celui qui a été décrit, notamment sous une forme de réalisation particulière, lors de l'exposé de la. première variante de réalisation. On pourra donc se reporter également, en tant que de besoin, à la précédente description du premier algorithme.
Le procédé comprend les étapes principales suivantes :
- l'étape de sélectionner, en commençant par les bits de poids forts, le premier bit suivant le premier bit non nul de l'exposant p,
- l'étape consistant à mettre en œuvre, selon le cas, les opérations ci-après définies :
Cas où le bit sélectionné est égal à zéro :
Dans le cas où le bit sélectionné est égal à zéro :
• (a) on calcule le carré du contenu de la zone mémoire Y,
• (b) on stocke dans la zone mémoire Y, le résultat du calcul précédent,
• (c) on met en œuvre le premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir comme résultat un nombre U0 congru modulo N à cet argument et dont les q mots de poids faibles sont nuls, • (d) on stocke dans les q mots de poids faible de la zone mémoire Y, les q mots de poids forts du résultat U0 du calcul précédent,
• (e) on met à zéro le contenu des q mots de poids forts de la mémoire Y. Cas où le bit sélectionné est égal à un.
Dans le cas où le bit sélectionné est égal à un, on réalise les mêmes opérations (a) a (e) que dans le cas où l'exposant sélectionné est égal à zéro et en outre on multiplie le contenu de la mémoire Y, au terme de l'opération (e) , par le nombre F,
• (g) on stocke dans la zone mémoire Y, le résultat du calcul précédent,
• (h) on met en œuvre le premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir comme résultat un nombre U_ congru modulo N à cet argument et dont les q mots de poids faibles sont nuls,
• (i) on stocke dans les q mots de poids faible de la zone mémoire Y, les q mots de poids forts du résultat U_ du calcul précédent,
• (j) on met à zéro le contenu des q mots de poids forts de la mémoire Y.
Le procédé comprend en outre l'étape principale suivante :
- l'étape de lire le bit suivant de l'exposant p, dans l'ordre des poids décroissants, et
• lorsque le bit est égal à zéro on itère les opérations (a) à (e) ,
• lorsque le bit est égal à un on itère les opérations (a) à (j) .
Les itérations sont effectuées autant de fois que nécessaire.
Il résulte de la combinaison des traits techniques qu'au terme du processus, après avoir sélectionné tous les bits de l'exposant, la mémoire Y contient un nombre qui est congru modulo N au produit du nombre R par le résultat de l'exponentiation A puissance p.
Le procédé comprend en outre l'étape de mettre en œuvre le premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir un nombre S congru modulo N à cet argument et dont les q mots de poids faibles sont nuls.
Il résulte de la combinaison des traits techniques que les q mots de poids fort du nombre S représentent un nombre compris entre zéro et 2N et congru modulo N au résultat de l'exponentiation A puissance p.
Le procédé comprend en outre les étapes finales suivantes :
- l'étape de lire le nombre à q mots D constitué par les q mots de poids fort du nombre S,
- l'étape de comparer ce nombre au nombre N
- l'étape, lorsque D est supérieur à N, de retrancher le nombre N du nombre D .
Il résulte de la combinaison des traits techniques que le nombre D auquel on a éventuellement soustrait N est égal au résultat de l'exponentiation A puissance p modulo N qu'on souhaite calculer .
Variante de réalisation mettant en oeuvre un premier opérateur
De préférence selon une variante de réalisation, le procédé comporte un premier opérateur. Le procédé comprend les étapes préliminaires suivantes :
- l'étape de stocker en mémoire le reste modulo N du produit par R du nombre A, le reste stocké en mémoire est dénommé le nombre F,
- l'étape d' initialiser une zone mémoire de q mots, ci-après dénommée la zone mémoire Y, avec le nombre F.
Le premier opérateur prend en entrée deux nombres El, E2 stockés chacun sur q mots et fournissant en sortie un nombre W, stocké sur q mots, tel que le produit par R du nombre W soit congru modulo N au produit des entrées El , et E2. Les dites entrées El, E2 sont ci-après dénommées les entrées du premier opérateur et le nombre W est ci-après dénommé le résultat du premier opérateur.
Le procédé comprend les étapes principales suivantes :
- l'étape de sélectionner, en commençant par les bits de poids forts, le premier bit suivant le premier bit non nul de l'exposant p,
- l'étape consistant à mettre en œuvre, selon le cas, les opérations ci-après définies.
Cas où le bit sélectionné est égal à zéro Dans le cas où le bit sélectionné est égal à zéro, les opérations mises en œuvre sont les suivantes :
(a) l'étape de mettre en œuvre le premier opérateur, les deux entrées El et E2 du premier opérateur prenant toutes deux une valeur égale au contenu de la zone mémoire Y,
(b) l'étape de stocker le résultat W fourni par le premier opérateur dans la zone mémoire Y,
Cas où le bit sélectionné est égal à un Dans le cas où le bit sélectionné est égal à un, on réalise les mêmes opérations (a) et (b) que dans le cas où l'exposant sélectionné est égal à zéro et en outre on réalise les deux étapes suivantes :
(c) l'étape de mettre en œuvre le premier opérateur les entrées El et E2 de cet opérateur prenant l'une pour valeur le nombre F et l'autre une valeur égale au contenu de la zone mémoire Y,
(d) l'étape de stocker le résultat W fourni par le premier opérateur dans la zone mémoire Y.
Le procédé comprend en outre l'étape principale suivante :
- l'étape de lire le bit suivant de l'exposant p, dans l'ordre des poids décroissants, et
• lorsque le bit est égal à zéro on itère les opérations (a) à (b) , • lorsque le bit est égal à un on itère les opérations (a) à (d) .
Les itérations sont effectuées autant de fois que nécessaire .
Il résulte de la combinaison des traits techniques qu'au terme du processus, après avoir sélectionné tous les bits de l'exposant, la mémoire Y contient un nombre qui est congru modulo N au produit du nombre R par le résultat de l'exponentiation A puissance p.
Le procédé comprend en outre l'étape finale de mettre en œuvre le premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir un nombre S congru modulo N à cet argument et dont les q mots de poids faibles sont nuls .
Il résulte de la combinaison des traits techniques que les q mots de poids fort du nombre S représentent un nombre congru modulo N au résultat de l'exponentiation A puissance p.
Le procédé comprend en outre les étapes finales suivantes :
- l'étape de lire le nombre à q mots D constitué par les q mots de poids fort du nombre S,
- l'étape de comparer ce nombre au nombre N,
- l'étape, lorsque D est supérieur à N, de retrancher le nombre N du nombre D.
Il résulte de la combinaison des traits techniques que le nombre D auquel on a éventuellement soustrait N est égal au résultat de l'exponentiation A puissance p modulo N qu'on souhaite calculer.
Forme de réalisation du premier algorithme De préférence, selon une forme de réalisation particulière du premier algorithme, le premier algorithme consiste à itérer q fois une opération ayant pour effet de remplacer le nombre obtenu au terme de l'itération précédente par un nombre qui lui est congru modulo N et tel que le nombre obtenu au terme de la ième itération ait tous ses mots de poids les plus faibles nuls jusqu'au ième. La ième opération comprend les quatre étapes suivantes :
(a) on multiplie le ième mot, dans l'ordre des poids croissants, du nombre issu de l'itération précédente, ou lors de la première itération le mot de poids faible de l'argument du premier algorithme, par une constante prédéfinie de manière à obtenir un résultat dont on ne conserve que le mot de poids faible,
(b) on obtient au terme de l'étape précédente (a) un résultat, dénommé x, qu'on multiplie par le nombre d,
(c) on décale le résultat x de la première étape (a) de q+i crans vers les poids forts et on ajoute le nombre ainsi décalé au nombre issu de l'itération précédente ou lors de la première itération à l'argument du premier algorithme,
(d) on obtient au terme de l'étape (b) un résultat, dénommé y, qu'on décale de i crans dans le sens des poids forts puis qu'on soustrait au nombre issu du résultat de l'addition effectuée à l'étape (c) précédente.
Le résultat de cette soustraction constitue le résultat de l'itération en cours.
Il résulte de la combinaison des traits techniques qu' on obtient au terme des quatre étapes de la ième itération un nombre qui est congru modulo N à l'argument du premier algorithme et dont tous les mots de poids les plus faibles sont nuls jusqu'au ième.
Autre forme de réalisation du premier opérateur
De préférence selon une forme de réalisation particulière du premier opérateur, le premier opérateur comprend les étapes suivantes :
- l'étape de multiplier entre elles les entrées El et E2 du premier opérateur pour obtenir un nombre T stocké sur 2q mots,
- l'étape de mettre en œuvre le premier algorithme avec comme argument le nombre T pour fournir comme résultat un nombre dénommé U, stocké sur 2q mots, - l'étape de lire le nombre à q mots constitué par les q mots de poids fort du nombre U, le nombre à q mots constituant le résultat W du premier opérateur.
Il résulte de la combinaison des traits techniques que les q mots de poids faible de U sont nuls. Il résulte également de la combinaison des traits techniques que la sortie W multipliée par R est congrue modulo N au produit des entrées El et E2.
Autre forme de réalisation du premier opérateur
Étape préliminaire
De préférence selon une autre forme de réalisation du premier opérateur, le premier opérateur comprend les étapes préliminaires suivantes :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El du premier opérateur.
Étape principale
Le premier opérateur comprend l'étape principale consistant à itérer les sous-étapes suivantes :
- (a) la sous-étape de multiplier le mot ainsi sélectionné par l'entrée E2, le résultat de cette multiplication est un nombre stocké sur q+1 mots et est dénommé P,
- (b) la sous-étape d'additionner le nombre P, calculé à l'étape précédente, au contenu de la mémoire Z, le bit de retenue est positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans la mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de la mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m, - (e) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre N, le résultat de cette multiplication est un nombre dénommé Q stocké sur q+1 mots,
- (f) la sous-étape d'additionner le nombre Q, calculé à l'étape (e) précédente, au contenu de la mémoire Z,
- (g) la sous-étape de stocker dans la mémoire Z le résultat de l'addition effectuée dans l'étape précédente.
Le mot de poids faible de la mémoire Z contient la valeur zéro.
L'étape principale comprend également les sous-étapes suivantes :
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de la mémoire Z,
- (i) la sous-étape de stocker dans le mot' de poids fort de la mémoire Z le contenu du bit de retenue,
- (j) la sous-étape de mettre à zéro le bit de retenue .
Le premier opérateur comprend en outre l'étape principale de lire le mot suivant de l'entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j), autant de fois que nécessaire.
Il résulte de la combinaison des traits techniques qu'au terme du processus, après avoir sélectionné, dans l'ordre des .poids croissants, tous les mots constituant l'entrée El, la mémoire Z contient un nombre, compris entre zéro et 2N, dont le produit par R est égal, modulo N, au produit des nombres El et E2.
Étape principale finale
Le premier opérateur comprend en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de la mémoire Z, - l'étape, lorsque ce contenu est supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction est stocké dans la mémoire Z.
Le résultat W du premier opérateur est égal au contenu de la mémoire Z.
Autre forme de réalisation du premier opérateur
Étape préliminaire
De préférence selon une autre forme de réalisation du premier opérateur, le premier opérateur comprend les étapes préliminaires suivantes :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El du premier opérateur.
Étape principale
Le premier opérateur comprend l'étape principale consistant à itérer les sous-étapes suivantes :
- (a) la sous-étape de multiplier le mot ainsi sélectionné par l'entrée E2 du premier opérateur, le résultat de
- cette multiplication est un nombre stocké sur q+1 mots et est dénommé P,
- (b) la sous-étape d'additionner le nombre P, calculé à l'étape précédente, au contenu de la mémoire Z, le bit de retenue est positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans la mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de la mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) les sous-étapes :
• d'additionner le résultat m de l'étape précédente au contenu du mot de poids fort de la mémoire Z, • de stocker le résultat de cette addition dans le même mot de poids fort,
• en cas de dépassement de capacité de cette addition, de mettre à 1 le bit de retenue,
- (f) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre d, le résultat de cette multiplication est un nombre dénommé Q,
- (g) la sous-étape de soustraire le nombre Q, calculé à l'étape précédente, au contenu de la mémoire Z, puis de stocker dans la mémoire Z le résultat de cette soustraction.
Le mot de poids faible de la mémoire Z contient la valeur zéro.
L'étape principale consiste également à itérer les sous-étapes suivantes :
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de la mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de la mémoire Z le contenu du bit de retenue,
- (j) la sous-étape de mettre à zéro le bit de retenue .
Le premier opérateur comprend en outre l'étape principale de lire le mot suivant de l'entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j) autant de fois que nécessaire.
Il résulte de la combinaison des traits techniques qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, la mémoire Z contient un nombre H dont le produit par R est égal, modulo N, au produit des nombres El et E2.
Etape principale finale le premier opérateur comprend en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de la mémoire Z, - l'étape, lorsque ce contenu supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction est stocké dans la mémoire Z.
Le résultat W du premier opérateur est égal au contenu de la mémoire Z.
Ainsi qu'on l'a déjà noté, le stockage du nombre Q ( voir étape (f) ) nécessite un mot de plus que le nombre de mots nécessaire pour stocker d. par conséquent, on économise d'autant plus de temps de calcul et de mémoire que d tient sur peu de mots, à l'idéal un seul mot.
De préférence, selon l'invention, le procédé est tel que pour calculer le reste modulo N du produit par R de la base A, dénommé le nombre F :
- on multiplie le nombre A par le reste modulo N du carré de R, pour obtenir un nombre dénommé T, stocké sur 2q mots,
- on applique le premier algorithme avec comme argument le nombre T, pour obtenir comme résultat un nombre V, qui lui est congru modulo N et dont les q mots de poids faibles sont nuls .
Le nombre F est alors le nombre à q mots formés des q mots de poids forts du nombre V.
Description détaillée
D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description de variantes de réalisation de l'invention données à titre d'exemple indicatif et non limitatif.
Avant de décrire comment on réalise en pratique les opérations en arithmétique modulo N, décrivons en détail comment se font les calculs sur des grands nombres
On suppose que les calculs seront réalisés sur un processeur qui fait des opérations élémentaires, additions et multiplications, sur des mots de w bits, par exemple w=32, pour un processeur à 32 bits. On notera B le nombre 2^ , 2 puissance w, et on considère qu'un mot de w bits représente un nombre entier compris entre 0 et B-l, ou encore un nombre en arithmétique modulo B. Un tel nombre sera appelé un scalaire.
Une addition élémentaire prend deux scalaires, donc deux mots de w bits, et les additionne. Le résultat occupe +1 bits, compte tenu d'une éventuelle retenue. Il sera stocké sous la forme d'un mot de w bits, contenant le résultat compte non tenu de la retenue, donc le résultat en arithmétique modulo B, accompagné d'un bit indiquant s'il y a ou non retenue, ce bit est parfois appelé bit d'overflo c'est-à-dire bit de dépassement de capacité.
Une multiplication élémentaire prend deux scalaires, donc deux mots de w bits, les multiplie entre eux et stocke le résultat, qui occupe alors 2w bits, sur deux mots de w bits, en séparant les w bits les plus significatifs et les w bits les moins significatifs.
Évaluons le nombres d'opérations élémentaires nécessaires, additions et/ou multiplications, pour une addition et une multiplication en grands nombres. Ce nombre n'est pas équivalent au nombre d' instructions ou au nombre de tops d'horloge nécessaires à un processeur pour réaliser le calcul, car on ne tient pas compte de la richesse potentielle du jeu d'instruction. Celui-ci peut permettre, dans certains cas, au cours de la même instruction, d'ajouter le résultat d'une multiplication au contenu d'un registre, ou de deux registres en séparant le mot de poids fort et le mot de poids faible du résultat. Cela permet donc de réaliser une ou deux additions supplémentaires en même temps que la multiplication demandée, c'est-à-dire dans le même cycle d'horloge et sans nécessiter de temps additionnel. C'est en particulier le cas pour des implémentations dans le silicium en utilisant des processeurs comme le processeur ARM.
Étant donné un grand nombre T, dont l'écriture binaire nécessite r fois w bits, on utilisera, pour son stockage dans un système informatique, une suite de r mots de w bits, notés T[0], T[l],... , T[r-1], en convenant que T est égal à la somme des produits T[i].(B i) ,où le point désigne la multiplication et l'expression BAi représente B puissance i, le nombre i variant entre 0 et r-l> et B étant égal à 2Aw . Cette représentation sera appelée la représentation binaire standard du nombre T. On conviendra d'écrire l'expression, T[r-1], ... , T[l], T[0] , pour désigner le nombre T dans cette représentation informatique. On prendra garde à l'ordre d'écriture des mots. Cette notation est analogue à la notation décimale classique où par exemple le nombre à quatre chiffres décimaux 4893 représente la somme 4.10 3 + 8.10A2 + 9.10 + 3 . Le nombre B et les mots T[i], dans la représentation introduite ici, jouent les mêmes rôles que le nombre 10 et que les chiffres dans la notation décimale classique. Le nombre i est appelé l'indice ou le poids du mot T[i] dans la représentation de T. La représentation sur r mots de w bits permet de représenter tous les nombres entiers compris entre 0 et BAr - 1, c'est-à-dire 2 (r.w) - 1 . Dans la suite, nous dirons que T est un nombre à r mots, un scalaire étant par définition un nombre à un seul mot.
Dans cette représentation les mots T[j] d'indice élevé seront appelés « mots de poids fort » ou « mots les plus significatifs » et ceux d'indice j faible seront appelés « mots de poids faible » ou « mots les moins significatifs ».
Une addition entre deux grands nombres, respectivement à r et à s mots, en supposant s inférieur ou égal à r, se ramène à s additions mot par mot, les mots étant pris dans l'ordre croissant de leur poids, avec éventuelle propagation d'une retenue qui sera prise en compte à l'étape suivante.
Une méthode simple et naturelle pour réaliser la multiplication entre un nombre T de r mots et un nombre U de s mots consiste à utiliser une zone mémoire V de r+s mots, mémoire qui fonctionnera comme un accumulateur et qui, à la fin du calcul, contiendra le résultat final. Cette zone V sera, au préalable, initialisée à zéro. Puis, pour tout couple formé d'un mot de T et d'un mot de U, donc au total r.s fois, on multiplie entre eux ces deux mots, multiplication élémentaire, résultat sur deux mots, les deux mots résultats étant ajoutés aux mots adéquats de la zone mémoire V . On a donc au total r.s multiplications et 2 r.s additions, compte non tenu des reports de bits de retenue. Notons que, les r+s mots de la zone V étant au préalable initialisée à zéro, les premières additions sur ces mots sont en fait des affectations, et en toute rigueur, le nombre exact d'additions est égal à 2 r.s - (r+s) .
Si on utilise un processeur adéquat, une programmation astucieuse permet de faire pratiquement toutes les additions en même temps que les multiplications. Dans un tel cas, une évaluation approximative du temps de calcul nécessaire, estimé en nombre de cycles d'horloge du processeur utilisé, nécessite uniquement de prendre en compte les multiplications.
En particulier, une multiplication entre un nombre stocké sur r mots et un scalaire, stocké sur s=l mot, représente r multiplications élémentaires et (r-1) additions élémentaires, pour la prise en compte des retenues, le résultat étant stocké sur r+1 mots.
Une multiplication entre deux nombres représentés chacun sur r mots de w bits (ou l'élévation au carré d'un mot de w bits) représente dans le cas général rA2 (r au carré) multiplications élémentaires et 2r. (r-l) additions élémentaires.
Analysons maintenant le problème des opérations en arithmétique modulo N où N est un grand nombre impair, dont l'écriture binaire nécessite par exemple 512 ou 1024 bits, ce qui correspond à environ 150 ou 300 chiffres décimaux. Ce nombre N sera représenté comme un nombre à q mots . Par exemple si on travaille sur un processeur à w=32 bits et si N est un nombre à 512, respectivement 1024, bits, on aura q - 16, respectivement 32.
On définit alors le nombre R comme étant la première puissance de 2 qui ne peut pas être stockée sur q mots . Ce nombre est égal à 2 à la puissance le produit qw c'est-à-dire à B puissance q, soit 2 puissance 512 ou 2 puissance 1024 dans les exemples ci-dessus. Ce nombre est, par construction, supérieur à N.
On appelle d la différence R-N , et on note rd le nombre minimal de mots nécessaire au stockage informatique de la valeur de d, en représentation binaire standard. Ce nombre rd est toujours inférieur ou égal à q.
Dans les applications pratiques, on se place habituellement dans le cas où le bit de poids fort de N est égal à 1 (N est effectivement un nombre à 512 ou 1024 bits) , et on a alors les inégalités 0 < d < R/2 < N < R . En général d est bien plus petit que la borne ci-dessus, et ra peut être significativement inférieur à q . Dans le cas idéal ra sera égal à 1 .
On appellera e le nombre stocké sur un seul mot et tel que le produit d.e ait son mot de poids faible égal à 1. (Le nombre e est donc l' inverse modulo B du mot de poids faible de d) . N étant impair, il en est de même de d, donc d est premier à B, ce qui prouve l'existence et l'unicité de e .
On appellera f le reste modulo N du carré de d. Notons que lorsque d est petit, et en particulier lorsque rd est inférieur à q/2, le nombre f est tout simplement égal au carré du nombre d.
Les nombres d, e et f sont calculés à l'avance et stockés dans la mémoire du processeur utilisé pour effectuer les calculs .
Nous décrivons pour commencer une méthode permettant de remplacer un nombre T par un nombre U qui est congru à T modulo N et dont le mot de poids faible, d'indice 0, est nul. On suppose que T est écrit sur 2q mots, les mots de poids forts étant, si nécessaire, nuls.
Dans un premier temps, on multiplie par e le mot de poids faible de T, et on ne garde que le mot de poids faible du résultat. Ce mot de poids faible sera noté x. Le nombres x est donc le reste par B du produit T[0] .e . D'une part, le mot x est additionné au mot d'indice q de T (avec propagation de l'éventuelle retenue sur le mot d'indice q+1) , et d'autre part le mot x est multiplié par d pour obtenir un nombre y qui sera soustrait au nombre T. Notons que le nombre y occupe au maximum rd+l mots.
Soit U la nouvelle valeur de T après ces deux opérations. On démontre que ce nombre U est congru modulo N au nombre initial T dont on était parti. Par ailleurs le mot de poids faible de U est nul, cela résulte de ce que le produit d.e est congru à 1 modulo B . Notons que le fait de savoir d' avance que ce mot est nul peut être utilisé lors de l'implementation informatique de l'algorithme.
De la même façon, si, dans le nombre T, les i mots de poids les plus faibles sont nuls, c'est-à-dire si les mots T[0], T[l], ..., T[i-1], avec les notations décrites précédemment, sont nuls, on peut par une méthode similaire, remplacer le nombre T par un nombre qui lui est congru modulo N et dont le mot d'indice i est nul. Pour ce faire, on calcule le nombre x égal au mot de poids faible du produit e.T[i], et le nombre y égal au produit x.d . Le nombre x sera additionné au mot d'indice q+i de T, avec éventuelle propagation de retenue, et le nombre y sera décalé de i crans dans la direction des poids forts avant d'être soustrait du nombre T ainsi modifié. Soit U la nouvelle valeur de T après ces deux opérations . On démontre que ce nombre U est congru modulo N au nombre initial T dont on était parti, et que par ailleurs les i+1 mot de poids faible de U sont nuls .
De proche en proche, en itérant au plus q fois l'opération précédente, on peut ainsi remplacer un nombre T par un nombre U qui lui est congru modulo N et dont les q mots de poids faible sont nuls.
La méthode ainsi décrite, composée d'une suite d'itérations, constitue un premier algorithme qui permet de passer d'un nombre T à nombre V multiple de R et congru à T modulo N. Ce premier algorithme est d'autant plus rapide que le nombre rd de mots nécessaires pour stocker d est faible.
Ce premier algorithme est l'un des éléments de base de la présente invention.
Pour effectuer la multiplication modulo N de deux nombres A et B, on calcule dans un premier temps deux nombres F et G à q mots et respectivement congrus modulo N aux produits A.R et B.R. Pour ce faire, on multiplie A, respectivement B, par f pour obtenir un nombre dénommé TA, respectivement TB, stocké sur 2q mots. On applique alors à TA, respectivement TB, le premier algorithme décrit ci-avant, pour obtenir un nombre VA, respectivement VB, congru, modulo N, à TA, respectivement TB, et multiple de R.
En extrayant les q mots de poids fort de ces deux résultats on obtient les nombres F et G recherchés . On calcule le produit F.G qu'on note T. Ce nombre, stocké sur 2q bits, est congru modulo N à ABRR. On applique le premier algorithme et on lit les q mots de poids fort pour obtenir un nombre congru modulo N à ABR, et on répète la même opération pour obtenir un nombre congru modulo N à AB. Si ce nombre est inférieur à N, c'est le résultat cherché, à savoir le reste par N du produit des nombres A et B. Si ce nombre n'est pas inférieur à N, on peut démontrer qu' il est inférieur à 2N et il suffira de lui soustraire N pour obtenir le résultat cherché.
La méthode décrite ici prend tout son intérêt lorsque rd est petit car le premier algorithme est alors rapide, de même que les produits par f qui est alors un nombre à 2 rd mots . La seule opération longue reste le calcul du produit F.G .
La méthode peut encore être améliorée si on imbrique le calcul du produit F.G et l'application du premier algorithme au résultat de cette multiplication. Cette opération sera réalisée en considérant l'un des nombres facteurs, par exemple G, dans son ensemble, mais en utilisant mot après mot les mots formant l'autre facteur, par exemple F, en commençant par les mots de poids faible. En pratique, on procède comme suit. Dans une étape préliminaire, on initialise à 0 une zone mémoire Y formée de q+1 mots et d'un bit de retenue. Cette zone mémoire fonctionnera d'une part comme un registre à décalage et d'autre part comme un accumulateur dans lequel s'additionneront les résultats intermédiaires de calcul. On itère alors les opérations suivantes pour un indice i variant de 0 à q-1.
Lors de l'itération d'indice i, on multiplie le mot d'indice i de F par le nombre G pour obtenir un résultat P, sur q+1 mots, qui sera ajouté au contenu de la mémoire Y. Notons que si le jeu d'instructions du processeur utilisé le permet, l'opération d'addition dans un accumulateur peut être réalisée dans la même instruction élémentaire que la multiplication. C'est le cas par exemple lorsqu'on utilise un processeur de type ARM. L'ensemble de ces opérations, multiplication d'un nombre à q mots par un scalaire et addition du résultat au contenu d'une zone mémoire peut alors s'effectuer en q instructions élémentaires du processeur.
On multiplie ensuite le contenu du mot de poids faible de la mémoire Y par le nombre e défini plus haut, et on ne conserve que le mot de poids faible du résultat, multiplication mot-mot sans retenue. Ce mot de poids faible sera appelé m. D'une part m sera ajouté au mot de poids q de Y, avec stockage d'une éventuelle retenue dans le bit retenue de Y. D'autre part le produit de m par d, nombre à rd+l mots, sera soustrait à la mémoire Y. A la suite de ces deux opérations, le mot de poids faible de Y est nul. On décale alors le contenu de mots de Y d'un mot vers la droite, le bit de retenue étant recopié dans le mot de poids fort. Cette opération achève l'itération en cours.
Après les q itérations, la mémoire Y contient un nombre inférieur à 2N et dont le produit par R est congru modulo N au produit F.G . Si Y est supérieur ou égal à N, on lui soustrait N . La mémoire Y contient maintenant le résultat final de toutes ces opérations, à savoir le reste par N d'un nombre dont le produit par R est égal au produit F.G .
L'ensemble des opérations décrites ici constitue un opérateur qui prend comme arguments les deux nombres F et G et fournit comme résultat le reste par N d'un nombre dont le produit par R est égal au produit F.G .
Un des intérêts de l'imbrication de la multiplication avec le premier algorithme est l'économie de mémoire permise par cette méthode. En effet il suffit des q+1 mots, plus un bit, de la mémoire Y pour stocker les produits intermédiaires, au lieu des 2q mots nécessaires au stockage du produit F.G dans le cas où ce produit est calculé préalablement à l'application du premier algorithme.
Voyons maintenant comment la méthode développée ici peut être utilisée pour le calcul des exponentielles modulaires . Remarquons tout d'abord que le calcul d'une exponentiation Ap [mod N] est plus complexe que celui d'une simple multiplication. Un calcul direct de AAp = a.a.a a, avec p facteurs, représente p-1 multiplications modulo N ce qui, dès que p devient grand, devient très rapidement prohibitif en temps de calcul. Lorsque p atteint l'ordre de grandeur des valeurs habituellement utilisées dans les applications, nombres à plus de 100 chiffres -décimaux, le temps de calcul dépasse très significativement l'âge de l'univers, même si l'on faisait travailler en parallèle tous les ordinateurs de la planète.
Une méthode indirecte permet néanmoins de calculer AAp [mod N] en un temps acceptable. Le principe de cette méthode consiste à calculer, par des élévations au carré successive, multiplication d'un nombre par lui-même, modulo N, la liste des puissances de A , modulo N, dont l'exposant est une puissance de 2 , c'est-à-dire (A, A 2 [mod N] , AA4 [mod N] , AA8 [mod N] , A 16 [mod N] , A 2 [mod N] , AA64 [mod N] , et ainsi de suite ... ) . On examine alors le développement binaire de l'exposant p, c'est sous cette forme que p est stocké en machine. On retient dans la liste précédente les éléments qui correspondent à des bits à 1 dans ce développement et on les multiplie entre eux, toujours modulo N. Si l'exposant s'écrit sur r bits dont t bits à 1, il faut donc r-1 élévations au carré, suivies de t-1 multiplications pour calculer le résultat.
A titre d'exemple illustratif, prenons le cas de l'exposant 181 qui se décompose en 128+32+16+4+1 s'écrit donc en binaire 1011 0101 . Par 7 élévations au carré successives, on peut calculer la liste des puissances de A d'exposants successifs 2, 4, 8, 16, 32, 64 et 128 . En remarquant que le résultat recherché AA181 est égal au produit des 5 facteurs AA128 [mod N] , A 32 [mod N] , A 16 [mod N] , AA4 [mod N] et AA1 = A , on voit qu'il suffit de 4 multiplications modulo N pour obtenir le résultat final recherché. Soit au total 11 multiplications modulo N au lieu de 180. Le gain est encore considérablement plus spectaculaire lorsque l'exposant est un très grand nombre .
Les algorithmes habituellement implémentés dans les applications informatiques s'inspirent de cette méthode. Leur principe est du domaine public et est décrit par exemple dans « Applied Cryptography » de Bruce Schneier (John iley 1994) ou dans « The Art of Computer Programming Volume 2 Semi numerical Algorithms» de D. Knuth (Addison Wesley, 1981 pour la seconde édition) .
D'une façon générale, une exponentiation en arithmétique modulo N peut se ramener à approximativement 3/2 fois r multiplications modulo N, où r est le nombre de bits nécessaires à la représentation binaire de l'exposant p de l'exponentielle, soit 768 ou 1536 multiplications modulo N si on travaille avec des exposants à 512 ou 1024 bits. Chacune de ces multiplications modulo N se ramène à une multiplication en grands nombres, temps de calcul proportionnel au carré du nombre de mots nécessaires pour représenter N dans le processeur de calcul, suivi d'une réduction modulo N. Si on effectue cette réduction de façon classique, il faut effectuer une division en grands nombres, ce qui, en temps de calcul, est équivalent à plusieurs multiplications en grands nombres.
Les méthodes objet de la présente invention permettent d'accélérer significativement les calculs d'exponentiation modulaire.
Le nombre A le nombre destiné à être élevé à la puissance p modulo N est stocké sur q mots. L'exposant p est simplement stocké en mémoire par son développement binaire, en f utilisant autant de bits ou de mots que nécessaire. L'algorithme mis en œuvre, on lira successivement les bits de ce développement .
Dans une étape préliminaire, on calcule et on stocke en mémoire un nombre F, stocké sur q mots et égal au reste par N du produit A.R, avec les notations utilisées précédemment. Ce calcul est effectué en utilisant la même méthode que dans le cas de la multiplication.
On se réserve une zone mémoire de 2q mots, notée Y, et destinée à recueillir les résultats partiels des calculs. Dans un premier temps, cette zone mémoire est initialisée au nombre F calculé ci-dessus. Ce nombre F, stocké sur q mots, servira à initialiser les q mots de poids faible de Y, les q mots de poids forts étant initialisés à zéro.
On sélectionnera alors, bit à bit, les bits de l'exposant p, en commençant par les bits de poids fort, et pour chaque bit on effectuera la séquence d'opérations suivantes.
Au début de cette séquence d'opérations, les q mots de poids forts de la zone mémoire Y contiennent la valeur 0. Cette mémoire représente donc un nombre stocké sur q mots, donc un nombre inférieur à R.
On calcule alors le carré de ce nombre, carré dont le stockage nécessite maintenant 2q mots. Soit V0 le résultat de ce calcul. On applique à V0 l'algorithme décrit plus haut sous le nom de premier algorithme, qui a pour effet de calculer un nombre U0 congru modulo N à V0 et dont les q mots de poids faibles sont nuls. On stocke alors dans les q mots de poids faibles de la mémoire Y les q mots de poids fort de U0 et on met à zéro les mots de poids fort de Y. Le contenu de Y est donc obtenu en échangeant les q mots de poids fort et les q mots de poids faibles de U0.
A ce stade, comme au début de la séquence, les q mots de poids forts de la zone mémoire Y contiennent donc la valeur 0.
Lorsque le bit de p sélectionné au début de la séquence est égal à 0, on réitère la séquence en sélectionnant le bit suivant dans p, dans le sens des poids décroissants.
Lorsque le bit est de p sélectionné au début de la séquence est égal à 1, on effectue en outre les opérations suivantes .
On multiplie le contenu de la mémoire Y, donc les' q mots de poids faible, car les autres sont nuls, par le nombre F. Soit V_ le résultat de ce calcul. Le stockage de V. nécessite maintenant 2q mots. La suite des opérations est similaire à ce qui est fait plus haut. On applique à V. l'algorithme décrit plus haut sous le nom de premier algorithme, qui a pour effet de calculer un nombre U. congru modulo N à V_ et dont les q mots de poids faibles sont nuls. On stocke alors dans les q mots de poids faibles de la mémoire Y les q mots de poids fort de U. et on met à zéro les mots de poids fort de Y,. Le contenu de Y est donc obtenu en échangeant les q mots de poids fort et les q mots de poids faibles de U..
A ce stade, comme au début de la séquence, les q mots de poids forts de la zone mémoire Y contiennent donc la valeur 0, et on réitère la séquence depuis le début après avoir sélectionné le bit suivant dans p, dans le sens des poids décroissants .
A la fin de ces opérations, après avoir épuisé tous les bits de l'exposant p, la mémoire Y contient un nombre qui est congru modulo N au produit de R par A puissance p. On applique à nouveau le premier algorithme en prenant comme argument le contenu de la mémoire Y pour obtenir un nombre S congru modulo N à cet argument et dont les q mots de poids faibles sont nuls. Soit D le nombre à q mots formé des mots de poids forts de S. Ce nombre est positif, est inférieur à 2N et est congru modulo N au nombre A puissance p. S'il est inférieur à N, c'est nombre qu'on souhaitait calculer, reste de la division par N du nombre A puissance p. S'il est supérieur ou égal à N, il suffit de lui retrancher N pour trouver le résultat souhaité.
Le procédé de calcul de l'exponentiation modulaire décrit ci-dessus, applique à plusieurs reprises une suite d'opérations consistant à effectuer tout d'abord une multiplication entre deux grands nombres, élévation au carré de Y, ou multiplication de Y par F, puis à appliquer au résultat de cette multiplication le premier algorithme décrit précédemment et consistant à remplacer ledit résultat par un nombre qui lui est congru modulo N et dont les q mots de poids faibles sont nuls, et finalement à extraire le nombre formé des q mots de poids forts du résultat du premier algorithme.
De même que nous avons pu imbriquer ces opérations dans le cas de la multiplication, nous pouvons aussi les imbriquer ici, et remplacer la suite d'opérations ci-dessus par l'application de l'opérateur décrit précédemment, qui étant donné deux arguments, selon le cas Y et le même Y ou Y et F, fournit comme résultat le reste par N d'un nombre dont le produit par R est égal au produit des arguments de l'opérateur.
Cela a pour conséquence entre autres une économie de mémoire, car la mémoire de travail Y ne nécessite plus alors que q+1 bits (plus un bit de parité) au lieu des 2q bits nécessaires si on n'imbrique pas les opérations.

Claims

REVENDICATIONS
1. Procédé permettant d'accélérer le calcul de multiplications en arithmétique modulo N, N désignant un entier comportant notamment plusieurs centaines de chiffres décimaux ; lesdites multiplications intervenant notamment dans des protocoles de cryptographie mis en œuvre à l'aide de ressources informatiques ; ledit procédé étant plus particulièrement conçu pour économiser lesdites ressources informatiques, telles que puissance de calcul et/ou espace mémoire ; ledit procédé comprenant les étapes préliminaires suivantes :
- l'étape de stocker ledit nombre N sur q mots,
- l'étape de soustraire ledit nombre N d'une puissance de 2 supérieure à N, notée R, pour obtenir un nombre, noté d ; ledit nombre R étant la première puissance de 2 ne pouvant pas être stockée sur q mots ; ledit procédé comprenant en outre l'étape préliminaire suivante :
- l'étape de stocker ledit nombre d dans une mémoire de ladite ressource informatique ; ledit procédé comportant un premier opérateur prenant en entrée deux nombres E., E2 stockés chacun sur q mots et fournissant en sortie un nombre W tel que le produit par R dudit nombre W soit congru modulo N au produit desdites entrées E., et E2 les dites entrées E., E2 étant ci-après dénommées les entrées dudit premier opérateur, et le nombre W étant ci-après dénommé le résultat dudit premier opérateur ; ledit procédé comportant un premier algorithme ayant pour objet de remplacer un argument, stocké sur 2q mots, par un résultat qui est congru modulo N audit argument et dont les q mots de poids faibles sont nuls ; ledit argument étant ci-après dénommé l'argument dudit premier algorithme ; ledit résultat étant ci-après dénommé le résultat dudit premier algorithme ,- de sorte que le résultat dudit premier algorithme est un multiple de R ; ledit procédé comprenant en outre les étapes principales suivantes pour multiplier entre eux modulo N deux nombres A et B,
- l' étape de stocker en mémoire les restes modulo N du produit par R des nombres A et B, lesdits restes stockés en mémoire étant respectivement dénommés le nombre F et le nombre G,
- l'étape de mettre en œuvre le premier opérateur, les entrées El et E2 prenant respectivement comme valeur les nombres F et G,
- l'étape de stocker le résultat W du premier opérateur sous la forme d'un nombre à 2q mots, ci-après dénommé H ; de sorte que ce nombre H est égal au reste modulo N du produit des nombres A, B et R ; ledit procédé comprenant en outre l'étape principale suivante :
- l'étape de mettre en œuvre ledit premier algorithme avec comme argument ledit nombre H, stocké sur 2q mots, pour fournir un nombre V congru modulo N audit nombre H et dont les q mots de poids faibles sont nuls ;
- l'étape de lire le nombre à q mots C constitué par les q mots de poids fort dudit nombre V ; ledit nombre C ou le nombre C-N étant égal au reste modulo N du produit des nombres A et B.
2. Procédé selon la revendication 1 ; ledit premier algorithme consistant à itérer q fois une opération ayant pour effet de remplacer le nombre obtenu au terme de l'itération précédente par un nombre qui lui est congru modulo N et tel que le nombre obtenu au terme de la ième itération ait tous ses mots de poids les plus faibles nuls jusqu'au ième ; ladite ième opération comprenant les quatre étapes suivantes : (a) on multiplie le ième mot, dans l'ordre des poids croissants, du nombre issu de l'itération précédente, ou, lors de la première itération, le mot de poids faible de l'argument dudit premier algorithme, par une constante prédéfinie de manière à obtenir un résultat dont on ne conserve que le mot de poids faible,
(b) on obtient au terme de l'étape précédente (a) un résultat, dénommé x, qu'on multiplie par ledit nombre d,
(c) on décale le résultat x de la première étape (a) de q+i crans vers les poids forts et on ajoute le nombre ainsi décalé au nombre issu de l'itération précédente ou lors de la première itération à l'argument dudit premier algorithme,
(d) on obtient au terme de l'étape (b) un résultat, dénommé y, qu'on décale de i crans dans le sens des poids forts puis qu'on soustrait au nombre issu du résultat de l'addition effectuée à l'étape (c) précédente ; le résultat de cette soustraction constitue le résultat de l'itération en cours ; de sorte qu'on obtient au terme desdites quatre étapes de la ième itération un nombre qui est congru modulo N audit argument dudit premier algorithme et dont tous les mots de poids les plus faibles sont nuls jusqu'au ième.
3. Procédé selon la revendication 1 ou 2 ; ledit premier opérateur comprend les étapes suivantes : l'étape de multiplier entre elles les entrées El et E2 dudit premier opérateur, ayant pris pour valeurs les nombres F et G, le résultat de cette multiplication étant un nombre T stocké sur 2q mots,
- l'étape de mettre en œuvre ledit premier algorithme avec comme argument ledit nombre T pour fournir comme résultat un nombre dénommé U, stocké sur 2q mots,
- l'étape de lire le nombre à q mots constitué par les q mots de poids fort dudit nombre U, ledit nombre constituant le résultat W dudit premier opérateur ; de sorte que les q mots de poids faible de U sont nuls ; de sorte que ledit résultat W multiplié par R est congru modulo N au produit desdites entrées El et E2 ;
4. Procédé selon- la revendication 1 ou 2 ; ledit premier opérateur comprenant les étapes préliminaires suivantes :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El dudit premier opérateur, ladite entrée El ayant pris pour valeur le nombre F ; ledit premier opérateur ' comprenant l'étape principale consistant à itérer les sous-étapes suivantes :
- (a) la sous-étape de multiplier ledit mot ainsi sélectionné par l'entrée E2 ayant pris pour valeur le nombre G, le résultat de cette multiplication étant un nombre stocké sur q+1 mots et étant dénommé P,
- (b) la sous-étape d'additionner ledit nombre P, calculé à l'étape précédente, au contenu de ladite mémoire Z, ledit bit de retenue étant positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans ladite mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de ladite mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre N, le résultat de cette multiplication étant un nombre dénommé Q stocké sur q+1 mots,
- (f) la sous-étape d'additionner ledit nombre Q, calculé à l'étape (e) précédente, au contenu de la mémoire Z,
- (g) la sous-étape de stocker dans ladite mémoire Z le résultat de l'addition effectuée dans l'étape précédente ; de sorte que le mot de poids faible de ladite mémoire Z contient la valeur zéro ;
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de ladite mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de ladite mémoire Z le contenu dudit bit de retenue,
- (j) la sous-étape de mettre à zéro ledit bit de retenue ; ledit premier opérateur comprenant en outre l'étape principale suivante :
- l'étape de lire le mot suivant de l'entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j) , autant de fois que nécessaire ; de sorte qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, ladite mémoire Z contient uri nombre, compris entre zéro et 2N, dont le produit par R est égal, modulo N, au produit des entrées El et E2 ; ledit premier opérateur comprenant en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de ladite mémoire Z,
- l'étape, lorsque ce contenu est supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction étant stocké dans la mémoire Z ; le résultat W dudit premier opérateur étant égal au contenu de la mémoire Z.
5. Procédé selon la revendication 1 ou 2 ; ledit premier opérateur comprenant l'étape préliminaire suivante :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue, - l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El dudit premier opérateur, ladite entrée El ayant pris pour valeur le nombre F ; ledit premier opérateur comprenant l'étape principale consistant à itérer les sous-étapes suivantes :
- (a) la sous-étape de multiplier ledit mot ainsi sélectionné par ladite entrée E2 dudit premier opérateur, ladite entrée E2 ayant pris pour valeur le nombre G, le résultat de cette multiplication étant un nombre stocké sur q+1 mots et étant dénommé P,
- (b) la sous-étape d'additionner ledit nombre P, calculé à l'étape précédente, au contenu de ladite mémoire Z, ledit bit de retenue étant positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans ladite mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de ladite mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) les sous-étapes :
• d'additionner le résultat m de l'étape précédente au contenu du mot de poids fort de ladite mémoire Z,
• de stocker le résultat de cette addition dans le même mot de poids fort,
• en cas de dépassement de capacité de cette addition, de mettre à 1 ledit bit de retenue,
- (f) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre d, le résultat de cette multiplication étant un nombre dénommé Q,
- (g) la sous-étape de soustraire ledit nombre Q, calculé à l'étape précédente, au contenu de ladite mémoire Z, puis de stocker dans ladite mémoire Z le résultat de cette soustraction ; de sorte que le mot de poids faible de ladite mémoire Z contient la valeur zéro ;
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de ladite mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de ladite mémoire Z le contenu dudit bit de retenue,
- (j) la sous-étape de mettre à zéro ledit bit de retenue ; ledit premier opérateur comprenant en outre l'étape principale suivante :
- l'étape de lire le mot suivant de ladite entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j) autant de fois que nécessaire ; de sorte qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, ladite mémoire Z contient un nombre H dont le produit par R est égal, modulo N, au produit des nombres El et E2 ; ledit premier opérateur comprenant en outre les deux 'étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de ladite mémoire Z,
- l'étape, lorsque ce contenu supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction étant stocké dans la mémoire Z ; le résultat W dudit premier opérateur étant égal au contenu de la mémoire Z ;
6. Procédé selon l'une quelconque des revendications 1 à 5 ; ledit procédé étant tel que pour calculer le reste modulo N, dénommé le nombre F, respectivement dénommé le nombre G , du produit par R d'un nombre donné A, respectivement B :
- on multiplie le nombre A, respectivement le nombre B, par le reste modulo N du carré de R, pour obtenir un nombre dénommé Tft, respectivement TB, stocké sur 2q mots, - on applique ledit premier algorithme avec comme argument ledit nombre TA, respectivement ledit nombre TB, pour obtenir comme résultat un nombre VA, respectivement un nombre VB, qui lui est congru modulo N et dont les q mots de poids faibles sont nuls ; ledit nombre F, respectivement ledit nombre G, est alors le nombre à q mots formés des q mots de poids forts dudit nombre VA, respectivement dudit nombre VB.
7. Procédé permettant d' accélérer le calcul d'exponentiations en arithmétique modulo N, N désignant un entier comportant notamment plusieurs centaines de chiffres décimaux ; lesdites exponentiations intervenant notamment dans des protocoles de cryptographie mis en œuvre à l'aide de ressources informatiques ; ledit procédé ayant pour objet d'élever un nombre A, ci après dénommé la base, à une puissance p modulo N ; p étant un nombre entier supérieur ou égal à 2, ci- après dénommé l' exposant, et étant représenté sous forme binaire ; ledit procédé étant plus particulièrement conçu pour économiser lesdites ressources informatiques, telles que puissance de calcul et/ou espace mémoire ,- ledit, procédé comprenant les étapes préliminaires suivantes :
- l'étape de stocker ledit nombre N sur q mots,
- l'étape de soustraire ledit nombre N d'une puissance de 2 supérieure à N, notée R, pour obtenir un nombre, noté d ; ledit nombre R étant la première puissance de 2 ne pouvant pas être stockée sur q mots ;
- l'étape de stocker ledit nombre d dans une mémoire de ladite ressource informatique ; ledit procédé comprenant en outre les étapes préliminaires suivantes :
- l'étape de stocker en mémoire le reste modulo N du produit par R de la base A, ledit reste stocké en mémoire étant dénommé le nombre F, - l'étape d' initialiser une zone mémoire de 2q mots, ci-après dénommée la zone mémoire Y, avec une copie nombre F ; ledit procédé comportant un premier algorithme ayant pour objet de remplacer un argument, stocké sur 2q mots, par un résultat qui est congru modulo N audit argument et dont les q mots de poids faibles sont nuls ; ledit argument étant ci-après dénommé l'argument dudit premier algorithme ; ledit résultat étant ci-après dénommé le résultat dudit premier algorithme ; de sorte que le résultat dudit premier algorithme est un multiple de R ; ledit procédé comprenant les étapes principales suivantes :
- l'étape de sélectionner, en commençant par les bits de poids forts, le premier bit suivant le premier bit non nul de l'exposant p,
- l'étape consistant à mettre en œuvre, selon le cas, les opérations ci-après définies : dans le cas où le bit sélectionné est égal à zéro :
• (a) on calcule le carré du contenu de la zone mémoire Y ;
• (b) on stocke dans la zone mémoire Y, le résultat du calcul précédent ;
• (c) on met en œuvre ledit premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir comme résultat un nombre U0 congru modulo N à cet argument et dont les q mots de poids faibles sont nuls ;
• (d) on stocke dans les q mots de poids faible de la zone mémoire Y, les q mots de poids forts du résultat U0 du calcul précédent ;
• (e) on met à zéro le contenu des q mots de poids forts de la mémoire Y ; dans le cas où le bit sélectionné est égal à un, on réalise les mêmes opérations (a) à (e) que dans le cas où ledit exposant sélectionné est égal à zéro et en outre : • (f) on multiplie le contenu de la mémoire Y, au terme de l'opération (e) , par le nombre F ;
• (g) on stocke dans la zone mémoire Y, le résultat du calcul précédent ;
• (h) on met en œuvre ledit premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir comme résultat un nombre U. congru modulo N à cet argument et dont les q mots de poids faibles sont nuls ;
• (i) on stocke dans les q mots de poids faible de la zone mémoire Y, les q mots de poids forts du résultat U. du calcul précédent ;
• (j) on met à zéro le contenu des q mots de poids forts de la mémoire Y ; ledit procédé comprenant en outre l'étape principale suivante :
- l'étape de lire le bit suivant de l'exposant p, dans l'ordre des poids décroissants, et
• lorsque ledit bit est égal à zéro on itère les opérations (a) à (e) ;
• lorsque ledit bit est égal à un on itère les opérations (a) à (j) ; lesdites itérations étant effectuées autant de fois que nécessaire ; de sorte qu'au terme du processus, après avoir sélectionné tous les bits de l'exposant, la mémoire Y contient un nombre qui est congru modulo N au produit du nombre R par le résultat de l'exponentiation A puissance p ; ledit procédé comprenant en outre l'étape de mettre en œuvre ledit premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir un nombre S congru modulo N à cet argument et dont les q mots de poids faibles sont nuls ; de sorte que les q mots de poids fort du nombre S représentent un nombre compris entre zéro et 2N et congru modulo N au résultat de l'exponentiation A puissance p ,- ledit procédé comprenant en outre les étapes finales suivantes :
- l'étape de lire le nombre à q mots D constitué par les q mots de poids fort dudit nombre S,
- l'étape de comparer ce nombre au nombre N
- l'étape, lorsque D est supérieur à N, de retrancher le nombre N du nombre D ; de sorte que le nombre D auquel on a éventuellement soustrait N est égal au résultat de l'exponentiation A puissance p modulo N qu'on souhaite calculer.
8. Procédé selon la revendication 7 ; ledit procédé comprenant les étapes préliminaires suivantes :
- l'étape de stocker en mémoire le reste modulo N du produit par R du nombre A, ledit reste stocké en mémoire étant dénommé F ;
- l'étape d' initialiser une zone mémoire de q mots, ci-après dénommée la zone mémoire Y, avec le nombre F ; ledit procédé comportant un premier opérateur prenant en entrée deux nombres El, E2 stockés chacun sur q mots et fournissant en sortie un nombre W, stocké sur q mots, tel que le produit par R dudit nombre W soit congru modulo N au produit desdites entrées El, et E2 les dites entrées El, E2 étant ci- après dénommées les entrées dudit premier opérateur, et le nombre W étant ci-après dénommé le résultat dudit premier opérateur ; ledit procédé comprenant les étapes principales suivantes :
- l'étape de sélectionner, en commençant par les bits de poids forts, le premier bit suivant le premier bit non nul de l'exposant p,
- l'étape consistant à mettre en œuvre, selon le cas, les opérations ci-après définies : dans le cas où le bit sélectionné est égal à zéro : (a) l'étape de mettre en œuvre ledit premier opérateur les deux entrées El et E2 dudit premier opérateur prenant toutes deux une valeur égale au contenu de la zone mémoire Y,
(b) l'étape de stocker le résultat W fourni par ledit premier opérateur dans la zone mémoire Y, dans le cas où le bit sélectionné est égal à un : on réalise les mêmes opérations (a) et (b) que dans le cas où ledit exposant sélectionné est égal à zéro et en outre les deux étapes suivantes :
(c) l'étape de mettre en œuvre ledit premier opérateur les entrées El et E2 dudit opérateur prenant l'une pour valeur le nombre F et l'autre une valeur égale au contenu de la zone mémoire Y,
(d) l'étape de stocker le résultat W fourni par ledit premier opérateur dans la zone mémoire Y, ledit procédé comprenant en outre l'étape principale suivante :
- l'étape de lire le bit suivant de l'exposant p, dans l'ordre des poids décroissants, et
• lorsque ledit bit est égal à zéro on itère les opérations (a) à (b) ;
• lorsque ledit bit est égal à un on itère les opérations (a) à (d) ; lesdites itérations étant effectuées autant de fois que nécessaire ; de sorte qu'au terme du processus, après avoir sélectionné tous les bits de l'exposant, la mémoire Y contient un nombre qui est congru modulo N au produit du nombre R par le résultat de l'exponentiation A puissance p ; ledit procédé comprenant en outre l'étape finale de mettre en œuvre ledit premier algorithme avec comme argument le contenu de la mémoire Y pour obtenir un nombre S congru modulo N à cet argument et dont les q mots de poids faibles sont nuls ; de sorte que les q mots de poids fort du nombre S représentent un nombre congru modulo N au résultat de l'exponentiation A puissance p ; ledit procédé comprenant en outre les étapes finales suivantes :
- l'étape de lire le nombre à q mots D constitué par les q mots de poids fort dudit nombre S,
- l'étape de comparer ce nombre au nombre N
- l'étape, lorsque D est supérieur à N, de retrancher le nombre N du nombre D ; de sorte que le nombre D auquel on a éventuellement soustrait N est égal au résultat de l'exponentiation A puissance p modulo N qu'on souhaite calculer.
9. Procédé selon la revendication 7 ou 8 ; ledit premier algorithme consistant à itérer q fois une opération ayant pour effet de remplacer le nombre obtenu au terme de l'itération précédente par un nombre qui lui est congru modulo N et tel que le nombre obtenu au terme de la ième itération ait tous ses mots de poids les plus faibles nuls jusqu'au ième ; ladite ième opération comprenant les quatre étapes suivantes :
(a) on multiplie le ième mot, dans l'ordre des poids croissants, du nombre issu de l'itération précédente, ou lors de la première itération le mot de poids faible de l'argument dudit premier algorithme, par une constante prédéfinie de manière à obtenir un résultat dont on ne conserve que le mot de poids faible,
(b) on obtient au terme de l'étape précédente (a) un résultat, dénommé x, qu'on multiplie par ledit nombre d,
(c) on décale le résultat x de la première étape (a) de q+i crans vers les poids forts et on ajoute le nombre ainsi décalé au nombre issu de l'itération précédente ou lors de la première itération à l'argument dudit premier algorithme,
(d) on obtient au terme de l'étape (b) un résultat, dénommé y, qu'on décale de i crans dans le sens des poids forts puis qu'on soustrait au nombre issu du résultat de l'addition effectuée à l'étape (c) précédente, le résultat de cette soustraction constitue le résultat de l'itération en cours, de sorte qu'on obtient au terme desdites quatre étapes de la ième itération un nombre qui est congru modulo N audit argument" dudit premier algorithme et dont tous les mots de poids les plus faibles sont nuls jusqu'au ième.
10. Procédé selon la revendication 8 ou 9 ; ledit premier opérateur comprend les étapes suivantes :
- l'étape de multiplier entre elles les entrées El et E2 dudit premier opérateur pour obtenir un nombre T stocké sur 2q mots,
- l'étape de mettre en œuvre ledit premier algorithme avec comme argument ledit nombre T pour fournir comme résultat un nombre dénommé U, stocké sur 2q mots,
- l'étape de lire le nombre à q mots constitué par les q mots de poids fort dudit nombre U, ledit nombre à q mots constituant le résultat W dudit premier opérateur ; de sorte que les q mots de poids faible de U sont nuls ; de sorte que ladite sortie W multipliée par R est congrue modulo N au produit desdites entrées El et E2.
11. Procédé la revendication 8 ou 9 ; ledit premier opérateur comprenant les 'étapes préliminaires suivantes :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El dudit premier opérateur, ledit premier opérateur comprenant l'étape principale consistant à itérer les sous-étapes suivantes : - (a) la sous-étape de multiplier ledit mot ainsi sélectionné par l'entrée E2, le résultat de cette multiplication étant un nombre stocké sur q+1 mots et étant dénommé P,
- (b) la sous-étape d'additionner ledit nombre P, calculé à l'étape précédente, au contenu de ladite mémoire Z, ledit bit de retenue étant positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans ladite mémoire Z le résultat de l'addition effectuée dans l'étape précédente,
- (d) la sous-étape de multiplier le contenu du mot de poids faible de ladite mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre N, le résultat de cette multiplication étant un nombre dénommé Q stocké sur q+1 mots,
- (f) la sous-étape d'additionner ledit nombre Q, calculé à l'étape (e) précédente, au contenu de la mémoire Z,
- (g) la sous-étape de stocker dans ladite mémoire Z le résultat de l'addition effectuée dans l'étape précédente ,- de sorte que le mot de poids faible de ladite mémoire Z contient la valeur zéro ;
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de ladite mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de ladite mémoire Z le contenu dudit bit de retenue,
- (j) la sous-étape de mettre à zéro ledit bit de retenue ; ledit premier opérateur comprenant en outre l'étape principale suivante :
- l'étape de lire le mot suivant de l'entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j), autant de fois que nécessaire ; de sorte qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, ladite mémoire Z contient un nombre, compris entre zéro et 2N, dont le produit par R est égal, modulo N, au produit des nombres El et E2 ; ledit premier opérateur comprenant en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de ladite mémoire Z,
- l'étape, lorsque ce contenu est supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction étant stocké dans la mémoire Z ; le résultat W dudit premier opérateur étant égal au contenu de la mémoire Z .
12. Procédé selon la revendication 8 ou 9 ; ledit premier opérateur' comprenant l'étape préliminaire suivante :
- l'étape d' initialiser à zéro une zone mémoire Z formée de q+1 mots et d'un bit de retenue,
- l'étape de sélectionner, en commençant par les mots de poids faibles, le premier mot de l'entrée El dudit premier opérateur ; ledit premier opérateur comprenant l'étape principale consistant à itérer les sous-étapes suivantes :
- (a) la sous-étape de multiplier ledit mot ainsi sélectionné par ladite entrée E2 dudit premier opérateur, le résultat de cette multiplication étant un nombre stocké sur q+1 mots et étant dénommé P,
- (b) la sous-étape d'additionner ledit nombre P, calculé à l'étape précédente, au contenu de ladite mémoire Z, ledit bit de retenue étant positionné à 1 ou à 0 selon qu' il y a ou non dépassement de capacité,
- (c) la sous-étape de stocker dans ladite mémoire Z le résultat de l'addition effectuée dans l'étape précédente, - (d) la sous-étape de multiplier le contenu du mot de poids faible de ladite mémoire Z par une constante prédéfinie, de manière à obtenir un résultat dont on ne conservera que le mot de poids faible, dénommé m,
- (e) les sous-étapes :
• d'additionner le résultat m de l'étape précédente au contenu du mot de poids fort de ladite mémoire Z,
• de stocker le résultat de cette addition dans le même mot de poids fort,
• en cas de dépassement de capacité de cette addition, de mettre à 1 ledit bit de retenue,
- (f) la sous-étape de multiplier le résultat m de l'étape précédente par le nombre d, le résultat de cette multiplication étant un nombre dénommé Q,
- (g) la sous-étape de soustraire ledit nombre Q, calculé à l'étape précédente, au contenu de ladite mémoire Z, puis de stocker dans ladite mémoire Z le résultat de cette soustraction ; de sorte que le mot de poids faible de ladite mémoire Z contient la valeur zéro ;
- (h) la sous-étape de décaler d'un mot dans la direction des mots de poids faibles le contenu des mots de ladite mémoire Z,
- (i) la sous-étape de stocker dans le mot de poids fort de ladite mémoire Z le contenu dudit bit de retenue,
- (j) la sous-étape de mettre à zéro ledit bit de retenue ; ledit premier opérateur comprenant en outre l' étape principale suivante :
- l'étape de lire le mot suivant de ladite entrée El, dans le sens des poids croissants et de réitérer les sous étapes précédentes (a) à (j ) autant de fois que nécessaire ,- de sorte qu'au terme du processus, après avoir sélectionné, dans l'ordre des poids croissants, tous les mots constituant l'entrée El, ladite mémoire Z contient un nombre H dont le produit par R est égal, modulo N, au produit des nombres El et E2 ; ledit premier opérateur comprenant en outre les deux étapes finales suivantes :
- l'étape de comparer au nombre N le contenu de ladite mémoire Z,
- l'étape, lorsque ce contenu supérieur à N, de lui soustraire le nombre N, le résultat de la soustraction étant stocké dans la mémoire Z ; le résultat W dudit premier opérateur étant égal au contenu de la mémoire Z.
13. Procédé selon l'une quelconque des revendications 7 à 12 ; ledit procédé étant tel que pour calculer le reste modulo N du produit par R de la base A, dénommé le nombre F :
- on multiplie le nombre A par le reste modulo N du carré de R, pour obtenir un nombre dénommé T, stocké sur 2q mots,
- on applique ledit premier algorithme avec comme argument ledit nombre T, pour obtenir comme résultat un nombre V, qui lui est congru modulo N et dont les q mots de poids faibles sont nuls ; ledit nombre F est alors le nombre à q mots formés des q mots de poids forts -dudit nombre V.
PCT/FR2003/050022 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire Ceased WO2004015559A2 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
EP03755658A EP1532519A2 (fr) 2002-08-05 2003-07-29 Calcul cryptographique suivant la methode de montgomery
CA002494769A CA2494769A1 (fr) 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire
AU2003273500A AU2003273500A1 (en) 2002-08-05 2003-07-29 Method for accelerating calculations in modular arithmetic

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0209942A FR2843211B1 (fr) 2002-08-05 2002-08-05 Procede pour accelerer des calculs en arithmetique modulaire
FR02/09942 2002-08-05

Publications (2)

Publication Number Publication Date
WO2004015559A2 true WO2004015559A2 (fr) 2004-02-19
WO2004015559A3 WO2004015559A3 (fr) 2004-05-13

Family

ID=30129691

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2003/050022 Ceased WO2004015559A2 (fr) 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire

Country Status (5)

Country Link
EP (1) EP1532519A2 (fr)
AU (1) AU2003273500A1 (fr)
CA (1) CA2494769A1 (fr)
FR (1) FR2843211B1 (fr)
WO (1) WO2004015559A2 (fr)

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0720778A (ja) * 1993-07-02 1995-01-24 Fujitsu Ltd 剰余計算装置、テーブル作成装置および乗算剰余計算装置
FR2775368B1 (fr) * 1998-02-26 2000-04-14 Sgs Thomson Microelectronics Coprocesseur d'arithmetique modulaire permettant de realiser des operations non modulaires rapidement

Also Published As

Publication number Publication date
AU2003273500A1 (en) 2004-02-25
EP1532519A2 (fr) 2005-05-25
WO2004015559A3 (fr) 2004-05-13
FR2843211A1 (fr) 2004-02-06
FR2843211B1 (fr) 2005-05-20
CA2494769A1 (fr) 2004-02-19

Similar Documents

Publication Publication Date Title
EP0443679B1 (fr) Procédé de calcul d&#39;une opération du type A.X modulo N, dans un procédé de codage selon une méthode de type RSA
EP0853275B1 (fr) Coprocesseur comprenant deux circuits de multiplication opérant en parallèle
EP1368747B1 (fr) Procede et dispositif pour reduire le temps de calcul d&#39;un produit, d&#39;une multiplication et d&#39;une exponentiation modulaire selon la methode de montgomery
EP0712072A1 (fr) Procédé de mise en oeuvre de réduction modulaire selon la méthode de Montgomery
EP0314559A1 (fr) Circuit de calcul utilisant une arithmétique résiduelle
WO2007074149A1 (fr) Procédé cryptographique comprenant une exponentiation modulaire sécurisée contre les attaques à canaux cachés, cryptoprocesseur pour la mise en oeuvre du procédé et carte à puce associée
EP0795241B1 (fr) Procede de cryptographie a cle publique base sur le logarithme discret
FR2849512A1 (fr) Multiplieur modulaire de montgomery et procede de multiplication correspondant
EP1291763A1 (fr) Procédé de brouillage d&#39;un calcul à quantité secrète
WO2020012104A1 (fr) Circuit de génération de facteurs de rotation pour processeur ntt
EP1493078B1 (fr) Procédé cryptographique protégé contre les attaques de type à canal caché
CA2257907A1 (fr) Procede de cryptographie a cle publique
EP0939363B1 (fr) Procédé de mise en oeuvre d&#39;une multiplication modulaire selon la méthode de Montgoméry
EP3306465B1 (fr) Procédé de traitement cryptographique comprenant une multiplication d&#39;un point d&#39;une courbe elliptique par un scalaire
EP0785503A1 (fr) Procédé de production d&#39;un paramètre de correction d&#39;erreur associé à la mise en oeuvre d&#39;opérations modulaires selon la méthode de Montgomery
EP1532519A2 (fr) Calcul cryptographique suivant la methode de montgomery
EP0947913B1 (fr) Procédé de réalisation amélioré d&#39;une division entière
CA2359198C (fr) Unite de calcul pour l&#39;execution d&#39;un protocole cryptographique
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
FR2734679A1 (fr) Procede de cryptographie a cle publique base sur le logarithme discret
EP3451316A1 (fr) Dispositif de réduction modulaire
FR2842051A1 (fr) Procede de cryptographie incluant le calcul d&#39;une multiplication modulaire au sens de montgomery et entite electronique correspondante
WO2006134306A1 (fr) Protection d&#39;un calcul d&#39;exponentiation modulaire effectue par un circuit integre
FR3153166A3 (fr) Procédé de multiplication sécurisée entre un polynôme creux et un polynôme dense dans un algorithme cryptographique, dispositif électronique et programme d’ordinateur associés.
Covanov Multiplication algorithms: bilinear complexity and fast asymptotic methods

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NI NO NZ OM PH PL PT RO RU SC SD SE SG SK SL TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2003755658

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2494769

Country of ref document: CA

WWP Wipo information: published in national office

Ref document number: 2003755658

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP