Exponentiation remainder operation circuit

An exponentiation remainder operation circuit, comprising:

• a first exponentiation remainder operator for performing an exponentiation remainder operation for a n/2 bit length parameter, in which n is an even number;
• a second exponentiation remainder operator for performing exponentiation remainder operation for a n/2 bit length parameter;
• a first adder/subtractor for performing addition and subtraction for a n/2 bit length parameter;
• a second adder/subtractor for performing addition and subtraction for a n/2 bit length parameter;
• and
• control means for performing exponentiation remainder operation for a n-bit length parameter by controlling art exponentiation remainder operation of said first exponentiation remainder operator for art upper n/2 bits of said n-bit length parameter, art exponentiation remainder operation of said second exponentiation remainder operator for a lower n/2 bits of said n-bit length parameter, and addition and subtraction of the results of operations of said first and second exponentiation remainder operators by said first and second adders/subtractors;
• said control means including:
• first and second selection means for controlling selection whether a carry signal is used in the operation of said first exponentiation remainder operator and said first adder/subtractor;
• a central processing unit (CPU) for outputting a control signal for controlling operations of said first and second exponentiation remainder operators and said first and second adders/subtractors;
• and
• a storage portion for storing the n-bit parameter as an object of operation, intermediate and final results of operations by said first and second exponentiation remainder operators and said first and second adders/subtractors,
• said first exponentiation remainder operator inputs an output signal of said first selection means as a carry input signal and a first control signal controlling whether the input carry signal is used for operation, and selects one of an exponentiation remainder operation and multiplication remainder operation as an operation to be executed based on a second control signal;
• said second exponentiation remainder operator inputs a carry input signal and a fixed value 0 as the first control signal for controlling whether the input carry signal is used for operation, selects one of the exponentiation remainder operation and the multiplication remainder operation as the operation to be executed based on the second control signal, and outputs a carry output signal to said first selection means;
• said first adder/subtractor inputs an output signal of said second selection means as a carry input signal and a third control signal for selecting one of addition and subtraction as the operation to be executed;
• said second adder/subtractor inputs 0 as a carry input signal and said third control signal for selecting one of addition and subtraction as the operation to be executed, and outputs a carry output signal to said second selection means;
• said first selection means inputs the first control signal for performing switching control for switching the output signal between 0 and the carry output signal from said second exponentiation remainder operator;
• and
• said second selection means inputs the first control signal for performing switching control for switching the output signal between 0 and the carry output signal from said second adder/subtractor.

A method of an exponentiation remainder operation comprising the steps of:

• providing a first exponentiation remainder operator for performing an exponentiation remainder operation for a n/2 bit length parameter, in which n is an even number;
• providing a second exponentiation remainder operator for performing an exponentiation remainder operation for a n/2 bit length parameter;
• providing a first adder/subtractor for performing addition and subtraction for a n/2 bit length parameter;
• providing a second adder/subtractor for performing addition and subtraction for a n/2 bit length parameter;
• and
• providing control means for performing an exponentiation remainder operation for a n-bit length parameter by controlling the exponentiation remainder operation of said first exponentiation remainder operator for an upper n/2 bits of said n-bit length parameter, the exponentiation remainder operation of said second exponentiation remainder operator for a lower n/2 bits of said n bit length parameter, and addition and subtraction of the results of operations of said first and second exponentiation remainder operators by said first and second adders/subtractors;
• operating said control means for controlling said first and second exponentiation remainder operators, and said first and second adders/subtractors for performing an exponentiation remainder operation for deriving a remainder of division of a result obtained by exponentiation of a parameter C with a parameter E as an exponent, by a parameter N, wherein C, E, and N are n-bit length integers;
• deriving first and second remainder operation results as remainders of division of first and second prime numbers P and Q by the parameter C when the parameter N is expressed by a n/2 bit length of two prime numbers, by said first and second exponentiation remainder operators;
• deriving a third remainder operation result expressed by a sum of two n/2 bit length values, which is the remainder in the division of the result of exponentiation of said first remainder operation result by a parameter EP as a remainder of division of a parameter (P-1) by the parameter E, by the first prime number P, by said first exponentiation remainder operator;
• deriving, in parallel to such process of said first exponentiation remainder operator, a fourth remainder operation result expressed by a sum of two n/2 bit length values, which is the remainder in the division of the result of exponentiation of said second remainder operation result by a parameter EQ as a remainder of division of a parameter (Q-1) by the parameter E, by the second prime number Q, by said second exponentiation remainder operator;
• deriving a fifth remainder operation result as a remainder of division of the sum of two n/2 bit length values which is the third remainder operation result, by the parameter P, and a sixth remainder operation result as a remainder of division of the sum of two n/2 bit length values which is the fourth remainder operation result, by the parameter Q, by the first and second exponentiation remainder operators;
• deriving a subtraction result by subtracting said fifth remainder operation result from said sixth remainder operation result by said first adder/subtractor;
• deriving a parameter V which is a n/2 bit length parameter and a remainder of which is one when it is multiplied by said parameter P and then the product is divided by Q, and deriving a seventh remainder operation result expressed by a sum of two n/2 bit length values as remainders of a division of a product of said parameter V and said subtraction result by the parameter Q, by said second exponentiation remainder operator;
• deriving an eighth remainder operation result as a remainder of division of the sum of two n/2 bit length values as the seventh remainder operation result by the parameter Q, by said first and second exponentiation remainder operators;
• deriving a product of multiplication of said second remainder operation result by the parameter P by said first and second exponentiation remainder operators;
• and
• deriving a final result of the exponentiation remainder operation as a sum of the parameter C and said fifth remainder operation result.

