CN108008934A - A kind of compound finite field inversions device based on look-up table - Google Patents

Abstract

The invention discloses a kind of compound finite field inversions device based on look-up table, including controller, input port, output port and arithmetic unit；The input port is used to input compound finite field gf ((2ⁿ)²) inversion operation number a (x)；The controller is used to call the arithmetic unit to carry out inversion operation to the inversion operation number a (x), obtains compound finite field gf ((2ⁿ)²) inversion operation result b (x)；The arithmetic unit is used to run add operation and multiplying, square operation and inversion operation based on look-up table；The output port is used to export the inversion operation result b (x).The present invention can effectively improve the operation efficiency of finite field inversions.

Description

A Composite Finite Field Inversion Device Based on Lookup Table

technical field

The invention relates to the field of computer technology, in particular to a compound finite field inversion device based on a lookup table.

Background technique

Finite field inversion is a finite field operation, and it is widely used in cryptographic algorithms together with operations such as finite field addition, multiplication, division, square, and power. Composite finite fields belong to finite fields, and the inversion of composite finite fields is characterized by subfield operations. The commonly used compound finite field is GF((2 ⁿ ) ² ), the size of the field is (2 ⁿ ) ² , and its subfield is GF(2 ⁿ ). The inversion operation of GF((2 ⁿ ) ² ) generally requires the addition, multiplication, and inversion operations of the subfield GF(2 ⁿ ). Because the compound finite field is the inversion of GF((2 ⁿ ) ² ), it includes subfield GF(2 ⁿ ) operation, so the efficiency of GF((2 ⁿ ) ² ) inversion can be improved by optimizing the GF(2 ⁿ ) operation.

In the real-time and speed-sensitive environment, the compound finite field invertor in the prior art cannot achieve the computational efficiency required by the finite field inversion.

Contents of the invention

Aiming at the problems existing in the prior art, the present invention provides a compound finite field inversion device based on a lookup table, which can effectively improve the computing efficiency of finite field inversion.

The technical scheme that the present invention proposes with respect to above-mentioned technical problem is as follows:

The invention provides a compound finite field inversion device based on a lookup table, including a controller, an input port, an output port and an arithmetic unit;

The input port is used to input the inversion operand a(x) of the compound finite field GF((2 ⁿ ) ² );

The controller is used to call the arithmetic unit to perform an inversion operation on the inversion operand a(x) to obtain an inversion operation result b(x) of the composite finite field GF((2 ⁿ ) ² );

The arithmetic unit is used to perform addition and look-up table-based multiplication, squaring and inversion;

The output port is used to output the inversion result b(x).

Further, the polynomial representation of the inversion operand a(x) is a(x)=a _h x+a _l ;

The polynomial representation of the inversion result b(x) is b(x)=b _h x+b _l ; b(x)=a(x) ^-1 ;

Among them, a _h , a _l , b _h , b _l are all elements of the finite field GF(2 ⁿ ).

Further, the arithmetic unit includes an addition module, a first multiplication module, a second multiplication module, a first square operation module, a second square operation module and an inverse operation module;

The input port is also used to input a clock signal;

The controller is specifically configured to call the first square operation module to calculate s ₀ =a _h ² , call the second square operation module to calculate s ₁ =a _l ² , and call the addition in the first clock cycle. The operation module calculates s ₂ =a _h +a _l ;

In the second clock cycle, call the first multiplication module to calculate s ₃ = _al ×s ₂ , call the second multiplication module to calculate s ₄ =s ₀ ×e;

In the third clock cycle, call the addition module to calculate s ₅ =s ₄ +s ₃ ;

In the fourth clock cycle, call the inversion operation module to calculate s ₆ =s ₅ ^-1 ;

In the fifth clock cycle, call the first multiplication module to calculate b _l =s ₂ ×s ₆ , call the second multiplication module to calculate b _h =a _h ×s ₆ , and then calculate b(x)= b _h x+b _l ;

Among them, s ₀ , a _h , s ₁ , a _l , s ₂ , s ₃ , s ₄ , s ₅ , s ₆ , b _l , b _h are all elements of the finite field GF(2 ⁿ ), and e is the finite field Constant of GF(2 ⁿ ).

