METHOD TO SECURELY EXECUTE A MODULAR EXPONENTIATION

摘要

The present invention relates to a method to execute a modular exponentiation R=Xe mod N, said method implementing several variable registers and an indicator register m and performing looped calculations. In the invention each loop includes at least two operations from values stored in variable registers, said operations depending on the value stored in m and on the value of the bit(s) of the exponent currently processed, m indicating if the calculation is completed for the current exponent bit at the end of the operations in the current loop.

主权项

1. Method to execute a modular exponentiation defined by the following mathematical formula:
R=Xe mod N, e being an exponent having a size of s bits, X being a variable, N being a modulus larger than X, R being the result of the modular exponentiation operation;
said method implementing several variable registers and an indicator register m, said method being characterized in that it comprises the following execution steps comprising steps a, b and c, referred to as initialization steps, steps d, e and f, referred to as calculation steps, and step g, referred to a termination step: a) initializing variable registers, at least one of the variable registers with 1 or a constant according to the modular multiplication used, this last variable register being intended to store a current intermediate result, and one of the variable registers with the variable X or a multiple of X mod N according to the modular multiplication used; b) initializing indicator register m with 0 c) initializing an incremental value i with s−1; while i>0, d) performing a determined number of operations, at least two, from values stored in variable registers, first operation being a square of the current intermediate result or a multiplication by X of the current intermediate result, depending on the value stored in the indicator register m and second operation being a square of the current intermediate result from the first operation or a multiplication by X of the current intermediate result from the first operation depending on the value stored in m and on the value of ei, ei being the bit i in the binary representation of e therefore run through from the most significant bit es-1 to the least significant bit e0; e) updating m in function of current exponent bit ei and m value, m indicating if the calculation is completed for the current exponent bit ei at the end of the operations in d); f) updating i in function of current index i, of exponent bits ei and ei-1 and m value, calculation being looped to step d) while i>0; and if i=0, g) proceeding to a termination step, said termination step returning an error message when e0 is null and the value in m indicates the calculation is not completed for the current exponent bit or returning the result of at least a last operation, the operation(s) depending on the indication given by m and on the value of e0.