Modular multiplication device and method

Abstract

There is provided a modular multiplication device for performing a multiplication of a first multiplicand and a second multiplicand modulo a given modulus, each of the multiplicand comprising a given number of digits, each digit having a given word size. The modular multiplication device comprises: a multiplier for multiplying at least one digit of the first multiplicand with the second multiplicand to produce a multiplier output; a modular reduction unit configured to reduce a quantity derived from the multiplier output by the product of an extended modulus and an integer coefficient, the extended modulus being the product of the given modulus with an extension parameter, which provides a reduction output, the reduction output being a positive integer strictly smaller than the extended modulus, wherein the modular multiplication device further comprises a selection unit configured to select the extension parameter such that the time taken for the device to perform the multiplication is independent from the multiplicands.

Claims

1. A modular multiplication device for performing a multiplication of a first multiplicand and a second multiplicand modulo a given modulus, each of said multiplicands comprising a given number of digits, each digit having a given word size, said modular multiplication device comprising: a multiplier for multiplying at least one digit of the first multiplicand with said second multiplicand to produce a multiplier output; a modular reduction unit configured to reduce a quantity derived from said multiplier output by the product of an extended modulus and an integer coefficient, said extended modulus being the product of said given modulus with an extension parameter, which provides a reduction output, said reduction output being a positive integer strictly smaller than said extended modulus, wherein said modular multiplication device further comprises a selection unit configured to select said extension parameter such that the time taken for said device to perform said multiplication is independent from said multiplicands.

2. The modular multiplication device of claim 1, wherein said selection unit is configured to select said extension parameter as a function of the ratio between an integer constant and the double of said modulus.

3. The modular multiplication device of claim 2, wherein said selection unit is configured to select said extension parameter to be inferior to said ratio.

4. The modular multiplication device of claim 2, wherein said selection unit is configured to select said extension parameter in an interval strictly comprised between 1 and said ratio.

5. The modular multiplication device of claim 2, wherein said integer constant is a power of two raised to an exponent, said exponent being equal to the product of said word size by an integer, said integer constant representing the number of words used to represent the modulus added to one.

6. The modular multiplication device of claim 4, wherein the selection unit is configured to select said extension parameter in an interval strictly comprised between one and an upper threshold defined as two raised to the word size divided by two.

7. The modular multiplication device of claim 1, wherein said extension parameter is the largest prime smaller than the half the power of two raised to said word size.

8. The modular multiplication device of claim 1, wherein said multiplier is configured to iteratively multiply a set of digits of said first multiplicand comprising at least one digit with said second multiplicand, which provides an intermediate multiplier output, and said modular reduction unit iteratively reduces each intermediate multiplier output, which provides an intermediate reduction output, said modular multiplication device further comprising at least one adder for adding said intermediate reduction output.

9. The modular multiplication device of claim 8, wherein said selection unit is configured to update said extension parameter over said iterations.

10. The modular multiplication device of claim 8, wherein said selection unit is configured to select the same extension parameter over said iterations.

11. The modular multiplication device of claim 1, wherein said multiplier is configured to multiply said first multiplicand by said second multiplicand, which provides a main multiplier output, and said modular reduction unit being configured to reduce said main multiplier output.

12. A Montgomery multiplication engine, wherein said Montgomery multiplication engine comprises a modular multiplication device according to claim 1, the modular multiplication device comprising: a coefficient determination unit configured to determine said integer coefficient from said quantity derived from said multiplier output and said integer constant, said integer constant being superior to the modulus and being a power of two raised to the word size, which provides said integer coefficient; a division unit configured to divide said reduction output by the integer constant.

13. The Montgomery multiplication engine of claim 12, wherein said integer coefficient is positive.

14. A Barret multiplication engine, wherein said Barret multiplication engine comprises a modular multiplication device according to claim 1, said integer coefficient being negative.

15. A Quisquater multiplication engine, wherein said Quisquater comprises a modular multiplication device according to claim 1, said integer coefficient being negative.

16. A cryptosystem system for implementing a cryptographic algorithm in an electronic device, said cryptographic algorithm being based on the result of at least one modular multiplication between two multiplicands, wherein said cryptographic system comprises a modular multiplication device according to claim 1 to perform said at least one modular multiplication.

17. The cryptosystem system of claim 16, wherein the cryptographic algorithm is a Rivest, Shamir, and Adleman (RSA) algorithm, and wherein the cryptographic algorithm comprises a modular exponentiation unit for computing an exponent of a message, the RSA cryptographic algorithm being based on a private key d, a public key e and system parameters p, q where p and q are primes such that the public key e is prime to (p1) and (q1), the cryptographic system comprising an exponentiation unit for exponentiating the message to the power e modulo a modulus equal to pq, wherein said exponentiation unit iteratively perform said exponentiation of the message using said modular multiplication device.

18. A cryptosystem system according to claim 16, wherein the cryptographic algorithm is an Elliptic Curve Cryptography algorithm lying on a given elliptic curve, and said system comprises a scalar multiplication unit configured to receive two coordinates of a point of said elliptic curve defined in a coordinate system over a finite field and a key being an binary number to generate a result of a scalar multiplication between said binary number and said point of the elliptic curve, wherein said scalar multiplication unit comprises said modular multiplication device.

