JP2003288014A - Elliptic curve calculation device and elliptic curve calculation method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a high speed elliptic curve calculation device which 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 in scalar multiplication method using a Montgomery-type elliptic curve. <P>SOLUTION: An elliptic curve calculation device 200 that receives an arbitrary integer k of n bits and outputs scalar-multiplied points k×G against a point G on a Montgomery-type elliptic curve E on an finite 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, (2<SP>2</SP>)×G,..., (2<SP>(n-1)</SP>)×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. <P>COPYRIGHT: (C)2004,JPO

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for performing an operation on an elliptic curve, and more particularly to an apparatus for calculating a scalar multiplication point for a point on a Montgomery type elliptic curve.

[0002]

2. Description of the Related Art Public key cryptography In recent years, data communication based on computer technology and communication technology has become widespread, and in this data communication, a secret communication method or a digital signature method is used. Here, the secret communication method is a method for performing communication without leaking the communication content to anyone other than a specific communication partner. The digital signature method is a communication method that shows the validity of the communication contents to the communication partner and proves the identity of the sender.

An encryption method called public key encryption is used for these secret communication methods or digital signature methods. Public key cryptography is a method for easily managing different encryption keys for each communication partner when there are many communication partners, and is an essential basic technology for communicating with many communication partners. In secret communication using public key cryptography, the encryption key and the decryption key are different, and the decryption key is kept secret, but the encryption key is disclosed.

The discrete logarithm problem is used as the basis for the security of this public key cryptography. Typical discrete logarithm problems include one defined on a finite field and one defined on an elliptic curve (for example, Non-Patent Document 1). 2. Discrete Logarithm Problem on Elliptic Curve The discrete logarithm problem on elliptic curve is described below.

Let el be a prime number and E be an elliptic curve defined on a finite field GF (p). Consider a set of points on E in which the formal point O is added to all the points whose both x and y coordinates belong to GF (p), and this set forms a group with the point O as a zero element. The order of the elliptic curve indicates the original number of the above set. When G = (gx, gy), -G is -G =
It is defined as (gx, -gy).

The discrete logarithm problem on the elliptic curve E is the elliptic curve E when the order of the elliptic curve E is divisible by a large prime number.
The base G is the element G included in. At this time, for a given element Y included in the elliptic curve E, if there is a natural number x such that (Equation 1) Y = x * G, the problem is to obtain x. Here, p is a prime number and GF (p) is a finite field having p elements. Further, in this specification, the symbol * indicates an operation for adding an element included in an elliptic curve a plurality of times, and x * G adds an element G included in an elliptic curve x times, as shown in the following equation. Means that. A point such as x * G = G + G + G + ... + G x * G is called a scalar multiplication point of G. The discrete logarithm problem is used as the basis for the security of public key cryptography because the problem is extremely difficult for a finite field GF (p) having many elements.

3. Elgamal Signature Applying Discrete Logarithm Problem on Elliptic Curve Hereinafter, a digital signature scheme based on Elgamal signature applying the discrete logarithm problem on elliptic curve will be described with reference to FIG. This figure is a sequence diagram showing the procedure of the digital signature method based on the above-mentioned El Gamal signature.
User A110, Management Center 120 and User B130
Are connected by a network. Let p be a prime number and E be an elliptic curve over the finite field GF (p). The base point of E is G, and the order of E is q. That is, q is the smallest positive integer that satisfies (Equation 2) q * G = 0.

(1) Generation of public key by the management center 120 The management center 120 is notified by the user A11 who has been notified in advance.
User A11 according to Equation 3 using secret key xA of 0
A public key YA of 0 is generated (steps S141 to S14).
2). (Formula 3) YA = xA * G After that, the management center 120 publishes the prime number p, the elliptic curve E, and the base point G as system parameters,
In addition, the public key Y of the user A110 is transmitted to the other user B130.
A is disclosed (steps S143 to S144).

(2) Signature Generation by User A110 The user A110 generates a random number k (step S14).
5). Next, the user A110 calculates (Equation 4) R1 = (rx, ry) = k * G (step S146), and calculates s from (Equation 5) s × k = m + rx × xA (mod q). (Step S147). Where m
Is a message transmitted by the user A 110 to the user B 130. However, x has shown multiplication. further,
The user A 110 transmits the obtained (R1, s) as a signature together with the message m to the user B 130 (step S148).

(3) Signature verification by user B130 The user B130 confirms the identity of the user A110 who is the sender by determining whether or not (Equation 6) s * R1 = m * G + rx * YA is satisfied ( Step S14
9). This is (Equation 7) s * R1 = {((m + rx * xA) / k) * k} * G = (m + rx * xA) * G = m * G + (rx * xA) * G = m * G + rx * It is clear from YA.

4. Addition of points on elliptic curve and calculation amount by doubling operation In each of public key generation, signature generation, and signature verification in the digital signature scheme by the Elgamal signature that applies the discrete logarithm problem on the elliptic curve shown above, , The multiplication of points on the elliptic curve is performed. For example, "x
"A * G", "k * G" shown in Equation 4, "s * R" shown in Equation 6
1 ”,“ m * G ”, and“ rx * YA ”are scalar multiplication operations of points on the elliptic curve.

The calculation formula of the elliptic curve is described in detail in Non-Patent Document 2. The elliptic curve calculation formula will be described below. The equation of the elliptic curve is y ^ 2 =
x ^ 3 + a × x + b and the coordinates of an arbitrary point P are (x
1, y1), and the coordinates of an arbitrary point Q are (x2, y2). Here, the coordinate of the point R determined by R = P + Q is (x
3, y3).

In this specification, the symbol ^ indicates a power operation, and 2 ^ 3 means 2 × 2 × 2, for example. When P ≠ Q, R = P + Q is an addition operation. The formula of addition is shown below. x3 = {(y2-y1) / (x2-x1)} ^ 2-x1-x2 y3 = {(y2-y1) / (x2-x1)} (x1-x3) -y1 When P = Q, R = P + Q = P + P = 2 × P, and R
= P + Q is a doubling operation. The formula for doubling is shown below. x3 = {(3x1 ^ 2 + a) / 2y1} ^ 2-2x1 y3 = {(3x1 ^ 2 + a) / 2y1} (x1-x3) -y1

The above calculation is a calculation on a finite field in which an elliptic curve is defined. As shown above, in the affine coordinates that are binary coordinates, that is, in the coordinates described so far, addition on the elliptic curve (hereinafter, “elliptic curve addition”)
Also called. ), One reciprocal calculation on a finite field is required for each addition on the elliptic curve. In general,
The reciprocal calculation on the finite field requires about 10 times the calculation amount as compared with the multiplication calculation on the finite field.

Therefore, for the purpose of reducing the calculation amount, coordinates of a triplet called projective coordinates are used. Projective coordinates are coordinates consisting of a triplet X, Y, Z, and a certain number n with respect to coordinates (X, Y, Z) and coordinates (X ′, Y ′, Z ′). Exists, X '= nX, Y' = n
If there is a relation of Y, Z '= nZ, (X, Y, Z)
= (X ', Y', Z ').

Affine coordinates (x, y) and projective coordinates (X,
Y, Z) are (x, y) → (x, y, 1) (X, Y, Z) → (X / Y, Y / Z) (when Z ≠ 0) and correspond to each other. is doing. Where the symbol → is
It is used in the following meaning. When one element of the element P2 corresponds to the element P1, it is expressed as P1 → P2. Reigen O is
It can be expressed in projective coordinates, and O = (0,1,0).

Hereinafter, it is assumed that all elliptic curve calculations are performed in projective coordinates. Next, the addition formula and the doubling formula of the elliptic curve on the projective coordinates will be described. These formulas are, of course, consistent with the addition and doubling formulas in affine coordinates mentioned earlier. The operation of multiplication by a power (scalar multiplication of a point on an elliptic curve) can be realized by repeating addition and doubling of points on the elliptic curve. In this power operation, the calculation amount of addition does not depend on the parameters of the elliptic curve, but the calculation amount of doubling depends on the parameters of the elliptic curve.

Here, p is a 160-bit prime number,
Let elliptic curve on the finite field GF (p) be E: y ^ 2 = x ^
3 + ax + b, and the elements P and Q on the elliptic curve E are P = (X1, Y1, Z1) and Q = (X2, Y
2, Z2), R = (X3, Y3, Z3) = P + Q is calculated as follows.

(I) When P ≠ Q In this case, an addition operation is performed. (step 1-1) Calculation of intermediate value Calculate the following:   (Equation 8) U1 = X1 × Z2 ^ 2   (Formula 9) U2 = X2 × Z1 ^ 2   (Formula 10) S1 = Y1 × Z2 ^ 3   (Formula 11) S2 = Y2 × Z1 ^ 3   (Formula 12) H = U2-U1   (Formula 13) r = S2-S1  (step 1-2) Calculation of R = (X3, Y3, Z3)   Calculate the following:   (Formula 14) X3 = -H ^ 3-2xU1xH ^ 2 + r ^ 2   (Equation 15) Y3 = -S1 * H ^ 3 + r * (U1 * H ^ 2-X3)   (Formula 16) Z3 = Z1 × Z2 × H

(Ii) When P = Q (that is, R = 2)
P) In this case, the calculation is doubled. (step 2-1) Calculation of intermediate value Calculate the following. (Expression 17) S = 4 * X1 * Y1 ^ 2 (Expression 18) M = 3 * X1 ^ 2 + a * Z1 ^ 4 (Expression 19) T = -2 * S + M ^ 2 (step 2-2) R = (X3 , Y3, Z3) The following is calculated. (Formula 20) X3 = T (Formula 21) Y3 = -8 * Y1 ^ 4 + M * (S-T) (Formula 22) Z3 = 2 * Y1 * Z1

Next, the amount of calculation for performing addition and doubling of an elliptic curve will be described. Where finite field GF (p)
The calculation amount by the above-mentioned one multiplication is represented by 1 Mul, and the calculation amount by the one-time multiplication is represented by 1 × Sq. In a general microprocessor, 1 × Sq≈0.8 × Mul.

According to the above example, the calculation amount of addition on the elliptic curve shown in the case of P ≠ Q is obtained by counting the number of multiplications and the number of multiplications in Equations 8 to 16. Is 12 × Mul + 4 × Sq. This means that the calculation amount of addition in the equations 8, 9, 10, 11, 14, 15, 16 is 1 × Mul + 1 × Sq, 1 respectively.
XMul + 1xSq, 2xMul, 2xMul, 2xM
It is clear from ul + 2 × Sq, 2 × Mul, and 2 × Mul.

Further, according to the above example, the calculation amount of the doubling on the elliptic curve shown in the case of P = Q is calculated by the equations 17 to
In Expression 22, it is 4 × Mul + 6 × Sq, which is obtained by counting the number of multiplications and the number of multiplications. This is because the calculation amount of the doubling in Expressions 17, 18, 19, 21, and 22 is 1 × Mul + 1 × Sq,
1 × Mul + 3 × Sq, 1 × Sq, 1 × Mul + 1 × S
It is clear from q and 1 × Mul.

In the counting of the number of times, for example, for H ^ 3 in equation 14, it can be expanded to H ^ 3 = H ^ 2 × H, so the calculation amount of H ^ 3 is 1 × Mul + 1.
XSq, and Z1 ^ 4 in Equation 18 can be expanded to Z1 ^ 4 = (Z1 ^ 2) ^ 2, so the calculation amount of Z1 ^ 4 is 2Sq.

Regarding H ^ 2 in the equation 14, since H ^ 2 has been calculated in the process of calculating H ^ 3, the calculation amount of H ^ 2 is not counted again. Further, when counting the number of multiplications, the number of multiplications performed by multiplying a certain value by a small value is not counted. The reason will be described below. The small value referred to here is a small fixed value to be multiplied in Expressions 8 to 22,
Specifically, the values are 2, 3, 4, 8 and the like. These values can be represented by a 4-bit binary number at most. on the other hand,
The other variables usually have a value of 160 bits.

Generally, in a microprocessor, multiplication of a multiplier and a multiplicand is performed by repeating shift and addition of the multiplicand. That is, for each bit of the multiplier represented by a binary number, if this bit is 1, the multiplicand represented so that the least significant bit of the multiplicand represented by a binary number matches the position where this bit exists. Shift 1
Get one bit string. For all bits of the multiplier, add at least one bit string thus obtained.

For example, in the multiplication of a 160-bit multiplier and a 160-bit multiplicand, the 160-bit multiplicand is shifted 160 times to obtain 160 bit strings, and the obtained 160 bit strings are added. On the other hand, in the multiplication of the 4-bit multiplier and the 160-bit multiplicand, 160
Shift the multiplicand of bits four times to get four bit strings,
The four obtained bit strings are added.

Since the multiplication is performed as described above, when the multiplication is performed by multiplying a certain value by a small value, the number of times of the repetition is reduced. Therefore, the amount of calculation can be considered to be small, and therefore the number of multiplications is not counted. As described above, in the case of performing the doubling of the elliptic curve, the equation 18 includes the parameter a of the elliptic curve. If, for example, a small value is adopted as the value of this parameter a, the calculation amount of doubling on the elliptic curve becomes
It can be reduced by 1 Mul, resulting in 3 Mul + 6Sq. In addition,
Regarding the addition, even if the parameters of the elliptic curve are changed, the calculation amount does not change. Scalar multiplication of an elliptic curve is performed as follows.

(Prior Art 1) p is a 160-bit prime number, E is an elliptic curve over a finite field GF (p), and E (GF
Let G be an arbitrary element of (p)). K * G is calculated based on these parameters. Here, the binary representation of k is k = k [159] × 2 ^ 159 + ... + k [2] × 2 ^ 2 + k [1] × 2 + k [0] = [k [159], ..., k [ 2], k [1], k [0]] (k [0], ..., K [159] = 0 or 1). Step 1: c = 159 and S = O. Step 2: When k [c] = 1, S ← S + G. Step 3: c ← c-1. Step 4: If c <0, output S and end. Otherwise, set S ← S + S and go to step 2.

In the above calculation amount, assuming that the probability that k [c] = 1 is ½, and one addition of the elliptic curve is EAdd, and doubling is EDob, 80 × EAAdd + 160 × ED
It becomes ob. In general, when p and k are n-bit prime numbers and integers, respectively, the calculation amount is ½ × n × EAAdd + n × EDob.

In the above scalar multiplication operation, (2 ^ i)
When G (i = 1, 2, ..., 159) is calculated in advance and the result is stored in the table, the calculation can be performed as follows.

(Prior Art 2) p is a 160-bit prime number, E is an elliptic curve over a finite field GF (p), and E (GF
Let G be an arbitrary element of (p)). Also, (2 ^ i) * G
It is assumed that the coordinates (i = 1, 2, ..., 159) are calculated in advance. At this time, based on these parameters, k
* Calculate G. Step 1: c = 159 and S = O. step2: When k [c] = 1, S ← S + 2 ^ c * G
And Step 3: c ← c-1. Step 4: If c <0, output S and end. Otherwise, go to step 2.

In the above method, since elliptic curve addition is not performed, the calculation amount is 80 × EAAdd. Generally p, k
Are respectively n-bit prime numbers and integers, the calculation amount is 1/2 × n × EDob. Thus, (2 ^
i) Since * G is calculated in advance, the amount of calculation can be reduced. The prior art 2 can be used in the scalar multiplication operation of the base point G of the elliptic curve in the 3 Elgamal signature. This is because the base point G is a system parameter.

