Patent ID: 7647367

Claim:
An apparatus implemented in hardware, the apparatus being adapted for calculating a multiplication of a multiplier and a multiplicand with regard to a modulus by means of an iteration method, the apparatus comprising: an examiner for examining digits of the multiplier for a current iteration step by means of a multiplication-lookahead algorithm so as to obtain a multiplication-lookahead shift value; a determinator for determining an intermediate-result shift value larger than zero, so that an intermediate result which stems from an iteration step preceding the current iteration step and is shifted toward more significant bits by the intermediate-result shift value has a most significant bit, whose significance is closer to a significance of a most significant bit of the modulus than is a most significant bit of the intermediate result from the preceding iteration step; a calculator for calculating a multiplicand shift value as a difference between the intermediate-result shift value and the multiplication-lookahead shift value; and a processor for performing a three-operands operation using an intermediate result shifted in accordance with the intermediate-result shift value, a multiplicand shifted in accordance with the multiplicand shift value, and the modulus, so as to obtain an intermediate result for the current iteration step, wherein the iteration method comprises several iteration steps within a cryptographic calculation, the multiplier, the multiplicand, the modulus and the intermediate result for the current iteration step being parameters of the cryptographic calculation.