CN102122241A - Analog multiplier/divider applicable to prime field and polynomial field - Google Patents

Abstract

The invention relates to a dual-domain modular multiplication modulus divider for ECC (elliptic curve cryptography) algorithm that is suitable for high-speed network applications and portable mobile device applications. It consists of 4 PE computing units, 5 register files Regfile, and Booth encoding Unit, input register Load file, control module control and 17 multiplexers, which are used to change the connection between the four PE operation units and the reading position of the data to complete modular division or modular multiplication Operation, with scalability, can support up to 480-bit modular multiplication and division operations. Modular multiplication and modular division operations can share hardware units to reduce hardware area; addition, subtraction and shift operations of long operands in the algorithm All are carried out in units of words, which greatly accelerates the convergence speed of the algorithm, thus doubling the operation speed.

Description

A Modular Multiplication and Modulo Divider Applicable to Prime Fields and Polynomial Fields

technical field

The invention belongs to the technical field of integrated circuit design, and in particular relates to a dual-domain modulus multiplier and divider for elliptic curve cryptography (ECC) algorithms, which is suitable for high-speed network applications and portable mobile device applications.

Background technique

In contemporary times, with the deepening of informatization, more and more information will be exposed in public media. In order to protect those sensitive information, various cryptographic algorithms are applied to the field of wireless network communication. However, the relatively limited processing capabilities of communication devices, especially portable devices, cannot meet the demand for increasing data volume.

Cryptosystems can generally be divided into two types: symmetric cryptosystems and public key cryptosystems. The biggest advantage of the symmetric cryptosystem is high efficiency, but the main disadvantage is quite obvious: the key distribution problem, that is, the channel for distributing the key is required to be both confidential and authentic; another shortcoming is the key management problem, that is, in the In a network with N entities, each entity must access the keys of N-1 entities. However, public key cryptography does not have these shortcomings. Public key cryptography only requires the exchange of keys to be authentic, not confidential, and provides confidentiality and non-repudiation.

At present, Elliptic Curve Cryptography (ECC) has become one of the most popular public key ciphers besides RSA cryptography, and it can provide the same function as RSA cryptosystem. Its security is built on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP). It is generally accepted that 160-bit elliptic curve ciphers provide a level of security equivalent to 1024-bit RSA ciphers. Because the key is short, the encryption and decryption speed is faster in practical applications, and power consumption, bandwidth and storage space can be saved. The core operations of the ECC algorithm are modular multiplication and inversion, and the performance of modular multiplication and inversion is related to the performance of the entire ECC chip. In addition, the time parallelism of the ECC algorithm is more obvious. A high-performance and full-featured modular multiplication invertor, and fully explore the parallelism of the algorithm time, can obtain high encryption speed with only a small hardware cost, and meet the needs of current high-speed network applications. In addition, due to the low hardware consumption and low power consumption, it can also adapt to the application needs of portable mobile devices. With the development of computer technology, the calculation speed is also increasing rapidly. It is necessary for us to increase the data length to strengthen the security of the encryption algorithm. This design has scalability in the hardware structure, and can easily expand the data width.

Contents of the invention

The purpose of the present invention is to propose a dual-domain modulo multiplier modulo divider for the Elliptic Curve Cryptography ECC algorithm suitable for high-speed network applications and portable mobile device applications, which has scalability and significantly reduces hardware costs.

The technical scheme of the present invention is: a kind of modulus multiplication modulus divider (as shown in Figure 1) that is applicable to prime field and polynomial field, by 17 multiplexers (1～17), 4 computing units PE (26 ～29), input register (23), 5 register files (18～22), Booth encoding unit (24) and control module (25); Wherein:

a. When the second multiplexer (2) and the eighth multiplexer (8) select 1 state, and 13 multiplexers (3～7, 10～17) select 0 state, by the first multiplexer Way selector (1), ninth multiplexer (9), 5 register files (18-22), input register (23), Booth encoding unit (24), control module (25) and 4 PE operations Units (26-29) form a modulus divider (see Figure 5), and the modulo division operation adopts the Euclidean algorithm; wherein:

The first multiplexer (1), the input is the output of the arithmetic unit PE0 (26), the output is selected by the stage signal, and output to the first register file (18) or the second register file (19);

The ninth multiplexer (9), the input is the output of the arithmetic unit PE2 (28), the output is selected by the stage signal, and the output is to the third register file (20) or the fourth register file (21);

The output of the first register file (18) and the second register file (19) is all to the input register (23);

The outputs of the third register file (20) and the fourth register file (21) are all to the PE3 arithmetic unit (29);

The output of the fifth register file (22) is to Booth encoder (24);

The output of the input register (23) is to the PE0 arithmetic unit (26);

Booth encoding unit (24) is output to PE2 computing unit (28);

The control module (25) is output to PE0 and PE1 computing units (26, 27);