5. Montgomery type elliptic curve The equation of the above elliptic curve is y ^ 2 = x ^ 3 + ax
Only those in the form of x + b. This elliptic curve is called the Wire-Strass type elliptic curve. On the other hand, an elliptic curve whose equation is Em: B × y ^ 2 = x ^ 3 + A × x ^ 2 + x is called a Montgomery-type elliptic curve. The point G on the elliptic curve Em is taken, and the n1 times point and the n2 times point thereof are respectively n1 * G = (X1, Y1, Z1), n
2 * G = (X2, Y2, Z2), (n1-n2) * G =
When expressed by (X3 ′, Y3 ′, Z3 ′), (n1 + n2) * G = (X3, Y3, Z3) = n1 * G
+ N2 * G is calculated as follows. (I) When n1 ≠ n2 (addition) (step1-1) Calculation of intermediate value U1 = X1 + Z1 U2 = X2 + Z2 V1 = X1-Z1 V2 = X2-Z2 (step1-2) (n1 + n2) * G = (X3) Y
3, Z3) X3 = Z3 ′ × (V1 × U2 + U1 × V2) ^ 2 Z3 = X3 ′ × (V1 × U2-U1 × V2) ^ 2 (ii) When n1 = n2 (double calculation) ( Step 2-1) Calculation of intermediate value U1 = X1 + Z1 V1 = X1-Z1 (step2-2) (n1 + n2) * G = (X3, Y
3, Z3) calculation X3 = V1 ^ 2 × U1 ^ 2 Z3 = (4 × X1 × Z1) × (V1 ^ 2 + (A + 2) /
Since “(A + 2) / 4” of 4 × (4 × X1 × Z1) step 2-2 can be calculated in advance, the calculation amount of each is 4 × when ignored.
Mul + 2 × Sq (3 × Mul + 2 when Z3 ′ = 1)
× Sq), the doubling becomes 3 × Mul + 2 × Sq. As described in 4, the calculation amount for addition and doubling of the points of the Wire-Strass type elliptic curve is 12 × Mul + 4, respectively.
× Sq, 4 × Mul + 6 × Sq. Therefore, the Montgomery-type elliptic curve is faster in point addition and doubling.
Even in the Montgomery-type elliptic curve, (X1, Y
(-1) times (1,1, Z1) is (X1, -Y1, Z1). In addition, the Y coordinate cannot be obtained from the Montgomery elliptic curve. The Montgomery elliptic curve is described in detail in Non-Patent Document 3.

As described above, the Montgomery-type elliptic curve can be operated at high speed. However, in the addition of n1 * G and n2 * G, the coordinates of (n1-n2) * G are required, and therefore the binary expansion cannot be performed in the scalar multiplication operation like the Wire-Strass elliptic curve. For example, when calculating 5 * G, since 5 = 2 × 2 + 1, 2 * G is calculated, then 2 * (2 * G) = 4 * G, and then (4
* G) + G is calculated. However, (2 * 2 * G) and G
And the difference of those points (2 × 2-1) * G
= 3 * G must be obtained. Therefore, the scalar multiplication operation method like the prior art 1 cannot be used.

Therefore, the calculation is performed as follows. (Prior Art 3) p is an n-bit prime number, and E is GF
(P) Montgomery-type elliptic curve, G to E (GF
(P)). k = 2 ^ (n-1) + k [1] ×
2 ^ (n-2) + ... + k [n-2] × 2 + k [n-
1], k * G is calculated.

S [i] and T [i] are defined as follows. S [i] = (2 ^ i + k [1] × 2 ^ (i-1) + ...
+ K [i−1] × 2 + k [i]) * G T [i] = S [i] + G step1: i = 1 and S [0] = G. Step 2: Calculate T [0] = 2 * G. step3: It is determined whether k [i + 1] = 0 and k [i
When +1] = 0, the following is done. S [i + 1] = 2 * S [i] T [i + 1] = S [i] + T [i] Otherwise, calculate as follows: S [i + 1] = S [i] + T [i] T [i + 1 ] = 2 * T [i] step4: i ← i + 1. Step 5: It is determined whether i> n−1, and if i> n−1, S [n] is output as k * G. Otherwise, go to step 3.

FIG. 33 is a calculation flow chart schematically showing the calculation procedure of the scalar multiplication operation in the prior art 3 as described above. Here, it is shown that addition or doubling is repeated from right to left. In this figure,
Solid arrows indicate additions on the elliptic curve, dotted arrows indicate doubling on the elliptic curve, and numbers in circles on the arrows indicate the order of additions (total number of additions made so far). , The numbers in parentheses above the arrows indicate the order of doubling (the total number of doublings performed so far). For example, the first addition (addition of circled value 1) indicates that 3 * G is calculated by performing addition on the elliptic curve of G and 2 * G, and the first doubling (parentheses) The addition of the subscripted number 1) indicates that 2 * G is calculated by performing doubling on G on the elliptic curve.

According to this method, since the difference between the two elements (addition elements) to be added is always G (known), the labor for calculating the difference is unnecessary, and the calculation amount is
Net time required for addition and doubling, that is, n × EAd
d + n × EDob is enough.

Specifically, since G is known, Z
Since the coordinate can be considered as 1, EAdd = 3 × M
ul + 2 × Sq and EDob = 3 × Mul + 2 × Sq. However, Mul and Sq are the calculation amounts of multiplication and multiplication of GF (p), respectively, and generally Sq = 0.8 × Mu.
It is l. By substituting these equations, the calculation amount of the prior art 3 is n × (3 × Mul + 2 × Sq) + n × (3 × Mul + 2
× Sq) = 6 × n × Mul + 4 × n × Sq = 46/5 ×
It becomes n × Mul.

[0041]

[Non-Patent Document 1] Nikol Blitz "Acous
In Namba Atheory and Cryptgrahy (Neal Koblitz, "A Course in Number theory and
Cryptography ", Springer-Verlag, 1987)

[0042]

[Non-Patent Document 2] "Efficient elliptic curve exponent
iation "(Miyaji, Ono, and Cohen, Advances in cry
ptology-proceedings of ICICS'97, Lecture notes i
n computer science, 1997, Springer-verlag, 282-29
0.)

[0043]

[Non-Patent Document 3] "Speeding the Pollard and Elliptic
Curve Methods of Factorization "(PL Montgomery,
Math. Of Comp. 48, 1987, pp.243-264)

[0044]

However, the calculation method of the prior art 3 is (2 ^ i) like the prior art 2.
Considering that * G is calculated in advance (using a table), the algorithm does not use the point of (2 ^ i) * G. There is no reduction, and there is little merit in pre-calculating (2 ^ i) * G. In addition, in the scalar multiplication operation of a Montgomery-type elliptic curve, there is no method that makes it effective to calculate a scalar multiplication point such as (2 ^ i) * G in advance. Therefore, the Montgomery-type elliptic curve is fast in the method that does not have the table of the scalar multiplication points as in the case of the conventional technique 3, but has a problem that there is no effective method when the table is provided.

That is, the conventional scalar multiplication operation method of the Montgomery-type elliptic curve is a power of 2 of a certain point (scalar multiplication).
There is a problem that it is not an effective method when there is a table of points.

As can be seen from the above description, x-coordinates (x-coordinates and z-coordinates in the projective coordinates of the triplet) can be obtained by addition and doubling on the Montgomery-form elliptic curve, but y There is also the problem that coordinates cannot be obtained. Therefore, the conventional Montgomery-type elliptic curve scalar multiplication method cannot be applied to the elliptic curve cryptography in which the y coordinate of the scalar multiplication point is required.

Therefore, according to the present invention, in a scalar multiplication operation method on a Montgomery-type elliptic curve, it is possible to effectively use a table storing the coordinates of a constant scalar multiplication point such as a power of 2 of a certain point G. A first object is to provide a simple elliptic curve calculation device and the like.

A second object of the present invention is to provide an elliptic curve calculation device capable of generating not only the x coordinate of the scalar multiplication point obtained by the scalar multiplication operation but also the y coordinate thereof.

[0049]

In order to achieve the above first object, an elliptic curve calculation device according to the present invention takes an n-bit arbitrary integer k as an input and puts it on a finite field F given in advance. An elliptic curve calculation device for outputting a scalar multiplication point k * G with respect to a point G on a Montgomery type elliptic curve E.
The scalar multiplication point k is obtained by repeating addition on the elliptic curve E with any one of * G, (2 ^ 2) * G, ..., (2 ^ (n-1)) * G as the first addition element. It is characterized by comprising a scalar multiplication unit for calculating * G.

Here, the elliptic curve calculation device further comprises a calculation procedure generation means for generating a calculation procedure indicating an iterative procedure of addition on the elliptic curve E, and the scalar multiplication unit calculates the calculation procedure generation. The scalar multiplication point k * G may be calculated according to the calculation procedure generated by the means.

Further, the calculation procedure generation means (2 ^ (m-1) + u) * G, (2 ^) for natural numbers m and u.
The first calculation for calculating (2 ^ m + u) * G from (m-1)) * G and u * G, or (2 ^ m) * G, (2 ^ m-
A second calculation for calculating (2 ^ (m + 1) -u) * G from u) * G and u * G, or (2 ^ m) * G,-(2 ^ m
-U) * G and (2 ^ (m + 1) -u) * G to u * G
A calculation procedure may be generated in which the third calculation for calculating is the addition on the elliptic curve E.

Further, the calculation procedure generating means associates the addition on the elliptic curve E with at least one of the first to third calculations according to the value of each bit of the k to perform the calculation. The procedure may be generated.

Further, when the value of the bit of k is 0, the calculation procedure generating means associates at least the first calculation as addition on the elliptic curve E corresponding to the bit, and the bit is calculated. If the value of 1 is 1, the calculation procedure may be generated by associating at least the second calculation as an addition on the elliptic curve E corresponding to that bit.

Further, in the calculation procedure generating means, in each addition in the repetition of addition on the elliptic curve E, the expression form of the second addition element to be added with the first addition element is positive in the first calculation. Expression (2 ^ (m-
1) + u) * G or minus expression (2 ^ m−u) * G in the second calculation, the expression format information specifying the expression format is generated as the calculation procedure, and the scalar multiplication unit calculates In each addition in the repetition of addition on the elliptic curve E, any one of the first to third calculations may be performed based on the expression format information.

Further, the expression format information indicates whether the second addition element is switched from which expression of the plus expression and the minus expression to which expression each time the addition is repeated on the elliptic curve E. The information may be the information indicating the number of times the second addition element appears consecutively in one of the plus expression and the minus expression in the repetition of addition on the elliptic curve E. It may be.

The scalar multiplication unit is G, 2 *
G, (2 ^ 2) * G, ..., (2 ^ (n-1)) * G has a table storage unit for storing at least a part thereof, and the points stored in the table storage unit are first added. As an element, addition on the elliptic curve E may be performed.

Further, the elliptic curve calculation device according to the present invention is
Using an arbitrary n-bit integer k as an input, for a point G on a Montgomery-form elliptic curve E on a finite field F given in advance,
An elliptic curve calculation device that outputs a scalar multiplication point k * G, which is 2 * G, 3 * G, 6 * G, 12 * G, ..., (2 ^
Scalar multiplication means for calculating the scalar multiplication point k * G by repeating addition on the elliptic curve E with any one of (n-1) +2 (n-2)) * G as the first addition element. You may prepare.

Here, the elliptic curve calculation device further comprises calculation procedure generation means for generating a calculation procedure indicating an iterative procedure of addition on the elliptic curve E, and the scalar multiplication calculation means generates the calculation procedure. The scalar multiplication point k * G may be calculated according to the calculation procedure generated by the means.

Further, the calculation procedure generating means adds the first addition element (2 ^ (m-1) + 2 ^) to natural numbers m and u.
(M-2)) * G, second addition element (2 ^ (m-2) +
u) * G and a first calculation for calculating (2 ^ m + u) * G from the difference (2 ^ (m-1) -u) between the first addition element and the second addition element, or the first addition Element (2 ^ m + 2 ^
(M-1)) * G, second addition element (2 ^ (m-1)-
u) * G and a second calculation for calculating (2 ^ (m + 1) -u) * G from the difference (2 ^ m + u) between the first addition element and the second addition element is added on the elliptic curve E. May be generated.

Further, the calculation procedure generating means is the first
Alternatively, a division target indicating whether the result obtained by the addition on the elliptic curve E by the second calculation is the second addition element in the next iterative addition or the difference between the first addition element and the second addition element. Information may be generated as the calculation procedure.

Further, the scalar multiplication unit is 2 * G,
3 * G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2
(N−2)) * G may be provided with a table storage unit for storing at least a part thereof, and the points stored in the table storage unit may be used as the first addition element to perform addition on the elliptic curve E.

In order to achieve the second object,
An elliptic curve calculation device according to the present invention is characterized in that, in the elliptic curve calculation device, a y coordinate restoration means for restoring the y coordinate of the scalar multiplication point k * G is further provided.

Here, the first addition element is G, 2 *
G, (2 ^ 2) * G, ..., (2 ^ (n-1)) * G, and the scalar multiplication unit calculates the projection coordinates (x, y, z) of the triplet. Using, by repeating addition on the elliptic curve E using the x coordinate of the first addition element, the x and z coordinates of the scalar multiplication point k * G are calculated,
The y-coordinate restoring means is a projection coordinate (x, y,
z), the x and z coordinates of the scalar multiplication point k * G and the x and z coordinates of the second addition element added to the first addition element used to calculate the scalar multiplication point k * G. And the x and y coordinates of the first addition element, the scalar multiplication point k *
The y coordinate of G may be restored.

The first addition element is 2 * G, 3 *.
G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2 (n
-2)) * G, and the scalar multiplication unit uses the triplet projective coordinates (x, y, z) to generate the elliptic curve using the x coordinate of the first addition element. By repeating the addition on E, the x and z coordinates of the scalar multiple k * G are calculated, and the y coordinate restoring means uses the triplet projective coordinates (x, y, z) to The x and z coordinates of the scalar multiplication point k * G and the x and z of the second addition element added to the first addition element used to calculate the scalar multiplication point k * G.
The y coordinate of the scalar multiple k * G may be restored from the coordinate and the x and y coordinates of the first addition element.

Further, the present invention is realized as an encryption device or a decryption device using the above elliptic curve calculation device, as an elliptic curve calculation method using the above means as steps, or a program causing a computer to function as the above means. Or as a computer-readable recording medium in which such a program is recorded.

[0066]

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. [Embodiment 1] 1. Configuration and Operation of Elliptic Curve Calculation Device 200 FIG. 1 shows elliptic curve calculation device 200 according to the first embodiment.
It is a functional block diagram showing the configuration of. The elliptic curve calculation device 200 is realized by a computer device that executes a dedicated program or a logic circuit such as an LSI, and the finite field GF.
(P) Montgomery-type elliptic curve E: B × y ^ 2 = x ^
3 + A × x ^ 2 + x parameter p (prime number), GF
Elements A and B of (p) and a point G belonging to E (GF (p)),
The power of 2 of the point G (2 ^ i) * G (i = 1,
2, ..., n-1) is given in advance, and an arbitrary k of n bits is input, and a scalar multiplication point of point G x * of point k * G
It is an arithmetic unit that outputs coordinates, and is characterized in that it makes a calculation while making effective use of the power of 2 of the point G (2 ^ i) * G. The calculation procedure generating unit 210 and the scalar multiplication unit 220 Composed. The above n indicates the number of bits of k.

The calculation procedure generation unit 210 is a processing unit for executing preliminary calculation for generating a calculation procedure for calculating the scalar multiple k * G of the point G, and k * G is a power of 2 of G (2
^ I) An addition element specifying unit 210a that specifies an addition element by repeating division into addition forms using * G
And an array generation output unit 210b that outputs the addition element specified by the addition element specification unit 210a as an array.

Specifically, as shown in the flowchart of FIG. 2, the calculation procedure generating section 210 receives an integer k as an input and outputs an array CS [i] (i = 1, 2, ...
...) is output. Here, one array CS [i] is 1
It is composed of four elements that specify one addition, that is, (addition result, first addition element, second addition element, difference between first addition element and second addition element). Note that at least one of the first addition element and the second addition element is a power of 2 of the point G.

The addition element specifying unit 210a specifies the array CS [i] according to the following procedure. Step S201: Set w ← k. However, w ← k is w
It indicates that k is substituted for. Step S202: Counter c ← 1, oldflag ←
0 and newflag ← 0. Step S203: u is set so that w = 2 ^ (| w | −1) + u. Here, | w | indicates the number of bits of w. Step S204: v so that w = 2 ^ | w | −v
Put. Step S205: Determine whether u> v. If yes, go to step S206. If not, go to step S207. Step S206: The newflag is set to 1, and the calculation procedure CS [c] is a value of type I, that is, [(2 ^ | w |-
v) * G, (2 ^ (| w | -1)) * G, (2 ^ (| w
| -1) -v) * G, v * G], and w ← 2 ^ (| w
| -1) -v. Go to step S210.

