[go: up one dir, main page]

CN107885486B - A complex finite field inversion device based on search tree - Google Patents

A complex finite field inversion device based on search tree Download PDF

Info

Publication number
CN107885486B
CN107885486B CN201711259841.4A CN201711259841A CN107885486B CN 107885486 B CN107885486 B CN 107885486B CN 201711259841 A CN201711259841 A CN 201711259841A CN 107885486 B CN107885486 B CN 107885486B
Authority
CN
China
Prior art keywords
node
finite field
inversion
operation module
tree
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201711259841.4A
Other languages
Chinese (zh)
Other versions
CN107885486A (en
Inventor
易海博
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shenzhen Polytechnic
Original Assignee
Shenzhen Polytechnic
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Shenzhen Polytechnic filed Critical Shenzhen Polytechnic
Priority to CN201711259841.4A priority Critical patent/CN107885486B/en
Publication of CN107885486A publication Critical patent/CN107885486A/en
Application granted granted Critical
Publication of CN107885486B publication Critical patent/CN107885486B/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/726—Inversion; Reciprocal calculation; Division of elements of a finite field

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)
  • Error Detection And Correction (AREA)

Abstract

The invention discloses a composite finite field inversion device based on a search tree, which is characterized by comprising a controller, an input port, an output port and an arithmetic unit, wherein the input port is connected with the output port of the controller; the input port is used for inputting a composite finite field GF ((2)n)2) The inversion operand a (x); the controller is used for calling the arithmetic unit to perform inversion operation on the inversion operand a (x) to obtain a composite finite field GF ((2)n)2) The inversion result b (x) of (a); the arithmetic unit is used for operating addition operation, multiplication operation, square operation and inversion operation based on a search tree; the output port is used for outputting the inversion operation result b (x). The invention can effectively improve the operation efficiency of finite field inversion.

Description