19. A method for performing a multiplication of a first multiplicand and a second multiplicand modulo a given modulus, each of said multiplicands comprising a given number of digits, each digit having a given word size, said method comprising: multiplying at least one digit of the first multiplicand with said second multiplicand to produce a multiplier output; reducing a quantity derived from said multiplier output by the product of an extended modulus and an integer coefficient, said extended modulus being the product of said given modulus with an extension parameter, which provides a reduction output, said reduction output being a positive integer strictly smaller than said extended modulus, wherein said method further comprises selecting said extension parameter such that the time taken for said device to perform said multiplication is independent from said multiplicands.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate various embodiments of the invention and, together with the general description of the invention given above, and the detailed description of the embodiments given below, serve to explain the embodiments of the invention.

(2) FIG. 1 represents a cryptographic system in accordance with certain embodiments of the invention.

(3) FIG. 2 is a block diagram representing the modular multiplication device according to certain embodiments.

(4) FIG. 3 is a flowchart depicting the modular multiplication method according to certain embodiments.

(5) FIG. 4 is a flowchart that depicts an embodiment of the multiplication method implemented in a Montgomery engine.

(6) FIG. 5 depicts a cryptographic system comprising an exponentiation unit according to one application of the invention.

(7) FIG. 6 is a flowchart depicting the modular exponentiation method according to certain embodiments.

(8) FIG. 7 is a flowchart depicting an Elliptic Curve Scalar multiplication method according to certain embodiments.

(9) It is noted that the drawings of the invention are not necessarily to scale. The drawings are merely schematic representations. The drawings are intended to depict only typical embodiments of the invention, and therefore should not be considered as limiting the scope of the invention.

DETAILED DESCRIPTION

(10) Embodiments of the invention provide improved modular multiplication methods and devices for determining the result of a modular multiplication of two multiplicands, each comprising a number of digits.

(11) Embodiments of the invention further provide a cryptographic system and method using the result of such modular multiplication method and device in cryptographic operations such that the protection of the cryptographic system and method is ensured against attacks which are conventionally based on the observation of the extra-reduction. Exemplary cryptographic operations include encryption, decryption operations, signature and authentication operations. The following description of certain embodiments will be made with reference to such as encryption and/or decryption operations for illustrative purpose only.

(12) Referring to FIG. 1, a cryptographic system 100 in accordance with certain embodiments of the invention is represented. The cryptographic system 100 comprises a modular multiplication device 10 configured to perform a modular multiplication of a first multiplicand x and a second multiplicand y modulo a given modulus N. Each multiplicand x and y comprises a given number of digits, each digit having a given word size w (for example w=8, 32 or 64 bits).

(13) The modular multiplication device 10 may be implemented in a hardware or software module and operates on a set of parameters to produce a modular multiplication result noted xy from the two inputs x and y.

(14) To initialize the modular multiplication device 10, the device may be loaded with a modulus N and a multiplication constant R.sub.ext.

(15) The cryptographic system 100 may include a processor for executing instructions. The processor may be a register-based processor comprising registers to store components of the value to be reduced, such as the modulus N and the multiplication constant R.sub.ext.

(16) A memory 14 may be used to store the results of the operations performed by the modular multiplication device 10.

(17) FIG. 2 is a block diagram representing the modular multiplication device according to certain embodiments.

(18) The modular multiplication device 10 comprises a multiplier 101 for multiplying of at least one digit of the first multiplicand with said second multiplicand to produce a multiplier output.

(19) The modular multiplication device 10 further comprises a modular reduction unit 102 configured to reduce the multiplier output modulo a given extended modulus Nr, the extended modulus being defined as the product of said given modulus N with an extension parameter r, which provides a reduction output, the reduction output being a positive integer strictly smaller than the extended modulus Nr.

(20) According to one aspect of the invention, the modular multiplication device 10 further comprises a selection unit 103 configure to select the extension parameter r such that the time taken for said device to perform said multiplication is independent from said multiplicands. The modular multiplication thus completes in deterministic timing and allows for non trivial computation check by reduction of the computation modulo r. Accordingly, the modular multiplication is executed in constant time without conditional reduction, thereby protecting the cryptographic system 100 from attacks which are based on such conditional reduction and ensuring fault injection resistance, while having almost no overhead in terms of computation.

(21) The modular multiplication device 10 may be allocated a memory space for storing words in the memory 14, the maximal size of said memory space being defined by an integer constant R.sub.ext (also referred to hereinafter as multiplication constant). The multiplication constant R.sub.ext thus represents the maximal number of words allocated to the modular multiplication. The memory space may be used to store data used to perform the modular multiplication operation, such as inputs (multiplicands), outputs (modular multiplication result) and intermediary values used to execute the modular multiplication operation.

(22) In certain embodiments, the selection unit 103 may be configured to select the extension parameter r as a function of a parameter

(23) $\frac{R_{\mathrm{ext}}}{2N}$
defined as the ratio between said multiplication constant R.sub.ext and the double of said modulus2N.

(24) In particular, the selection unit 103 may be configured to select the extension parameter r such that the extension parameter is strictly inferior to the parameter

