KR100194769B1 - Using memory to find inverses on finite fields - Google Patents

Abstract

1. Technical field to which the invention described in the claims belongs

Using memory to find inverses on finite fields

2. Technical Challenges to be Solved by the Invention

In the exponent reduction process, it is determined whether m-1 is an even number, an odd number that is a multiple of 3, or an odd number that is not a multiple of 3, and provides a method of computing the inverse on a finite field that processes using an odd number that is a multiple of 3 box.

3. The point of the solution of the invention

A first step of determining an exponent part of a finite field and setting an exponent m; If it is determined that m-1 is an even number, a multiple of 3 and an odd number, or an odd number that is not a multiple of 3, then if m-1 is an odd number other than a multiple of 3, Storing the result in the intermediate storage means (T _j ), calculating a exponent part by shifting after factor decomposition if the number is an odd number or an odd number that is a multiple of 3, and storing the result; And a third step of computing the inverse using the stored value.

4. Important Uses of the Invention

Used for communication network authentication system or smart card.

Description

Using memory to find inverses on finite fields

The present invention relates to a method for quickly obtaining a signature value of a message in a communication network access authentication system or a smart card for information protection in a short time.

Mass production and distribution of information using information and communication equipment in modern society has become an indispensable process in information society. During this process, there are things we often overlook. It is a matter of information security in the process. If the production and distribution processes of information are unsafe, no one will use the system.

One method used to solve the problems raised directly above is the use of smart cards. Thus, a legitimate user who owns this smart card can quickly process the job anytime, anywhere.

The role of the smart card is to obtain the signature value of the message in a short time by using 8 bit process and a small amount of memory when performing a payment service by a cryptographic mechanism such as a digital signature. However, in the digital signature mechanism, it is often necessary to quickly calculate the inverse when generating the signature value. Generally, the computer we are using is a 32-bit processor, whereas the smart card is an 8-bit process and its processing speed is relatively slow. Effective inversion calculation methods on the finite field to solve these vulnerabilities have recognized the need for development in various fields such as mathematics, computation, and electronics.

In general, the concept of fast multiplication is generalized to operations on a finite field GF (2 ^m ), and the theories are expanded. The application of the Normal Basis and the presentation of the Massey-Omura Fast Multiplication Method are typical examples of the development of smart card technology. Moreover, inversion calculations on finite fields related to this invention are recognized as important in some digital signatures or user authentication processes.

The type of inverse calculation on a finite field first determines the normal basis of the finite field, transforms the inverse calculation to a fixed number of exponentiation computations to take advantage of the efficiency of the square operation using the base, How to do it. It can also be divided by the use of memory such as registers in the calculation process. Of the methods that have been published so far, Itoh's method is known as the fastest method of using memory.

Normal basis is a base on the GF (2 ^m), before the assumption we have found that the base, and has the property that it is very convenient to the square operation of the elements shown in the base with respect to the .α∈ GF (2 ^m) Becomes the basis of GF (2 ^m ) with respect to the finite field GF (2), we Is the normal basis of GF (2 ^m ). An element χ of GF (2 ^m ) , It is assumed that < RTI ID = Become The coefficient of χ Is shifted to the right one time. finally The coefficient of . What we can think of here is that if we multiply an element of GF (2 ^m ) by a polynomial basis, we must perform m ² multiplications in GF (2), but if we use a normal basis, we can do it with a single shifting That is the gain in performance speed. Note all the finite field is normal is known as having a base, it is for certain α m for generating a normal basis for GF (2 ^m) is known for the fact that the constructor of GF (2 ^{m) *} a.

On the other hand, in the encryption method such as digital signature using the finite sieve, inversion calculation is highly required. In particular, in the signature scheme based on E1 Gamal and the US Digital Signature Standard (DSS), the signer's signature generation time includes the inversion calculation time do. The use of regular bases in these calculations not only allows users to save time, but also has important value in the theoretical aspect.

First, if α is a nonzero element of GF (2 ^m ), α ^-1 is expressed by the following equation (1).

