Device and method for calculation on elliptic curve

Abstract

In scalar multiplication method using a Montgomery-type elliptic curve, a high-speed elliptic curve calculation device that can use effectively a table that stores coordinates of a certain scalar multiple points like points multiplied by exponentiation of two to a certain point G and so forth. An elliptic curve calculation device 200 that receives an arbitrary integer k of n bits and outputs scalar-multiplied points against a point G on a Montgomery-type elliptic curve E on an infinite field F that is given in advance comprises: a calculation procedure generation unit 210 that generates a calculation procedure that addition on the elliptic curve E with either of G, 2*G, 22*G, . . . , 2n-1*G as the first addition element is repeated and a scalar multiplication unit 220 that calculates the scalar-multiplied points k*G by repeating addition on the elliptic curve E, referring to a table memorizing unit 220b that stores values (coordinates) of exponentiation of two against the point G and complying with the generated calculation procedure.

Description

[0001] (1) Field of the Invention[0002] The present invention relates to a device that performs a calculation on an elliptic curve, and in particular relates to a device that calculates a scalar-multiplied point that is generated by multiplying a scalar against a point on a Montgomery-type elliptic curve[0003] (2) Description of the Prior Art[0004] 1. Public-Key Encryption[0005] Recently, data communication based on computer technology and communication technology becomes widely available, and in this data communication, a secret communication mode or a digital signature mode is used. Here, the secret communication mode is a mode to communicate without leaking communication contents to a person other than the other specified party of the communication. Moreover, the digital signature mode is a mode that shows the correctness of communication contents to the other party of the communication and certifies the identity of the originator.[0006] In these secret communication mode or digi...

AI Technical Summary

Problems solved by technology

The reason that makes the discrete logarithm problem a premise of the security of the public-key encryption is that the above-mentioned problem to the finite field that has many elements is extremely difficult.

Additionally, on a Montgomery-type elliptic curve, y coordinate cannot be obtained.

Additionally, in the scalar multiplication, there is no method in which calculation of a scalar-multiplied point like (2.sup.i)*G in advance is effective.

Consequently, a Montgomery-type elliptic curve is high-speed in the method that does not have the table of the scalar-multiplied points like the Prior Art 3 but there is a problem that no effective method exists in the case of having the table.

In other words, there is a problem that the conventional scalar multiplication method of the Montgomery-type elliptic curve is not effective in the case of having the table of points multiplied by exponentiation of two for a given point.

Moreover, as is apparent because of the above explanation, in the addition and the double calculation on the Montgomery-type elliptic curve, x coordinate (in the case of a projection coordinates that is a 3-term coordinates, x coordinate and z coordinate) can be obtained but there is a problem that y coordinate cannot be obtained.

Consequently, the conventional scalar multiplication on a Montgomery-type elliptic curve cannot be applied to the elliptic curve encryption that needs y coordinate of a scalar-multiplied point.

Images