(25) $\frac{R_{\mathrm{ext}}}{2N}$

(26) $r<\frac{R_{\mathrm{ext}}}{2N}$

(27) This allows for an operation of the modular multiplication device in deterministic time (i.e. without extra-reduction).

(28) In one embodiment, the selection unit 103 may be configured to select the extension parameter specifically in an interval strictly comprised between 1 and the ratio

(29) $\frac{R_{\mathrm{ext}}}{2N}$

(30) In a preferred embodiment, the multiplication constant R.sub.ext may be superior to N and a power of two raised to an exponent equal to the product of said word size w by an integer l representing the number of words used to represent the modulus N added to one:
R.sub.ext=2.sup.w(l+1)

(31) The extension parameter r may be accordingly selected in the interval

(32) $I=]1,\frac{2^{w\left(l+1\right)}}{2N}[.$

(33) By selecting the extension parameter r in the range l, this removes the need for an extra-reduction, thereby preventing attackers from extracting the secret key, even in the presence of countermeasures.

(34) Particularly, the selection unit 103 may be configured to select said extension parameter in an interval J strictly comprised between one and an upper threshold

(35) $\frac{2^w}{2}$
defined as the ratio between two raised to the word size 2.sup.w and 2:

(36) $J=]1,\frac{2^w}{2}[.$

(37) The following description of certain embodiments of the invention will be made mainly with reference to a multiplication constant R.sub.ext equal to 2.sup.w(l+1) and an extension parameter selected in the interval l for illustration purpose only.

(38) The extension parameter r may be prime to further increase the capacity of fault detection. In certain embodiments, the multiplier may be configured to iteratively multiply a set of digits of the first multiplicand x comprising at least one digit with the second multiplicand y, which provides an intermediate multiplier output, and said modular reduction unit 101 may be configured to iteratively reduce each intermediate multiplier output, which provides an intermediate reduction output. The modular multiplication device 10 may further comprise at least one adder 104 for adding the intermediate reduction outputs.

(39) Alternatively, the multiplier 101 may multiply the first multiplicand x with the second multiplicand y, which provides a main multiplier output, the modular reduction unit 102 then reducing the main multiplier output.

(40) The cryptographic system 100 may be for example an asymmetric cryptographic system which implements public key encryption by arithmetic operation using a multiple-length integer as a modulus N. For example, in RSA cryptographic systems, encryption and decryption are executed by power calculations in a remainder computation system using an odd composite number as a modulus. In elliptic curve encryption on a prime field F.sub.p, addition of points on an elliptic curve is implemented by an appropriate combination of addition, subtraction, multiplication, and division using an odd prime number as a modulus, and encryption and decryption are executed by repetition of the point addition operation.

(41) In one embodiment, the modular multiplication device 10 may be implemented in a Montgomery multiplication engine.

(42) In a Montgomery multiplication engine (also referred to as the Montgomery reduction engine), calculations with respect to a modulus N are based on the use of an auxiliary number R referred to as the Montgomery radix or Montgomery base such that gcd(R, N)=1.

(43) In certain embodiments, the modulus N may be a prime number, the radix being then preferably set to 2 to some exponent L, typically chosen as the first convenient power of 2 larger than the modulus (R=2.sup.L).

(44) The Montgomery multiplication of two numbers a and b is the Montgomery reduction of their product, written as xy=xyR.sup.1 mod N.

(45) As R and N satisfy gcd(R, N)=1, there exist two numbers R.sup.1 and N with 0<R.sup.1<N and 0<N<R, satisfying: RR.sup.1NN=1.

(46) Embodiments of the invention provide an improved Montgomery modular multiplication engine by injecting a selected value of the extension parameter r.

(47) The cryptographic system and method according to the embodiments of the invention may be applied to perform a Montgomery Multiplication with or without final reduction, for exponentiation operations for different public key encryption techniques such as RSA or ECSM (Elliptic Curve Scalar Multiplication) based systems.

(48) The Montgomery reduction of a number c with radix R and a prime modulus N represents the quantity given by cR.sup.1 mod N.

(49) The Montgomery multiplication of two numbers a and b represents the Montgomery reduction of their product, written as ab=abR.sup.1 mod N.

(50) As used herein, the notation x bar () denotes the Montgomery multiplication operation.

(51) The modular multiplication device 10 may be implemented in a Montgomery Engine to calculate the Montgomery product xy of two multiplicands x and y.

(52) The Montgomery engine 10 may be implemented in a hardware or software module and operates on a set of parameters to produce a result. For example, the engine may be used to produce the result xy on two inputs x and y.

(53) The Montgomery engine 10 may be also configured to convert to and from Montgomery form. To convert to Montgomery form, the engine receives a and R.sup.2 as inputs and produces an output =aR.sup.2=aR mod N. Conversely, for converting back to the regular form, the engine receives and 1 as inputs and outputs 1=aRR.sup.1=a mod N.

(54) The Montgomery engine may also be configured to calculate the Montgomery reduction of a number. In this case, the engine receives a and 1 as inputs and produces =a1=aR.sup.1 mod N as an output.

(55) In a Montgomery engine, calculations are carried out on numbers in their Montgomery form (the Montgomery form of a number x being defined as x=xR mod N).

(56) In some cryptographic schemes operating on numbers modulo a prime, given the modulus N, the radix R may be expressed in base 2 form, such as 2 to some positive integer exponent wl (R=2.sup.wl), where w is the wordsize of the machine in bits and l represents the number of words needed to represent the modulus N.

(57) Referring to FIG. 3, a flowchart is presented in accordance with certain embodiments of the invention that depicts the modular multiplication method.

(58) In step 200, the positive integer modulus integer N and the multiplication constant R.sub.ext are loaded and the multiplicands x and y are received.

(59) The multiplication constant R.sub.ext may be defined in base two as the number 2 raised to the w(l+1) exponent, with l representing the number of words used to represent the modulus N and w designates the word size:
R.sub.ext=2.sup.w(l+1)

(60) In step 202, the extension parameter r is selected in the range

(61) $I=]1,\frac{2^{w\left(l+1\right)}}{2N}[.$

(62) In step 204, at least one digit x.sub.1 of the first multiplicand is multiplied with the second multiplicand x and y.

(63) In step 206, a quantity A=x.sub.1yuNr is determined, with u being determined such that uR.sub.ext (x.sub.1y is reduced modulo Nr).

(64) Depending on the application of the invention, the method may comprise applying an operation on the reduction result A using the multiplication constant R.sub.ext, which provides a quantity A.

(65) The parameter u may be determined for example by estimating the quotient of x.sub.1*y (or x.sub.1*y*R.sup.1 in the case of a Montgomery engine) divided by Nr, such estimation being such that q2uq where q represents the exact quotient.

(66) In step 208, the quantity A or the quantity A derived from A may be returned.

(67) The extension parameter r obviates the need for a further reduction modulo Nr to adapt the result to the register size. In particular, selecting an extension parameter r of the type prime number in the interval

(68) $I=]1,\frac{2^{w\left(l+1\right)}}{2N}[$
allows to prevent attacks based on differential power analysis and correlation power analysis. In particular, in certain embodiments, in step 202, r may be selected such that:

(69) 0$2^{\mathrm{wl}}<\mathrm{Nr}<\frac{2^{w\left(l+1\right)}}{2}$
with l representing a positive integer.

(70) Conventional approaches apply default choices of modulus extension Nr for fault detection which keeps Nr on a bitwidth multiple of w, thereby resulting in a weakness with respect to side-channel attacks as extra reductions are needed with R=2.sup.w(l+1) if r fits on two words. In contrast, the selection of r according to the embodiments of the invention allows detecting faults while at the same time eliminating extra reductions.

(71) Depending on the application of the invention (for example certain exponentiation applications), the extension parameter may be specifically selected in the interval in the range

(72) $]1,\frac{2^{w\left(l+1\right)}}{4N}[.$

(73) In certain embodiments, l may be chosen to be equal to the number of words used to represent the modulus N and r may be chosen in the interval]1, 2.sup.w/2[. Accordingly, the computation may be extended of one word only.

(74) The extension parameter r may be chosen randomly or according to certain criteria in the interval]1, 2.sup.w/2[ to prevent attacks based on Differential Power Analysis and Correlation Power Analysis (For example, such that the Hamming distance between the different values of Nr is large).

(75) In particular, r may be set to 2 (r=2) so that the modulus extension Nr is as smaller as possible. As a result, a large number of high most significant bits may be set to zero. The circuit can thus manipulate a number of zero-value bits, thereby reducing the power consumption.

(76) In certain embodiments, the multiplication step 204 may be iteratively performed to multiply a set of digits of the first multiplicand x with the second multiplicand y, which provides an intermediate multiplier output, and the reduction step may be iterated to reduce each intermediate multiplier output, which provides intermediate reduction output, the modular multiplication method further comprising the intermediate reduction outputs.

(77) The extension parameter r may be set for all iterations of steps 204 to 210 or a set of iteration or recomputed for each iteration of steps 204 to 210.

(78) The multiplication step 204 may alternatively multiply directly the first multiplicand with said second multiplicand and apply the reduction step 206 to the multiplication result thus obtained.

(79) FIG. 4 is a flowchart that depicts an embodiment of the multiplication method implemented in a Montgomery engine.

(80) In step 300, the positive integer modulus integer N is received and the constant R.sub.ext are received.

(81) In step 302, the extension parameter is selected radix r is selected as described in relation with step 202.

(82) In step 303, an integer N may be selected in [0, R.sub.ext1] such that:
NrN1(mod R.sub.ext),

(83) In step 304, the multiplication step is performed. It comprises determining the quantity=xyN mod Rext.

(84) In step 306, a quantity A=(xy+uNr) is determined (A is determined by reducing xy modulo Nr).

(85) In step 307, the quantity A is divided by Rext, which provides a quantity A derived from

(86) $A^{}\left(A^{}=\frac{\mathrm{xy}+\mathrm{uNr}}{\mathrm{Rext}}\right).$

(87) In step 308, the quantity A is returned by the Montgomery engine (for example published to the requesting application).

(88) It should be noted that operations modulo and division by R.sub.ext may consist in ignoring some bits for the modular operation and shifting for the division operation. This obviates the need for explicitly storing the multiplication constant R.sub.ext in certain embodiments if R.sub.ext is a power of 2.

(89) The Montgomery multiplication function without final reduction will be noted hereinafter .sub.ext.

(90) In certain embodiments, the modular multiplication method may be used to perform exponentiation operation.

(91) FIG. 5 depicts a cryptographic system 100 comprising an exponentiation unit according to an exponentiation application.

(92) The cryptographic system 100 uses the modular multiplication device 10 to compute the modular exponentiation of an integer A (referred to as the base). The modular exponentiation of a given base A represents the remainder when the base A is raised to d-th power (referred to as the exponent) A.sup.d and is divided by the modulus N. The modular exponentiation method may be used in the public-key cryptographic systems 100 to determine many products.

(93) In accordance with certain embodiments, the modular exponentiation may be calculated using the following function: cA.sup.d(mod N). There exist several exponentiation methods for computing n iterations of a multiplication operation (elementary multiplication operation) instead of d such as the left-to-right binary method or right-to-left binary method. The modular exponentiation method may thus involve several calls to the modular multiplication method.

(94) To compute an elementary multiplication operation, the modular exponentiation method may use the modular multiplication method implemented by the modular multiplication device 10 (for example a Montgomery engine) as it has a low computational complexity. The following description of certain embodiments of the exponentiation method will be made with reference to an application of the modular multiplication method to the Montgomery engine for illustration purpose only.

(95) FIG. 6 is a flowchart depicting the modular exponentiation method according to certain embodiments.

(96) In step 500, the positive integer modulus integer N and the multiplication constant R.sub.ext are received.

(97) In step 502, the extension parameter r may be selected according to as described in relation with step 202 of FIG. 3.

(98) In step 504, the quantity .sub.ext=AR.sub.ext mod Nr is computed.

(99) In step 506, the modular exponentiation is recursively computed from .sub.ext using the exponentiation function .sub.ext to determine .sub.ext.sup.d.

(100) This includes invoking several times the modular multiplication function to compute elementary multiplication operations. Each iteration determines .sub.ext.sub.extB.sub.ext by implementing steps 204 to 208 of FIG. 2. Each subsequent multiplication invokes steps 204 to 208 of the modular multiplication function to recursively calculate the product of the current value of .sub.ext and .sub.ext.

(101) The (d1)-th iteration the Montgomery multiplication function thus provides .sub.ext raised to d-th power: .sub.ext.sup.d.

(102) In step 508, a post-processing step may be performed to determine A.sub.ext.sup.d from .sub.ext.sup.d using the modular multiplication method without reduction (denoted .sub.no-reduc):
A.sub.ext.sup.d=.sub.ext.sup.d.sub.no-reduc1.

(103) In step 510, the base A raised to the d-th power is returned as:
A.sup.d=A.sub.ext.sup.d mod N

(104) It should be noted that the selection step 502, may be performed once or at each iteration of modular multiplication method (in which case, step 202 is iterated and step 502 is removed).

(105) To obviate the need for an extra reduction, R.sub.ext may be selected to be greater than the minimal R, i.e., R.sub.ext=2.sup.w(l+1) and r may be chosen as a prime number such that Nr has at least one bit less than R.sub.ext so as to remove the need for extra reduction condition. This result in performing a modulus extension from N to Nr where r is a prime number satisfying:

(106) $N<\mathrm{Nr}<\frac{2^{w\left(l+1\right)}}{2}=2^{w\left(\left[{\log }_2\left(N\right)/w\right]+1\right)-1)}$