Using the above method, m-2 times multiplication is required. The Itoh's method, which will be described next, obtains more advantages than the above method in the number of multiplications.

The inverse calculation method proposed by Itoh is the most efficient technique known to reduce the number of multiplications.

Consider GF (2 ^m ) factorization as in the following equation (2).

In the case of m being an odd number in the above equation (2) Lt; / RTI > has already been calculated, It is necessary to perform one multiplication. Assuming that m is an odd number, It is necessary to perform two multiplications. In order to calculate α ^-1 in GF (2 ^m ), it is suggested that the number of multiplications required by using this process in a deductive manner is as shown in the following equation (3).

nb (m-1) +? (m-1) -2

Where nb (χ) is the minimum number of bits needed to represent the integer χ, and ω (m-1) is the Hamming weight in the binary representation of m-1.

GF (2 ⁵⁹³ ) is taken as an example, and it is expressed by the following Equation (4).

In order to implement the above method, the equations in [Equation 4] should be divided into the following processes.

First Course: And stores it.

Since a certain number of squares corresponds to a single shifting, γ requires 4 multiplications and 556 shiftings.

Step 2: And stores it.

β requires two multiplications and 28 shiftings.

Step 3: .

delta requires 3 multiplications and 8 shiftings.

Step 4: Finally calculate δβγ.

In this process, two more multiplications are required.

(592) = 10 and ω (592) = 3) and two storage locations (593 bits) to store two intermediate values to obtain α ^-1 . If the optimal normal basis is used, it is possible to perform one multiplication process with m shifting operations. Thus, 7115 shifting operations are required to obtain the inverse of the normal basis using GF (2 ^m ).

As described above, the conventional Itoh inversion calculation method has a problem that a processing method is not efficient and a large amount of memory is required.

In order to solve the above problems, the present invention has been made to solve the above problems, and it is an object of the present invention to provide a method and apparatus for reducing the exponent part in a multi- (Itoh) is an inverse calculation method, and if it is an odd number that is a multiple of 3, it is aimed to provide a method for obtaining inverses on a finite field which is processed by shifting.

FIG. 1 is a processing flowchart according to the present invention. FIG.

According to an aspect of the present invention, there is provided a method for obtaining inversions on a finite field using a memory, the method comprising: a first step of performing a preprocessing process of setting and initializing an exponent m, ; If m-1 is an odd number other than a multiple of 3 after performing an exponent part reduction discrimination process for determining whether m-1 is an even number, a multiple of 3 and an odd number, or an odd number other than a multiple of 3, factor decomposition is performed Storing the result in the intermediate storage means (T _j ) after the exponent sub-operation, storing the result in the intermediate storage means (T _j ), calculating the exponent portion by shifting after performing factor decomposition when it is an odd number or an odd multiple of 3; Determining whether m-1 is greater than a predetermined value, repeating the steps from the second step if the value is greater than a predetermined value, and terminating exponent factor decomposition when the value is less than a predetermined value, .

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

Now, the method according to the present invention, which has improved the in-house calculation method of Itoh, will be described in detail as follows.

The core principle of the inversion calculation method according to the present invention is to use the inversion method of Itoh when m-1 is an even number or an odd number that is not a multiple of 3 as in the following Equation (5) When m-1 is an odd multiple of 3, it is processed by shifting.

Here, it should be noted that when m-1 is an odd number that is a multiple of 3 and m-1 is an odd number but not a multiple of 3, the number of times of multiplication is equal to twice, ) / 3 < (m-2) / 2 is always established, the number of shifting repetitions and the number of necessary multiplications of the present invention are smaller than or equal to the inverse calculation method proposed by Itoh. In addition, the number of memories to temporarily store values in the middle is also reduced, which can be beneficial in many ways.

For reference, using Itoh's inversion method, the average number of iterations of the exponent is [log ₂ (m-1)] for the total number of bits of m-1. The probability Pr (0 | i) at which each bit of the i-th bit is 0 is 1/2, the required number of multiplications is twice, and the probability Pr (1 | i) The number of times of multiplication is one and the number of times of the average number of multiplications is (Pr (0 | i) × 2 + Pr (1 | i) × 1) × log ₂ (m-1) × [log ₂ (m-1)].