Further, the addition operation module includes n XOR logic gates, which are used to calculate e _i = _ci +d for two known elements c(x) and d(x) of the finite field GF(2 ⁿ ) _i , and then get the addition result

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , d(x)=d _n-1 x ^n-1 +d _n-2 x ^n-2 +...+d ₀ , e(x)=e _{n- 1} x ^n-1 +e _n-2 x ^n-2 +...+e ₀ , i=0,1,... .,n-1, n≥1, + is the addition operation of finite field GF(2 ⁿ ), c _n-1 ,c _n-2 ,...,c ₀ ,d _n-1 ,d _n-2 , ..., d ₀ , e _n-1 , e _n-2 ,..., e ₀ are all elements of the finite field GF(2 ⁿ ).

Further, the first square operation module and the second square operation module are respectively used for the known element c(x) of the finite field GF(2 ⁿ ), from the first column of the pre-established square lookup table Find c _i , get the element e _i in the second column of the row where c _i is located, and then obtain the square operation result of c(x)

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , e(x)=en _-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，i＝0,1,...,n-1，c _n-1 ,c _n-2 ,...,c ₀ ,e _n-1 ,e _{n -2} ,...,e ₀ are all elements of the finite field GF(2 ⁿ ).

Further, the first square operation module and the second square operation module are also used to calculate β=α ² modp(x) for each element α of the finite field GF(2 ⁿ ), and store α In the first column of the table, store β in the second column of the row where α is located in the table to build the square lookup table;

Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ and β are elements of the finite field GF(2 ⁿ ).

Further, the first multiplication module and the second multiplication module are respectively used for two known elements c(x) and d(x) of the finite field GF(2 ⁿ ), from a pre-established multiplication lookup table Find all _ci in the first column of the row, find d _i in the second column of the row where ci is located, obtain the element _{e i in} the third column of the row where d _i is located, and then obtain c(x) and d( The result of the multiplication operation of x)

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , d(x)=d _n-1 x ^n-1 +d _n-2 x ^n-2 +...+d ₀ ，e(x)＝e _{n- 1} x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，c _n-1 ,c _{n- 2} ,...,c ₀ ,d _n-1 ,d _n-2 ,...,d ₀ ,e _n-1 ,e _n-2 ,...,e ₀ are all finite fields GF(2 ⁿ ), i=0,1,...,n-1, n≥1.

Further, the first multiplication module and the second multiplication module are also used to calculate δ=α×βmodp(x) for any two elements α and β of the finite field GF(2 ⁿ ), and α Stored in the first column of the table, storing β in the second column of the row where α is located in the table, and storing δ in the third column of the row where β is located in the table, to establish the multiplication lookup table;

Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ ,δ are elements of the finite field GF(2 ⁿ ).

Further, the inversion operation module is used to search for c _i from the first column of the pre-established inversion lookup table for the known element c(x) of the finite field GF(2 ⁿ ), if c _i is found , then obtain the element e _i of the second column of the row where c _i is located, and then obtain the inverse operation result of c(x)

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , e(x)=en _-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，i＝0,1,...,n-1，c _n-1 ,c _n-2 ,...,c ₀ ,e _n-1 ,e _{n -2} ,...,e ₀ are all elements of the finite field GF(2 ⁿ ).

Further, the inversion operation module is also used to calculate β=α ^{- 1} modp(x) for each element α of the finite field GF(2 ⁿ ), and store α in the first column of the table, and store β Stored in the second column of the row where α is located in the table, to construct the inversion lookup table;

Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ ,δ are elements of the finite field GF(2 ⁿ ).

The beneficial effects brought by the technical solution provided by the embodiments of the present invention are:

In the compound finite field inversion operation, the multiplication operation, square operation and inversion operation are performed based on the lookup table. Compared with the finite field inversion device in the prior art, the operation efficiency is effectively improved, and it can be widely used in symmetric encryption (such as DES , AES), public key cryptography and Rainbow, TTS, UOV signatures and other mathematics and engineering fields.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings that need to be used in the description of the embodiments will be briefly introduced below. Obviously, the drawings in the following description are only some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained based on these drawings without creative effort.

