CN110166223A - A kind of Fast Software implementation method of the close SM4 of state - Google Patents

Abstract

The invention provides a rapid software implementation method of the national secret SM4, which comprises: a data arrangement step, a key arrangement step, an iterative calculation step, a data reverse arrangement step, and a reverse order calculation step. The present invention uses bit slice technology, SIMD technology and composite domain technology to realize the parallel encryption of 256 groups of plaintext messages, implement the nonlinear transformation in SM4 in the composite domain, and combine the nonlinear transformation and linear transformation compression to make SM4 encryption The calculation of the synthetic permutation T in the algorithm is simplified from the original inverse operation on GF(2 ⁸ ), two affine transformations, 4 circular left shifts and 4 XOR operations to one time on GF(2 ⁴ ). The inverse operation, two affine transformations, three multiplication operations on the finite field GF(2 ⁴ ) and four subsequent operations reduce the computational complexity and improve the execution efficiency.

Description

A Fast Software Implementation Method of National Secret SM4

technical field

The present invention relates to the technical field of computer security, in particular to an SM4 encryption method

Background technique

The fundamental task of cryptosystems is when data is encrypted. According to the relationship between encryption key and decryption key, various data encryption systems can be divided into two categories: symmetric encryption system and public key encryption system. Commonly used symmetric encryption methods include DES, AES, IDEA, RC6, etc.

SM4 is a block cipher algorithm, the plaintext, key, and ciphertext are all 128 bits, and the encryption and decryption keys are the same. Encryption and decryption are realized through a nonlinear iterative round function of 32 cycles. These include non-linear transformation s-boxes, and linear transformations consisting of circular XORs. In addition to the 256-byte s box, another two sets of parameters FK and cK are defined (refer to the website of the Cryptography Bureau for specific data). The basic process is to first divide the 128-bit key into 4 groups according to the 32-bit group, and then generate 32 groups of 32-bit round keys according to the key expansion algorithm; then divide the input 128-bit data into 4 groups according to the 32-bit group Perform a loop operation.

Contents of the invention

Aiming at the defects in the current software implementation method, the present invention proposes the following improved software optimization method.

A rapid software implementation method of national secret SM4, comprising:

Data arrangement step, 256 groups of 128-bit data are represented as X _{[256] [128]} , X _[i] represents the i-th group of data, i=0, 1, . . ., 255, and there is bit matrix transposition transformation TRANS256( ): X _[128][256] =TRANS(X _[256][128] ), characterized in that the input is 256*128 bits, and the output is 128*256 bits, so that the same bits of 256 sets of data are gathered in the same in memory block;

In the key arrangement step, the k-th round encryption key is recorded as RK _{k, [32]} , k=0, 1, ..., 31, there is a transformation TRANS32(·): TRK _{k, [32] [256]} = TRANS32 (RK _{k, [32]} ), is characterized in that, the definition { } ₂₅₆ means that elements are repeated 256 times and spliced together, then TRK _{k, [i]} = {RK _{k, [i]} } ₂₅₆ , the realization will be The i-th bit of the key RK is copied 256 times and stored in the i-th item of TRK;

Iterative calculation steps, and record the data after data arrangement as X ²⁵⁶ represents a two-dimensional array X _[128][256] , Point to the i*32th item of X _[128][256] , i=0, 1, 2, 3, record the k-th round encryption key after key arrangement as Perform 32 iterative calculations: in, is an XOR operation;

Data anti-arranging step, there is the same bit matrix transposition TRANS256( ): X _[256][128] =TRANS256(X _[1286][256] ), it is characterized in that the data after iterative calculation is obtained from the sliced The 128 groups of 256-bit data organization methods are restored to the normal 256 groups of 128-bit data;

Reversing the calculation steps, let Then the output 256 groups of 128-bit encrypted data are expressed as

Wherein, the input and output of the combined permutation T are both 32*256 bits, and T(·)=L(τ(·)) is formed by combining the nonlinear transformation τ and the linear transformation L.

Furthermore, 256 sets of 128-bit data are regarded as two 128 sets of 128-bit data, and the SIMD idea is used to implement data arrangement and data reverse arrangement in parallel, and 7 sets of masks are used to complete the bit matrix transposition. The hexadecimal representation of the 7 groups of masks is:

MASK0＝55555555555555555555555555555555555555555555555555555555555555

MASK1＝3333333333333333333333333333333333333333333333333333333333333

MASK2=0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F

MASK3 = 00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF

MASK4=0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF

MASK5 = 00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF

MASK6 = 0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF

Each mask is 128 bits.

Further, 256 sets of 32-bit input data are expressed as: in, Both are 8*256 bits, then