The output of the PE0 arithmetic unit (26) is written into the first register file (18) or the second register file (19) according to the selection of the stage signal;

The output of PE1 arithmetic unit (27) is to PE2 arithmetic unit (28);

The output of the PE2 arithmetic unit (28) is written into the third register file (20) or the fourth register file (21) according to the selection of the stage signal;

The output of PE3 arithmetic unit (29) is to PE1 arithmetic unit (27);

b. When the first multiplexer (1) and the ninth multiplexer (9) are not working, and 13 multiplexers (3～7, 10～17) are in 1 state, the second multiplexer Selector (2), eighth multiplexer (8), 5 register files (18-22), input register (23), Booth encoding unit (24), control module (25) and 4 PE operation units (26～29) form modular multiplier (seeing Fig. 6), and modular multiplication operation adopts Modular Gomery algorithm; Wherein:

The second multiplexer (2), the input is the data stored in the first register file (18) and the fourth register file (21), with First_round as the selection signal, selects the correct data to output in the input register (23) ;

The eighth multiplexer (8), the input is the data stored in the second register file (19) and the fifth register file (22), and uses First_round as the selection signal to select and output the correct data into the input register (23) ;

The third register file (20) is output in the Booth encoder (24);

Two bits of the input register (23) are output to the PE0 arithmetic unit (26);

The output of the Booth coding unit (24) provides input for 4 PE computing units (26～29) respectively;

The output of PE0 arithmetic unit (26) is to PE1 arithmetic unit (27);

The output of PE1 arithmetic unit (27) is to PE2 arithmetic unit (28);

The output of PE2 computing unit (28) is to PE3 computing unit (29);

The outputs of the PE3 arithmetic unit (29) are sent to the fifth register file (22) and the fourth register file (21) respectively.

The above arithmetic unit PE (as shown in Figure 2) consists of 6 multiplexers (30-35), 2 registers (36, 37), 2 inverting controllers (38, 39), 3 carry-save addition device (40, 41, 42), PE internal control module (43) and PE internal shifter (44); wherein:

The input of the eighteenth multiplexer (30) is the multiple mul_h of the accumulated multiplicand during the modular multiplication operation and the multiple div_h of the accumulated D register value during the modular division operation, and is selected by the operation function Func_sel to select the correct W register The multiple selection signal of the value is output to the selection control terminal of the nineteenth multiplexer (31);

The input of the nineteenth multiplexer (31) is the value of 0, the W register and the value of the 2*W register, and the output of the eighteenth multiplexer (31) is used as a selection signal to select the correct operand value To the first inverting controller (38);

The input of the twentieth multiplexer (32) is the multiples double1 and double2 of the modulus P during the word operation, and is selected by the operation function Func_sel, and outputs the correct multiple selection signal to the twenty-third multiplexer (35);

The input of the twenty-first multiplexer (33) is the multiples zero1 and zero2 of the modulus P during the word operation, and is selected by the operation function Func_sel, and outputs the correct multiple selection signal to the twenty-third multiplexer (35) ;

The input of the twenty-second multiplexer (34) is the multiples neg1 and neg2 of the modulus P during the word operation, and is selected by the operation function Func_sel, and outputs the correct multiple selection signal to the second inverting controller (39);

The input of the twenty-third multiplexer (35) is the value of 0, modulo P and 2*modulo P, and is selected by the output of the twentieth and twenty-first multiplexer (32,33) signal, select the correct operand value to the second inverting controller (39);

The seventh register (36) is used to store the value of a word in the modulo P during operation;

The eighth register (37) is used to store the value of a word in W when computing;

The input of the first inverting controller (38) is the output value of the 19th multiplexer (31), and the control signal is the output value of the 18th multiplexer (30), and the output is after the input is reversed. value;

The input of the second inverting controller (39) is the output value of the twenty-third multiplexer (35), and the control signal is the output value of the twenty-second multiplexer (34), and the output is the input value after taking reversed value;

The input of the first carry reserve adder (40) is the result and the carry (Uc, Us) of the current word of the U register that preserves an operand, and the field selection signal Field of the prime field or the polynomial field, the first word First_word, and The output of the first inverting controller (38), the output is the value Us_1 and the carry Uc_1 by the carry save adder;

The input of the second carry save adder (41) is the output Uc_1 of the first carry save adder (40), Us_1, the field selection signal Field of the prime field or the polynomial field, the first word First_word, and the second inversion control The output of the device (39), the output is the value Us_2 and the carry Uc_2 of the adder saved by the carry;

The input of the third carry save adder (42) is the input Uc_3, Us_3 and carry of the PE internal shifter (44), and the output is the value Us_out and the carry Uc_out through the carry save adder;

The input of the PE internal control module (43) is the lower two bits of the output Us_1 and Uc_1 of the first carry reserve adder (40), and the lower two bits of the modulus P, the value of the number shift of the right shift, and the output is to determine the following A control signal of a multiple of the added modulo P;

