Patent ID: 6434585
Filing Date: 2002-08-13
Classification: A47B,A47C,B43L,G06F

Abstract:
In a system for performing modular reduction operations integral to cryptographic key calculations, a method for performing efficient Montgomery multiplication, comprising the steps of:(a) providing KN bits of an operand A from a preload register to a multiplier in a single clock pulse, where K and N are positive integers and KN is the product of K and N; (b) providing N bits of an operand B from memory to the multiplier in a single clock pulse, where the operand B is comprised of a total of KN bits; (c) multiplying the KN bits of the operand A by the N bits of the operand B; (d) providing N bits of a new predicted value for the operand A from the memory to the preload register in a single clock pulse that is also used to perform the multiplication of step (c), where the new predicted value for the operand A is comprised of a total of KN bits and based on past values of the operand A; (e) repeating steps (a) through (d) K times until the KN bits of the operand A have been multiplied by the KN bits of the operand B to generate an output number having KN bits, and the KN bits of the new predicted value for the operand A have been provided to the preload register; (f) providing N bits of the output number to a multiplier output port in a single clock pulse; (g) providing N bits of the output number to the preload register if the output number is required for a subsequent multiplication; (h) providing N bits of the output number to memory if the output number is not required for a subsequent multiplication; and (i) repeating steps (f) through (h) until all KN bits of the output number have been provided to memory; wherein steps (a) through (i) are executed to perform Montgomery routine support operations beneficial for performing Montgomery multiplication in a cryptographic key calculation.