Modular operation circuit adopting iterative calculations
AssigneePUFsecurity Corporation
InventorWen-Ching Lin
Life of this patent
Estimating the term…
Abstract
A modular operation circuit includes a controller, a modular multiplier and a modular adder. The controller divides a first number into K segments. The modular multiplier performs modular multiplication operations and the modular adder performs modular addition operations to the K segments in (K−1) iterations for deriving a remainder of a division of the first number by a second number.
Claims20
A method for operating a modular operation circuit to derive a remainder of a division of a first number by a second number in a cryptosystem, the modular operation circuit comprising a controller, a modular multiplier and a modular adder, the method comprising:
- the controller dividing the first number into K segments;
- during a first iteration:
- the modular multiplier performing a first modular multiplication operation to generate a first intermediate result according to a first segment of the K segments and a first base number;
- and
- the modular adder performing a first modular addition operation to generate a first iteration remainder according to the first intermediate result and a second segment of the K segments;
- and
- during a second iteration:
- the modular multiplier performing a second modular multiplication operation to generate a second intermediate result according to the first iteration remainder and a second base number;
- and
- the modular adder performing a second modular addition operation to generate a second iteration remainder according to the second intermediate result and a third segment of the K segments;
- wherein:
- K is an integer greater than 2;
- each of the K segments has a bit length smaller than or equal to a third number;
- the third number is a rounding-up result of logarithm of the second number to base 2;
- the first base number is calculated according to a first exponential value of a bit length of the second segment with a base of 2;
- and
- the second base number is calculated according to a second exponential value of a bit length of the third segment with a base of 2.
A modular operation circuit for deriving a remainder of a division of a first number by a second number in a cryptosystem, the modular operation circuit comprising:
- a controller configured to divide the first number into K segments;
- a modular multiplier coupled to the controller and configured to perform a first modular multiplication operation to generate a first intermediate result according to a first segment of the K segments and a first base number during a first iteration, and perform a second modular multiplication operation to generate a second intermediate result according to a first iteration remainder and a second base number during a second iteration;
- and
- a modular adder coupled to the controller and configured to perform a first modular addition operation to generate the first iteration remainder according to the first intermediate result and a second segment of the K segments during the first iteration, and perform a second modular addition operation to generate a second iteration remainder according to the second intermediate result and a third segment of the K segments during the second iteration;
- wherein:
- K is an integer greater than 2;
- each of the K segments has a bit length smaller than or equal to a third number;
- the third number is a rounding-up result of a logarithm value of the second number to base 2;
- the first base number is calculated according to a first exponential value of a bit length of the second segment with a base of 2;
- and
- the second base number is calculated according to a second exponential value of a bit length of the third segment with a base of 2.
Dependencies are inferred from the claim text.