(107) In still other embodiments, the modular multiplication function may be used to perform ECSM (Elliptic Curve Scalar Multiplication) in an Elliptic Curve cryptosystem 100.

(108) Indeed, fault attacks may be directed not only to RSA cryptosystem but also to elliptic curve cryptosystems. Operations on elliptic curves may be used in an asymmetric cryptographic system 100.

(109) Elliptic curves are generally defined as a set of points satisfying a certain cubic equation called the Weierstrass Equation in some field , i.e., as the graph of the Weierstrass Equation. Mathematically, they represent a special class of planar curves. Elliptic curves and their points can be expressed in a variety of representations such as affine coordinates, projective coordinates, Jacobian coordinates, and Montgomery form.

(110) Elliptic curves used in cryptography are defined over a prime field .sub.p with p prime or over a binary field .sub.2.sub.t for some large t. They are particularly suitable for an implementation of embedded devices that have memory constraints. Because of the physical characteristics of these devices and their use in potentially hostile environments, they are particularly sensitive to side-channel attacks (SCA) which use information observed during the execution of the algorithm to determine a secret key.

(111) The most important operation of ECC is the scalar multiplication of an elliptic curve point P with a secret scalar factor k. This operation is often noted [k]P. Its computational cost is decisive in the overall efficiency of the ECC however implementing SCA countermeasures is very resource consuming.

