CN111339577B - A construction method of S-box with excellent DPA resistance - Google Patents

Abstract

The invention discloses a construction method of an S box with excellent DPA resistance, which relates to the technical field of information security, can obtain the S box with excellent DPA resistance, can also be used for improving the DPA resistance of the existing S box, and simultaneously can retain other important cryptology properties such as nonlinearity, algebraic times, difference consistency, absolute value indexes and the like. By contrast, the S box obtained by the method has the DPA resistance obviously superior to that of the existing practical S box, and other various important cryptology properties are the same, so that the S box has stronger safety and practicability.

Description

A construction method of S-box with excellent DPA resistance

technical field

The invention relates to the technical field of information security, in particular to a construction method of an S-box with excellent DPA resistance.

Background technique

The S-box is the only nonlinear component in the block cipher, and its cryptographic properties directly affect the security of the related cryptosystem. Therefore, the S-box plays a very important role in symmetric cryptography. The defense against various attack methods starts with constructing S-boxes with good cryptographic properties, such as nonlinearity, differential consistency, algebraic times, and absolute value indicators. A sufficiently secure S-box should have high nonlinearity, not low algebraic degree, low differential consistency, low absolute value index, etc.

In 1996, side-channel attacks, proposed by Kocher, pose a serious threat to the security of physical encryption devices. Among the types of side channel attacks, Differential Power Analysis (DPA) is one of the most effective attack methods. Compared with traditional attack methods, such as linear attacks, algebraic attacks, differential attacks, etc., this attack method has a very powerful attack efficiency. It only needs a little physical information to extract the key information, thereby successfully breaking an encryption system. . Especially the widely used AES, the S-box adopted by it is very poor in resisting the DPA attack. Therefore, in recent years, many researchers have been exploring how to construct an S-box with excellent DPA resistance, thereby improving the DPA resistance of related cryptographic devices at a small cost. The transparency order is a cryptographic property that has been proven to be an effective measure of S-box DPA resistance. In recent years, the S box obtained by DPA resistance has been studied, and its DPA resistance has been greatly improved compared to AES. However, the important cryptographic properties of the S-box obtained by these technical means, such as nonlinearity, differential consistency, absolute value index, etc., cannot meet the requirements of security and practicability.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to overcome the deficiencies of the prior art and provide a construction method of an S-box with excellent DPA resistance. The academic properties also meet the safety requirements and practicality requirements.

The present invention adopts the following technical solutions for solving the above-mentioned technical problems:

A method for constructing an S-box with excellent DPA resistance proposed according to the present invention comprises the following steps:

Step 1. Given an n-bit input and balanced S box F, F is used as the initial input of the iterative construction process, and F is put into the set SF; the iterative construction process is step 2-step 7;

Step 2. Generate a candidate pool according to the truth table of the input S box F, and the candidate pool contains all the bit positions that can be reversed;

Step 3. Take b elements from the candidate pool, these b elements are b bit positions; then perform a bit inversion operation at the b bit positions of the S box to generate a new S box;

The b elements taken out need to meet the following requirements: 1) b=2k, k=1,2,..., ^2n-1 ; 2) the same component function belonging to the S box; 3) the bits corresponding to these b elements A vector of bits with a Hamming weight of ^2b-1 ;

Step 4. Repeat the process of Step 3 until the elements in the candidate pool are empty, and generate all new S boxes associated with F;

Step 5. For each newly generated S box, calculate the value of its loss function, and put the S box and the value of the corresponding loss function into the list L;

Step 6. Determine whether the list L is empty. If L is empty, increase the value of b, and at the same time, b meets the requirements 1), 2) and 3) in step 3, and execute steps 3-5; if L is not If it is empty, select an S-box with the smallest loss function value from the list L;

Step 7. Determine whether the S box selected in step 6 exists in the set SF:

If so, delete the S box and its corresponding loss function value from the list L, and perform step 6;