Composite finite field inversion device based on search tree
Technical Field
The invention relates to the technical field of computers, in particular to a composite finite field inversion device based on a search tree.
Background
Finite field inversion belongs to finite field operation, and is widely used by cryptographic algorithms together with operations such as finite field addition, multiplication, division, squaring, and squaring. The composite finite field belongs to a finite field, and the inversion of the composite finite field is characterized in that the operation of a subdomain is required. A commonly used complex finite field is GF ((2)n)2) The size of the field is (2)n)2The subfield of which is GF (2)n)。GF((2n)2) The inversion operation of (2) generally requires the sub-field GFn) Addition, multiplication, inversion, etc. Since the complex finite field is GF ((2)n)2) Inversion containment subfield GF (2)n) Operation, therefore by optimizing GF (2)n) The operation can promote GF ((2)n)2) The inversion efficiency of (1).
The composite finite field inverter in the prior art cannot realize the arithmetic efficiency required by finite field inversion in real time and in a speed-sensitive environment.
Disclosure of Invention
Aiming at the problems in the prior art, the invention provides a composite finite field inversion device based on a search tree, which can effectively improve the operation efficiency of finite field inversion.
The technical scheme provided by the invention for the technical problem is as follows:
the invention provides a composite finite field inversion device based on a search tree, which comprises a controller, an input port, an output port and an arithmetic unit, wherein the input port is connected with the output port of the controller;
the input port is used for inputting a composite finite field GF ((2)n)2) The inversion operand a (x);
the controller is used for calling the arithmetic unit to perform inversion operation on the inversion operand a (x) to obtain a composite finite field GF ((2)n)2) The inversion result b (x) of (a);
the arithmetic unit is used for operating addition operation, multiplication operation, square operation and inversion operation based on a search tree;
the output port is used for outputting the inversion operation result b (x).
Further, the polynomial expression of the inverse operand a (x) is a (x) ═ ahx+al；
The polynomial expression of the inversion result b (x) is b (x) ═ bhx+bl；b(x)＝a(x)-1；
Wherein, ah,al,bh,blAre all finite fields GF (2)n) Of (2) is used.
Furthermore, the arithmetic unit comprises an addition operation module, a multiplication operation module, a square operation module and an inversion operation module;
the input port is also used for inputting a clock signal;
the controller is specifically configured to invoke the addition module to calculate s in a first clock cycle0＝ah+alCalling the square operation module to calculate s1＝ah 2Invoking the multiplication operation module to calculate s3＝ah×al；
In the second clock period, calling the square operation module to calculate s2＝al 2Invoking the multiplication operation module to calculate s4＝s1×e；
In the third clock cycle, calling the addition operation module to calculate s5＝s4+s3；
In the fourth clock cycle, calling the addition operation module to calculate s6＝s5+s2；
In the fifth clock cycle, calling the inversion operation module to calculate s7＝s6 -1；
In the sixth clock cycle, calling the multiplication operation module to calculate bl＝s0×s7；
In the seventh clock cycle, calling the multiplication operation module to calculate bh＝ah×s7Further, b (x) and b are calculatedhx+bl；
Wherein s is0,ah,s1,al,s2,s3,s4,s5,s6,s7,bl,bhAre all finite fields GF (2)n) E is a finite field GF (2)n) Is constant.
Further, the addition module comprises n xor logic gates for the finite field GF (2)n) C (x) and d (x), calculating ei＝ci+diFurther obtain the addition result
Figure BDA0001493293820000031
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，d(x)＝dn-1xn-1+dn-2xn-2+...+d0，e(x)＝en- 1xn-1+en-2xn-2+...+e0I-0, 1, n-1, n ≧ 1, + is finite field GF (2)n) Addition of cn-1,cn-2,...,c0,dn-1,dn-2,...,d0,en-1,en-2,...,e0Are all finite fields GF (2)n) Of (2) is used.
Further, the multiplication is carried outThe computation block comprises a plurality of AND and XOR gates for the finite field GF (2)n) C (x) and d (x), calculating
Figure BDA0001493293820000032
And
Figure BDA0001493293820000033
j is 0,1, 2n-2, and then calculated
Figure BDA0001493293820000034
i is 0,1, n-1, n is more than or equal to 1, and a multiplication result is obtained
Figure BDA0001493293820000035
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，d(x)＝dn-1xn-1+dn-2xn-2+...+d0，e(x)＝en- 1xn-1+en-2xn-2+...+e0Mod is a modulo operation, p (x) xn+pn-1xn-1+.. +1 is the finite field GF (2)n) Irreducible polynomial of (a), pn-1,pn-2,...,p1,vjl,cl,dk,Sj,ei,vjiAre all finite fields GF (2)n) Of (2) is used.
Further, the squaring operation module comprises a plurality of AND and XOR gates for finite fields GF (2)n) C (x), calculating
Figure BDA0001493293820000036
And
Figure BDA0001493293820000037
j is 0,1, 2n-2, and then calculated
Figure BDA0001493293820000038
i is 0,1, n-1, n is more than or equal to 1, and a square operation result is obtained
Figure BDA0001493293820000039
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，e(x)＝en-1xn-1+en-2xn-2+...+e0Mod is a modulo operation, p (x) xn+pn-1xn-1+.. +1 is the finite field GF (2)n) Irreducible polynomial of (a), pn-1,pn-2,...,p1,vjl,cl,ck,Sj,ei,vjiAre all finite fields GF (2)n) Of (2) is used.
Further, the inversion module comprises a plurality of and or gates for addressing the finite field GF (2)n) Based on the search tree, e (x) ═ c (x)-1；
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，e(x)＝en-1xn-1+en-2xn-2+...+e0，cn-1,cn-2,...,c0,en-1,en-2,...,e0Are all finite fields GF (2)n) Of (2) is used.
Further, the inversion operation module is specifically configured to construct two search trees, where each search tree has n layers, and corresponds to the 0 th layer to the n-1 th layer respectively; the 0 th layer of each search tree is provided with a tree node, one tree node is set as a left node, and the other tree node is set as a right node; from the 0 th layer to the n-2 th layer, each tree node of each layer is provided with two child nodes which are respectively set as a left node and a right node and are used as the tree node of the next layer; wherein, the left node represents a value of 0, and the right node represents a value of 1;
for c (x) ═ cn-1xn-1+cn-2xn-2+...+c0From c0At the beginning, according to c0The value of (d) is entered into two tree nodes at level 0Line marking, if c0If the value of (1) is 0, marking a left node of the two tree nodes, and if the value of (1) is 1, marking a right node of the two tree nodes, thereby obtaining a 0 th layer of marked nodes;
according to c1If c is the value of (c), marking two child nodes of the 0 th layer marking node1If the value of (c) is 0, then the left node of the two child nodes is marked, if c is1If the value of (1) is 1, marking the right node of the two child nodes so as to obtain a layer 1 marked node;
sequentially marking each layer until a marking node of the (n-1) th layer is obtained;
if the marking node of the n-1 th layer is connected with another tree node of the n-1 th layer, judging that c (x) has an inverse element;
judging whether the connected tree nodes are left nodes or right nodes, and if the connected tree nodes are left nodes, setting en-1If it is 0, e is set for right noden-1＝1；
Judging whether the tree node of the (n-2) th layer to which the connected tree nodes belong is a left node or a right node, and if the tree node is the left node, setting en-2If it is 0, e is set for right noden-2＝1；
Sequentially judging each layer until e is set0To obtain the result of the inversion operation
Figure BDA0001493293820000051
The technical scheme provided by the embodiment of the invention has the following beneficial effects:
in the complex finite field inversion operation, inversion operation is carried out based on a search tree, compared with a finite field inverter in the prior art, the operation efficiency is effectively improved, and the method can be widely applied to the mathematical fields and the engineering fields of symmetric encryption (such as DES and AES), public key cryptography, Rainbow, TTS, UOV signature and the like.
Drawings
In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings needed to be used in the description of the embodiments will be briefly introduced below, and it is obvious that the drawings in the following description are only some embodiments of the present invention, and it is obvious for those skilled in the art to obtain other drawings based on these drawings without creative efforts.
Fig. 1 is a schematic structural diagram of a finite field multiplier of a complex finite field inversion apparatus based on a lookup tree according to an embodiment of the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, embodiments of the present invention will be described in detail with reference to the accompanying drawings.
The embodiment of the invention provides a composite finite field inversion device based on a search tree, which is shown in figure 1 and comprises a controller 1, an input port, an output port b and an arithmetic unit;
the input port comprises a port a for inputting a composite finite field GF ((2)n)2) The inversion operand a (x);
the controller 1 is used for calling the arithmetic unit to perform an inversion operation on the inversion operand a (x) to obtain a composite finite field GF ((2)n)2) The inversion result b (x) of (a);
the arithmetic unit is used for operating addition operation, multiplication operation, square operation and inversion operation based on a search tree;
the output port b is used for outputting the inversion operation result b (x).
The controller is respectively connected with the input port, the output port and the arithmetic unit and used for scheduling connected components. The input port comprises a port a for inputting the composite finite field GF ((2)n)2) The output port comprises a port b for outputting the composite finite field GF ((2)n)2) The result b (x) of the inversion operation of (a).
Further, the polynomial expression of the inverse operand a (x) is a (x) ═ ahx+al；
The polynomial expression of the inversion result b (x) is b (x) ═ bhx+bl；b(x)＝a(x)-1；
Wherein, ah,al,bh,blAre all finite fields GF (2)n) Of (2) is used.
Incidentally, GF ((2)n)2) Is q (x) x2+ x + e, e is the finite field GF (2)n) Is constant. The inverse operand a (x) is composed of two n-bit numbers, and can be expressed in polynomial form or coefficient form, such as a (x) a (a)h,al)，ah,alIs a finite field GF (2)n) Of (2) is used. The inversion result b (x) is composed of two n-bit arrays, and can be expressed in the form of a polynomial or a coefficient, such as b (x) b (b)h,bl)，bh,blIs a finite field GF (2)n) Of (2) is used.
Furthermore, the arithmetic unit comprises an addition operation module 2, a multiplication operation module 3, a square operation module 4 and an inversion operation module 5;
the input port further comprises a port clk for inputting a clock signal;
the controller 1 is specifically configured to invoke the addition operation module to calculate s in a first clock cycle0＝ah+alCalling the square operation module to calculate s1＝ah 2Invoking the multiplication operation module to calculate s3＝ah×al；
In the second clock period, calling the square operation module to calculate s2＝al 2Invoking the multiplication operation module to calculate s4＝s1×e；
In the third clock cycle, calling the addition operation module to calculate s5＝s4+s3；
In the fourth clock cycle, calling the addition operation module to calculate s6＝s5+s2；
In the fifth clock cycle, calling the inversion operation module to calculate s7＝s6 -1；
In the sixth clock cycle, calling the multiplication operation module to calculate bl＝s0×s7；
In the seventh clock cycle, calling the multiplication operation module to calculate bh＝ah×s7Further, b (x) and b are calculatedhx+bl；
Wherein s is0,ah,s1,al,s2,s3,s4,s5,s6,s7,bl,bhAre all finite fields GF (2)n) E is a finite field GF (2)n) Is constant.
The controller 1 is connected to the addition module 4, the first multiplication module 5, the second multiplication module 6, the first square operation module 7, the second square operation module 8, and the inversion module 9, respectively. The input port further comprises a port clk for inputting a clock signal. The controller is also used for analyzing the clock signal. The clock signal is a single bit signal, the value of which is 0 or 1, representing low level or high level, and the transition from low level to high level representing the beginning of a clock cycle. The addition module includes a module for calculating GF (2)n) A logic gate circuit for addition; the multiplication module includes a module for calculating GF (2)n) A logic gate circuit for multiplication; the squaring module includes a module for calculating GF (2)n) A squared logic gate circuit; the inversion operation module comprises a calculation module for calculating GF (2)n) An inverted lookup structure.
Further, the addition module comprises n xor logic gates for the finite field GF (2)n) C (x) and d (x), calculating ei＝ci+diFurther obtain the addition result
Figure BDA0001493293820000071
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，d(x)＝dn-1xn-1+dn-2xn-2+...+d0，e(x)＝en- 1xn-1+en-2xn-2+...+e0I-0, 1, n-1, n ≧ 1, + is finite field GF (2)n) Addition of cn-1,cn-2,...,c0,dn-1,dn-2,...,d0,en-1,en-2,...,e0Are all finite fields GF (2)n) Of (2) is used.
The finite field GF (2)n) The addition of (2) uses exclusive or logic gates, so that the addition block comprises n exclusive or logic gates for computing GF (2)n) The addition of two known elements c (x) and d (x) e (x) ═ c (x) + d (x). In a specific operation, e is calculated for i 0,1i＝ci+diThe result of the addition operation is obtained
Figure BDA0001493293820000081
Further, the multiplication operation module comprises a plurality of AND logic gates and XOR logic gates for addressing the finite field GF (2)n) C (x) and d (x), calculating
Figure BDA0001493293820000082
And
Figure BDA0001493293820000083
j is 0,1, 2n-2, and then calculated
Figure BDA0001493293820000084
i is 0,1, n-1, n is more than or equal to 1, and a multiplication result is obtained
Figure BDA0001493293820000085
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，d(x)＝dn-1xn-1+dn-2xn-2+...+d0，e(x)＝en- 1xn-1+en-2xn-2+...+e0Mod is a modulo operation, p (x) xn+pn-1xn-1+.. +1 is the finite field GF (2)n) Irreducible polynomial of (a), pn-1,pn-2,...,p1,vjl,cl,dk,Sj,ei,vjiAre all finite fields GF (2)n) Of (2) is used.
The finite field GF (2)n) The addition uses an exclusive-or gate and the multiplication uses an and gate, so that the multiplication module comprises a plurality of and gates and exclusive-or gates for computing GF (2)n) The multiplication e (x) of two known elements c (x) and d (x) of (a), (b), (c), (x) and (x). At specific operation, for j 0,1
Figure BDA0001493293820000086
And
Figure BDA0001493293820000087
for i-0, 1
Figure BDA0001493293820000088
Finally, the multiplication result is obtained
Figure BDA0001493293820000089
Further, the squaring operation module comprises a plurality of AND and XOR gates for finite fields GF (2)n) C (x), calculating
Figure BDA00014932938200000810
And
Figure BDA00014932938200000811
j is 0,1, 2n-2, and then calculated
Figure BDA00014932938200000812
i is 0,1, n-1, n is more than or equal to 1, and a square operation result is obtained
Figure BDA00014932938200000813
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，e(x)＝en-1xn-1+en-2xn-2+...+e0Mod is a modulo operation, p (x) xn+pn-1xn-1+.. +1 is the finite field GF (2)n) Irreducible polynomial of (a), pn-1,pn-2,...,p1,vjl,cl,ck,Sj,ei,vjiAre all finite fields GF (2)n) Of (2) is used.
The finite field GF (2)n) The addition uses an exclusive-or gate and the multiplication uses an and gate, so that the multiplication module comprises a plurality of and gates and exclusive-or gates for computing GF (2)n) The square e (x) of (c), (x) c (x)2. At specific operation, for j 0,1
Figure BDA0001493293820000091
And
Figure BDA0001493293820000092
for i-0, 1
Figure BDA0001493293820000093
Finally, the square operation result is obtained
Figure BDA0001493293820000094
Further, the inversion module comprises a plurality of and or gates for addressing the finite field GF (2)n) Based on the search tree, e (x) ═ c (x)-1；
Wherein c (x) cn-1xn-1+cn-2xn-2+...+c0，e(x)＝en-1xn-1+en-2xn-2+...+e0，cn-1,cn-2,...,c0,en-1,en-2,...,e0Are all finite fields GF (2)n) Of (2) is used.
Further, the inversion operation module is specifically configured to construct two search trees, where each search tree has n layers, and corresponds to the 0 th layer to the n-1 th layer respectively; the 0 th layer of each search tree is provided with a tree node, one tree node is set as a left node, and the other tree node is set as a right node; from the 0 th layer to the n-2 th layer, each tree node of each layer is provided with two child nodes which are respectively set as a left node and a right node and are used as the tree node of the next layer; wherein, the left node represents a value of 0, and the right node represents a value of 1;
for c (x) ═ cn-1xn-1+cn-2xn-2+...+c0From c0At the beginning, according to c0The value of (c) marks two tree nodes of the 0 th layer0If the value of (1) is 0, marking a left node of the two tree nodes, and if the value of (1) is 1, marking a right node of the two tree nodes, thereby obtaining a 0 th layer of marked nodes;
according to c1If c is the value of (c), marking two child nodes of the 0 th layer marking node1If the value of (c) is 0, then the left node of the two child nodes is marked, if c is1If the value of (1) is 1, marking the right node of the two child nodes so as to obtain a layer 1 marked node;
sequentially marking each layer until a marking node of the (n-1) th layer is obtained;
if the marking node of the n-1 th layer is connected with another tree node of the n-1 th layer, judging that c (x) has an inverse element;
judging whether the connected tree nodes are left nodes or right nodes, and if the connected tree nodes are left nodes, setting en-1If it is 0, e is set for right noden-1＝1；
Judging whether the tree node of the (n-2) th layer to which the connected tree nodes belong is a left node or a right node, and if the tree node is the left node, setting en-2If it is 0, e is set for right noden-2＝1；
For each layer in turnMaking a judgment until e is set0To obtain the result of the inversion operation
Figure BDA0001493293820000101
The tree node at the 0 th level of each tree is a root node, the root node of one tree is a left root node, and the root node of the other tree is a right root node. From level 0 to level n-2, each tree node of each level has two children as tree nodes of the next level, e.g., two root nodes of level 0 have two children as tree nodes of level 1, respectively, and thus level 1 has 4 tree nodes. The tree nodes in the (n-1) th layer are leaf nodes. Each path from the root node to the leaf node represents a GF (2)n) Of (2) is used. For example, the path from the left root node, to the left of its two children nodes, until the leftmost leaf node ends (leftmost node of layer n-1) represents GF (2)n) Element (00.. 00)2。
If GF (2)n) Inversion of (a), (b), (c), (x)-1And from layer 0 to node n of layer n-1tRepresents GF (2)n) Element c (x) of (1), node n from layer 0 to layer n-1kRepresents GF (2)n) E (x) of (1), then node n of layer n-1kAnd ntAre connected. Therefore, the operation process of the inversion operation module is as follows:
first, for c (x) ═ cn-1xn-1+cn-2xn-2+...+c0Judgment c0If the value of (1) is 0 or 1, marking a left root node, otherwise marking a right root node;
then, the root node for searching the 0 th layer mark has two child nodes, and c is judged1If the value of (1) is 0 or 1, marking a left node if the value of (0) is 0, otherwise marking a right node;
marking nodes on each layer from the next to the next according to the judging method until the n-1 layer, and marking a certain leaf node;
if the marked leaf node is connected with another leaf node, c (x) has an inverse element and marks the connected leaf node;
if the leaf node is the left node, en-1If this leaf node is the right node, then e is 0n-1＝1；
If the parent node of the leaf node (i.e., the tree node to which the leaf node belongs) is the left node, en-2If the parent node of the leaf node is the right node, e is 0n-2＝1；
Then, e is calculated for each layer according to the judgment methodiUp to layer 0;
finally, the process is carried out in a batch,
Figure BDA0001493293820000111
is (x) ═ c (x)-1The operation result of (1).
The working process of the complex finite field inversion device provided by the embodiment of the present invention is described below by taking n as an example, which is 4.
The input port operand a (x) is the complex finite field GF ((2)4)2) May be expressed in the form of a polynomial:
a(x)＝ahx+al，
ah,alis a finite field GF (2)4) Of (2) is used.
The operand b (x) of the output port is the complex finite field GF ((2)4)2) May be expressed in the form of a polynomial:
b(x)＝bhx+bl，
bh,blis a finite field GF (2)4) Of (2) is used.
The clock signal clk at the input port is a single bit signal with a clock period of 20 ns.
The controller is used to schedule other components, calculate GF ((2)4)2) B (x) a (x)-1In which GF ((2))4)2) Is q (x) x2+ x +9, the procedure is as follows:
firstly, in the first clock period, an addition operation module is called to calculate s0＝ah+al，s0,ah,alIs a finite field GF (2)4) An element of (1);
calculating s by calling square operation module1＝ah 2，s1,ahIs a finite field GF (2)4) An element of (1);
calling multiplication operation module to calculate s3＝ah×al，s3,ah,alIs a finite field GF (2)4) An element of (1);
then, in the second clock cycle, calling square operation module to calculate s2＝al 2，s2,alIs a finite field GF (2)4) An element of (1);
calling multiplication operation module to calculate s4＝s1×e，s4,s1E is a finite field GF (2)4) An element of (1);
then, in the third clock cycle, calling an addition operation module to calculate s5＝s4+s3，s5,s4,s3Is a finite field GF (2)4) An element of (1);
then, in the fourth clock cycle, the addition operation module is called to calculate s6＝s5+s2，s6,s5,s2Is a finite field GF (2)4) An element of (1);
then, in the fifth clock cycle, calling an inversion operation module to calculate s7＝s6 -1，s7,s6Is a finite field GF (2)4) An element of (1);
next, in the sixth clock cycle, a multiplication module is called to calculate bl＝s0×s7，bl,s0,s7Is a finite field GF (2)4) An element of (1);
then, in the seventh clock cycle, calling multiplication operation module to calculate bh＝ah×s7，bl,ah,s7Is a finite field GF (2)4) An element of (1);
finally, b (x) bhx+blIs a (x) ═ ahx+alThe inverse of (3).
In the embodiment of the invention, inversion operation is carried out based on the search tree in the composite finite field inversion operation, compared with the finite field inverter in the prior art, the operation efficiency is effectively improved, and the method can be widely applied to the mathematical fields and the engineering fields of symmetric encryption (such as DES and AES), public key cryptography, Rainbow, TTS, UOV signature and the like.
The above description is only for the purpose of illustrating the preferred embodiments of the present invention and is not to be construed as limiting the invention, and any modifications, equivalents, improvements and the like that fall within the spirit and principle of the present invention are intended to be included therein.

