Signed montgomery arithmetic
AssigneeCerticom Corp.
InventorRobert J. Lambert
Life of this patent
Estimating the term…
Loading patent…
AssigneeCerticom Corp.
InventorRobert J. Lambert
Estimating the term…
A system and method configured for applying Montgomery style reduction directly to negative quantities as well as positive values, producing the new form which does not require conditional operations to move values into the positive range. The low-order components of the resulting product, or partially completed product, can be reduced either by the addition of multiples of the modulus, as is usual in the standard Montgomery multiplication which accepts positive values, or by subtracting multiples of the modulus, which of course depends on the actual computation. Signed versions of the Montgomery values in a Montgomery computation are used to avoid the conditional addition and subtraction that can leak information, for example, using a two's complement representation.
A method for performing Montgomery arithmetic in a cryptographic operation comprising representing operands in a Montgomery arithmetic operation as signed values;
A computer readable medium for performing Montgomery arithmetic in a cryptographic operation comprising computer readable instructions for representing operands in a Montgomery arithmetic operation as signed values;
A Montgomery machine comprising an arithmetic logic unit configured to operate on signed versions of Montgomery operands;
Dependencies are inferred from the claim text.