The input of the PE internal shifter (44) is the value of the output value Us_2, Uc_2 of the second carry save adder (41), and the value of the digit shift of the right shift, and the output is Us_3, Uc_3 and Us_3 after the right shift. The value of the carry that is shifted to the right.

The dual-domain modular multiplication modulus divider for the ECC (elliptic curve cryptography) algorithm proposed by the present invention is suitable for high-speed network applications and portable mobile device applications, and can perform up to 480-bit modular division operations, using SMIC 0.18μm CMOS technology In general, the critical path delay is 4.71 nanoseconds, the highest frequency is 212.3MHz, it takes 13us to complete 256-bit module division, and the area is 37k equivalent gates, and the time for 256-bit module multiplication is 1.4us, and the area is 11.4k equivalent gates .

The ECC algorithm is a public key algorithm. The main operations in ECDH and ECDSA focus on the point multiplication operation, and the point multiplication is composed of point doubling and point addition, and the doubling and point addition operations are mainly under the finite field. Modular multiplication and modular division algorithms. It is the best compromise between performance and flexibility to use hardware to complete the modular multiplication and modular division algorithm of finite fields, and use software to implement different public key algorithms in the upper layer. The algorithm commonly used to deal with finite field modular division is mainly the Euclidean algorithm, and the specific algorithm implementation is shown in Figure 3; while the algorithm for dealing with finite field modular multiplication is mainly the Montgomery modular multiplication algorithm, and the specific algorithm implementation is shown in Figure 4.

The present invention has the advantage that it can simultaneously handle the modular multiplication and modular division operations in the prime field and the binary field in the ECC operation. The main operation components are composed of PE operation units with the same structure, and the connection relationship between the operation units can be reconfigured. , can correspondingly accelerate the speed of different algorithms; at the same time, it can also achieve hardware multiplexing as much as possible, and reduce the hardware area while meeting the performance requirements.

The advantage of the present invention also is to propose a kind of computing unit PE unit that specially handles modular multiplication and modular division in the ECC computing, by analyzing the computing process under prime domain and binary domain, has extracted the basic operation in the computing: U=(U +mul_h*W+kP)>>shift operation. Each PE operation unit can complete this basic operation. When performing modular multiplication and modular division, the operation of each PE unit can be reasonably allocated to speed up the modular multiplication and modular division operation.

The third advantage of the present invention is that the main operation part of the modular multiplication module divider is made up of a plurality of PE operation units with the same structure, and the structure is configurable (illustrated with four PE operation units in Fig. 1), and can be configured according to hardware or power According to the requirements, the PE operation unit is increased or decreased accordingly to meet the new requirements.

Description of drawings

Fig. 1 is a top-level structural diagram of a dual-domain modulus multiplier and divider of the present invention;

Fig. 2 is the structural diagram of the PE operation unit of the dual-domain modular multiplication modulus divider of the present invention;

Fig. 3 is the improved Euclidean modular division algorithm of the present invention;

Fig. 4 is the improved Montgomery modular multiplication algorithm of the present invention;

Fig. 5 is the equivalent hardware structure diagram when the double-field modulus multiplier modulo divider of the present invention is done modulo division;

Fig. 6 is the equivalent hardware structure figure when doing modular multiplication by the dual domain modular multiplication modulus divider of the present invention;

Fig. 7 a is the algorithm explanatory diagram of data path when the present invention carries out modulo division operation;

Figure 7b is an equivalent explanatory diagram of Figure 5;

Fig. 8 a is the algorithm explanatory diagram of data path when the present invention carries out modular multiplication operation;

FIG. 8b is an equivalent explanatory diagram of FIG. 6 .

Numbers in the figure: 1 is the first multiplexer, 2 is the second multiplexer, 3 is the third multiplexer, 4 is the fourth multiplexer, 5 is the fifth multiplexer, 6 is the sixth multiplexer, 7 is the seventh multiplexer, 8 is the eighth multiplexer, 9 is the ninth multiplexer, 10 is the tenth multiplexer, and 11 is the eleventh multiplexer 12 is the twelfth multiplexer, 13 is the thirteenth multiplexer, 14 is the fourteenth multiplexer, 15 is the fifteenth multiplexer, and 16 is the sixteenth multiplexer Way selector, 17 is the seventeenth multiplexer, 18 is the first register file, 19 is the second register file, 20 is the third register file, 21 is the fourth register file, 22 is the fifth register file, 23 is the input register, 24 is the Booth coding unit, 25 is the control module, 26 is the PE0 operation unit, 27 is the PE1 operation unit, 28 is the PE2 operation unit, 29 is the PE3 operation unit, 30 is the eighteenth multiplexer, 31 For the nineteenth multiplexer, 32 for the twentieth multiplexer, 33 for the twenty-first multiplexer, 34 for the twenty-second multiplexer, and 35 for the twenty-third multiplexer 36 is the seventh register, 37 is the eighth register, 38 is the first inverting controller, 39 is the second inverting controller, 40 is the first carry save adder, 41 is the second carry save adder, 42 is the third carry reserve adder, 43 is the PE internal control module, and 44 is the PE internal shifter.