Claims (6)

1.一种基于查找树的复合有限域求逆装置，其特征在于，包括控制器、输入端口、输出端口和运算器；1. a composite finite field inversion device based on search tree, is characterized in that, comprises controller, input port, output port and operator; 所述输入端口用于输入复合有限域GF((2n)2)的求逆运算数a(x)；The input port is used to input the inverse operand a(x) of the composite finite field GF((2 n ) 2 ); 所述控制器用于调用所述运算器对所述求逆运算数a(x)进行求逆运算，获得复合有限域GF((2n)2)的求逆运算结果b(x)；The controller is configured to call the operator 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 n ) 2 ); 所述运算器用于运行加法运算、乘法运算、平方运算和基于查找树的求逆运算；The operator is used to perform addition operations, multiplication operations, square operations and search tree-based inversion operations; 所述输出端口用于输出所述求逆运算结果b(x)；the output port is used for outputting the inversion operation result b(x); 所述求逆运算数a(x)的多项式表示形式为a(x)＝ahx+al；The polynomial representation of the inverse operand a(x) is a(x)= ah x+a l ; 所述求逆运算结果b(x)的多项式表示形式为b(x)＝bhx+bl；b(x)＝a(x)-1；The polynomial representation of the inversion operation result b(x) is b(x)=b h x+b l ; b(x)=a(x) −1 ; 其中，ah,al,bh,bl均为有限域GF(2n)的元素；Among them, a h , a l , b h , b l are all elements of the finite field GF(2 n ); 所述运算器包括加法运算模块、乘法运算模块、平方运算模块和求逆运算模块；The operator includes an addition operation module, a multiplication operation module, a square operation module and an inversion operation module; 所述输入端口还用于输入时钟信号；The input port is also used for inputting a clock signal; 所述控制器具体用于在第一个时钟周期，调用所述加法运算模块计算s0＝ah+al，调用所述平方运算模块计算s1＝ah 2，调用所述乘法运算模块计算s3＝ah×al；The controller is specifically configured to, in the first clock cycle, call the addition operation module to calculate s 0 =a h +a l , call the square operation module to calculate s 1 =a h 2 , and call the multiplication operation module Calculate s 3 =a h ×a l ; 在第二个时钟周期，调用所述平方运算模块计算s2＝al 2，调用所述乘法运算模块计算s4＝s1×e；In the second clock cycle, the square operation module is called to calculate s 2 =a l 2 , and the multiplication operation module is called to calculate s 4 =s 1 ×e; 在第三个时钟周期，调用所述加法运算模块计算s5＝s4+s3；In the third clock cycle, call the addition operation module to calculate s 5 =s 4 +s 3 ; 在第四个时钟周期，调用所述加法运算模块计算s6＝s5+s2；In the fourth clock cycle, call the addition operation module to calculate s 6 =s 5 +s 2 ; 在第五个时钟周期，调用所述求逆运算模块计算s7＝s6 -1；In the fifth clock cycle, call the inversion operation module to calculate s 7 =s 6 −1 ; 在第六个时钟周期，调用所述乘法运算模块计算bl＝s0×s7；In the sixth clock cycle, call the multiplication operation module to calculate b l =s 0 ×s 7 ; 在第七个时钟周期，调用所述乘法运算模块计算bh＝ah×s7，进而计算b(x)＝bhx+bl；In the seventh clock cycle, call the multiplication operation module to calculate b h =a h ×s 7 , and then calculate b(x)=b h x+b l ; 其中，s0,ah,s1,al,s2,s3,s4,s5,s6,s7,bl,bh均为有限域GF(2n)的元素，e为有限域GF(2n)的常数。Among them, s 0 , a h , s 1 , a l , s 2 , s 3 , s 4 , s 5 , s 6 , s 7 , b l , b h are all elements of the finite field GF(2 n ), e is a constant of the finite field GF(2 n ). 2.如权利要求1所述的基于查找树的复合有限域求逆装置，其特征在于，所述加法运算模块包括n个异或逻辑门，用于针对有限域GF(2n)的两个已知元素c(x)和d(x)，计算ei＝ci+di，进而获得加法运算结果
Figure FDA0002969506490000021
2. The complex finite field inversion device based on a search tree according to claim 1, wherein the addition operation module comprises n XOR logic gates for two of the finite field GF(2 n ) Knowing the elements c(x) and d(x), calculate e i = ci +d i , and then obtain the addition result
Figure FDA0002969506490000021
 其中，c(x)＝cn-1xn-1+cn-2xn-2+...+c0，d(x)＝dn-1xn-1+dn-2xn-2+...+d0，e(x)＝en-1xn-1+en-2xn-2+...+e0，i＝0,1,...,n-1，n≥1，+是有限域GF(2n)的加法运算，cn-1,cn-2,...,c0,dn-1,dn-2,...,d0,en-1,en-2,...,e0均为有限域GF(2n)的元素。where c(x)=c n-1 x n-1 +c n-2 x n-2 +...+c 0 , d(x)=d n-1 x n-1 +d n-2 x n-2 +...+d 0 , e(x)=e n-1 x n-1 +e n-2 x n-2 +...+e 0 , i=0,1,.. .,n-1, n≥1, + is the addition operation of finite field GF(2 n ), c n-1 ,c n-2 ,...,c 0 ,d n-1 ,d n-2 , ...,d 0 , e n-1 , e n-2 , ..., e 0 are all elements of the finite field GF(2 n ). 3.如权利要求1所述的基于查找树的复合有限域求逆装置，其特征在于，所述乘法运算模块包括多个与逻辑门和异或逻辑门，用于针对有限域GF(2n)的两个已知元素c(x)和d(x)，计算
