Apparatus and method for calculating a result of a modular multiplication

Abstract

Apparatus for calculating a result of a modular multiplication of a first operand and a second operand with regard to a modulus, each having a length of 2 n bits, the operands and the modulus are split into sub-operands of half the length and are fed to controller controlling MMD unit for performing a MultModDiv operation in accordance with a predetermined step sequence with corresponding input operands and MMD moduli to obtain integer quotient values and residual values with regard to the MMD modulus at an output. The combiner is operable to combine integer quotient values and residual values from predetermined steps of the step sequence to obtain the result.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS[0001]This application is a continuation of International Application No. PCT / EP03 / 04426, filed Apr. 28, 2003, which designated the United States and was not published in English, and which is incorporated herein by reference in its entirety.BACKGROUND OF THE INVENTION[0002]1. Field of the Invention[0003]The present invention relates to computing algorithms, and in particular to computing algorithms required for cryptographic applications.[0004]2. Description of the Related Art[0005]Key lengths are steadily increasing especially in public-key cryptography, but also in other fields of cryptography. This is because security requirements placed upon such cryptographic algorithms are also increasing. The use of the RSA method as a representative of an asymmetric cryptography concept, that is to say the use of a public-key method, increases security from so-called brute-force attacks as the key length used increases. Brute-force attacks are attacks ...

AI Technical Summary

Benefits of technology

This approach reduces execution time by 40% compared to existing methods, enables the use of shorter calculating units for longer operands, and provides additional information from the Div operation, which can be calculated with minimal hardware changes, enhancing security and efficiency.

Problems solved by technology

This leads to the fact that, for example, a 2048-bit RSA algorithm cannot be efficiently handled on 1024-bit coprocessors.

Recently it has turned out that the Chinese Remainder Theorem is particularly susceptible to DFA attacks (DFA=differential fault analysis).

One problem associated with many methods therefore is the “doubling” of so-called modular multiplication, which is a central operation in cryptographic calculations.

This is very time consuming, since the numbers A, B, N, .

. . may only ever be loaded fraction by fraction, which is why conventional methods require a large amount of organization and are error-prone, if they do not fail completely.

Images