CN-122027121-A - Method and system for constructing reflexive S box based on m sequence generation and logic optimization

CN122027121ACN 122027121 ACN122027121 ACN 122027121ACN-122027121-A

Abstract

The invention provides a method and a system for constructing a self-reflecting S box based on m-sequence generation and logic optimization, and belongs to the technical fields of cryptography and hardware security. Firstly, constructing an n-level linear feedback shift register according to a set S box bit number n and a primitive polynomial, generating an m-sequence in a non-all-zero initial state, adding an all-zero state at the tail end, constructing an autoreflective S box lookup table through a symmetrical mapping strategy, and mapping an ith element and a symmetrical position element in the sequence to realize encryption and decryption by using the same S box. Then, the lookup table is used as a Boolean function truth table, is simplified into a simplest expression by utilizing a logic minimization algorithm, and is decomposed into a hierarchical logic circuit. During actual processing, N data blocks are firstly converted into a bit plane format from block storage, then the parallel operation is carried out through a layering circuit, and finally the result is transposed back to the block storage. The method can multiplex the same S box hardware module in the encryption and decryption process, and remarkably saves hardware resources.

Inventors

DING JIULING
CUI ZHENXING
LI XUEFENG
XU JUNJIE
MA ZHONGJUN

Assignees

山东未来网络研究院(紫金山实验室工业互联网创新应用基地)

Dates

Publication Date: 20260512
Application Date: 20260119

Claims (10)

1. The method for constructing the reflexive S box based on m-sequence generation and logic optimization is characterized by comprising the following steps of: Configuring S box bit number n, selecting an n-order primitive polynomial, constructing an n-order linear feedback shift register based on the primitive polynomial, and initializing by using a non-all-zero initial state vector; driving the linear feedback shift register to circularly shift to generate a period with the length of Adding all zero state vectors to the end of the m-sequence to form an m-sequence containing all A complete sequence of individual states; constructing a self-reflecting S-box lookup table by adopting a symmetrical mapping strategy so as to ensure that the ith element in the sequence is subjected to And the first Individual elements Pairing and mapping; The generated self-reflection S box lookup table is used as a truth table of a Boolean function, a logic minimization algorithm is applied to simplify the Boolean function, a simplest logic expression is obtained, and the simplest logic expression is decomposed into a layered logic circuit which comprises an input layer, a top layer, a middle layer, a bottom layer and an output layer; Acquiring N data blocks to be processed, executing input data transposition, and converting the data blocks from a block type storage format to a bit plane storage format; and applying the hierarchical logic circuit to the transposed bit plane data, realizing parallel logic operation, executing output data transposition, and recovering the processed bit plane data into a block type storage format.
2. The m-sequence generation and logic optimization based self-inverting S-box construction method of claim 1, wherein the driving linear feedback shift register cyclically shifts, in particular as follows: In each clock period, driving the bits in the linear feedback shift register to move one bit in one direction, outputting the highest bit or the lowest bit, calculating new input bits by a feedback function according to the state of the current linear feedback shift register until the state of the register returns to the initial state for the first time, generating a period with the length of The feedback function is defined by a primitive polynomial.
3. The m-sequence generation and logic optimization based self-inverting S-box construction method of claim 1, wherein the logic minimization algorithm is a quinine-maclaky algorithm, and patterns that can form exclusive or exclusive nor operation are identified and combined in the combining term process.
4. The m-sequence generation and logic optimization based reflexive S-box construction method of claim 1, wherein in the hierarchical structure: the input layer is used for carrying out linear preprocessing and expansion on an input signal to generate a plurality of intermediate signals; The top layer is used for introducing the preliminary nonlinear characteristic and generating an intermediate bit plane with nonlinearity; the middle layer is used for carrying out depth nonlinear combination transformation and improving algebraic times and nonlinearity; the bottom layer is used for cross-combining the linear signal and the nonlinear signal to generate a basic component bit plane required by output; the output layer is used to generate a final output bit plane by linear combination.
5. The m-sequence generation and logic optimization based reflexive S-box construction method of claim 1, wherein the boolean function comprises eight inputs and eight outputs.
6. The m-sequence generation and logic optimization based reflexive S-box construction method of claim 1, wherein said input data transpose comprises: n128-bit data blocks are formed into 128 bit planes, the j-th bit plane being formed by the j-th bits of all N data blocks, each bit plane being represented by an N-bit machine word.
7. The m-sequence generation and logic optimization based reflexive S-box construction method of claim 6, wherein the output data transpose is the inverse of the input data transpose, combining 128 bit plane data into N128 bit ciphertext data blocks, and restoring to a standard block storage format.
8. An m-sequence generation and logic optimization based reflexive S-box construction system using the method of any one of claims 1-7, comprising: The self-inverting S box construction module is used for configuring S box bit number n, selecting an n-order primitive polynomial, constructing an n-order linear feedback shift register based on the primitive polynomial, and initializing by using a non-all-zero initial state vector; driving the linear feedback shift register to circularly shift to generate a period with the length of Adding all zero state vectors to the end of the m-sequence to form an m-sequence containing all Constructing a self-reflection S-box lookup table by adopting a symmetrical mapping strategy so as to enable the ith element in the sequence to be And the first Individual elements Pairing and mapping; The logic optimization and layering module is used for taking the generated self-reflection S box lookup table as a truth table of a Boolean function, simplifying the Boolean function by applying a logic minimization algorithm, obtaining a simplest logic expression, and decomposing the simplest logic expression into a layering logic circuit, wherein the layering logic circuit comprises an input layer, a top layer, a middle layer, a bottom layer and an output layer; The bit slice parallel processing module is used for acquiring N data blocks to be processed, executing input data transposition, converting the data blocks from a block type storage format to a bit plane storage format, applying the hierarchical logic circuit to the transposed bit plane data, realizing parallel logic operation, executing output data transposition and recovering the processed bit plane data to the block type storage format.
9. An m-sequence generation and logic optimization based reflexive S-box construction device comprising a processor and a memory storing program instructions, characterized in that the processor is configured to execute the m-sequence generation and logic optimization based reflexive S-box construction method according to any one of claims 1-7 when running the program instructions.
10. A computer readable storage medium, characterized in that it has stored thereon a computer program which, when executed by a processor, implements the m-sequence generation and logic optimization based reflexive S-box construction method as claimed in any one of the preceding claims 1-7.

