JP4998225B2 - Finite field computation method and finite field computation device - Google Patents

Description

  The present invention relates to a calculation method of a finite field (Galois field) GF (q), and more particularly to a calculation method of a reduction calculation of a remainder calculation using an irreducible polynomial.

  Arithmetic operations of finite fields (Galois fields) are widely performed in technical fields such as error correction systems for digital audio equipment and public key cryptosystems. It is known that an efficient encryption system can be realized by applying the bilinearity of pairing of points on an elliptic curve in the operation of a finite field. There are two types of pairing: Weil pairing and Tate pairing. Since Tate pairing requires less computation, Tate pairing or its improved version is used in the cryptographic field. Nevertheless, Tate pairing is computationally intensive, and various speedup methods have been proposed to date.

Duursma-Lee algorithm and η _T pairing have been studied as representative algorithms that speed up Tate pairing. In these operations, multiplication on the characteristic 3 finite field GF (3 ^m ) is mostly occupied. Therefore, it is important to increase the efficiency of multiplication on GF (3 ^m ) for speeding up. Hereinafter, an example in a finite field GF (3 ^m ) with characteristic 3 will be described. However, the calculation method and the calculation apparatus of the present invention are not limited to the finite field GF (3 ^m ) with characteristic 3.

Non-Patent Document 1 describes the speed-up of Tate pairing operation, and requires the multiplication of a finite field GF (3 ^m ) and uses pairing in high-speed calculation of pairing in elliptic curve cryptography. It is described that a new encryption system such as ID-based encryption becomes possible.

As described in Non-Patent Document 1, the pairing calculation requires many multiplications of the characteristic 3 finite field GF (3 ^m ) with a large amount of calculation. The multiplication of GF (3 ^m ) is calculated in the following two stages.

  (1) Calculate the product of two polynomials of m-1 order or less having the elements of GF (3) as coefficients. The calculation result is a polynomial of 2m-2 order or lower with the element of GF (3) as a coefficient.

(2) The remainder g (x) = f (x) by the m-th irreducible polynomial p (x) with the coefficient of the element of GF (3) as the coefficient for the product polynomial f (x) obtained in (1) Modp (x) is calculated. This value is an m-1 or lower order polynomial with the factor of GF (3) as a coefficient, and this is the result of multiplication of GF (3 ^m ). In the above calculation of f (x) modp (x), a reduction calculation is performed on terms of the polynomial f (x) of the mth order or higher.

  It is assumed that an nth-order polynomial on GF (3) to be reduced is f (x) and an mth-order irreducible polynomial on GF (3) is p (x). Here, n ≧ m (in the case of n <m, g (x) = f (x)). The reduction operation is an operation for converting f (x) into a polynomial g (x) of m−1 order or less by a remainder operation using p (x). Hereinafter, the reduction calculation will be described.

f (x) and p (x) can be expressed as follows. (In general, the m-th order high coefficient of p (x) is 1)
f (x) = c _n x ⁿ + c _n-1 x ^n-1 + ... + c ₁ x + c ₀ (1)
p (x) = x ^m + d _m-1 x ^m-1 + ... + d ₁ x + d ₀ (2)
From the relational expression of P (x) = 0, the following expression is obtained.

x ^m = -d _m-1 x ^m-1 + ...- d ₁ xd ₀ (3)
Using this equation, the terms of the mth order or higher of f (x) are replaced. Specifically, the following equation is obtained by multiplying both sides by c _n x ^nm so that x ^{m in} equation (3) is equal to the top term of f (x).

c _n x ⁿ = -c _n d _m-1 x ^n-1 + ...- c _n d ₁ x ^{n-m + 1} -c _n d ₀ x ^nm (4)
Then, when the first term of f (x) is replaced with the expression on the right side of (4), the following expression is obtained.

f (x) = (c _n-1 -c _n d _m-1 ) x ^n-1 + (c _n-2 -c _n d _m-2 ) x ^n-2 ... + (c _{n-m + 1} -c _n d ₁ ) x ^{n-m + 1}
+ (c _nm -c _n d ₀ ) x ^nm + c _nm-1 x ^nm-1 + c ₁ x + c ₀ (5)
This equation (5) is an n−1 order polynomial, and is an n−1 order polynomial in which the order of f (x) is smaller by one.

  Next, the processing for replacing the first term is performed on the equation (5), which is an n−1th order polynomial, in the same manner as described above to obtain an n−2nd order polynomial. Thereafter, the same processing is repeated until an m-1 order polynomial is obtained. The obtained result becomes the result g (x) of the mod operation.

  In many cases, a plurality of m-th irreducible polynomials on GF (3) exist for each m. For the purpose of an application, consider an m-th irreducible polynomial that can efficiently perform a reduction operation when only m is specified and there is a degree of freedom in selecting an m-th irreducible polynomial to be used in an actual operation. Here, it is assumed that the calculation is executed by software processing using a general CPU without using dedicated hardware for a fixed m-th irreducible polynomial.

