JP3460798B2 - Elliptic product-sum calculation method, elliptic-product-sum calculation device, and recording medium storing elliptic-product-sum calculation program - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for realizing a high-speed elliptic product sum operation of a plurality of points of a cubic function on a field F _p , which is used in cryptography, and a program therefor. The present invention relates to a recorded recording medium.

[0002]

2. Description of the Related Art In elliptic cryptography, an elliptic curve E _P on a prime field (finite field)

[0003]

[Equation 7]

A solution set of the above integer points (x, y) is regarded as a message space. That is, the points on the elliptic curve are limited to a finite integer value (0 or more and less than p), and the calculation is the remainder divided by this upper limit value p (mod calculation).

Now, let P (x ₁ , y ₁ ), Q (x ₂ , y ₂ ) be two points on the elliptic curve E _P on the prime field F _P , and T = cP + dQ.
Is the value to be calculated. T (x ₃ , y ₃ ) is also a point on the elliptic curve E _P. FIG. 6 shows a flowchart of a conventional calculation procedure. However, c and d are

[0006]

[Equation 8]

Binary representation is performed as in the above, and the coefficient of the i-th bit of c and d is respectively defined as c _i , d _i (ε {0,1}). k is _ck
It is a maximum integer such that ≠ 0 or d _k ≠ 0. Also,
The definitions of various operations on the elliptic curve are as follows.

The ellipse doubling operation T = 2P is 1. If P = a _{(0,0), x 3 = 0} , y 3 = 0 2. If P ≠ (0,0),

[0009]

[Equation 9] And

Further, the elliptic curve addition operation T = P + Q is 3. When P = (0,0), x ₃ = x ₂ , y ₃ = y ₂ 4. If P ≠ (0,0) and Q = (0,0), then x
₃ = x ₁ , y ₃ = y ₁ 5. P ≠ (0,0), Q = (0,0), and P + Q
= (0,0), x ₃ = 0, y ₃ = 0 6. P ≠ (0,0), Q ≠ (0,0) and P + Q ≠
If (0,0),

[0011]

[Equation 10] And

The flowchart of FIG. 6 executes the following processing. T ← 0 for (i = k; i ≧ 0; i−−) {if ((c _i == 0) && (d _i == 0)) then {T ← 2T} if ((c _i == 1) ) && (d _i == 0)) then {T ← 2T; T
← T + P} if ((c _i == 0) && (d _i == 1)) then {T ← 2T; T
← T + Q} if ((c _i == 1) && (d _i == 1)) then {T ← 2T; T
← T + (P + Q)}} Return T 0 is set to T as an initial value, and i = k, k−1, ...,
The values (00) and (0) of (c _i , d _i ) in the order of 2, 1, 0
Predetermined operations are repeatedly executed according to 1), 10), and 11 to obtain the final result T.

According to the processing procedure shown in FIG. 6, the required number of elliptic curve addition / subtraction and elliptic curve doubling required for the conventional calculation procedure is shown in FIG. 7 using k defined above.

[0014]

SUMMARY OF THE INVENTION An object of the present invention is an elliptic product that multiplies a plurality of different points on an elliptic curve on a prime field (finite field) by an integer and adds the results of the integer multiplication. Method and apparatus capable of performing sum operation at higher speed than in the prior art, and recording medium recording the program
To provide the body .

[0015]

In the present invention, a prime field F _p having p as a prime number is _defined as

[Equation 11] 2 on the elliptic curve Ep on the field Fp defined by
Let P and Q be points, and set two independent integers c and d,