FIG. 1 is a schematic structural diagram of a compound finite field inversion device based on a lookup table provided by Embodiment 1 of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the implementation manner of the present invention will be further described in detail below in conjunction with the accompanying drawings.

Embodiment one

An embodiment of the present invention provides a compound finite field inversion device based on a lookup table, as shown in FIG. 1 , the device includes a controller 1, an input port, an output port b, and an arithmetic unit;

The input port includes a port a, which is used to input the inversion operand a(x) of the compound finite field GF((2 ⁿ ) ² );

The controller 1 is used to call the arithmetic unit to perform an inversion operation on the inversion operand a(x), and obtain an inversion operation result b(x) of the compound finite field GF((2 ⁿ ) ² );

The arithmetic unit is used to perform addition and look-up table-based multiplication, squaring and inversion;

The output port b is used to output the inversion result b(x).

Wherein, the controller is respectively connected with the input port, the output port, and the arithmetic unit, and is used for scheduling the connected components. The input ports include port a for inputting the inversion operand a(x) of the composite finite field GF((2 ⁿ ) ² ), and the output ports include port b for outputting the composite finite field GF((2 ⁿ ) ² ) The inverse operation result b(x) of .

Further, the polynomial representation of the inversion operand a(x) is a(x)=a _h x+a _l ;

The polynomial representation of the inversion result b(x) is b(x)=b _h x+b _l ; b(x)=a(x) ^-1 ;

Among them, a _h , a _l , b _h , b _l are all elements of the finite field GF(2 ⁿ ).

It should be noted that the irreducible polynomial of GF((2 ⁿ ) ² ) is q(x)=x ² +x+e, and e is a constant of the finite field GF(2 ⁿ ). The inverse operand a(x) is composed of two n-bit numbers, which can be expressed in the form of polynomials or in the form of coefficients, such as a(x)=a(a _h , a _l ), a _h , a _l is an element of the finite field GF(2 ⁿ ). The inverse operation result b(x) consists of two n-bit numbers, which can be expressed in the form of polynomials or in the form of coefficients, such as b(x)=b(b _h , b _l ), b _h ,b _l is an element of the finite field GF(2 ⁿ ).

Further, the arithmetic unit includes an addition module 4, a first multiplication module 5, a second multiplication module 6, a first square operation module 7, a second square operation module 8 and an inverse operation module 9;

The input port also includes a port clk for inputting a clock signal;

The controller is specifically configured to call the first square operation module to calculate s ₀ =a _h ² , call the second square operation module to calculate s ₁ =a _l ² , and call the addition in the first clock cycle. The operation module calculates s ₂ =a _h +a _l ;

In the second clock cycle, call the first multiplication module to calculate s ₃ = _al ×s ₂ , call the second multiplication module to calculate s ₄ =s ₀ ×e;

In the third clock cycle, call the addition module to calculate s ₅ =s ₄ +s ₃ ;

In the fourth clock cycle, call the inversion operation module to calculate s ₆ =s ₅ ^-1 ;

In the fifth clock cycle, call the first multiplication module to calculate b _l =s ₂ ×s ₆ , call the second multiplication module to calculate b _h =a _h ×s ₆ , and then calculate b(x)= b _h x+b _l ;

Among them, s ₀ , a _h , s ₁ , a _l , s ₂ , s ₃ , s ₄ , s ₅ , s ₆ , b _l , b _h are all elements of the finite field GF(2 ⁿ ), and e is the finite field Constant of GF(2 ⁿ ).

It should be noted that the controller 1 is connected to the addition module 4 , the first multiplication module 5 , the second multiplication module 6 , the first square module 7 , the second square module 8 and the inversion module 9 . The input port also includes a port clk for inputting a clock signal. The controller is also used to parse the clock signal. The clock signal is a single-bit signal, with a value of 0 or 1, representing a low level or a high level, and a transition from a low level to a high level represents the beginning of a clock cycle. The addition module includes a logic gate circuit for calculating GF (2 ⁿ ) addition; the first multiplication module and the second multiplication module include a lookup table structure and a calculation circuit for calculating GF (2 ⁿ ) multiplication respectively; the first The square operation module and the second square operation module include a lookup table structure and a calculation circuit for calculating the square of GF(2 ⁿ ) respectively; the inverse operation module includes a lookup table structure and a calculation circuit for calculating the inverse of GF(2 ⁿ ) .

