Patent ID: 7835517

Claim:
An encryption processing apparatus for performing one of a scalar multiplication of kP+lQ based on two points P and Q on an elliptic curve defined by elliptic curve cryptography and scalar values k and l, and a scalar multiplication of kD 1 +lD 2 based on divisors D 1 and D 2 defined by hyperelliptic curve cryptography and scalar values k and l, the encryption processing apparatus comprising: an encryption processor including a scalar value controller configured to generate joint regular form of (k, l) k=<kn, . . . k0> and l=<ln, . . . l0>, which are set so that all the bits of the scalar values k and l are represented by 0, +1, or −1, and the combination (ki, li) of bits at positions corresponding to the scalar values k and l is set to satisfy (ki, li)=(0, ±1) or (±1, 0); and a computation execution section configured to perform a scalar multiplication of kP+lQ or kD 1 +lD 2 with the joint regular form of (k, l) generated by the scalar value controller, wherein, it is determined whether or not both the scalar values k and l are even or odd, and when both the scalar values k and l are even or odd, the scalar value controller changes one of the scalar values so as to be set to a combination of an even number and an odd number, and generates joint regular form of (k, l) k=<kn, . . . k0> and l=<ln, . . . l0> in which the combination (ki, li) of bits at positions corresponding to the changed scalar values k and l satisfies (ki, li)=(0, ±1) or (±1, 0), and the computation execution section performs a scalar multiplication of kP+lQ or kD 1 +lD 2 on the basis of the changed scalar values, performs a correction computation, and computes scalar double-and-add results by applying the scalar values before being changed.