Device for performing modular multiplication

IMPROVED METHOD FOR PERFORMING MODULAR AND

C ONVENTI ONAL MULTIPLIC ATI ON

Field of the Invention

The invention relates to a process and apparatus for carrying out modular multiplication and exponentiation of large numbers and related operations, particularly for Public Key Cryptographic authentication and encryption protocols.

This application makes reference to 2 applications which have since been cancelled: application No. 103921 and copending application No. 104753.

Background of the Invention

In parent copending Application No. 103921, and in first copending addition application number 104753, a device and method is described and claimed, more specifically, a compact synchronous microelectronic peripheral machine for standard microprocessors, with means for proper clocking and control, which is specifically intended to carry out a modular multiplication method known as the Interleaved Montgomery Multiprecision Modular Multiplication Method, and modular exponentiation processes based on the said multiplication method, which processes are often used in encryption systems. The parent application fully describes the mathematical basis for those methods, which involves the use of a T operator, such tnat, for any two numbers A and B which are the multiplicand and the multiplier, and a /93 modular N, A. Β. I mod N ξ 2<Α.Β)Ν, wherein I is a parasitic factor . X which actually has no influence on the overall precision.

To enact the !?operator on Α.Β the following process can be carried out, using a precalculated constant J:

1) X = A-B

2) Y = (X-J) mod 2ⁿ (only the n LS bits are necessary)

3) Z = X + Y-N

4) S = Z/2ⁿ.

5) P ¥ S mod N (N is to be subtracted from S, if S > N)

Finally, at step 5):

P ¥ ί(Α.Β)Ν,

After the subtraction of N, if necessary:

P = !ΜΑ.Β)ν = A-B mod N

J is a constant which depends on module N only and is defined by J = *N¹־ mod 2^N. The symbol = signifies congruence, while the symbol ¥ signifies limited congruence, viz. that an equality exists or an equality plus a modulo exists.

The hardware described in the parent application and in application^ No. 104753 carries out modular multiplication and exponentiation by applying the !? operator in a new and original proceeding. Further, the squaring can be carried out in the same method, by applying it to a multiplicand and a multiplier that are equal. Modular exponentiation involves a succession of modular multiplications and squarings, and therefore is carried out by a method which comprises the repeated, /93 suitably combined and oriented application of the aforesaid multiplication squaring and exponentiation methods. However, a novel and improved way of carrying out modular exponentiation will be further specified herein.

The aforesaid copending applications describe a method for carrying out modular multiplication, wherein the multiplicand A, the multiplier B and the modulo N comprise m characters of k bits each, the multiplicand and the multiplier not being greater than the modulo, which comprises the steps of:

- precalculating a parameter H and at least the least significant character Jo of another parameter J, as hereinafter defined, and loading Jo into a k-bit register;

- loading the multiplier B and the modulo N into respective registers of mbit length, wherein n=m-k;

- setting an n-bit long register S to zero; and carrying out an i-iteration m times, wherein i is from zero to m-1, each ith iteration comprising the following operations:

a) transferring the ith character Am of the multiplicand A from A! register means to storing means chosen from among register and latch means;

b) generating the value X = S(i-l) + A(m) . B, wherein S(i-l) is the updated value of S, as hereinafter defined, by :

I - cycle right shifting of the B register into multiplying means,

II - serially multiplying B by Am,

III - cycle right shifting of the modulo register N,

IV ־ determining the updated value of S(i-l) as the value stored in the S register after the (i-l)th iteration, if the same is not greater .

than N, or if it is greater than N, by serially subtracting N from it and assuming the resulting value as the updated value of S(i-l); and

V ־ cycle right shifting of the register S and serially adding the value of the multiplication A(!.!) . B bit by bit to the updated value of S;

c) multiplying the LS character of X, Xo by Jo and entering the value X0 . Jq mod into register means as Yo, while delaying N and X by k clock cycles;

d) calculating the value Z = X + Yo ־ N by:

I - multiplying Yo by N by a delayed right shifting of the N register concurrent with the aforesaid right cycle shifting thereof, and

II - adding X to the value of Yq . N;