Description

Method and system for constructing reflexive S box based on m sequence generation and logic optimization Technical Field The invention relates to a method and a system for constructing a reflexive S box based on m-sequence generation and logic optimization, belonging to the technical fields of cryptography and hardware security. Background In modern cryptography, symmetric cryptographic algorithms, such as Advanced Encryption Standard (AES), are the cornerstone for guaranteeing data confidentiality. The security strength of these algorithms depends to a large extent on its internal unique nonlinear transformation component, the substitution box (S-box). The S box has the main function of carrying out complex nonlinear replacement on input data so as to effectively confuse the statistical relationship among plaintext, secret key and ciphertext, thereby resisting mainstream password attack means such as differential password analysis, linear password analysis and the like. An S box with excellent design has to reach higher standards for cryptographic indexes such as differential uniformity, nonlinearity, algebraic frequency, avalanche effect and the like. Currently, the need for lightweight cryptography is increasingly prominent in internet of things (IoT), embedded systems, and other resource-constrained application scenarios. Devices in these scenarios are severely limited in their computing power, memory space, and power consumption. However, conventional S-box implementations face a serious set of technical challenges. Firstly, the resource consumption is huge. When the S-box is implemented as a hardware circuit, if a look-up table (LUT) is used, the S-box is solidified in a read-only memory (ROM) or is synthesized into a combinational logic circuit by a hardware description language, a relatively large chip area is occupied. And secondly, there is a performance bottleneck. Conventional byte-by-byte table look-up operations are serial in nature and have throughput rates that are difficult to meet when high-speed data streams are to be processed. The following is poor design flexibility. Most standard algorithms employ a fixed S-box, and once the S-box is found to have a cryptographic defect, the security of the whole algorithm is severely threatened, and the fixed structure also makes it easier to be the target of side channel attacks. And finally, the decryption implementation process is complex. Many standard symmetric cryptographic algorithms, such as AES, do not have autoreactivity S (x)) +.x. This means that a separate inverse S-box (InverseS-box) must be additionally implemented when designing the decryption circuitry. This results in the encryption and decryption module not sharing S-box resources, making hardware costs nearly doubled, contrary to the design goals of lightweight applications. Taking the S-box of the Advanced Encryption Standard (AES) as an example, its standardized implementation is a typical representative solution in the current field. The S-box of the scheme is defined based on inversion operations and an affine transformation over the galois field GF (28). On a hardware or software implementation, a look-up table (LUT) containing 256 entries is typically employed. However, this prior art solution has significant drawbacks. First is the resource overhead problem. ROM-based approaches require a fixed memory area, while combinational logic circuits generated directly by synthesis tools tend to be massive and structurally redundant, as it is difficult for automation tools to find algebraic structures deep in boolean functions for efficient logic reduction. Second, non-autoreactivity results in decryption implementation redundancy. The standard S-box of AES does not have a self-inverting feature and the decryption process must use a completely different Inverse S-box (Inverse S-box) which also requires a separate 256-entry look-up table or a separate set of combinational logic circuits. This makes it impossible for the encryption and decryption modules to share the same S-box component, resulting in a significant increase in the total hardware area, which is counter to the design goals of lightweight cryptographic applications. In addition, whether ROM look-up table or combinational logic, the traditional implementation method processes one byte of data at a time, and the application requirement of high throughput rate is difficult to meet. Although advanced technologies such as tower domain decomposition and SAT solver and the like are studied to deeply optimize a logic circuit of a fixed S box, and a remarkable area reduction effect is obtained, the methods have complex processes and do not fundamentally solve the problem of reflexibility and design flexibility of the S box. Therefore, a new S-box architecture solution capable of simultaneously solving the problems of resource consumption, performance bottleneck, design flexibility and encryption/decryption multiplexing is needed.