Here, the calculation procedure [x1 * G, x2 * G,
x3 * G, x4 * G] is the elliptic curve addition x1 * G of x2 * G and x3 * G, and x2 * G, x3 * G, x4 * G (=
x2 * G-x3 * G). Step S207: It is determined whether oldflag = 1. If yes, go to step S208. If not, go to step S209. Step S208: The calculation procedure CS [c] is set to a value of type II, that is, [v * G, (2 ^ | v |) * G,-(2 ^ |
v | −v) * G, w * G], and c ← c + 1. Step S209: With newflag set to 0, the calculation procedure CS [c] is set to a value of type III, that is, [(2 ^ (|
w | -1) + u) * G, (2 ^ (| w | -2) + u) *
G, (2 ^ (| w | -2)) * G, u * G], and w
← 2 ^ (| w | -2) + u. Step S210: oldflag ← newflag,
Let c ← c + 1 and w ←. Step S211: It is determined whether or not w = 3 × 2 ^ e (e ≧ 0). If yes, go to step S212. If not, go to step S203. Step S212: CS [c] is a value of type IV, that is, [(3 × 2̂e) * G, (2̂ (e−1)) * G,
(2 ^ e) * G, (2 ^ e) * G]. Finally, the array generation / output unit 210b has all the calculation procedures CS [i] (i = 1, i = 1, 1 specified by the addition element identification unit 210a.
2, ...) And c are output to the scalar multiplication unit 220, and the process ends.

The scalar multiplication unit 220 calculates the calculation procedure CS [i] (i = 1, 1 output from the calculation procedure generation unit 210.
2, ...) and the counter c, the calculation unit for calculating and outputting the final calculation result k * G by repeating addition on the elliptic curve. The point G as shown in FIG. Of 2
A table storage unit 2 that stores in advance a power of ((2 ^ i) * G; i = 1, 2, ...; However, only the x coordinate).
20b, a temporary storage unit 220 that is a working memory
c, an elliptic curve addition unit 220d that is an adder that performs addition on an elliptic curve, and an arithmetic control unit 220a that controls each of the components 220b to 220d according to the calculation procedure CS [i] from the calculation procedure generation unit 210. Note that the table storage unit 220b stores only the x-coordinate of the power-of-two point of the point G, as can be seen from the above description of the Montgomery-form elliptic curve. This is because the y coordinate is unnecessary in multiplication.

The scalar multiplication unit 220 calculates k * G according to the flowchart shown in FIG. Specifically, the arithmetic control unit 220a performs calculation / control in the following steps. Step S301: Substitute c for the counter d. Step S302: Read CS [c] (S302
a), the calculation procedure [x1 * G, x2 * G, x3 * G,
x4 * G], the elliptic curve addition unit 220d is caused to perform elliptic curve addition, and the point x1 * G (= x2 * G + x3 *
G) is calculated (S302b). At this time, (2 ^
i) * G (power of 2), the value read from the table storage unit 220b is used, and the obtained addition result x1 * G is stored in the temporary storage unit 220c and used in the next calculation. So that the elliptic curve addition unit 220
Control d. Step S303: Set d ← d-1. Step S304: Determine whether d = 0 (S304
a). If so, the elliptic curve addition unit 220d is caused to output the last calculated result x1 * G, and the processing ends (S30).
4b). If not, go to step S302.

Here, the addition method on the elliptic curve used in the above steps will be described below. P = (X1, Y1, Z
1), Q = (X2, Y2, Z2), difference between two points P−Q =
From (X3 ′, Y3 ′, Z3 ′), P + Q = (X3, Y
3, Z3) is obtained as follows. (Step1-1) Calculation of intermediate value U1 = X1 + Z1 U2 = X2 + Z2 V1 = X1-Z1 V2 = X2-Z2 (step1-2) P + Q = (X3, Y3, Z3) calculation X3 = Z3 ′ × (V1 × U2 + U1) XV2) ^ 2 Z3 = X3'x (V1xU2-U1xV2) ^ 2 As can be seen from these equations, the y coordinate does not appear in the addition on the Montgomery-form elliptic curve, so the x coordinate Only (in the projection coordinate of the triplet, the x coordinate and the z coordinate) are calculated. For the Montgomery type elliptic curve used in the elliptic curve calculation device 200, see "Speeding the Pollard an
d Elliptic Curve Methods of Factorization "(PLMon
See tgomery, Math. of Comp. 48, 1987, pp.243-264).

The overall operation of the elliptic curve calculation device 200 configured as described above is as follows. The elliptic curve calculation device 200 receives the input integer k and inputs it to the calculation procedure generation unit 210. The calculation procedure generation unit 210 uses the input integer k to calculate the calculation procedure CS [i] (i = 1, 2,
......) is obtained and input to the scalar multiplication unit 220. The scalar multiplication unit 220 receives the input calculation procedure CS [i].
From (i = 1, 2, ...), the scalar multiplication point k * G of the point G of the elliptic curve is calculated and output.

2. Operation of Elliptic Curve Calculation Device 200 for Specific Numerical Example Below, a numerical example in the case of k = 102 will be shown. The processing by the calculation procedure generation unit 210 will be described. The processing for the value of the counter c is shown below. (When counter c = 1) Step S203: w = 102 = 2 ^ 6 + 38, so u ← 38 Step S204: w = 102 = 2 ^ 7−26, so v ← 26 Step S205: 38> 26 Therefore, step S
To 206. Step S206: newflag ← 1, CS [1] ←
[(2 ^ 7-26) * G (= 102 * G), (2 ^ 6)
* G, (2 ^ 6-26) * G (= 38 * G), 26 *
G], w ← 2 ^ 6-26 = 38, go to step S210. Step S210: oldflag ← newflag =
1, c ← c + 1 Step S211: Since w = 38 and cannot be represented by 3 × 2 ^ e, go to Step S203. (When counter c = 2) Step S203: Since w = 38 = 2 ^ 5 + 6,
u ← 6 Step S204: w = 38 = 2 ^ 6-26, so v ← 26 Step S205: 6 <26, so Step S2
To 07. Step S207: Since oldflag = 1, go to Step S208. Step S208: CS [2] ← [26 * G, (2 ^
5) * G,-(2 ^ 5-26) * G (= -6 * G),
(2 ^ 6-26) * G (= 38 * G)], c ← c + 1 Step S209: newflag ← 0, CS [3] ←
[(2 ^ 5 + 6) * G (= 38 * G), (2 ^ 4 + 6)
* G (= 22 * G), (2 ^ 4) * G, 6 * G], w ←
2 ^ 4 + 6 = 22 Step S210: oldflag ← newflag =
0, c ← c + 1 Step S211: Go to Step S203 where w = 22 and cannot be represented by 3 × 2 ^ e. (When counter c = 4) Step S203: Since w = 22 = 2 ^ 4 + 6,
u ← 6 Step S204: Since w = 22 = 2 ^ 5-10, v ← 10 Step S205: Since 6 <10, Step S2
To 07. Step S207: Since oldflag = 0, go to Step S209. Step S209: newflag ← 0, CS [4] ←
[(2 ^ 4 + 6) * G (= 22 * G), (2 ^ 3 + 6)
* G (= 14 * G), (2 ^ 3) * G, 6 * G], w ←
2 ^ 3 + 6 = 14 Step S210: oldflag ← newflag =
0, c ← c + 1 Step S211: Since w = 14 and cannot be represented by 3 × 2 ^ e, go to Step S203. (When counter c = 5) Step S203: Since w = 14 = 2 ^ 3 + 6,
u ← 6 Step S204: Since w = 14 = 2 ^ 4-2,
v ← 2 Step S205: Since 6> 2, Step S20
Go to 6. Step S206: newflag ← 1, CS [5] ←
[(2 ^ 4-2) * G (= 14 * G), (2 ^ 3) *
G, (2 ^ 3-2) * G (= 6 * G), 2 * G], w ←
2 ^ 3-2 = 6, go to step S210. Step S210: oldflag ← newflag =
1, c ← c + 1 Step S211: Since w = 6 and w = 3 × 2, the processing proceeds to Step S212. Step S212: CS [6] ← [(3 × 2) * G (=
6 * G), (2 ^ 2) * G, 2 * G, 2 * G], end.

From the above, the output of the calculation procedure generator 210 is CS [1] = [102 * G, (2 ^ 6) * G, 38 * G, 26 * G] CS [2] = [26 * G , (2 ^ 5) * G, -6 * G, 38 * G] CS [3] = [38 * G, 22 * G, (2 ^ 4) * G, 6 * G] CS [4] = [ 22 * G, 14 * G, (2 ^ 3) * G, 6 * G] CS [5] = [14 * G, (2 ^ 3) * G, 6 * G, 2 * G] CS [6] = [6 * G, (2 ^ 2) * G, 2 * G, 2 * G] and c = 6.

Next, the processing of the scalar multiplication unit 220 will be described. First, in step S301, c = 6 is substituted for d. The processing for the counter d is shown below. (When counter d = 6) Step S302: CS [6] = [6 * G, (2 ^ 2)
* G, 2 * G, 2 * G], so 2 ^ 2 * G, 2 *
Elliptic curve addition is performed from G and the difference 2 * G to obtain 6 * G. Step S303: d ← d-1 = 5 Step S304: Since d = 5, step S30
Go to 2. (When counter d = 5) Step S302: CS [5] = [14 * G, (2 ^
3) * G, 6 * G, 2 * G], so (2 ^ 3) *
Elliptic curve addition is performed from G, 6 * G and the difference 2 * G to obtain 14 * G. Here, since 6 * G has already been calculated when the counter d = 6, the calculation result there is used. Step S303: d ← d-1 = 4 Step S304: Since d = 4, step S30
Go to 2. (When counter d = 4) Step S302: CS [4] = [22 * G, 14 *
G, (2 ^ 3) * G, 6 * G], so 14 * G,
Elliptic curve addition is performed from (2 ^ 3) * G and the difference 6 * G to obtain 22 * G. Here, since 14 * G and 6 * G have already been calculated when the counters d = 5 and 6, respectively, the calculation results there are used. Step S303: d ← d−1 = 3 Step S304: Since d = 3, step S30
Go to 2. (When counter d = 3) Step S302: CS [3] = [38 * G, 22 *
G, (2 ^ 4) * G, 6 * G], so 22 * G,
Elliptic curve addition is performed from (2 ^ 4) * G and the difference 6 * G to obtain 38 * G. Here, 22 * G and 6 * G have already been calculated when the counters d = 4 and 6, so the calculation results there are used. Step S303: d ← d−1 = 2 Step S304: Since d = 2, step S30
Go to 2. (When counter d = 2) Step S302: CS [2] = [26 * G, (2 ^
5) * G, -6 * G, 38 * G], so (2 ^
5) Elliptic curve addition is performed from * G, -6 * G and the difference 38 * G to obtain 26 * G. Here, 38 * G is already calculated when the counter d = 3, and −6 * G is the Y coordinate of 6 * G obtained when d = 6 is multiplied by (−1). Therefore, it is obtained from the calculation result there. Step S303: d ← d-1 = 1 Step S304: Since d = 1, step S30
Go to 2. (When counter d = 1) Step S302: CS [1] = [102 * G, (2 ^
6) * G, 38 * G, 26 * G], so (2 ^
6) 102 * G is obtained by performing elliptic curve addition from * G, 38 * G and the difference 26 * G. Here, since 38 * G and 26 * G have already been calculated when the counters d = 3 and 4, respectively, the calculation results there are used. Step S303: d ← d-1 = 0 Step S304: Since d = 0, 102 * G is output, and the process ends.

As described above, in the above numerical example, the elliptic curve calculation device 200 can correctly obtain the scalar multiplication point 102 * G. 3. Description by Calculation Flow Diagram Next, the elliptic curve calculation device 200 according to the first embodiment.
The operation will be described with reference to a calculation flow chart.

FIG. 5 is a calculation flow chart showing a scalar multiplication operation method (basic idea; approach 1) by the elliptic curve operation device 200 in the first embodiment. Calculation procedure generation unit 21 of elliptic curve calculation device 200 of the present embodiment
As described in the upper part of this figure [coefficient division guideline], 0 is repeatedly divided into two for the coefficient k in advance when calculating the scalar multiple k * G of the point G. At this time, Division is performed so that a power-of-two coefficient appears every time (hereinafter, such division of coefficients is referred to as "coefficient division").

Specifically, as shown in the calculation flow chart shown in the lower column [specific example] of FIG. 5, one coefficient of the elliptic curve addition becomes a power of 2 from a high digit to a low digit. Then, the scalar coefficient k is divided into two. In this figure, only the coefficient at the point G is shown (that is, "* G").
Is omitted; the same applies to the following calculation flow chart). Also, the solid arrow indicates addition on the elliptic curve,
The three addition elements are two addition elements to be added (one of them is a power of 2) and the difference between these two addition elements.

For example, in this figure, 87 * G, that is,
((2 ^ 6) +23) * G is the first addition element ((2 ^ 6)
5) +23) * G and the second addition element (2 ^ 5) * G, and the difference 23 * G between them is calculated. At this time, one addition element (2 ^ 5) * G is divided so that it becomes a power of 2 of the point G. Subsequently, for the addition element ((2 ^ 5) +23) * G that is not a power of 2 in the same manner, the first addition element ((2 ^ 4) +23) * G and the second addition element (2 ^ 4) are similarly set. * Divided into G and their difference 2
Calculate 3 * G. Also at this time, one addition element (2 ^
4) Divide * G so that it is a power of 2 of point G.
In this way, 2 until
The calculation procedure is determined by repeating the division into two for the addition elements that are not powers of.

For the calculation procedure thus determined, the scalar multiplication unit 220 of the elliptic curve calculation device 200
Calculates the final result k * G by repeating the elliptic curve addition from the lower digit to the higher digit. In particular,
First, using (2 ^ 1) * G, 1 * G and 1 * G,
Elliptic curve addition of (2 ^ 1) * G and 1 * G is performed, and the result ((2 ^ 1) +1) * G is obtained. Then, using the results ((2 ^ 1) +1) * G, (2 ^ 1) * G, and 1 * G obtained now, ((2 ^ 1) +1) * G and (2 ^)
1) The elliptic curve addition with * G is repeated (here, addition is repeated 9 times in total), and the final result 87 * G is calculated.

In addition, in each elliptic curve addition, the point G
For the power of 2 of the above, by using a value calculated in advance (a value stored in the table storage unit 220b), the calculation becomes unnecessary. In addition, the difference value (difference between the first addition element and the second addition element) required at the time of elliptic curve addition is always the value that has appeared in the process of the elliptic curve addition up to that point. No need to calculate. In other words, it is sufficient to retain the values that have appeared in the past and reuse them. For example, the difference value 23 * G required in the last elliptic curve addition in this figure is equal to the value (2 ^ 4 + 7) * G calculated in the preceding elliptic curve addition,
There is no need to newly calculate.

FIG. 6 is a calculation flow chart showing a method of scalar multiplication by the elliptic curve calculation device 200 according to the first embodiment (a concept adopted in the embodiments; approach 2; a development of approach 1). Is. Here, as shown in the upper column of this figure [coefficient division guideline], in order to shorten the addition expression by the above-mentioned approach 1 (representation by the addition form of 9 times in total) (representation by a smaller number of times of addition) In addition, not only the positive expression but also the negative expression is introduced as the expression form of the addition element. The plus expression is an addition type expression format of (2 ^ n) + c, and the minus expression is a subtraction type expression format of (2 ^ (n + 1))-d.

That is, as a value to be divided, a plus expression ((2 ^ n) + c) * G and a minus expression ((2 ^ n
(N + 1))-d) * G is used as the candidate, and the expression format with the smaller absolute value of the term (c, -d, etc.) except the power of 2 in the coefficient is adopted.

More specifically, for example, when (2 ^ 5) +23 is obtained as the coefficient to be divided, as shown in the calculation flow chart in the lower column [Specific example] of FIG. , The negative expression (2 ^ 6) -9 showing the same value as that value is compared, and the expression form (2 ^ 6) -9 of the smaller absolute value of the terms (5 and -9) excluding the power of 2 is Will be adopted. As a result, the difference between the two addition elements obtained after the coefficient division becomes smaller, and the total number of divisions decreases. As shown in this figure, the calculation procedure that required 9 additions in the above approach 1 is reduced to 7 times in the approach 2.

4. Effect of Embodiment 1 As can be seen from the processing of the scalar multiplication unit 220, the elliptic curve calculation device 200 according to the present embodiment causes (2 ^ i) * G to appear for each counter value in repeated calculation of elliptic curve addition. And (2 ^ i) * G (i = 1,
The table of coordinates 2, ..., N-1) can be effectively used. Therefore, the amount of calculation is reduced, and the calculation speed is faster than the conventional method. Detailed calculation amount is
When k is n bits, the amount of calculation differs depending on k, but when it is averaged, it is (5/4 × n−3) × EAAdd. Here, EAdd is the calculation amount of elliptic curve addition.

