Apparatus and method for modular multiplication and exponentiation based on montgomery multiplication

• US 6,748,410 B1
• Filed: 01/10/2000
• Issued: 06/08/2004
• Est. Priority Date: 05/04/1997
• Status: Expired due to Term

• Current Assignee: SanDisk IL Ltd. (Western Digital Corporation)
• Original Assignee: M-Systems Flash Disk Pioneers Ltd. (Western Digital Corporation)
• Inventors: Hadad, Isaac, Gressel, Carmi David, Dror, Itai, Mostovoy, Michael, Molchanov, Alexey
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/480,102
• Time in Patent Office: 1,611 Days
• Field of Search: 708/491-492
• US Class Current: 708/491
• CPC Class Codes: G06F 7/728 using Montgomery reduction

Abstract

This invention discloses apparatus and methods for accelerating processing, loading and unloading of data, from and to a plurality of memory addresses in a CPU having an accumulator, and to a memory-mapped coprocessing device for continuous integer computations.

Claims

1. A microelectronic apparatus for performing modular multiplication, squaring and reduction, the apparatus multiplying a multiplicand A by a multiplier B over a modulus N, wherein B is a serial fed multiplier having no more than k bits, multiplicand A comprises no more than k bits, and N comprises no more than k bits, the apparatus comprising:

a first (B) register operative to store the multiplier B;

a modular multiplication device accepting multiplicands each having no more than k bits, the modular multiplication device including a single accumulation device at least k+1 bits long and operative to repeatedly receive a multiplicand and simultaneously output a bit;

a digital logic sensing detector operative to anticipate that a non-zero bit would be about to be output from the single accumulation device and to determine a number of times, Y0, that the modulus N should be added into the single accumulation device so as to force the non-zero bit to zero,

the modular multiplication device being operative, during a first phase, to switch multiplicand values, in turn, into the single accumulation device, and to receive, bit by bit, contents of the (B) register and the Y0 value from the digital logic sensing detector, thereby to force the k first output bits of the single accumulation device to zero, the multiplicand values which are to be switched in turn into the accumulation device comprising at least one value but not more than two values selected from the group consisting of the following three values;

(a) an all-zero string value;

(b) a multiplicand A; and

(c) at least a portion of the modulus N; and

an output transfer mechanism, operative in a last phase to unload a final modular multiplication result from the accumulation device.

2. Apparatus according to claim 1 for performing interleaved modular multiplication and reduction in a plurality of interleaved iterations,

wherein the Y0 value is saved, and wherein the multiplicand values switched in turn into the accumulation device in the first phase comprise at least one value but not more than two values selected from the group consisting of the following three values: (a) an all-zero string value;

(b) a multiplicand A; and

(c) a k-bit least significant portion of the modulus N;

the apparatus also comprising a second (S) register operative to store a temporary result S from an iteration i for use during a subsequent iteration i+1 and an n-bit third (N) register operative to store the modulus N, wherein n is larger than k;

the modular multiplication device being operative, in a first phase of each iteration, to multiply one of a plurality of k bit slices of multiplicand A, by multiplier B,

the modular multiplication device being operative, during a second phase between the first and last phases, to switch into the single accumulation device, in turn, multiplicand values, and to receive multiplier values from the B and N registers, the multiplicand values switched in turn into the accumulation device comprising at least one value but not more than two values selected from the group consisting of the following three values;

(a) an all-zero string value;

(b) a portion of the multiplicand A; and

(c) the Y0 value as saved from the first phase;

the apparatus also comprising a serial addition device operative, during each iteration, to summate the temporary result value S in the second (S) register with the bit output of the accumulation device, thereby to generate a new temporary result for a next in turn iteration.

3. Apparatus according to claim 2, operative to anticipate a Y0 value using the following concurrent one-bit values:

i) a least significant bit of the multiplicand A ANDed to a bit concurrently output from the (B) register;

ii) a least significant carry out bit from the accumulation device;

iii) an “

S out”

summation bit from a second least significant cell of the accumulation device;

iv) a concurrent bit from the previously computed temporary result; and

v) a carry out bit from the serial addition device.

4. Apparatus according to claim 1 wherein the output of the single accumulation device is fed out serially, wherein the digital logic sensing detector is operative to anticipate whether the modulus value (N) is to be added into the single accumulation device.

5. Apparatus as in claim 4 wherein the accumulation device comprises a plurality of cells, wherein k least significant zeroes egress from the modular multiplication device and wherein the apparatus also comprises a logic device which controls the modular multiplication device and which uses the following three quantities to anticipate a next Y0 bit:

i) the least significant bit of multiplicand A ANDed to the bit concurrently output from the (B) register;

ii) a least significant carry-out bit from the accumulation device; and

iii) an “

S out”

summation bit from a second least significant cell of the accumulation device.

6. A method for performing modular multiplication, squaring and reduction, including multiplying a multiplicand A by a multiplier B over a modulus N, wherein B is a serial fed multiplier having no more than k bits, multiplicand A comprises no more than k bits, and N comprises no more than k bits, the method comprising:

storing a multiplier B in a first (B) register;

providing a modular multiplication device

accepting multiplicands having no more than k bits, the modular multiplication device including a single accumulation device at least k+1 bits long and operative to repeatedly receive a multiplicand and simultaneously output a bit;

anticipating that a non-zero bit is about to be output from the single accumulation device and determining a number of times, Y0, that the modulus N should be added into the single accumulation device so as to force the non-zero bit to zero,

during a first phase, switching into the single accumulation device, in turn, multiplicand values, and receiving, bit by bit, the contents of the (B) register and the Y0 value, thereby to force k first output bits of the single accumulation device to zero, the multiplicand values switched in turn into the accumulation device comprising at least one value but not more than two values selected from the group consisting of the following three values;

(a) an all-zero string value;

(b) a multiplicand A; and

(c) at least a portion of the modulus N; and

in a last phase, unloading a final modular multiplication result from the accumulation device.

7. A method according to claim 6 for performing interleaved modular multiplication and reduction in a plurality of interleaved iterations, wherein the Y0 value is saved, and wherein the multiplicand values switched in turn into the accumulation device in the first phase comprise at least one value but not more than two values selected from the group consisting of the following three values:

(a) an all-zero string value;

(b) a multiplicand A; and

(c) a k-bit least significant portion of the modulus N, the method also comprising;

providing a second (S) register operative to store a temporary result S from an iteration for use during a subsequent iteration i+1 and an n-bit third (N) register operative to store the modulus N, wherein n is larger than k;

the modular multiplication device being operative, in the first phase of each iteration, to multiply one of a plurality of slices of multiplicand A by multiplier B,

the modular multiplication device being operative, during a second phase between the first and last phases, to switch into the single accumulation device, in turn, multiplicand values, and to receive multiplier values from the (B) and (N) registers, the multiplicand values switched in turn into the accumulation device comprising at least one value but not more than two values selected from the group consisting of the following three values;

(a) an all-zero string value;

(b) a portion of the multiplicand A; and

(c) the Y0 value as saved from the first phase,

the method also comprising summating, during each iteration, the temporary result value S from the second (S) register with the bit output of the accumulation device, thereby to generate a new temporary result for a next in turn iteration, and

in a last phase, unloading a final modular multiplication result from the accumulation device.