Figure FDA0002969506490000022
和
Figure FDA0002969506490000023
进而计算
Figure FDA0002969506490000024
获得乘法运算结果
Figure FDA0002969506490000025
3. The complex finite field inversion device based on a search tree as claimed in claim 1, wherein the multiplication operation module comprises a plurality of AND logic gates and XOR logic gates, which are used for the finite field GF(2 n ) for the two known elements c(x) and d(x), compute
Figure FDA0002969506490000022
and
Figure FDA0002969506490000023
and then calculate
Figure FDA0002969506490000024
get multiplication result
Figure FDA0002969506490000025
 其中，c(x)＝cn-1xn-1+cn-2xn-2+...+c0，d(x)＝dn-1xn-1+dn-2xn-2+...+d0，e(x)＝en-1xn-1+en-2xn-2+...+e0，mod为模运算，p(x)＝xn+pn-1xn-1+...+1为有限域GF(2n)的不可约多项式，pn-1,pn-2,...,p1,vjl,cl,dk,Sj,ei,vji均为有限域GF(2n)的元素。where c(x)=c n-1 x n-1 +c n-2 x n-2 +...+c 0 , d(x)=d n-1 x n-1 +d n-2 x n-2 +...+d 0 , e(x)=e n-1 x n-1 +e n-2 x n-2 +...+e 0 , mod is the modulo operation, p(x )=x n +p n-1 x n-1 +...+1 is an irreducible polynomial of finite field GF(2 n ), p n-1 ,p n-2 ,...,p 1 ,v jl , c l , d k , S j , e i , v ji are all elements of finite field GF(2 n ). 4.如权利要求1所述的基于查找树的复合有限域求逆装置，其特征在于，所述平方运算模块包括多个与逻辑门和异或逻辑门，用于针对有限域GF(2n)的已知元素c(x)，计算