Unlike the prior art 3, since the difference U between two points cannot be calculated in advance, the Z coordinate is not always 1. for that reason,
EAdd = 4 × Mul + 2 × Sq, EDob = 3 × Mu
1 + 2 × Sq. However, Mul and Sq are calculation amounts of multiplication and multiplication of GF (p), respectively, and generally Sq = 0.8 × Mul. When these equations are substituted, the calculation amount of the elliptic curve calculation device 200 is (5/4 × n−3) × (4 × Mul + 2 × Sq) = (5
× n-12) × Mul + (5/2 × n-6) × Sq =
(7 × n−84 / 5) × Mul, and the calculation amount of the prior art 3 is n × (3 × Mul + 2 × Sq) + n × (3 × Mul + 2
× Sq) = 6 × n × Mul + 4 × n × Sq = 46/5 ×
n × Mul. Therefore, the elliptic curve calculation device 200 is about 1.3 times faster than the prior art 3.

FIG. 7 is a diagram comparing the calculation method of the prior art 3 shown in FIG. 33 and the calculation method of the first embodiment (lower column of FIG. 6). As can be seen from this figure, for example, for the calculation of 87 * G, according to the prior art 3, 6
While addition of 5 times and doubling of 5 times are required, according to the first embodiment, only 7 additions are required. In other words, in terms of the amount of calculation, the prior art 3 and the first embodiment have 50.
It becomes 6: 39.2, and the calculation speed is set to the first embodiment.
Is 1.3 times faster than the prior art 3.

As described above, according to the first embodiment, high-speed elliptic curve calculation can be performed, and the practical value of the present invention is very large.

[Second Embodiment] Next, an elliptic curve calculation device according to a second embodiment of the present invention will be described. 1. Configuration and Operation of Elliptic Curve Calculation Device 300 FIG. 8 is an elliptic curve calculation device 300 according to the second embodiment.
3 is a block diagram showing the configuration of FIG. This elliptic curve calculation device 300 is realized by a logic device such as a computer device or an LSI that executes a dedicated program, as in the first embodiment, and the Montgomery type elliptic curve E: B × on a finite field GF (p). y ^ 2 = x ^ 3 + A × x ^ 2 + x parameter p (prime number), elements A and B of GF (p), and E (GF (p))
Point G that belongs to and a power-of-two point of that point G (2 ^ i)
* G (i = 1, 2, ..., N-1) x-coordinate is given in advance, and an arbitrary n-bit k is input and the x-coordinate of scalar multiplication point k * G of point G is output. It is a device, and is characterized in that it makes a calculation while making effective use of the power of 2 of the point G (2 ^ i) * G, and is composed of a calculation procedure generation unit 310 and a scalar multiplication unit 320.

This elliptic curve calculation device 300 generates a calculation procedure for the scalar multiplication of the point G based on preliminary calculation (calculation suitable for computer processing) using binary representation,
This is different from the first embodiment in which the processing efficiency by the computer is not taken into consideration in that the scalar multiplication operation of the point G is executed according to the generated calculation procedure.

The calculation procedure generation unit 310 is a processing unit for executing preliminary calculation for generating a calculation procedure for calculating a scalar multiple k * G of the point G, and k * G is a power of 2 of G (2
^ I) An addition type specifying unit 310a that repeats division into addition forms using * G and specifies the type (addition type) of switching of the expression form (plus expression / minus expression) of the obtained addition element , Addition type identification unit 3
An array generation / output unit 310b that outputs the addition type specified by 10a as an array.

Specifically, as shown in the flowchart of FIG. 9, the calculation procedure generator 310 receives the integer k as an input, and the array {S [i]} (S [i] is the i-th number of the array. 1 ≦ i ≦ | k |) is output. Where the array S
[I] is the type of the i-th addition in the repeated addition for calculating k * G, that is, the expression of the coefficient of the addition element (or the value obtained as a result of the addition) that is not a power of 2 of the point G. Paying attention to the form, "0" when the coefficient is changed from the positive expression to the positive expression by the addition, "1" when the coefficient is changed from the positive expression to the negative expression, and "2" when the coefficient is changed from the negative expression to the negative expression. “,” Is set to “3” when the negative expression is changed to the positive expression.

In FIG. 9, the addition type specifying unit 310a
Specifies the array {S [i]} according to the following procedure. In the following, k = k [n-1] * 2 ^ (n-1) + k [n-2] * 2
^ (N-2) + ... + k [1] × 2 + k [0], the bit representation of k is [k [n-1], k
Let [n-2], ..., K [1], k [0]]. Step S401: Set w ← k. However, w ← k is w
It indicates that k is substituted for. Step S402: Counter c ← n-1. Step S403: u ← w-2 ^ c. Step S404: It is determined whether u [c-1] is 1. If it is 1, go to step S406. Otherwise, go to the next step. Step S405: It is determined whether u [c-2] is 0 (S405a). When 0, S [c] ← 0, w ←
Let w-2 ^ (c-1) (S405b). When 1, S [c] ← 1, w ← w-2 ^ (c-1), u ← w-
Let 2 ^ (c-1) (S405c). Step S40
Go to 7. Step S406: It is determined whether u [c-2] is 1 (S406a). When 1, S [c] ← 2, w ←
Let w-2 ^ c and u ← u-2 ^ c (406b). When 0, S [c] ← 3, w ← w-2 ^ c, u ← w-2
^ (C-1) (S406c). Step S407: w = 2 ^ (c-1) + 2 ^ (c-
It is determined whether it is 2) (S407a). If this expression holds, the addition type identifying unit 310a determines that S [1] ← c−
1, and the array generation / output unit 310b sets the array {S [i]}
Is output to the scalar multiplication unit 320 and the processing is terminated (S407).
b). Otherwise, go to the next step. Step S408: Set c ← c-1. Step S40
Go to 4.

The scalar multiplication unit 320 calculates the calculation procedure S [i] (i = 1, 2,
, Which is a calculation unit that calculates and outputs the final calculation result k * G by repeating addition on the elliptic curve based on (2) i (* 2 ^ i) * G I = 1,
2, ...; However, only the x coordinate) is stored in advance, a table storage unit 320b, a temporary storage unit 320c that is a working memory, an elliptic curve addition unit 320d that is an adder that performs addition on an elliptic curve, and In accordance with the calculation procedure S [i] from the calculation procedure generation unit 310, each of the constituent elements 320b-3
The calculation control unit 320a controls the 20d.

The scalar multiplication unit 320 calculates k * G according to the flowchart shown in FIG. Specifically, the arithmetic control unit 320a performs the following steps.
Calculate and control. Step S501: d ← S1. Elliptic curve adder 3
Add elliptic curve to 20d 2 ^ d * G + 2 ^ (d-1) * G
Is executed and is substituted into T, and U ← 2̂ (d−1) * G. Step S502: Set d ← d + 1. Step S503: T ′ ← T. Step S504: The value of S [d] is determined (S504
a), process as follows. (1) When S [d] = 0 or 1, T and 2 ^ (d−1) * G (the difference between the two points is U) in the elliptic curve addition unit 320d.
The elliptic curve addition of is calculated and the result is substituted for T (S504b). (2) When S [d] = 2 or 3, let the elliptic curve addition unit 320d calculate elliptic curve addition of 2 ^ d * G and T (the difference between two points is U), and substitute the result in T. Yes (S504
c).

For powers of 2 such as (2 ^ d) * G, the value read from the table storage unit 320b is used, and the obtained addition result is stored in the temporary storage unit 320c. And substitute it for the variable T. Step S505: It is determined whether d = | k | −1 (S
505a), if this expression is satisfied, T is output (S50
5b), the process ends. Otherwise, go to the next step. Step S506: Check the value of S [d + 1] (S506
a) and when S [d + 1] = 1, U ← T ′ is set (S506b). When S [d + 1] = 3, the elliptic curve addition unit 320d is caused to execute elliptic curve addition of 2 ^ d * G and −U (the difference between the two points is T), and the result is substituted for U (S506c). ). Go to step S502.

The specific calculation method of the elliptic curve addition used in the above steps is as described in the first embodiment. Elliptic curve calculation device 3 configured as described above
The overall operation of 00 is as follows.

The elliptic curve calculation device 300 uses the input integer k.
Is input to the calculation procedure generation unit 310. The calculation procedure generation unit 310 calculates the array {S from the input integer k.
[I]} is calculated and input to the scalar multiplication unit 320.
The scalar multiplication unit 320 receives the input array {S [i]}
Then, the scalar multiplication point k * G of the point G of the elliptic curve is calculated and output.

2. Operation of Elliptic Curve Calculation Device 300 for Specific Numerical Example Below, a numerical example in the case of k = 102 will be shown. First, the process of the calculation procedure generation unit 310 will be described. Since n = 7, the initial value of the counter c is 6. The processing for the value of the counter c is shown below. (When Counter c = 6) Step S403: u ← w−2 ^ (n−1) = 38 Step S404: Determination of u [c−1] = u [5]. u
Since [5] = 1 (∵u = 2 ^ 5 + 6), the process proceeds to step S406. Step S406: determination of u [c-2] = u [4]. u
Since [4] = 0, S [6] ← 3, w ← w-2 ^ c
= 102-2 ^ 6 = 38, u ← w-2 ^ (c-1) = 3
8-2 ^ 5 = 6 Step S407: w = 2 ^ (c-1) + 2 ^ (c-
2) determination of whether or not. Not satisfying step S408: Step S is performed by setting c ← c-1 = 5
To 404. (When Counter c = 5) Step S404: Determination of u [c−1] = u [4]. u
Since [4] = 0, go to step S405. Step S405: determination of u [c-2] = u [3]. u
Since [3] = 0, S [5] ← 0, w ← w-2 ^
(C-1) = 38-2 ^ 4 = 22. Step S407
What. Step S407: w = 2 ^ (c-1) + 2 ^ (c-
2) determination of whether or not. Not satisfying step S408: assuming that c ← c-1 = 4, step S408
To 404. (When Counter c = 4) Step S404: Determination of u [c-1] = u [3]. u
Since [3] = 0, go to step S405. Step S405: determination of u [c-2] = u [2]. u
Since [2] = 1, S [4] ← 1, w ← w-2 ^
(C-1) = 22-2 ^ 3 = 14, u ← w-2 ^ (c-
1) = 14-2-2 = 6. Go to step S407. Step S407: w = 2 ^ (c-1) + 2 ^ (c-
2) determination of whether or not. Not satisfying step S408: assuming c ← c-1 = 3, step S408
To 404. (When Counter c = 3) Step S404: Determination of u [c−1] = u [2]. u
Since [2] = 1, the process proceeds to step S406. Step S406: determination of u [c-2] = u [1]. u
Since [1] = 1, S [3] ← 2, w ← w-2 ^ c
= 14-2 ^ 3 = 6, u ← u-2 ^ (c-1) = 6-2
^ 2 = 2. Go to step S407. Step S407: w = 2 ^ (c-1) + 2 ^ (c-
2) determination of whether or not. Since w = 6 = 2̂2 + 2̂1 is satisfied, S [1] = c−1 = 2 is set and the array {S [i]} is output and the processing ends.

From the above, the output of the calculation procedure generation unit 310 is [2, 0, 2, 1, 0, 3].

Next, the processing by the scalar multiplication unit 320 will be described. Since S1 = 2, d = 2. First,
In step S501, 2 ^ 2 * G + 2 ^ 1 * G is calculated and substituted for Q, so that U ← 2 ^ 1 * G. Next, in step S502, d ← d + 1 = 3. The processing for the subsequent values of d is shown below. (When d = 3) Step S503: Q ′ ← Q Step S504: Determine the value of S [d] = S [3]. S
Since [3] = 2, 2 ^ 3 * G and Q (the difference between the two points is
2 ^ 3 * G-Q = (2 ^ 3- (2 ^ 2 + 2 ^ 1)) * G
= 2 * G = U) elliptic curve addition and substitute for Q (Q =
14 * G). Step S505: Determine whether d = | k | −1 = 6.
Not satisfying step S506: determination of S [d + 1] = S [4]. S
Since [4] = 1, U ← Q ′ (= 6 * G). Go to step S502. (When d = 4) Step S503: Q ′ ← Q Step S504: Determine the value of S [d] = S [4]. S
Since [4] = 0, Q and 2 ^ 3 * G (the difference between the two points is
Q-2 ^ 3 * G = (14-2 ^ 3) * G = 6 * G = U)
Then, the elliptic curve is added and the value is substituted for Q (Q = 22 * G). Step S505: Determine whether d = | k | −1 = 6.
Not satisfying step S506: determination of S [d + 1] = S [5]. S
Since [5] = 0, there is no processing here. Go to step S502. (When d = 5) Step S503: Q ′ ← Q Step S504: Determine the value of S [d] = S [5]. S
Since [5] = 0, Q and 2 ^ 4 * G (the difference between the two points is
Q-2 ^ 4 * G = (22-2 ^ 4) * G = 6 * G = U)
Then, the elliptic curve is added and the value is substituted for Q (Q = 38 * G). Step S505: Determine whether d = | k | −1 = 6.
Not satisfied Step S506: Determine the value of S [d + 1] = S [6]. Since S [6] = 3, 2 ^ 5 * G and -U (the difference between the two points is 2 ^ 5 * G-(-U) = (2 ^ 5 + 6) * G = 3.
8 * G) elliptic curve addition and substitute for U (U = 26 *
G). Go to step S502. (When d = 6) Step S503: Q ′ ← Q Step S504: Determine the value of S [d] = S [6]. S
Since [6] = 3, 2 ^ 6 * G and Q (the difference between the two points is
2 ^ 6 * G-Q = (2 ^ 6-38) * G = 26 * G =
U) elliptic curve addition and substitute for Q (Q = 102 *
G). Step S505: Determine whether d = | k | −1 = 6.
To satisfy the condition, output Q (= 102 * G) and end.

As described above, in the above numerical example, the elliptic curve calculation device 300 can correctly obtain the scalar multiplication point 102 * G.

3. Description by Calculation Flow Diagram Next, the elliptic curve calculation device 300 according to the second embodiment.
The operation will be described with reference to a calculation flow chart.

FIG. 11 is a calculation flowchart showing a method of scalar multiplication by the elliptic curve calculation device 300 according to the second embodiment. Elliptic curve calculation device 300 of the present embodiment
As described in the upper column of this figure [coefficient division guideline], the calculation procedure generation unit 310 repeats two divisions for the coefficient k in advance when calculating the scalar multiple k * G of the point G. However, at this time, regarding the coefficient to be divided, paying attention to the most significant two digits in the binary representation of the coefficient, "1
If it is "0", it is expressed as a plus expression, while "1"
If it is "1", it is expressed by a minus expression and then coefficient division is executed. Then, for each coefficient division, an addition type (0/1/2/3) indicating how the expression format of the division target (coefficient) is switched is specified.

Specifically, as shown in the calculation flow chart in the middle column [specific example] of FIG.
For 02, its binary representation is 1100110,
Since the highest two digits are "11", 102 is 2 ^ 7-2
Expressed with a negative expression of 6, then 2 ^ 6 and 2 ^ 6
-26 (= 38). Next, since 38 has a binary representation of 100110 and the highest two digits are "10", the 38 to be divided is 2 ^ 5 +.
Expressed as a positive expression of 6, then 2 ^ 4 and 2 ^ 4 +
Divide into 6 and 6. At this time, the first coefficient division (division for 102) changes the division target from the negative expression to the positive expression. Therefore, the value of the corresponding one of the expression type switching types shown in the lower column of FIG. 3 "
Is set as the value of the array S [i].

As described above, in the example of this figure, the coefficient to be divided changes in the negative expression, the positive expression, the positive expression, the negative expression, the negative expression, ... The array S [i] is 3,0,1,2,
… Will be.

When the expression form of the division target is switched from the minus expression to the plus expression, the difference value between the two addition elements generated by the division also needs to be divided. In the example of this figure, the difference value 26 generated when the division target is switched from the minus expression (2 ^ 7-26) to the plus expression (2 ^ 5 + 6) is also divided into the addition elements shown.

As described above, in the second embodiment, the calculation procedure S [i] generated by the calculation procedure generation unit 310 is the switching information of the representation format of the target coefficient in the iterative division with respect to the scalar coefficient k, and The information is simplified as compared with the first embodiment in which the division element (addition element) is output as the calculation procedure.

4. Effects of Second Embodiment As is apparent from the processing of the scalar multiplication unit 320, the elliptic curve calculation device 300 according to the present embodiment is similar to the first embodiment, in the repeated calculation of the elliptic curve addition,
(2 ^ i) * G appears at each addition, and (2 ^ i)
The table of coordinates of * G (i = 1, 2, ..., N-1) can be effectively used. Therefore, the amount of calculation is reduced, and the calculation speed is about 1.3 times faster than that of the conventional technique 3.