Detailed ways

Further illustrate the present invention below in conjunction with accompanying drawing.

Fig. 1 is the top-level structural diagram of the double-field modulus multiplication modulus divider of the present invention, and main computing unit is PE0 (26), PE1 (27), PE2 (28) and PE3 (29) four computing units, four computing unit structures The same (see Figure 2), and can accelerate the completion of the basic operations of modular multiplication and modular division. The modular multiplication and modulus divider can complete the modular multiplication and modulus division operations under the prime field and the binary field. Data such as result (division result) and modulus are all stored in five register files (18～22). The Booth coding unit is used to provide the value of mul_h used in the modular multiplication operation, and the Control unit is used to provide the value of div_h used in the modular division operation. The 17 multiplexers (1~17) are used to change the connection between the four PE operation units and the reading position of the data to complete the modular division or modular multiplication operation. The entire ECC modular multiplication and modulus division can be reconfigured The connection paths between units are used to complete different algorithms.

1. Modulus status

Modulo division state is by the first, the 9th multiplexer (1,9), five register files Regfile (18～22), input register (23), Booth encoding unit (24), control module (25), four Consists of four PE computing units (26-29), the data path is as shown in accompanying drawing 5, the completed modulus division algorithm is as shown in accompanying drawing 7a, and the top-level explanatory diagram during modulus division is as shown in accompanying drawing 7b, wherein:

The input of the first multiplexer (1) is the result calculated in PE0, which is selected by the stage signal, and writes the input result into Regfile1 or Regfile2.

The ninth multiplexer (9), the input is the result calculated in PE2, selected by the stage signal, and writes the input result into Regfile3 or Regfile4.

The first register file (18), when the stage signal is 0, stores the calculation result and the carry (Cc, Cs) in the C register initialized with the divisor, and when the stage signal is 1, what stores is initialized with the modulo P The calculation result and carry (Dc, Ds) in the D register; the input is the calculation result of PE0, which is output to the input register (23).

The second register file (19), when the stage signal was 0, stored the calculation result and the carry (Dc, Ds) in the D register initialized with the modulo P, and when the stage signal was 1, what stored was initialized with the divisor The calculation result and the carry (Cc, Cs) in the C register; the input is the calculation result of PE0, which is output to the input register (23).

The third register file (20), when the stage signal is 0, stores the calculation result and the carry (Uc, Us) in the U register initialized with the dividend, and when the stage signal is 1, stores the W initialized with 0 The calculation result and carry (Wc, Ws) in the register; the input is the calculation result of PE2, and it is output to the PE3 arithmetic unit.

The fourth register file (21), when the stage signal is 0, stores the calculation result and the carry (Wc, Ws) in the W register with 0 initialization, and when the stage signal is 1, what stores is the U initialized with the dividend The calculation result and carry (Uc, Us) in the register; the input is the calculation result of PE2, and it is output to the PE3 arithmetic unit.

The fifth register file (22), when the stage signal is 0 or 1, all stores the value of the modulo (0, P); it is output to the Booth encoder (24).

Input register (23), the input is first, the output result of the second register pile (18,19); Output in PE0 operation unit.

Booth encoding unit (24), when Func sel is modular multiplication operation, multiplier is encoded as Booth encoder; And when modular division operation, only uses as register; Input is the result of the 5th register file (22); Output to the PE2 computing unit.

The control module (25) provides the calculation required parameter divh for the PE0 and PE1 calculation units, and outputs to the PE0 and PE1 calculation units.

PE0 arithmetic unit (26), completes C=(C+div_h*D)>>shift operation, input the value from the output (C, D) of input register (23), and the output divh of control module (25); Output The result (Cc, Cs) calculated by the carry adder is reserved; it is written into the first register file (18) or the second register file (19) according to the selection of the stage signal.

PE1 operation unit (27), completes U=U+div_h*W operation, and the value that input is (U, W) comes from PE3 operation unit (29), and the output div_h of control module (25); Output is to preserve the carry adder The calculated results (Uc, Us) are output to the PE2 arithmetic unit (28).

PE2 arithmetic unit (28), completes U=(U+kP) >> shift operation, input is the output of PE1 arithmetic unit (27), and the input module P of Booth encoding unit; Output is the result ( Cc, Cs); write to the third (20) or fourth register file (21) according to the selection of the stage signal.

The PE3 computing unit (29) only finishes storing the data in the read third register file (20) or the fourth register file (21); and outputs to the PE1 computing unit (27).

