ARITHMETICAL DEVICE, ARITHMETICAL DEVICE ELLIPTICAL SCALAR MULTIPLICATION METHOD AND ELLIPTICAL SCALAR MULTIPLICATION PROGRAM, ARITHMETICAL DEVICE MULTIPLICATIVE OPERATION METHOD AND MULTIPLICATIVE OPERATION PROGRAM, AS WELL AS ARITHMETICAL DEVICE ZERO DETERMINATION METHOD AND ZERO DETERMINATION PROGRAM

摘要

An elliptic scalar multiplication kG can be processed in a fixed amount of computation time regardless of the value of a random number k, and timing analysis of the elliptic scalar multiplication kG can be prevented. An initial setting unit 121 sets a specific point G on an elliptic curve in a scalar multiplication variable R. A scalar multiplication unit 122 references a t-bit bit sequence representing a random number k one bit at a time from the most significant bit, and each time one bit is referenced, sets in a work variable R[0] a value obtained by doubling the scalar multiplication variable R, and sets in a work variable R[1] a value obtained by adding the specific point G to the value set in the work variable R[0]. Then, 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 performs a subtraction of a constant value 2 t G from the scalar multiplication variable R, and outputs a value obtained by the subtraction as a scalar multiple point kG.