CN105681033A - Out-of-order encryption device for multivariable quadratic equation - Google Patents

Abstract

The invention discloses an out-of-order encryption device for a multivariable quadratic equation. The out-of-order encryption device comprises a monomial subscript generator, used for generating n(n+1)/2 monomial subscripts (i, j) out of order when computing each multivariable quadratic equation, wherein the i is greater than or equal to 1, the j is greater than or equal to i, and the n is greater than or equal to j; a monomial multiplying unit, used for sequentially computing n monomials aijxixj of the multivariable quadratic equations according to the generation sequence of the monomial subscripts (i, j), wherein aij is plaintext, and xi is a secret key, or aij is the secrete key, and xi is the plaintext; and an accumulator, used for sequentially accumulating the n monomials aijxixj and then writing into a register to obtain ciphertext. By using the out-of-order encryption device provided by the invention, the security of the secret key can be effectively improved, and the side channel attack can be resisted.

Description

An out-of-order encryption device for multi-variable quadratic equations

technical field

The invention relates to the technical field of information security, in particular to an out-of-order encryption device for multivariable quadratic equations.

Background technique

The MQ problem (MQproblem) refers to the problem of solving a set of multivariable quadratic equations on a finite field. Generally speaking, the problem is NP difficult. The MQ problem is a very promising research problem in cryptography. A large number of cryptographic algorithms have been designed based on the MQ problem, including multivariate public key cryptography (MPKC), stream cipher algorithm QUAD, and identity authentication algorithms. Among them, the multivariate quadratic equation can be expressed as follows:

Q(x)＝∑ _{1≤i≤j≤n} α _ij x _i x _j +∑ _1≤i≤n β _ij x _i +γ

Side channel attack (side channel attack referred to as SCA), also known as side channel attack, is a method of attacking encryption equipment for side channel information leakage such as time consumption, power consumption or electromagnetic radiation during the operation of encryption electronic equipment. . This attack method brings serious threats to cryptographic devices.

However, none of the prior art considers the side-channel leakage problem of multivariable quadratic equations. When encrypting, each monomial in multiple multivariate quadratic equations is directly calculated in the same order, and then the calculation results of each monomial are accumulated and temporarily stored in the register. By analyzing the power consumption of the corresponding register storage operation of each multivariate quadratic equation, the attacker can obtain the key or plaintext information (a _ij or x _j information), and then break the cryptographic algorithm.

Contents of the invention

The embodiment of the present invention proposes a multi-variable quadratic equation out-of-sequence encryption device, which can effectively improve the security of keys and resist sidewalk attacks.

An embodiment of the present invention provides an out-of-order encryption device for multivariable quadratic equations, including:

A monomial subscript generator, used to generate n(n+1)/2 monomial subscript values (i,j) out of order when calculating each multivariate quadratic equation; 1≤i≤j≤n;

A monomial multiplier, used to sequentially calculate n monomials α _ij x _i x _j of the multivariate quadratic equation in the order in which the monomial subscript values (i, j) are generated; wherein, α _ij is plaintext, and x _i is key, or, α _ij is the key, _xi is the plaintext; and,

The accumulator is used for accumulating the n monomials α _ij x _i x _j in sequence and writing them into the register to obtain the ciphertext.

Further, the monomial subscript generator uses an out-of-order generation method to generate a monomial subscript; the out-of-order generation method specifically includes:

S11. When calculating each multivariate quadratic equation, randomly generate the monomial subscript initial value i=i _s , j=j _s ; 1≤i _s ≤j _s ≤n;

S12, judging whether j is n, if so, then execute step S13, if not, then execute step S14;

S13, judging whether i is n, if so, then execute step S15, if not, then execute step S16;

S14. Assign j as j+1, and continue to execute step S17;

S15. Assign i and j as 1, and continue to execute step S17;

S16. Assign i as i+1, assign j as i+1, and continue to execute step S17;

S17. Judging whether i is i _s and j is j _s -1, if yes, then the monomial subscript value in the multivariate quadratic equation is generated, if not, continue to step S12.

Further, the accumulator is specifically used to sequentially accumulate each monomial α _ij x _i x _j into the register according to the calculation sequence of the monomial α _ij x _i x _j , and the accumulated value in the register is the ciphertext .