From the above reduction calculation method, it is clear that it is more efficient that the number of terms of the irreducible polynomial used in the reduction calculation is as small as possible. Of the irreducible polynomials on GF (3), the binomial expression is only x ² +1, so the ternary expression x ^m + ax ^k + b (m>k>0; a, b∈GF (3); ab ≠ 0 ) Is a candidate.

  Since the remainder calculation using the irreducible polynomial is described in Patent Document 1 and the like, further explanation is omitted.

Shirase, Takagi, Okamoto, "Efficient Algorithm for Tate Pairing" IEICE Technical Report ISEC2006-12,0019-26, IEICE Sakai, Ogishi, Kasahara, "Cryptography Based on Pairing" Cryptography Theory and Algebraic Curve Theory that Supports It, First Workshop (August 30-September 1, 2000, Chuo University Ichigaya Campus) G. Granger, D. Page & M. Stam, "Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three", IEEE Trans. On Computers, Vol.54, No.7, pp852.860, 2005 JP 2000-148013 A

As described above, in the reduction operation in the multiplication of GF (3 ^m ), the irreducible ternary expression x ^m + ax ^k + b is a candidate. In the conventional example including the hardware implementation, the one having the smallest k has been used so far.

  Here, the purpose is to reduce the processing steps and increase the speed when performing a reduction operation using a general CPU.

In order to achieve the above object, this finite field calculation method and apparatus, when performing a reduction operation with an irreducible polynomial using a general CPU, determines the degree of the irreducible polynomial, the order of the intermediate term, and the irreducible polynomial. At least one of the values obtained by subtracting the order of the intermediate term from the order uses an irreducible polynomial that is a multiple of the word width of the arithmetic processing of the CPU. Thereby, a part of the shift process in the reduction calculation can be omitted.
For example, the case where the order of the intermediate term is a multiple of the word width will be described. It is assumed that the word width is W bits, the irreducible polynomial is represented by a trinomial x ^m + ax ^k + b, and the order of the intermediate term is a multiple of the word width. That is, k = W × g (g is an integer of 1 or more). m is larger than W and is usually 90 or more for pairing calculation.

As described above, in the reduction operation in the multiplication of GF (3 ^m ), the irreducible ternary expression x ^m + ax ^k + b is a candidate, and many of them have the smallest k in the past, and at least the software using the CPU In the case where computation is performed by wear control, there has been no intention that the order of the intermediate term is a multiple of the word width of the CPU for the purpose of efficient computation.

  When performing a reduction operation using an irreducible polynomial by software control using the CPU, each bit data representing the coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation is stored as continuous bit data. Then, data of the number of bits corresponding to the word width of the arithmetic processing of the CPU is processed in parallel. At this time, the reduction target portion of the target polynomial having a degree equal to or higher than the degree of the irreducible polynomial is assigned in units of word width in order from the higher order bit, and the term corresponding to the degree of the irreducible polynomial corresponds to the smallest bit in the word width. Shifting by the shift amount to be shifted, and adding / subtracting the shifted word width unit data to / from the corresponding terms of the target polynomial whose degree is related to the first term of the irreducible polynomial, the intermediate term and the constant term . In this case, if the order of the intermediate term is a multiple of the CPU word width as in the present invention, the shift amount within the word width for addition and subtraction of the intermediate term and the constant term is the same, and the shift processing is shared. Therefore, the amount of processing can be reduced accordingly.

  The reduction of the shift processing is not limited to the above case. If the degree of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU, the coefficient stored in the addition / subtraction processing of the constant term is shifted in units of word width. Therefore, the shift processing within the word width for addition / subtraction of the constant term is not necessary. If the value obtained by subtracting the degree of the intermediate term from the degree of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU, the shift processing within the word width for addition / subtraction of the intermediate term is unnecessary, and the processing amount Can be reduced. This is the same when the irreducible polynomial has four or more terms. If each term is a multiple of the word width, the shift processing within the word width is not necessary as described above, and the intermediate terms If the order difference is a multiple of the word width of the arithmetic processing of the CPU, the shift amounts for addition and subtraction of the intermediate terms are the same, so that the shift processing within the word width can be shared.

  In the example described later, an example is described in which the characteristic is a finite field of 3 suitable for speeding up Tate pairing and the irreducible polynomial is a trinomial. However, the degree of the irreducible polynomial, the order of the intermediate term, and the existing The feature of the present invention that at least one of the values obtained by subtracting the order of the intermediate term from the order of the polynomial is a multiple of the CPU word width is also effective in a finite field other than characteristic 3 such as characteristic 2. As described above, it is also effective when the irreducible polynomial has four or more terms.

  When the characteristic is 3, the coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation can be represented by 2-bit data, but the upper and lower bits of each term are stored as continuous bit data. The data of the number of bits corresponding to the word width of the arithmetic processing of the CPU is processed in parallel.

  According to the described embodiment, it is possible to reduce the amount of processing when performing a reduction operation using an irreducible polynomial generated by a finite field remainder operation by software control using a CPU, and to increase the speed.

  The finite field arithmetic unit of the embodiment is realized by software control by a program installed in hardware using an arithmetic unit having a hardware configuration as shown in FIG. 1 and executes finite field arithmetic.

  As shown in FIG. 1A, the hardware used in the embodiment is a general computer having a CPU 21, a ROM 25, a RAM 26, an I / O 27, and an external bus 28 for connecting them. The CPU 21 includes an arithmetic unit (ALU) 22, a register group 23, and an internal bus 24 that connects them. The internal bus 24 has a word width (bit width) of 16 bits, and the CPU 21 performs various processes with a word width of 16 bits. Although a CPU with a word width of 16 bits is used here, the present invention is not limited to this, and CPUs with word widths of 8 bits, 32 bits, and 64 bits that are widely used may be used.

  FIG. 1B is a functional block diagram of the finite field arithmetic device of the embodiment. As shown in FIG. 1B, the existence / decrease calculation unit (apparatus) 31 includes a reduction calculation unit 32. The reduction calculation unit 32 stores a coefficient of each term of the target polynomial as continuous bit data, and includes a count storage unit 33 realized by the register group 23.