If not, judge whether the S-box meets the preset security requirements: if so, output the S-box and terminate the iterative construction process; if not, put the S-box into the set SF, and put the S-box into the set SF The box is used as the input S box of the next iterative construction process, that is, the S box is used as the input S box in step 2; and steps 2-7 are executed.

As a further optimization scheme for the construction method of the S-box with excellent DPA resistance according to the present invention, the loss function in step 5 is:

为二元域上的n维向量空间，

为二元域上的非零n维向量空间，W_F(c,b)为S盒关于向量c,b的Walsh谱值，b、β为二元域上的n维向量，c、α为二元域上非零n维向量，R为常数，σ(α,β)为S盒关于向量α,β的差分谱值，N₄(σ(α,β))为判断σ(α,β)是否大于4的函数，τ_F为S盒的透明阶。where n represents that the S box is n input bits,

is an n-dimensional vector space on a binary field,

is a non-zero n-dimensional vector space on the binary field, W _F (c,b) is the Walsh spectral value of the S box about the vector c, b, b, β are the n-dimensional vectors on the binary field, c, α are A non-zero n-dimensional vector on the binary field, R is a constant, σ(α, β) is the difference spectrum value of the S box with respect to the vectors α, β, N ₄ (σ(α, β)) is the judgment σ(α, β) ) is a function of whether it is greater than 4, and τ _F is the transparency order of the S-box.

As a further optimization scheme of the construction method of the S-box with excellent DPA resistance according to the present invention, the security requirements preset in step 7 are: the nonlinearity of the S-box is 112, the algebraic number is greater than 3, and the difference is consistent The property is 4, the absolute value index is 32, and the transparency level is less than 6.9160.

As a further optimization scheme of the construction method of the S-box with excellent DPA resistance according to the present invention, R is set to 2-5.

Compared with the prior art, the present invention adopts the above technical scheme, and has the following technical effects:

(1) The present invention can generate an S box with excellent DPA resistance, very high nonlinearity, low differential consistency, low absolute value index, and high algebraic degree. Compared with the existing technical research scheme, the constructed S box It has stronger security and practicality;

(2) The present invention can improve the DPA resistance of the existing S box, while retaining other important cryptographic properties, such as nonlinearity, differential consistency, algebraic times, absolute value indicators, etc.; the ability of the S box of the present invention to resist other attacks It is also strong enough so that the S-box of the present invention can have higher security to meet practical requirements.

Description of drawings

Figure 1 shows the method of the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

Fig. 1 is the method of the present invention, and the specific embodiment of the present invention is:

Step 1, given an n-bit input and balanced S-box F, as the initial input of the iterative construction process, and put it into the set SF. The iterative construction process is steps 2-7:

Step 2, according to the input truth table of the S box F, add all the bit positions of the S box to a candidate pool PF, which contains all possible inverted bit positions, and has a total of n*2 ⁿ elements.

Step 3. Take b elements, ie bit positions, from the candidate pool. The b elements taken out need to meet the requirements: 1) b=2k, (k=1, 2, . . . , 2 ^n-1 ). 2) The same component function that belongs to the S-box. 3) A vector composed of bits corresponding to the b elements, and its Hamming weight is 2 ^b-1 . Then a bit inversion operation is performed at the b position of the S box to generate a new S box F'.

Step 4, repeat the process of step 3 until all elements in the candidate pool are empty, and generate all S boxes F' associated with F.

Step 5, for each newly generated S box F', calculate the value CF of its loss function, and put the S box F' and the corresponding loss function value CF into the list L. The loss function used in the calculation is:

为二元域上的n维向量空间，

为二元域上的非零n维向量空间，R为常数，设置为2～5。Among them, n represents the number of input bits of S box F,

is an n-dimensional vector space on a binary field,

is a non-zero n-dimensional vector space on the binary field, R is a constant, set to 2~5.

W _F (c, b) is the Walsh spectral value of the S box with respect to the vectors c, b, defined as:

其中，x＝(x₁,x₂,…,x_n),b＝(b₁,b₂,…,b_n) 为二元域上的n维向量，"·"为内积运算，即x·b＝x₁b₁⊕x₂b₂⊕…⊕x_nb_n。⊕为二元域上的加法，即模2加法。

Among them, x=(x ₁ ,x ₂ ,...,x _n ),b=(b ₁ ,b ₂ ,...,b _n ) is the n-dimensional vector on the binary field, "·" is the inner product operation, that is x·b=x ₁ b ₁ ⊕x ₂ b ₂ ⊕…⊕x _n b _n . ⊕ is the addition on the binary field, that is, the addition modulo 2.

其中#表示集合元素的数目。N ₄ (σ(α,β)) is a judgment function, which judges whether the difference spectrum value σ(α,β) of the S box about the n-dimensional vector α,β on the binary field is greater than 4, if it is greater than 4, return 1, otherwise Returns 0. where σ(α,β) is defined as

Where # represents the number of set elements.

τ _F is the transparency order of the S-box F, which is defined as:

是S盒F的互相关系数，定义为here

is the cross-correlation coefficient of S-box F, defined as

Among them, max means taking the maximum value, β=(β ₀ ,β ₁ ,…,β _n ) is an n-dimensional vector on the binary field, and F=(f ₁ ,f ₂ ,…,f _n ),f _i (x), f _j (x) are the component functions of the S box F, β _i , β _j are the bit information of the i and j positions in the vector β, where 0≤i,j,≤n.

For a given S-box F, calculate the value of the loss function designed above. The smaller the calculated value, the higher the nonlinearity and the lower the differential consistency in the cryptographic properties of the S-box. The smaller the absolute value index, the lower the transparency level, the higher the DPA resistance. Thus, the S-box can be improved to resist DPA attacks, linear attacks, algebraic attacks, differential attacks and other attacks, thereby improving the security and practicability of related equipment.

Step 6, determine whether the list L is empty, if L is empty, then increase the value of b, while b meets the requirements 1), 2) and 3) in step 3. Reproduce step 3 in the process of starting the iterative construction. If L is not empty, select an S box in the list L, and the S box must meet the requirement of having the minimum loss function value;

Step 7, determine whether the S box selected in step 6 exists in the set SF. If so, delete the S box and its corresponding loss function value from the list L, and repeat step 6; if not, judge whether the S box meets the security requirements designed in advance. Specifically:

Calculate the non-linearity, transparency order, differential consistency, algebraic degree, absolute value index and other properties of the S-box. Whether the nonlinearity is equal to 112, the transparency degree is less than 6.9160, the algebraic degree is greater than 3, the differential consistency is equal to 4, and the absolute value is equal to 4. The indicator is equal to 32. The specific calculation process is as follows:

nonlinearity

differential consistency

其中r(a,b)为其自相关函数，定义为：Absolute value indicator

where r(a,b) is its autocorrelation function, defined as:

If satisfied, output the S-box and terminate the iterative construction process. If it is not satisfied, put the S box into the set SF, and use it as the input S box of the next iterative construction process, and repeat the iterative construction process, that is, steps 2-7.

The cryptographic properties of the present invention and the widely used S-box of AES are compared as shown in Table 1

Table 1

nonlinearity Algebraic degree differential consistency Absolute value indicator Transparency method of the invention 112 7 4 32 6.8930 AES S Box 112 7 4 32 6.9160