(112) FIG. 7 is a flowchart depicting the Elliptic Curve Scalar multiplication (ECSM) method according to certain embodiments. The following description of FIG. 5 will be made with reference to a Montgomery multiplication for illustration purpose.

(113) In step 600 a private key (scalar k) and a request for an ECSM product, e.g., a request for Q=[k]P may be received. The base point P is noted as P=(x,y) and the scalar k is noted as k=(a, b). The parameters N and R.sub.ext are also received or loaded.

(114) In response to the reception of the request for the ECSM product (Q=[k]P), the extension parameter r is selected, in step 602 as described previously in relation with step 202 of FIG. 2.

(115) In step 604, the curve parameters and the base point are preprocessed. The preprocessing comprising replacing each parameter x, y, a and b are converted into the Montgomery form: x is thus converted into x.sub.ext=xR.sub.ext mod Nr; y is thus converted into y.sub.ext=yR.sub.ext mod Nr; a is thus converted into a.sub.ext=aR.sub.ext mod Nr; b is thus converted into b.sub.ext=bR.sub.ext mod Nr.

(116) In step 606, the ECSM Q=[k]P is computed using the Montgomery multiplication function instead of the regular Montgomery multiplication.

(117) The method thus receives the base point P on an elliptic curve and a scalar k (representing the secret scalar), the base point P having a prime order, and generates a random integer.