Further, the ciphertext corresponding to each multivariate quadratic equation is $Q\left(x\right)={\&Sigma;}_{j_{\mathrm{the\; s}}\&le;j\&le;\mathrm{no}}{\mathrm{\&alpha;}}_{i_{\mathrm{the\; s}}j}{x}_{i_{\mathrm{the\; s}}}{x}_j+{\&Sigma;}_{i_{\mathrm{the\; s}}<i\&le;j\&le;\mathrm{no}}{\mathrm{\&alpha;}}_{ij}{x}_i{x}_j+{\&Sigma;}_{\begin{array}{c}1\&le;i\&le;i_{\mathrm{the\; s}},\\ i\&le;j\&le;\mathrm{no}\end{array}}{\mathrm{\&alpha;}}_{ij}{x}_i{x}_j+{\&Sigma;}_{i_{\mathrm{the\; s}}\&le;j<j_{\mathrm{the\; s}}}{\mathrm{\&alpha;}}_{i_{\mathrm{the\; s}}j}{x}_{i_{\mathrm{the\; s}}}{x}_j.$

Implementing the embodiment of the present invention has the following beneficial effects:

The out-of-order encryption device for multivariate quadratic equations provided by the embodiments of the present invention can generate n(n+1)/2 subscript values in a way of out-of-order generation of monomial subscript values when calculating each multivariate quadratic equation The monomial subscript value (i, j), and according to the generation sequence of the monomial subscript value (i, j), calculate n(n+1)/2 monomial formulas α _ij x _i x _j sequentially, so that different multivariate quadratic The calculation order of the monomials in the equation is different. Finally, each monomial in the multivariable quadratic equation is accumulated in the register to realize the encryption of the key. By disrupting the calculation order of each monomial, the same key information can be used in the appear at different times, thereby resisting sidewalk attacks and effectively improving the security of the key.

Description of drawings

Fig. 1 is the structure schematic diagram of the first embodiment of the out-of-order encryption device of multivariable quadratic equation provided by the present invention;

Fig. 2 is a schematic flow chart of an embodiment of a random order generation method in a multivariable quadratic equation random order encryption device provided by the present invention;

Fig. 3 is a structural schematic diagram of a second embodiment of the out-of-order encryption device for multivariable quadratic equations provided by the present invention.

detailed description

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

Referring to Fig. 1, it is a schematic structural diagram of an embodiment of an out-of-order encryption device for multivariate quadratic equations provided by the present invention, including:

Monomial subscript generator 1, used to generate n(n+1)/2 monomial subscript values (i, j) out of order when calculating each multivariate quadratic equation; 1≤i≤j≤n;

Monomial multiplier 2, used to sequentially calculate n monomials α _ij x _i x _j of the multivariate quadratic equation in the order in which the monomial subscript values (i, j) are generated; wherein, α _ij is plaintext, x _i is the key, or, α _ij is the key, and _xi is the plaintext; and,

The accumulator 3 is used for sequentially accumulating the n monomials α _ij x _i x _j and writing them into registers to obtain ciphertext.