Figure FDA0002969506490000031
进而计算
Figure FDA0002969506490000032
获得平方运算结果
Figure FDA0002969506490000033
4. The complex finite field inversion device based on a search tree according to claim 1, wherein the square operation module comprises a plurality of AND logic gates and XOR logic gates, which are used for the finite field GF(2 n ) of the known elements c(x), calculate
Figure FDA0002969506490000031
and then calculate
Figure FDA0002969506490000032
get the result of the square operation
Figure FDA0002969506490000033
 其中，c(x)＝cn-1xn-1+cn-2xn-2+...+c0，e(x)＝en-1xn-1+en-2xn-2+...+e0，mod为模运算，p(x)＝xn+pn-1xn-1+...+1为有限域GF(2n)的不可约多项式，pn-1,pn-2,...,p1,vjl,cl,ck,Sj,ei,vji均为有限域GF(2n)的元素。where c(x)=c n-1 x n-1 +c n-2 x n-2 +...+c 0 , e(x)=e n-1 x n-1 +e n-2 x n-2 +...+e 0 , mod is the modulo operation, p(x)=x n +p n-1 x n-1 +...+1 is the irreducible of the finite field GF(2 n ) Polynomials, p n-1 , p n-2 ,...,p 1 , v jl , c l , c k , S j , e i , v ji are all elements of the finite field GF(2 n ). 5.如权利要求1所述的基于查找树的复合有限域求逆装置，其特征在于，所述求逆运算模块包括多个与逻辑门和异或逻辑门，用于针对有限域GF(2n)的已知元素c(x)，基于查找树计算e(x)＝c(x)-1；5. The complex finite field inversion device based on a search tree as claimed in claim 1, wherein the inversion operation module comprises a plurality of AND logic gates and XOR logic gates, which are used for the finite field GF(2 n ) of known elements c(x), based on the search tree calculation e(x)=c(x) −1 ; 其中，c(x)＝cn-1xn-1+cn-2xn-2+...+c0，e(x)＝en-1xn-1+en-2xn-2+...+e0，cn-1,cn-2,...,c0,en-1,en-2,...,e0均为有限域GF(2n)的元素。where c(x)=c n-1 x n-1 +c n-2 x n-2 +...+c 0 , e(x)=e n-1 x n-1 +e n-2 x n-2 +...+e 0 , c n-1 ,c n-2 ,...,c 0 ,e n-1 ,e n-2 ,...,e 0 are all finite fields GF (2 n ) elements. 6.如权利要求5所述的基于查找树的复合有限域求逆装置，其特征在于，所述求逆运算模块具体用于构建两颗查找树，每颗查找树具有n层，分别对应第0层至第n-1层；每棵查找树的第0层分别具有一个树节点，一个设为左节点，另一个设为右节点；从第0层到第n-2层，每一层的每个树节点具有两个子节点，分别设为左节点和右节点并作为下一层的树节点；其中，左节点代表数值0，右节点代表数值1；6. the composite finite field inversion device based on search tree as claimed in claim 5, is characterized in that, described inversion operation module is specifically used for constructing two search trees, and each search tree has n layers, corresponding to the first Level 0 to level n-1; the level 0 of each search tree has one tree node, one is set as the left node, and the other is set as the right node; from level 0 to level n-2, each level Each tree node of has two child nodes, which are set as the left node and the right node respectively and serve as the tree node of the next layer; wherein, the left node represents the value 0, and the right node represents the value 1; 对于c(x)＝cn-1xn-1+cn-2xn-2+...+c0，从c0开始，根据c0的值对第0层的两个树节点进行标记，若c0的值为0，则标记两个树节点中的左节点，若为1，则标记两个树节点中的右节点，从而获得第0层标记节点；For c(x)=c n-1 x n-1 +c n-2 x n-2 +...+c 0 , starting from c 0 , pair the two tree nodes at level 0 according to the value of c 0 Mark, if the value of c 0 is 0, mark the left node in the two tree nodes, if it is 1, mark the right node in the two tree nodes, so as to obtain the 0th layer marked node; 根据c1的值对第0层标记节点所具有的两个子节点进行标记，若c1的值为0，则标记两个子节点中的左节点，若c1的值为1，则标记两个子节点中的右节点，从而获得第1层标记节点；According to the value of c 1 , mark the two child nodes of the mark node at level 0. If the value of c 1 is 0, mark the left node of the two child nodes. If the value of c 1 is 1, mark the two child nodes. The right node in the node, thereby obtaining the 1st layer marked node; 依次对每一层进行标记，直到获得第n-1层标记节点；Mark each layer in turn until the n-1th layer marked node is obtained; 若所述第n-1层标记节点与第n-1层的另一个树节点相连，则判定c(x)有逆元；If the mark node of the n-1th layer is connected to another tree node of the n-1th layer, it is determined that c(x) has an inverse element; 判断相连的树节点是左节点还是右节点，若是左节点则设置en-1＝0，若是右节点则设置en-1＝1；Determine whether the connected tree node is a left node or a right node, if it is a left node, set e n-1 =0, if it is a right node, set e n-1 =1; 判断相连的树节点所属的第n-2层的树节点是左节点还是右节点，若是左节点则设置en-2＝0，若是右节点则设置en-2＝1；Determine whether the tree node of the n-2th layer to which the connected tree node belongs is a left node or a right node, if it is a left node, set e n-2 =0, if it is a right node, set e n-2 =1; 依次对每一层进行判断，直到设置出e0的值，从而获得求逆运算结果