When carrying out modulo division operation, the connection relationship of four PE units is as shown in accompanying drawing 5 after the selection of multiplexer, and PE0 computing unit (26) completes C=(C+div_h*D)>>shift operation, And PE1, PE2 cooperate, finish the calculation to register U, wherein PE1 finishes the operation of U=(U+divh*W), PE2 operation unit (28) finishes the operation of U=(U+kp)>>shift, PE3 uses Used as data memory.

When performing modulo division operation, the basic idea is as follows (see Figure 3): for known X, Y, P, find Z=X/Ymod P. Two equations are used: CX≡UY mod P and DX≡WY mod P. When initializing C=Y, U=X, D=P, W=0, then use the extended Euclidean algorithm to convert gcd(C, D) into gcd(0, 1) or gcd(0, -1), where In the process, W and U do the linear transformation under the corresponding prime domain, and finally get W=X/Y mod P or W=-X/Y mod P.

The basic operations used in the modular division algorithm are: C=(C+div_h*D)>>shift; U=U+div_h*W; U=(U+kP)>>shift, which has a similar structure, so the design A basic operation unit that can complete the operation of X=(X+kY)>>shift, so that the operation requirement of modulo division can be completed. In consideration of obtaining the maximum parallelism of operations, four PE operation units (26-29) perform corresponding operations, and the control module (25) provides operation units with the required parameters div_h, five register files (18-22) To store the data required for operation, due to the consideration of scalability and flexibility, the multi-bit modulo operation in the operation is decomposed into word-level operations. Then the hardware unit for the modulo division operation is obtained, see Figure 5, the top-level simplified The figure is shown in accompanying drawing 7b.

The designed PE operation unit has a similar operation structure and can complete the operation of Z=(Z+mX+nY)>>shift, as shown in FIG. 1 . In this way, the PE operation unit also satisfies the operation requirements in the division.

The PE0 operation unit (26) completes C=(C+div_h*D)>>shift operation, and the operands C, D, div_h and shift are all provided by the external control module and the register file. Each clock completes the C=(C+div_h*D)>>shift operation of a word. In order to ensure that it can work at a higher clock frequency, the operation uses the carry-save adder CSA, so the result contains two parts. The result of the operation and the carry result are each 32 bits, and these two parts of the value are temporarily stored in the register file.

The PE1 computing unit (27) completes the operation of U=(U+div_h*W), and the operands U, W and div_h are all provided from the external control module and other computing units. Each clock completes the operation of U=(U+div_h*W) of a word. The operation result includes the result of the operation and the carry (Uc, Us), and the result is written into the next operation unit PE2 to complete the subsequent operation. Form a small two-stage pipeline.

The PE2 arithmetic unit (28) completes the operation of U=(U+kp)>>shift, and the operands U, P, k and shift come from other arithmetic units or external register files. Each clock completes the operation of U=(U+kp)>>shift of a word. The operation result includes the operation result and the carry (Uc, Us), and temporarily stores the two parts of the result in the external register file.

PE3 calculation unit (29) completes the data storage function at this moment, and no longer participates in calculation, can be consistent with algorithm like this, and does not need to add more hardware structures to store the calculation data of PE1 calculation unit (26).

The operation operands required at this time are C, D, U, W, P, div_h and shift, among which C, D, U and W need to store the initial value on the one hand, and on the other hand, they also need to process C and D, U For the exchange of data with W, five register files are used in the implementation. In order not to add too much area, the stage signal is used to distinguish, and the register files are multiplexed in the division.

The first register file (18) has 16 64-bit registers. When the stage signal is 0, the data of (Cc, Cs) is stored, and when the stage signal is 1, the data of (Dc, Ds) is stored. The data.

The second register file (19) has 16 64-bit registers, when the stage signal is 0, the data of (Dc, Ds) is stored, and when the stage signal is 0, the storage is (Cc, Cs) The data.

The third register file (20) has 16 64-bit registers. When the stage signal is 0, the data of (Uc, Us) is stored, and when the stage signal is 0, the data of (Wc, Ws) is stored. The data.

The fourth register file (21) has 16 64-bit registers. When the stage signal is 0, the data of (Wc, Ws) is stored, and when the stage signal is 0, the data of (Uc, Us) is stored. The data.

The fifth register file (22) has 16 64-bit registers, and when the stage signal is 0 or 1, all data (0, P) modulo P are stored.

And Booth coding unit (24) only provides the data storage effect of modulus P now, the Booth coding unit when the modular multiplication like this reuses, needn't add temporary storage unit again specially for modulus P again.

2. Modular multiplication status

The modular multiplication state is composed of the second and the eighth multiplexer (2, 8), five register files (18-22), input register (23), Booth encoding unit (24), four PE operation units (26-22), 29) Composition, the data path is as shown in Figure 6, the modular multiplication algorithm of concrete realization is as shown in accompanying drawing 8a, and the top-level explanation diagram during modular multiplication is as shown in accompanying drawing 8b. Wherein:

The second multiplexer (2), the input is the data stored in the first register file (18) and the fourth register file (21), whether it is the signal First round of the first operation as the selection signal, selects the correct Data into the input register (23).

The eighth multiplexer (8), the input is the data stored in the second register file (19) and the fifth register file (22), whether it is the signal First_round of the first operation as a selection signal, and selects the correct data into the input register (23).

The first register file (18) stores the value (W, P) of the multiplicand W and the modulo P, and is stored in the register file by word; it is output to the second multiplexer (2).

The second register file (19) stores the value of U in the operation and the carry (Uc, Us), which is also stored in the register file by word; it is output to the eighth multiplexer (8).

The third register file (20), which stores the value (0, C) of the multiplier in the operation, is also stored in the register file by word; it is output to the Booth encoder (24).

The fourth register file (21) stores the value of the multiplicand and the modulus (W, P) stored in the operation, and the fourth register file (21) acts as a fifo during modular multiplication, and the stored data is also by word Stored in the register file; output to the second multiplexer (2).

The fifth register file (22), stored is the value of U stored in the operation and the carry (Uc, Us), and the effect of the fifth register file (22) is also a fifo during modular multiplication, and the stored data is stored in word by word In the register file; output in the eighth multiplexer (8).

The input register (23) has two 64bit data inputs, which are respectively the multiplicand and the modulus P (W, P) and the carry and result (Uc, Us) in the calculation; output to the PE0 arithmetic unit (26).

Booth coding unit (24), the input is the data in the multiplier C; The multiples mul_h0, mul_h1, mul_h2 and mul_h3 that are multiplied by W are provided for the four PE operation units respectively.

PE0 operation unit, the input is two 64bit data, which are the multiplicand and the modulus P(W, P) and the carry and result (Uc, Us) in the calculation; complete the operation U=(U+mul_h*W+kP )>>shift; the output is the calculated result and the carry (Uc, Us) and the multiplicand and the value of the modulus P (W, P), which are output to the PE1 arithmetic unit.

PE1 operation unit, the input is two 64bit data, which are respectively the multiplicand and the modulus P(W, P) and the carry and result (Uc, Us) in the calculation in PE0; complete the operation U=(U+mul_h*W +kP)>>shift; the output is the calculated result and the carry (Uc, Us) and the value of the multiplicand and the modulus P (W, P), and output to the PE2 arithmetic unit.

PE2 operation unit, the input is two 64bit data, which are respectively the multiplicand and the modulus P(W, P) and the carry and result (Uc, Us) in the calculation in PE1; complete the operation U=(U+mul_h*W +kP)>>shift; the output is the calculated result and the carry (Uc, Us) and the value of the multiplicand and the modulus P (W, P), and output to the PE3 arithmetic unit.

PE3 operation unit, the input is two 64bit data, which are respectively the multiplicand and the modulus P(W, P) and the carry and result (Uc, Us) in the calculation in PE2; complete the operation U=(U+mul_h*W +kP)>>shift; the output is the calculated result and the carry (Uc, Us) and the multiplicand and the value of the modulus P (W, P), the former is output to the fifth register file (22), and the latter is output to In the fourth register file (21).

When performing modular multiplication, the connection relationship of the four PE units is selected by the multiplexer as shown in Figure 8b, and the four PE units form a pipeline structure, and U=(U+mul_h*W+kP )>>shift operation.

For the modular multiplication operation, under the prime field, the Montgomery modular multiplication through the base-4 Booth code is adopted, and the basic operation used in the algorithm is U=(U+mul_h*W+kP)>>shift. In order to obtain a faster calculation speed, let the four PE calculation units (26-29) perform U=(U+mul_h*W+kP)>>shift operation to form a four-stage pipeline.

According to the value of Field (prime field or polynomial field) and C, set the parameter value required for this accumulation operation. Where mul_h represents the multiple of the multiplicand when accumulating. The parameter shift indicates the number of digits to be shifted right by U after this accumulation. The determination method of parameter k is the same as algorithm 1, and the purpose is to make the lowest shift bit of the value after U+kP be 0. The value of the parameter h is the number of digits of the multiplier. In order to make the operation result under the prime field within GF(P), the algorithm adjusts the result. However, operations under the polynomial domain will skip this step (see Figure 4).

It can be seen that this algorithm can support the modular multiplication operation in the dual field, and the modular multiplication operation in the prime field can be reduced to half of the original number of accumulation operations because of the use of booth coding. It should be noted that: in order to realize scalability and enable modular multiplication and modular division operations to share hardware units, the addition, subtraction and shift operations of long operands in Algorithm 1 and Algorithm 2 are all performed in units of words. Let the operand length be n, word length be w,

Then the vector of operands in units of words is expressed as {0, W ^(e-1) , . . . , W ⁽¹⁾ , W ⁽⁰⁾ }. The purpose of adding an all-zero word on the high bit is to prevent the result from overflowing during the addition operation. In addition, it can also be used as a sign word to facilitate the sign bit expansion after the addition result is shifted to the right.