e) ignoring the least significant character of Z and entering the remaining characters into the S register, whereby to enter Z/2k, except for the last iteration;

f) comparing Z/2^k to N bit by bit for the purpose of determining the updated value of S, S(i) in the manner hereinbefore defined;

g) wherein the ith character of the multiplicand A! is loaded into the A register means at any time during the aforesaid operations;

5) at the last (mth) iteration, ignoring the least significant character of Z/2k and entering the remaining characters into the B register, as the value of C ¥!? (A . B)N;

6) repeating the steps 3) to 4), wherein C or C-N, if C is greater than N, is substituted for B and H is substituted for A, whereby to calculate P = ¢(0 . H) modN; and

7) assuming the value of !?obtained from the last iteration as the result of the operation A . B mod N.

/93

Said multiplication method is particularly described in application

No. 104753, and therefore will be designated as the multiplication method of application No. 104753 or a Montgomery multiplication, or a multiplication in the (Pfield of numbers.

Said copending applications also describe a method for performing the /modular exponentiation of D = A® modN which comprises the following steps:

1) loading the modulo number into the aforesaid register N;

2) setting the aforesaid register S to zero;

3) loading the base A to be exponentiated into the aforesaid register B;

4) storing the exponent E in a computer register;

5) shifting said exponent E left;

6) ignoring all the zero bits thereof which precede the first 1 bit and ignoring the first 1 bit of said exponent E, and for all the following hits performing the operations 7 to 9:

7) for every one of said bits, regardless of its being 0 or 1, squaring the content of register B by the multiplication method hereinbefore set forth, wherein the successive characters of the base are loaded into register A! from register B;

8) if and only if the current bit of the exponent E is 1, multiplying, after performing operation 7), the content of register B by the base A; and

9) after each Montgomery square or Montgomery multiply operation to perform a Montgomery C . H multiplication (T(C . H)n, and

10) after performing steps 6-9 for all bits of E, storing the result of the last operation as D ¥ A^E mod N in register B.

/93

Further, said copending applications describe a method for performing modular exponentiation of D = A^E mod N which comprises the steps of:

1) loading the modulo number into the aforesaid register N;

2) setting the aforesaid register S to zero;

3) loading the base A to be exponentiated into the aforesaid register B;

4) storing the exponent E in a computer register, and a precalculated parameter T in the CPU memory;

5) shifting said exponent E left;

6) ignoring all the zero bits thereof which precede the first 1 bit and ignoring the first 1 bit of said exponent E, and for all the following bits performing the operations 7 to 8:

7) for every one of said bits, regardless of its being 0 or 1, carrying out operations 4 and 5 of the multiplication method hereinbefore set forth, wherein both the multiplicand and the multiplier are the base A, and wherein the successive characters of the base are loaded into register A; from register B;

8) if and only if the current bit of the exponent E is 1, carrying out, after performing operation 7), operations 4 and 5 of the multiplication method hereinbefore set forth, wherein the multiplicand is the content of register B and the multiplier is the base A; and

9) after performing steps 7-8 for all bits of E, performing an additional Montgomery multiplication of register B by the parameter T (3{B T) n), and then storing the result of the last operation as D ¥ A^Emod N in register B.

Parameter T is defined as T = (2ⁿ)S modN, wherein

S = 2Q־!+E mod 2Q¹־, as explained in detail in the parent application.

/93

It is the purpose of this invention to provide an improved method for performing an exponentiation operation, and to provide a method for performing a multiplication operation of large numbers in the conventional field of numbers (not the modular field), by the same hardware described therein, the preferred embodiment of which is the device described in the parent application and in the addition application number 104753, and to which multiplexer M2_l;6 in Figure 3 (38 in Figure 2) has been appended.

Summary of the Invention

This invention provides an even more improved method for performing modular exponentiation of D = A^E mod N, which comprises the steps of:

1) storing the exponent E in a computer register.

2) loading the modulo number into the aforesaid register N;

3) setting the aforesaid register S to zero;

4) performing a multiplication operation, by the method of application No. 104753, of Α*=(Ρ/ΆΉ)ν while A is the operand to be exponentiated, and H is a precalculated parameter as defined before.

