Patent ID: 7558817

Claim:
A cryptographic apparatus for calculating a result of a modular multiplication of a first operand and a second operand in relation to a modulus, the first operand, the second operand and the modulus each having a first length of 2n bits, n being an integer, the apparatus comprising: a provider configured to provide a first sub-operand and a second sub-operand from the first operand, a first tub-operand, a second sub-operand from the second operand, and a first sub-modulus and a second sub-modulus from the modulus, each having a second length of bits which is shorter than the first length of bits, wherein the provider comprises input registers for the operands having a length of 2n bits and output registers for the sub-operands having a length being shorter than 2n bits; an MultModDiv unit configured to perform an MultModDiv operation, the MultModDiv operation being defined o provide, from a term, an integer quotient value and a residual value with regard to an MultModDiv modulus, wherein the MultModDiv unit is an arithmetic unit having a length shorter than 2n bits; a controller configured to feed the MultModDiv unit with predetermined combinations of input operands and associated MultModDiv moduli in accordance with a predetermined step sequence, the input operands and MultModDiv moduli being based on the first and second sub-operands of the first operand, on the first and second sub-operands of the second operand, on the first and second sub-moduli of the modulus, on integer quotient values and residual values from steps in the predetermined step sequence, and on a factor 2 n , x equaling the second length of bits; and a combiner configured to combine integer quotient values and residual values from predetermined steps of the step sequence so as to obtain the result, wherein the combiner comprises a bit adder having a bit length shorter than 2n bits, wherein the combiner comprises input registers for the integer quotient values and the residual values, the input registers being shorter than 2n bits, wherein the combiner comprises a output memory having 2n bits configured to store the result, and wherein the result is an intermediate result of encrypted/decrypted data.