Further, the addition operation module includes n XOR logic gates, which are used to calculate e _i = _ci +d for two known elements c(x) and d(x) of the finite field GF(2 ⁿ ) _i , and then get the addition result

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , d(x)=d _n-1 x ^n-1 +d _n-2 x ^n-2 +...+d ₀ , e(x)=e _{n- 1} x ^n-1 +e _n-2 x ^n-2 +...+e ₀ , i=0,1,... .,n-1, n≥1, + is the addition operation of finite field GF(2 ⁿ ), c _n-1 ,c _n-2 ,...,c ₀ ,d _n-1 ,d _n-2 , ..., d ₀ , e _n-1 , e _n-2 ,..., e ₀ are all elements of the finite field GF(2 ⁿ ).

It should be noted that the addition of the finite field GF(2 ⁿ ) uses exclusive OR logic gates, so the addition operation module includes n exclusive OR logic gates, which are used to calculate the two known elements c(x) of GF(2 ⁿ ) Addition of d(x) e(x)=c(x)+d(x). During specific operation, for i=0,1,...,n-1, calculate e _i = _ci +d _i to obtain the addition result

Further, the first square operation module and the second square operation module are respectively used for the known element c(x) of the finite field GF(2 ⁿ ), from the first column of the pre-established square lookup table Find c _i , get the element e _i in the second column of the row where c _i is located, and then obtain the square operation result of c(x)

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , e(x)=en _-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，i＝0,1,...,n-1，c _n-1 ,c _n-2 ,...,c ₀ ,e _n-1 ,e _{n -2} ,...,e ₀ are all elements of the finite field GF(2 ⁿ ).

It should be noted that the first square operation module and the second square operation module have the same structure, and are used to calculate the square e(x)=c(x) ² of the known element c(x) of the finite field GF(2 ⁿ ) . During specific operation, first search for _ci in the first column of the square lookup table, and after finding it, the element in the second column of the row where _ci is located in the square lookup table is the square operation result of _ci , and store it in e _i . The result of the square operation of c(x) can be obtained

Further, the first square operation module and the second square operation module are also used to calculate β=α ² modp(x) for each element α of the finite field GF(2 ⁿ ), and store α In the first column of the table, store β in the second column of the row where α is located in the table to build the square lookup table;

Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ and β are elements of the finite field GF(2 ⁿ ).

It should be noted that before the operation of the first square calculation module and the second square calculation module, a square lookup table needs to be established in the modules. For each element of the finite field GF(2 ⁿ ), calculate its square, for example, the element of GF(2 ⁿ ) is α, calculate β=α ² modp(x), and store α in the first column of the table, and β Stored in the second column of the row of α in the table. After each element of the finite field GF(2 ⁿ ) and its square result are correspondingly stored in the table, the table serves as a square lookup table.

Further, the first multiplication module and the second multiplication module are respectively used for two known elements c(x) and d(x) of the finite field GF(2 ⁿ ), from a pre-established multiplication lookup table Find all _ci in the first column of the row, find d _i in the second column of the row where ci is located, obtain the element _{e i in} the third column of the row where d _i is located, and then obtain c(x) and d( The result of the multiplication operation of x)

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , d(x)=d _n-1 x ^n-1 +d _n-2 x ^n-2 +...+d ₀ ，e(x)＝e _{n- 1} x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，c _n-1 ,c _{n- 2} ,...,c ₀ ,d _n-1 ,d _n-2 ,...,d ₀ ,e _n-1 ,e _n-2 ,...,e ₀ are all finite fields GF(2 ⁿ ), i=0,1,...,n-1, n≥1.

It should be noted that the multiplication of the finite field GF(2 ⁿ ) uses AND logic gates. The first multiplication module and the second multiplication module have the same structure, and are used to calculate the multiplication e(x)=c(x) of two known elements c(x) and d(x) of the finite field GF(2 ⁿ ) )×d(x). During specific operation, first look up _ci in the first column of the multiplication lookup table. Generally, the first column of the multiplication lookup table has multiple ci _s , find out all _ci , and then start from the second column of the row where each _ci is located Find d _i in the elements of , and after finding it, store the third element in the row where c _i and d _i are located in e _i , and you can get the multiplication result of c(x) and d(x)