5) loading A* into the base register B.

6) performing a squaring operation of the contents of register B.

7) shifting said exponent E left;

8) ignoring all the zero bits thereof which precede the first 1 bit and ignoring the first 1 bit of said exponent E, and for all the following bits performing the operations 9 to 10:

9) for every one of said E bits, regardless of its being 0 or 1, carrying out operations 4 and 5 of the squaring method hereinbefore set forth, wherein both the multiplicand and the multiplier originate from the B /93 register, and wherein the successive characters of the Montgomery multiplier are loaded into register Aj from register B;

10) if and only if the current bit of the exponent E is 1, carrying out, after performing operation 9, operations 4 and 5 of the multiplication method hereinbefore set forth, wherein the multiplicand is the content of register B and the multiplier is the base A ; and

11) after performing steps 8-10 for all bits of E, performing an additional Montgomery multiplication of register B by the original base A and then storing the result of the last operation as D ¥ A^EmodN in register B if the exponent is odd; if the exponent were even, perform an additional Montgomery multipheation of D times 1: B¥2>(D-1)¥DI

It is seen that the exponentiation method of this invention eliminates the need for the computation of the parameter T, hereinbefore mentioned.

It has further been found, and this is another object of the present invention, that the machine described in the previous applications (in a 512 bit register size form) permits obtaining the result of the conventional multiplication of two n/2 bit numbers (actually any two operands which when multiplied will not cause a result longer than n bits, i.e. an overflow) without using the additional hardware or the cumbersome operations that would be required to obtain it according to the prior art. This is achieved by carrying out modular multiplication of said numbers by the multiplication process of the aforesaid application No. 104753, wherein the modulo number N is an n-bit number consisting of all l's (ίϊϊϊϊΙΓ..£Εί), equating Jo to 1, and loading /93 the multiplicand in B and manipulating A as in said multiplication process of application No. 104753.

The device for carrying out such multiplication in the normal field of numbers by the aforesaid method can be the same device described in our two copending applications, hereinbefore mentioned, which comprises control means including a CPU and a multiplication circuit which comprises:

an n-bit shift register B for the multiplier;

an n-bit shift register N for the modulo ;

an n-bit shift register for the value S as herein defined;

a k-bit register A! for the multiplicand;

k-bit register means for the values Jo and Yq as herein defined;

multiplier means for multiplying the content of the B register by that of the Aj register;

additional n-bit multiplier means; and adding, subtracting, multiplexing and delay means.

The said device is particularly described in parent application No. 103921, and therefore will be called hereinafter the device of application No. 103921.

Preferably, all connections between the n-bit registers and the remaining components and between components none of which is a latch, are 1-bit connections.

/93

Description of the Drawings

In the drawings:

- Fig. 1 is a block diagram of an apparatus suitable for carrying out the invention;

- Fig. 2 is a schematic block diagram of a modular multiplication circuit forming part of said apparatus with an additional multiplexer [38] which can force N to be all ones;

- Fig. 3 shows a particular modular multiplication circuit as appeared in the parent application with an additional multiplexer [M2_l ;6], which can force N to be all ones; and

- Fig. 4 is a schematic diagram illustrating the timing relationship y between the various operation of an iteration of the multiplication operation according to an embodiment of the invention;

Detailed Description of Preferred Embodiments

Fig. 1 illustrates in block diagram form a device for carrying out the methods according to the invention. The device comprises:

1) A complete Central Processing Unit (CPU)

2) Counters

3) A State Machine.

The CPU contains volatile and non-volatile memory some of which can be utilized by this multiplication process. The CPU controls the modular arithmetic block in the circuit.

/93

The CPU:

1) Communicates with a host.

2) Loads and unloads data to and from the chip.

3) Commands the circuit to perform a sequence of mathematical operations.

4) Is responsible for other cryptographic and noncryptographic, and data processing operations.

The counters generate the address for the embodied State Machine.

The embodied State Machine decodes the addresses and generates control signals to the MULT block. These control signals command the MULT block to perform the proper sequence of operations necessary to calculate the 2(A B)N transformation (where A can be equal to B).