[Equation 12] Expressed in binary as follows, and the coefficient of the i-th bit of c and d
Be c _i , d _i (ε {0, 1}), and c ₋₁ = d ₋₁ =
0, c _{2k + 1} + c _2k + c _2k-1 ≠ 0, d _{2k + 1}
By defining the maximum k such that + d _2k + d _2k−1 ≠ 0, the elliptic product sum calculation T = cP + dQ is calculated by a computer including a control circuit, a storage circuit and a calculation circuit.
It is automatically calculated by the following method . Control circuit
Is the initial value of the parameters P and Q and the calculation result T.
And stores T = 0 in the memory circuit, and thereafter two sets of integers c and d are set.
From i = k, k−1, ..., 2, 1, 0
Next, by shifting by 2 bits, (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i d _2i-1 ) is selected, and this selected (c _{2i + 1} c _2i c _2i-1 d ) is selected. _{2i + 1} d _2i
Based on the value of d _2i-1 ), (1) (000000) or (111000),
Ruiha (000111) or (111111)
In this case, the operation (2) (001000) or (010000), which is executed in the order of T ← 2T, T ← 2T ,
Ruiha (001111) or (010111)
In this case, T ← 2T, T ← 2T, T ← T + P are executed in this order.
Calculation (3) (000001) or (111001)
Ruiha (000010) or (11110)
In this case, T ← 2T, T ← 2T, T ← T + Q are executed in this order.
Calculation (4) (101000) or (110000)
Ruiha (101111) or (110111)
In this case, T ← 2T, T ← 2T, T ← TP are executed in this order.
Calculation (5) (000101), or (111101),
Ruiha (000110) or (111110)
In this case, T ← 2T, T ← 2T, T ← T-Q are executed in this order.
That operation, (6) (001001), or (010001), Oh
Ruiha (001010) or (010010)
In this case, T ← 2T, T ← 2T, T ← T + (P + Q) in that order.
Operation to be executed, (7) (001101), or (010101)
Ruiha (001110) or (010110)
In this case, T ← 2T, T ← 2T, T ← T + (P−Q) in that order.
The operation to be executed, (8) (101001), or (110001),
Ruiha (101010) or (110010)
In this case, T ← 2T, T ← 2T, T ← T- (PQ) in that order.
Operation to be executed, (9) (101101), or (110101)
Ruiha (101110) or (110110)
In the case of T ← 2T, T ← 2T, T ← T- (P + Q)
The operation to be executed, (10) (011000), or (011111)
In this case, T ← 2T, T ← T + P, T ← 2T are executed in this order.
Calculation of (11) (000011) or (111011)
In this case, T ← 2T, T ← T + Q, T ← 2T are executed in this order.
Calculation of (12) (100000) or (100111)
In this case, T ← 2T, T ← TP, T ← 2T are executed in this order.
Calculation of (13) (000100) or (111100)
In this case, T ← 2T, T ← TQ, T ← 2T are executed in this order.
In the case of (14) (011011), T ← 2T, T ← T +
(P + Q), operation performed in the order of T ← 2T, (15) (011100), T ← 2T, T ← T +
(P-Q), operation performed in the order of T ← 2T, (16) (100011), T ← 2T, T ← T-
(P-Q), operation performed in the order of T ← 2T, (17) (100100), T ← 2T, T ← T-
(P + Q), operation performed in the order of T ← 2T, (18) (011001), or (011010)
In case of T ← 2T, T ← T + P, T ← 2T, T ← T + Q
Operation executed in order , (19) (011101), or (011110)
In case of T ← 2T, T ← T + P, T ← 2T, T ← T-Q
Operations that are executed in sequence, (20) (100001), or (100010)
In case of T ← 2T, T ← T-P, T ← 2T, T ← T + Q
Calculations executed in sequence, (21) (100101), or (100110)
In case of T ← 2T, T ← T-P, T ← 2T, T ← T-Q
Calculations that are executed in sequence, (22) (001011), or (010011)
In case of T ← 2T, T ← T + Q, T ← 2T, T ← T + P
Calculations executed in sequence, in the case of (23) (101011) or (110011)
, T ← 2T, T ← T + Q, T ← 2T, T ← TP
The operation executed in (24) (001100) or (010100)
In case of T ← 2T, T ← T−Q, T ← 2T, T ← T + P
The operation to be executed in order, (25) (101100), or (110100)
In case of T ← 2T, T ← T-Q, T ← 2T, T ← TP
The operation circuit is instructed to perform one of the operations executed in order.
To show. The arithmetic circuit is based on the instruction from the control circuit,
Input P, Q, T from the memory circuit and perform the specified operation
The calculation result T is returned to the memory circuit.