It should be noted that computing a multivariate quadratic system with r equations over a finite field $\left\{\begin{array}{c}{Q}_1\left(x\right)={\mathrm{\&Sigma;}}_{1\&le;i\&le;j\&le;\mathrm{no}}{\mathrm{\&alpha;}}_{ij}^1{x}_i{x}_j+{\mathrm{\&gamma;}}^1\\ ......\\ Q_r\left(x\right)={\mathrm{\&Sigma;}}_{1\&le;i\&le;j\&le;\mathrm{no}}{\mathrm{\&alpha;}}_{ij}^r{x}_i{x}_j+{\mathrm{\&gamma;}}^r\end{array}\right.$ To realize the encryption of the key and plaintext. Wherein, if α _ij is the plaintext, then _xi is the key; if α _ij is the key, then _xi is the plaintext. In this embodiment, when calculating each multivariate quadratic equation in the multivariate quadratic equation system, the calculation order of each monomial α _ij x _i x _j in each multivariate quadratic equation is randomly disrupted, so that The order of computation of the monomial α _ij x _i x _j in different multivariate quadratic equations varies.

When calculating each multivariate quadratic equation separately, the monomial subscript generator 1 randomly generates n(n+1)/2 monomial subscript values (i, j), that is, the monomial subscript of the multivariate quadratic equation The values are reordered so that the order of the monomial subscript values differs for each multivariate quadratic equation. Among them, n(n+1)/2 monomial subscript values (i, j) cover all monomial subscript values in the multivariate quadratic equation. The monomial multiplier 2 calculates each monomial α _ij x _i x _j in accordance with the generation order of the respective monomial subscript values of each multivariate quadratic equation. When the monomial multiplier 2 calculates a monomial, the accumulator 3 accumulates the monomial into the register, and after accumulating all the monomials, the ciphertext corresponding to the multivariate quadratic equation can be obtained. The calculation results of the r equations in the multivariate quadratic equation group are correspondingly written into the r registers respectively.

There are n(n+1)/2 monomials in each multivariate quadratic equation. After the calculation order of the monomials is disrupted, if an attacker wants to obtain the key or plaintext information by analyzing the power consumption of r registers, he needs Consider A(n(n+1)/2,n(n+1)/2)=(n(n+1)/2)! As a result, it is difficult to realize the attack on the side channel.

It should be noted that the multivariable quadratic equation out-of-sequence encryption method provided by the embodiment of the present invention is generally applied in a smart card, and the key is encrypted by the algorithm of the multivariable quadratic equation and then stored in the memory of the smart card. Wherein, the calculation order of each monomial in each multivariable quadratic equation is different, and the order of accumulating into the memory is also different, so as to prevent an attacker from obtaining key information by analyzing the power consumption of the memory.

Further, the monomial subscript generator 1 generates a monomial subscript using an out-of-order generation method. As shown in Figure 2, the out-of-order generation method specifically includes:

S11. When calculating each multivariate quadratic equation, randomly generate the monomial subscript initial value i=i _s , j=j _s ; 1≤i _s ≤j _s ≤n;

S12, judging whether j is n, if so, then execute step S13, if not, then execute step S14;

S13, judging whether i is n, if so, then execute step S15, if not, then execute step S16;

S14. Assign j as j+1, and continue to execute step S17;

S15. Assign i and j as 1, and continue to execute step S17;

S16. Assign i as i+1, assign j as i+1, and continue to execute step S17;

S17. Judging whether i is i _s and j is j _s -1, if yes, then the monomial subscript value in the multivariate quadratic equation is generated, if not, continue to step S12.

It should be noted that the effect of resisting side-channel attacks is best by completely disrupting each monomial in each multivariate quadratic equation. At the same time, in order to reduce calculation time and storage overhead and avoid consuming a large amount of resources, only the initial calculation order in each multivariate quadratic equation is disrupted, so that each multivariate quadratic equation is calculated from a different initial monomial, and then It can still be calculated in order. For example, the monomial subscript generator 1 randomly generates the monomial initial subscript value (2,3) for the first multivariate quadratic equation, then the first multivariate quadratic equation starts from the monomial α ₂ x ₃₂ x ₃ in order Calculate to the monomial α _n x _nn x _n , then calculate from the monomial α ₁ x ₁₁ x ₁ to the monomial α ₂ x ₂₂ x ₂ ; randomly generate the initial subscript value of the monomial for the second multivariate quadratic equation (6,9 ), then the first multivariate quadratic equation is calculated sequentially from the monomial α ₆₉ x ₆ x ₉ to the monomial α _n x _nn x _n , and then from the monomial α ₁ x ₁₁ x ₁ to the monomial α ₆₈ x ₆ x ₈ etc. This out-of-order generation method makes the same operation of the key and plaintext in different multivariate quadratic equations hidden in different clock cycles, which cannot be observed through the characteristics of the power consumption curve of the memory, and is simple and efficient, which is beneficial to software Hardware efficient implementation.

Further, the accumulator 3 is specifically used to sequentially accumulate each monomial α _ij x _i x _j into the register according to the calculation order of the monomial α _ij x _i x _j , and the accumulated value in the register is the encrypted arts.

When calculating each multivariate quadratic equation, according to the calculation order of the monomial α _ij x _i x _j , each time a monomial α _ij x _i x _j is calculated, the monomial is accumulated into the register. Wherein, monomials in different multivariable quadratic equations are stored in different registers.

Further, the ciphertext corresponding to each multivariate quadratic equation is $Q\left(x\right)={\&Sigma;}_{j_{\mathrm{the\; s}}\&le;j\&le;\mathrm{no}}{\mathrm{\&alpha;}}_{i_{\mathrm{the\; s}}j}{x}_{i_{\mathrm{the\; s}}}{x}_j+{\&Sigma;}_{i_{\mathrm{the\; s}}<i\&le;j\&le;\mathrm{no}}{\mathrm{\&alpha;}}_{ij}{x}_i{x}_j+{\&Sigma;}_{\begin{array}{c}1\&le;i\&le;i_{\mathrm{the\; s}},\\ i\&le;j\&le;\mathrm{no}\end{array}}{\mathrm{\&alpha;}}_{ij}{x}_i{x}_j+{\&Sigma;}_{i_{\mathrm{the\; s}}\&le;j<j_{\mathrm{the\; s}}}{\mathrm{\&alpha;}}_{i_{\mathrm{the\; s}}j}{x}_{i_{\mathrm{the\; s}}}{x}_j.$

Among them, each multivariate quadratic equation randomly generates different monomial subscript initial values (i _s , j _s ), and then each calculates according to the above formula to obtain the ciphertext.

Referring to FIG. 3 , it is a schematic structural diagram of a second embodiment of the out-of-order encryption device for multivariable quadratic equations provided by the present invention, including out-of-order subscript controller 31, polynomial variable register 32, multiplier 33, and multiplier 34 , adder 35, register 36 and judger 37. Wherein, the value stored in the polynomial variable register 32 may be a key or plain text. The device for encrypting multivariate quadratic equations provided by the embodiment of the present invention is used to implement encryption of multivariate quadratic equations, wherein the multivariate quadratic equations have r multivariate quadratic equations. When calculating each multivariate quadratic equation, the out-of-sequence subscript controller 31 randomly generates monomial subscript values i and j, wherein the randomly generated initial monomial subscript values are i _s and j _s . The polynomial variable register 32 outputs variables x _i and x _j according to the monomial index values generated by the out-of-sequence index controller 31 . The multiplier 33 receives the variables x _i and x _j and multiplies them to output, and the multiplier 34 multiplies the value output by the multiplier 33 with the coefficient α _ij and outputs it to obtain the monomial, and then the monomial is accumulated to the register by the adder 35 36 in. Determiner 37 judges whether the subscript of this monomial is (i _s , j _s -1) after accumulating subscript is (i, j) monomial in register 36, if not, then judges as 0, and will be in register 36 The value and the next monomial are accumulated and written into the register 36; if not, the judgment is 1, and the value in the output register 36 is the ciphertext.

The out-of-order encryption device for multivariate quadratic equations provided by the embodiments of the present invention can generate n(n+1)/2 subscript values in a way of out-of-order generation of monomial subscript values when calculating each multivariate quadratic equation The monomial subscript value (i, j), and according to the generation sequence of the monomial subscript value (i, j), calculate n(n+1)/2 monomial formulas α _ij x _i x _j sequentially, so that different multivariate quadratic The calculation order of the monomials in the equation is different. Finally, each monomial in the multivariable quadratic equation is accumulated in the register to realize the encryption of the key. By disrupting the calculation order of each monomial, the same key information can be used in the appear at different times, thereby resisting sidewalk attacks and effectively improving the security of the key.

The above description is a preferred embodiment of the present invention, and it should be pointed out that for those skilled in the art, without departing from the principle of the present invention, some improvements and modifications can also be made, and these improvements and modifications are also considered Be the protection scope of the present invention.

Claims (4)

1. the random sequence encryption device of a multivariate quadratic equation, it is characterised in that, comprising:

Monomial subscript maker, for when calculating each multivariate quadratic equation, random sequence generates n (n+1)/2 monomial subscript value (i, j); 1≤i≤j≤n;

Monomial multiplier, for the order generated according to monomial subscript value (i, j), calculates n monomial α of described multivariate quadratic equation successively_ijx_ix_j; Wherein, α_ijFor plaintext, x_iFor key, or, α_ijFor key, x_iFor expressly; And,

Totalizer, for by described n monomial α_ijx_ix_jIt is written in register after adding up successively, obtains ciphertext.

2. the random sequence encryption device of multivariate quadratic equation as claimed in claim 1, it is characterised in that, described monomial subscript maker adopts random sequence generation method to generate monomial subscript; Described random sequence generation method specifically comprises:

S11, calculate each multivariate quadratic equation time, stochastic generation monomial subscript initial value i=i_s, j=j_s; 1≤i_s≤j_s≤ n;

S12, whether be n, if then performing step S13, if not, then perform step S14 if judging j;

S13, whether be n, if then performing step S15, if not, then perform step S16 if judging i;

S14, it is j+1 by j assignment, and continues to perform step S17;

S15, it is 1 by equal for i and j assignment, and continues to perform step S17;

S16, it is i+1 by i assignment, it is i+1 by j assignment, and continue to perform step S17;

Whether S17, to judge i be i_s, and whether j be j_s-1, if then in described multivariate quadratic equation, monomial subscript value generates complete, if not, then continue to perform step S12.

3. the random sequence encryption device of multivariate quadratic equation as claimed in claim 1, it is characterised in that, described totalizer is specifically for according to monomial α_ijx_ix_jCalculating order, successively by each monomial α_ijx_ix_jBeing added in register, the value after cumulative in described register is ciphertext.

4. the random sequence encryption device of multivariate quadratic equation as claimed in claim 2, it is characterised in that, the described corresponding ciphertext of each multivariate quadratic equation is $Q\left(x\right)={{\mathrm{\&Sigma;}}_j}_{s\&le;j\&le;n}{\mathrm{\&alpha;}}_{i_{s}j}{x}_{i_s}{x}_j+{\mathrm{\&Sigma;}}_{i_s<i\&le;j\&le;n}{\mathrm{\&alpha;}}_{ij}{x}_i{x}_j+{\mathrm{\&Sigma;}}_{\underset{i\&le;j\&le;n}{1\&le;i\&le;i_s,}}{\mathrm{\&alpha;}}_{ij}{x}_i{x}_j+{\mathrm{\&Sigma;}}_{i_s\&le;j<j_s}{\mathrm{\&alpha;}}_{i_{s}j}{x}_{i_s}{x}_j.$