The difference from the elliptic curve calculation device 200 of the first embodiment is that the description of the process of the device is in a form more suitable for a computer (process related to binary representation).
Therefore, programming becomes easy. As described above, the second embodiment enables high-speed elliptic curve calculation,
Further, the processing is in a form suitable for a computer, and the practical value of the present invention is very large.

[Third Embodiment] Next, an elliptic curve calculation device according to a third embodiment of the present invention will be described. 1. Configuration and Operation of Elliptic Curve Calculation Device 400 FIG. 12 shows elliptic curve calculation device 40 according to the third embodiment.
It is a block diagram which shows the structure of 0. Like the first and second embodiments, the elliptic curve calculation device 400 is realized by a logic circuit such as a computer device or an LSI that executes a dedicated program, and the Montgomery elliptic curve E on the finite field GF (p): B × y ^ 2 = x ^ 3 + A × x ^ 2 + x parameter p (prime number), elements A and B of GF (p), and E (GF
(P)) and the x coordinate of a point G belonging to (p)) and a power-of-two point (2 ^ i) * G (i = 1, 2, ..., N-1) of the point G are given in advance, and n bits are set. Is an arithmetic unit that outputs the x-coordinate of the scalar multiplication point k * G of the point G by inputting an arbitrary k of the point G, and a point that calculates while effectively utilizing the power of 2 of the point G (2 ^ i) * G And has a calculation procedure generation unit 410 and a scalar multiplication unit 420.

This elliptic curve calculation device 400 generates a calculation procedure for switching the representation form of the addition element based on preliminary calculation (calculation suitable for computer processing) using binary representation for scalar multiplication of point G. The second embodiment is different from the second embodiment in that it is common to the second embodiment in that the number of consecutive pieces of the same expression format is generated as a calculation procedure instead of the individual switching information. Hereinafter, points different from the second embodiment will be mainly described.

The calculation procedure generation unit 410 is a processing unit for executing preliminary calculation for generating a calculation procedure for calculating the scalar multiple k * G of the point G, and k * G is a power of 2 of G (2
^ I) An addition element that repeats division into addition forms using * G and specifies a switching point of the expression form of the obtained addition element (information about how many times the same expression form continues and then switches) An expression switching point specifying unit 410a,
Array generation output unit 41 that outputs the switching points specified by the addition element expression switching point specifying unit 410a as an array
It consists of 0b.

Specifically, as shown in the flowchart in FIG. 13, the calculation procedure generation unit 410 receives the integer k as an input and outputs the array {S [i]} (i = 1, 2, ..., S [1 ]
+2) is output. Here, the array {S [i]} is composed of the following values.

S [1]: The total number of expression forms (in the case where the same expression form is continuous, the number is one) that appears in the transition sequence of the expression forms obtained as a result of coefficient division. For example, when the expression form of the division target is − (minus expression), + (plus expression), +, −, −, 3 (“−”,
"+", "-").

S [2]: Number of "0" (binary expression) contained in the addition element obtained at the end of coefficient division. The addition element obtained at the end of the coefficient division is a binary expression and must be 10
... (an expression in which 1 and 0 or more 0s continue).

S [3]: The number of consecutive first-form representation forms from the upper digit in the representation-sequence transition sequence obtained by coefficient division. For example, the expression format of the division target is −,
If it is +, +,-,-, it is 1 (the first expression form "-" is one).

S [4]: The number of consecutive second expression formats from the upper digit in the transition string of the expression formats obtained by coefficient division. For example, the expression format of the division target is −,
If it is +, +,-,-, it is 2 (the second expression form "+" is two).

In the same manner, the process continues until S [S [1] +2]. In FIG. 13, the addition element expression switching point identification unit 4
10a identifies the array {S [i]} according to the following procedure. Step S601: The given k is a target of coefficient division. Step S602: With respect to the division target, the expression form is specified and stored by the same judgment as the second embodiment (“coefficient division guideline” in FIG. 6), and the division target is expressed in the expression form. Step S603: Similar to the second embodiment, the division target is divided into the first addition element (term of a power of 2) and the second addition element, and the difference value thereof is specified. Step S604: In order to determine whether or not all coefficient divisions have been completed, the second addition element to be the next division target is 3
Determine if it can be represented by × 2 ^ e. Step S605: If the affirmative determination is made in step S604, the expression format of the next division target is set to a negative expression, and the final division is performed on the division target. Step S606: Finally, the array generation / output unit 410b
Is the number of appearance formats that have appeared from the array of expression formats for the division target obtained by the coefficient division up to that point.
Set to [1], set the number of “0” (binary expression) included in the second addition element obtained by the last coefficient division to S [2], and set the expression format obtained by the coefficient division. In the transition sequence, the number of consecutive first representation formats from the upper digit is set to S [3], and similarly, the number of consecutive second representation formats is set to S [4], ... .. S [S [1] +
2] and output to the scalar multiplication unit 420. Step S607: When a negative determination is made in step S604, the second addition element is set as a new division target in order to continue the further coefficient division, and the same procedure (steps S602 to S604) is repeated.

The scalar multiplication unit 420 repeats addition on the elliptic curve based on the calculation procedure {S [i]} output from the calculation procedure generation unit 410 to obtain the final calculation result k * G. This is a calculation unit that calculates and outputs, and is a power of 2 of the point G ((2 ^ i) * G; i = 1, 2, ...;
Table storage unit 420 storing in advance (x coordinate only)
b, a temporary storage unit 420c that is a working memory,
A calculation procedure {S from the elliptic curve addition unit 420d and the calculation procedure generation unit 410, which is an adder that performs addition on the elliptic curve
[I]} according to [i]}, and comprises the arithmetic control part 420a which controls each component 420b-420d.

The scalar multiplication unit 420 calculates k * G according to the flowchart shown in FIG. Specifically, the arithmetic control unit 420a performs the following steps.
Calculate and control. Step S701: The first addition element, the second addition element, and the difference necessary for the first elliptic curve addition are specified based on the array element S [2] given from the calculation procedure generation unit 410. Steps S702 to S704: Elliptic curve addition of the same type (step S703) is repeated the number of times indicated by the array element S [1] given from the calculation procedure generation unit 410. Step S703: In the i-th elliptic curve addition in the S [1] times of elliptic curve addition, elliptic curve addition of the same type is performed the number of times indicated by the array element S [i + 2] given from the calculation procedure generation unit 410. repeat.

2. Operation of Elliptic Curve Calculation Device 400 for Specific Numerical Example Next, the elliptic curve calculation device 400 according to the third embodiment.
The operation will be described with reference to specific numerical examples and calculation flow charts.

First, the processing by the calculation procedure generation unit 410 will be described. FIG. 15 is a calculation flowchart showing a process of generating a calculation procedure (array {S [i]}) by the calculation procedure generation unit 410. As can be seen by comparing the calculation flow chart shown in the upper section [specific example] of this figure with the calculation flow chart shown in FIG. 11, the basic processing of coefficient division in this embodiment is the same as that in the second embodiment. It is the same. That is, the division into two is repeated for the coefficient k. At this time, if the most significant two digits in the binary expression of the coefficient to be divided are “10”, they are expressed in plus, while “11” is used. In some cases, the coefficient is divided after the negative expression.

However, the calculation procedure generation unit 4 of the present embodiment
In the coefficient division, 10 does not generate an array indicating what the expression form of the division object is switched to, but as shown in the lower column [array generation (calculation procedure generation)] of the figure, Information indicating how many steps (division) the expression format is switched is generated as an array {S [i]}.

Specifically, the coefficient "10" shown in this figure is used.
"2" is changed to the negative expression, the positive expression, the positive expression, the negative expression, and the negative expression with the coefficient division, so that it is specified as (1, 2, 2), and the array element S [ 3], S [4], S [5]. Then, the total number "3" just set is set in the array element S [1], and "0" included in the addition element "2" (binary expression "10") obtained at the end of the coefficient division. Set the number "1" in the array element S [2],
It is output as an array {S [i]} indicating the calculation procedure.

Next, the processing by the scalar multiplication unit 420 will be described. FIG. 16 is a diagram showing an operation of the scalar multiplication unit 420 corresponding to the specific example shown in FIG. That is, the calculation process until the scalar multiplication unit 420 that has received the array (3, 1, 1, 2, 2) shown in FIG. 15 calculates the value of 102 * G according to the flowchart shown in FIG. Intermediate values are shown.

The scalar multiplication unit 420 initializes the number of repetitions d of the elliptic curve addition of the same type based on the array element S [1] given from the calculation procedure generation unit 410, and then performs the first elliptic curve addition. The first addition element W, the second addition element T, the difference U, and the like required for are specified (step S80).
1).

Then, from S [3 + 2] = 2, elliptic curve addition is performed twice to generate an addition value in the negative expression, and the difference value U is updated (step S802). Then S
[2 + 2] = 2 is used to generate a plus expression addition value 2
Elliptic curve addition is performed twice to update the difference value U (step S803).

Finally, from S [1 + 2] = 1, one-time elliptic curve addition for generating an addition value in the negative expression is performed, and the obtained addition result T is output as the final result (102 * G). (Step S804).

3. Effect of Embodiment 3 As with Embodiments 1 and 2, the elliptic curve calculation device 400 according to the present embodiment can calculate (2 ^) in repeated calculation of elliptic curve addition, as can be seen from the processing of the scalar multiplication unit 420. i) * G appears at each addition, and (2
^ I) * G (i = 1, 2, ..., N-1) coordinate table can be effectively used. Therefore, the amount of calculation is reduced, and the calculation speed is about 1.3 times faster than that of the conventional technique 3.

The difference from the elliptic curve calculation device 200 of the first embodiment is that the description of the process of the device is in a form more suitable for a computer (process related to binary expression).
A difference from the elliptic curve calculation device 300 of the second embodiment is that the expression of the calculation procedure by the calculation procedure generation unit 410 is in a compressed short form. for that reason,
Programming is facilitated and the number of intermediate values required in the calculation process is suppressed.

As described above, according to the third embodiment, a high-speed elliptic curve calculation is possible, the processing is suitable for a computer, and the calculation can be performed in a smaller working memory area. The practical value of the invention is enormous.

[Embodiment 4] Next, an elliptic curve calculation device according to Embodiment 4 of the present invention will be described. 1. Configuration and Operation of Elliptic Curve Calculation Device 500 FIG. 17 is an elliptic curve calculation device 50 according to the fourth embodiment.
It is a block diagram which shows the structure of 0. This elliptic curve calculation device 500 is realized by a logic circuit such as a computer device or an LSI that executes a dedicated program, as in the first to third embodiments, and the Montgomery type elliptic curve E on the finite field GF (p): B × y ^ 2 = x ^ 3 + A × x ^ 2 + x parameter p (prime number), elements A and B of GF (p), and E (GF
(P)) and the x coordinate of a point G belonging to (p)) and a power-of-two point (2 ^ i) * G (i = 1, 2, ..., N-1) of the point G are given in advance, and n bits Is an arithmetic unit that outputs the x-coordinate of the scalar multiplication point k * G of the point G by inputting an arbitrary k of the point G, and a point that calculates while effectively utilizing the power of 2 of the point G (2 ^ i) * G And has an arithmetic control unit 510, a table storage unit 520, and an elliptic curve addition unit 530.

Unlike the first to third embodiments, this elliptic curve calculation device 500 does not generate a series of calculation procedures in advance by a preliminary calculation for the scalar multiplication of the point G, but provides it. The final result k * G is calculated by repeating the elliptic curve addition while analyzing k from the lower digit to the upper digit. That is, the final result is obtained only by the elliptic curve addition, instead of the two steps of generating the calculation procedure and elliptic curve addition.

The arithmetic control unit 510 is a processing unit for performing a temporary process for calculating k * G for a given coefficient k and a control for the elliptic curve addition unit 530. Based on the determination result by the bit determination unit 510a that determines the value (1/0) of each bit in the expression and the determination result by the bit determination unit 510a, three values required for elliptic curve addition (two addition elements and their difference values) ), And a temporary storage unit 510c that is a working memory.

The table storage unit 520 is a table in which the power of 2 of the point G ((2 ^ i) * G; i = 1, 2, ...; However, only the x coordinate) is stored in advance. This is the same as the table storage unit 220b and the like in the first form.

The elliptic curve addition unit 530 is included in the calculation control unit 51.
It is an adder or the like that performs addition on an elliptic curve using a value instructed by the arithmetic control unit 510 or a value read from the table storage unit 520 according to the control by 0.

FIG. 18 is a flow chart showing the operation of the elliptic curve calculation device 500 according to this embodiment. Step S901: The arithmetic control unit 510 acquires the coefficient k. Step S902: The lowest "1" in the binary representation of the obtained coefficient k is specified, and its digit is designated as k [s]. Then, the value 2 ^ s corresponding to the digit k [s] is specified as the first addition target (element to be added to the power of 2). Steps S903 to S907: Next, the digit k [s]
From the most significant digit to k [n-2], the digit k
The elliptic curve addition (steps S904 to S906) according to the value (1/0) of [i] is repeated. Step S904: Specifically, first, the bit determination unit 5
10a determines whether the digit k [i] is 1 or 0. Step S905: As a result, when it is determined that k [s] = 1, the addition element identification unit 510b identifies an addition element whose addition target is a negative expression. That is,
When the addition target is expressed as 2 ^ (s + 1) -d, 2 ^ (s + 1) -d, 2 ^ (s + 1), and d are generated as the elements necessary for the elliptic curve addition. Then, those values and control instructions are given to the elliptic curve addition unit 530 so that the elliptic curve addition using them is executed. The elliptic curve addition unit 530 uses the value read from the table storage unit 520 in accordance with the instruction from the addition element identification unit 510b for the power of 2 of the point G. Step S906: On the other hand, the digit k at step S904
When [i] is determined to be 0, the addition element identification unit 510b identifies an addition element whose addition target is a plus expression. That is, when the addition target is expressed as 2 ^ s + d, the elements necessary for the elliptic curve addition are 2 ^ s + d.
And 2 ^ s and d are generated. Then, those values and control instructions are given to the elliptic curve addition unit 530 so that the elliptic curve addition using them is executed.

The intermediate value and the like obtained by the elliptic curve addition are stored in the temporary storage unit 510c and used for the next elliptic curve addition.

2. Operation of Elliptic Curve Calculation Device 500 for Specific Numerical Example FIG. 19 shows an elliptic curve calculation device 50 for specific numerical values.
It is a calculation flowchart which shows operation | movement of 0. In calculating k * G, the elliptic curve calculation device 500 repeats elliptic curve addition of the power of 2 of the point G and the obtained result by sequentially referring to the lower digits of the coefficient k. Go,
At that time, if the value of the coefficient k [i] of interest is “1” as shown in the upper column of the figure [guideline for addition of elliptic curve], the addition target (initial value of addition) Alternatively, the value obtained by the immediately preceding elliptic curve addition) is expressed in plus, and the elliptic curve addition is executed. On the other hand, when the value of the coefficient k [i] of interest is “0”, Elliptic curve addition is executed after the addition target is expressed as a negative expression.

More specifically, as shown in the lower column [Specific example] of this figure, the arithmetic control unit 510 first sets the lowest "1" (in this case, 1) in the binary representation of the given coefficient k. , K
[S]; s = 1) is specified. The value 2 ^ 1 corresponding to the digit k [s] is specified as the first addition target (element to be added to the power of 2).

Subsequently, the elliptic curve addition according to the value (1/0) of the digit k [i] is sequentially repeated from the digit k [1] to k [5]. Specifically, first, the bit determination unit 5
10a determines the value of the digit k [1]. as a result,
From k [1] = 0, the addition element identification unit 510b identifies an addition element whose addition target is a negative expression. Specifically, (2 ^ (1+
1) -2) * G and (2 ^ (1 + 1)) * G and 2 * G are generated, and the elliptic curve addition unit 530 is made to perform elliptic curve addition.

Subsequently, the bit determining section 510a determines the value of the next higher digit k [2]. As a result, k [1] = 0
Accordingly, the addition element identification unit 510b similarly identifies the addition element whose addition target is a negative expression. Specifically, (2 ^ (2+
1) -2) * G and (2 ^ (2 + 1)) * G and 2 * G are generated, and the elliptic curve addition unit 530 is made to perform elliptic curve addition.

Then, the bit determination unit 510a determines the value of the next higher digit k [3]. As a result, k [1] = 1
Accordingly, the addition element identification unit 510b identifies the addition element whose addition target is a plus expression. Specifically, (2 ^ 3 + 6) * G and (2 ^
3) Generate * G and 6 * G, and make the elliptic curve addition unit 530 execute elliptic curve addition.