The first embodiment is a trinomial irreducible polynomial in which the degree of the intermediate term is a multiple of the word width of the CPU 21, that is, a multiple of 16.
FIG. 2 is a diagram showing a reduction calculation flow in the first embodiment. Here, it is assumed that a reduction operation is performed when a target polynomial f (x) (n-th order) to be calculated is subjected to a remainder operation with an irreducible ternary expression p (x) (m-th order), and f (x) The case where it is represented by Formula (1) and p (x) is represented by the following Formula (6) will be described as an example.

p (x) = x ^m + ax ^k + b (6)
In step 101, the parameters m, k, a, b and the word width (number of bits) W (16 bits here) of the irreducible ternary equation are input.

  In step 102, R and y indicating the positions of the m-th term and the first term (n-th term) within the word width when the coefficient of f (x) is stored in units of word width, and an irreducible factor. K indicating the position within the word width of the intermediate term (k-th term) of the ternary expression is calculated. R, y, and K are expressed by the following equations.

R = m mod W
y = (n + 1) mod W
K = truncate (k / W)
Here, “truncate” indicates a value obtained by rounding down the fractional part.

  In step 103, it is determined whether y is equal to or less than R. If y is equal to or less than R, the process proceeds to step 104B, and if y is greater than R, the process proceeds to step 104A.

In steps 104A and 104B, the maximum value max and the minimum value min of the variable i used for the calculation are calculated. max is different in steps 104A and 104B. In step 104A,
max = roundup {(n + 1) / W}
min = roundup {m / W} -1
In step 104B,
max = roundup {(n + 1) / W} -1
min = roundup {m / W} -1
Set to Here, roundup indicates a value rounded up after the decimal point.

  After steps 104A and 104B, the process proceeds to step 105.

  In step 105, arrays H and L with the number of elements being max are secured, and coefficient data of f (x) is stored in arrays H and L. FIG. 3 is a diagram for explaining a coefficient data storage method in the count storage unit 33 of the first embodiment.

  Since it is a finite field of characteristic 3, the coefficient is either 0, 1, or 2, and the coefficient data can be represented by 2 bits. The storage array is in units of word width (16 bits), and one array unit is composed of H (i) for storing the upper bits of 2 bits and L (i) for storing the lower bits. New sequences are reserved from H (0) to H (max) (and from L (0) to L (max)). For example, when n is 189 and m is 97, since R = 1 and y = 14, max = 11 is obtained by step 104B, and the array H is from H (0) to H (11). 12 array units are secured. In 12 array units, 12 × 16 = 192 bits can be stored, and coefficient data is not stored in the upper 2 bits of H (11).

  In step 106, the variable i is set to max, and in step 107, it is determined whether i is smaller than min. If it is smaller, the process proceeds to step 110. Otherwise, the process proceeds to step 108.

  In step 108, in order to perform addition / subtraction, data generation for matching the reduction target portion of f (x) with the positions of the intermediate term and constant term of p (x) and the calculation of the corresponding array position are performed.

  In the reduction operation, the first term of p (x) is made to correspond to a bit in the reduction target portion of f (x), and addition / subtraction processing according to the bit value is performed on the bit corresponding to the intermediate term and the constant term. . Therefore, if the last bit of the reduction target part of f (x), that is, the bit corresponding to the order of p (x) is shifted so as to correspond to the constant term, that is, corresponding to the last bit of the word width, Appropriate for performing operations in units of width (16 bits). This shift amount is represented by WR.

  Since the reduction operation needs to be performed in order from the higher order bits of the reduction target portion, the right R bits of H (12) and the left WR bit data strings of H (11) are concatenated to th, and L The right R pieces of (12) and the left WR bit data strings of H (11) are concatenated into tl to create word (16 bits) wide data. It is H (j1) corresponding to the intermediate term of p (x) and H (j2) corresponding to the constant term that is subjected to addition / subtraction processing according to this data. j1 and j2 are expressed by the following equations.