Furthermore, the function s(·) in the nonlinear transformation τ in the synthesis transformation T is: s(x ²⁵⁶ )=I(x ²⁵⁶ *A ₁ +C ₁ )*A ₂ +C ₂ , where, I( ) is the inverse operation on the composite field GF((2 ⁴ ) ² ), x ²⁵⁶ is a row vector of 8*256 bits, A ₁ , C ₁ , A ₂ , and C ₂ are in the following form:

C ₁ ={1 0 0 0 1 1 1 0}

C ₂ ={1 1 0 1 0 0 1 1}

go a step further,

Select h, g∈GF((2 ⁴ ) ² ), h=(h ₁ *x+h ₀ ) is the inverse element of g=(g ₁ *x+g ₀ ), where, h ₁ , h ₀ , g ₁ , g ₀ ∈GF(2 ⁴ ). then there is

Among them, the size of h and g is 8*256 bits, is an XOR operation, and the multiplication and inversion are operations on the finite field GF(2 ⁴ ), thus converting the inversion on the composite field GF((2 ⁴ ) ² ) into multiplication and summing on the finite field GF(2 ⁴ ) inverse.

definition ＜<< means circular left shift operation, Represents an XOR operation; known make but Let B ²⁵⁶ =τ(A ²⁵⁶ ), then Available:

in, XOR plus, so that the linear transformation can be optimized away.

Furthermore, let a ²⁵⁶ , b ²⁵⁶ , c ²⁵⁶ ∈GF(2 ⁴ ), and c ²⁵⁶ =a ²⁵⁶ *b ²⁵⁶ , then the multiplication operation on GF(2 ⁴ ) is:

in, It is XOR addition, and the default representation of AND operation.

Furthermore, let a ²⁵⁶ , c ²⁵⁶ ∈GF(2 ⁴ ), and c ²⁵⁶ =(a ²⁵⁶ ) ^-1 , then the inverse operation on GF(2 ⁴ ) is:

Among them, + is an OR operation, ~ is a NOT operation, and the AND operation is represented by default.

The technical effects of the present invention are: combining SIMD thought, using bit slice technology, using AVX2 instruction to process 256 groups of data in parallel, using compound domain decomposition technology to decompose the calculation in the synthetic permutation T in SM4, so that non- The linear transformation calculation is simplified from the original GF(2^8) inversion and two affine transformations to one GF(2^4) inversion, two affine transformations, and three multiplication operations on GF(2^4). , reducing computational complexity, maximizing parallel processing of data, and improving execution efficiency.

Description of drawings

Fig. 1 is a system architecture diagram of the SM4 encryption method designed by the present invention;

Fig. 2 is an illustration of the compound field inversion algorithm in the present invention.

Detailed ways

Describe in detail below in conjunction with accompanying drawings 1 and 2

Fig. 1 shows the SM4 encryption method that the present invention designs, and this method comprises:

Data arrangement step, 256 groups of 128-bit data are represented as X _{[256] [128]} , X _[i] represents the i-th group of data, i=0, 1, . . ., 255, and there is bit matrix transposition transformation TRANS256( ): X _[128][256] =TRANS(X _[256][128] ), characterized in that the input is 256*128 bits, and the output is 128*256 bits, so that the same bits of 256 sets of data are gathered in the same in memory block;

In the key arrangement step, the k-th round encryption key is recorded as RK _{k, [32]} , k=0, 1, ..., 31, there is a transformation TRANS32(·): TRK _{k, [32] [256]} = TRANS32 (RK _{k, [32]} ), is characterized in that, the definition { } ₂₅₆ means that elements are repeated 256 times and spliced together, then TRK _{k, [i]} = {RK _{k, [i]} } ₂₅₆ , the realization will be The i-th bit of the key RK is copied 256 times and stored in the i-th item of TRK;

Iterative calculation steps, and record the data after data arrangement as X ²⁵⁶ represents a two-dimensional array X _[128][256] , Point to the i*32th item of X _[128][256] , i=0, 1, 2, 3, record the k-th round encryption key after key arrangement as Perform 32 iterative calculations: in, is an XOR operation;

Data anti-arranging step, there is the same bit matrix transposition TRANS256( ): X _[256][128] =TRANS256(X _[1286][256] ), it is characterized in that the data after iterative calculation is obtained from the sliced The 128 groups of 256-bit data organization methods are restored to the normal 256 groups of 128-bit data;

Reversing the calculation steps, let Then the output 256 groups of 128-bit encrypted data are expressed as

Wherein, the input and output of the combined permutation T are both 32*256 bits, and T(·)=L(τ(·)) is formed by combining the nonlinear transformation τ and the linear transformation L.

In the data arrangement step, it is necessary to complete the bit matrix transposition with the help of 7 groups of masks. Treat 256 sets of 128-bit data as two 128 sets of 128-bit data, use SIMD idea to realize data arrangement and data reverse arrangement in parallel, and use 7 sets of masks to complete bit matrix transposition. The hexadecimal representation of the 7 groups of masks is:

MASK0＝55555555555555555555555555555555555555555555555555555555555555

MASK1＝3333333333333333333333333333333333333333333333333333333333333

MASK2=0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F

MASK3 = 00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF

MASK4=0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF

MASK5 = 00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF

MASK6 = 0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF

Each mask is 128 bits.

In the actual encryption calculation, 256 sets of 32-bit input data are expressed as: in, Both are 8*256 bits, then

The following is the key point of the present invention, which converts the inversion on the finite field GF(2 ⁸ ) to the inversion on the composite field GF((2 ⁴ ) ² ), reducing the computational complexity. The function s(·) in the nonlinear transformation τ in the synthetic transformation T is: s(x ²⁵⁶ )=I(x ²⁵⁶ *A ₁ +C ₁ )*A ₂ +C ₂ , where I(·) is the composite The inversion operation on the field GF((2 ⁴ ) ² ), x ²⁵⁶ is an 8*256-bit row vector, and the forms of A ₁ , C ₁ , A ₂ , and C ₂ are as follows:

C ₁ ={1 0 0 0 1 1 1 0}

C ₂ ={1 1 0 1 0 0 1 1}

go a step further,

Select h, g∈GF((2 ⁴ ) ² ), h=(h ₁ *x+h ₀ ) is the inverse element of g=(g ₁ *x+g ₀ ), where, h ₁ , h ₀ , g ₁ , g ₀ ∈GF(2 ⁴ ). then there is

Among them, the size of h and g is 8*256 bits, is an XOR operation, and the multiplication and inversion are operations on the finite field GF(2 ⁴ ), thus converting the inversion on the composite field GF((2 ⁴ ) ² ) into multiplication and summing on the finite field GF(2 ⁴ ) inverse.

Due to the use of bit slices, the result of the linear shift can be directly XORed with the target, thus optimizing the shift operation. definition ＜<< means circular left shift operation, Represents an XOR operation; known make but Let B ²⁵⁶ =τ(A ²⁵⁶ ), then Available:

Furthermore, let a ²⁵⁶ , b ²⁵⁶ , c ²⁵⁶ ∈GF(2 ⁴ ), and c ²⁵⁶ =a ²⁵⁶ *b ²⁵⁶ , then the multiplication operation on GF(2 ⁴ ) is:

in, It is XOR addition, and the default representation of AND operation.

Let a ²⁵⁶ , c ²⁵⁶ ∈GF(2 ⁴ ), and c ²⁵⁶ =(a ²⁵⁶ ) ^-1 , then the inverse operation on GF(2 ⁴ ) is:

Among them, + is an OR operation, ~ is a NOT operation, and the AND operation is represented by default.

A shortcut technology for software implementation of block cipher algorithm is the compound field decomposition method: the complex finite field operation of the S-box isomorphically mapped to the compound field for implementation, and the encryption and decryption operations do not need to look up the table to obtain the results through the operation, thereby avoiding memory overhead. . The input data of the S-box table lookup algorithm is 8 bits, and the output data is also 8 bits. The software lookup table algorithm of the SM4 algorithm needs to occupy a space of 256x 8 bits=2048 bits in the memory. The invention maps the S-box operation to the composite domain, without pre-storing any look-up table, and completes the S-box operation through logical operation, which greatly reduces the computational complexity and improves the execution efficiency.

Finally, it should be noted that: the above embodiments are only to illustrate and not limit the technical solutions of the present invention, although the present invention has been described in detail with reference to the above embodiments, those of ordinary skill in the art should understand that: the present invention can still be modified Any modification or partial replacement without departing from the spirit and scope of the present invention shall fall within the scope of the claims of the present invention.

Claims (9)

