Montgomery multiplier architecture

A method comprising:

• generating, based on radixes of respective operands, a radix of an inverse of a modulus, and a radix of the modulus, by an initial processing element (PE) circuit and during a first clock cycle, a first output including (i) a radix of a carry out and (ii) a radix of an intermediate result, the initial PE generates the output by:
• a first multiplier that receives the radixes of the respective operands and generate a first product thereof;
• a first adder configured to receive least significant bits (LSBs) of the product and a Montgomery multiplier result from a middle PE circuit of the middle PE circuits and determine a first sum thereof;
• a second adder configured to receive a most significant bit (MSB) of the sum and MSBs of the product and generate a second sum thereof;
• and
• a second multiplier configured to receive the radix of the inverse of the modulus and the second sum and generate the intermediate result that is a second product thereof;
• generating, based on the first output, by middle PE circuits, and during second and third clock cycles, respective second outputs including (i) respective radixes of a Montgomery multiplication result and (ii) further respective radixes of a carry out based on the first output;
• and
• generating, based on the second output, by a final PE circuit, and during third and fourth clock cycles, further respective radixes of the Montgomery multiplication result based on the second output.

A system for Montgomery multiplication, the system comprising:

• a clock;
• a cryptosystem configured to implement a cryptographic algorithm;
• an initial processing element (PE) circuit configured to, based on inputs from the cryptosystem and during a first clock cycle of the clock, generate a first output including (i) a radix of a carry out and (ii) a radix of an intermediate result, the inputs from the cryptosystem including a radix of a first operand, a radix of a second operand, a radix of an inverse of a modulus, and a radix of the modulus, the initial PE including:
• a first multiplier configured to receive the radixes of the respective operands and generate a first product thereof;
• a first adder configured to receive least significant bits (LSBs) of the product and a Montgomery multiplier result from a middle PE circuit of the middle PE circuits and determine a first sum thereof;
• a second adder configured to receive a most significant bit (MSB) of the sum and MSBs of the product and generate a second sum thereof;
• and
• a second multiplier configured to receive the radix of the inverse of the modulus and the second sum and generate the intermediate result that is a second product thereof;
• middle PE circuits configured to generate, during second and third clock cycles of the clock and based on the first output, a second output including (i) respective radixes of a first portion of a Montgomery multiplication result and (ii) further respective radixes of a carry out, the second and third clock cycles immediately after the first clock cycle;
• and
• a final PE circuit configured to generate, during fourth and fifth clock cycles of the clock based on the second output, further radixes of a second portion of the Montgomery multiplication result, the fourth and fifth clock cycles immediately after the third clock cycle.