(118) The scalar multiplication [k]P may then be determined in the Montgomery representation as Q=(x.sub.Qext, y.sub.Qext) using the Montgomery multiplication as:
Qext=(x.sub.Q,y.sub.Q)=[k]P

(119) The ECSM may be computed using the classic ECSM algorithms, using doubling of a point and addition of two different points.

(120) A post-processing may be further applied to convert back the product Q from the Montgomery form into the regular form, in step 608. This comprises converting the first component x.sub.Q into x.sub.Q and the component y.sub.Q into y.sub.Q by applying the Montgomery multiplication operator as follows:
x.sub.Qext=x.sub.Qext1
y.sub.Qext=y.sub.Qext1

(121) In step 609, the component x.sub.Q and y.sub.Q are determined from x.sub.Qext and y.sub.Qext according to:
x.sub.Q=x.sub.Qext mod N
y.sub.Q=y.sub.Qext mod N

(122) From the scalar product [k]P, the product Q=(x.sub.Q, y.sub.Q) may be published in step 310 to the requesting application.

(123) It is an advantage of the invention to extend the modulus by a selected random number instead of using a conventional modulus consisting in a fixed number of machine words (i.e., its size is a multiple of the machine word length) which is prone to attacks exploiting extra reductions. The use of an extended modulus allows a concomitant integrity check of the computation, reduces or even cancels the extra reductions (for example for RSA). In ECC computations (algorithms ECDBL & ECADD), since the reductions in additions/subtractions are absorbed during the Montgomery modular multiplication method according to the invention, such operations can be dropped or reordered.

(124) An exemplary application of the Montgomery modular multiplication method without reduction will be described hereinafter, considering a modulus p and a value of the radius R equal to: R=2.sup.+log.sup.2.sup.(N)

(125) Such radius R is equal to 2.sup. times the smaller power of two greater than N.

(126) The radius R satisfies the following inequality:
2.sup.R2.sup.+1N,

(127) It should be noted that the above inequality in the lower bound would only occur if N is a power of 2. If N is a prime or a composite RSA number, this is thus never satisfied.

(128) It has been demonstrated by the inventors that depending on the values of the parameter >0, the Montgomery modular multiplication may be implemented without extra-reduction and that for some values of the parameter . The absence of extra-reduction allows for performing instead an extra addition. In particular, it has been determined that: for 1, the Montgomery modular multiplication can be implemented without extra-reduction, and for 2, a number z can be even added such that 0zN1 without requiring an extra reduction.

(129) Even if not limited to such applications, such embodiment of the invention has particular advantages for an elliptic cryptographic system based on mixed coordinates system, such as for example Jacobian coordinates, and which can be used in the processes of encryption, decryption, signature generation, authentication, etc.

(130) Considering two points P1 and P2 on the Weierstrass form elliptic curve E, the sum of P1 and P2 is defined as P3=P1+P2.

(131) Computing P1+P2 when P1 is different from P2 is referred to as an elliptic curve addition or ECADD, and computing P1+P2=[2]P1 when P1=P2 is referred to as an elliptic curve doubling or ECDBL.

(132) The elliptic curve addition ECADD is performed to obtain the point P3=P1+P2=(x3, y3) by turning the intersection point of the straight line connecting the point P1=(x1, y1) on the elliptic curve to the point P2=(x2, y2) on the elliptic curve over the x axis.

(133) The elliptic curve doubling is performed to obtain the point P4=[2]P1=(x4, y4) by turning the intersection point of the tangent at the point P1=(x1, y1) on the elliptic curve over the x axis.

(134) Scalar multiplication refers to computing the point [d]P=P+P+ . . . +P (sum taken d times) for the elliptic curve over the finite field, for the point P on the curve, and for the integer (also referred to as a scalar) d. The scalar multiplication is represented by a combination of the elliptic curve addition and the elliptic curve doubling.

(135) The computations of elliptic curve addition, elliptic curve doubling, and scalar multiplication are a combination of addition, subtraction, multiplication, squaring, and inversion in the finite field. In many cases, the computation time of multiplication by addition, subtraction, and constant is comparatively shorter than the computation time of other processes and can be ignored. The computation time of the elliptic curve addition, the elliptic curve doubling, and the scalar multiplication can be frequently thus estimated by a sum of the computation times of multiplication, squaring, and inversion in the in the finite field.