The S box constructed by the method of the present invention is: [65,158,207,138,121,103,233,69,72,60,88,51,244,215,34,37,164,28,30,78,129,172,77,153,56,122,95,235,17,251,18,200,82,71 ,86,39,232,64,203,214,166,97,204,202,156,234,189,11,197,175, 218,245,24,136,196,253,9,128,100,239,41,165,35,93,114,7,127,33,8,90,160, 135,171,22,19,188,116,254,32,89,249,229,38,107,10,83,73,176,230,67,101 , 26,206,45,117,194,62,94,212,5,146,226,205,87,109,108,250,237,140,185,68, 184,80,98,223,126,167,4,25,192,178,221,119,70,61,20,243,210,145,177,174, 75,57,157,3,154,112,191,247,144,143,132,104,173,208,151,195,149,213,23, 139,181,48,137,1,222,74,186,228,255,16,65 ,44,120,252,179,242,76,21,147, 134,53,91,133,124,169,36,155,216,219,115,113,161,190,79,50,187,141,123, 231,99,150,58,52,225,238,31,209,47,42,46,106,96,2,148,201,131,241,102, 152,43,13,182,248,54,183,227,125,159,118,246,198,105,220,162,85,92,193 , 40,6,49,27,240,111,199,63,236,211,170,130,12,55,224,142,217,84,110,29,168,59,16,163]

The implementation method given above is only used to illustrate that the present invention is devoted to improving the DPA resistance of the S box, and does not limit the present invention to only take the above-mentioned parameter values and parameter forms. For those skilled in the art, without departing from the present invention. Under the premise of the thought, the present invention can have various transformation forms, so the protection scope of the present invention is not limited to the above-mentioned embodiments. Any modifications, equivalent replacements, improvements, etc. made within the ideological framework of the present invention shall be included within the scope of the claims of the present invention.

Claims (3)

1. A method of constructing an S-cassette with excellent DPA resistance, comprising the steps of:

step 1, giving an n-bit input and balanced S box F, wherein the S box F is used as an initial input of an iterative construction process, and the S box F is put into a set SF; the iterative construction process is step 2-step 7;

step 2, generating a candidate pool according to the input truth table of the S box F, wherein the candidate pool comprises all bit positions capable of being reversed;

step 3, b elements are taken out from the candidate pool, and the b elements are b bit positions; then, carrying out bit inversion operation on the b bit positions of the S box to generate a new S box;

the b elements taken out need to meet the following requirements: 1) b 2k, k 1,2, …,2^n-1(ii) a 2) The same component function attributed to the S-box; 3) the Hamming weight of the vector composed of the bits corresponding to the b elements is 2^b-1；

Step 4, repeating the process of step 3 until the elements in the candidate pool are emptied, and generating all new S boxes associated with the F;

step 5, calculating the value of the loss function of each newly generated S box, and putting the S box and the corresponding value of the loss function into a list L;

step 6, judging whether the list L is empty, if so, increasing the value of b, and simultaneously b meets the requirements 1), 2) and 3) in the step 3, and executing the step 3 to the step 5; if L is not empty, selecting an S box with the minimum loss function value from the list L;

and 7, judging whether the S box selected in the step 6 exists in the set SF:

if yes, deleting the S box and the corresponding loss function value from the list L, and executing the step 6;

if not, judging whether the S box meets the preset safety requirement: if yes, outputting the S box, and terminating the iterative construction process; if not, putting the S box into the set SF, and taking the S box as an input S box of the next iteration construction process, namely taking the S box as the input S box in the step 2; and executing the step 2 to the step 7;

the loss function in step 5 is:

where n represents the S-box as n input bits,

is an n-dimensional vector space over a binary domain,

is a non-zero n-dimensional vector space, W, over a binary domain_F(c, b) Walsh spectrum values of S-box with respect to vector c, b, β are N-dimensional vectors in binary domain, c, α are non-zero N-dimensional vectors in binary domain, R is a constant, σ (α, β) is a differential spectrum value of S-box with respect to vector α, β, N₄(σ (α, β)) is a function for determining whether σ (α, β) is greater than 4, τ_FIs a transparent step of the S-box.

2. The method of claim 1, wherein the safety requirements predetermined in step 7 are: the nonlinearity of the S-box is 112, the algebraic degree is greater than 3, the difference consistency is 4, the absolute value index is 32, and the transparency level is less than 6.9160.

3. The method of claim 1, wherein R is set to 2-5.

Images