JP3935902B2 - Generator polynomial generator and program recording medium thereof - Google Patents

Description

  The present invention relates to an arithmetic device on an elliptic curve used for realizing information security technology (elliptic curve encryption / signature, prime factorization), for example.

When realizing public key cryptography and digital signature on an elliptic curve, most of the processing time is spent on k-fold computation on the elliptic curve.
In general, an elliptic curve defined on a finite field GF (q) is used for encryption and signature. This is expressed as E / GF (q). q is a prime number or a power of a prime number. In the conventional mounting method, a prime number or 2 ^m is often used for q, but the present invention considers a general finite field.
An addition to point P on the elliptic curve can be defined. This is called “elliptical addition” or “elliptical doubling” to distinguish from normal addition. Both can be performed by combining addition / subtraction / multiplication / division on the finite field GF (q).

In general, a method of combining “ellipse addition” and “elliptical doubling operation” is used to configure the k-fold operation.
Therefore, the computation on the elliptic curve can be reduced to addition / subtraction / multiplication / division on the finite field GF (q), and speeding up these leads to speeding up the computation on the elliptic curve.
The elliptic curve calculation, GF (q _n) on the rational formula of column _{R (x 0, x 1,} ...) and x _0, x _1, enter the ... values of the GF (q _n) calculator, GF ( q _n-1 ) is passed to a GF (q _n-1 ) calculator that results in data and the GF (q _n-1 ) calculator receives the input as a sequence of calculations on GF (q _n-2 ). To the GF (q _n−2 ) computing unit, and the same thing is repeated, and the result calculated by the GF (q ₀ ) computing unit is output, that is, sequentially expanded, Japanese Patent Application No. 11-230123 entitled “Elliptic Curve Calculation Device and Program Recording Medium Using Sequential Enlargement” proposes that the number of multiplications can be reduced from the conventional elliptic curve calculation.

As squarer in this case of GF (q _n-1) of the m-th extension field _{GF (q n) = GF (} q n-1 m) on the GF (q _n-1) arithmetic unit, input A = (A ₀ , A ₁ ), the output A ² = (C ₀ , C ₁ ) by the element on the original GF (q _n-1 ) on GF (q _n ) = GF (q _n-1 ^m ) according to the normal basis If the bases are α and β (where α + β = −v ₁ ), A = A ₀ α + A ₁ β, A ² = C ₀ α + C ₁ β, and GF (q _{n− 1} ) Let the upper mth degree irreducible polynomial be f (x) = x ² + v ₁ x + v ₀ ,
A ² = (− A ₀ ² v ₁ + (A ₀ −A ₁ ) ² (v ₀ / v ₁ )) α
+ (− A ₁ ² v ₁ + (A ₀ −A ₁ ) ² (v ₀ / v ₁ )) β
It has been proposed to perform the operation. That computes A ₀ ² → L ₀ in GF (q _n-1) squarer 27B as shown in FIG. _{9, GF (q n-1} ) to calculate the A ₀ -A ₁ → L ₁ by the subtracter 27C , GF (q _n-1 ) squarer 27D calculates A ₁ ² → L ₂ , GF (q _n-1 ) squarer 27E calculates L ₁ ² → L ₃ , and GF (q _n-1 ) The constant multiplier 27F calculates −v ₁ L ₀ → L ₄ and the GF (q _n−1 ) constant multiplier 27G calculates (−v ₁ ) ⁻¹ (−v ₀ ) L ₃ → L ₅ , The GF (q _n-1 ) constant multiplier 27H calculates −v ₁ L ₂ → L ₆ , the GF (q _n−1 ) adder 27I calculates L ₄ + L ₅ → C ₀ , and GF (q _{n -1} ) The adder 27J calculates L ₅ + L ₆ → C ₁ to obtain A ² = (C ₀ , C ₁ ).

In this way, three square calculations and three multiple calculations are sufficient.
Also, the performed using a polynomial basis of GF (q _n-1) of m-th extension _{GF (q n) = GF (} q n-1 m) in the elliptic curve calculation using sequential enlargement, but used in its polynomial basis The generator polynomial must be irreducible. In the case of normal bases, when expanding sequentially, a generator of a normal base suitable for high-speed computation is defined for each expansion, thereby defining an irreducible polynomial with all the bases in the solution. Make a row of Therefore, when creating an irreducible polynomial, this solution must be a normal basis.

  An object of the present invention is to provide an apparatus for generating a generator polynomial for obtaining a base suitable for sequential expansion in an elliptic curve calculation apparatus using sequential expansion.

  Performing a procedure for generating a generator polynomial candidate, a selection procedure for selecting one of the generator polynomial candidates f (x), and an inspection procedure for checking whether the selected candidate f (x) is irreducible, If it is determined that the inspection procedure is irreducible, the selected candidate f (x) is output as a generator polynomial. If it is determined that the inspection procedure is not irreducible, the selection procedure and the inspection procedure are repeated.

  It is possible to generate a polynomial basis generator polynomial used for the expansion in the successive expansion elliptic curve calculation.

