Patent ID: 7177422

Claim:
An elliptic curve encryption processing method for encrypting and/or decrypting data using a Montgomery elliptic curve By 2 =x 3 +Ax 2 +x on a prime field, said elliptic curve encryption processing method comprising: computing simultaneously in the computation of kP+lQ a point kP which is a scalar quantity k times as great as a point P on said Montgomery elliptic curve and a point lQ which is a scalar quantity l times as great as a point Q on said Montgomery elliptic curve, said computing including: (i) an initial point computation step of calculating a set G t+1 of four initial points on the basis of said point P and said point Q; (ii) a bit value detection step of detecting a combination of each bit value of k and l of binary representation data of said scalar quantities k and l; and (iii) an iterative computation process step of selecting a computation relation of a set G t of the next four points based on said set G t+1 of four initial points according to a combination of each bit value of said binary representation data of k and l detected in said bit value detection step and performing a computation process of the next four points in accordance with said computation relation of said set G t , and selecting a computation relation of a set G i of the next four points based on a set G i+1 of the four computed points and repeatedly performing a computation process of the next four points according to the number of bits of k or l of said binary representation data in accordance with said computation relation of said set G i ; in which, when the high-order bit values of the high orders t to i when each bit of said binary representation data of k and l is k: (k t . . . k o ) 2 and l: (l t . . . l o ) 2 are m i =(k t . . . k i ) 2 and n i =(l t . . . l i ) 2 , said set G i of four points is formed of the four points which are indicated in the expressions below by using said point P and said point Q: m i P+n i Q m i P+(n i +1)Q (m i +1)P+n i Q (m i +1)P+(n i +1)Q, and said iterative computation process step includes computing said set G i of the next four points repeatedly on the basis of said set G i+1 of the four computed points in order to eventually compute a set G 0 of four points, and in which one point which is a constituent of said set G 0 of four points is computed as W=kP+lQ; and encrypting and/or decrypting the data using the computing results.