Further, the first multiplication module and the second multiplication module are also used to calculate δ=α×βmodp(x) for any two elements α and β of the finite field GF(2 ⁿ ), and α Stored in the first column of the table, storing β in the second column of the row where α is located in the table, and storing δ in the third column of the row where β is located in the table, to establish the multiplication lookup table;

Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ ,δ are elements of the finite field GF(2 ⁿ ).

It should be noted that before the operation of the first multiplication module and the second multiplication module, a multiplication lookup table needs to be established in the modules. For any two elements of the finite field GF(2 ⁿ ), calculate their multiplication, for example, the two elements of GF(2 ⁿ ) are α and β, calculate δ=α×βmodp(x), and store α in the table In the first column, β is stored in the second column of the row where α is located in the table, and δ is stored in the third column of the row where α and β are located in the table. After every two elements of the finite field GF(2 ⁿ ) and their multiplication results are correspondingly stored in the table, the table serves as a multiplication lookup table.

Further, the inversion operation module is used to search for c _i from the first column of the pre-established inversion lookup table for the known element c(x) of the finite field GF(2 ⁿ ), if c _i is found , then obtain the element e _i of the second column of the row where c _i is located, and then obtain the inverse operation result of c(x)

Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , e(x)=en _-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，i＝0,1,...,n-1，c _n-1 ,c _n-2 ,...,c ₀ ,e _n-1 ,e _{n -2} ,...,e ₀ are all elements of the finite field GF(2 ⁿ ).

It should be noted that the inversion operation module is used to calculate the inversion e(x)=c(x) ⁻¹ of the known element c(x) of the finite field GF(2 ⁿ ). When actually running, first search for _ci in the first column of the square lookup table. If _ci is not found, it means that _ci has no inverse element. If it is found, find the second column of the row where _ci is located in the inverse lookup table. The element of is the inversion result of c _i , stored in e _i , and the inversion result of c(x) can be obtained

Further, the inversion operation module is also used to calculate β=α ^{- 1} modp(x) for each element α of the finite field GF(2 ⁿ ), and store α in the first column of the table, and store β Stored in the second column of the row where α is located in the table, to construct the inversion lookup table;

Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ ,δ are elements of the finite field GF(2 ⁿ ).

It should be noted that before the operation of the inversion operation module, an inversion lookup table needs to be established in the module. For each element of the finite field GF(2 ⁿ ) (except the zero element), calculate the inversion, for example, the element of GF(2 ⁿ ) is α, calculate β=α ^-1 modp(x), and store α in the table in the first column of , store β in the second column of the row of α in the said table. After each element of the finite field GF(2 ⁿ ) and its inversion result are correspondingly stored in the table, the table is used as an inversion lookup table.

The following takes n=4 as an example to illustrate the working process of the compound finite field inversion device provided by the embodiment of the present invention.

The operand a(x) of the input port is an element of the compound finite field GF((2 ⁴ ) ² ), which can be expressed as a polynomial:

a(x)=a _h x+a _l ,

a _h , a _l are elements of the finite field GF(2 ⁴ ).

The operand b(x) of the output port is an element of the composite finite field GF((2 ⁴ ) ² ), which can be expressed as a polynomial:

b(x)=b _h x+b _l ,

b _h , b _l are elements of the finite field GF(2 ⁴ ).

The clock signal clk of the input port is a single-bit signal, and the clock period is 50 nanoseconds.

The controller computes the inverse of b(x)=a(x) ^-1 of GF((2 ⁴ ) ² ), where the irreducible polynomial of GF((2 ⁴ ) ² ) is q(x)=x ² +x +9, the steps are as follows:

The controller receives the input operand a(x) and the clock signal, and waits for the clock signal to change from low level to high level;

