Information security device and elliptic curve operating device

An elliptic curve calculation apparatus that processes information securely and reliably using an elliptic curve calculation, such that security of the elliptic curve calculation is based on a discrete logarithm problem on an elliptic curve E defined over a residue field Fp with a prime p being a modulus, and such that the elliptic curve calculation is for calculating a point k*C by multiplying a point C on the elliptic curve E with a coefficient k that is a positive integer less than the prime p, the elliptic curve calculation apparatus comprising:

• a point storage unit operable to store the point C on the elliptic curve E;
• a digit storage unit operable to store a value of each digit located at each of a plurality of digit positions of the coefficient k;
• an acquisition unit operable to acquire, from the digit storage unit, a value w of a digit located at one of the plurality of digit positions, the digit located at the one of the plurality of digit positions being an acquired digit;
• multiplication units equal in number to a number of types of possible values expressed by the acquired digit;
• a selection unit operable to select one of the multiplication units that corresponds to the acquired value w;
• and
• a repeat control unit operable to control the acquisition unit, the selection unit and the multiplication units so as to repeatedly perform a procedure of acquiring the value w from among the plurality of digit positions of the coefficient k, selecting the one of the multiplication units that corresponds to the acquired value w, and multiplying in the selected multiplication unit, the procedure being repeated so as to be performed with respect to all digit positions of the plurality of digit positions of the coefficient k,
• wherein each of the multiplication units is operable to multiply the point C with the acquired value w, so as to obtain a multiplication result, and add the multiplication result in a position, corresponding to the digit position of the acquired value on the elliptic curve E, and
• wherein, when a non-negative integer t exists that fulfills a condition that the acquired value w_can be divided by 2t and cannot be divided by 2t+1, the selected multiplication unit performs calculations that include, on the elliptic curve E, adding a point obtained by multiplying a point Q with w/2t or subtracting a point obtained by multiplying the point Q with |w/2t|.

An integrated circuit that processes information securely and reliably using an elliptic curve calculation, such that security of the elliptic curve calculation is based on a discrete logarithm problem on an elliptic curve E defined over a residue field Fp with a prime p being a modulus, and such that the elliptic curve calculation is for calculating a point k*C by multiplying a point C on the elliptic curve E with a coefficient k that is a positive integer less than the prime p, the integrated circuit comprising:

• a point storage unit operable to store the point C on the elliptic curve E;
• a digit storage unit operable to store a value of each digit located at each of a plurality of digit positions of the coefficient k;
• an acquisition unit operable to acquire, from the digit storage unit, a value w of a digit located at one of the plurality of the digit positions, the digit located at the one of the plurality of digit positions being an acquired digit;
• multiplication units equal in number to a number of types of possible values expressed by the acquired digit;
• a selection unit operable to select one of the multiplication units that corresponds to the acquired value w;
• and
• a repeat control unit operable to control the acquisition unit, the selection unit and the multiplication units, so as to repeatedly perform a procedure of acquiring the value w from among the plurality of digit positions of the coefficient k, selecting the one of the multiplication units that corresponds to the acquired value w, and multiplying in the selected multiplication unit, the procedure being repeated so as to be performed with respect to all digit positions of the plurality of digit positions of the coefficient k,
• wherein each of the multiplication units is operable to multiply the point C with the acquired value w, so as to obtain a multiplication result, and add the multiplication result in a position, corresponding to the digit position of the acquired value w, on the elliptic curve E, and
• wherein, when a non-negative integer t exists that fulfills a condition that the acquired value w_can be divided by 2t and cannot be divided by 2t+1, the selected multiplication unit performs calculations that include, on the elliptic curve E, adding a point obtained by multiplying a point Q with w/2t or subtracting a point obtained by multiplying the point Q with |w/2t|.

A method used in an information security apparatus that processes information securely and reliably using an elliptic curve calculation, such that security of the elliptic curve calculation is based on a discrete logarithm problem on an elliptic curve E defined over a residue field Fp with a prime p being a modulus, and such that the elliptic curve calculation is for calculating a point k*C by multiplying a point C on the elliptic curve E with a coefficient k that is a positive integer less than the prime p,

• wherein the information security apparatus includes:
• a point storage unit operable to store the point C on the elliptic curve E;
• and
• a digit storage unit operable to store a value of each digit located at each of a plurality of digit positions of the coefficient k,
• wherein the method comprises:
• an acquisition step of acquiring, from the digit storage unit, a value w of a digit located at one of the plurality of digit positions, the digit located at the one of the plurality of digit positions being an acquired digit;
• multiplication steps equal in number to a number of types of possible values expressed by the acquired digit;
• a selection step of selecting one of the multiplication steps that corresponds to the acquired value w;
• and
• a repeat control step of controlling the acquisition step, the selection step and the multiplication steps, so as to repeatedly perform a procedure of acquiring the value w from among the plurality of digit positions of the coefficient k, selecting the one of the multiplication steps that corresponds to the acquired value w, and multiplying in the selected multiplication step, the procedure being repeated so as to be performed with respect to all digit positions of the plurality of digit positions of the coefficient k,
• wherein each of the multiplication steps is for multiplying the point C with the acquired value w, so as to obtain a multiplication result, and adding the multiplication result in a position, corresponding to the digit position of the acquired value w, on the elliptic curve E, and
• wherein, when a non-negative integer t exists that fulfills a condition that the acquired value w_can be divided by 2t and cannot be divided by 2t+1, the selected multiplication step performs calculations that include, on the elliptic curve E, adding a point obtained by multiplying a point Q with w/2t or subtracting a point obtained by multiplying the point Q with |w/2t|.

A non-transitory computer-readable recording medium having a computer program recorded thereon, the computer program being used in an information security apparatus that processes information securely and reliably using an elliptic curve calculation, such that security of the elliptic curve calculation is based on a discrete logarithm problem on an elliptic curve E defined over a residue field Fp with a prime p being a modulus, and such that the elliptic curve calculation is for calculating a point k*C by multiplying a point C on the elliptic curve E with a coefficient k that is a positive integer less than the prime p,

• wherein the information security apparatus includes:
• a point storage unit operable to store the point C on the elliptic curve E;
• and
• a digit storage unit operable to store a value of each digit located at each of a plurality of digit positions,
• wherein the computer program causes the information security apparatus to execute a method comprising:
• an acquisition step of acquiring, from the digit storage unit, a value w of a digit located at one of the plurality of digit positions, the digit located at the one of the plurality of digit positions being an acquired digit;
• multiplication steps equal in number to a number of types of possible values expressed by the acquired digit;
• a selection step of selecting one of the multiplication steps that corresponds to the acquired value w;
• and
• a repeat control step of controlling the acquisition step, the selection step and the multiplication steps, so as to repeatedly perform a procedure of acquiring the value w from among the plurality of digit positions of the coefficient k, selecting the one of the multiplication steps that corresponds to the acquired value w, and multiplying in the selected multiplication step, the procedure being repeated so as to be performed with respect to all digit positions of the plurality of digit positions of the coefficient k,
• wherein each of the multiplication steps is for multiplying the point C with the acquired value w, so as to obtain a multiplication result, and adding the multiplication result in a position, corresponding to the digit position of the acquired value w, on the elliptic curve E, and
• wherein, when a non-negative integer t exists that fulfills a condition that the acquired value w_can be divided by 2t and cannot be divided by 2t+1, the selected multiplication step performs calculations that include, on the elliptic curve E, adding a point obtained by multiplying a point Q with w/2t or subtracting a point obtained by multiplying the point Q with |w/2t|.