Apparatus & method for modular multiplication & exponentiation based on Montgomery multiplication
AssigneeFortress U&T Ltd.
InventorsIsaac Hadad, Benjamin Arazi, Carmi David Gressel, Itai Dror
Life of this patent
Estimating the term…
Abstract
A modular arithmetic method and microelectronic apparatus therefore, operative to perform a sequence of interleaved Montgomery type multiplications and squaring operations, involves performing a sequence of modular multiplications and squarings using only a single carry save adder. Each multiplication is operative to perform the equivalent of three natural integer multiplication operations using an anticipatory device to determine a Y0 value, such that a result is an exponentiation.
Claims30
A microelectronic apparatus for performing a Montgomery type modular multiplication of P(Ai·B)N, wherein Ai is a multiplicand, B is a multiplier and N is a modulus, which is limited congruent to a remainder of Ai, times B, over N, times 2−k, input operands being at least n bits in length, and a result being at least 2k+1 bits long, including k disregarded least significant zero bits, which are not saved, where k is not less than n, the apparatus comprising:
- a first (B), and second (N) main memory register, each register holding at least one at least n bit long operand, said registers being respectively operative to store the multiplier, and the modulus, wherein the modulus is odd and is smaller than 2n;
- a modular multiplying device for at least k bit input multiplicands, with only one carry save adder, being at least k+1 bits long, and being operative to accept k bit multiplicands, the multiplication device operative to switch into the carry save adder, in turn, multiplicand values, and in turn to receive multiplier values from a B register, and an “on the fly” simultaneously generated anticipated value, Y0, as a multiplier which is operative to force k least significant zero output bits in the first phase, wherein at each effective machine cycle at least one designated multiplicand is added into the carry save adder;
- a digital logic sensing detector, operative to form the “on the fly” anticipated value, Y0, indicating when a modulus value is to be added to the value in the carry save adder such that all first k least significant multiplication output bits are forced to zero;
- the multiplicand values to be switched in turn into the carry save adder consisting of one or two of the following three multiplicands, an all-zero string value, the multiplicand Ai, and the modulus value N;
- the multiplier values which are input in turn into the multiplying device in the first phase being first the B operand, and concurrently, the second multiplier value consisting of the “on the fly” anticipated value, Y0, in the form of a k bit string, to force least significant zeroes in the output;
- the carry save adder being operative to output values simultaneously as multiplicands are added into the carry save adder;
- an output transfer mechanism, operative in a second phase to output a final P(A·B)N result from the carry save adder.
Apparatus for performing a Montgomery type modular multiplication denoted P(A·B)N which is congruent to A·B·2−n mod N in the normal field of natural integers, wherein n is larger than k, the multiplication process being performable in iterations in a plurality of phases including a first phase, a second phase, and a final phase, with input operands into a multiplying device, the operands at each iteration consisting of modulus N, a multiplier B, a previously computed partial result, Sn−1, and a k-bit string segment of A, a multiplicand, the segments progressing from the A0 string segment to the Am−1 string segment, wherein each iterative result is summated into a next temporary result Sn, in turn, wherein LS bits of iterative results are zeroes, the apparatus comprising:
- first (B), second (S) and third (N) main memory registers, each register capable of storing and outputting operands and being respectively operative to store the multiplier value B, the partial result values at each respective stage S and the modulus N;
- a modular multiplying device operative to summate into a single carry save adder with at least k bits in turn one or two of a plurality of multiplicand values during phases of the iterative multiplication process, and in turn to receive, as multipliers, an input from the B register, a value, Y0, from an “on the fly” anticipating unit usable as a multiplier to force LS zero output bits in each iteration, and values from the modulus, N, register;
- the multiplicand parallel registers operative at least to receive in turn, values from the A, B, and N register sources, and in turn, also the value Y0, being a multiplicand zero forcing value;
- a LS zero forcing Y0 detector device operative to generate a binary string operative to be a multiplier during the first phase and operative to be a multiplicand in the second phase;
- multiplicand values to be switched into the carry save adder for the first phase comprising a first zero value, a second value, Ai, which is a k bit string segment of a multiplicand, A, and a third value N0, being the least significant k bits of the modulus, N;
- wherein a temporary result value, Sn−1, resulting from a previous iteration, is operative to be summated with a value emanating from the carry save adder, to generate a partial result Sn for the next iteration;
- multiplicand values to be input, in turn, into the carry save adder for the second phase being, a first zero value, a second Ai operand, remaining in place from the first phase, and a third Y0 value having been anticipated in the first phase;
- multiplier values input into the multiplying device in the first phase being an LS string, B0, being the least significant string segment of the B operand, concurrently multiplying with the second multiplier value consisting of an anticipated Y0 string which is simultaneously loaded into a preload multiplicand buffer for the second phase;
- the two multiplier values input into the apparatus during the second phase being the MS n-k bit values from the multiplier B, and the n-k bits of the modulus, N, respectively;
- and
- a multiplying flush out device operative in the last phase to transfer the MS segment of a result value remaining in the carry save adder into a result register.
Dependencies are inferred from the claim text.