Fig. 2 shows in block diagram form a modular multiplication circuit according to the invention, which can be used for carrying out modular squaring and modular exponentiation. Numerals 10, 11 and 12 indicate three registers that are mbit long (n = m-k) which constitute B, S and N registers respectively into which the multiplier value S and the modulo number are loaded. The aforesaid registers are preferably divided into two n/2 registers, preferably including a k least significant bit subdivision for the N and B registers. Multiplexers 13,14 and 15 respectively are placed before the said registers, and if they are subdivided into component parts, a multiplexer is placed before each subdivision. Also shown in a block diagram, these registers are intended to be serially loaded, but it would also be possible to load them in parallel. 16,17 and 18 are three registers, each of which is k bits long, for receiving the values A״ Jo, and Yo values respectively.

Registers 16 and 17 are serial load-parallel output or serial and parallel load-parallel output shift registers. Register 18 is preferably a serial in parallel output shift register. The content of these registers is intended to be processed by multiplying means 19 and 20 through components 21 and 22, which are preferably k-bit latches. If they are latches, they are loaded from registers 16, 17 and 18 through k-bit buses. If they are registers, they can be serially loaded through 1-bit connections. Numerals 24, 25, 25', 26, 36, 37 and 38 also designate multiplexers. Multipliers 19 and 20 may be A serial, B parallel inputs, serial output multiplier means or any other serial/parallel inputs-serial outputs multiplying means. Multiplexer 38 can force the modulus N to be all 1 s for multiplying in the normal field of numbers.

Numerals 27, 28, 29, 30, and 31 designate 1-bit full/half adder/subtract means. 31 designates a full adder/subtract means. 32, 33 and 34 designate k-bit k-clock cycle delay means capable of delaying digital signals, which may be composed of analog or digital components, though digital components are preferred. 35 is a Borrow detector, which is a two bit latch/storage means. As is seen, the device according to the invention - although it is intended to handle large numbers such as 512-bit numbers ־ does not comprise buses, except optionally a few k bit buses, and this constitutes an important saving of hardware. When registers B, S and N comprise n/2 bit parts, the device of the invention can be used to carry out multiplication and exponentiation operations on 256-bit numbers, which is a substantial advantage as to the flexibility of the use of the device.

־132815/93

Fig. 3, which is self-explanatory and which is derived from the parent application, shows a preferred embodiment of the device of Fig. 2 wherein multiplexer M2_l;6 has been appended to the original Figure 3.

It will he evident to skilled persons how the device of Fig. 2 or Fig. 3 carries out the operations which constitute the multiplication method according to the invention. The timing relationship of said operation is, however, further illustrated in Fig. 4. Said figure diagramatically illustrates all the various operations carried out in effective successive clock cycles in an embodiment of the invention, in which n = 512, k = 32 and m = 16. This is a fairly common situation in the encryption art. When the invention is carried out according to the embodiment illustrated in Fig. 3, the same device can be used to operate with n = 256, as well.

In Fig. 4 a succession of the various operations is illustrated as a function of the effective clock cycles, which are marked on the abscissa axis. At the beginning of the operation and before any of the iterations which form a part of the modular multiplication method according to the invention, the values of Β, N and S are loaded in the respective registers. The first character of A is also loaded into the respective register [16]. As soon as an iteration begins and during k clock cycles, the shifting of the content of the B and S registers is carried out. The generation of the X value takes place during n+k effective clock cycles, the first k clock cycles being occupied by entering the value of Xo. During the first effective k clock cycles the value of Yo has been entered. During the next effective n+k clock cycles, the value of X, which had been introduced into multiplier 20, is now shifted or /93 introduced into adder 31 after having been delayed by delay 34. The value of N is used at three different time phases. First, to update S and B, second, delayed k effective clock cycles to multiply by Yo, and then delayed a second k effective clock cycles to sense how the next value of S or B will be updated. During the same n+k effective clock cycles, Z is calculated, as well as Z/2^k. The value of A! is loaded beginning with the first k effective clock cycles and continuing during the successive part of the iteration. The final value of Z/2^ is entered into register S (or B) during n clock cycles after the first 2k effective clock cycles.

