Information security device, exponentiation device, modular exponentiation device, and elliptic curve exponentiation device

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, 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 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, wherein
• the 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.

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, 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 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, wherein
• the 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 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, 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 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, wherein
• the 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.

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.

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.

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.