j1 = i-min + K
j2 = i-min
In step 109, the generated th and tl are added to or subtracted from the corresponding array position of f (x) according to a and b of p (x).

  FIG. 4 is a diagram showing this calculation process. Here, the coefficient a of the intermediate term of p (x) will be described, but the same applies to the coefficient b of the constant term.

  As shown in FIG. 4A, this operation is an operation on a finite field of characteristic 3, and if a is 1, the corresponding bit value (H (j1), L) of f (x) It can be replaced by subtraction of (th, tl) from (j1), and if a is 2, (th, tl) to the corresponding bit value (H (j1), L (j1) of f (x) The calculation result is overwritten on f (x), and this operation is performed in parallel for all the bits of the word width.

  FIG. 4B is a flowchart showing the processing described in FIG. 4A. It should be noted that th and tl of the addition function are interchanged.

  FIG. 4C is a flowchart showing the actual processing of the addition function, the values of the H and L registers of f (x), the values of th (h) and tl (l), and their calculation locations. A value to be overwritten can be calculated by calculating OR and XOR between the two. Since the calculation of the finite field is widely known, the description thereof is omitted.

  In step 109, when the above processing ends, all bits of H (i) and L (i) are set to zero, the variable i is decreased by 1, and the process returns to step 107.

  Thereafter, the processing of steps 108 and 109 is repeated until the processing of the term corresponding to the order of the first term of p (x) is completed while shifting the array unit to be calculated one unit at a time. , The process proceeds from step 107 to step 110, and the left WR bits of H (i) and L (i) are set to zero and the process is terminated.

  The arithmetic processing of the first embodiment has been described above. In the first embodiment, since the degree of the intermediate term of the irreducible polynomial is a multiple of the word width of the CPU, the intermediate term has the word width as in the constant term. It corresponds to LSB, the shift amount for the calculation of the intermediate term and the constant term is the same, and the shift processing can be made common, so that the calculation amount can be reduced.

  Next, the above processing will be described with reference to FIG. 5, taking a specific irreducible ternary expression as an example.

  FIG. 5 shows the case where the order n of the target polynomial f (x) is 189 and the parameters m, k, a, and b of the irreducible ternary expression p (x) are 97, 16, 1, and 2, respectively, that is, p This is an example where (x) is represented by the following equation.

p (x) = x ⁹⁷ + x ¹⁶ +2
As shown in the figure, since the order n of f (x) is 189, 13 array units from H (0) to H (12) are secured, and the order 96 is smaller than the order 97 of p (x) in the reduction operation. Therefore, 97 bits from 0 bits to 96 bits of f (x) are the range of the reduction result, and 93 bits from 97 bits to 189 bits are the reduction target part.

  The final bit of the reduction target part of f (x), that is, the bit corresponding to the order of p (x) is shifted so as to correspond to the constant term, that is, to correspond to the final bit of the word width. This shift amount is represented by WR, and in FIG. 5, the shift is performed by 15 bits so that 97 bits of f (x) become LSB having a 16-bit width.

  Since the reduction operation needs to be performed in order from the higher order bits of the reduction target portion, the th 1 bit on the right side of H (12) and the 15-bit column on the left side of H (11) are concatenated to th, and L (12) 1 bit on the right side and 15 bit column on the left side of L (11) are concatenated into tl to create data of word (16 bits) width. It is H (6) that is 6 array units away corresponding to the intermediate term of p (x) and H (5) that is 7 array units away corresponding to the constant term that is added or subtracted according to this data. As described above, since the array corresponding to the intermediate term and the array corresponding to the constant term are shifted by the word width, the shift process can be performed in common.

  The addition / subtraction process is performed as described above.

  When the addition / subtraction process is completed, all the bits of H (12) and L (12) are set to zero, the variable i is reduced by 1 to 11, and the same operation is repeated.

  When i becomes 6, the above arithmetic processing for the reduction target portion is completed. At this time, since the left WR (15) bits of H (6) are not zero, the process of setting this part to zero is performed and the process ends.

  Here, in order to explain the effect of the present invention, the order n of the target polynomial f (x) is 189, which is the same as the example of FIG. 5, and the parameters m, k, a, The case where b is 97, 12, 1, and 2 is shown in FIG. That is, in FIG. 6, p (x) is expressed by the following equation.

p (x) = x ⁹⁷ + x ¹² +2
As shown in FIG. 6, in order to perform addition / subtraction corresponding to the intermediate term of p (x), it is necessary to shift 11 bits so that 97 bits of f (x) correspond to 12 bits within the word width. . Therefore, such a shift is performed on H (12) and H (11) of f (x), th and tl are generated, and addition / subtraction is performed on H (6).

  When this process is completed, in order to perform addition / subtraction corresponding to the constant term of p (x), a process of shifting by 15 bits so that 97 bits of f (x) correspond to 0 bits within the word width is performed. (X) H (12) and H (11) are performed to generate th and tl, and addition / subtraction is performed on H (6).

  Next, a shift process of 11 bits is performed on H (11) and H (10) to generate th and tl, and addition / subtraction corresponding to the intermediate term is performed on H (5). Then, a shift process of 15 bits is performed with H (11) and H (10) to generate th and tl, and addition / subtraction corresponding to the constant term is performed with respect to H (5).

Thereafter, such processing is repeated.
In this way, when m = 12, the shift amount for performing addition / subtraction for the intermediate term and the constant term is different, so that it is necessary to separately perform the shift processing for the intermediate term operation and the shift processing for the constant term operation. is there.

  In the first embodiment, the case where the order of the intermediate term of the irreducible ternary expression is a multiple of the word width has been described by taking the case where the word width is 16 bits as an example, but the same effect is obtained by the irreducible ternary expression. It can also be obtained when the order is a multiple of the word width, or when the value obtained by subtracting the order of the intermediate term from the order of the irreducible ternary expression is a multiple of the word width. When the degree of the irreducible polynomial is a multiple of the word width, a shift process for adding or subtracting constant terms is not necessary. If the value obtained by subtracting the degree of the intermediate term from the degree of the irreducible ternary expression is a multiple of the word width of the arithmetic processing of the CPU, the shift process for adding / subtracting the intermediate term is not necessary.

Here, the reduction of the shift process will be examined more generally.
The reduction operation by the m-th irreducible ternary expression p (x) represented by the expression (6) with respect to the n-order polynomial f (x) represented by the expression (1) is the above-described process, and the program This is the process shown in FIG. In order to actually perform this processing, a number of coefficients equal to the number of bits of the word width are processed at the same time, so that the shift processing within the word width is necessary in the processing of the first and second rows in the for loop. .

In this process, the processing of each c _i, the processing corresponding to the intermediate section ax _k is added to the coefficient c _i-(mk) of the position moved by mk the a * c _i from i, for the constant term b In the process, b * c _i is added to the coefficient c _im at a position moved from i to m.

Accordingly, since the difference between the positions of the two coefficients c _{i− (mk)} and c _{im to be} added is k, the case where k (the order of the intermediate term) is divisible by the word width is described in the first embodiment. As described above, the shift data corresponding to the intermediate term and the constant term can be shared. In other words, only shift data corresponding to one of them needs to be created.

In contrast, in the process corresponding to the intermediate section ax ^k, since the difference between the position of c _i and c _i-(mk) is mk, mk, that is, from the order of the irreducible trinomial If the value obtained by subtracting the order of the intermediate term is divisible by the word width, it is not necessary to create shift data because the array data in which the coefficient is stored can be used as it is in the processing corresponding to the intermediate term. Only shift data corresponding to the term needs to be created.

Further, in processing corresponding to the constant term b, since adding the coefficients of the position moved the b * c _i from i by m, if the degree m of irreducible trinomial is divisible by the number of bits of the word width, In the processing corresponding to the constant term, the data of the array in which the coefficients are stored can be used as it is, so that it is not necessary to create shift data, and only the shift data corresponding to the intermediate term needs to be created.

  In any of the above cases, the amount of shift data to be created and the total amount of reduction processing are the same as compared with the case where the order of the intermediate term in the first embodiment is divisible by the word width. A reduction effect will be obtained.

As a second embodiment, an example in which the value obtained by subtracting the order of the intermediate term from the order of the irreducible ternary expression is a multiple of the word width will be described with reference to FIG.
In the second embodiment, when the order n of the target polynomial f (x) is 189 and the parameters m, k, a, and b of the irreducible ternary expression p (x) are 97, 81, 2, and 1, respectively, That is, this is an example where p (x) is expressed by the following equation.

p (x) = x ⁹⁷ + 2x ⁸¹ +1
As shown in the figure, since the order n of f (x) is 189, 13 array units from H (0) to H (12) are secured as in the first embodiment, and p (x) is obtained in the reduction operation. Since the order 96 is smaller than the order 97, 97 bits from 0 to 96 bits of f (x) are the range of the reduction result, and 93 bits from 97 bits to 189 bits are the reduction target part. It is.

Since the difference between the order 97 of p (x) and the order 81 of the intermediate term is 16, the data of the array in which the coefficients are stored can be used as it is, and shifted by 1 word (16 bits) and multiplied by -2 After that, it may be added to the array data.
As for the constant term, as in the first embodiment, the last bit of the reduction target part of f (x), that is, the bit corresponding to the order of p (x) corresponds to the constant term, that is, the word width After shifting so as to correspond to the last bit, it may be multiplied by −1 and added to the array data. Since the addition process is the same as that in the first embodiment, description thereof is omitted.

Next, processing for searching for an irreducible ternary expression will be described.
FIG. 9 is a flowchart showing a process for searching for irreducible ternary expressions. Here, it is assumed that k is a multiple of the word width in the above-described irreducible ternary expression represented by Expression (6). The value of m depends on the application field, but 500 or less is sufficient for pairing. In addition, when one ternary expression is given, the irreducibility determination can be performed sufficiently quickly using a mathematical expression processing system (for example, Risa / Asir) that targets a finite field. Therefore, searching for the irreducible ternary expression can be performed according to the flow shown in FIG.

  In step 201, the maximum value max of m is input. In step 202, m is set to 1. In step 203, it is determined whether m is larger than max.

  In step 204, k is set to 1, and in step 205, it is determined whether k is equal to m. If they are equal, the process proceeds to step 210, m is incremented by 1, and the process returns to step 203. Proceed to 206.

  In step 206, it is determined whether or not an irreducible ternary expression in which a and b are 2 at m and k at that time. It is determined whether a ternary expression in which a is 2 and b is 1 is irreducible. If it is irreducible, a list is given. If not, a ternary expression in which a is 2 and b is 2 in step 208 If it is irreducible, it is listed. If it is not irreducible, k is incremented by 1 in step 209, and the process returns to step 205.

  Thereafter, k and m are sequentially increased and the process is repeated to create an irreducible ternary expression list.

FIG. 10 lists all irreducible ternary expressions in which m is 256 or less and k is a multiple of 8. For example, if an irreducible ternary expression such as x ¹²⁸ + x ⁸⁰ +2 is used and an irreducible ternary expression in which the order of the intermediate term is a multiple of 8 (or 16) is used, shift processing within the word width is performed. Is unnecessary.

  When there is a list of irreducible polynomials as shown in FIG. 10, the following procedure can be considered to select an irreducible polynomial suitable for application.

(1) When m is determined by application and m is less than or equal to max In this case, it is confirmed whether there is a desired m irreducible polynomial in the list, and if there is not, the irreducible polynomial cannot be selected. If there is a desired m irreducible polynomial, check to see if any of them has k that is a multiple of the word width (bits) of the CPU you plan to use, select it, otherwise select word width If the CPU can be replaced with a different CPU, the irreducible ternary expression cannot be selected. If the CPU can be replaced, the same processing is performed by changing the word width of the CPU to be newly used.

(2) When m is determined by application and m is larger than max The first method re-creates a list with max = m in the flow shown in FIG. 9 and performs the processing of (1).

  In the second method, m is fixed at max in the flow of FIG. 9, and the processing of repeating steps 204 to 209 is performed, and irreducible polynomials with m = max are listed. Then, check if there is one in the list that has k that is a multiple of the word width (bit) of the CPU you plan to use, select it, and if not, check if it can be replaced with a CPU with a different word width. If the exchange is impossible, the irreducible ternary expression cannot be selected. If the CPU can be replaced, the same processing is performed by changing the word width of the CPU to be newly used.

(3) When m is not determined by application Since m can be arbitrarily selected, check whether there is a k having a multiple of the word width (bit) of the CPU to be used in the list, and if there is, If an arbitrary one (or an additional condition) is selected, it is confirmed whether it can be replaced with a CPU having a different word width. If it cannot be replaced, the irreducible ternary expression cannot be selected. If the CPU can be replaced, the same processing is performed by changing the word width of the CPU to be newly used.

(4) When using an irreducible ternary expression found without creating a list (m is determined)
In the flow of FIG. 9, m is set, k is set to the word width of the CPU, steps 205 to 209 are performed, and when a desired irreducible ternary expression is found, the process ends. When there is no irreducible ternary expression and the word width of the CPU can be changed, the same processing is performed by changing the word width.

(5) When using an irreducible ternary expression found without creating a list (m is not determined)
The process of (4) is performed by changing m.

  In the embodiment described above, an example has been described in which the characteristic is a finite field of 3 and the irreducible polynomial is a trinomial, but the characteristic of the present invention that the intermediate term is a multiple of the word width of the CPU is the characteristic. The present invention is also applicable to finite fields other than characteristic 3 such as Equation 2. In that case, since the coefficient of the reduction target polynomial can be expressed by 1 bit (0 or 1), this 1-bit string may be stored in the array.

In addition, there is a possibility that an irreducible ternary expression does not exist depending on the value of m. In such a case, the present invention can be applied by expanding to the irreducible 4-term equation, the irreducible 5-term equation, or the like.
When an n-ary irreducible polynomial of 4 or more terms is used, the number of intermediate terms is n-2, so that the order of at least one term of each intermediate term is a multiple of the word width or is irreducible. The value obtained by subtracting the order of the intermediate term from the order of the polynomial is a multiple of the word width, or is expanded to an irreducible n-term expression in which the difference in the order of the intermediate term is a multiple of the word width. It is possible.

  The present invention can be applied to all cases where polynomial reduction is used, but can be applied to the following fields, in particular.

A typical example to which the present invention can be applied is calculation of pairing on an elliptic curve. Pairing is used in various applications for elliptic curve cryptography, and an example thereof is ID-based cryptography. As an example of ID-based encryption, there is a method of creating and distributing a common key based on a communication person's ID information (e-mail address, public information such as a telephone number), and any value can be used for the ID . The use of pairing in this method is described in Non-Patent Document 2, and it is described that safety is improved as compared with ID-based encryption by a method other than pairing. As described in Non-Patent Document 1, it is necessary to calculate multiplication of GF (3 ^m ) for calculation of pairing, and multiplication of GF (3 ^m ) requires a remainder operation using an irreducible polynomial. The present invention can improve the efficiency of this remainder operation.

Finally, in order to explain the effect of the present invention, in the case of m = 97,167,193,239 in C language software implementation, k according to the present invention for the execution time of the conventional example in which the minimum k is selected. FIG. 11 shows the ratio of execution times when is selected. In FIG. 11, when m = 97, the word width is 16 bits, and the others are 32 bits. In any case, it can be seen that the present invention reduces the execution time to 60% to 70%.
The following supplementary notes are further disclosed with respect to the embodiments including the examples described above.
(Supplementary note 1) A finite field operation method for performing a finite field remainder operation by software control using a CPU,
When performing a reduction operation using an irreducible polynomial, at least one of the degree of the irreducible polynomial, the order of the intermediate term, and the value obtained by subtracting the order of the intermediate term from the order of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU A finite field arithmetic method characterized by using an irreducible polynomial. (1) (FIGS. 2 and 5)
(Supplementary Note 2) Each bit data representing a coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation is stored as continuous bit data, and the number of bits corresponding to the word width of the arithmetic processing of the CPU The finite field calculation method according to supplementary note 1, wherein the data is processed in parallel. (2) (Figure 3)
(Supplementary Note 3) The finite field is a finite field with characteristic 3, and the number of terms of the irreducible polynomial is 3 or more.
The finite field operation according to appendix 2, wherein the coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation is represented by 2-bit data, and the upper and lower bits of each term are stored as continuous bit data. Method. (3) (Figure 3)
(Supplementary Note 4) The irreducible polynomial is a trinomial, the order of the intermediate term is a multiple of the word width of the arithmetic processing of the CPU,
Each bit data representing the coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation is stored as continuous bit data, and the data of the number of bits corresponding to the word width of the CPU arithmetic processing is stored in parallel. A reduction target portion of the target polynomial that is equal to or higher than the degree of the irreducible polynomial in terms of the word width in order from the upper bit, and a term corresponding to the degree of the irreducible polynomial is set to the minimum bit in the word width. The data is shifted by the shift amount to be shifted correspondingly, and the data in the shifted word width unit is converted into the corresponding term of the target polynomial whose degree is in the relationship between the first term of the irreducible polynomial, the intermediate term, and the constant term. The finite field calculation method according to attachment 1, wherein addition / subtraction is performed. (4) (Figure 5)
(Supplementary note 5) The irreducible polynomial is a trinomial, and a value obtained by subtracting the order of the intermediate term from the order of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU. The finite field calculation method described in 1. (Fig. 8)
(Supplementary note 6) The finite field arithmetic method according to supplementary note 1, wherein the irreducible polynomial is a trinomial, and the degree of the irreducible polynomial is a multiple of a word width of arithmetic processing of the CPU.
(Supplementary note 7) The irreducible polynomial is an expression of four or more terms, and the difference between the orders of at least two intermediate terms of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU. The finite field calculation method according to 1. (Fig. 8)
(Supplementary note 8) A finite field arithmetic unit including a CPU and performing a finite field remainder operation by software control,
Reduction using at least one of the degree of the irreducible polynomial, the degree of the intermediate term, and the value obtained by subtracting the order of the intermediate term from the order of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU A finite field arithmetic device comprising reduction arithmetic means for performing arithmetic operations. (5) (FIGS. 1, 2, and 5)
(Additional remark 9) The said reduction calculating means is provided with the coefficient memory | storage means which memorize | stores each bit data showing the coefficient of each term of the object polynomial on the finite field which is the object of reduction calculation as continuous bit data, and said CPU Item 9. The finite field arithmetic device according to appendix 8, wherein data of the number of bits corresponding to the word width of the arithmetic processing is processed in parallel. (6) (Figure 3)
(Supplementary Note 10) The finite field is a finite field with characteristic 3, and the number of terms of the irreducible polynomial is 3 or more,
The reduction calculation means represents a coefficient of each term of a target polynomial on a finite field that is a target of the reduction calculation, expressed as 2-bit data, and stores coefficient data in which the upper bit and the lower bit of each term are stored as continuous bit data. The finite field arithmetic device according to appendix 8, comprising means. (Figure 3)
(Supplementary Note 11) The irreducible polynomial is a trinomial, and the degree of the intermediate term is a multiple of the word width of the arithmetic processing of the CPU,
The reduction calculation means includes:
Coefficient storage means for storing each bit data representing a coefficient of each term of a target polynomial on a finite field that is a target of reduction operation as continuous bit data,
Processing the data of the number of bits corresponding to the word width of the arithmetic processing of the CPU in parallel;
The reduction target portion of the target polynomial that is equal to or higher than the degree of the irreducible polynomial is assigned in units of the word width in order from the upper bit, and the term corresponding to the degree of the irreducible polynomial corresponds to the smallest bit in the word width. Supplementary Note 8: Shifts by the shift amount to be shifted, and adds / subtracts the shifted data in word width units to the corresponding term of the target polynomial whose degree is in the relationship between the first term of the irreducible polynomial, the intermediate term, and the constant term. The finite field arithmetic device described in 1. (Fig. 5)

  The present invention is applicable to any case where polynomial reduction is used in a finite field (Galois field) operation.

It is a figure which shows the structure of the hardware used in an Example. It is a reduction calculation flow of the first embodiment. It is a figure which shows the storage method of the coefficient data in 1st Example. It is explanatory drawing of the arithmetic processing in 1st Example. It is a figure explaining the shift process in 1st Example. It is a figure explaining the shift process in the prior art example for a comparison. It is a figure which shows the program for demonstrating the shift process in a reduction calculation. It is a figure explaining the shift process in 2nd Example. This is an irreducible ternary search flow. This is a list of irreducible ternary expressions in which m is 256 or less and k is a multiple of 8. It is a figure which shows the comparison result of the execution time of this invention and a prior art example.

Explanation of symbols

21 CPU
22 ALU
24 Internal bus 25 ROM
26 RAM
28 External bus

Claims (8)

A finite field operation method for performing a finite field remainder operation by software control using a CPU,
When performing a reduction operation using an irreducible polynomial, at least one of the degree of the irreducible polynomial, the order of the intermediate term, and the value obtained by subtracting the order of the intermediate term from the order of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU A finite field arithmetic method characterized by using an irreducible polynomial.   Each bit data representing the coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation is stored as continuous bit data, and the data of the number of bits corresponding to the word width of the CPU arithmetic processing is stored in parallel. The finite field calculation method according to claim 1, wherein the finite field calculation method is processed. The finite field is a finite field with characteristic 3, and the number of terms of the irreducible polynomial is 3 or more,
The coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation is represented by 2-bit data, and the upper bit and the lower bit of each term are stored as continuous bit data, respectively. Finite field calculation method. The irreducible polynomial is a trinomial, the degree of the intermediate term is a multiple of the word width of the arithmetic processing of the CPU, and bit data representing the coefficient of each term of the target polynomial on the finite field that is the target of the reduction operation Are stored as continuous bit data, and data of the number of bits corresponding to the word width of the arithmetic processing of the CPU is processed in parallel,
The reduction target portion of the target polynomial that is equal to or higher than the degree of the irreducible polynomial is assigned in units of the word width in order from the upper bit, and the term corresponding to the degree of the irreducible polynomial corresponds to the smallest bit in the word width. Shifting by a shift amount to be shifted, and adding / subtracting the shifted data in units of word width to a corresponding term of the target polynomial whose degree is a relation between the first term of the irreducible polynomial, an intermediate term, and a constant term. The finite field calculation method according to 1. A finite field arithmetic device that includes a CPU and performs a finite field remainder operation by software control,
Reduction using at least one of the degree of the irreducible polynomial, the degree of the intermediate term, and the value obtained by subtracting the order of the intermediate term from the order of the irreducible polynomial is a multiple of the word width of the arithmetic processing of the CPU A finite field arithmetic device comprising reduction arithmetic means for performing arithmetic operations.   The reduction operation means includes coefficient storage means for storing each bit data representing a coefficient of each term of a target polynomial on a finite field that is an object of reduction operation as continuous bit data, and 6. The finite field arithmetic unit according to claim 5, wherein data of a number of bits corresponding to a word width is processed in parallel. The finite field is a finite field with characteristic 3, and the number of terms of the irreducible polynomial is 3 or more,
The reduction calculation means represents a coefficient of each term of a target polynomial on a finite field that is a target of the reduction calculation, expressed as 2-bit data, and stores coefficient data in which the upper bit and the lower bit of each term are stored as continuous bit data. The finite field arithmetic unit according to claim 5, comprising means. The irreducible polynomial is a trinomial, and the order of the intermediate term is a multiple of the word width of the arithmetic processing of the CPU,
The reduction calculation means includes:
Coefficient storage means for storing each bit data representing a coefficient of each term of a target polynomial on a finite field that is a target of reduction operation as continuous bit data,
Processing the data of the number of bits corresponding to the word width of the arithmetic processing of the CPU in parallel;
The reduction target portion of the target polynomial that is equal to or higher than the degree of the irreducible polynomial is assigned in units of the word width in order from the upper bit, and the term corresponding to the degree of the irreducible polynomial corresponds to the smallest bit in the word width. Shifting by a shift amount to be shifted, and adding / subtracting the shifted data in units of word width to a corresponding term of the target polynomial whose degree is a relation between the first term of the irreducible polynomial, an intermediate term, and a constant term. 5. The finite field arithmetic device according to 5.

Images