Apparatus and method for modular multiplication and exponentiation based on montgomery multiplication
AssigneeM-Systems Flash Disk Pioneers Ltd.
InventorsCarmi David Gressel, Isaac Hadad, Itai Dror, Alexey Molchanov, Michael Mostovoy
Life of this patent
Estimating the term…
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.
Claims7
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.
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.
Dependencies are inferred from the claim text.