[0016]

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of the present invention will be described below. Here, an elliptic curve E _P on a prime field (finite field) with p as a prime number

[0017]

[Equation 13]

The two points above are P (x ₁ , y ₁ ), Q (x ₂ ,
y ₂ ), and the sum of elliptic products T = cP + dQ is obtained. T (x ₃ , y ₃ ) is also a point on the elliptic curve E _P. However, c and d are

[0019]

[Equation 14]

Binary representation is performed as described above, and coefficients of the i-th bit of c and d are respectively defined as c _i and d _i (ε {0,1}). Also,
Let c ₋₁ = d ₋₁ = 0. k is c _{2k + 1} + c _2k + c _2k-1 ≠
0 or a maximum integer such that d _{2k + 1} + d _2k + d _2k-1 ≠ 0.

FIG. 1 shows an example of the configuration of the present elliptic product sum operation computing device. In FIG. 1, a control circuit 100 controls the entire operation. The control circuit 100 has a register for holding c and d, a counter for counting the variable i, and the like,
i = k, k-1, ..., 2, 1, 0, in order, (c
_{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i d _2i-1 ) is selected, and according to the value, the memory circuit 110 is instructed to read the predetermined data, and the arithmetic circuit 120 is instructed. Specify the type of operation and execution order. The memory circuit 110 includes P, Q, P + Q, and P-.
Data such as Q and T (initial value is 0) is stored, and the data instructed by the control circuit 100 is read and given to the arithmetic circuit 120. The arithmetic circuit 120 has a function of performing operations such as double operation, addition, and subtraction, and receives the data given from the memory circuit 110 as input, and executes the instructed operations of the control circuit 100 in the instructed order. , T of the calculation result is returned to the memory circuit 110.

FIG. 2 shows a schematic processing flowchart of the elliptic product sum operation computing device. Under the control of the control circuit 100, parameters P, Q, c, d, etc. are input, P, Q are stored in the memory circuit 110, and c, d are set in the internal register of the control circuit 100 (step 210). Next, the control circuit 1
00 to control the operations of the memory circuit 110 and the arithmetic circuit 120 to execute the calculation of T = cP + dQ (step 22
0), and the calculation result T is output (step 230).

FIG. 3 is a detailed processing flowchart of the calculation part (step 220) of T = cP + dQ in FIG.
Further, FIG. 4 shows the contents of cases (Case) 1 to 25 in FIG.

The definitions of various operations on the elliptic curve are as follows. (1) Elliptic double operation T = 2P 1. If P = a _{(0,0), x 3 = 0} , y 3 = 0 2. If P ≠ (0,0),

[0025]

[Equation 15]

(2) Elliptic curve addition operation T = P + Q 1. When P = (0,0), x ₃ = x ₂ , y ₃ = y ₂ 2. If P ≠ (0,0) and Q = (0,0), then x ₃
= X ₁ , y ₃ = y ₁ . P ≠ (0,0), Q = (0,0), and P + Q =
In the case of (0,0), x ₃ = 0, y ₃ = 0 4. P ≠ (0,0), Q ≠ (0,0), and P + Q ≠
If (0,0),

[0027]

[Equation 16]

(3) Elliptic subtraction operation T = P-Q 1. When P = (0,0), x ₃ = x ₂ , y ₃ = p−y ₃ 2. If P ≠ (0,0) and Q = (0,0), then x
₃ = x ₁ , y ₃ = y ₁ 3. P ≠ (0,0), Q = (0,0), and P = Q
In the case of, x ₃ = 0, y ₃ = 0 4. P ≠ (0,0), Q ≠ (0,0), and P ≠ Q
In the case of,

[0029]

[Equation 17]

The flowchart of FIG. 3 executes the following processing. T ← 0 for (i = k; i ≧ 0; i−−) {if (Case1) then {T ← 2T; T ← 2T} else if (Case2) then {T ← 2T; T ← 2T; T ← T
+ P} else if (Case3) then {T ← 2T; T ← 2T; T ← T
+ Q} else if (Case 4) then {T ← 2T; T ← 2T; T ← T
-P} else if (Case 5) then {T ← 2T; T ← 2T; T ← T
-Q} else if (Case 6) then {T ← 2T; T ← 2T; T ← T
+ (P + Q)} else if (Case 7) then {T ← 2T; T ← 2T; T ← T
+ (P−Q)} else if (Case8) then {T ← 2T; T ← 2T; T ← T
-(P-Q)} else if (Case 9) then {T ← 2T; T ← 2T; T ← T
− (P + Q)} else if (Case10) then {T ← 2T; T + P; T ← 2
T} else if (Case11) then {T ← 2T; T + Q; T ← 2
T} else if (Case12) then {T ← 2T; TP-T; T ← 2
T} else if (Case13) then {T ← 2T; T−Q; T ← 2
T} else if (Case14) then {T ← 2T; T + (P + Q); T
← 2T} else if (Case15) then {T ← 2T; T + (P−Q); T
← 2T} else if (Case16) then {T ← 2T; T- (P-Q); T
← 2T} else if (Case17) then {T ← 2T; T- (P + Q); T
← 2T} else if (Case18) then {T ← 2T; T + P; T ← 2
T; T ← T + Q} else if (Case19) then {T ← 2T; T + P; T ← 2
T; T ← T−Q} else if (Case20) then {T ← 2T; T−P; T ← 2
T; T ← T + Q} else if (Case21) then {T ← 2T; TP-T; T ← 2
T; T ← T−Q} else if (Case22) then {T ← 2T; T + Q; T ← 2
T; T ← T + P} else if (Case23) then {T ← 2T; T + Q; T ← 2
T; T ← T−P} else if (Case24) then {T ← 2T; T−Q; T ← 2
T; T ← T + P} else if (Case25) then {T ← 2T; T−Q; T ← 2
T; T ← T-P}}

The program of the above processing procedure (this program is called an elliptic product sum calculation program) is provided by being recorded in a computer-readable recording medium such as a floppy disk, a memory card, a compact disk (CD-ROM) or the like. It is possible to Control circuit 100
However, the processing flow of FIG. 3 is realized by reading and executing the elliptic product sum calculation program of this recording medium. The control circuit 100 may hold a ROM in which the elliptic product sum calculation program is recorded in advance.

In the processing procedure shown in FIG. 3, P + Q and P-
It is necessary to calculate Q in advance and store it in the storage circuit 110. According to the processing procedure shown in FIG. 3, ellipse addition / subtraction and ellipse 2 required in the present embodiment are performed using k defined above.
The required number of times of double operation is shown in FIG. Compared with the conventional method of FIG. 7, the number of elliptic addition / subtraction operations can be reduced by about 20% on average.

FIG. 5 shows another embodiment of the control circuit 100, and shows a configuration example in which the processing of FIG. 3 is realized by a hardware lock. In FIG. 5, 101 is c and d
Is a shift register that stores 2 bits, shifts by 2 bits by shift lock, and i = k, k−1, ..., 2, 1,
The data (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d
_2i d _2i-1 ) is realized. Decoder 102
-1 to 102-25 correspond to cases 1 to 25 in FIG.
Output data of the shift register 101 (c _{2i + 1} c _2i c _2i-1
(d _{2i + 1} d _2i d _2i-1 ) is decoded in parallel, and if there is a match in any of them, the corresponding decoder outputs a match signal. The arithmetic control table 103 holds an arithmetic command group corresponding to case 1-25, and the decoders 102-1 to 10-2
Based on the decoded output of 2-25, the storage circuit 110 is instructed to read desired data under the control of the corresponding operation command group, and the operation circuit 120 is instructed about the type of operation and its execution order. To do.

According to the configuration of FIG. 5, the cases 1 and 2 of FIG.
The case classification of 5 can be processed in parallel, further speeding up is realized. Further, by using hard logic, it is possible to realize a semiconductor integrated circuit in which the control circuit 100, the memory circuit 110, and the arithmetic circuit 120 are integrally configured.

[0035]

As described above, according to the present invention,
An operation of multiplying two different points on the elliptic curve E _P on the prime field F _P by an integer and adding the results of the integer multiplication is performed by a conventional method using a signed iterative doubling method. There is an advantage that it can be calculated faster.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration example of an elliptic product sum computing device according to an embodiment of the present invention.

FIG. 2 is an overall processing flowchart of the elliptic product sum computing device of FIG.

FIG. 3 is a detailed processing flowchart of a product-sum operation calculation part in FIG.

FIG. 4 is a diagram showing the classification of operations and execution order in FIG.

5 is a diagram showing a configuration example in which the function of the control circuit of FIG. 1 is realized by hard logic.

FIG. 6 is a processing flowchart of an elliptic product sum performance according to a conventional method.

FIG. 7 is a diagram showing the number of elliptic curve addition operations and elliptic curve doubling operations required for the calculation process of the conventional method of FIG.

FIG. 8 is a diagram showing the number of elliptic curve addition / subtraction calculations and elliptic curve doubling calculations required for the calculation process of the embodiment of the present invention in FIG. 3;

[Explanation of symbols]

100 control circuit 110 memory circuit 120 arithmetic circuits

─────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-5-150722 (JP, A) JP-A-6-118873 (JP, A) The Fast Cascade Expenditure Alg origin and it's application on Cryptography, Lectur. es in Computer Science, Lecture Notes in Computer Science, p. 447-456 Public Key Cryptography Based on Cubic Curve, NTT R & D, October 10, 1995, Vol. 44, No. 10, p. 91-98 More Flexible Expiration with Precomputation, Lecture Notes in Computer Science, Vol. 839, p. 95-107 (58) Fields surveyed (Int.Cl. ⁷ , DB name) G09C 1/00 650 G06F 17/10 JISC file (JOIS)

Claims (3)

(57) [Claims] 1. A prime field F _p having p as a prime number is defined as follows: 2 on the elliptic curve Ep on the field Fp defined by
Let P and Q be points, and set two mutually independent integers c and d as follows : Expressed in binary as follows, and the coefficient of the i-th bit of c and d
Be c _i , d _i (ε {0,1}), and c ₋₁ = d ₋₁ =
0, c _{2k + 1} + c _2k + c _2k−1 ≠ 0, d _{2k + 1} + d
By defining the maximum k such that _2k + _d2k-1 ≠ 0 , the elliptic product sum calculation T = cP + dQ is automatically calculated by the computer including the control circuit, the storage circuit and the calculation circuit. The control circuit uses the parameters P, Q and the calculation result T as the first parameter.
T = 0 is stored in the memory circuit as the period value, and two sets of integers c,
From d, i = k, k−1, ..., 2, 1, 0
Then, by shifting by 2 bits, (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i d _2i-1 ) is selected, and the selected (c _{2i + 1} c _2i c _2i-1 d ) is selected. _{2i + 1} d _2i
Based on the value of d _2i-1 ), (1) (000000) or (111000),
Ruiha (000111) or (111111)
In this case, the operation (2) (001000) or (010000), which is executed in the order of T ← 2T, T ← 2T ,
Ruiha (001111) or (010111)
In this case, T ← 2T, T ← 2T, T ← T + P are executed in this order.
Calculation (3) (000001) or (111001)
Ruiha (000010) or (11110)
In this case, T ← 2T, T ← 2T, T ← T + Q are executed in this order.
Calculation (4) (101000) or (110000)
Ruiha (101111) or (110111)
In this case, T ← 2T, T ← 2T, T ← TP are executed in this order.
Calculation (5) (000101), or (111101),
Ruiha (000110) or (111110)
In this case, T ← 2T, T ← 2T, T ← T-Q are executed in this order.
That operation, (6) (001001), or (010001), Oh
Ruiha (001010) or (010010)
In this case, T ← 2T, T ← 2T, T ← T + (P + Q) in that order.
Operation to be executed, (7) (001101), or (010101)
Ruiha (001110) or (010110)
In this case, T ← 2T, T ← 2T, T ← T + (P−Q) in that order.
The operation to be executed, (8) (101001), or (110001),
Ruiha (101010) or (110010)
In this case, T ← 2T, T ← 2T, T ← T- (PQ) in that order.
Operation to be executed, (9) (101101), or (110101)
Ruiha (101110) or (110110)
In the case of T ← 2T, T ← 2T, T ← T- (P + Q)
The operation to be executed, (10) (011000), or (011111)
In this case, T ← 2T, T ← T + P, T ← 2T are executed in this order.
Calculation of (11) (000011) or (111011)
In this case, T ← 2T, T ← T + Q, T ← 2T are executed in this order.
Calculation of (12) (100000) or (100111)
In this case, T ← 2T, T ← TP, T ← 2T are executed in this order.
Calculation of (13) (000100) or (111100)
In this case, T ← 2T, T ← TQ, T ← 2T are executed in this order.
In the case of (14) (011011), T ← 2T, T ← T +
(P + Q), operation performed in the order of T ← 2T, (15) (011100), T ← 2T, T ← T +
(P-Q), operation performed in the order of T ← 2T, (16) (100011), T ← 2T, T ← T-
(P-Q), operation performed in the order of T ← 2T, (17) (100100), T ← 2T, T ← T-
(P + Q), operation performed in the order of T ← 2T, (18) (011001), or (011010)
In case of T ← 2T, T ← T + P, T ← 2T, T ← T + Q
Operation executed in order, (19) (011101), or (011110)
In case of T ← 2T, T ← T + P, T ← 2T, T ← T-Q
Operations that are executed in sequence, (20) (100001), or (100010)
In case of T ← 2T, T ← T-P, T ← 2T, T ← T + Q
Calculations executed in sequence, (21) (100101), or (100110)
In case of T ← 2T, T ← T-P, T ← 2T, T ← T-Q
Calculations that are executed in sequence, (22) (001011), or (010011)
In case of T ← 2T, T ← T + Q, T ← 2T, T ← T + P
Calculations executed in sequence, in the case of (23) (101011) or (110011)
, T ← 2T, T ← T + Q, T ← 2T, T ← TP
The operation executed in (24) (001100) or (010100)
In case of T ← 2T, T ← T−Q, T ← 2T, T ← T + P
The operation to be executed in order, (25) (101100), or (110100)
In case of T ← 2T, T ← T-Q, T ← 2T, T ← TP
One of the operations to be executed in order is instructed to the arithmetic circuit , and the arithmetic circuit stores the memory based on the instruction from the control circuit.
Input P, Q, and T from the circuit to perform the instructed operation
An elliptic product sum calculation method , which is executed and returns T as a calculation result to a storage circuit . 2. A prime field F _p having p as a prime number, and 2 on the elliptic curve Ep on the field Fp defined by
Let P and Q be points, and set two mutually independent integers c and d as follows : Expressed as a binary number, and the coefficient of the i-th bit of c and d
Be c _i , d _i (ε {0, 1}), and c ₋₁ = d ₋₁ =
0, c _{2k + 1} + c _2k + c _2k−1 ≠ 0, d _{2k + 1} + d
We define the maximum k such that _2k + d _2k-1 ≠ 0.
Te, In oval product-sum operation unit for calculating the elliptical sum operation calculates T = cP + dQ, storage means for storing the parameters P, Q, the operation result T, 2 sets of integers c, a storage unit for storing d, the Depending on the value of (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i d _2i-1 ) of two sets of integers c and d , (1) (000000) or (111000), or ( In the case of (000111) or (111111), the operation (2) (001000) or (010000), or (001111) or (010111), which is executed in the order of T ← 2T and T ← 2T, T ← 2T , T ← 2T, T ← T + P, (3) (000001), (111001), (000010), or (111010), T ← 2T, T ← 2T, T ← T + Q In the case of (4) (101000), (110000), (101111), or (110111), T ← 2T, T ← 2T, T ← TP (5) In the case of (000101), (111101), (000110), or (111110), an operation executed in the order of T ← 2T, T ← 2T, T ← TQ, (6) (001001) , Or (010001), or (001010), or (010010), the operations executed in the order of T ← 2T, T ← 2T, T ← T + (P + Q), (7) (001101), or (010101) , Or (001110) or (010110), the operations executed in the order of T ← 2T, T ← 2T, T ← T + (P−Q), ) In the case of (101001), (110001), (101010), or (110010), the operations executed in the order of T ← 2T, T ← 2T, T ← T- (PQ), (9) ( 101101), or (110101), or (101110), or (110110), the operations executed in the order of T ← 2T, T ← 2T, T ← T− (P + Q), (10) (011000), or In the case of (011111), the operation executed in the order of T ← 2T, T ← T + P, T ← 2T, (11) (000011), or in the case of (111011), T ← 2T, T ← T + Q, T ← 2T Operation to be executed in order, (12) (100000), or in the case of (100111), operation to be executed in the order of T ← 2T, T ← TP, T ← 2T, (13) (000100) , Or (111100), T ← 2T, T ← T−Q, T ← 2T, and (14) (011011), T ← 2T, T ← T +
(P + Q), operation performed in the order of T ← 2T, (15) (011100), T ← 2T, T ← T +
(P-Q), operation performed in the order of T ← 2T, (16) (100011), T ← 2T, T ← T-
(P-Q), operation performed in the order of T ← 2T, (17) (100100), T ← 2T, T ← T-
(P + Q), operation performed in the order of T ← 2T, (18) In the case of (011001) or (011010), operation performed in the order of T ← 2T, T ← T + P, T ← 2T, T ← T + Q, (19) In the case of (011101) or (011110), the operation executed in the order of T ← 2T, T ← T + P, T ← 2T, T ← TQ, (20) (100001), or (100010) In the case of T ← 2T, T ← T−P, T ← 2T, T ← T + Q, in the order of (21) (100101) or (100110), T ← 2T, T ← T−P, Operation executed in order of T ← 2T, T ← T−Q, (22) (001011), or (010011), executed in order of T ← 2T, T ← T + Q, T ← 2T, T ← T + P Calculation, (23) (101011) or ( In the case of 10011), T ← 2T, T ← T + Q, T ← 2T, T ← T-P are executed in this order, (24) (001100), or (010100), T ← 2T, T ← T -Q, T ← 2T, T ← T + P, (25) (101100) or (110100), T ← 2T, T ← T-Q, T ← 2T, T ← T-P Means for defining operations to be executed in the order of, and first, T = 0 is initially set in the storage means.
From integers c and d of i = k, k-1, ..., 2,1,0
Sequentially, by sequentially shifting by 2 bits and selecting (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i d _2i-1 ) , depending on the value, the above defined (1 )~(twenty five)
Control means for instructing the calculation means of the corresponding calculation
If, based on the instruction from the control unit, P from the storage means,
Input Q and T to execute the specified operation and
And a calculation means for returning the result T to the storage means.
A characteristic elliptic product sum calculation device . Wherein the element F _p to prime p, Equation 5] 2 on the elliptic curve Ep on the field Fp defined by
Let P and Q be points, and set two mutually independent integers c and d as follows : Expressed in binary as follows, and the coefficient of the i-th bit of c and d
Be c _i , d _i (ε {0, 1}), and c ₋₁ = d ₋₁ =
0, c _{2k + 1} + c _2k + c _2k−1 ≠ 0, d _{2k + 1} + d
By defining the maximum k such that _2k + _d2k-1 ≠ 0 , the elliptic product sum calculation T = cP + dQ is calculated by a computer including a control circuit, a storage circuit, and a calculation circuit.
Elliptic product sum calculation program for automatic calculation by computer
A computer-readable recording medium in which
Then, the control circuit first sets the parameters P and Q and the calculation result.
T = 0 is stored in the memory circuit as the initial value of T, and then 2
From the set of integers c and d, i = k, k−1, ..., 2 , 1, 0
In this order, by sequentially shifting by 2 bits each, (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i d _2i-1 ) is selected, and the selected (c _{2i + 1} c _2i c _2i-1 d _{2i + 1} d _2i
Based on the value of d _2i-1 ), (1) (000000) or (111000),
Ruiha (000111) or (111111)
In this case, the operation (2) (001000) or (010000), which is executed in the order of T ← 2T, T ← 2T ,
Ruiha (001111) or (010111)
In this case, T ← 2T, T ← 2T, T ← T + P are executed in this order.
Calculation (3) (000001) or (111001)
Ruiha (000010) or (11110)
In this case, T ← 2T, T ← 2T, T ← T + Q are executed in this order.
Calculation (4) (101000) or (110000)
Ruiha (101111) or (110111)
In this case, T ← 2T, T ← 2T, T ← TP are executed in this order.
Calculation (5) (000101), or (111101),
Ruiha (000110) or (111110)
In this case, T ← 2T, T ← 2T, T ← T-Q are executed in this order.
That operation, (6) (001001), or (010001), Oh
Ruiha (001010) or (010010)
In this case, T ← 2T, T ← 2T, T ← T + (P + Q) in that order.
Operation to be executed , (7) (001101), or (010101)
Ruiha (001110) or (010110)
In this case, T ← 2T, T ← 2T, T ← T + (P−Q) in that order.
The operation to be executed, (8) (101001), or (110001),
Ruiha (101010) or (110010)
In this case, T ← 2T, T ← 2T, T ← T- (PQ) in that order.
Operation to be executed, (9) (101101), or (110101)
Ruiha (101110) or (110110)
If T ← 2T, T ← 2T, T ← in the order of T- (P + Q)
The operation to be executed, (10) (011000), or (011111)
In this case, T ← 2T, T ← T + P, T ← 2T are executed in this order.
Calculation of (11) (000011) or (111011)
In this case, T ← 2T, T ← T + Q, T ← 2T are executed in this order.
Calculation of (12) (100000) or (100111)
In this case, T ← 2T, T ← TP, T ← 2T are executed in this order.
Calculation of (13) (000100) or (111100)
In this case, T ← 2T, T ← TQ, T ← 2T are executed in this order.
In the case of (14) (011011), T ← 2T, T ← T +
(P + Q), operation performed in the order of T ← 2T, (15) (011100), T ← 2T, T ← T +
(P-Q), operation performed in the order of T ← 2T, (16) (100011), T ← 2T, T ← T-
(P-Q), operation performed in the order of T ← 2T, (17) (100100), T ← 2T, T ← T-
(P + Q), operation performed in the order of T ← 2T, (18) (011001), or (011010)
In case of T ← 2T, T ← T + P, T ← 2T, T ← T + Q
Operation executed in order, (19) (011101), or (011110)
In case of T ← 2T, T ← T + P, T ← 2T, T ← T-Q
Operations that are executed in sequence, (20) (100001), or (100010)
In case of T ← 2T, T ← T-P, T ← 2T, T ← T + Q
Calculations executed in sequence, (21) (100101), or (100110)
In case of T ← 2T, T ← T-P, T ← 2T, T ← T-Q
Calculations that are executed in sequence, (22) (001011), or (010011)
In case of T ← 2T, T ← T + Q, T ← 2T, T ← T + P
Calculations executed in sequence, in the case of (23) (101011) or (110011)
, T ← 2T, T ← T + Q, T ← 2T, T ← TP
The operation executed in (24) (001100) or (010100)
In case of T ← 2T, T ← T−Q, T ← 2T, T ← T + P
The operation to be executed in order, (25) (101100), or (110100)
In case of T ← 2T, T ← T-Q, T ← 2T, T ← TP
The operation circuit is instructed to perform one of the operations executed in order.
Shimesuru treatment process, the arithmetic circuit, based on an instruction from the control circuit, the order
Next, input P, Q, T from the memory circuit
The processing process for executing the calculated calculation and returning the calculation result T to the memory circuit.
Process for running computer
A recording medium characterized by being recorded.