1. A fast software implementation method of national secret SM4, characterized in that, comprising: Data orchestration steps: 256 groups of 128-bit data are represented as X _[256][128] , X _[i] represents the i-th group of data, i=0, 1, ..., 255, there is a bit matrix transposition transformation TRANS256( ): Make X _[128][256] =TRANS(X _[256][128] ), the input is 256*128 bits, and the output is 128*256 bits, so that the same bits of 256 groups of data are gathered in the same memory block; Key orchestration steps: Denote the k-th round encryption key as RK _{k, [32]} , k=0, 1, ..., 31, there is a transformation TRANS32(·): TRK _{k, [32][256]} = TRANS32(RK _{k, [32]} ), the definition { } ₂₅₆ means to repeat the elements 256 times and splicing them together, then TRK _{k, [i]} = {RK _{k, [i]} } ₂₅₆ , to realize the copying of the i-th bit of the key RK 256 deposits into the i-th item of TRK; Iterative calculation steps: Record the data after data arrangement as X ²⁵⁶ represents a two-dimensional array X _[128][256] , Point to the i*32th item of X _[128][256] , i=0, 1, 2, 3, record the k-th round encryption key after key arrangement as Perform 32 iterative calculations: in, is an XOR operation; Data de-arranging steps: There is a bit matrix transposition TRANS256( ): X _[256][128] = TRANS256(X _[128][256] ), the data after iterative calculation is restored to normal from the 128 groups of 256-bit data organization after slicing 256 sets of 128-bit data; Calculation steps in reverse order: make Then the output 256 groups of 128-bit encrypted data are expressed as Wherein, the input and output of the combined permutation T are both 32*256 bits, and T(·)=L(τ(·)) is formed by combining the nonlinear transformation τ and the linear transformation L. 2. the fast software implementation method of national secret SM4 according to claim 1 is characterized in that, 256 groups of 128-bit data are regarded as two 128 groups of 128-bit data to realize data arrangement and data reverse arrangement, and utilize 7 groups of masks The code completes the bit matrix transposition; the hexadecimal representation of the 7 groups of masks is: MASK0＝55555555555555555555555555555555555555555555555555555555555555 MASK1＝3333333333333333333333333333333333333333333333333333333333333 MASK2=OFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFOFO MASK3＝OOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFFOOFF MASK4=OOOOFFFFOOOOFFFFOOOFFFFOOOOFFFFOOOOFFFFOOOOFFFFOOOOFFFFOOOOFFFF MASK5=OOOOOOOOFFFFFFFOOOOOOOFFFFFFFOOOOOOOFFFFFFFFFOOOOOOOFFFFFFFF MASK6=OOOOOOOOOOOOOOOOFFFFFFFFFFFFFFFOOOOOOOOOOOOOOOOFFFFFFFFFFFFFFFF Each mask is 128 bits. 3. the fast software implementation method of national secret SM4 according to claim 1, is characterized in that, in iterative calculation step: 256 groups of 32 bit input data are represented as: in, Both are 8*256 bits, then 4. The fast software implementation method of the national secret SM4 according to claim 3 is characterized in that the affine transformation on the finite field GF(2 ⁸ ) is combined with the isomorphic mapping matrix, thereby the finite field GF(2 ⁸ ) is transformed into an affine transformation on the complex domain GF((2 ⁴ ) ² ), the function S(·) in the nonlinear transformation τ in the synthetic transformation T is: S(x ²⁵⁶ )= I(x ²⁵⁶ *A ₁ +C ₁ )*A ₂ +C ₂ , where I(·) is the inverse operation on the composite field GF((2 ⁴ ) ² ), and x ²⁵⁶ is a row of 8*256 bits The vectors, A ₁ , C ₁ , A ₂ , C ₂ are of the form: C ₁ ={1 0 0 0 1 1 1 0} C ₂ ={1 1 0 1 0 0 1 1}. 5. according to the fast software implementation method of national secret SM4 described in claim 4, it is characterized in that, 6. the fast software implementation method of national secret SM4 according to claim 4 is characterized in that, select h, g∈GF((2 ⁴ ) ² ), h=(h ₁ *x+h ₀ ) is g= The inverse of (g ₁ *x+g ₀ ), where, h ₁ , h ₀ , g ₁ , g ₀ ∈GF(2 ⁴ ); then we have Among them, the size of h and g is 8*256 bits, is an XOR operation, and multiplication and inversion are operations on the finite field GF(2 ⁴ ), thus further transforming an inversion on the composite field GF((2 ⁴ ) ² ) into an operation on the finite field GF(2 ⁴ ) One inversion and three multiplications. 7. the fast software implementation method of national secret SM4 according to claim 5, is characterized in that, defines ＜<< means circular left shift operation, Represents an XOR operation; known make but Let B ²⁵⁶ =τ(A ²⁵⁶ ), then Among them, 0≤k≤31, can get: in, For XOR addition, after slicing operations, the linear transformation can be simplified from the original four times of circular left shift and four times of XOR to four times of XOR, and the circular left shift can be optimized by direct indexing. 8. the fast software implementation method of national secret SM4 according to claim 6, is characterized in that, order a ²⁵⁶ , b ²⁵⁶ , c ²⁵⁶ ∈GF(2 ⁴ ) and c ²⁵⁶ ＝a ²⁵⁶ *b ²⁵⁶ , then the multiplication operation on GF(2 ⁴ ) is: in, It is XOR addition, and the default representation of AND operation. 9. the fast software implementation method of national secret SM4 according to claim 6, is characterized in that, order a ²⁵⁶ , c ²⁵⁶ ∈GF(2 ⁴ ), and c ²⁵⁶ ＝(a ²⁵⁶ ) ^-1 , then the inverse operation on GF(2 ⁴ ) is: Among them, + is an OR operation, ~ is a NOT operation, and the AND operation is represented by default.