In a system including a first exponentiation remainder operator for performing an exponentiation remainder operation for a n/2 bit length parameter, in which n is an even number, a second exponentiation remainder operator for performing an exponentiation remainder operation for n/2 bit length parameter, a first adder/subtractor for performing addition and subtraction for a n/2 bit length parameter, a second adder/subtractor for performing addition and subtraction for a n/2 bit length parameter and control means for controlling said first and second exponentiation remainder operators, and said first and second adders/subtractors,

• a process for an exponentiation remainder operation for deriving a remainder of division obtained by exponentiation of a parameter C with a parameter E as an exponent, by a parameter N, wherein C, E, and N are n-bit length integers, said process comprising the steps of:
• deriving first and second remainder operation results as remainders of a division of first and second prime numbers P and Q by the parameter C when the parameter N is expressed by a n/2 bit length of two prime numbers, by said first and second exponentiation remainder operators;
• deriving a third remainder operation result expressed by a sum of two n/2 bit length values, which is the remainder in the division of the result of exponentiation of said first remainder operation result by a parameter EP as a remainder of division of a parameter (P-1) by the parameter E, by the first prime number P, by said first exponentiation remainder operator;
• deriving, in parallel to such process of said first exponentiation remainder operator, a fourth remainder operation result expressed by a sum of two n/2 bit length values, which is the remainder in the division of the result of exponentiation of said second remainder operation result by a parameter EQ as remainder of division of a parameter (Q-1) by the parameter E, by the second prime number Q, by said second exponentiation remainder operator;
• deriving a fifth remainder operation result as a remainder of division of the sum of two n/2 bit length values which is the third remainder operation result, by the parameter P, and a sixth remainder operation result as a remainder of division of the sum of two n/2 bit length values which is the fourth remainder operation result, by the parameter Q, by the first and second exponentiation remainder operators;
• deriving a subtraction result by subtracting said fifth remainder operation result from said sixth remainder operation result by said first adder/subtractor;
• deriving a parameter V which is a n/2 bit length parameter and a remainder of which is one when it is multiplied by said parameter P and then the product is divided by Q, and deriving a seventh remainder operation result expressed by a sum of two n/2 bit length values as remainders of division of a product of said parameter V and said subtraction result by the parameter Q, by said second exponentiation remainder operator;
• deriving an eighth remainder operation result as a remainder of division of the sum of two n/2 bit length values as the seventh remainder operation result by the parameter Q, by said first and second exponentiation remainder operators;
• deriving a product of multiplication of said second remainder operation result by the parameter P by said first and second exponentiation remainder operators;
• and
• deriving a final result of the exponentiation remainder operation as a sum of the parameter C and said fifth remainder operation result.