In the first clock cycle, the controller calls the first square operation module to calculate s ₀ =a _h ² , s ₀ , a _h are elements of the finite field GF(2 ⁴ ); the controller calls the second square operation module to calculate s ₁ = a _l ² , s ₁ , a _l are the elements of the finite field GF(2 ⁴ ); the controller calls the addition operation module to calculate s ₂ =a _h +a _l , s ₂ , a _h , a _l are the elements of the finite field GF(2 ⁴ ) elements;

In the second clock cycle, the controller calls the first multiplication module to calculate s ₃ =a _l ×s ₂ , s ₃ , a _l , and s ₂ are elements of the finite field GF(2 ⁴ ); the controller calls the second multiplication operation The module calculates s ₄ =s ₀ ×9, s ₄ , s ₀ are elements of the finite field GF(2 ⁴ );

In the third clock cycle, the controller calls the addition module to calculate s ₅ =s ₄ +s ₃ , s ₅ , s ₄ , and s ₃ are elements of the finite field GF(2 ⁴ );

In the fourth clock cycle, the controller invokes the inversion operation module to calculate s ₆ =s ₅ ^-1 , s ₆ , s ₅ are elements of the finite field GF(2 ⁴ );

In the fifth clock cycle, the controller calls the first multiplication module to calculate b _l =s ₂ ×s ₆ , b _l , s ₂ , and s ₆ are elements of the finite field GF(2 ⁴ ); the controller calls the second multiplication operation The module calculates b _h ＝a _h ×s ₆ , b _l , a _h , s ₆ are elements of the finite field GF(2 ⁴ );

Finally, b(x)=b _h x+b _l is the inverse of a(x)=a _h x+a _l , and is output to the output port by the controller.

In the compound finite field inversion operation, the embodiment of the present invention performs multiplication, square operation and inversion operation based on the lookup table. Compared with the finite field invertor in the prior art, the operation efficiency is effectively improved, and it can be widely used in various field of engineering.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within range.

Claims (10)