As well known in the art, and by definition, an exponentiation operation is actually a series of multiplications of the base operand by itself. As mentioned in our two previous applications, each mutiplication operation performed by our machine adds a parasitic product I to the result e.g. to calculate C=A²modN by the machine of our invention, a product of C=!PfA-A)N=(A-A-DmodN results. In order to eliminate the parasitic quantity I, a second operation of C =!KC-H)N = A²modN is needed for each multiplication operation (H is a precalculated parameter). Thus, according to the parent application, in order to calculate A^E, the operation of C=iHC-H)N should be repeated as many times as the Montgomery squares or multiplys were performed. In our addition application No. 104753 we introduced the parameter T, that can be precalculated, and is equal to T = (2ⁿ)S modN, wherein S = 2<!T₊e _mod 2Q¹־, as explained in detail in application number 10753. As shown in application No. 104753, only one multiplication of C=!P(C-T)n is needed at the end of all the multiplication operations, and there is no need for the many /93 multiplications of C=!P(C-H)n for each time a Montgomery square or multiply is performed, but for many purposes the large exponents are not constants (i.e. the NIST DSS signature algorithm) and T cannot be precalculated.

The introduction of the parameter T can be avoided if the following steps are followed in order to calculate A^E:

Assuming that we have precalculated the Montgomery constant, H, and that our device can both square and multiply in the P field, we wish to calculate:

C ξ A^E mod N.

Let E(j) denote the j bit in the binary representation of the exponent E, starting with the MS bit whose index is 1 and concluding with the LS bit whose index is q, we can exponentiate as follows for odd exponents:

A*¥(HA-H)n

B = A*

FORj = 2TOq ΒΥ!ΗΒ.Β)_ν

IFE(j) = l andJ^qTHEN

B ¥ Φ(Β.Α*)_Ν

IFJ = qTHEN B¥fKBA)_N

ENDFOR

C = B

In the transition from each step to the next, N is subtracted from B whenever B is larger than or equal to N.

/93

After the last iteration, the value B is Y to A^E mod N, and C is the final value.

For even exponents, the last step could be:

IFJ = qTHEN

B¥2(B-1)n

To clarify, we shall use the following example:

E = 1011 -> E(l) =1; E(2)=0; E(3) =1; E (4) = 1;

To find A¹¹modN;q = 4

Α*=!ΗΑ.Η)ν = AI2־ I=AI־lmod N

B = A* for j = 2 to q

B = ϊ(Β.Β)ν which produces: A²(!²( ¹־.I = A²!¹־

E(2) = 0; B = A²!¹־ j=3 B = #B-B)n > (A²(!²( ¹־.I = A⁴!¹־

E(3)=l B = !KB-A*)n --------> (A⁴!¹־) (Al¹־).! = A⁵!¹־ j=4

Β = ί(Β.Β)_Ν

A¹⁰!²־.! = A¹⁰.!¹־

As E(4) was odd, the last multiplication will be by A, to remove the parasitic I¹־.

B = ί(Β.Α) -------> A¹⁰!¹־ . A.! = A¹¹

C = B

Numerical example:

A^E mod N; A=91!6; E = 11 !0 = 10112; Ν=Α59!θ; Η = 44B /93

Therefore: q = 4; J = 217;n = 12

To show that the basic tenets hold we calculate I and 11־ using

Montgomery multiplication:

#1.1)ν=1.1.ι χ = 1.1 y = 1-217 mod 2⁴ z = 1 + 217 * a59 = 15a000 z/1000 = 15a < N

I=15a q = 4; n = 12; J = 217; A = 91;

A*=!KA-H)_N = Al¹־ = lK91-44b)N x = 91 44b = 26e7b y = x . J mod 2⁴ =....30d

2<1־H)n =1-1-2-1 = 1-¹ x = 44b y = 44b. 217 mod 2⁴ z = 44b + 8bd-a59= 5a7000 z/1000 < N

I5 = ¹־a7.

E(2) = 0; E(3) = E(4)= 1; N = a59 z = x + (30d) (a59) = 22000016 z/1000 = 22016 check: A-I^mod N = 91. 5a7 mod a59------>z/1000 = 220

