Compact microelectronic device for performing modular multiplication and exponentiation over large numbers

Microelectronic apparatus for performing modular multiplication of a multiplier by a multiplicand, the apparatus comprising:

• first (B), second (S) and third (N) main switched and clocked serial -in serial-out registers respectively operative to store the multiplier, a partial result and a modulus;
• a first multiplying device in which the multiplicand resides and which is operative, for each of a plurality of portions of the multiplicand in turn, to receive the multiplier from the B register, to multiply the multiplier by a current portion of the multiplicand, and to generate an output comprising a product of said multiplication;
• a serial adder operating on the output of the first multiplying device and a limited congruence of the partial result residing in the s register and operative to provide an output;
• a second multiplying device receiving, in a first phase, the output of the serial adder and a Montgomery constant and receiving, in a second phase, the modulus from the N register, and operative, in the first phase, to compute a first phase product of the Montgomery constant by a portion of the output of the serial adder and, in the second phase, to multiply the modulus by the first phase product, thereby to generate a second phase output which, when combined with the serial adder output, generates said partial result;
• and
• a subtractor for subtracting the modulus from the contents of the S register, to produce a limited congruence thereof
• wherein, after the plurality of portions of the multiplicand have been processed by the first multiplying device, said partial result constitutes a limited congruence of a result of performing said modular multiplication of said multiplier by said multiplicand.