On the other hand, when the above method is applied to the present invention, the average number of iterative factor decompositions of the exponent part for m-1 can be calculated based on the above exponential deconvolution formula (Pr (6k, 6k + 1, 6k + 2, 6k +4, 6k + 5)) it can be seen that _{[log 2 (m-1)} ] + (Pr (6k + 3)) [log 3 (m-1)] a. Here, Pr (6k, 6k + 1, 6k + 2, 6k + 4, 6k + 5) is 5/6 and Pr (6k + 3) is 1/6. In addition, the probability Pr (6k, 6k + 2, 6k + 4 | i) that the number becomes a multiple of 2 in each i-th stage is 3/6, the necessary number of multiplications is 1, The odd odd probability Pr (6k + 3, 6k + 5 | i) is 1/6, the necessary multiplication number is 2, and the odd odd probability Pr / 6, and the required multiplication number is 2, and the average number of multiplications is < RTI ID = 0.0 >

. Therefore, it can be seen that the number of times of the mean multiplication of the present invention is less than that of the Itoh inverse calculation method, so that it can be processed more efficiently in an environment having a small calculation capacity.

FIG. 1 is a processing flowchart according to the present invention. FIG.

An example of Gf (2 ¹¹² ) will be described using the method of the present invention.

The present invention comprises a preprocessing process for obtaining inverses, an exponent reduction and factorization process, and an exponent operation process.

First, in the preprocessing process, the exponent part of the finite element requiring the inverse is determined and the exponent m is determined. In the above example, m is 112.

Next, the exponent reduction and factorization process is performed. In the exponent division reduction process, it is determined whether m-1 is an even number, a multiple of 3, an odd number, or an odd number that is not a multiple of 3. Here, m-1 is 111, which is an odd number that is a multiple of 3. Then, the exponent part is factorized in the form of (2 ^x -1) f (y) according to the equation (5) as in the equation (7). Then, exponentiation is performed. In other words, The initial value of A _i is α, and the process is performed from the low order to the high order of f (y), shifted by the corresponding order, and the result is multiplied by the result of shifting by the next higher order. By repeating this processing, the result of processing for the highest order is multiplied by the result of processing and storing before And stores it again in A _i . This is the case even when m-1 is an even number.

On the other hand, when exponent part is abbreviated by considering x as m-1 in the exponent part (2 ^x -1), the value of A _i is stored in the intermediate register T _j when it is an odd number instead of a multiple of 3. Then, if x is greater than 3, it goes back to the exponent part abbreviation.

By performing the processing in a cyclic manner in this manner, the following formula (11) can be obtained. The result of factorization of the exponent obtained in the equation (11) includes (2 ⁹ -1) g (z) and the final exponent part reduction discrimination process is performed. On the other hand, when this processing is performed, 2 ³ -1 = (2-1) (2 ² + 2 + 1) = 2 ² + 2 + 1 (or 2 ² -1 = 2 + 1) Shape can be obtained. In FIG. 1, when the m-1 value of the exponent is 2 or 3 after exponent reduction, 2 ² -1 is replaced by 2 + 1 and 2 ³ -1 is replaced by 2 ² + 2 + 1 End exponent reduction and population decomposition process. In particular, if the exponent factor decomposition results in the form of (2 ^y -1) g (z) +1 as in (9), then (2 ^x -1) f The exponent sub-operation is obtained .

In this way, the officer we are seeking , And inverse calculation is terminated. Here, j is from 1 to k (when the exponent part reduction discrimination processing is an odd number instead of a multiple of 3).

As shown in Equation (14) above, the number of times of multiplication is nine, and only one memory is required to store the intermediate value. However, with Itoh's method, nb (111) + ω (111) -1 = 11 times multiplication is required and five intermediate memories are needed, so the difference can be clearly seen.