Squarer (normal basis)
This apparatus is an example configuration according to m-th extension _{GF (q n) = GF (} q n-1 m) on the squarer of GF (q _n-1) above arithmetic unit GF (q _n-1).
In this configuration example, m = 2, and when the m- _th order generator polynomial on GF (q _n-1 ) having all bases as solutions is f (x) = x ² + v ₁ x + v ₀ , v ₀ = u ² This is a device in the case where uεGF (q _n-1 ) exists.

In this explanation and in FIG. 1, A = (A ₀ , A ₁ ) and A ² = (C ₀ , C ₁ ) are the original GF on GF (q _n ) = GF (q _n−1 ^m ) according to the normal basis. (Q _n-1 ) is an expression based on the element, and when the base is α and β, it means A = A ₀ α + A ₁ β and A ² = C ₀ α + C ₁ β, respectively.
The apparatus 100 shown in the figure outputs an element A ² on GF (q _n ) in response to an input of _element A = (A ₀ , A ₁ ) on GF (q _n ) = GF (q _n−1 ^m ). 1 illustrates an example of a configuration of a device.

When the operation of this apparatus is realized by a program, it is executed according to the flow shown in FIG.
The GF (q _n ) multiplier 100 includes a GF (q _n-1 ) constant multiplier, a GF (q _n-1 ) adder, a GF (q _n-1 ) subtractor, and GF (q _{n− 1} ) It is composed of a multiplier, a controller 111 for controlling them, and a memory 112.
The GF (q _n−1 ) subtractor 101 receives A ₀ and A ₁ as inputs, and the GF (q _n−1 ) constant multiplier 102 receives the output L ₁ of the subtractor 101 as input, and GF (q _n−1 ). The adder 103 receives A ₀ and the output L ₅ of the constant multiplier 102, the GF (q _n-1 ) subtractor 104 receives A ₀ and L ₅ , and the GF (q _n-1 ) adder 105 L ₅ and A ₁ are input, the GF (q _n−1 ) subtractor 106 receives L ₅ and A ₁ , and the GF (q _n−1 ) multiplier 107 receives the output of the adder 103 and the subtractor 104. The output is input, the GF (q _n−1 ) constant multiplier 108 receives the multiplier 107, and the GF (q _n−1 ) multiplier 109 receives the output of the adder 105 and the output of the subtractor 106 as inputs. , GF (q _n-1 ) constant multiplier 110 receives the output of multiplier 109 as an input.

The squarer 100 operates as follows.
An input value A = (A ₀ , A ₁ ) is input and temporarily stored in the memory 112. Although not specifically described below, data necessary for the operation is read from the memory 112, and the operation result is stored in the memory 112.
_{Step1: GF (q n-1} ) The subtractor 101 calculates the L ₁ ← A ₀ -A ₁ outputs an L ₁ with respect to A ₀ and A ₁ of the input.
Step 2: The GF (q _n-1 ) constant multiplier 102 calculates L ₅ <-(u / v ₁ ) L ₁ for the input L ₁ and outputs L ₅ .

Step 3: The GF (q _n-1 ) adder 103 calculates and outputs L ₅ + A ₀ for the inputs L ₅ and A ₀ .
Step 4: The GF (q _n-1 ) subtractor 104 calculates L ₅ -A ₀ for the input L ₅ , A ₀ and outputs it.
Step 5: The GF (q _n-1 ) adder 105 calculates and outputs L ₅ + A ₁ for the input L ₅ and A ₁ .
Step 6: The GF (q _n-1 ) subtractor 106 calculates and outputs L ₅ -A ₁ for the input L ₅ and A ₁ .