In this way, the final value k * G is calculated by repeating the elliptic curve addition using the positive expression or the negative expression for k [1] to k [5].

3. Effect of Fourth Embodiment In the elliptic curve calculation device 500 according to the present embodiment, (2 ^ i) * G appears for each addition in the repeated calculation of the elliptic curve addition, as in the first to third embodiments. ,
The table of coordinates of (2 ^ i) * G (i = 1, 2, ..., N-1) can be effectively used. Therefore, the amount of calculation is reduced, and the calculation speed is about 1.3 times faster than that of the conventional technique 3.

A difference from the elliptic curve calculation devices of the first to third embodiments is that preliminary calculation for collectively generating a series of calculation procedures is not performed. In the present embodiment, the calculation procedure is not generated all at once, but the calculation procedure is generated for each addition of elliptic curves in the scalar multiplication operation (the expression format is determined). As a result, the preliminary calculation and the scalar multiplication operation are united with each other, only the parameters necessary for each elliptic curve addition are generated and used, and the program scale and circuit scale are reduced. Processing speed can be improved.

As described above, according to the fourth embodiment, a high-speed elliptic curve calculation is possible, the processing is in a form suitable for a computer, and it can be realized by a program or circuit of a smaller scale. Yes, the practical value of the present invention is very great.

[Fifth Embodiment] An elliptic curve calculation device according to a fifth embodiment of the present invention will now be described. 1. Configuration and Operation of Elliptic Curve Calculating Device 600 FIG. 20 shows elliptic curve calculating device 60 according to the fifth embodiment.
It is a block diagram which shows the structure of 0. This elliptic curve calculation device 600 is realized by a logic circuit such as a computer device or an LSI that executes a dedicated program, as in the first embodiment, and is a Montgomery type elliptic curve E: B × on a finite field GF (p). y ^ 2 = x ^ 3 + A × x ^ 2 + x parameter p (prime number), elements A and B of GF (p), and E (GF (p))
In the arithmetic unit, the x-coordinates of the point G that belongs to and the point of a constant multiple of the point G are given in advance, and the x-coordinate of the scalar-multiplied point k * G of the point G is input by inputting any k of n bits Yes,
It has a feature in performing calculation while effectively utilizing a value of a fixed multiple of the point G, and has a calculation procedure generation unit 610 and a scalar multiplication unit 62.
It consists of 0 and.

This elliptic curve calculation device 600 is common to the first embodiment in that it uses a value of a constant multiple of the point G held in advance, but those values are 2 * G and (2 ^ (i + 1).
+ 2 ^ i) * G (where i = 0, 1, 2, ..., N-
2), (2 ^ i) * G (where i = 1,
2, ..., N-1) is different from that of the first embodiment.

The calculation procedure generation unit 610 is a processing unit for executing preliminary calculation for generating a calculation procedure for calculating the scalar multiple k * G of the point G, and k * G is a constant multiple of G, that is,
Repeating division into an addition form using 2 * G or (2 ^ (i + 1) + 2 ^ i) * G, and the object of division at that time is an addition element obtained by the division or two addition elements The division target specifying unit 610a that specifies the difference (division type), and the array generation output unit 610b that outputs the division type specified by the division target specifying unit 610a as an array.

FIG. 21 is a calculation flow chart showing a method of coefficient division by the calculation procedure generation unit 610. In the present embodiment, the division target specifying unit 610a performs coefficient division according to the following two rules.

Rule 1 relates to the division method. Here, the division target specifying unit 610a sets c ≦ 2 for the division target ((2̂n) + c) * G, as shown in Rule 1 of the upper column [coefficient division guideline] of this figure. ^ (N
-1), it is divided into addition elements of plus expression,
That is, (2 ^ (n-2) + c) * G and (2 ^ (n-
1) + 2 ^ (n-2)) * G and c> 2 ^ (n
If it is −1), it is divided into addition elements represented by minus, that is, (2 ^ (n-1) + d) * G and (2 ^ n +).
2 ^ (n-1)) * G (where d = 2 ^)
n-c).

In this way, at least one of the addition elements obtained by the division is divided so as to be the sum of powers of two consecutive 2s (2 ^ (n-1) + 2 ^ (n-2)). That is, the coefficient sum of powers of 2 (2 ^ (n-1) +
2 ^ (n−2)) is added (hereinafter referred to as “first addition element”) and other addition elements (hereinafter referred to as “second addition element”). Note that the coefficient division divides two consecutive powers of 2 (2 ^ (n-1) + 2 ^
The reason why (n-2)) is generated is to perform elliptic curve addition by effectively using a storage table in which the value of the point G of such coefficient multiplication is held in advance, as described later.

Rule 2 relates to the object of division. Here, the division target specifying unit 610a, as shown in Rule 2 of the upper column of the figure [coefficient division guideline],
The larger of the difference between (i) the second addition element and (ii) the first addition element and the second addition element is divided. That is, the second
The process of comparing the addition element and the difference and dividing the larger one is repeated. This reduces the number of coefficient divisions.

Specifically, as shown in rule 2 of the figure, the first addition element (2 ^ 5 + 2 ^ 4) and the second addition element (2 ^ 4 + 7) obtained by dividing (2 ^ 6 + 7) ) And the difference (2 ^ 5-7), the second addition element (2 ^ 4 +
7) and the difference (2 ^ 5-7) are compared, and the larger one (2 ^ 5)
-7), the following coefficient division is repeated.

The reason why the coefficient division for the remaining (smaller) value in the above comparison is not necessary is that it will always appear in the subsequent coefficient division (becomes a target of coefficient division).

A specific example of coefficient division according to the above two rules is as shown in [Specific Example] of this figure. For 87 * G, the coefficient (87; 2 ^ 6)
+23) is divided into the first addition element (2 ^ 5 + 2 ^ 4) and the second addition element (2 ^ 4 + 23), and the difference (2 ^ 5-23) between them is calculated to obtain the first coefficient. Finish the division.

Next, the obtained second addition element (2 ^ 4 + 2)
3 = 2 ^ 5 + 7) is compared with the difference (2 ^ 5-23 = 2 ^ 3 + 1), and coefficient division is performed on the larger one (2 ^ 5 + 7). As a result, the first addition element (2 ^ 4 + 2 ^ 3) and the second addition element (2 ^ 3 + 7) and their difference (2 ^ 4-7)
To get

In this way, both the coefficient of the second addition element and the coefficient of the difference are repeated until the power of two consecutive sums of 2 or 2, respectively. After such coefficient division, the elliptic curve addition is repeated in the opposite direction to the coefficient division (from the lower digit to the upper digit) by referring to a storage table described later to obtain the final curve. Then, the scalar multiplication point (87 * G) of the point G can be obtained.

FIG. 22 is a flow chart showing the detailed processing procedure of the calculation procedure generation unit 610. The calculation procedure generated by the calculation procedure generation unit 610 is expressed by the following rules.

That is, the calculation procedure generator 610 receives an arbitrary integer k of k bits as an input and outputs the array {S [i]} (S
[I] outputs the i-th number of the array, 1 ≦ i ≦ | k |). In the array S [i], S [1] indicates information about the number of "0" s consecutive from the least significant digit in the binary representation of k, and S [2] indicates the last division target in the coefficient division. A division type is shown, and S [i] (i = 3,
4, ...) Indicate the division type in the i-th coefficient division.

Specifically, S [1] is k = k '× 2 ^
The value e when expressed as e, S [2] indicates the division type in the last division, as shown below, and S [i] (i = 3, 4, ...) Is the i-th In the second coefficient division, whether the element to be divided after the division is the second addition element (at that time, S [i] = 1 to indicate the first division type), or Is it the difference between the two addition elements that is divided after that division (at that time, as shown by the second division type,
S [i] = 2) is shown. Where k [1] and k
Regarding [2], if (1) k ′ = 1 (a special case), then S [1] = 1 and S [2] = 3,
(2) If k ′ = 3 (a special case), S
[1] = e, S [2] = 4, and (3) otherwise (most cases), (a) if the last division target coefficient is 2 ^ 2 + 1, S [ 1] = e, S [2]
= 1 and (b) the last division target coefficient is 2 ^ 3 +
In the case of 1, S [1] = e and S [2] = 2.

In the case of the above (3), it is known that the final division target coefficient is either the above (a) or (b). In FIG. 22, the division target specifying unit 610a follows the procedure described below for array {S [i]}.
Specify. In the following, k = k [n-1] * 2 ^ (n-1) + k [n-2] * 2
^ (N-2) + ... + k [1] × 2 + k [0], the bit representation of k is [k [n-1], k
Let [n-2], ..., K [1], k [0]]. Step S951: The maximum e, k 'that satisfies k = k' × 2 ^ e is obtained. Step S952: The counter c ← n−1 indicating the bit position to be processed and the index c1 ← 3 designating the element of the array S [i] are set. Step S953: It is determined whether k '= 1. If k ′ = 1, this corresponds to the case of (1) above, and step S954
What. Otherwise, go to step S955. Step S954: S [1] ← 1, S [2] ← 3, S
As [3] ← 2, S [4] ← 2, ..., S [e] ← 2 (S954a), the array {S [i]} is output (S954).
b), end. Step S955: Determine whether k '= 3 (S955
a). When k ′ = 3, it corresponds to the case of (2) above,
S [1] ← e and S [2] ← 4 are set (S955b), the array {S [i]} is output (S955c), and the processing is ended. Step S956: It is determined whether k '[c-1] = 1 (S956a). When k ′ [c−1] = 1, this corresponds to coefficient division by the minus expression, c ← c + 1 and c2 ← 0 are set (S956b), and the process proceeds to step S958. Other than that, it corresponds to the coefficient division by the plus expression, and goes to the next step. Step S957: k '[c-2] = 0, k' [c-3]
It is determined whether both = 0 are satisfied (S957a). In the case where both are satisfied, it is the case that the difference after the coefficient division is the difference between both addition elements, so c2 ← -1 is set (S957b), and the process proceeds to the next step. In other cases, the second divided element is the one that is divided after this coefficient division, and therefore the processing proceeds to step S959. Step S958: k '← 2 ^ c + 2 ^ (c-1) -k'
By updating k ′ and setting S [c1] ← 2, the coefficient division by the second division type is completed. Go to step S961. Step S959: It is determined whether k ′ [c−2] = 0 holds (S959a). If so, c2 ← -1 (S95
9b), if not satisfied, c2 ← 0 (S959c)
And Step S960: k '← k'-2 ^ (c-1) -2 ^
By updating k'as (c-2) and setting S [c1] ← 1, coefficient division by the first division type is completed. Step S961: c ← c− to shift to the next digit
Let 1 + c2, c1 ← c1 + 1. Step S962: It is determined whether k '= 5 or k' = 9. When k ′ = 5, this corresponds to the case of (3) (a) above, and the process proceeds to the next step. When k ′ = 9, the above (3)
This corresponds to the case of (b), and proceeds to step S964. Otherwise, it is necessary to further divide the coefficients, so step S9
Return to 56, until the division target is "5" or "9",
The same process is repeated. Step S963: The array {S [i]} is output as S [1] ← e, S [2] ← 1, and the process ends. Step S964: The array {S [i]} is output as S [1] ← e, S [2] ← 2, and the process ends.

The scalar multiplication unit 620 calculates the calculation procedure S [i] output from the calculation procedure generation unit 610 (i = 1, 2,
, Which is a calculation unit for calculating and outputting the final calculation result k * G by repeating addition on the elliptic curve based on the table storage unit 620b that stores a predetermined multiple of the point G in advance. , A temporary storage unit 62 that is a working memory
0c, an elliptic curve addition unit 620d that is an adder that performs addition on an elliptic curve, and an operation control unit 620a that controls each of the components 620b to 620d according to the calculation procedure S [i] from the calculation procedure generation unit 610.

As shown in FIG. 23, the table storage unit 620b stores the x-coordinates of the constant multiple points of the n points G, that is,
2 * G and (2 ^ (i + 1) + 2 ^ i) * G (where i
= 0, 1, 2, ..., N−2) x-coordinate is stored in advance in a ROM or the like. That is, the number of stored values is almost the same as that in the first embodiment, but the values are different.

The calculation control unit 620a reverses the calculation flow (coefficient division) of FIG. 21 by the calculation procedure generation unit 610, that is, referring to the values stored in the table storage unit 620b, starting from the lowest digit. By controlling each of the constituent elements 620b to 620d so as to repeat the elliptic curve addition toward higher digits, k * G is calculated. Specifically, the arithmetic control unit 620a performs calculation / control according to the following steps so that the scalar multiplication unit 620 operates according to the flowchart of FIG. Step S971: First, S [2] is determined (S971
a). The case of S [2] = 4 corresponds to the case of (2) above, and k * G is referred from the table storage unit 620b (S
971b), output (S971c), and end. Step S972: After setting e ← S [1] (S972
a), it is determined whether k [n-2] = 1 (S972b).
If it holds, a counter c1 ← n−e (S972c) indicating the number of necessary coefficient divisions (number of digits), c1 otherwise.
← n-e-1 (S972d). Step S973: It is determined whether S [2] = 3 (S97
3a). If it holds, it corresponds to the case of (1) above,
U ← G, V ← 2 * G, c2 ← 1 (S973b),
Go to step S975. Otherwise, step S974
What. In this flow, U is the second addition element and V is the first addition element.
This is a parameter that stores the difference between the addition element and the second addition element. For 2 * G, the table storage unit 620
It is the value read from b. Step S974: Determine whether S [2] = 1 (S97
4a). If so, U ← 2 * G, V ← G, c2 ← 1
(S974b), otherwise, U ← 3 * G, V ← 3
* G, c2 ← 2, c1 ← c1-1 (S974
c). Note that 2 * G and 3 * G are values read from the table storage unit 620b. Step S975: As described above, the initial values U and V
After determining, the table storage unit 620b is referenced to set W ← (2 ^ c2 + 2 ^ (c2-1)) * G. W is a parameter for storing the first addition element.
Note that (2 ^ c2 + 2 ^ (c2-1)) * G is a value read from the table storage unit 620b. Step S976: It is determined whether S [c1] = 1. Elliptic curve addition corresponding to the first split type, if
That is, to generate the second addition element U, go to the next step. Otherwise, go to step S978 to generate an elliptic curve addition corresponding to the second division type, that is, a difference V between both addition elements. Step S977: The elliptic curve addition unit 620d is caused to execute the elliptic curve addition to calculate U ← W + U (the difference is V). Step S978: After setting T ← V, the elliptic curve adding unit 620d is caused to calculate V ← W + U (the difference is V), and U ← T. Step S979: Determine whether c1 = 3. If so, go to step S981 to execute the final elliptic curve addition. Step S980: c1 ← c1-1, c2 ← c2 + 1 is set, and the same elliptic curve addition is repeated until c1 = 2, and the process returns to step S975. Step S981: By referring to the table storage unit 620b, W ← (2 ^ c2 + 1 + 2 ^ c2) * G, and let the elliptic curve addition unit 620d calculate U ← W + U (the difference is V) (S981a), and the result U Is output as the final result (S981b), and the process ends.

Note that (2 ^ c2 + 2 ^ (c2-1)) *
G is a value read from the table storage unit 620b. The specific calculation method of the elliptic curve addition used in the above steps is as described in the first embodiment.

The overall operation of the elliptic curve calculation device 600 configured as described above is as follows. The elliptic curve calculation device 600 receives the input integer k and inputs it to the calculation procedure generation unit 610. The calculation procedure generation unit 610
An array {S [i]} is calculated from the integer k and input to the scalar multiplication unit 620. The scalar multiplication unit 620 calculates the table storage unit 620 from the input array {S [i]}.
By repeating the elliptic curve addition while referring to the value stored in b, the scalar multiplication point k * G of the point G of the elliptic curve is calculated and output.

2. Operation of Elliptic Curve Calculation Device 600 for Specific Numerical Example Below, a numerical example in the case of k = 102 shown in FIG. 25 will be shown. First, the processing in the calculation procedure generation unit 610 will be described. Here, not the mechanical processing (bit processing) by the calculation procedure generation unit 610 but the meaning and content thereof will be described.

As shown in [Generation of Calculation Procedure] in FIG. 25, the division target specifying unit 610a is 102 = 51 × 2̂1.
From this, k ′ = 51 and e = 1 are specified (step S95).
2). From k ′ = 51, k ′ [5], k ′ [4],
k ′ [3], k ′ [2], k ′ [1], and k ′ [0] are 1,1,0,0,1,1 respectively.