The PE0 operation unit (26) completes U=(U+mul_h0*W+kP)>>shift operation, and the operands U, W, P, mul_h0 and shift are all provided by the external control module and the register file. Each clock completes the operation of U=(U+mul_h*W+kP)>>shift of a word. In order to ensure that it can work at a higher clock frequency, the operation uses the carry-save adder CSA, so the result contains two In the part, the result of the operation and the result of the carry are each 32 bits, and the values of these two parts are written into the next operation unit for pipeline operation.

PE1 arithmetic unit (27) completes U=(U+mul_h1*W+kP)>>shift operation, operands U, W, P, mul_h1 and shift are all provided by the external control module and last PE arithmetic unit. Each clock completes the operation of U=(U+mul_h*W+kP)>>shift of a word. In order to ensure that it can work at a higher clock frequency, the operation uses the carry-save adder CSA, so the result contains two In the part, the result of the operation and the result of the carry are each 32 bits, and the values of these two parts are written into the next operation unit for pipeline operation.

PE2 arithmetic unit (28) completes U=(U+mul_h2*W+kP)>>shift operation, operands U, W, P, mul_h2 and shift are all provided by external control module and last PE arithmetic unit. Each clock completes the operation of U=(U+mul_h*W+kP)>>shift of a word. In order to ensure that it can work at a higher clock frequency, the operation uses the carry-save adder CSA, so the result contains two In the part, the result of the operation and the result of the carry are each 32 bits, and the values of these two parts are written into the next operation unit for pipeline operation.

PE3 arithmetic unit (29) completes U=(U+mul_h3*W+kP)>>shift operation, operands U, W, P, mul_h3 and shift are all provided by external control module and last PE arithmetic unit. Each clock completes the operation of U=(U+mul_h*W+kP)>>shift of a word. In order to ensure that it can work at a higher clock frequency, the operation uses the carry-save adder CSA, so the result contains two Part, the result of the operation and the carry result are 32 bits each, and the values of these two parts are written into the register file unit for pipeline operation.

Parameters such as U, W, P, and mul_h need to be provided here, so parameters such as U, W, and P are designed and stored in the first, second, third, fourth, and fifth register files (18-22), and the four The four parameters mul_h0, mul_h1, mul_h2 and mul_h3 used by each PE operation unit are provided by the Booth coding unit (24). Within one clock, the Booth coding unit provides the mul_h value used by four computing units at a time, so that four PE computing units (26-29) form a four-stage pipeline for parallel computing. in:

The first register file (18) stores the initial multiplicand and the value (W, P) of the modulo P, and outputs to the PE0 operation unit (26) for operation.

The second register file (19) stores the carry and the result (Uc, Us) calculated by the operation unit, and outputs to the PE0 operation unit (27) for operation.

The third register file (20) stores the value (0, C) of the multiplier C, which is output to the Booth encoding unit (24), and provides the required parameters mul_h for four operations simultaneously for four PE operation units (26～29) .

The fourth register file (21) stores the value of (W, P) of the current operation in the form of fifo, and outputs it to the PE0 operation unit (26) for operation.

The fifth register file (22) stores the value of (Uc, Us) of the current operation in the form of fifo, and outputs it to the PE0 operation unit (26) for operation.

Claims (4)

1. a mould that is applicable to prime field and polynomial expression territory takes advantage of mould to remove device, it is characterized in that: it is made up of 17 MUX (1～17), 4 arithmetic element PE (26～29), input register (23), 5 register files (18～22), Booth coding unit (24) and control module (25); Wherein:

A. select 1 attitude, 13 MUX (3～7,10～17) when selecting 0 attitude in second MUX (2) and the 8th MUX (8), form mould by first MUX (1), the 9th MUX (9), 5 register files (18～22), input register (23), Booth coding unit (24), control module (25) and 4 PE arithmetic elements (26～29) and remove device, the mould division operation adopts the Euclidean algorithm;

B. do not work in first MUX (1) and the 9th MUX (9), 13 MUX (3～7,10～17) are when selecting 1 attitude, form mould by second MUX (2), the 8th MUX (8), 5 register files (18～22), input register (23), Booth coding unit (24), control module (25) and 4 PE arithmetic elements (26～29) and take advantage of device, modular multiplication adopts mould Montgomery algorithm.

2. take advantage of mould to remove device by the described mould in prime field and polynomial expression territory that is applicable to of claim 1, it is characterized in that: among the described step a:

First MUX (1) is input as the output of arithmetic element PE0 (26); Select output by the stage signal, export first register file (18) or second register file (19) to;

The 9th MUX (9) is input as the output of arithmetic element PE2 (28); Select output by the stage signal, export the 3rd register file (20) or the 4th register file (21) to;

The output of first register file (18) and second register file (19) is all to input register (23);