Step 7: The GF (q _n−1 ) multiplier 107 calculates T ₀ ← (L ₅ + A ₀ ) (L ₅ −A ₀ ) for the inputs (L ₅ + A ₀ ) and (L ₅ −A ₀ ). And output.
Step 8: The GF (q _n−1 ) constant multiplier 108 calculates −v ₁ (L ₅ + A ₀ ) (L ₅ −A ₀ ) for the input (L ₅ + A ₀ ) (L ₅ −A ₀ ). And output as C ₀ .
Step 9: The GF (q _n-1 ) multiplier 109 calculates T ₁ <-(L ₅ + A ₁ ) (L ₅ -A ₁ ) for the inputs (L ₅ + A ₁ ) and (L ₅ -A ₁ ). And output.
Step 10: The GF (q _n-1 ) constant multiplier 110 calculates -v ₁ (L ₅ + A ₁ ) (L ₅ -A ₁ ) for the input (L ₅ + A ₁ ) (L ₅ -A ₁ ). and outputs it as C ₁ to.
Step 11: (C ₀ , C ₁ ) is output as A ² .

Generator polynomial used to the generator polynomial generator shown in generating polynomial generator Figure 2 carried out using a polynomial basis of GF (q _n-1) of m-th extension _{GF (q n) = GF (} q n-1 m) It is an example of 1 structure of the apparatus which calculates | requires. The apparatus 200 is configured by connecting a memory 202 and an irreducibility determination apparatus 203 to a control apparatus 201.

When the operation of this apparatus is realized by a program, it is executed according to the flow shown in FIG.
Step 0: The control device 201 inputs the input finite field GF (q _n-1 ) and the expansion order m. Further, j generator polynomial candidates f _i (x), (i = 1,..., J) are generated. i is initialized to 0.
Check if i = j and if i is not j Step 1: Select a generator polynomial candidate f _i (x) on the input finite field GF (q _n-1 ) by adding i to +1.
Step 2: Use the irreducibility determination device 203 to check whether the f _i (x) is irreducible.
Step 3: If irreducible, output f _i (x) as generator polynomial g (x). If not irreducible, go back to Step 1 and try again.
The configuration of the irreducibility determination device 203 will be described later.

Moreover, as a structure of this apparatus, the structure by the following structures and its combination can also be made.
When f (x) is a quadratic polynomial x ² + v ₁ x + v ₀ , a candidate f _i (x) with v ₁ = −1 is generated at Step 0 for the purpose of performing multiplication using a polynomial basis at high speed. .

If f (x) is a quadratic polynomial x ² + v ₁ x + v ₀ , candidates f _i (x) for which v ₁ = 0 in Step 0 are obtained for the purpose of performing inverse elements and squares using polynomial bases at high speed. Generate.
A candidate that can be expressed as v ₁ = 0 and v ₀ = u ² in Step 0 for the purpose of performing high-speed square using a polynomial basis when f (x) is a quadratic polynomial x ² + v ₁ x + v ₀ Generate f _i (x).

Regular polynomial normalized polynomial generating apparatus shown in normal polynomial generator Figure 3 used to perform GF a (q _n-1) of m-th extension _{GF (q n) = GF (} q n-1 m) using a normal basis It is an example of 1 structure of the apparatus which calculates | requires. The apparatus 300 is configured by connecting a memory 302, an irreducibility determination apparatus 303, and a regular determination apparatus 304 to a control apparatus 301.

When the operation of this apparatus is realized by a program, it is executed according to the flow shown in FIG.
Step 0: A finite field GF (q _n-1 ) and an expansion order m are input. Generate generator polynomial candidates f _i (x), (i = 1,..., J), initialize i to 0, determine whether i = j, and if i is not j,
Step 1: Select a generator polynomial candidate f _i (x) on the input finite field GF (q _n−1 ) by adding i to +1.
Step 2: Use the irreducibility determination device 303 to check whether f _i (x) is irreducible.

Step 3: If not irreducible, return to Step 1 and start again.
Step 4: If irreducible, the regular decision device 304 is used to check whether f _i (x) is regular. (This check method is described in, for example, “Cryptography / Zero Knowledge Proof / Number Theory” by Tatsuaki Okamoto and Kazuo Ota, Kyoritsu Shuppan pp.167)
Step 5: If it is not regular, return to Step 1 and try again. If regular, f _i (x) is output as a generator polynomial f (x).
Moreover, as a structure of this apparatus, it can also be comprised as follows.
When f (x) is a quadratic polynomial x ² + v ₁ x + v ₀ , f (x) that can be expressed as v ₀ = u ² is generated at Step ₀ for the purpose of performing a square using a polynomial basis at high speed. To do.

Irreducibility determination apparatus The irreducibility determination apparatus shown in FIG. 4 is a configuration example of the irreducibility determination apparatuses 203 and 303 in the apparatus shown in FIGS. The device 400 includes a control device 401 and a polynomial Euclidean mutual separation device 402.

