Patent ID: 7580966

Claim:
A method of processing the calculation of a Montgomery product ā· b ·p −1 mod n on the basis of a high-radix 2 ω Montgomery method, where ω is a radix and ω≧2, n is a modulus of a modular product, p is equal to 2 k , where k is a natural integer such that 2 k−1 ≦n<2 k , ā is a Montgomery remainder of a cryptographic variable a so that ā:=a·p mod n, and b is a Montgomery remainder of a cryptographic variable b so that b :=b·p mod n, the method being implemented on computing hardware formed from a set of electronic components comprising at least one carry-save adder, having an input and an output, carried out by said computing hardware to increase a number of encrypting and decrypting operations performed per unit time, and comprising a loop of operations, iterated s times, wherein the i th loop with i going from 0 to s−1, comprises: a first arithmetic operation of addition of a value of one of several first products, denoted ā i · b and a value of a variable, denoted u, wherein ā i represents the ω least significant bits of operand ā, after the operand ā having been shifted to the right i times by ω bits; a second arithmetic operation of addition of a value of one of several second products, denoted m·n, and a value of said variable u, where m is defined by the following relation: m:=u 0 ·n′ 0 mod 2 ω where u 0 represents the ω least significant bits of the variable u, and n′ 0 is equal to −n 0 −1 , where n 0 represents the ω least significant bits of the modulus n, a third operation of division of the variable u by a power of 2, denoted 2 ω according to a third relationship u := u 2 ω , wherein the method comprises delivering, at the input of said at least one carry-save adder, the value of the variable u in the form of a carry-save ordered pair and said value of one of the several first and second products, denoted ā i · b , m·n respectively, in order to perform said first and second arithmetic addition operations and in order to obtain at the output of said at least one carry-save adder a result of respectively the first and the second arithmetic addition operations in the form of a carry-save ordered pair, allocating to the value of the variable u the result obtained at the output to said at least one carry-save adder, the variable u being registered in the form of a carry-save ordered pair formed by two variables C and S, carrying out the third operation of division of the variable u in the form of a carry-save ordered pair in two steps comprising a) a preliminary step of calculation and storage of a carry digit, R e , which is at risk of being lost by the division of each said variable C and S by the power of 2 and; b) a step of division of each said variable C and S by the power of 2; and repeating the delivery and allocation operations for each iteration.