The output of the 3rd register file (20) and the 4th register file (21) is all to PE3 arithmetic element (29);

The 5th register file (22) output to Booth scrambler (24);

Input register (23) output to PE0 arithmetic element (26);

Booth coding unit (24) outputs to PE2 arithmetic element (28);

Control module (25) outputs to PE0 and PE1 arithmetic element (26,27);

The output of PE0 arithmetic element (26) is written to first register file (18) or second register file (19) according to the selection of stage signal;

PE1 arithmetic element (27) output to PE2 arithmetic element (28);

The output of PE2 arithmetic element (28) is written to the 3rd register file (20) or the 4th register file (21) according to the selection of stage signal;

PE3 arithmetic element (29) output to PE1 arithmetic element (27).

3. take advantage of mould to remove device by the described mould in prime field and polynomial expression territory that is applicable to of claim 1, it is characterized in that: among the described step b:

Second MUX (2) is input as the data of first register file (18) and the 4th register file (21) stored; As selecting signal, select the correct data of output with First_round in input register (23);

The 8th MUX (8) is input as the data of second register file (19) and the 5th register file (22) stored; As selecting signal, select the correct data of output with First_round in input register (23);

The 3rd register file (20) output to Booth scrambler (24);

Two of input register (23) output to PE0 arithmetic element (26);

The output of Booth coding unit (24) is respectively 4 PE arithmetic elements (26～29) input is provided;

PE0 arithmetic element (26) output to PE1 arithmetic element (27);

PE1 arithmetic element (27) output to PE2 arithmetic element (28);

PE2 arithmetic element (28) output to PE3 arithmetic element (29);

The output branch of PE3 arithmetic element (29) is clipped to the 5th register file (22) and the 4th register file (21).

4. mould according to claim 1 takes advantage of mould to remove device, it is characterized in that: described arithmetic element PE is made up of 6 MUX (30～35), 2 registers (36,37), 2 anti-phase controllers (38,39), 3 carry save adders (40,41,42), PE internal control module (43) and PE internal displacement device (44); Wherein:

The 18 MUX (30) be input as modular multiplication the time add up when adding up the multiple mul_h of multiplicand and the mould division operation multiple div_h of D register value, by operating function Func_sel as selection, select the multiple of correct W register value and select signal, output to the selection control end of the 19 MUX (31);

The 19 MUX (31) be input as 0, the value of W register and the value of 2*W register, as selecting signal, select the anti-phase controller of correct operand value to the first (38) by the output of the 18 MUX (31);

The 20 MUX (32) be input as word arithmetic the time mould P multiple double1 and double2,, export correct multiple and select signal to the 23 MUX (35) as selection by operating function Func_sel;

The 21 MUX (33) be input as word arithmetic the time mould P multiple zero1 and zero2,, export correct multiple and select signal to the 23 MUX (35) as selection by operating function Func_sel;

The 22 MUX (34) be input as word arithmetic the time mould P multiple neg1 and neg2,, export correct multiple and select the anti-phase controller of signal to the second (39) as selection by operating function Func_sel;

The 23 MUX (35) be input as 0, the value of mould P and the value of 2* mould P, by the 20, the output of the 21 MUX (32,33) is as selecting signal, selects the anti-phase controller of correct operand value to the second (39);

The value of a word among the mould P of the 7th register (36) when being used for depositing computing;

The 8th register (37) value of a word among the W when being used for depositing computing;

The output valve that is input as the 19 MUX (31) of the first anti-phase controller (38), control signal is the output valve of the 18 MUX (30), is output as input through the numerical value after the negate;

The output valve that is input as the 23 MUX (35) of the second anti-phase controller (39), control signal is the output valve of the 22 MUX (34), is output as input through the numerical value after the negate;

The result and the carry (Uc that are input as the current word of U register of preserving an operand of first carry save adder (40), Us), and signal Field is selected in the territory in prime field or polynomial expression territory, first word First_word, with the output of the first anti-phase controller (38), be output as value Us_1 and carry Uc_1 by carry save adder;

The output Uc_1 that is input as first carry save adder (40) of second carry save adder (41), Us_1, signal Field is selected in the territory in prime field or polynomial expression territory, first word First_word, with the output of the second anti-phase controller (39), be output as value Us_2 and carry Uc_2 by carry save adder;

Input Uc_3, the Us_3 and the carry that are input as PE internal displacement device (44) of the 3rd carry save adder (42) are output as value Us_out and carry Uc_out through carry save adder;

The output Us_1, the Uc_1's that are input as first carry save adder (40) of PE internal control module (43) is low two, and low two of mould P, the value of the figure place shift that moves to right, is output as and determines that the back adds the control signal of the multiple of mould P;

The output valve Us_2 that is input as second carry save adder (41) of PE internal displacement device (44), the value of Uc_2, and the value of the figure place shift that moves to right are output as the value through Us_3, Uc_3 after moving to right and the carry that moves to right out.

Images