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

摘要

A scalar multiplication unit references a t-bit sequence representing a random number k one bit at a time from the most significant bit, and upon each referencing, sets in a work variable R[0] a value obtained by doubling a specific point G on an elliptic curve set in a scalar multiplication variable R, and sets in a work variable R[1] a value obtained by adding the specific point G to the work variable R[0]. The scalar multiplication unit 122 sets the work variable R[0] in the scalar multiplication variable R if the value of the referenced bit is 0, and sets the work variable R[1] in the scalar multiplication variable R if the value of the referenced bit is 1. A scalar multiple point output unit 123 outputs as a scalar multiple point kG a value obtained by subtracting a constant value 2tG from the scalar multiplication variable R.

主权项

1. 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, the apparatus comprising:
circuitry configured to implement
a constant storage unit that pre-stores a coordinate value 2tG obtained by scalar multiplication of the coordinate value G of the specific point by 2 to a power of t;an initial setting unit that sets the coordinate value G of the specific point in a scalar multiplication variable R;a scalar multiplication unit that references 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, sets in a zeroth work variable R[0] a coordinate value obtained by doubling the scalar multiplication variable R, sets in a first work variable R[1] a coordinate value obtained by adding a coordinate value of multiplying the coordinate value G of the specific point by a predetermined number to the coordinate value set in the zeroth work variable R[0], sets 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 sets 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;a scalar multiple point output unit that performs a subtraction of the coordinate value 2tG stored in the constant storage unit from the scalar multiplication variable R set by the scalar multiplication unit, and outputs a coordinate value kG for the cryptographic digital signature, obtained by the subtraction; anda multiple-precision residue operation unit 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 multiple-precision residue operation unit setting 0 in a temporary variable temp if the multiple-precision integer a is even, setting the prime number p in the temporary variable temp if the multiple-precision integer a is odd, setting in a residue operation variable c a value obtained by adding the temporary variable temp to the multiple-precision integer a, and outputting as the residue value r, a value obtained by right-shifting by 1 bit the residue operation variable c that is set, wherein the initial setting unit sets a multiple-precision integer representing the coordinate value G of the specific point in the scalar multiplication variable R; wherein the scalar multiplication unit, using operations of the multiple-precision residue operation unit, calculates the coordinate value obtained by doubling the scalar multiplication variable R and the coordinate value obtained by adding the coordinate value G of the specific point to the zeroth work variable R[0]; and wherein the scalar multiple point output unit, using operations of the multiple-precision residue operation unit, calculates the coordinate value kG for the cryptographic digital signature, obtained by subtracting the coordinate value 2tG from the scalar multiplication variable R.