Figure FDA0002969506490000041
Each layer is judged in turn until the value of e 0 is set, so as to obtain the result of the inversion operation
Figure FDA0002969506490000041
CN201711259841.4A 2017-12-04 2017-12-04 A complex finite field inversion device based on search tree Expired - Fee Related CN107885486B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201711259841.4A CN107885486B (en) 2017-12-04 2017-12-04 A complex finite field inversion device based on search tree

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201711259841.4A CN107885486B (en) 2017-12-04 2017-12-04 A complex finite field inversion device based on search tree

Publications (2)

Publication Number Publication Date
CN107885486A CN107885486A (en) 2018-04-06
CN107885486B true CN107885486B (en) 2021-09-07

Family

ID=61772960

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201711259841.4A Expired - Fee Related CN107885486B (en) 2017-12-04 2017-12-04 A complex finite field inversion device based on search tree

Country Status (1)

Country Link
CN (1) CN107885486B (en)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108874365A (en) * 2018-06-29 2018-11-23 深圳职业技术学院 A kind of finite field inverter and finite field inversions method based on irreducible trinomial
CN108897526B (en) * 2018-06-29 2022-10-21 深圳职业技术学院 Compound finite field inverter based on multiple square operations and inversion method thereof
CN109656513B (en) * 2018-12-07 2022-11-11 深圳职业技术学院 A Composite Finite Field Division Device Based on Cardiac Model

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101572602A (en) * 2008-04-28 2009-11-04 陈婧 Finite field inversion method and device based on hardware design
CN101630244A (en) * 2009-07-28 2010-01-20 哈尔滨工业大学深圳研究生院 System and method of double-scalar multiplication of streamlined elliptic curve
CN102902510A (en) * 2012-08-03 2013-01-30 华南理工大学 Galois field inversion device
CN106909339A (en) * 2017-02-22 2017-06-30 深圳职业技术学院 A kind of Galois field multiplier based on binary tree structure

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4905161B2 (en) * 2007-01-31 2012-03-28 富士通株式会社 RAID device and data restoration device using Galois field
CN104639282B (en) * 2013-11-14 2018-09-11 杭州海康威视数字技术股份有限公司 RS interpretation methods and its device in communication system

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101572602A (en) * 2008-04-28 2009-11-04 陈婧 Finite field inversion method and device based on hardware design
CN101630244A (en) * 2009-07-28 2010-01-20 哈尔滨工业大学深圳研究生院 System and method of double-scalar multiplication of streamlined elliptic curve
CN102902510A (en) * 2012-08-03 2013-01-30 华南理工大学 Galois field inversion device
CN106909339A (en) * 2017-02-22 2017-06-30 深圳职业技术学院 A kind of Galois field multiplier based on binary tree structure

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
"有限域运算和多变量公钥密码硬件的优化和设计";易海博;《中国博士学位论文全文数据库》;20150815(第8期);I136-11 *