Next, the coefficient division is repeated for k '(steps S952 to S962). First, k '= 51 =
For 2 ^ 5 + 19, from 19> 2 ^ 4, coefficient division by negative expression, that is, 2 ^ 5 + 19 = 2 ^ 6-13
Is divided into a coefficient (2 ^ 5 + 2 ^ 4) of the first addition element and a coefficient (2 ^ 4-13) of the second addition element, and a difference (2 ^ 5 + 13) between them is calculated. Then, the coefficient (2 ^ 4-13) of the second addition element is compared with the difference (2 ^ 5 + 13). Since the difference is larger, the difference (2 ^ 5)
+13) is divided. At the same time, an array element (S [3] = 2) indicating that (coefficient division by the second division type)
Is determined (step S958).

Next, the coefficient (2 ^ 5 + 1) to be divided is
For 3), from 13 ≦ 2 ^ 4, coefficient division by the plus expression, that is, the coefficient of the first addition element (2 ^ 4 + 2 ^)
3) and the coefficient of the second addition element (2 ^ 3 + 13), and the difference (2 ^ 4-1) between them is calculated. Then, the coefficient (2 ^ 3 + 13) of the second addition element and the difference (2 ^ 3)
413), the second addition element is larger, so
Next, the second addition element (2 ^ 3 + 13) is divided. At the same time, the array element (S [4] = 1) indicating that (coefficient division by the first division type) is determined (step S960).

Thereafter, the same coefficient division is repeated to determine the array element S [5] = 1 (step S96).
0), the final division target “9” is obtained. Since this division target “9” corresponds to the cases of (3) and (b) above, it is determined that S [1] = e = 1 and S [2] = 2 (step S964).

Finally, the array generation / output unit 610b outputs the arrays S [1], S [2], S obtained by the above coefficient division.
The value of [3], S [4], S [5], that is, {1, 2,
2, 1, 1} is output to the scalar multiplication unit 620 (step S965).

Next, the processing of the scalar multiplication unit 620 that has acquired the array {S [i]} from the calculation procedure generation unit 610 will be described in terms of its meaning rather than mechanical processing (bit processing). To do.

As shown in [Scalar multiplication operation] in FIG. 25, the scalar multiplication operation unit 620 first sets S [2] = 2, S.
Since [1] = 1, as the initial value, the second addition element U (6 *
G) and the difference (6 * G) between both addition elements (step S9)
74c; each coefficient is multiplied by 2 ^ 1 since S [1] = 1).

From the table storage section 620b, the first
The addition element W ((2 ^ 3 + 2 ^ 2) * G) is read (step S975), and from S [5] = 1 (step S97).
6), an elliptic curve of the first addition element W ((2 ^ 3 + 2 ^ 2) * G) referenced from the table storage unit 620b and the second addition element U ((2 ^ 2 + 2 ^ 1) * G) of the initial value The addition is executed, and the result is the second addition element U ((2 ^ 4 + 2 ^
1) * G) (step S977).

Similarly, from S [4] = 1 (step S976), the first reference from the table storage unit 620b is performed.
Elliptic curve addition of the addition element W ((2 ^ 4 + 2 ^ 3) * G) and the second addition element U ((2 ^ 3 + 10) * G) calculated immediately before is executed, and the result is the second addition element. U ((2 ^
5 + 10) * G) (step S977).

Then, from S [3] = 2 (step S9)
76), elliptic curve addition of the first addition element W ((2 ^ 5 + 2 ^ 4) * G) referenced from the table storage unit 620b and the second addition element U ((2 ^ 4 + 26) * G) calculated immediately before And the result is the difference value V ((2 ^ 6 + 26)
* G) (step S978).

Finally, based on the first addition element W ((2 ^ 6 + 2 ^ 5) * G) referenced from the table storage section 620b and the difference value V ((2 ^ 6 + 26) * G) calculated immediately before, The first addition element W ((2 ^ 6 + 2 ^ 5) * G) and the second
Elliptic curve addition with the addition element U ((2 ^ 5-26) * G) is executed (step S981a), and the result is the final result (2 ^ 7-26) * G, that is, 102 * G. Is output as a result (step S981b).

As described above, in the fifth embodiment, the calculation procedure S [i] generated by the calculation procedure generation unit 610 does not use the value of the power of 2 of the point G held in advance,
Coefficient division is performed so that a value that is scalar-multiplied by two consecutive sums of powers of 2 is used for the point G. As a result, the scalar multiple k * G of the point G is calculated with a smaller number of times of elliptic curve addition as compared with the first embodiment.

3. Effects of Fifth Embodiment According to the elliptic curve calculation device 600 of the present embodiment, for example, 102 * G in the second embodiment shown in FIG.
As can be seen by comparing the calculation flow of (6 additions) with that of the present embodiment (4 additions) shown in FIG. compared,
1.5 times faster. That is, compared with the prior art 3, 2.
26 times faster.

Further, in the case of calculation of 87 * G, according to the elliptic curve calculation device 600 of the present embodiment, the addition of 4 times is sufficient, and the addition of 7 times is required in the first to fourth embodiments. Compared with Prior Art 3, the speed is 1.75 times faster, which is 2.2.
6 times faster.

The values stored in the table storage unit 620b in this embodiment are different from those in the first to fourth embodiments, but the numbers are almost the same (in the first to fourth embodiments, ( (n-1) values are stored, and since n values are stored in the fifth embodiment), their storage capacities are almost the same.

As described above, according to the fifth embodiment, the scalar multiplication operation of the point G is executed faster than in the first to fourth embodiments, even though the sizes of the storage tables are almost the same, and the real time is performed. It can be applied to concealment in communication, and the practical value of the present invention is very large.

In the fifth embodiment, the table storage unit 620b stores a constant multiple of n points G, that is, 2 * G and (2 ^ (i + 1) + 2 ^ i) * G (where i = 0. ，
1, 2, ..., N-2) are stored in advance, but only a part of them may be stored. For example, 2 * G
Is calculated by the scalar multiplication unit 620 performing doubling, and need not be stored in the table storage unit 620b. As a result, the number of values stored in advance in the table storage unit 620b becomes (n-1), which is the same as in the first to fourth embodiments.

[Sixth Embodiment] Next, an elliptic curve calculation device according to a sixth embodiment of the present invention will be described. 1. Configuration and Operation of Elliptic Curve Calculation Device 700 FIG. 26 shows an elliptic curve calculation device 70 according to the sixth embodiment.
It is a block diagram which shows the structure of 0. This elliptic curve calculation device 700 is realized by a logic circuit such as a computer device or an LSI that executes a dedicated program, as in the first embodiment, and is a Montgomery type elliptic curve E: B × on a finite field GF (p). y ^ 2 = x ^ 3 + A × x ^ 2 + x parameter p (prime number), elements A and B of GF (p), and E (GF (p))
Is a computing unit that is given in advance a point G belonging to the point G and a point of a constant multiple of the point G, and outputs a scalar multiple k * G of the point G by inputting an arbitrary k of n bits. It is characterized in that it calculates while effectively utilizing the value of, and outputs not only the x coordinate of the scalar multiplication point k * G but also the y coordinate.

In other words, the elliptic curve calculation devices according to the first to fifth embodiments calculate only the x coordinate of the scalar multiplication point k * G to be calculated, but the elliptic curve calculation device 700 according to the present embodiment calculates the scalar to be calculated. Calculate the x and y coordinates of the double point k * G. This is for the following reason.

Some encryption systems using elliptic curves include
Not only the scalar multiplication operation of a certain point (k * P for the point P, L * Q for the point Q, etc.) but also the addition of k * P + L * Q is required (for example, ECDSA verification). However, in the Montgomery-type elliptic curve, k *
Although P and L * Q can be calculated, k * P + L * Q cannot be added. Therefore, for k * P + L * Q, it is necessary to perform the same addition as for the Weierstrass-form elliptic curve, and the Y coordinate is required for the addition.
In other words, the elliptic curve calculation device 700 according to the present embodiment uses not only the x coordinate of the scalar multiple k * G but also the cryptographic system that requires the calculation of k * P + L * Q.
The y coordinate is also calculated.

The elliptic curve calculation device 700 uses k * G as a calculation procedure for calculating the scalar multiple K * G of the point G.
Is a constant multiple of G, that is, 2 * G or (2 ^ (i + 1) +
2 ^ i) A point that is repeatedly divided into addition forms using * G, and a value that is a constant multiple of the point G held in advance is 2
* G and (2 ^ (i + 1) + 2 ^ i) * G (where i
= 0, 1, 2, ..., N−2) is stored in common with the elliptic curve calculation device 600 according to the fifth embodiment. In other words, this elliptic curve calculation device 700 has the same calculation procedure generation unit 610 as the elliptic curve calculation device 600 of the fifth embodiment, and a scalar multiplication unit that executes a scalar multiplication operation in a procedure substantially similar to that of the fifth embodiment. And 720.
Hereinafter, components common to the elliptic curve calculation device 600 of the fifth embodiment will be denoted by the same reference numerals, description thereof will be omitted, and different points will be mainly described.

The scalar multiplication unit 720 calculates the calculation procedure S [i] output from the calculation procedure generation unit 710 (i = 1, 2,
..) to calculate and output the final calculation result k * G by repeating addition on the elliptic curve, which has substantially the same configuration as the scalar multiplication unit 620 of the fifth embodiment. Elements are provided, but a table storage unit 720b is provided instead of the table storage unit 620b of the fifth embodiment,
Also, the difference is that a Y-coordinate restoring unit 720e is further provided.

As shown in FIG. 27, the table storage unit 720b stores the x-coordinates and the y-coordinates of the constant multiple points of the n points G, that is, 2 * G and (2 ^ (i + 1) + 2 ^ i) *. G
It is a ROM or the like in which the x and y coordinates of (where i = 0, 1, 2, ..., N-2) are stored in advance.

The Y coordinate restoring unit 720e performs the final elliptic curve addition by the elliptic curve adding unit 620d by the same iterative calculation as the scalar multiplication operation in the fifth embodiment, and then the element ( P1 + P2 → P
Points P, P1, P2 in the above, where the point P2 is the scalar multiplication point k * G finally obtained according to the formula of the Y coordinate restoration using the coordinates of the point stored in the table storage unit 720b).
Restore (calculate) the y-coordinate of Specifically, points P and P
Using the x and z coordinates of 1 and the x and y coordinates of the point P2, Y
The y coordinate of the point P is restored according to the coordinate restoration formula.

FIG. 28 shows the Y by the Y coordinate restoration unit 720e.
It is a figure explaining the basic approach of coordinate restoration. The premise, symbols, and formulas are shown in the upper column of the figure [Y-coordinate restoration formula]. Now, the Montgomery elliptic curve:
At B × y ^ 2 = x ^ 3 + A × x ^ 2 + x, the point P1
By the elliptic curve addition of (X1, Y1, Z1) and the point P2 (x2, y2, 1), the final scalar multiplication point P (X,
Suppose that Y, Z) is obtained. Here, the coordinates of each point are expressed by projective coordinates (a triplet of X, Y, Z). Further, the point P2 has its x-coordinate and y-coordinate set in the table storage unit 720.
This is the point previously stored in b.

At this time, assuming that the coordinates of the point P after the Y coordinate restoration are (Xrec, Yrec, Zrec), these coordinates are
It is expressed by the following formula. Xrec =-(2 * B * y2 * Z * Z1) * X Yrec = Z1 * [(X + x2 * Z + 2 * A * Z) * (X
Xx2 + Z) -2xAxZ ^ 2]-(X-x2xZ) ^
2 × X1 Zrec = − (2 × B × y2 × Z × Z1) × Z That is, the coordinates required to restore the Y coordinate of the point P are the points P and P.
The X and Z coordinates of 1 and the X and Y coordinates of the point P2.

In the lower column of this figure [application to the embodiment],
The processing procedure of the Y coordinate restoration unit 720e using the above Y coordinate restoration formula is shown. That is, the final point P = k *
In order to calculate G = (2 ^ n + c) * G, the point P2 = (2 ^ (n-1) +2 is calculated by the elliptic curve addition unit 620d.
^ (N-2)) * P and the point P1 = (2 ^ (n-1) +
c)) * P and their difference (2 ^ (n-1) -c) * P
Since the elliptic curve addition using and is performed, immediately after that,
The Y coordinate restoration unit 720e restores the Y coordinate of the point P using the X and Z coordinates of the points P and P1 and the X and Y coordinates of the point P2 according to the above Y coordinate restoration formula.

FIG. 29 is a flowchart showing the operation of the scalar multiplication unit 720, which corresponds to the flowchart (FIG. 24) of the scalar multiplication unit 620 in the fifth embodiment. The difference from the flowchart of FIG. 24 is the final elliptic curve addition (S181a) and the Y coordinate restoration (S181b).

Under the control of the arithmetic control unit 620a, the elliptic curve addition unit 620d performs the final elliptic curve addition (S181a). That is, by referring to the table storage unit 720b, that point (2 ^ c2 + 1 + 2 ^ c2) * G
Is substituted for the value W, the value U calculated by the immediately preceding elliptic curve addition is substituted for the value T, and then the elliptic curve addition of the values W and U is performed (the difference is the value V) to obtain the value. The result is substituted for the value U (S181a).

Finally, the Y coordinate restoration unit 720e
Is the X and Z coordinates of the values T and U and the X and Y coordinates of the W (coordinates stored in the table storage unit 720b) according to the Y coordinate restoration formula described above.
The coordinates are restored (S181b), and the obtained value U (X, Y and Z coordinates) is output (S181c).