When the operation of this apparatus is realized by a program, it is executed according to the flow shown in FIG.
A definition field GF (q _n-1 ), a candidate f (x), and an expansion order m are input.
Make g (x) = (x ^ q _n-1 ^m-1 ) -x. Here A ^ B represents the A ^B. Next, a polynomial Euclid algorithm is used to find the greatest common divisor polynomial of the input polynomial f (x) and g (x) = (x ^ q _n-1 ^m-1 ) -x,
If the greatest common denominator polynomial is a 0th order expression, "irreducible" is output, and if it is 1st order or higher, "reducible" is output.

In the above description, each device can be made to function by causing a computer to decode and execute the program. In this case, the processing contents of the functions that each device should have are described by a program. The processing functions are realized on the computer by executing the program on the computer.
The program describing the processing contents can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. Specifically, for example, the magnetic recording device may be a hard disk device or a flexible Discs, magnetic tapes, etc. as optical disks, DVD (Digital Versatile Disc), DVD-RAM (Random Access Memory), CD-ROM (Compact Disc Read Only Memory), CD-R (Recordable) / RW (ReWritable), etc. As the magneto-optical recording medium, MO (Magneto-Optical disc) or the like can be used, and as the semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory) or the like can be used.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its storage device. When executing the process, the computer reads the program stored in its own recording medium and executes the process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).
Further, at least a part of the above processing contents may be realized by hardware.

Block diagram illustrating an example of GF (q _n) squaring unit of the present invention. 1 is a block diagram showing a polynomial basis generator for generating polynomial basis according to the present invention. FIG. The block diagram which shows the normal polynomial production | generation apparatus of this invention. The block diagram which shows the structure of the irreducibility determination apparatus used for FIG. 2, FIG. Flow diagram showing a GF (q _n) squares procedure in the embodiment shown in FIG. FIG. 3 is a flowchart showing a polynomial basis generation polynomial generation processing procedure in the embodiment shown in FIG. 2. The flowchart which shows the normal polynomial production | generation procedure in the Example shown in FIG. 5 is a flowchart showing an irreducibility determination processing procedure of the apparatus shown in FIG. 4. Shows a functional configuration of a previously proposed a GF (q _n) squarer.

Claims (4)

An apparatus for generating a generator polynomial used for performing m-order expansion from a finite field GF (q _i ) (q _i is a prime number or a power of a prime number) to GF (q _{i + 1} ),
Means for generating a plurality of generator polynomial candidates f (x) ;
Selecting means for selecting one of the generator polynomial candidates f (x);
Inspection means for inspecting whether the selected candidate f (x) is irreducible;
If it is determined that the checking means is irreducible, means for outputting the selected candidate f (x) as a generator polynomial;
A means for repeating the selection means and the inspection means when it is determined that the inspection means is not irreducible ,
The device is used for secondary expansion from GF (q _i ) to GF (q _{i + 1} ),
The means for generating the generator polynomial candidate generates a generator polynomial candidate f (x) of v ² + v ₁ x + v ₀ where v ₁ is −1 (where v ₀ and v ₁ are elements of GF (q _i )). A polynomial generating apparatus for generating a polynomial basis characterized by being a means . An apparatus for generating a generator polynomial used for performing m-order expansion from a finite field GF (q _i ) (q _i is a prime number or a power of a prime number) to GF (q _{i + 1} ),
Means for generating a plurality of generator polynomial candidates f (x);
Selecting means for selecting one of the generator polynomial candidates f (x);
Inspection means for inspecting whether the selected candidate f (x) is irreducible;
If it is determined that the checking means is irreducible, means for outputting the selected candidate f (x) as a generator polynomial;
A means for repeating the selection means and the inspection means when it is determined that the inspection means is not irreducible,
The device is used for secondary expansion from GF (q _i ) to GF (q _{i + 1} ),
The means for generating the generator polynomial candidate is a means for generating a generator polynomial candidate of x ² + v ₁ x + v ₀ where v ₁ is 0 (where v ₀ and v ₁ are elements of GF (q _i )). A polynomial generator for generating a characteristic polynomial basis. The generator polynomial generator according to claim 2 , wherein
Generating a polynomial basis characterized in that the means for generating the generator polynomial candidate is a means for generating a generator polynomial candidate in which v ₀ can be expressed as u ² (where u is an element of GF (q _i )). Polynomial generator. A computer-readable recording medium storing a program for causing a computer to function as the generator polynomial generator according to any one of claims 1 to 3 .

Images