Patent ID: 6748410
Filing Date: 2004-06-08
Classification: G06F

Abstract:
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.