Moreover, it can be seen that the method of the present invention is much more advantageous when m-1 is a multiple of 3, as shown in the above example, and the method of the present invention is even more useful as long as m-1 is larger. Generally, digital signature techniques use exponent coefficients more than 160 bits in terms of safety of discrete logarithms.

In another method of the present invention, when applying the exponent reduction discrimination processing expression of the present invention to the inverse calculation, the exponent reduction discrimination processing is firstly performed such that m-1 is a multiple of 3, Sub-factorization is done in multiples of three, otherwise it can be divided into even and odd numbers as before.

However, unlike the first method of the present invention, it is advantageous in terms of saving the number of memories.

Considering the improved invention as an example of Itoh's method, it can be seen that

In comparison, the number of multiplications is the same without change, but the number of memories is one, which is more profitable than the two methods of Itoh.

It will be apparent to those skilled in the art that various modifications and variations can be made in the present invention without departing from the spirit or scope of the invention. The present invention is not limited to the drawings.

The present invention as described above can greatly improve the processing speed and save a lot of memory compared to the conventional Itoh inversion calculation method.

Claims (6)

In a method for obtaining an inverse on a finite field using a memory, A first step of performing a preprocessing process of setting the exponent m and initializing the exponent part of the finite field requiring the inverse process; If m-1 is an odd number other than a multiple of 3 after performing an exponent part reduction discrimination process for determining whether m-1 is an even number, a multiple of 3 and an odd number, or an odd number other than a multiple of 3, factor decomposition is performed Storing the result in the intermediate storage means (T _j ) after the exponent sub-operation, storing the result in the intermediate storage means (T _j ), calculating the exponent portion by shifting after performing factor decomposition when it is an odd number or an odd multiple of 3; And determining whether m-1 is larger than a predetermined value, repeating the steps from the second step if the value is greater than a predetermined value, and terminating exponent factor decomposition when the value is less than a predetermined value, To find the inverse on the finite field. The method according to claim 1, The second step comprises: performing an exponent part reduction discrimination process for determining whether m-1 is an even number, a multiple of 3 and an odd number, or an odd number that is not a multiple of 3; As a result of the determination in the above step, of And if it is a multiple of 3 and an odd number of And when it is an odd number other than a multiple of 3 of Performing an factorization process to factorize the input signal; And If the exponent factor decomposition result of the above step is in the form of (2 ^x -1) f (y) or (2 ^x -1) f (y) +1 Storing the result in A _i and storing the value of A _i in the intermediate register (T _j ) when x is an odd number other than a multiple of 3 in (2 ^x -1) of the exponent part To find the inverse on a finite field. 3. The method of claim 2, Wherein the step of performing the exponent part reduction discrimination processing comprises: determining whether m-1 is an even number; And Determining whether the odd number is an even number or an odd number if the odd number is not an even number or an odd number if the odd number is not an odd number. 3. The method of claim 2, Wherein the step of performing the exponent part reduction discrimination processing comprises: determining whether m-1 is a multiple of 3 and an odd number; And Determining whether the odd number is an odd number that is not an odd number that is a multiple of 3 or an odd number that is not a multiple of 3. The method of claim 1, 3. The method of claim 2, In the step And storing the result in A _i , , The initial value of A _i is α, which is processed in order from low order to high order of f (y), shifted by the corresponding order, multiplied by the result of shifting the result by the next higher order, By multiplying the result of processing for the highest order with the result of processing and storing it before The process how to obtain the inverse on a finite field characterized in that stored in A _i. 6. The method according to any one of claims 1 to 5, In the third step, determining whether m-1 is greater than 3; Repeating the steps from the second step if it is determined to be greater than 3; determining whether m-1 is 3 or 2 when m-1 is 3 or less; As a result of the above step, when x is 3, 2 ³ -1 = (2-1) (2 ² + 2 + 1) = 2 ² + 2 + 1 And stores the result in A _i . When m-1 is 2, 2 ² -1 = 2 + 1 is set And storing the result in A _i ; And And computing the inverse of the finite field.