Patent ID: 7580966
Filing Date: 2009-08-25
Classification: G06F,H04L

Abstract:
1. 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 ā is a Montgomery remainder of a cryptographic variable a so that ā:=a·p mod n, and 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 a first arithmetic operation of addition of a value of one of several first products, denoted ā 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: where u n′ a third operation of division of the variable u by a power of 2, denoted 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 ā 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 repeating the delivery and allocation operations for each iteration.