1. A compound finite field inverting device based on look-up table, is characterized in that, comprises controller, input port, output port and operator; The input port is used to input the inversion operand a(x) of the compound finite field GF((2 ⁿ ) ² ); The controller is used to call the arithmetic unit to perform an inversion operation on the inversion operand a(x) to obtain an inversion operation result b(x) of the composite finite field GF((2 ⁿ ) ² ); The arithmetic unit is used to perform addition and look-up table-based multiplication, squaring and inversion; The output port is used to output the inversion result b(x). 2. the compound finite field inversion device based on look-up table as claimed in claim 1, is characterized in that, the polynomial expression form of described inversion operand a(x) is a(x)=a _h x+a _l ; The polynomial representation of the inversion result b(x) is b(x)=b _h x+b _l ; b(x)=a(x) ^-1 ; Among them, a _h , a _l , b _h , b _l are all elements of the finite field GF(2 ⁿ ). 3. the compound finite field inversion device based on look-up table as claimed in claim 2, is characterized in that, described arithmetic unit comprises addition operation module, the first multiplication operation module, the second multiplication operation module, the first square operation module , the second square operation module and the inverse operation module; The input port is also used to input a clock signal; The controller is specifically configured to call the first square operation module to calculate s ₀ =a _h ² , call the second square operation module to calculate s ₁ =a _l ² , and call the addition in the first clock cycle. The operation module calculates s ₂ =a _h +a _l ; In the second clock cycle, call the first multiplication module to calculate s ₃ = _al ×s ₂ , call the second multiplication module to calculate s ₄ =s ₀ ×e; In the third clock cycle, call the addition module to calculate s ₅ =s ₄ +s ₃ ; In the fourth clock cycle, call the inversion operation module to calculate s ₆ =s ₅ ^-1 ; In the fifth clock cycle, call the first multiplication module to calculate b _l =s ₂ ×s ₆ , call the second multiplication module to calculate b _h =a _h ×s ₆ , and then calculate b(x)= b _h x+b _l ; Among them, s ₀ , a _h , s ₁ , a _l , s ₂ , s ₃ , s ₄ , s ₅ , s ₆ , b _l , b _h are all elements of the finite field GF(2 ⁿ ), and e is the finite field Constant of GF(2 ⁿ ). 4. The compound finite field inversion device based on look-up table as claimed in claim 3, is characterized in that, described addition operation module comprises n XOR logic gates, is used for two for finite field GF (2 ⁿ ) Given the elements c(x) and d(x), calculate e _i = _ci +d _i , and then obtain the addition result Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , d(x)=d _n-1 x ^n-1 +d _n-2 x ^n-2 +...+d ₀ , e(x)=e _n-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ , i=0,1,... .,n-1, n≥1, + is the addition operation of finite field GF(2 ⁿ ), c _n-1 ,c _n-2 ,...,c ₀ ,d _n-1 ,d _n-2 , ..., d ₀ , e _n-1 , e _n-2 ,..., e ₀ are all elements of the finite field GF(2 ⁿ ). 5. The compound finite field inversion device based on look-up table as claimed in claim 3, is characterized in that, described first square operation module and described second square operation module are respectively used for finite field GF (2 ⁿ ) The known element c(x) of , look up _ci from the first column of the pre-established square lookup table, obtain the element _{e i of} the second column of the row where ci is located, and then obtain the square operation result of c(x) Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , e(x)=en _-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，i＝0,1,...,n-1，c _n-1 ,c _n-2 ,...,c ₀ ,e _n-1 ,e _{n -2} ,...,e ₀ are all elements of the finite field GF(2 ⁿ ). 6. the compound finite field inversion device based on lookup table as claimed in claim 5, is characterized in that, described first square operation module and described second square operation module are also used for finite field GF (2 ⁿ ) for each element α, calculate β=α ² modp(x), and store α in the first column of the table, store β in the second column of the row where α is located in the table, to establish the square lookup surface; Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ and β are elements of the finite field GF(2 ⁿ ). 7. The compound finite field inversion device based on look-up table as claimed in claim 3, is characterized in that, described first multiplication module and the second multiplication module are respectively used for two for finite field GF (2 ⁿ ) Known elements c(x) and d(x), find out all c _i from the first column of the pre-established multiplication lookup table, find d _i from the second column of the row where c _i is located, and obtain the found The third column element e _i of the row where d _i is located, and then obtain the multiplication result of c(x) and d(x) Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , d(x)=d _n-1 x ^n-1 +d _n-2 x ^n-2 +...+d ₀ , e(x)=e _n-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ , c _n-1 ,c _{n- 2} ,...,c ₀ ,d _n-1 ,d _n-2 ,...,d ₀ ,e _n-1 ,e _n-2 ,...,e ₀ are all finite fields GF(2 ⁿ ), i=0,1,...,n-1, n≥1. 8. The compound finite field inversion device based on look-up table as claimed in claim 7, is characterized in that, described first multiplication module and the second multiplication module are respectively also used for finite field GF (2 ⁿ ) For any two elements α and β, calculate δ=α×βmodp(x), and store α in the first column of the table, store β in the second column of the row where α is located in the table, and store δ in the The third column of the row where β is located in the table, to set up the multiplication lookup table; Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ ,δ are elements of the finite field GF(2 ⁿ ). 9. The compound finite field inversion device based on look-up table as claimed in claim 3, is characterized in that, described inversion operation module is used for the known element c (x) of finite field GF (2 ⁿ ), from Search for c _i in the first column of the pre-established inversion lookup table, if c _i is found, obtain the element e _i of the second column of the row where c _i is located, and then obtain the inversion result of c(x) Among them, c(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₀ , e(x)=en _-1 x ^n-1 +e _n-2 x ^n-2 +...+e ₀ ，i＝0,1,...,n-1，c _n-1 ,c _n-2 ,...,c ₀ ,e _n-1 ,e _{n -2} ,...,e ₀ are all elements of the finite field GF(2 ⁿ ). 10. The compound finite field inversion device based on a lookup table as ^claimed in claim 9, wherein the inversion operation module is also used for calculating β= α ^-1 modp(x), and α is stored in the first column of the table, and β is stored in the second column of the row where α is in the table, to construct the inversion lookup table; Among them, mod is a modular operation, p(x)=x ⁿ +p _n-1 x ^n-1 +...+1 is an irreducible polynomial of finite field GF(2 ⁿ ), p _n-1 ,p _{n- 2} ,...,p ₁ ,δ are elements of the finite field GF(2 ⁿ ).