Information security device, exponentiation device, modular exponentiation device, and elliptic curve exponentiation device
First Claim
1. An information security device for securely and reliably managing predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
- A, the group being formed from a predetermined set and a binary operation performed using elements of the set, the power operation k &
A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, and the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &
A in the group, the device comprising;
initializing means for storing the identity element as an initial value in a variable X and a variable B2;
repetition control means for controlling calculation means, storage means, and exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &
A, the result of the power operation k &
A being stored in the variable X at the completion of the repetitions;
the calculation means for performing the binary operation using the variable X and the same variable X, performing the binary operation again using the initial binary operation result and an operand stored in the variable B2, and storing the further binary operation result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
1 Assignment
0 Petitions
Accused Products
Abstract
In an exponentiation device, a relatively large table is generated outside of a coprocessor so as to enable high-speed exponentiation to be performed using the small window method. The selection of data from the table and transfer of data to the coprocessor are conducted in parallel with a multiple-length arithmetic operation performed in the coprocessor. So as to avoid bottlenecks occurring in the data transfer between a CPU and the coprocessor, two data banks are provided in the coprocessor for storing the data to be used in the arithmetic operation. By providing two banks in the coprocessor, it is possible to use one for transferring data while data stored in the other is being used in the arithmetic operation. When the operation using the stored data has been completed, the banks are switched, and the arithmetic operation is then repeated using the newly transferred data while at the same time conducting data transfer in readiness for the following operation.
11 Citations
19 Claims
-
1. An information security device for securely and reliably managing predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
- A,
the group being formed from a predetermined set and a binary operation performed using elements of the set, the power operation k &
A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, andthe discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &
A in the group, the device comprising;
initializing means for storing the identity element as an initial value in a variable X and a variable B2;
repetition control means for controlling calculation means, storage means, and exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &
A, the result of the power operation k &
A being stored in the variable X at the completion of the repetitions;
the calculation means for performing the binary operation using the variable X and the same variable X, performing the binary operation again using the initial binary operation result and an operand stored in the variable B2, and storing the further binary operation result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
- A,
-
14. An information security method used by an information security device that securely and reliably manages predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
- A,
the device including initializing means, repetition control means, calculation means, storage means, and exchange means, the group being formed from a predetermined set and a binary operation performed using elements of the set, the power operation k &
A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, andthe discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &
A in the group, the method comprising;
an initializing step for having the initializing means store the identity element as an initial value in a variable X and a variable B2; and
a repetition control step for having the repetition control means control the calculation means, the storage means, and the exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &
A, the result of the power operation k &
A being stored in the variable X at the completion of the repetitions, whereinthe calculation means performs the binary operation using the variable X and the same variable X, performs the binary operation again using the initial binary operation result and an operand stored in the variable B2, and stores the further binary operation result in the variable X, the storage means selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and the exchange means exchanges the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
- A,
-
15. An information security program used by an information security device that securely and reliably manages predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
- A,
the device including initializing means, repetition control means, calculation means, storage means, and exchange means, the group being formed from a predetermined set and a binary operation performed using elements of the set, the power operation k &
A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, andthe discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &
A in the group, the program comprising;
an initializing step for having the initializing means store the identity element as an initial value in a variable X and a variable B2; and
a repetition control step for having the repetition control means control the calculation means, the storage means, and the exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &
A, the result of the power operation k &
A being stored in the variable X at the completion of the repetitions, whereinthe calculation means performs the binary operation using the variable X and the same variable X, performs the binary operation again using the initial binary operation result and an operand stored in the variable B2, and stores the further binary operation result in the variable X, the storage means selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and the exchange means exchanges the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
- A,
-
16. A computer-readable storage medium storing an information security program used by an information security device that securely and reliably manages predetermined information based on the intractability of the discrete logarithm problem in a group by performing a power operation k &
- A,
the device including initializing means, repetition control means, calculation means, storage means, and exchange means, the group being formed from a predetermined set and a binary operation performed using elements of the set, the power operation k &
A involving k number of repetitions of the binary operation performed using the element A of the group and the identity element of the group, andthe discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k &
A in the group, the program comprising;
an initializing step for having the initializing means store the identity element as an initial value in a variable X and a variable B2; and
a repetition control step for having the repetition control means control the calculation means, the storage means, and the exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the power operation k &
A, the result of the power operation k &
A being stored in the variable X at the completion of the repetitions, whereinthe calculation means performs the binary operation using the variable X and the same variable X, performs the binary operation again using the initial binary operation result and an operand stored in the variable B2, and stores the further binary operation result in the variable X, the storage means selects an operand to be used by the calculation means in the following step and stores the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means, and the exchange means exchanges the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
- A,
-
17. An exponentiation device for exponentiating Ak over a natural number field, the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=Ak over the natural number field, the device comprising:
-
initializing means for storing an integer value 1 as an initial value in a variable X and a variable B2;
repetition control means for controlling calculation means, storage means, and exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the exponentiation Ak, the result of the exponentiation Ak being stored in the variable X at the completion of the repetitions;
the calculation, means for performing the multiplication using the variable X and the same variable X, performing the multiplication again using the initial multiplication result and an operand stored in the variable B2, and storing the further multiplication result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
-
-
18. A modular exponentiation device for exponentiating Ak over a residue field,
the residue field being formed from a predetermined set and a multiplication over the residue field performed using elements of the set, the exponentiation Ak involving k number of repetitions of the multiplication performed using the element A of the residue field and an integer value 1, and the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=Ak over the residue field, the device comprising: -
initializing means for storing the integer 1 as an initial value in a variable X and a variable B2;
repetition control means for controlling calculation means, storage means, and exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the exponentiation Ak, the result of the exponentiation Ak being stored in the variable X at the completion of the repetitions;
the calculation means for performing the multiplication using the variable X and the same variable X, performing the multiplication again using the initial multiplication result and an operand stored in the variable B2, and storing the further multiplication result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
-
-
19. An elliptic curve exponentiation device for multiplying k×
- A on an elliptic curve,
the elliptic curve being formed from a predetermined set and an addition on the elliptic curve performed using elements of the set, the multiplication k×
A on the elliptic curve involving k number of repetitions of the addition performed using the element A of the elliptic curve and a zero element, being a point at infinity above the elliptic curve, and the discrete logarithm problem being to determine the element k, when k exists, such that an element Y=k×
A on the elliptic curve, the device comprising;
initializing means for storing the zero element as an initial value in a variable X and a variable B2;
repetition control means for controlling calculation means, storage means, and exchange means to repeat, for the number of bits in a bit sequence resulting when the element k is represented in binary, a step composed of the respective operations of calculating, storing, and exchanging, so as to perform the multiplication k×
A, the result of the multiplication k×
A being stored in the variable X at the completion of the repetitions;
the calculation means for performing the addition using the variable X and the same variable X, performing the addition again using the initial addition result and an operand stored in the variable B2, and storing the further addition result in the variable X;
the storage means for selecting an operand to be used by the calculation means in the following step and storing the selected operand in a variable B1, the operation conducted by the storage means being completed during a duration of the operation conducted by the calculation means; and
the exchange means for exchanging the operand in the variable B2 for the operand in the variable B1 when the operations conducted by the calculation means and the storage means have been completed.
- A on an elliptic curve,
Specification