As described above, the scalar multiplication unit 620 repeats the scalar multiplication operation (elliptic curve addition) of the point G (S971a to 181a), similarly to the first to fifth embodiments, the x coordinate of the point G. (In the 3-tuple projective coordinate, x coordinate and z
(Coordinates) is repeated, and the point k * G (U) and the point k * G are calculated in the Y coordinate restoration immediately after the elliptic curve addition for obtaining the final point k * G is performed (S181b). X and Z of each second addition element (U) used in
The Y coordinate of the point k * G is restored using the coordinate and the X and Y coordinates of the first addition element (W; the point stored in the table storage unit 720b) used to calculate the point k * G. is doing.

2. Operation of Elliptic Curve Calculation Device 700 for Specific Numerical Example Below, a numerical example in the case of k = 102 shown in FIG. 30 will be shown. Note that the processing in the calculation procedure generation unit 710 is the same as the processing in the fifth embodiment (upper column in FIG. 25), and therefore is not shown in this figure.

An example of calculation by the scalar multiplication unit 720 is shown in the upper column of the figure [Elliptic curve addition]. That is,
It is shown that the calculation of the scalar multiple point (x coordinate and z coordinate) of the point G is repeated by repeating the elliptic curve addition from the lower digit to the higher digit. This calculation procedure is the same as in the case of the fifth embodiment (lower column of FIG. 25). However, with the x-coordinate of (2 ^ 5-26) * G used when 102 * G was calculated by elliptic curve addition of (2 ^ 6 + 2 ^ 5) * G and (2 ^ 5-26) * G For the z coordinate,
The temporary storage unit 620c is used for the next Y coordinate restoration.
Stored in.

[0206] The bottom section of the book, [Y Coordinate Restoration], shows the state of Y coordinate restoration by the Y coordinate restoration unit 720e which is executed immediately after the last elliptic curve addition is performed. That is, the Y-coordinate restoring unit 720e receives 102 * G and (2 ^ 5
-26) * G x and z coordinates and (2 ^ 6 + 2 ^ 5) *
From the x and y coordinates of G (values stored in the table storage unit 720b), according to the above Y coordinate restoration formula, 10
Restore the y coordinate of 2 * G.

The scalar multiplication unit 720 outputs 102 * G (x, y and z coordinates) thus obtained. 3. Effects of Embodiment 6 According to the elliptic curve calculation device 700 of this embodiment, only the x coordinate (x and z coordinates in the projective coordinates of the triplet) of the scalar multiplication point k * G of the point G to be finally obtained is used. However, the y coordinate is also calculated. The operation added to calculate the y coordinate is
Only the Y coordinate restoration operation immediately after the final elliptic curve addition.

Therefore, with the elliptic curve calculation device 700 of the present embodiment, only a small amount of calculation is added, and in addition to the effect of the fifth embodiment, the cipher requiring the y-coordinate of the scalar multiplication point is required. The effect that it can also be applied to the system is exhibited.

It should be noted that the elliptic curve calculation device 7 of the present embodiment.
00 indicates to the elliptic curve calculation device 600 of the fifth embodiment, Y
Although the function of coordinate restoration is added, the present invention is not limited to such a combination.
That is, the function of Y coordinate restoration in the present embodiment (the function of storing not only the x coordinate but also the y coordinate in the table storage unit and performing the calculation of the Y coordinate) is performed in the first to fourth embodiments. It may be added to any elliptic curve calculation device. As a result, in any of the elliptic curve calculation devices according to the first to fifth embodiments, the x coordinate and the y coordinate of the scalar multiplication point are generated, and the application range of these elliptic curve calculation devices is expanded.

The elliptic curve calculation device in the above embodiments can perform, for example, the scalar multiplication operation of the base point G which is a system parameter in the public key cryptography using the elliptic curve, and uses the public key cryptography. It is effective as a calculation engine for secret communications and digital signatures. Such an elliptic curve calculation device can be realized as a program executed by a general-purpose computer or as an IC such as an LSI.

That is, as shown in FIG. 31, a communication device such as a personal computer or a mobile phone can be used in an elliptic curve calculation device according to the present embodiment and encryption, decryption, or digital processing based on scalar multiplication by the elliptic curve calculation. By providing an encryption / decryption device that performs signature, digital signature verification or key sharing, electronic payment, electronic signature, e-mail in a communication network such as the Internet, or concealment of communication data by a mobile phone, etc. Can be realized.

[0212]

As is apparent from the above description, the elliptic curve calculation device according to the present invention executes a scalar multiplication operation satisfying the following conditions. (1) Performs an operation on a Montgomery-type elliptic curve capable of performing an elliptic curve operation (addition / multiplication) at a higher speed than the Wire-Strass elliptic curve. (2) In the scalar multiplication of the base point G, which is a system parameter in the elliptic curve cryptosystem, a point that is a constant coefficient multiple of the point G, that is, a power of 2 (2 ^ i) * G times the point G, or Two consecutive sums of two powers of point G (2
It is possible to effectively use a table that stores any one of ^ (n-1) +2 (n-2)) * G times. (3) Scalar multiplication point k
It is possible to calculate not only the x-coordinate of * G (x-coordinate and z-coordinate in the projective coordinate of the triplet) but also the y-coordinate.

[Brief description of drawings]

FIG. 1 is a functional block diagram showing a configuration of an elliptic curve calculation device according to a first embodiment of the present invention.

FIG. 2 is a flowchart showing an operation of a calculation procedure generation unit of the elliptic curve calculation device.

FIG. 3 is a diagram showing data stored in a table storage unit of the same elliptic curve calculation device.

FIG. 4 is a flowchart showing an operation of a scalar multiplication unit of the elliptic curve calculation device.

FIG. 5 is a calculation flowchart showing a method (basic idea; approach 1) of a scalar multiplication operation by the elliptic curve operation device.

FIG. 6 is a calculation flowchart showing a method of scalar multiplication by the same elliptic curve calculation device (approach 2 obtained by expanding approach 1).

FIG. 7 is a diagram for comparatively explaining the calculation methods in the first embodiment and the conventional technique 3.

FIG. 8 is a functional block diagram showing a configuration of an elliptic curve calculation device according to a second embodiment of the present invention.

FIG. 9 is a flowchart showing an operation of a calculation procedure generation unit of the elliptic curve calculation device.

FIG. 10 is a flowchart showing an operation of a scalar multiplication unit of the elliptic curve calculation device.

FIG. 11 is a calculation flowchart showing a method of scalar multiplication by the elliptic curve calculation device.

FIG. 12 is a functional block diagram showing a configuration of an elliptic curve calculation device according to a third embodiment of the present invention.

FIG. 13 is a flowchart showing an operation of a calculation procedure generation unit of the elliptic curve calculation device.

FIG. 14 is a flowchart showing an operation of a scalar multiplication unit of the elliptic curve calculation device.

FIG. 15 is a calculation flowchart showing a generation process of a calculation procedure (array {S [i]}) by a calculation procedure generation unit of the elliptic curve calculation device.

16 is a diagram showing the operation of the scalar multiplication unit corresponding to the specific example shown in FIG.

FIG. 17 is a functional block diagram showing a configuration of an elliptic curve calculation device according to a fourth embodiment of the present invention.

FIG. 18 is a flowchart showing an operation of the elliptic curve calculation device.

FIG. 19 is a calculation flowchart showing the operation of the elliptic curve calculation device.

FIG. 20 is a functional block diagram showing a configuration of an elliptic curve calculation device according to a fifth embodiment of the present invention.

FIG. 21 is a calculation flowchart showing a method of coefficient division by the calculation procedure generation unit of the elliptic curve calculation device.

FIG. 22 is a flowchart showing a detailed processing procedure of a calculation procedure generation unit of the elliptic curve calculation device.

FIG. 23 is a diagram showing data stored in a table storage unit of the elliptic curve calculation device.

FIG. 24 is a flowchart showing an operation of a scalar multiplication unit of the elliptic curve calculation device.

FIG. 25 is a diagram showing a process of the elliptic curve calculation device for a specific numerical example.

FIG. 26 is a functional block diagram showing the configuration of an elliptic curve calculation device according to a sixth embodiment of the present invention.

FIG. 27 is a diagram showing data stored in a table storage unit of the elliptic curve calculation device.

FIG. 28 is a diagram illustrating Y by a Y coordinate restoration unit of the elliptic curve calculation device.
It is a figure explaining the basic approach of coordinate restoration.

FIG. 29 is a flowchart showing an operation of a scalar multiplication unit of the elliptic curve calculation device.

FIG. 30 is a diagram showing a process of the elliptic curve calculation device for a specific numerical example.

FIG. 31 is a diagram showing an application example of the elliptic curve calculation device according to the present invention.

FIG. 32 is a sequence diagram showing a procedure of a digital signature method using an El Gamal signature.

FIG. 33 is a calculation flow chart schematically showing a calculation procedure of a scalar multiplication operation in Conventional Technique 3.

[Explanation of symbols]

200, 300, 400, 500, 600, 700
Elliptic curve calculation device 210, 310, 410, 610 Calculation procedure generation unit 210a, 510a Addition element identification unit 210b, 310b, 410b, 610b Array generation output unit 220, 320, 420, 620, 720 Scalar multiplication calculation unit 220a, 320a, 420a, 510, 620a Operation control units 220b, 320b, 420b, 520, 620b, 7
20b Table storage units 220c, 320c, 420c, 510c, 620c
Temporary storage units 220d, 320d, 420d, 530, 620d Ellipse addition unit 310a Addition type identification unit 410a Addition element representation switching point identification unit 510a Bit determination unit 610a Division target identification unit 720e Y coordinate restoration unit

Claims (31)

[Claims] 1. An elliptic curve operation for inputting an arbitrary n-bit integer k and outputting a scalar multiplication point k * G for a point G on a Montgomery-form elliptic curve E on a finite field F given in advance. A point G having a predetermined scalar value of n or less as a coefficient
An elliptic curve calculation device comprising: a scalar multiplication unit for calculating the scalar multiplication point k * G by repeating addition on the elliptic curve E using the scalar multiplication point as a first addition element. 2. The first addition element is G, 2 * G, (2
The elliptic curve calculation device according to claim 1, wherein any one of ^ 2) * G, ..., (2 ^ (n-1)) * G. 3. The elliptic curve calculation device further comprises calculation procedure generation means for generating a calculation procedure indicating an iterative procedure of addition on the elliptic curve E, and the scalar multiplication operation means is the calculation procedure generation means. The elliptic curve calculation device according to claim 2, wherein the scalar multiplication point k * G is calculated in accordance with the calculation procedure generated by. 4. The calculation procedure generating means is a natural number m, u
, (2 ^ (m-1) + u) * G, (2 ^ (m-1)) * G
And a first calculation for calculating (2 ^ m + u) * G from u * G, or (2 ^ (m + 1)-from (2 ^ m) * G, (2 ^ m-u) * G and u * G. u) * G for the second calculation, or (2 ^ m) * G,-(2 ^ m-u) * G and (2 ^ (m
4. The elliptic curve calculation device according to claim 3, wherein a calculation procedure for generating a third calculation for calculating u * G from +1) -u) * G as addition on the elliptic curve E is generated. 5. The calculation procedure generation means is configured to perform addition on the elliptic curve E and the first calculation according to the value of each bit of the k.
5. The calculation procedure is generated by associating with at least one of the third calculations.
The elliptic curve calculation device described. 6. The calculation procedure generation means, when the value of the bit of k is 0, associates at least the first calculation as an addition on the elliptic curve E corresponding to the bit, and the bit 6. The calculation procedure is generated when at least the second calculation is made to correspond to the addition on the elliptic curve E corresponding to the bit when the value of is 1. Elliptic curve calculator. 7. The calculation procedure generation means is configured such that, in each addition in the repetition of addition on the elliptic curve E, the expression form of the second addition element to be added with the first addition element is positive in the first calculation. Expression (2 ^ (m-1) +
u) * G or minus expression (2 ^ m−u) * G in the second calculation, the expression procedure information is generated as the calculation procedure, and the scalar multiplication unit calculates the ellipse. The elliptic curve calculation device according to claim 3, wherein any one of the first to third calculations is performed based on the expression format information in each addition in the repetition of addition on the curve E. . 8. The expression format information indicates whether the second addition element is switched from which expression of the positive expression and the negative expression to which expression each time the addition is repeated on the elliptic curve E. The elliptic curve calculation device according to claim 7, which is information indicating. 9. The expression format information indicates the number of consecutive occurrences of the second addition element in one of the expression expressions of the plus expression and the minus expression in the repetition of addition on the elliptic curve E. The elliptic curve calculation device according to claim 7, which is information. 10. The scalar multiplication unit is G, 2 *
G, (2 ^ 2) * G, ..., (2 ^ (n-1)) * G has a table storage unit for storing at least a part thereof, and the points stored in the table storage unit are first added. The elliptic curve calculation device according to claim 2, wherein addition on the elliptic curve E is performed as an element. 11. The first addition element is 2 * G, 3 *.
G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2 (n
2. The elliptic curve calculation device according to claim 1, which is any one of -2)) * G. 12. The elliptic curve calculation device further comprises calculation procedure generation means for generating a calculation procedure indicating an iterative procedure of addition on the elliptic curve E, and the scalar multiplication operation means is the calculation procedure generation means. The elliptic curve calculation device according to claim 11, wherein the scalar multiplication point k * G is calculated according to the calculation procedure generated by. 13. The calculation procedure generating means is a natural number m,
For u, the first addition element (2 ^ (m-1) + 2 ^ (m-2)) *
G, the second addition element (2 ^ (m-2) + u) * G, and the difference between the first addition element and the second addition element (2 ^ (m-
1) -u) to calculate (2 ^ m + u) * G, or a first addition element (2 ^ m + 2 ^ (m-1)) * G and a second addition element (2 ^ (m- 1) -u) * G and the difference (2 ^ m + u) between the first addition element and the second addition element from (2 ^)
13. The elliptic curve calculation device according to claim 12, wherein a calculation procedure that generates a second calculation for calculating (m + 1) -u) * G is addition on the elliptic curve E is generated. 14. The calculation procedure generation means sets the result obtained by the addition on the elliptic curve E by the first or the second calculation as a second addition element in the next iterative addition, or a first addition element. The elliptic curve calculation device according to claim 13, wherein division target information indicating whether the difference between the second addition element and the second addition element is generated is the calculation procedure. 15. The calculation procedure generation means generates information including the value k ′ and the value e in the case where k is expressed as k ′ × 2 ^ e, as initial information included in the calculation procedure. The elliptic curve calculation device according to claim 14. 16. The calculation procedure generating means generates the initial information including information indicating whether k ′ is 1, 3 or another value, in the initial information. The elliptic curve calculation device described. 17. The scalar multiplication unit is 2 * G, 3.
* G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2
(N−2)) * G has a table storage unit that stores at least a part of it, and performs addition on the elliptic curve E by using the point stored in the table storage unit as a first addition element. The elliptic curve calculation device according to claim 11. 18. The elliptic curve calculation device according to claim 1, further comprising y-coordinate restoration means for restoring the y-coordinate of the scalar multiple k * G. 19. The first addition element is G, 2 * G,
One of (2 ^ 2) * G, ..., (2 ^ (n-1)) * G, wherein the scalar multiplication unit is a triplet of projective coordinates (x, y,
z), the x and z coordinates of the scalar multiplication point k * G are calculated by repeating addition on the elliptic curve E using the x coordinate of the first addition element, and the y coordinate restoration means. Is the projection coordinate (x, y,
z), the x and z coordinates of the scalar multiplication point k * G and the x and z coordinates of the second addition element added to the first addition element used to calculate the scalar multiplication point k * G. And the x and y coordinates of the first addition element, the scalar multiplication point k *
The elliptic curve calculation device according to claim 18, wherein the y coordinate of G is restored. 20. The first addition element is 2 * G, 3 *
G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2 (n
-2)) * G, wherein the scalar multiplication unit is a triplet of projective coordinates (x, y,
z), the x and z coordinates of the scalar multiplication point k * G are calculated by repeating addition on the elliptic curve E using the x coordinate of the first addition element, and the y coordinate restoration means. Is the projection coordinate (x, y,
z), the x and z coordinates of the scalar multiplication point k * G and the x and z coordinates of the second addition element added to the first addition element used to calculate the scalar multiplication point k * G. And the x and y coordinates of the first addition element, the scalar multiplication point k *
The elliptic curve calculation device according to claim 18, wherein the y coordinate of G is restored. 21. A cryptographic device for performing encryption based on an arithmetic operation on a Montgomery-type elliptic curve, wherein an arbitrary n-bit integer k is input, and on a Montgomery-type elliptic curve E on a finite field F given in advance. For point G of
An elliptic curve calculation means for outputting a scalar multiplication point k * G; and a utilization means for performing encryption, decryption, digital signature, digital signature verification or key sharing based on the scalar multiplication operation by the elliptic curve calculation means, The elliptic curve calculation means repeats addition on the elliptic curve E with the scalar multiplication point of the point G having a predetermined scalar value of n or less as a coefficient to be the first addition element to repeat the scalar multiplication point k. A cryptographic device characterized by calculating * G. 22. Inputting an arbitrary integer k of n bits,
This is an elliptic curve calculation method for outputting a scalar multiplication point k * G for a point G on a Montgomery-form elliptic curve E on a finite field F given in advance. Point G as coefficient
An elliptic curve calculation method comprising: a scalar multiplication operation step of calculating the scalar multiplication point k * G by repeating addition on the elliptic curve E using the scalar multiplication point as a first addition element. 23. The first addition element is G, 2 * G,
23. The elliptic curve calculation method according to claim 22, wherein one of (2 ^ 2) * G, ..., (2 ^ (n-1)) * G. 24. The first addition element is 2 * G, 3 *
G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2 (n
23) The elliptic curve calculation method according to claim 22, wherein any one of -2)) * G. 25. The elliptic curve calculation method further includes a calculation procedure generation step of generating a calculation procedure indicating an iterative procedure of addition on the elliptic curve E, and in the scalar multiplication step, the calculation procedure generation step. The scalar multiplication point k * G according to the calculation procedure generated by
23. The elliptic curve calculation method according to claim 22, wherein 26. The elliptic curve calculation method according to claim 22, further comprising a y coordinate restoration step of restoring the y coordinate of the scalar multiplication point k * G. 27. Inputting an arbitrary n-bit integer k,
A program for an elliptic curve calculation device that outputs a scalar multiplication point k * G for a point G on a Montgomery-form elliptic curve E on a finite field F given in advance. Point G with a coefficient of a scalar type
And a scalar multiplication operation step for calculating the scalar multiplication point k * G by repeating addition on the elliptic curve E using the scalar multiplication point as a first addition element. 28. The first addition element is G, 2 * G,
The program according to claim 27, wherein the program is any one of (2 ^ 2) * G, ..., (2 ^ (n-1)) * G. 29. The first addition element is 2 * G, 3 *.
G, 6 * G, 12 * G, ..., (2 ^ (n-1) +2 (n
The program according to claim 27, which is any one of -2)) * G. 30. The program further includes a calculation procedure generation step for generating a calculation procedure indicating a repeating procedure of addition on the elliptic curve E, and the scalar multiplication operation step generates the calculation procedure generation step. According to the calculation procedure, the scalar multiplication point k * G
28. The program according to claim 27, wherein 31. The program according to claim 27, wherein the program further includes a y-coordinate restoring step of restoring the y-coordinate of the scalar multiple k * G.