AI־Ua59 = 4f remainder 220

A* = 220

B = A* = 22016 for j = 2 to 4 j = 2 B = 1KB . B)_N = !KA* A*)_n

B = 1K220 . 220)_N x = 220² = 48400 y = x-Jmod 2ⁿ =...cOO z = x + (cOO) (a59) = 80b000 z/1000 = 80b

A²!80 = ¹־b check:A²mod a59 = 9b2 -->

—>9b2-5a7 mod a59-36cde/a59= 54b remainder 80b /93

E(2) = Ο

Β = (A . I¹־ . A . I¹־ . I) = A² . I¹־ j = 3 B = 2{B-B)_N = (A².!²( ¹־ . I modN = A⁴!¹־ x = 80b. 80b = 408079 y = x . J mod 2ⁿ= ..cdf z = x + (40b079 +(cdf)-(a59)=c5e000 z/1000 = c5e c5e > N

B = c5e - a59 = 205 = A⁴!¹־ check: A⁴ = 9b2²modN s 577; 577 . 1577-5 =1־a7 = 205

E(3)=l

B = 21205 . A*)_n = A5.I-1 x = 205 . 220 = 44aa0 y = x •217 mod 2ⁿ = .. 460 z = x + (460) (a59) = 319000 z/1000 = 319 check: A⁴!¹־. A = 205 modN = 319

A5 = 577-91 = 5fb ; 5fb-5a7 = A319 = 1־1• ⁵־ j = 4 B = 2<319-319)n = A^1OI1־ x = 319-319 = 99871 y = x-Jmod2ⁿ =...427 z = x + (427) (a59) = 349000 z/1000 = 349 check: 5fb5־fbN = ΑίθΝ 5 8c5 A¹®.!8 = ⁴־c5-5a7 = 349 as: E(4) = 1 multiply by A (not A*)

B = 2CA1O-I¹־-A)_N = A11_N .

x = 349-91 = 10c59 y = x-Jmod2ⁿ =...dff z = x + (dfO (A59) = 92b000

AH mod N = 92b check: X= 8c5-91 = 4f795 -> X/n = 7a remainder 92b

Had we wanted to find Al° (E(4) = 0), i.e. an even exponent /93 we would take A¹⁰.!¹־ and multiply it by 1 ¢(349-1 )_Nx = 349 y = 349-217 mod 2^ = .. d8f z = x + (d8f) (a59) = 8c5000 A10= 8c5 which was shown previously.

As hereinbefore stated, the apparatus described in the aforesaid copending applications permits to obtain the result of a conventional multiplication of large numbers. For example, it is possible to multiply two 256 bit numbers if a machine of 512 bit registers is used. In order to do this, value of all 1's is loaded into register N or alternatively supplied by a switch providing a constant logic 1 at the output of register N and the remaining operation is carried out as in application number 104753.

If N = , the following conditions exist:

1) H=J=J_O=I=I-1=1 and:

2) C=!KA . B)n=A . B . I, but, 1=1 (as shown in 1), so that:

3) C=A . B

That means that the result C is equal the multiplication of A B in the conventional field of numbers.

־202815/93

Example:

(All numbers in Hexadecimal)

N=ffflff, so: H=J=J_O=I=I-1=1

Let: A=f79, B=efe, so: A0=79, A!=f, A₂=0

S₀=0

X=0+79+efe=7160e

Y=l*Oe=e=Y_o

Z=7160e+e*ffifff=e071600, and by dropping the least significant 00:

Sl=e0716

X=e0716+f*efe=ee7f8

Y=l*fB=Y₀

Z=ee7f8+f8*ffffff=f80ee700, and by dropping the least significant 00 (zeros):

S?=f80ee7

X=S₂+0*B=:S2=f80ee7

Y=l*e7=e7

Z=X+e7*fiifff=e7f80e00, and by dropping the least significant 00:

S3=e7f80e

Check: e79*efe=e7f80e

While an embodiment of the invention has been described by way of illustration, it will be evident that the invention may be carried out by skilled persons with many modifications, variations and adaptations, without departing from its spirit or exceeding the scope of the claims.