Arithmetic apparatus, elliptic scalar multiplication method of arithmetic apparatus, elliptic scalar multiplication program, residue operation method of arithmetic apparatus, and residue operation program

An elliptic scalar multiplication method of an apparatus that calculates a coordinate value kG, for a cryptographic digital signature, obtained by scalar multiplication of a coordinate value G of a specific point included in an elliptic curve by a multiplier value k represented by a t-bit bit sequence, wherein the apparatus includes circuitry implementing an initial setting unit, a scalar multiplication unit, a scalar multiple point output unit, and a multiple-precision residue operation unit, comprising:

• calculating, by the multiple-precision residue operation unit, as a residue value r, a remainder that is obtained when a value obtained by dividing a multiple-precision integer a by two is divided by a prime number p, set 0 in a temporary variable temp if the multiple-precision integer a is even, set the prime number p in the temporary variable temp if the multiple-precision integer a is odd, set in a residue operation variable c a value obtained by adding the temporary variable temp to the multiple-precision integer a, and output as the residue value r, a value obtained by right-shifting by 1 bit the residue operation variable c that is set,
• setting, by the initial setting unit, a multiple-precision integer representing the coordinate value G of the specific point in a scalar multiplication variable R;
• referencing, by the scalar multiplication unit, the t-bit bit sequence representing the multiplier value k in units of a predetermined number of bits from a most significant bit;
• and
• each time the predetermined number of bits of the bit sequence are referenced,
• calculating, by using the multiple-precision residue operation unit, a first coordinate value obtained by doubling the scalar multiplication variable R,
• setting the first coordinate value calculated in a zeroth work variable R[0],
• calculating by using the multiple-precision residue operation unit a second coordinate value obtained by adding a coordinate value of multiplying the coordinate value G of the specific point by a predetermined number to the first coordinate value set in the zeroth work variable R[0],
• setting the second coordinate value calculated in a first work variable R[1],
• setting the zeroth work variable R[0] in the scalar multiplication variable R if a value of the predetermined number of bits referenced is zero, and
• setting the first work variable R[1] in the scalar multiplication variable R if the value of the predetermined number of bits referenced is non-zero;
• calculating, by the scalar multiple point output unit, using operations of the multiple-precision residue operation unit, a third coordinate value obtained by subtracting a constant value 2tG obtained by scalar multiplication of the coordinate value G of the specific point by 2 to a power oft from the scalar multiplication variable R set by the scalar multiplication unit;
• and
• outputting the calculated third coordinate value as the coordinate value kG for the cryptographic digital signature.

An apparatus for generation of a cryptographic digital signature by calculating, as a residue value r, a remainder that is obtained when a value obtained by dividing a multiple-precision integer a by two is divided by a prime number p, the apparatus comprising:

• circuitry configured to implement
• a multiple-precision integer determination unit that sets 0 in a temporary variable temp if the multiple-precision integer a is even, and sets the prime number p in the temporary variable temp if the multiple-precision integer a is odd,
• a residue operation variable setting unit that performs an addition of the temporary variable temp to the multiple-precision integer a, and sets a value obtained by the addition in a residue operation variable c, and
• a shift operation unit that performs a right shift of the residue operation variable c by 1 bit, and outputs a value obtained by the right shift as the residue value r.

A method for generation of a cryptographic digital signature by implementation of a residue operation method of an apparatus that calculates, as a residue value r, a remainder that is obtained when a value obtained by dividing a multiple-precision integer a by two is divided by a prime number p, the residue operation method comprising:

• by circuitry configured to implement a multiple-precision integer determination unit, setting 0 in a temporary variable temp if the multiple-precision integer a is even, and setting the prime number p in the temporary variable temp if the multiple-precision integer a is odd;
• by the circuitry configured to implement a residue operation variable setting unit, performing an addition of the temporary variable temp to the multiple-precision integer a, and setting a value obtained by the addition in a residue operation variable c;
• and
• by the circuitry configured to implement a shift operation unit, performing a right shift of the residue operation variable c by 1 bit, and outputting a value obtained by the right shift as the residue value r.