Patent ID: 8626811
Filing Date: 2014-01-07
Classification: G06F

Abstract:
1. A method for performing modular operations using a modulus n in a cryptographic system, the method being performed by a computing device including a Montgomery machine having a fixed block length; the modulus n having a block length different from the fixed block length of the Montgomery machine or a multiple thereof; the method comprising: the Montgomery machine obtaining a new modulus n′ having a block length equal to the fixed block length of the Montgomery machine or a multiple thereof; the Montgomery machine obtaining a value representative of a Montgomery radix R; the Montgomery machine performing at least one modular additive operation with the new modulus n′, whereby a carry stemming from the at least one modular additive operation results in reduction of a result of the at least one modular additive operation by n′; the Montgomery machine obtaining a value μ′ of the form μ′=(−n′) the Montgomery machine performing at least one modular multiplicative operation with the modulus n to convert a result of the modular operations out of Montgomery form; and the Montgomery machine storing the result of the modular operations in memory for subsequent retrieval by the Montgomery machine: and wherein the at least one modular multiplicative operation utilizes the value μ′, and wherein the at least one modular additive operation is used in computing R