Patent ID: 7486789

Claim:
A device for securing data, the device comprising: an elliptic curve calculation unit for receiving an arbitrary integer K of n bits and outputting scalar-multiplied points k*G on a Montgomery-type elliptic curve E of B×y 2 =x 3 +A×x 2 +x on a finite field F, where G is a predetermined point on the Montgomery-type elliptic curve E, wherein the elliptic curve calculation unit includes: a calculation procedure generation unit for expanding the scalar-multiplied points k*G to an addition formula by dividing the scalar-multiplied points k*G into a sum of a first addition element and a second addition element and further repeatedly dividing the second addition element into a first addition element and a second addition element, and for generating a calculation procedure of repeating addition on the Montgomery-type elliptical curve E according to the expanded addition formula, the first addition element being any one of G, 2*G, 2 2 *G, . . . , 2 n−1 *G, and the second addition element being different from the first addition element, wherein the calculation procedure is an array indicating a sequence in which all addition elements obtained by the dividing are to be added, the array including array elements corresponding in number to the number of the divisions, each of the array elements including information identifying a corresponding addition obtained by the dividing; and a scalar multiplication unit for calculating the scalar-multiplied points k*G according to the calculation procedure generated by the calculation procedure generation unit, the scalar multiplication unit has a table memorizing unit for memorizing at least part of the first addition element, and for performing addition on the Montgomery-type elliptic curve E with a point memorized in the table memorizing unit as the first addition element, and the point memorized in the table memorizing unit is any point of an x-coordinate or any point of the x-coordinate and a z-coordinate; and a utilization unit for executing at least one of encrypting the data, decrypting the data, generating a digital signature for the data, performing digital signature verification for the data, and performing a key sharing for the data, based on the scalar-multiplied points k*G outputted by the elliptic curve calculation unit, and outputting a result of the execution.