CN116432765A - RISC-V-based special processor for post quantum cryptography algorithm - Google Patents

Abstract

The invention discloses a special processor for a post quantum cryptography algorithm based on RISC-V, which adopts a super-standard quantity pipeline design with separate reading and writing and calculation, and comprises a reading and writing pipeline and a calculating pipeline which can be executed in parallel, and comprises a finger taking part, a decoding part, an executing part, a writing back part and the like, wherein parallel calculating unit modules contained in the executing part are realized by adopting a component recombination technology and an operator fusion technology, and the same component is used for realizing core operation of the post quantum cryptography algorithm with different calculating types and bit widths, thereby reducing the hardware resource expenditure of the processor and accelerating the operation speed, and parallel calculating unit modules and parallel register modules contained in the processor form a parallel storage system and data flow with mixed bit widths, so that the loads of the two pipelines of calculation, reading and writing are balanced and the bandwidth is reduced.

Description

A special processor for post-quantum cryptography algorithm based on RISC-V

technical field

The invention belongs to the technical field of post-quantum cryptography algorithm hardware acceleration and RISC-V (Reduced Instruction SetComputer-V, the fifth generation reduced instruction set processor) instruction set expansion processor, and specifically relates to a post-quantum cryptography algorithm based on RISC-V dedicated processor.

Background technique

