Montgomery Reduction in Cryptographic Operations

Abstract

An apparatus and a method for performing a Montgomery reduction of an input C modulo a modulus N, in particular in the framework of a Montgomery multiplication, comprising: (i) performing a multiplication to obtain an approximated product Y on the basis of a value D and the modulus N, wherein only a higher-order part of the approximated product Y is computed and/or approximated on the basis of an incomplete execution of the multiplication, and wherein the value D is derived from the input C and an auxiliary integer N′ of the Montgomery reduction, (ii) determining a sum by adding a word or partial word of the input C to a word or partial word of the approximated product Y, (iii) determining a carry on the basis of the sum, and (iv) adding the carry to the input C or to a value derived from the input C.

Dependencies are inferred from the claim text.