Patent ID: 8364740

Claim:
A device for calculating a result of a modular multiplication with a multiplier, a multiplicand and a modulus, comprising: a unit for providing the multiplicand in at least three portions, wherein each portion comprises a number of digits less than half the number of digits of the multiplicand, and wherein the at least three portions include all digits of the multiplicand; and a sequential calculator, wherein the sequential calculator is formed to calculate a first intermediate result using a MultModAdd (MMA) operation, wherein a more significant portion of the multiplicand, the multiplier and the modulus are used as operands in the MultModAdd (MMA) operation, and wherein other portions than the more significant portion of the multiplicand are not used to calculate the first intermediate result, to calculate a second intermediate result using a MultModAdd (MMA) operation with a less significant portion of the multiplicand, the multiplier, the modulus and the first intermediate result as operands, and wherein other portions than the less significant portion of the multiplicand are not used to calculate the second intermediate result, and to calculate and store a third intermediate result using a MultModAdd (MMA) operation with a still less significant portion of the multiplicand, the multiplier, the modulus, and the second intermediate result as operands, and wherein other portions than the still less significant portion of the multiplicand are not used to calculate the third intermediate result, wherein the third intermediate result represents the result of the modular multiplication, if the multiplicand is divided into exactly three portions, or wherein the result of the modular multiplication is derivable from the third intermediate result by a further sequential calculation, if the multiplicand is divided into more than three portions, and wherein the sequential calculators is formed to execute the following equations: C =[( A·B 2 mod N )· Z+A·B 1 mod N]·Z+A·B 0 mod N, wherein C is the third intermediate result, wherein A is the multiplier, wherein Z=2 i , wherein i is a number of digits of the portions, wherein B 2 is the most significant portion of the multiplicand, wherein B 1 is a less significant portion of the multiplicand, wherein B 0 is the least significant portion of the multiplicand, wherein N is the modulus, and wherein mod indicates a modular reduction operation.