Post-quantum cryptography is a new generation of public key cryptography that can cope with quantum computer attacks. The construction of traditional public key cryptographic algorithms (RSA, Diffie-Hellman, elliptic curve, etc.) currently in use is based on mathematically difficult problems such as large integer decomposition, discrete logarithm (and elliptic curve version). However, with the continuous development of quantum computer technology and the emergence of efficient quantum algorithms (such as Shor's algorithm in 1994), sufficiently large and stable quantum computers can solve these difficult problems within polynomial time complexity, and traditional public key cryptography algorithms will soon be unavailable. Safe again. In order to ensure information security, the cryptography community has formulated a new post-quantum cryptography algorithm standard after years of extensive research and discussion, so as to gradually promote and replace the traditional cryptography algorithm that will no longer be safe.

However, it is difficult to deploy post-quantum cryptography algorithms on existing hardware devices, especially low-cost terminal devices. Compared with the traditional public key cryptographic algorithm, the post-quantum cryptographic algorithm has the characteristics of larger calculation amount and more complex calculation form. Its larger key length and calculation scale also make the planning of data flow and storage space in the calculation process very difficult. It is difficult to implement applications with high real-time requirements. In order to improve the running speed of the post-quantum cryptography algorithm, the academic community has carried out extensive research, and optimized and accelerated it at the software and hardware levels. High, low circuit multiplexing, high resource overhead and other disadvantages; for the low-performance, low-cost terminal equipment that dominates applications such as the Internet of Things, there are still vacancies in the field of hardware acceleration solutions for quantum cryptography algorithms.

The RISC-V instruction set is an open source instruction set architecture based on the reduced instruction set (RISC) principle, which is suitable for small, fast, low-power designs, has strong scalability, and is widely used in low-cost terminal equipment In the design, it is one of the basic technologies adopted in this design.

Contents of the invention

In order to solve the problems in the prior art and fill the technical vacancy in this field, the present invention proposes a post-quantum cryptographic algorithm special processor based on RISC-V instruction set expansion. The present invention aims to use the characteristics of easy expansion of the RISC-V instruction set, combined with the characteristics of parallelism, high reusability, and low power consumption of technologies such as computing component reorganization technology, operator fusion technology, and instruction multiple emission technology, to achieve a lower The power consumption and resource overhead accelerate the calculation speed of the post-quantum cryptography algorithm, and a low-power and high-speed post-quantum cryptography algorithm dedicated processor is designed.

Technical scheme of the present invention is as follows:

The present invention firstly provides a post-quantum cryptographic algorithm special processor based on RISC-V, which adopts a superscalar pipeline design that separates reading and writing from calculation, and has two pipelines that can be executed in parallel, each pipeline has Instruction fetching, decoding, execution, and write-back four parts executed in sequence, the processor specifically includes:

Instruction fetching part, reading and writing and computing pipelines multiplex the same instruction fetching part, which is used to obtain instructions from the instruction cache outside the processor, and distribute instructions to the decoding part of the two pipelines of the processor after pre-analysis , including an instruction interface module used as an interface to exchange data with an instruction cache outside the processor, a prefetch module for pre-reading multiple instructions and caching them, and an instruction distribution module, wherein the instruction distribution module adopts a sequential multi-issue scheme; this part Send non-read-write instructions to the computing pipeline, and send read-write instructions to the read-write pipeline;

The decoding part, which mainly includes four register modules and two decoder-type modules, is used to process the instructions sent by the fetching part, translate these instructions into specific control signals, and read the register modules. Data, and then send these control signals and data to the execution part of the two pipelines; the register module is shared by the two pipelines; the decoder type module includes the first decoder module belonging to the calculation pipeline and the first decoder module belonging to the read and write pipeline Two decoder modules, these two decoder modules respectively translate the instructions received by the corresponding pipelines, and respectively read the required data from the required register modules, and then send the control signals and data corresponding to the pipelines to the execution part of the respective pipeline;

The execution part, which is used to perform specific calculations or memory access operations according to the control signals and data sent by the decoding part, and then send the calculation results and control signals to the write-back part of the two pipelines. The execution part of the calculation pipeline includes Parallel computing unit module, the parallel computing unit module adopts a mixed bit width design, supports parallel computing of data with multiple bit widths up to 256 bits; the execution part of the read and write pipeline includes the first stage of the read and write control unit module, this stage It is used to access the data cache outside the processor according to the control signal and data sent by the decoding part, while other parts of the module work in the write-back part of the read-write pipeline;

The write-back part is used to write the calculation results sent by the calculation pipeline and the execution part of the read-write pipeline back to the corresponding register module contained in the decoding part according to the control signal, wherein the write-back part of the read-write pipeline includes read-write control The second stage of the unit module, which is used to return the result obtained by accessing the external data cache in the first stage to the processor and store it in the register module.

Compared with prior art, the beneficial effect that the present invention has has:

(1) The present invention adopts the superscalar pipeline technology that separates reading and writing from calculation, and configures the computing and reading and writing resources of the processor in two pipelines respectively. The two pipelines can work in parallel, and read and write data while calculating , so as to improve the running speed of the post-quantum cryptography algorithm; in addition, its indexing part combines the characteristics of the post-quantum cryptography algorithm and adopts the sequential multi-shot design, which can save a lot of resources and power consumption compared with the commonly used out-of-order multi-shot .

(2) The present invention adopts component reorganization technology and operator fusion technology, and uses the same basic resources to provide support for post-quantum cryptography algorithms of different types and different bit widths through reorganization, which greatly reduces the overhead of hardware resources, and through Operator fusion reduces the number of cycles required by the algorithm and improves the running speed of the post-quantum cryptography algorithm.

(3) The present invention adopts the storage structure and data flow design with different read-write and calculation bit widths, and combines the characteristics of the core operation of the post-quantum cryptography algorithm to realize the balance of the workload of the two pipelines of calculation and read-write without affecting The algorithm runs at a faster speed while reducing bandwidth requirements and hardware resource overhead.

Description of drawings

Fig. 1 is the post-quantum cryptographic algorithm dedicated processor pipeline architecture diagram of the present invention;

Fig. 2 is the architectural diagram of the parallel computing unit module in the present invention;

Fig. 3 is the schematic diagram of storage structure and data flow among the present invention;

Fig. 4 is a schematic diagram of a combination of processing modules in the parallel computing unit module corresponding to the XORVNA instruction of the example in the embodiment;

Fig. 5 is the command emission sequence corresponding to a butterfly operation when performing NTT (fast number theory transformation) operation in the embodiment of the present invention;

FIG. 6 is an assembly instruction flow corresponding to a butterfly operation when performing NTT (fast number theory transformation) operation in an embodiment of the present invention.

Detailed ways

The present invention will be further elaborated and described below in combination with specific embodiments. The embodiments are merely exemplary of the disclosure and do not delineate the scope of limitation. The technical features of the various implementations in the present invention can be combined accordingly on the premise that there is no conflict with each other.

As shown in Figure 1, the embodiment of the present invention provides a post-quantum cryptographic algorithm special processor based on RISC-V. Pipelines that can be executed in parallel, each pipeline has four parts that are executed sequentially: fetch, decode, execute, and write back.

In a specific embodiment of the present invention, the processor specifically includes:

Instruction fetching part, reading and writing and computing pipelines multiplex the same instruction fetching part, which is used to obtain instructions from the instruction cache outside the processor, and distribute instructions to the decoding part of the two pipelines of the processor after pre-analysis , including an instruction interface module used as an interface to exchange data with an instruction cache outside the processor, a prefetch module for pre-reading multiple instructions and caching them, and an instruction distribution module, wherein the instruction distribution module adopts a sequential multi-issue scheme; this part Send non-read-write instructions to the computing pipeline, and send read-write instructions to the read-write pipeline;

The decoding part, which mainly includes four register modules and two decoder-type modules, is used to process the instructions sent by the fetching part, translate these instructions into specific control signals, and read the register modules. data, and then send these control signals and data to the execution part of the two pipelines; the register modules include a general-purpose register module for storing 32-bit data, a first parallel register module and a second parallel register module for storing 128-bit data , and parameter register modules for storing 32-bit parameters, these modules are shared by two pipelines; the decoder type modules include the first decoder module belonging to the calculation pipeline and the second decoder module belonging to the read and write pipeline , the two decoder modules respectively translate the instructions received by the corresponding pipelines, and each read the required data from the required register modules, and then send the control signals and data corresponding to the pipelines to the execution part of the respective pipelines ;

The execution part, which is used to perform specific calculations or memory access operations according to the control signals and data sent by the decoding part, and then send the calculation results and control signals to the write-back part of the two pipelines. The execution part of the calculation pipeline includes Parallel computing unit module, the parallel computing unit module adopts a mixed bit width design, supports parallel computing of data with multiple bit widths up to 256 bits; the execution part of the read and write pipeline includes the first stage of the read and write control unit module, this stage It is used to access the data cache outside the processor according to the control signal and data sent by the decoding part, while other parts of the module work in the write-back part of the read-write pipeline;

The write-back part is used to write the calculation results sent by the calculation pipeline and the execution part of the read-write pipeline back to the corresponding register module contained in the decoding part according to the control signal, wherein the write-back part of the read-write pipeline includes read-write control The second stage of the unit module, which is used to return the result obtained by accessing the external data cache in the first stage to the processor and store it in the register module.

Further, as shown in Figure 1, the post-quantum cipher algorithm special processor based on RISC-V also includes six register groups, wherein the first instruction fetching to decoding register group is used for temporarily storing the instruction fetching part to be sent to Calculate the signals and data of the decoding part of the pipeline, the second fetch to the decoding register group is used to temporarily store the signals and data to be sent to the decoding part of the reading and writing pipeline, and the first decoding to the execution register group It is used to temporarily store the signals and data sent by the decoding part of the calculation pipeline to the execution part of the calculation pipeline, and the second decoding to the execution register group is used to temporarily store the decoding part of the read-write pipeline to be sent to the execution part of the calculation pipeline The signals and data, the first execution to the write-back register group is used to temporarily store the signals and data to be sent to the write-back part by the execution part of the calculation pipeline, and the second execution to the write-back register group is used to temporarily store the execution of the read-write pipeline The signal and data to be sent by the section to the writeback section.

As shown in Figure 2, the parallel computing unit module of the execution part of the post-quantum cryptography algorithm processor in the embodiment of the present invention adopts component reorganization technology and operator fusion technology to realize, and uses the same component to realize different computing types and bit widths. The core operation of the post-quantum cryptography algorithm, this module includes:

The preprocessing module is used for data transformation before calculation of NTT (fast number theory transformation) and keccak algorithm;

Post-processing module, used for data transformation after calculation of NTT and keccak algorithms;

The processing module, including the main computing resources, is composed of a 64-bit shifter module used to realize the shift operation and 8 identical subunit modules used to realize other computing operations; each subunit module contains a A 32-bit multiplier module for multiplication-related operations, a 32-bit carry-save adder module for modulo and logic operations, and two 32-bit adder modules for addition and subtraction; between these modules there is Optional connection methods, several modules in the processing module have multiple connection methods, which are respectively used to support the calculation operations in different operations of different bit widths required in the post-quantum cryptography algorithm, and can be obtained according to the instructions obtained by the fetching part. Different, the decoding part translates the difference between the translated specific calculation operation and the corresponding control signal, and the processing module in the execution part will select a different connection method according to the corresponding connection method of the control signal, so as to execute different bits. A wide range of different computing operations to obtain computing results.

As shown in Figure 3, the parallel computing unit module, the first parallel register module, and the second parallel register module in the embodiment of the present invention form a mixed bit-width parallel storage system and data flow, wherein the first parallel register module, the second The parallel register module logically includes 16 128-bit registers, and each 128-bit register is physically composed of two 64-bit registers. When performing parallel computing operations on the computing pipeline, the parallel computing unit module can perform up to 8 groups of operations at the same time, and each group is an operation between two 32-bit numbers, so the total input is two 256-bit operands of input A and input B , each operand is concatenated from the 128-bit number provided by parallel register 1 and the 128-bit number provided by parallel register 2. When performing read and write operations in the read and write pipeline, the read and write control unit module reads 128-bit data from external storage and stores it in parallel register module 1 or parallel register module 2, or reads 32-bit data from external storage and stores it in parallel register module 2. Into the parameter register; when the read-write pipeline performs a write operation, the read-write control unit module writes the value of a 128-bit register in the parallel register module 1 or parallel register module 2 into the external storage during the write operation. Different storage and computing bit widths improve the load balance between computing and reading and writing pipelines in operations such as NTT, which can save bandwidth and improve resource utilization.

As shown in Figure 4, in the embodiment of the present invention, a post-quantum cryptography algorithm special instruction supported by the present invention is introduced. The 64-bit result is the value of A^(~B&C). The calculation operation corresponding to this instruction is a step in the core operation keccak operation commonly used in the post-quantum cryptography algorithm. Figure 4 shows the connection and combination methods adopted by the processing modules of the parallel computing unit module when executing the operation corresponding to the instruction, that is, splicing the 32-bit carry-save adders in the four subunit modules shown in Figure 2, Two 64-bit carry-save adders are formed and connected as shown in Figure 4. The inverting module connected to B shown in FIG. 4 is not marked in FIG. 2 , and there are many other similar unmarked auxiliary circuits, all of which are common technologies in the field.

As shown in Figure 5 and Figure 6, the embodiment of the present invention introduces the superscalar pipeline architecture of the separation of reading and writing and calculation for the core operation NTT (fast number theory transformation) operation commonly used in post-quantum cryptography algorithms. How to speed up the execution of this operation. Figure 5 shows the instruction emission sequence of the butterfly unit calculation that needs to be executed repeatedly during the NTT operation process, in which IF, ID, EX, and WB correspond to the four instruction fetching, decoding, execution, and writing back shown in Figure 1, respectively. part. Each butterfly unit calculation needs to multiply the two input data A and B and then sum and difference to obtain two outputs C and D, where C=A+(B*w), D=A-(B* w), where w is a known constant called the twiddle factor. The two instructions corresponding to the two adjacent and aligned rows in Figure 5 are a calculation instruction and a read and write instruction executed in parallel, such as the calculation instruction mulvh in the first row and the read and write instruction S1b in the second row. In the instruction fetch IF stage shown in Figure 1, the instructions will be sent to the calculation pipeline and the read-write pipeline by the instruction distribution module, and run in parallel at the same time, so that the processor can simultaneously execute two instructions of calculation and reading and writing. As can be seen in Fig. 5, each butterfly unit calculation includes 7 calculation instructions and 8 read and write instructions, which need to be carried out in turn in a traditional single-pipeline processor, and it takes 15 cycles to complete, while in the present invention, both It only takes 8 cycles to complete, which nearly doubles the running speed. In addition, the 7 computing instructions adopted are: mulvh, mulv, mulvm, mulvhf, subv, addmv, submv. These seven instructions are parallel computing instructions with a bit width of 256 bits, compared to only 32 The common 32-bit processor of 1-bit data, the present invention can calculate 8 groups of 32-bit data at a time, so each instruction can provide eight times of parallel acceleration. FIG. 6 shows a specific assembly instruction flow corresponding to a butterfly unit calculation in an NTT calculation performed in an embodiment of the present invention.

The above-mentioned embodiments only express several implementation modes of the present invention, and the description thereof is relatively specific and detailed, but should not be construed as limiting the patent scope of the present invention. The present invention can support various post-quantum cryptography algorithms and various core operations contained therein, and correspondingly has dozens of special-purpose extended instructions not yet listed and corresponding combinations of components in the processing module in the parallel computing unit module. For those skilled in the art, without departing from the concept of the present invention, several modifications and improvements can be made, and these all belong to the protection scope of the present invention.

Claims (4)

1. A post-quantum cryptography algorithm-specific processor based on RISC-V, characterized in that it adopts a superscalar pipeline design that separates reading and writing and computing, and has two pipelines that can be executed in parallel for reading and writing and computing, and each pipeline has Instruction fetching, decoding, execution, and write-back four parts of sequential execution, the processor specifically includes: Instruction fetching part, reading and writing and computing pipelines multiplex the same instruction fetching part, which is used to obtain instructions from the instruction cache outside the processor, and distribute instructions to the decoding part of the two pipelines of the processor after pre-analysis , including an instruction interface module used as an interface to exchange data with an instruction cache outside the processor, a prefetch module for pre-reading multiple instructions and caching them, and an instruction distribution module, wherein the instruction distribution module adopts a sequential multi-issue scheme; this part Send non-read-write instructions to the computing pipeline, and send read-write instructions to the read-write pipeline; The decoding part, which mainly includes four register modules and two decoder-type modules, is used to process the instructions sent by the fetching part, translate these instructions into specific control signals, and read the register modules. Data, and then send these control signals and data to the execution part of the two pipelines; the register module is shared by the two pipelines; the decoder type module includes the first decoder module belonging to the calculation pipeline and the first decoder module belonging to the read and write pipeline Two decoder modules, these two decoder modules respectively translate the instructions received by the corresponding pipelines, and respectively read the required data from the required register modules, and then send the control signals and data corresponding to the pipelines to the execution part of the respective pipeline; The execution part, which is used to perform specific calculations or memory access operations according to the control signals and data sent by the decoding part, and then send the calculation results and control signals to the write-back part of the two pipelines. The execution part of the calculation pipeline includes Parallel computing unit module, the parallel computing unit module adopts a mixed bit width design, supports parallel computing of data with multiple bit widths up to 256 bits; the execution part of the read and write pipeline includes the first stage of the read and write control unit module, this stage It is used to access the data cache outside the processor according to the control signal and data sent by the decoding part, while other parts of the module work in the write-back part of the read-write pipeline; The write-back part is used to write the calculation results sent by the calculation pipeline and the execution part of the read-write pipeline back to the corresponding register module contained in the decoding part according to the control signal, wherein the write-back part of the read-write pipeline includes read-write control The second stage of the unit module, which is used to return the result obtained by accessing the external data cache in the first stage to the processor and store it in the register module. 2. post-quantum cryptographic algorithm special processor according to claim 1, is characterized in that, the register module of described decoding part comprises the general-purpose register module that is used to store 32-bit data, is used to store the first of 128-bit data A parallel register module and a second parallel register module, and a parameter register module for storing 32-bit parameters, these modules are shared by two pipelines. 3. The special processor for post-quantum cryptography algorithm according to claim 1, characterized in that, said parallel computing unit module adopts component reorganization technology and operator fusion technology to realize, and uses the same component to realize different computing types and Bit-wide post-quantum cryptography algorithm core operation, this module includes: The preprocessing module is used for data transformation before calculation of NTT (fast number theory transformation) and keccak algorithm; Post-processing module, used for data transformation after calculation of NTT and keccak algorithms; The processing module, including the main computing resources, is composed of a 64-bit shifter module used to realize the shift operation and 8 identical subunit modules used to realize other computing operations; each subunit module contains a A 32-bit multiplier module for multiplication-related operations, a 32-bit carry-save adder module for modulo operations and logic operations, and two 32-bit adder modules for addition and subtraction; each of the processing modules The module has a variety of connection methods, which are respectively used to support the calculation operations in different operations of different bit widths required in the post-quantum cryptography algorithm. According to the different instructions obtained by the fetching part, the decoding part translates the specific calculation operations and After receiving the corresponding control signal, the processing module in the execution part will select the corresponding connection mode according to the control signal, so as to perform different calculation operations with different bit widths to obtain calculation results. 4. post-quantum cryptographic algorithm special processor according to claim 1, is characterized in that, described parallel computing unit module and the first parallel register module, the second parallel register module have formed the parallel storage system of mixed bit width and Data flow, in which the first parallel register module and the second parallel register module logically contain 16 128-bit registers, and each 128-bit register is physically composed of two 64-bit registers; parallel computing is performed on the computing pipeline During operation, the parallel computing unit module can perform up to 8 groups of operations at the same time, and each group is an operation between two 32-bit numbers, so the total input is two 256-bit operands of input A and input B, and each operand is composed of The 128-bit number provided by the first parallel register module and the 128-bit number provided by the second parallel register module are spliced together; when the read-write pipeline performs read-write operations, the read-write control unit module reads from the external storage during the read-out operation. 128-bit data is stored in the first parallel register module or the second parallel register module, or 32-bit data is read from external storage and stored in the parameter register module; when the read-write pipeline performs write operations, the read-write control unit module is writing The operation writes the value of a 128-bit register in the first parallel register module or the second parallel register module to the external storage.

Images