Also Published As

Publication number Publication date
CN107885486A (en) 2018-04-06

Similar Documents

Publication Publication Date Title
CN110351087B (en) Pipelined Montgomery modular multiplication operation method
JP5312318B2 (en) Method and device for generating pseudo-random strings
CN107885486B (en) A complex finite field inversion device based on search tree
CN112491543B (en) IC card decryption method based on improved Montgomery modular exponentiation circuit
CN103942028A (en) Large integer multiplication method and device applied to password technology
Costello et al. A brief discussion on selecting new elliptic curves
Noor et al. Resource shared galois field computation for energy efficient AES/CRC in IoT applications
CN109933304B (en) Rapid Montgomery modular multiplier operation optimization method suitable for national secret sm2p256v1 algorithm
Nawari et al. Fpga based implementation of elliptic curve cryptography
Vijayakumar et al. Comparative study of hyperelliptic curve cryptosystem over prime field and its survey
CN108008934B (en) A lookup table based complex finite field inversion device
El-Razouk et al. New Bit-Level Serial GF (2^ m) Multiplication Using Polynomial Basis
Ay et al. Constant-time hardware computation of elliptic curve scalar multiplication around the 128 bit security level
CN106909339A (en) A kind of Galois field multiplier based on binary tree structure
Lee et al. Efficient $ M $-ary exponentiation over $ GF (2^{m}) $ using subquadratic KA-based three-operand Montgomery multiplier
CN108897526B (en) Compound finite field inverter based on multiple square operations and inversion method thereof
CN206332680U (en) Multivariate digital signature device
CN103942027A (en) Reconfigurable rapid parallel multiplier
CN108228138A (en) A kind of method of special domain Fast Modular Multiplication in SIDH
CN108268243B (en) Composite domain multiplication device based on search
He et al. A Universal Single and Double Point Multiplications Architecture for ECDSA Based on Differential Addition Chains
CN108874367B (en) A Composite Finite Field Inverter Based on Power Operation and Its Inverting Method
Nirmal et al. Novel Delay Efficient Approach for Vedic Multiplier with Generic Adder Module
Lin et al. An efficient algorithm for computing modular division over GF (2 m) in elliptic curve cryptography
CN102955682A (en) Modular multiplier

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20210907

CF01 Termination of patent right due to non-payment of annual fee