(136) In such exemplary application, the field multiplication in the Elliptic Curve Addition noted ECADD, is directly followed by a field square in Elliptic Curve Doubling noted ECDBL, namely Z3=Z1*Z2*H in ECADD, which is followed by Z1.sup.4 in ECDBL when computing M. It should be noted that Z1.sup.4 is computed as (Z1.sup.2).sup.2: according to a ECDBL, P3=(X.sub.3, Y.sub.3, Z.sub.3)=2P.sub.1 can be computed as:
X.sub.3=T, Y.sub.3=8Y.sub.1.sup.4+M(ST), Z.sub.3=2Y.sub.1Z.sub.1, S=4X.sub.1Y.sub.1.sup.2, M=3X.sub.1.sup.2+Z.sub.1.sup.4, T=2S+M.sup.2 according to ECADD, P.sub.3=(X.sub.3, Y.sub.3, Z.sub.3)=P.sub.1+P.sub.2 can be computed as:
X.sub.3=H.sup.32U.sub.1H.sup.2+R.sup.2, Y.sub.3=S.sub.1H.sup.3+R(U.sub.1H.sup.2X.sub.3), Z.sub.3=Z.sub.1Z.sub.2H, U.sub.1=X.sub.1Z.sub.2.sup.2, U.sub.2=x.sub.2Z.sub.1.sup.2S.sub.1=Y.sub.1Z.sub.2.sup.3, S.sub.2=Y.sub.2Z.sub.1.sup.3, H=U.sub.2U.sub.1, R=S.sub.2S.sub.1

(137) There is also a field multiplication in ECDBL which is directly followed by a field square in ECDBL, namely (2*Y.sub.1)*Z.sub.1=Z.sub.3 which is followed by Z.sub.1.sup.4 in ECDBL when computing M.

(138) In such application of the invention, the protection consists in breaking the correlation between X.sub.1 and X.sub.2 doing a modulus extension according to the embodiments of the invention such that the final modulus Nr does not satisfy the assumption of being of size a multiple of machine words. Thus R is not chosen multiple of 32 or 64 bits, unlike what is done in conventional approaches (such as the article On Countermeasures Against Fault Attacks on Elliptic Curve Cryptography Using Fault Detection by Arash Hariri and Arash Reyhani-Masoleh, Fault Analysis in Cryptography, 2012, Springer). This allows using all the bits of the radius R.

(139) In the above ECBL and ECADD equations, the term U.sub.1H.sub.2X.sub.3 involves a multiplication U.sub.1H.sub.2 and an addition of X.sub.3, with 0X.sub.3<N, after the multiplication, assuming that X.sub.3 is the coordinate of a point in affine coordinates.

(140) The Montgomery modular multiplication method according to the embodiments of the invention removes the need for extra-reduction, the computational resources thus saved being reusable to perform additional operations such as additions.

(141) The Montgomery modular multiplication method according to the embodiments of the invention can be written according to the following algorithm in pseudo code:

(142) TABLE-US-00001 Input: 0 x,y 2.sup.1N 1 Output: ( xyR.sup.1mod N) + N, for some 1. c ab 2. d (cN.sup.1)mod R 3. e c + dN//e mod R = 0 4. f e/R 5. Return f

(143) It should be noted that a CIOS (namely Coarsely Integrated Operand Scanning) implementation of this algorithm is particularly efficient.

