JP2004205868A - Hyperelliptic curve scalar multiplication method and apparatus - Google Patents

Abstract

A scalar multiplication device for a hyperelliptic curve in a high-speed encryption system is provided.
When calculating a scalar multiplication of an element D of a Jacobi variety associated with a hyperelliptic curve, in a pre-calculation, two sets of calculations that can be independently calculated are included in a set, and each calculation is included once in each calculation. Inverse element calculation is reduced using Montgomery trick and the integer k (= 2 ^s + h (h, s is an integer)) that needs to be calculated internally is multiplied by [k] D = [2 ^s ] D + [ Instead of calculating h] D, replace doubling with addition by calculating [k] D = [2 ^s-1 ] D + ([2 ^s-1 ] D + [h] D) By performing the improvement, the number of multiplications and inverse element calculations on the definition field is reduced, and a scalar multiplication device optimal for a genus 2 hyperelliptic curve is constructed.
[Selection diagram] FIG.

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an encryption technology as an information security technology, and more particularly to a scalar multiplication device required for encryption and digital signature technology realized using a genus 2 hyperelliptic curve on a finite field.
[0002]
[Prior art]
Non-Patent Document 1 proposes an encryption and decryption apparatus based on the discrete logarithm problem of a Jacobi manifold accompanying a hyperelliptic curve as an encryption method that can be expected to have higher security.
[0003]
Finite field F_qThe hyperelliptic curve above is the equation y^Two+ h (x) y = f (x) is defined as a set of points (x, y). Where f (x) is a finite field F_qThe above monic 2g + 1 order polynomial, h (x) is a finite field F_qThe above polynomial of order g or less, and g is called the genus of the hyperelliptic curve.
[0004]
The factor on the hyperelliptic curve is the point P on the hyperelliptic curve C_iForm sum D = Dn_PP_iCan be represented by using Where n_PIs an integer and some n_PIs assumed to be 0.
[0005]
Next, -P = (x, -y) is called a conjugate of P = (x, y). Factors that do not include points that are conjugate to each other are called semi-reduced factors,
k = Σn_PIs called a factor weight. Of semi-reduced factors
Those for which k ≦ g are called reduced factors. Jacobi variety J associated with hyperelliptic curve C_C(F_q) Is a set of irreducible factors, and a group structure can be given by defining an addition operation and an identity element described later for the irreducible factors.
[0006]
A method using a pair of polynomials is known as a factor expression method. According to Non-Patent Document 2, an arbitrary factor D = Σn_PP is two finite fields F satisfying_qIt can be expressed using the above polynomials a and b.
[0007]
(1) a: monic polynomial
(2) deg (b) <deg (a)
(3) b^Two+ hb≡f mod a
When D is a reduced factor, the condition (2) is replaced by deg (b) <deg (a) ≦ g. Thereafter, factor D is changed to F_qIt is represented using the above set of polynomials (a, b). Then the Jacobi variety J_C(F_q) Is represented by (1,0).
[0008]
Addition and doubling can be defined for factors on the hyperelliptic curve.
[0009]
Hyperelliptic curve of genus 2
y^Two= x⁵⁺Ax^Four+ Bx^Three+ Cx^Two+ Dx + E
(A, B, C, D, E∈F_q(q is a power of a prime number p of 3 or more)) and the addition and doubling algorithms are described in detail in Non-Patent Document 3 below.
[0010]
Hereinafter, based on Non-Patent Document 4, an outline of an addition algorithm for the most common combination of factors will be described.
[0011]
Input: reduced factor D with weight 2₁= (a₁, b₁), D_Two= (a_Two, b_Two)
Output: reduced factor D_Three= (a_Three, b_Three) = D₁+ D_Two
Where a_i= x^Two+ s_ix + t_i, b_i= u_ix + v_i,
(s_i, t_i, u_i, v_i∈F_q), a₁, a_TwoHave no common factor,
b₁, ≠ -b_Two, b₁≠ 0, b_TwoSuppose that ≠ 0 is satisfied.
[0012]
Step 1: Calculate r.
[0013]
Step 2: I≡r / a₁ mod a_Two Is calculated.
[0014]
Step 3: H≡ (b_Two-b₁) I mod a_TwoIs calculated.
[0015]
Step 4: calculate intermediate data
α₁= 1 / rh₁, α_Two= rα, α_Three= h₁ ^Twoα₁ β = rα_Two, γ = β^TwoIs calculated respectively.
[0016]
Step 5: Monicize H
[0017]
Step 6: J = Ha₁Is calculated.
[0018]
Step 7:
a_Three= (H (J + 2βb₁)) / a_Two-γ (f-b₁ ^Two) / a₁a_TwoIs calculated.
[0019]
Step 9:
b_Three≡- (α_ThreeJ + b₁) mod a_ThreeIs calculated.
[0020]
According to Non-Patent Document 3, the operation cost of the above algorithm is a finite field F_qIf the cost of the above inverse calculation is I and the calculation cost of the multiplication is M, then 1I + 25M.
[0021]
Next, a double calculation method according to Non-Patent Document 3 will be described.
[0022]
Input: reduced factor D with weight 2₁= (a₁, b₁), But gcd (a₁, b₁) = 1.
Output: reduced factor D_Three= (a_Three, b_Three) = 2D₁
Step 1: Calculate r.
[0023]
Step 2: I≡2rb₁ mod a₁Is calculated.
[0024]
Step 3: H≡ (f-b₁ ^Two) / a₁ mod a₁Is calculated.
[0025]
Step 4: J≡IH mod a₁Calculation
Step 5: Choose an arithmetic method.
[0026]
First order coefficient j of J₁If is 0, proceed to step 11; otherwise, proceed to step 6.
[0027]
Step 6: Calculate intermediate data.
[0028]
α₁= 1/2 (rj₁), α_Two= 2rα₁, α_Three= j₁ ^Twoα₁,
β = j₁ ^Twoα₁, γ = β^TwoIs calculated respectively.
[0029]
Step 7: Monicize J
[0030]
Step 8: K = Ja₁Is calculated.
[0031]
Step 9: a_Three= ((Ja₁+ βb₁)^Two-f) / a₁ ^TwoIs calculated.
[0032]
Step 10: b_Three≡- (α_ThreeK + b₁) mod a_ThreeAnd proceeds to step 14.
[0033]
Step 11: Calculate K = J / (2r).
[0034]
Step 12: a_ThreeIs calculated.
Step 13: b_ThreeAnd proceeds to step 14.
[0035]
Step 14: D_Three= (a_Three, b_Three) Is output.
[0036]
The calculation cost of the doubling algorithm is 1I + 29M, the genus 2 hyperelliptic curve is y^Two= x^Five+ Bx^Three+ Cx^TwoWhen it is limited to + Dx + E, it becomes 1I + 27M.
[0037]
Further, the above algorithm is extended to the characteristic 2 in Non-Patent Document 4 below.
[0038]
The operation cost for the most common set of factors in this case is 1I + 25M for addition and 1I + 27M for doubling as in the case of characteristic 3 or more.
[0039]
Finite field F_qThe discrete logarithm problem of the hyperelliptic curve defined above is the Jacobi variety J_C(F_qJacobi variety J if the order of) is divisible by a large prime_C(F_qElement D included in)₀Is the base point. Then the Jacobi variety J_C(F_qThe element included in) is D₁Against
D₁= [k] D₀= D₀+ D₀+… + D_o(add k times)
The problem is that if there is an integer k such that
[0040]
Cryptographic security depends on the fact that the above problem is very difficult for Jacobi varieties with many elements.
[0041]
Next, an encryption method applying the discrete logarithm problem on the Jacobi variety accompanying the hyperelliptic curve will be described first.
[0042]
(1) Key generation
Input: hyperelliptic curve C, base point D₀, D₀Order n
Output: key pair (d_s, D_p)
Step 1: d satisfying 1 <d <n at random_sIs selected as the secret key.
[0043]
Step 2: D_p= [d_s] D₀Is calculated as a public key.
[0044]
Step 3: key pair (d_s, D_p) Is output.
[0045]
(2) Encryption
Input: hyperelliptic curve C, base point D, order n of D, public key D_p, Plaintext m
Output: ciphertext (C₁, C_Two)
Step 1: Randomly select r that satisfies 1 <r <n.
[0046]
Step 2: C₁= [r] D₀Is calculated.
[0047]
Step 3: C_Two= m + [r] D_pIs calculated.
[0048]
Step 4: Ciphertext (C₁, C_Two) Is output.
[0049]
(3) decryption
Input: hyperelliptic curve C, base point D, order n of D, secret key d_s,
Ciphertext (C₁, C_Two)
Output: decrypted text m
Step 1: m = C_Two-[d_s] C₁Is calculated.
[0050]
Step 2: Output m as a decrypted text.
[0051]
As can be seen from the above conventional example, the encryption method using a hyperelliptic curve requires a scalar multiplication operation of a fixed point and an arbitrary point.
[0052]
The k-times operation can be calculated by the following method shown in Non-Patent Document 5 by combining the addition operation and the doubling operation.
[0053]
Conventional example 1: Sliding window method
Input: reduced factor D₀, Integer
k = k₀+ k₁2 +… + k_d-1Two^d-1, k_j∈ {0,1}
(0 ≦ j ≦ d-1), positive integer r.
Output: D₁= [k] D₀
Step 1: pre-calculation
Step 1.1: D [1] = D₀, D [2] = [2] D₀far.
[0054]
Step 1.2: i is 1 to 2^r-1Calculate D [2i + 1] = D [2i-1] + D [2] up to -1.
[0055]
Step 1.3: j = d-1, D₁= (1,0) (= infinity point).
[0056]
Step 2: main loop
Step 2.2: k_jIf = 0, proceed to step 2.3; otherwise, proceed to step 2.5.
[0057]
Step 2.3: D₁= [2] D₁Is calculated.
[0058]
Step 2.4: Calculate j = j-1 and proceed to step 2.8.
Step 2.5: t is j-t + 1 ≦ r and k_tH = (k_jk_j-1… K_t)_Twofar.
[0059]
Step 2.6: D₁= [2^{j-t + 1}] D₁Calculate + D [h].
[0060]
Step 2.7: Calculate j = t-1.
[0061]
Step 2.8: If j ≠ −1, return to step 2.2. If j = −1, proceed to step 2.9.
[0062]
Step 2.9: D as operation result₁Is output.
[0063]
When an elliptic curve is used, Non-Patent Document 6 below shows a high-speed calculation method in a pre-calculation step of the above algorithm.
[0064]
This algorithm achieves high-speed processing by reducing the number of inverse calculations included in the addition and doubling operations on the elliptic curve once each using a Montgomery trick.
[0065]
First, the Montgomery trick will be described based on Non-Patent Document 7.
[0066]
Montgomery trick
Input: a₁, a_Two,…, A_n
Output: a₁, a_Two,…, A_nThe inverse of a₁ ^-1, a_Two ^-1,…, A_n ^-1
Step 1: c₁= a₁deep.
[0067]
Step 2: Repeat Step 2.1 from i to 2 to n.
[0068]
Step 2.1: c_i= c_i-1a_iIs calculated.
[0069]
Step 3: u = c_n ^-1Is calculated.
[0070]
Step 4: Set i = n and repeat the following steps until i <0.
[0071]
Step 4.1: a_i ^-1= c_i-1Calculate u.
[0072]
Step 4.2: u = ua_iIs calculated.
[0073]
Step 4.3: Calculate i = i-2.
[0074]
Step 5: a₁ ^-1= u is calculated.
[0075]
Step 6: a₁ ^-1, a_Two ^-1,…, A_n ^-1Is output.
[0076]
The cost of Montgomery tricks is
Since it is known that 1I + (3n-3) M, and 1I is generally equivalent to about 30M, a significant speed-up can be achieved as compared with the case where the inverse calculation is performed n times.
[0077]
Next, based on Non-Patent Document 6, a high-speed pre-calculation method using the fact that inverse calculation is used once each for addition and doubling on an elliptic curve using Affine coordinates will be described.
[0078]
Conventional example 2: fast pre-calculation method
Input: Point P, m = 2 on elliptic curve^r.
Output: P, [2] P, [3] P, [5] P,…, [m-3] P, [m-1] P.
Step 1: [2] Calculate P.
[0079]
Step 2: Repeat steps 2.1 and 2.2 from i = 1 to i = r-2.
[0080]
Step 2.1:
([2ⁱ+1] P, [2ⁱ+3] P,…, ([2^{i + 1}-1] P, ([2^{i + 1}] P) is calculated in one inverse calculation by using the Montgomery trick. The calculation method is based on the fact that the calculation of P + [2] P and [2] [2] P can be performed independently in the case of i = 1. The calculation of ([3] P, [4] P) is performed by combining them once. In the step of i = 2, ([5] P, [7] P, [8] P) is converted to P + [4] P, [3] P + [4] P, [2] [4] By calculating P), the inverse element is calculated in one time. Hereinafter, the same calculation is repeated for each I.
[0081]
Step 2.2: Calculate i = i + 1.
[0082]
Step 3: Using the same method as in Step 2.1 ([2^r-1+1] P,
[2^r-1+3] P,…, [2^r-1] Calculate P).
[0083]
Step 4:
P, [2] P, [3] P, [5] P, ..., [m-3] P, [m-1] P are output.
[0084]
The above-described high-speed pre-calculation method can be applied to a hyperelliptic curve because addition and doubling include one inverse calculation.
[0085]
[Non-patent document 1]
Neal Koblitz, `` Neal Koblitz, Hyperelliptic Crypto Systems '', 1989, J. Crypto, 1989, p139-150
[Non-patent document 2]
D. Mumford, `` Tate lectures on theta II '', Birkhauser, 1984, volume 43 of Progr.Math.
[Non-Patent Document 3]
Masafumi Takahashi, "Improvement of genus 2 hyperelliptic curve" 2002, Proc of SCIS2002 Vol1, p155-160
[Non-patent document 4]
Sugizaki Daiki, Matsuo Kazuto, Zhao Shinki, Tsujii Shigeo, "Extension of Harley Addition Algorithm for Hyperelliptic Curves on Characteristic 2 Finite Field", IEICE 2002 ISEC-2002-9, p49-56
[Non-Patent Document 5]
I. Blake G. Seroussi and N. Smart, `` Elliptic Curvesin Cryptography '', Canbridge U.P, 1998 London Mathematical Society Lecture Note Series, no.265
[Non-Patent Document 6]
H. Cohen, A. Miyaji and T. Ono, `` Efficient elliptic curve exponentiation using mixed coordinates '', Springer-Verlag, 1998, Proceedings Asiacrypt'98, Lecture Notes in Computer Science 1514, p51-65
[Non-Patent Document 7]
H. Cohen, `` A course in computational algebraic number theory '', Springer-Verlag, 1993, GTM 138
[0086]
[Problems to be solved by the invention]
In an encryption method using a hyperelliptic curve, an arithmetic device for performing a scalar multiplication operation is essential. In particular, a scalar multiplication operation at an arbitrary point has a large load in encryption processing, and therefore, it is necessary to perform the operation at high speed.
[0087]
Scalar multiplication is composed of a combination of addition and doubling. There is a degree of freedom in the combination of addition and doubling, for example, considering 9 times D
(1) [9] D = [8] D + D
(2) [9] D = [4] D + ([4] D + D)
(3) [9] D = [3] D + [2] ([3] D)
Calculation methods such as this are conceivable. Next, considering the total number of operations, in case of (1) [8 (= 2^Three)] D can be calculated by doubling 3 times, so 1 addition and 3 doublings 4 times in total, in case of (2), 2 additions and 2 doublings 4 times in total, (3 In the case of), the addition and doubling are performed twice, for a total of four times, and the total number of operations is the same, but the number of additions and doublings performed therein are different. Therefore, when there is a difference in the processing time between the addition and the doubling, the scalar multiplication operation can be performed by using a calculation method in which many operations having a short processing time appear.
[0088]
The scalar multiplication method of Conventional Example 1 is mainly intended to speed up the scalar multiplication of a point on an elliptic curve. Addition and doubling on projective coordinates, which are the most commonly used in constructing elliptic curve cryptography, add 16M (characteristic 3 or more) or 20M (characteristic 2), and doubling adds 10M. The doubling is faster than. For this reason, when performing the scalar multiplication operation, if an algorithm having the same total number of times of addition and doubling is used, the scalar multiplication operation can be realized at a higher speed by using an algorithm having a larger number of doubling operations.
[0089]
However, if the addition algorithm is faster, such as the addition and doubling of factors on a genus 2 hyperelliptic curve, an algorithm that uses more additions if the total number of additions and doublings is the same It is desirable to use
[0090]
In addition, the high-speed pre-calculation method shown in the conventional example 2 is also 4 times, 8 times,.^r-1There is a problem that double calculation is required. In the case of an elliptic curve using Affine coordinates, addition is 1I + 3M, doubling is 1I + 4M, and the ratio of operations other than the inverse calculation is small. Is larger, but in the case of a genus 2 hyperelliptic curve, the computational load other than the inverse is large, so that it is not possible to obtain the effect of speeding up by simply adapting it.
[0091]
[Means for Solving the Problems]
The present invention provides a method for scalar multiplication by using addition instead of doubling as much as possible in cases where addition is faster than doubling, such as in operations on genus 2 hyperelliptic curves. Reduce processing time.
[0092]
Specifically, the integer k is 2^s+ h (h and s are integers), k times D based on the conventional example
[k] D = [2^s] D + [h] D instead of calculating
[k] D = [2^s-1] D + ([2^s-1By taking advantage of the fact that the number of doubling operations can be reduced by calculating [D + [h] D), a scalar multiplication device with a small number of doubling operations is constructed. In addition, the pre-calculation method is improved, and the pre-calculation is performed at a higher speed with a smaller number of unnecessary point calculations than in the conventional example. These improvements provide a high-speed encryption device.
[0093]
More specifically, the present invention relates to a hyperelliptic curve scalar multiplication device, an input section for inputting a hyperelliptic curve to be operated on and data to be operated, and a hyperelliptic curve holding information of the hyperelliptic curve. An information holding unit, a calculation target data holding unit for holding calculation target data, a scalar multiplication unit performing a scalar multiplication operation method, an addition calculation unit and a doubling calculation unit used internally in the scalar multiplication unit , An operation result holding unit for holding the operation result, and an output unit for outputting the operation result.
[0094]
Furthermore, the present invention is characterized in that a scalar multiplication on a Jacobi manifold associated with a genus 2 hyperelliptic curve defined on a finite field is calculated at high speed.
[0095]
In addition, the present invention provides D, 3 [D], [5] D, [7] D, [9] D, [11] D, [11] D for the element D of the Jacobi variety accompanying the hyperelliptic curve. 13] D and [15] D are calculated in advance.
[0096]
Further, the present invention is characterized in that the number of inverse element calculations on a definition field is reduced by applying Montgomery trick to two operations that can be calculated independently in the pre-calculation.
[0097]
Further, the present invention is characterized in that the method of using the pre-computed result is optimized according to the input.
[0098]
In addition, the present invention provides a method for calculating a scalar multiple of the element D of a Jacobi variety associated with a hyperelliptic curve, the integers that need to be calculated internally.
k (= 2^s+ h (h and s are integers) times
[k] D = [2^s-1] D + ([2^s-1] D + [h] D).
[0099]
BEST MODE FOR CARRYING OUT THE INVENTION
FIG. 1 is a functional configuration diagram of a super-elliptic curve scalar multiplication device (hereinafter, calculation device) 101 that realizes the present embodiment. The arithmetic device 101 includes a control arithmetic unit 102 and a data holding unit 103.
[0100]
The control calculation unit 102 calculates the parameters of the genus 2 hyperelliptic curve, the definition field information, and the point D on the Jacobi manifold.₀And integer k, and [k] D₀Input / output unit 104, a control unit 105 for controlling the entire hyperelliptic curve scalar multiplication device 101, a scalar multiplication unit 106 for performing scalar multiplication, and an integer k constituting the scalar multiplication unit 106 in hexadecimal expansion. The hexadecimal expansion unit 107 includes a hyperelliptic curve operation unit 108 that performs an original operation of the Jacobi variety. Further, the hyperelliptic curve operation unit includes an adding unit 109 and a doubling unit 110.
[0101]
The data holding unit 103 stores the element D of the Jacobi variety which is the operation target data input by the input / output unit 104.₀And an operation target data holding unit 111 for holding an integer k, a hyperelliptic curve parameter and a hyperelliptic curve information holding unit 112 for holding definition field information, and a precalculation result holding for a precalculation result when performing a scalar multiplication operation The unit 113 includes an intermediate data holding unit 114 that holds intermediate data used in the scalar multiplication unit 106, and an operation result holding unit 115 that holds the operation result calculated by the control operation unit 102. Next, the flow of operations will be described assuming that each operation is controlled by the control unit 105.
[0102]
The calculation target data, the hyperelliptic curve parameters, and the definition information input by the input / output unit 104 are stored in the calculation target data storage unit 111 and the hyperelliptic curve information storage unit 112.
[0103]
Next, the scalar multiplication unit 106 performs a pre-calculation using the information held in the calculation target data holding unit 111 and the hyperelliptic curve information holding unit 112. The pre-calculation result is held in the pre-calculation result holding unit 113. You. Next, the scalar multiplication unit 106 performs scalar multiplication using the precalculation result held in the precalculation result holding unit 113. The intermediate calculation result in the pre-calculation and the scalar multiplication operation is held in the intermediate data holding unit 114 as necessary. The scalar multiplication operation is performed according to the flowchart shown in FIG.
[0104]
Finally, the hyperelliptic curve scalar multiplication unit 101 is operated by the input / output unit 104 to generate a genus 2 hyperelliptic curve parameter y.^Two+ h (x) y = f (x), definition field information, operation result [k] D₀Is output.
[0105]
The above-mentioned arithmetic unit has a general interface including a CPU, a memory, a hard disk device and other external storage devices, an input device such as a keyboard, an output device such as a display, and an external storage device and an input / output device. It can be constructed on an information processing apparatus having a general configuration.
[0106]
Each of the processing units 104 to 110 of the arithmetic unit 102 is realized as a process embodied on the information processing device when the CPU executes a program (also referred to as a code or a module) loaded into the memory. Further, a memory or an external storage device is used as each of the holding units 111 to 115 of the data holding unit 103.
[0107]
Each of the programs described above is stored in an external storage device in advance, loaded on a memory as needed, and executed by the CPU. The above-mentioned program may be loaded into a memory from a portable storage medium, if necessary, from a portable storage medium, for example, an external storage device that handles a CD-ROM. After being installed from the portable storage medium to the external storage device from the external storage device via the external storage device, the program may be loaded into the memory from the external storage device as necessary, or further, a network connection device (not shown). May be temporarily downloaded to an external storage device and then loaded into a memory by a transmission signal which is a type of a medium readable by an information processing device on a network, or may be directly loaded into a memory via a network. May be loaded.
[0108]
Next, an embodiment and operation of the present embodiment will be described in detail with reference to FIGS.
[0109]
FIG. 2 is a flowchart illustrating the processing performed in FIG.
[0110]
<Step 201>
In FIG. 2, a definition field input unit 201 is a finite field F which is a definition field as information of a hyperelliptic curve._qAnd genus 2 hyperelliptic curves
y^Two+ h (x) y = f (x) is accepted as input.
[0111]
Where the finite field F_qThe information
(1) In the case of prime field Prime number q of 3 or more as the order of finite field
(2) q = p for extended fieldⁿA prime p (called characteristic) and an extended degree n satisfying.
[0112]
<Step 202>
The element D of the Jacobi variety that is the data to be operated on₀= (a₀, b₀), Input the integer k.
[0113]
Where the element D of the Jacobi variety₀Gives the genus 2 hyperelliptic curve
y^Two+ h (x) y = f (x) (deg (f) = 5, deg (h) ≦ 2)
deg (b_i) <deg (a_i) ≦ 2 (a_i, b_i∈F_q[x]) and
b_i ^Two+ hb_i≡f mod a_iA set of polynomials (a_i, b_i).
[0114]
<Step 202>
kD₀Is calculated.
[0115]
<Step 203>
Calculation result D_Three= (a_Three, b_Three) Is output.
[0116]
Step 202 will be described in detail with reference to the flowchart for explaining the operation of the scalar multiplication unit 107 shown in FIG. The addition and doubling of the Jacobi variety are calculated according to References 1 and 2.
[0117]
(1) Pre-calculation
<Step 301>
Integer k
k₀+ k₁2 +… + k_d-1Two^d-1, k_j∈ {0,1} (0 ≦ j ≦ d-1).
[0118]
<Step 302>
D [1] = D₀, D [2] = [2] D₀far.
[0119]
<Step 303>
(D [3], D [4]) = ([3] D, [4] D)
[3] D = D + [2] D, [4] D = [2] D [2] However, for each inverse calculation that needs to be performed once for each calculation, the Montgomery trick is used to reduce the two required inverse calculations to one.
[0120]
<Step 304>
(D [5], D [7]) = (D [3] + D [2], D [3] + D [4]),
(D [9], D [11]) = (D [7] + D [2], D [7] + D [4]),
(D [13], D [15]) = (D [11] + D [2], D [15] + D [4])
Is calculated respectively. By applying the method using the Montgomery trick described in step 303 to each set, calculation is performed by one inverse calculation per set.
[0121]
<Step 305>
D₁= (1,0) (= infinity point) and j = d-1.
[0122]
(2) Main loop
<Step 306>
k_jIf = 0, proceed to step 307; otherwise, proceed to step 309.
[0123]
<Step 307>
D₁= [2] D₁Is calculated.
[0124]
<Step 308>
j = j-1 is calculated, and the routine proceeds to step 313.
[0125]
<Step 309>
t is j-t + 1 ≦ 4 and k_t= 1 as the smallest integer that satisfies
h = (k_jk_j-1… K_t)_Twofar.
[0126]
<Step 310>
D₁= [2^jt] D₁Is calculated.
[0127]
<Step 311>
D_Two= D₁Calculate + D [h].
[0128]
<Step 312>
D₁= D₁+ D_TwoIs calculated.
[0129]
<Step 313>
Calculate j = t-1.
[0130]
<Step 314>
If j ≠ −1, the flow returns to step 306, and if j = −1, the flow proceeds to step 315.
[0131]
<Step 315>
D as the operation result₁Is output.
[0132]
Next, a key generation device using this embodiment will be described.
[0133]
FIG. 4 shows a key generation device.
[0134]
The key generation device 401 includes a control operation unit 402 and a data holding unit 403.
[0135]
The control calculation unit 402 uses a hyperelliptic curve
y^Two+ h (x) y = f (x), base point D₀The input / output unit 404 that inputs the order n and its definition body information and outputs the generated key information, the control unit 405 that controls the entire key generation device 401, the random number generation unit 406 that generates a random number, and the base point It comprises a hyperelliptic curve scalar multiplication unit 407 for calculating an integer multiple.
[0136]
The data storage unit 403 includes a hyperelliptic curve information storage unit 408 that stores the parameters of the hyperelliptic curve, the base point and its order, and the definition field information input by the input / output unit, the key information generated by the control operation unit, and the A key information holding unit 409 holds elliptic curve information. Next, the flow of operations will be described assuming that each operation is controlled by the control unit 405.
[0137]
Hyperelliptic curve parameters input by the input / output unit 404, base point D₀The order n and the definition field information are stored in the hyperelliptic curve information storage unit 408 and the key information storage unit 409.
[0138]
Next, in the random number generation unit 406
0 <d_s<n (n is the base point D₀Random number d that satisfies_sIs generated and held in the key information holding unit 409 as a secret key.
[0139]
Next, the base point D is calculated in the hyperelliptic curve scalar multiplication unit 407.₀D_sDouble
D_p= [d_s] D₀Is calculated using a hyperelliptic curve calculation unit, and held as a public key in a key information holding unit 409.
[0140]
Finally, the key issuing device 401 uses the input / output device 404 to
y^Two+ h (x) y = f (x), base point D₀, D₀Order n, definition field information, secret key d_sAnd public key D_pIs output.
[0141]
Next, an encryption device using the present embodiment will be described.
[0142]
FIG. 5 shows an encryption device.
[0143]
The encryption device 501 includes a control operation unit 502 and a data holding unit 503.
[0144]
The control operation unit 502 receives the hyperelliptic curve information and outputs the generated cipher text, an input / output unit 504, a control unit 505 that controls the entire encryption device 501, an encryption processing unit 506 that performs an encryption process, and The cryptographic processing unit includes a random number generation unit 507 for generating random numbers and a hyperelliptic curve scalar multiplication unit 508 for calculating an integer multiple of the original Jacobian variety.
[0145]
The data holding unit 503 is a plaintext information holding unit 509 for holding the plaintext information to be encrypted input by the input / output unit 504, and similarly, a genus 2 hyperelliptic curve input by the input / output unit
y^Two+ h (x) y = f (x), base point D₀And an order n thereof, a hyperelliptic curve information holding unit 510 for holding definition field information, a key information holding unit 511 for holding a public key used for encryption, and a ciphertext holding for a ciphertext generated by the control operation unit. It comprises a unit 512. Next, the flow of operations will be described assuming that each operation is controlled by the control unit 505.
[0146]
The plaintext information input by the input / output unit 504 is stored in the plaintext information storage unit 509.
[0147]
The hyperelliptic curve, the base point, its order, and the definition information input by the input / output unit 504 are stored in the hyperelliptic curve information storage unit 510.
[0148]
The public key information input by the input / output unit 504 is held in the public key information holding unit 512.
[0149]
Next, the encryption processing unit 506 performs an encryption process using the information stored in the plaintext information storage unit 509, the hyperelliptic curve information storage unit 510, and the public key information storage unit 511 to create a ciphertext. The encryption process is performed according to the flowchart shown in FIG.
[0150]
Finally, the ciphertext created by the encryption processing unit 506 is held in the ciphertext information holding unit 512 and output from the input / output unit 504.
[0151]
FIG. 6 shows a flowchart of the encryption processing performed by the encryption processing unit 506 in FIG. The public key is D_p, The base point of the Jacobi variety
D₀, The order is described as n.
[0152]
<Step 601>
Select a random number r that satisfies 0 <r <n.
[0153]
<Step 602>
Let m be the plaintext to be encrypted
C₁= [r] D₀And C_Two= [r] D_pCalculate + m.
[0154]
<Step 603>
(C₁, C_Two) Is output as ciphertext.
[0155]
Next, a decoding device using this embodiment will be described.
[0156]
FIG. 7 shows a decoding device.
[0157]
The decoding device 701 includes a control operation unit 702 and a data holding unit 703.
[0158]
The control operation unit 702 inputs the hyperelliptic curve information and the ciphertext to be decrypted, outputs and outputs a decrypted plaintext, a control unit 705 that controls the entire decryption device 701, and performs a decryption process. The decoding processing unit 706 and the decoding processing unit include a hyperelliptic curve scalar multiplication unit 707 that calculates an integer multiple of the original Jacobian variety.
[0159]
The data holding unit 703 is a ciphertext information holding unit 708 for holding the ciphertext information to be decrypted input by the input / output unit 704, and similarly the hyperelliptic curve input by the input / output unit 704.
y^Two+ h (x) y = f (x), base point D₀And an order n thereof, a hyperelliptic curve information holding unit 709 holding definition field information, a secret key information holding unit 710 holding a secret key used for decryption, and a plaintext holding a plaintext decrypted by the decryption processing unit 706. It comprises an information holding unit 711. Next, the flow of operations will be described assuming that each operation is controlled by the control unit 705.
[0160]
The ciphertext information input by the input / output unit 704 is held in the ciphertext information holding unit 708.
[0161]
The hyperelliptic curve parameters, base points and their orders, and definition information input by the input / output unit 704 are stored in the hyperelliptic curve information storage unit 709.
[0162]
The secret key information input by the input / output unit 704 is held in the secret key information holding unit 710.
[0163]
Next, in the decryption processing unit, decryption processing is performed using the information stored in the ciphertext information storage unit 708, the hyperelliptic curve information storage unit 709, and the secret key information storage unit 710 to create a decrypted text. The decoding process is performed according to the flowchart shown in FIG.
[0164]
Finally, the plaintext decrypted by the decryption processing unit 706 is stored in the plaintext information storage unit 711 and output from the input / output unit 704.
[0165]
FIG. 8 shows a flowchart of the decoding process performed by the decoding processing unit 706 in FIG. The secret key is d_s, The ciphertext to be decrypted is₁, C_Two).
[0166]
<Step 801>
Ciphertext (C₁, C_Two) And x,
m = C_Two-[d_s] C₁Is calculated.
[0167]
<Step 802>
Output m as plain text.
[0168]
As described above, in the present embodiment, when calculating the scalar multiplication of the element D of the Jacobi variety associated with the hyperelliptic curve,
(1) In the pre-calculation, two sets of calculations that can be calculated independently are combined into one set, and the inverse calculation included in each calculation is reduced using Montgomery trick.
[0169]
(2) The integer k (= 2^s+ h (h and s are integers) times
[k] D = [2^sInstead of calculating] D + [h] D
[k] D = [2^s-1] D + ([2^s-1] D + [h] D) replaces doubling with addition.
[0170]
The number of multiplications and inverse element calculations on the definition field was reduced by making two improvements.
[0171]
Next, the specific effects of the above-described device will be described. Assuming that the multiplication cost on the definition field is M and the inverse calculation cost is I, the calculation cost of the pre-calculation applying (1) is 5I + 239M. In general, since 1I is about 30M, the calculation cost is about 389M. Similarly, the operation cost of the pre-computation part of the conventional example is 442M, and the operation cost of the operation method of the high-speed pre-calculation method of the conventional example 2 is 492M, which indicates that the operation is faster than the conventional example.
[0172]
Regarding the effect of (2), when k times the element D of the Jacobi variety associated with the hyperelliptic curve of genus 2, if k is K bits, the maximum K / 4-1 It is possible to replace the doubling of the times with the addition. For example, in the case of a hyperelliptic curve of genus 2, the multiplication on the definition field can be reduced up to K / 2-2 times.
[0173]
【The invention's effect】
According to the present invention, it is possible to provide a hyperelliptic curve encryption device that enables a high-speed encryption method.
[Brief description of the drawings]
FIG. 1 is a system functional configuration diagram of the present embodiment.
FIG. 2 is a flowchart illustrating the operation of the present embodiment.
FIG. 3 is a flowchart illustrating a scalar multiplication operation on a Jacobi manifold according to the embodiment;
FIG. 4 is a configuration diagram of a key generation device using the present embodiment.
FIG. 5 is a configuration diagram of an encryption device using the present embodiment.
FIG. 6 is a flowchart illustrating the operation of an encryption device using the present embodiment.
FIG. 7 is a configuration diagram of a decoding device using the present embodiment.
FIG. 8 is a flowchart illustrating the operation of a decoding device using the present embodiment.
[Explanation of symbols]
101: super elliptic curve scalar multiplication device, 102: control operation unit, 103: data holding unit, 104: input / output unit, 105: control unit, 106: scalar multiplication unit, 107: hexadecimal expansion unit, 108: super Elliptic curve calculation unit, 109: addition calculation unit, 110: doubling calculation unit, 111: calculation target data storage unit, 112: hyperelliptic curve information storage unit, 113: pre-calculation data storage unit, 114: intermediate data storage unit , 115: calculation result holding unit, 401: key generation device, 402: control calculation unit, 403: data holding unit, 404: input / output unit, 405: control unit, 406: random number generation unit, 407: hyperelliptic curve scalar multiple Operation unit, 408: Hyperelliptic curve information storage unit, 409: Key information storage unit, 501: Encryption device, 502: Control operation unit, 503: Data storage unit, 504: Input / output unit, 505: Control unit, 506: Cryptographic processing unit, 507: random number processing unit, 508: superelliptic curve scalar multiplication unit, 509: plaintext information holding unit, 510: superelliptic curve information holding unit, 512: public key information holding unit, 513: ciphertext information holding Part, 701: decryption equipment 702: control operation unit, 703: data storage unit, 704: input / output unit, 705: control unit, 706: decryption processing unit, 707: hyperelliptic curve scalar multiplication unit, 708: ciphertext information storage unit, 709 : Super elliptic curve information storage unit, 710: public key information storage unit, 711: plaintext information storage unit.

Claims (6)

A hyperelliptic curve scalar multiplication device,
An input unit that receives input of a hyperelliptic curve to be operated on and data to be operated on,
A hyperelliptic curve information storage unit for storing information on the hyperelliptic curve,
A calculation target data holding unit for holding calculation target data;
A scalar multiplication unit that includes an addition operation unit and a doubling operation unit and performs a scalar multiplication operation method;
An operation result holding unit that holds an operation result;
A super-elliptic curve scalar multiplication device having an output section for outputting a calculation result. A hyperelliptic curve scalar multiplication device according to claim 1,
A super-elliptic curve scalar multiplication device for quickly calculating a scalar multiplication on a Jacobi manifold associated with a genus 2 super-elliptic curve defined on a finite field. A hyperelliptic curve scalar multiplication device according to claim 1,
For the element D of the Jacobi variety associated with the hyperelliptic curve,
Hyperelliptic curve scalar multiplication characterized by precalculating D, 3 [D], [5] D, [7] D, [9] D, [11] D, [13] D, [15] D Arithmetic unit. A hyperelliptic curve scalar multiplication device according to claim 1,
A super-elliptic curve scalar multiplication device that reduces the number of inverse element calculations on a definition field by applying a Montgomery trick to two operations that can be independently calculated in a pre-calculation. A hyperelliptic curve scalar multiplication device according to claim 1,
A super-elliptic curve scalar multiplication device, which optimizes the use of a pre-computed result according to an input. A hyperelliptic curve scalar multiplication device according to claim 1,
Integers that need to be computed internally when computing the scalar multiple of the element D of the Jacobi variety associated with the hyperelliptic curve
k (= 2 ^s + h (h and s are integers)) times
A super-elliptic curve scalar multiplication device, which is obtained by calculating [k] D = [2 ^s-1 ] D + ([2 ^s-1 ] D + [h] D).

Images