(144) The following interval values for the internal variables c, d, e, f of the Montgomery modular multiplication method according to the embodiments of the invention are considered: 0c(2.sup.1N1).sup.2, 0dR1, 0e(2.sup.1N1).sup.2+N(R1,

(145) $0f\frac{1}{R}\left({\left(2^{-1}N-1\right)}^2+N\left(R-1\right)\right),$

(146) To remove the need for extra-reduction, the result f of the modular multiplication may be compatible with the condition on the inputs of the Montgomery modular algorithm so that f also satisfies:
0f2.sup.1N1

(147) As f also satisfies:

(148) $0f\frac{1}{R}\left({\left(2^{-1}N-1\right)}^2+N\left(R-1\right)\right)$

(149) To verify condition , it is sufficient that:
(2.sup.1N1).sup.2+N(R1)R(2.sup.1N1)(2.sup.1N1).sup.2NR(2.sup.1N1N)0

(150) Indeed, R satisfies the inequality R2.sup.1N which is equivalent to:
R(2.sup.1N1N)2.sup.N(2.sup.1N1N)

(151) Hence condition can be satisfied if:
(2.sup.1N1).sup.2NR(2.sup.1N1N)(2.sup.1N1).sup.2N2.sup.N(2.sup.1N1N)

(152) The right hand side quantity of the previous equation can be rewritten as follows:

(153) $\begin{array}{c}{\left(2^{-1}N-1\right)}^2-N-2^{}N\left(2^{-1}N-1-N\right)=2^{2-2}{N}^2+\\ 1-2^{}N-N-\\ 2^{2-1}{N}^2+\\ 2^{}N+2^{}{N}^2\\ =1-\left(2^{2-2}+2^{}\right)N-N\end{array}$

(154) The right hand side quantity of the previous equation is negative because N>1. Condition is accordingly satisfied.

(155) By adding one further addition f+z after the last step of the Montgomery modular multiplication algorithm N such that a number z is added to f with 0zN1, the condition can be rewritten as follows:
(2.sup.1N1).sup.2N(R1)+R(N1)R(2.sup.1N1)

(156) This equation can be rewritten as:
(2.sup.1N1).sup.2+N2.sup.N(2.sup.1N1NN+1)01+(2.sup.22+2.sup.+1)N.sup.22.sup.NN0

(157) Such condition is verified if:
C.sub.1: 2.sup.22+2.sup.+10
C.sub.2: >3

(158) It should be noted that: for =3, 2.sup.22+2.sup.+1=0 and for >3, the quantity 2.sup.22+2.sup.+1 is strictly negative.

(159) Accordingly, if the conditions .sub.1 and .sub.2 are verified, one further addition in affine coordinates can be tolerated without extra-reduction, such as the addition, for example to compute the term U.sub.1H.sub.2X.sub.3 involving the addition of X.sub.3 according to FIG. 1.

(160) The protection method makes it possible to move the implementation outside of the attack exposure by selectively resizing the modulus so that the effect of extra reductions is not leaking information about the sequence of operations.

(161) Further, a re-blinding step may be further applied during the exponentiation, whereas such blinding is conventionally done at the input of the exponentiation only.

(162) The invention also provides a protection method used to protect the cryptographic system 100 against different types of attacks such as an attack on regular exponentiation on finite fields when the system 100 uses a Montgomery modular multiplication method according to the certain embodiments of the invention. Such attack is based on the fact that it can be determined whether the result of a multiplication (or a square) feeds (or not) a square. For example, considering an attack which is able to trace the data in a sequence of arithmetic operations, it has been noted that, especially with a very high correlation (between about 15% to 30%, in absolute values), it can be determined if the result from a multiplication is fed into a squaring operation as described in H. Sato, D. Schepers and T. Takagi (2005), Exact Analysis of Montgomery Multiplication, Progress in Cryptology-INDOCRYPT 2004, Lecture Notes in Computer Science, publisher:Springer Berlin, volume 3348, page 1387-1394.

(163) The various embodiments of the invention allows in one computation to get the correct answer by reducing the result modulo the nominal p, and to get a checksum by reducting the result modulo the other factor r.

(164) The various embodiments also allow to get aligned on the memory words.

(165) The invention offers protection against several attacks including: timing attacks as the modular multiplication is executed in constant time without conditional reduction which is conventionally the basis of several attacks); fault injection attacks thanks to a redundancy which allows checking the computations.

(166) It should be noted that the invention may be implemented in any cryptosystem (e.g. RSA, ECC). In addition, a complementary verification method may be used for fault detection in certain applications.

(167) In particular, the invention may be applied to protect asymmetrical cryptosystems against fault injection attacks, as discussed in Fault Analysis in Cryptography (Marc Joye and Michael Tunstall, Springer LNCS, 2011, DOI: 10.1007/978-3-642-29656-7; ISBN 978-3-642-29655-0). For example, it prevents the attacker from using one fault to break the cryptosystem (such as attacker using the BellCoRe attack against RSA when optimized with the Chinese Remainder Theorem). This also offers a protection against other faults attacks which use one fault to reveal one bit of the secret, such as safe errors on ECC.

(168) The invention may have a significant impact on removal of covert channels (data leakage) and resistance to fault injection for use in a cryptographic system implemented in an embedded system (such as smartcards) but also for use in a cryptographic scheme implemented in a M2M platform or terminal in IoT architecture (Internet of Things).

(169) Additional advantages and modifications will readily appear to those skilled in the art. The invention in its broader aspects is therefore not limited to the specific details, representative methods, and illustrative examples shown and described. Accordingly, departures may be made from such details without departing from the spirit or scope of applicant's general inventive concept. In particular, although the invention has particular advantages for a Montgomery multiplication engine, it should be noted that the invention also applies to other modular multiplication engine such as the Barret multiplication engine or the Quisquater multiplication engine which conventionally feature extra-reductions when implemented in a straightforward manner. Barrett and Quisquater modular multiplication engines are other efficient modular multiplications for which the reduction cost is reduced by an operation in a special representation. It should be noted that according to an application of the invention to a Barrett modular multiplication engine, the modular multiplication method may comprise one or more subtractions according to step 206 (A=x.sub.1yuNr). According to an application of the invention to a Quisquater modular multiplication engine, the modular multiplication method comprise only one subtraction according to step 206 (A=x.sub.1yuNr).

(170) Embodiments of the present invention can take the form of an embodiment containing both hardware and software elements.

(171) Furthermore, the cryptography methods described herein can be implemented by computer program instructions supplied to the processor of any type of computer to produce a machine with a processor that executes the instructions to implement the functions/acts specified herein. These computer program instructions may also be stored in a computer-readable medium that can direct a computer to function in a particular manner. To that end, the computer program instructions may be loaded onto a computer to cause the performance of a series of operational steps and thereby produce a computer implemented process such that the executed instructions provide processes for implementing the functions/acts specified herein.