TW448376B - Circuit and method cryptographic multiplication for computing the RSA and ECC algorithms - Google Patents

Abstract

An integrated cryptographic system (24) executes a mathematical algorithm that computes equations for public-key cryptography. An arithmetic processor (22) receives data values stored in a temporary storage memory (14) and computes both the rivest-shamir-adleman (RSA) and elliptic curve cryptography (ECC) algorithms. Multiplication cells (270 and 280) have an INT/POLY terminal that selects a C-register (246) for computing RSA modular exponentiation or ECC elliptic curve point multiplication.

Description

448376 V. Description of the invention (1) This application has been filed in the United States of America: Patent United States on December 18, 1998 under the patent application number 09 / 215,934. Background of the invention

The present invention is generally related to the public key security technology, and particularly to the integrated circuit that generates the public golden wall cipher. Key cryptographic algorithm, which can provide a high degree of security for digital data between electronic devices. RSA and £: (: (: '(Fp) modulus mathematical calculations can be calculated using hardware multipliers. Implementation, and ECC (polynomial basis F 2M) polynomial mathematical algorithms can be executed with different hardware multipliers. The two hardware multipliers used to calculate RSA and ECC algorithms can be pipelined internally. In order to respond to the large number of parallel calculations that the two algorithms will use. The low-power function provided by the multiplier of the pipeline structure is required for many applications. The hardware is used to implement the calculation of the RSA and ECC algorithms, and Not easy. So 'the type of cryptography that best fits the system determines the hardware multiplier architecture that is optimal for computing RSA or ECC algorithms. With the increase in demand for faster cryptographic operations and more efficient freshness, we need a more Hardware modular multiplier architecture 'to ensure that it improves speed and efficiency while still maintaining a high level of density. So' integrated circuits are used to implement the cryptographic multiplication system to make it rainy and cost effective. And low power will be a good way. If the multiplication system is a multiplication system that calculates RSA and ECC algorithms, it is even better. Brief description of the diagram

448376 V. Description of the invention (2) The block diagram of FIG. 1 is a specific implementation of the integrated circuit-type cryptographic system in which the RSA arithmetic processor and the ECC arithmetic processor are separate; the block diagram of FIG. 2 is within A specific implementation of the integrated circuit type cryptographic system with only a single processor to perform RS a and ECC data cryptographic calculations; the circuit diagram of FIG. 3 is a specific embodiment of a part of the single processor of FIG. 2; the circuit diagram of FIG. 4 is Figure 2 shows another embodiment of a part of a single processor; the circuit diagram of Figure 5 is a circuit diagram of a part of a multiplier used to calculate an ECC algorithm (polynomial basis F2M); the block diagram of Figure δ is I × N multiplier used to calculate RSA or ECC algorithm ♦ 9 Figure 7 is a circuit diagram of the constituent units when the C register in the multiplier of FIG. 6 is used for single-cycle multiplication; and FIG. 8 is the C register in the multiplier of FIG. 6 When the register is used for double-cycle multiplication, the circuit diagram of its constituent units. Detailed description of the preferred embodiments In general, the integrated cryptographic circuit of the present invention can provide cryptographic codes that support Wester-Domir-Adolman (RSA) and Elliptic Curve Cryptography (ECC) algorithms. Features. The integrated circuit capable of generating passwords has been applied to e-commerce, caller 'mobile circuits, smart cards and smart card terminals. Information such as personal health records, financial records, fingerprints, and retinal traces can be encrypted using integer modular multiplication, modular polynomial multiplication, addition, subtraction, and exponential operations. The integrated cryptographic circuit provides a hardware Structure to efficiently calculate RSA and ECC algorithms-

4483 7 6 V. Description of the invention (3) The block diagram of FIG. 1 is a specific embodiment of the integrated cryptosystem 10, which has an RSA arithmetic processor 18 and a separate ECC arithmetic processor 20. This single-chip cryptographic system 10 is planned to operate in a data communication network. It uses RSA or ECC algorithms to perform cryptographic functions. Cryptographic system] 〇 Contains a main interface interface box 12 ′ The input of this interface is connected to an interface bus. The cryptographic system 10 transmits and receives data signals through this data bus with other external electronic devices (not shown). For example, cryptographic system 10 external electronic devices, such as microprocessors, random access memory (RAM) 'read only memory (R0M), memory access controller (MAC), memory security management unit (SMMU) and Universal Asynchronous Receive / Transmit (UART) blocks are both to upload data to the terminal on the master interface block 2 or process the data on the terminal 12 on the master interface block. The squares connected to the outside of the password system 10 are not shown in the circle. The password system 10 also contains temporary storage memory 14, and the input of this memory is connected to the main interface interface block 12. The temporary storage memory 14 receives data that can activate the cryptographic system 10 to perform the public key cryptographic function. Therefore, the memory 14 stores data supporting the RSA modulus exponent operation and the elliptic curve point multiplication operation. These two operations are performed by the RSA arithmetic processor 18 and the ECC arithmetic processor 20, respectively. Specifically, if the RSA modulus exponent operation is to be performed, the data stored in the memory 1 4 includes, for example, the modulus value N, the values of the operands A and B, and the partial product value. If an elliptic curve point is to be performed Multiplication, then the data stored in memory 14 includes, for example, reduced polynomials, values of odd prime numbers, ECC system parameters of generator points, elliptic curve parameters, point scalers,

4483 76 V. Description of the invention (4) and temporary values. Typically, the ratio of the RSA and ECC key sizes that can be stored in the storage capacity of the memory 14 is about four to one * For example, if the memory can store a RS A key of 24 bits in size, the same The capacity can store approximately 256-bit ECC keys. Therefore, compared with the use of the ECC algorithm, the 'memory 14' can provide a higher level of security when using the RSA algorithm. Use the memory 14 to store the data required by both the RS A arithmetic processor 18 and the ECC arithmetic processor 20 'to reduce and reduce the silicon area and overall cost of the cryptographic system 10. Similar types of software instructions can also be used to calculate The ECC and RSA algorithms. For example, the RSA algorithm uses the binary square-and-multiplication subroutine when calculating the exponential function, and the ECC algorithm uses the double- and ~ plus when calculating the point multiplication. Subroutine. Therefore, similar subroutines are used for mathematical operations that support RSA or ECC algorithms. Similar things can be found among many individual algorithms, such as the integer modulus -N of RSA and the modulus multiplication in the polynomial basis of ECC. In operation, the data values stored in the memory 14 are transferred to the RS a arithmetic processor 18 or the ECC arithmetic processor 20. The control signals provided by the control circuit 16 manage the data transfer among the memory 14, the RSA arithmetic processor 18, the ECC arithmetic processor 20, and the master-side interface block 12. In addition, when processing data, the control signals generated by the control block 16 also control the mathematical calculations provided by the RSA arithmetic processor 8 and the ECC arithmetic processor 20. From another angle, 'from the control block 1 β The control signal can enable the RSA arithmetic processor 18 for calculating the RSA algorithm, or enable the RSA arithmetic processor

448376 V. Description of the invention (5) ECC arithmetic processor for calculating ECC algorithm 20 »The similarity between RSA and ECC algorithm reduces the number of control signals generated by the control circuit 1 6 The block diagram in Figure 2 is the product Another specific embodiment of the cryptographic system 24 of the type 'it has only a single arithmetic processor 22 to calculate RS A and ECC algorithms. It should be noted that the same reference numerals represent the same components. The main interface block 12 of the password system 24 is connected to other electronic devices (not shown) through an interface bus'. The data signal is transferred to the temporary storage memory 14 for storing data through the main interface interface box 12. The control signal 16 provides a control signal to the arithmetic processor 22 to manage the transfer of data in the temporary storage memory 14 and control the functions provided by the arithmetic processor 22. The INI '/ POLY signal is such a control signal generated by the control circuit 16. The INT / P0LY signal can select (or enable) the arithmetic processor 22 to perform the RSA algorithm or the mathematical operation of the ECC algorithm. Therefore, the arithmetic processor 22 provides the cryptographic function based on the RSA modulus index or the ECC elliptic curve point multiplication. FIG. 3 is a detailed implementation circuit diagram of a part of the single arithmetic processor 22 in FIG. 2. The arithmetic processor 22 performs a multiplication of the operands Λ and B, and then supplies the product values P ^ C P⑴ 'Pi + 2 and P; +3' to the modulo reducer 60. Operands A and B can be numeric data, or ordinary text strings converted into ordinal numbers using the American Standard Code for Information Interchange (ASCII), or other converted sets. The modulo reducer 60 of the arithmetic processor 22 includes an X column and an Y row adder p column, where X and Y are integers. A preferred embodiment of the adder array "quotes should be sixteen rows and six columns. It should be noted, however, that the present invention

Page 9 4483 76 V. Description of the invention (6) There is no restriction on the adder array must be sixteen rows, sixteen columns' or the number of rows and columns must be the same. For simplicity, we will simplify the modulo reducer 60 to one or four times. Four adder array with some related logic gates. Adders 90, 92, 94, and 96 form the adder array of the modular reducer 60, and adders 100, 100, 104, and 106 form the adder array of the modular reducer 60, X, and adder n 〇, 112, 114, and 116 form the adder array row of the modular reducer 60, and the adders 120, 1 22, 1 24, and 126 form the adder array row of the modular reducer 60 &. Adders 90 to ", 100 to 106: 110 to 1 6 and 120 to 126 each have a first and a second data input, a carry input (CI), a carry output (c. ), And a total output (S). Hit X. The first inputs of the adders 90, 92, 94, and 96 are connected to the input terminals 80, 82, 84, and 86, respectively. Two inputs and gates 89, 91, 93 and 7 = inputs are connected to each other 'and are connected to latch 128 in common. Outputs ^ J, 9 3 and 9 5 are connected to adders 9 0, 9 2 through and two f · 2 inputs respectively. . $ 外 'carry output (C0) of adder 90, 彳 # + connected to carry input (CI) of adder 92, adder 92 out' is connected to carry input of adder 94 through and between 92A, port: two The carry output is connected to the carry output of the adder 96 through the 94A and the data input of the flash ^ through the 96A. The turn-out of the lock 152 is connected to the carry input of the adder 90 = Impedance: Π, for example, and 90A, 92A, 94A, and 96A are also called ^ circuits. There is a choice to connect to all blocking circuits (or cause

1 side 10th stomach 4483 7 6 V. Description of the invention (7) Yes) When the signal is logic 1, the carry signal can pass through the blocking circuit. On the other hand, when the selection (or enable) signal is logic 0, the carry signal may be blocked from passing through the blocking circuit. The first inputs of the adders 100, 102, 104, and 106 of the lines 乂 are connected to the outputs of the line XDi adders 90, 92, 94, and 96, respectively. The two inputs and the first inputs of the switches 99'101'103 and 105 are connected to each other and are commonly connected to the Q output of the latch 132. The outputs of gates 99, 101, 103 and 105 are connected to the second inputs of adders 100, 102, 104 and 106, respectively. In addition, the carry output of the adder 100 is connected to the carry input of the adder 丨 00A through the AND gate, and the carry output of the adder 102 is connected to the adder 104 through the AND gate 102A. Carry input; the carry output of adder I 04 is connected to the carry input of adder 106 through the AND gate 104A. Adder 〖〇6 Carry Output ′ is connected to the data input of the latch 156 through the gate 1 06 A. The output of latch 1 5 β is connected to the carry input of adder 丨 0 〇. The first inputs of the adders 1 1 0, 1 1 2, 1 1 4 and 1 1 6 of the row X2 are respectively connected to the outputs of the adders 100, 102, 104 and 106 of the row X 2. The two inputs and the first inputs of the gates 109 '111, 113, and 115 are connected to each other and are commonly connected to the Q output of the latch 136. The outputs of the AND gates 109, Π1, η3 and 115 are connected to the second inputs of the adders U0, 112, 114 and 116, respectively. In addition, the carry output of the adder 11 〇 passes through the AND gate 丨} 〇Α is connected to the carry round of the adder Π2; the carry output of the adder 112 is connected to the carry input of the adder 114 through the AND gate 112A; Carry of adder 114: It is connected to the carry input of adder 116 through AND gate 114A. The carry output of the adder 11 6 is connected to the data of the latch 1 through the gate 丨 丨 6Α 448376 V. Description of the invention (8) Input. The output of latch 1 60 is connected to the first inputs of adders 120, 122, 124 and 126 of carry input line X3 of adder 11 0, respectively to the adders 110'112, 114, and 116 of line X2. Output. The two inputs and the first inputs of the gates 119, 121 ', 123 and 125 are connected to each other' and are commonly connected to the Q output of the latch 140. The outputs of the AND gates 119, 121, 123 and 125 are connected to the second inputs of the adders 1 2 0, 1 2 2, 1 2 4 and 1 2 6 respectively. In addition, the carry output of the adder 120 is connected to the carry input of the adder 122 through the AND gate 120A; the carry output of the adder 122 is connected to the carry input of the adder 124 through the AND gate 1 22A; the carry of the adder 124 Output 'is the carry input connected to adder 1 26 through gate 1 24A. The carry output of adder 126 is passed through the data input of latch 162 and gate 126A. The output of latch 162 is connected to the carry input of adder 120. The outputs S of the adders 120, 122, 124, and 126 are connected to the output terminals 164, 166, 168, and 170, respectively. And gates 90A-96A, 100A-106A, 110A-116A, and 120A-126A are enabled when the arithmetic processor 22 is calculating integer-modular-N multiplication; and the arithmetic processor is calculating Polynomial-based modular multiplication is disabled. In other words, when the polynomial-based modulo multiplication algorithm is being calculated, the carry output signals of the adder 90_96'100-106 and the 12_126 cannot be transmitted. The reference number of the sum gate is added with an "A". This is to indicate that each adder (such as the adder 90) has a corresponding sum gate (that is, 90A), which can affect the addition. Whether the carry output of the adder can be passed to the carry input (pass or block) of an adjacent adder. In addition, the second inputs of the gates 9, 9, 10, 1, 13 and 1 2 5 are connected to each other,

Page 12 448376 V. Description of the invention (9) It is connected to the input terminal 81 in common. The second inputs of the gates 91, 103 and 115 are connected to each other 'and are commonly connected to the input terminal 83 and the input of the latch 158. The second inputs of the gates 93 and 105 are connected to each other and are commonly connected to the inputs of the input terminal 85 and the latch 154. The second input of the AND gate 95 is the input connected to the input terminal 87 and the latch 150. The second inputs of the AND gates 99, 111 and 123 are connected to each other and are commonly connected to the output of the latch 58. The second inputs of the gates 109 and 121 are connected to each other and are commonly connected to the input terminal 85 and the output of the latch 154. The second input of the AND gate 1 19 is the output connected to the latch 158. The latches 128'132, 136, and 140 each have a set input (S), a reset input (R) ', and an output (Q). When the signal T has a high logic value such that the signal number of the output Q is the same as the signal value of the input S, the latches 128, 132, 136, and 140 are enabled. When the signal T transitions from a high logic value to a low logic value, the signal of the output Q is latched. The input r signal can reset the output Q signal. The reset inputs R of 128, 132, 136, and 140 are connected to each other and are commonly connected to the terminal 79. The terminal 79 is connected to receive the reset signal R. The two inputs and the output of the gate 130 are connected to the setting wheel of the latch 128. The first input of the AND gate 130 is connected to the first input of the adder 90. The two inputs and the output of the gate 134 are connected to the setting input of the latch 132. The first input of the AND gate 1 34 is connected to the first input of the adder 102. The two inputs and the output of the gate 138 are connected to the set inputs of the latch 136. The first input of the AND gate 1 38 is connected to the first input of the adder 1 1 4. The two inputs and the output of the gate 142 are connected to the set input of the latch 140. The first input of sum 142 is connected to the first input of adder 126.于 和 门 130 ’

Page 13 448376 V. Description of Invention (ίο) The second inputs of 134, 138 and 142 are connected to each other and are connected to the terminal 78 in common. The terminal 78 is connected for receiving the signal T. Large operands, such as, for example, the multiplication of two 1024-bit operands, are multiplied by a multiplier (not shown) and pipelined to pass or rotate. Typically, for larger operands A and B, they will be divided into smaller groups, which are called groups of numbers, for example, numbers A0- and -h. The pipelined multiplier is sized to multiply these numbers. For example, if the numbers Αβ-ΑΝ and Xin-81,. Are double digits of 16 bits, the multiplier is also a 16-bit multiplier (but the invention is not limited to this). In general terms, the integer-modulus-N Montgomery multiplication is of the form: (A * R mod N) (B * R mod Ν) + ΜΝ where = A is the first operand and is an integer; B is the The second operand is an integer; N is an odd value; mod N is the remainder of (A * B * R) / N, which can define the number of components in the finite domain; R is 2 integers greater than the value of N Power value; and \ is a reduced value '. This value should be such that (A * R mod N) (B * R moci N) + \ N is divisible by R without losing significant bits. In operation, after receiving the product of (a * R mod N) and (B * R mod N), the modulo reducer 60 generates a reduced partial product output for integer-modulus-N Montgomery multiplication. For the sake of simplicity 'we will use four-digit numbers as an example to illustrate the integer-modulus-N Montgomery multiplication. Referring to FIG. 3, input terminals 80, 82, 84

Page 14 448376 V. Description of the invention (11) and 86 receive operands, such as, for example, the respective terms of: pi + D, P1 + 1, p1 + 2, and! ^ Also, the product of multiplication with heart ^ Receiving with the rule ^ ", ^^ input into the terminal 81 '83 The modulo reducer 60 generates a reduced modulo 1 phase 2 multiplied by this, that is, the value of 'integer N. Terminals 164-170., Term' and round Out to the end of output 2: Subtractor ”. The Foster 1 Gammaley reduction algorithm is implemented. In this: = reduction algorithm, the logical value of a certain bit is described in 1. Total value. When a specific bit has a logical two, the architecture of the modulo reducer 60 allows the value to be aligned and added to the force ^ value. H is determined by adding the M, the 132, 136, and 140 and stored. In other words, when the production-subtraction product term is in the reduction process at the output terminal 1 64- 1 70, the value of ^ is determined instead of being determined before multiplying the numbers Aq and ^. For example, when A1Q = 9, U6 and N1Q = 13, the value of the (A * R mod N) term is 0001 (based on 2). When bi () = 1i, = 16 and 1 = 13, the value of the (B * R m〇d N) term is 0111. Note that we will multiply the operands A0 and BG by R first to simplify the hardware modulation problem. When the operands (A * R mod N) and (B * R mod N) are multiplied, the product terms pii3, Pi9, Pii, Pi. Becomes 01 1 1. k u μ Initially, the reset signal of terminal 79 will cause the Q outputs of latches 28, 132, 136 and 140 to become logic zero. One input of the AND gate 130 receives the product term PitQ 'with a logical value of 1 and the other input receives the signal T. And the gate 13〇 will produce a logic 1 value output, so that the latch 1 2 8 is set, that is, the Q output of the latch 1 2 8 will be a logic value 1 ^ It must be noted that in the operand Ae and the heart,

Page 15 4483 7 6 V. Description of the invention (12) That is, during the operation of multiplying the operand A0 and the lower ordinal number of the heart, the signal T is a logical value 1. It should also be noted that the output q of the latch 128 is a logic 1 value, which will cause the AND gates 89, 91, 93, and 95 to be enabled, making the value Ni +. , N ..., Niu and Ni + 3 can be sent to the second inputs of adders 90, 92, 94 and 96, respectively. Therefore, the value produced by the adder of the line "Xc" is the sum of the values of n, Nif2, Ni + 3 and the corresponding values of Pl (1, Pi + 1, Pi + 2, and Pi + 3. The 90th Both the first and second inputs are logic values 1, so output 5 will be a logic value 0; and adder 90 will generate a carry signal on output C0. The first input of adder 92 is a logic 1 value The second input receives a logic 0 value. In addition, there is a logical j value signal representing the carry on the input CI. The output S of the adder 92 becomes a logical value 0, and the carry signal on the output c0 is a logical value. 1. The first input of the adder 94 receives a logic 1 and the second input receives a logic 1 from the AND gate 93, and its carry signal is enabled by the AND gate 92A. The output S of the adder 94 has a logical value i; the carry output signal on the carry output C0 is also a logical value 1. Similarly, the first input of the adder 96 receives logic 0 and the second input The terminal receives a logic 1 from the AND gate 95, and its carry signal is enabled by the AND gate 94A. The output of the adder 94 The logical value of the output signal on s is 0; and the carry output signal on the carry wheel out c0 is a logical value 1. According to the Foster-Montgomery reduction algorithm, if the specific bit position has a logical value of 1 'also That is, the position of the least significant bit on the terminal 80 is rotated so that B makes the N value lined up and added to the p value. Again, according to the Foster-Montgomery reduction algorithm, the L line

Page 16 4483 76 V. The value of the data generated by the adder of the description of the invention (13) 'will depend on the data in the special data bit position. In this example, the special data bit position is the output S of the adder 92. It must be noted that what is received by the input of the gate 134 is a logic 0 signal from the output S of the adder 92. The latch 132 will not be set, so its output Q remains at a logic value of zero. The AND gates 99, 101, 103, and 105 will leave logical values of 0 on the second inputs of the adders 100, 102, 104, and 106, respectively. The first and second inputs of the adder 100 are both logic values 0, so the output s produced by the adder 100 is logic value 0. Similarly, the first and second inputs of the 'adder 102 are both logic values 0, so the output S produced by it is a logic value 0. The first input of the adder 104 is a logical value 1 'and the second input is a logical value 0', so the output S produced by the adder 104 is a logical value 1. The first and second inputs of the adder 106 are both logic values 0, so the output S produced by it is a logic value 0. Therefore, the values generated by the row Xii adders 106, 104, 102, and 100 are arranged as follows: 0100 ° The value of the data generated by the adder of row X2 has the values, which are also treated as special data. Depending on the position of the bit. In this example, the special data bit is the output logic value of the adder 104. It must be noted that what is received by the input of gate 1 38 is a logic 1 signal from the output S of the adder 104. The output value of AND gate 1 3 8 is logic 1, which causes latch 1 3 6 to be set, so its output Q becomes logic value 1. The gates 109, 111, 113, and 115 are all enabled by the logic value 1 generated by the latch 136. Therefore, the data of the adders 100 ′, 102 ′, 104, and 106 are transferred to the second inputs of the adders 110, 112, 114, and 116, respectively. The first and the first of the adder 11

Page 17 4483 7 6 V. Description of the invention (14) 'Both inputs are logical values 0, so the output S produced by them is a logical value 0. Similarly, the first and second inputs of the 'adder 112 are both logic 0, so the output S produced by it is a logic 0. The first and second inputs of the adder 114 are both logic values 1, so the output S produced by it is a logic value 0, and the carry output signal of output C0 is a logic 1 value. The first and second inputs of the adder 116 are both logic values 0 and a logic 1 value is also transmitted from the sum gate 4A to its carry input terminal. The output s of the adder 116 produces a logical one. For this reason, the adders 116, 114, 112, and 110 of row 2 each produce values that are arranged as follows: 1 00. The value of the data generated by the adders 120, 122, 124, and 126 in line X3 'also depends on the data at the particular data bit position. In this example, 'the special data bit is the output logic value of the adder 1 6. What is received at the input of question 142 is a logic 1 signal from the output δ of the adder 116. The AND gate 142 has a logical value 1 from the adder 116, and a logical 1 value of the # sign T so that the latch 140 is set. The logic 1 value of the Q output of the latch 140 enables 閛 H9, 121, 123, and 125. The data at the outputs of the adders 1 1 0 ′ 1 1 2, 1 1 4 and 1 1 6 are transferred to the first rounds of the adders 120, 122 ′ 124 and 126, respectively. The first and second inputs of the adder 120 are both logical values 0 ', so the output S produced by the adder 120 is a logical value zero. Similarly, the first and second inputs of the 'adder 22' are both logic 0's, so the round-out S produced by it is a logic 0. The first and second inputs of the adder 124 are also logic values 0, so the output S produced by the adder 124 is logic value 0. The first and second rounds of adder 126 are logical values! , So a logic 0 value is generated on the output terminal S ’, and a logic value is generated on the carry output terminal.

Page 18 V. Description of the invention (15) Carry output signal of 1 value. Therefore, the adders 126, 124, 122, and 120 of line 3, on the output terminals 1 64-170, produce their respective values: 〇〇〇〇〇 in the first part of the AG and Bo During the reduction process when the product becomes zero, the latches 128, 132, 136, and 140 are set to contain the value 1101 for \, which will be used in subsequent pipelined multiplication operations. As the product of the first part is reduced to zero, the signal T changes from a logical one to a logical zero, and the value of \ is stored in latches 128, 132, 136, and 140. The stored value, the number below N, and the product of number b; -b63 and ^ -heart 3 are all taken by the modular reducer 60 to complete the multiplication of the polynomial. FIG. 4 is a circuit diagram of another specific implementation of the multiplier structure 171 which is a part of the single arithmetic processor 22 of FIG. 2. The multiplier structure 1 7 1 performs mathematical operations on integer-modular-n multiplication and modular polynomial base multiplication. For brevity, the multiplier structure 1 71 is reduced to a four-by-four adder array. Although we described the multiplier structure 1 7 1 as an adder array with the same number of columns and rows, the present invention is not limited to this. Multiplier structure 171 has XQ line adders 90, 92, 94, and 96; X line adders 100'102, 104, and 106; X2 line adders iiQ, 112, 114, and 116, and X3 43 adder | § 120 '122' 124 plate 126. In addition, latches 1, 52, 1, 56, 60, and 162 are stored for the carry output signal. The carry output signal will be used in the calculation of the integer-modulus-N multiplication to generate the next partial product. Latches 150, 154, and 158 store the ^ material bit of operand 6 ' Latch 226 ' 228 and 23 0 store data bits of N values, and this N value will be used to generate the next partial product.

448376 V. Description of the invention (16) Each of the multiplexers in the multiplier structure 171 has four inputs, one output and two selection inputs. Multiplexers 172-178, 182-188, 192-198 'and the outputs of 202-208 are connected to the first input of the adder', but it must be noted that 'the outputs of these multiplexers can also be connected to such The second input of the adder. The signal on the first and second selection wheels of the multiplexer can select one of the four input signals of the multiplexer and transfer it to the output of the multiplexer. The output signals of the multiplexers 172-178 are respectively transferred to the first inputs of the adders 90-96. The output signals of the multiplexers 182-188 are respectively transferred to the first inputs of the adders 100-106. The output signals of the multiplexers 192-1 98 are respectively transferred to the first inputs of the adders 1 1 0 -1 16. The output signals of the multiplexers 202-208 are respectively transferred to the first input 0 of the adders 120-126. In addition, the first selection inputs of the multiplexers 1 72-1 78 are commonly connected to each other to receive signals. The second selection inputs of the multiplexers 1 72- 1 78 are also connected to each other and are commonly connected to the output of the latch 122. The first selection inputs of the multiplexers 1 82-1 88 are commonly connected to each other to receive signals. The second selection inputs of the multiplexers 182-188 are also connected to each other and are commonly connected to the output of the latch 216. The first selections of the multiplexers 1 92-1 98 are connected in common to each other to receive the signal A (ίΛ2). The second selection inputs of the multiplexers 1 92- 1 98 are also connected to each other and are commonly connected to the output of the latch 220. The first selection inputs of the multiplexers 202-208 are commonly connected to each other to receive the signal A (& A3). The second selection inputs of the multiplexer 2 02-208 are also connected to each other and are commonly connected to the output of the latch 224. Multiplexers 172-178, 182-188, 192-198, and No. 2 02-208

Page 20 448376 V. Description of the Invention (π) One input is connected in common to receive a logic zero value. The second inputs of the multiplexers 172, 174, 176, and 178 respectively receive the values of B (bit.) 'Β (bit 0' B (bit 2) and 6 (bit 3). The multiplexer 172, The third inputs of 174, 176, and 178 respectively receive N (bit 0) 'Ν (bit)' N (bit 2) and N (bit 3) values. Multiplexer 172 '174 '17 1 The fourth round of 7 8 receives the scores of the sum of N and B respectively. Therefore, the fourth input of each multiplexer receives the logical sum of its second and third input values. When the logic values received by the first and second selection inputs of the multiplexer are 00, the multiplexers 172-178, 182-188, 192-198 and 202-208 respectively transfer the signals on their first inputs to the outputs. When the logic value received by the first and second selection inputs is 01, the multiplexer 1 72-1 78, 182-188, 192-198, and 202-208 each transfer the signal on its second input to the output. When the logic value received by the first and second selection inputs is 10, Multiplexer 172-1 78 182-188, 19 2-198, and 202-208, each of which transfers the signal on its third input to the output. When the logic value received by the first and second selection inputs is 11, the multiplexer 172-178, 182-188, 192-198, and 202-208, each of which transfers the signal on its fourth input to the output. When the signal T is transferred from logic 1 to logic 0, latch 21 2, 21 6, 220 and 224 lock the data signals from logic circuits 210, 214, 218, and 222, respectively. The data signals generated by logic circuit 2 10 are the product of signals A (^ 0) and Bα⑽, and P ( 〇) The value of the exclusive OR operation, where P (〇) is the least significant bit of the previous partial product value.

4 483 76 V. Explanation of the invention (18) Negative material ^ 5 疋 6A (the product of bit A and bit B (bit 0, the value of the output signal of the adder μ is mutually exclusive or calculated. Logic circuit 218 The generated data signal is k number A (the product of bit n and Bf bit 0 'and the output signal of adder 1 are mutually exclusive or calculated. The data signal generated by logic circuit 222 is signal ^ bit 3) And 8 (bit (product of 0) and the output signal of the adder 116 are mutually exclusive OR operation & value. And gates 90A-96A are located in the carry path chain of the row \ adder. Therefore, and gates 90A-96A have The ability to control the transmission of signals on the carry chain of row Xq. Similarly, the gates 100A-106A are located in the carry path chain of the adder's' ability to control the transmission of signals on the carry chain of row X!丨 丨 ^ _ 1 1 6 A is located in the carry path chain of the row X2 adder, and has the ability to control the transmission of signals on the carry chain of the row & AND gate 12〇A-126A is located in the row " χ addition 2 In the carry path chain of the router, it has the ability to control the transmission of the letter ^ on the carry chain of the Xinxin. When the multiplier structure 171 is calculating the integer_modulus-n multiplication Sum gates 108 and 96A '100A-106A, 110A_116A, and 12〇A-126α When the multiplier result ㈣i is calculating a modular polynomial basis multiplication, and the closing 90 ° _96α' 100Α-106Α '110Α-116Α and 120Α-126Α are Disabled. In other words, the carry chain path of the multiplication structure 171 is unblocked only when the integer modulo 1 multiplication is calculated, and the carry signal on the path can be transmitted to the adjacent adder unit. The number 7CAG and The product processing of partial products will cause the logical value of the output terminals 164-170 to shrink. Therefore, all the numbers obtained by multiplying the digits and multiplying the digit centers are logical zero values. In addition, Latches 28, 132, 136, and 140 have also been set appropriately during the period of multiplication of Ao and the heart, 4 483 " ^ V. Description of the invention (19) The value of is stored. In the following phase During the multiplication operation, the stored value, together with the corresponding N〗 -N63, the number B] _B63, and the number will be used by the multiplication structure 171 for mathematical operations of integer-modulus-N multiplication. With reference to Figure 4, the following example is a calculation of the product of modular polynomials Process. The Montgomery reduction algorithm for polynomial multiplication takes the following form: (A * R m 〇d N) (Β * R m 〇d Ν) + \ 木 Ν where: A is the first operand and is a polynomial B is the first operator and is a polynomial; N is a reduced polynomial; mod N is the remainder of (A * B * R) / N, which can define the number of components in the finite field; R is greater than The value of N that is an integer power of 2; and \ is a reduced value '; this value should make (A * R mod N) (B * R mod N) + \ N be divisible by R without losing significant bits yuan. For example, when we use 2 as the basis, suppose a = 5 (basis ten) or X2 +1 (polynomial form) 'R = 1 6 (basis ten) or X4 (polynomial form), and N = ll (basis ten) ) Or X3 + X + l (polynomial form), then the (A * R mod N) term becomes: (XHX4) mod N, and the result should be equal to χ + i or 01}. In addition, when B = 4 (base ten), R = 16 (base ten), and N = U (base ten), 'this (B * R mod N) becomes (X6) mOd N, and the result should equal χ2 + ι (polynomial form) or the value 1 0 1. Note that we will associate the operator center with β. First multiply by r 'to simplify the hardware modulation problem. When the operands (A * R mod Ν) and (B * R m〇d N) are multiplied, the product term Pi + 3, Pu2, ρ; ", p" fl becomes m '/. multiplier

Page 23 ^ 48376 V. Description of the invention (20) Structure 171 Reduces the product value of [(A * R mod N) * (B * R mod N)] mod N by a factor of R, resulting in the value 0111 or a polynomial form (XHX + l). Initially, the reset signal of terminal 79 will cause the Q outputs of latches 128, 132, 136, and 140 to become logic zero. One input of the AND gate 130 receives the product term Pi + Q having a logical value of 1, and the other input receives a signal T. The AND gate 130 will produce a logic 1 value output, so that the latch 1 2 8 is set, that is, the Q output of the latch 1 2 8 will be a logic value 1. It must be noted that the signal T is a logical value 1 during the operation of the core of the operator and the dagger, that is, the multiplication of the lower-order elements of the operators AG and BQ. It should also be noted that the output Q of the latch 128 is a logic 1 value, which will cause the AND gates 89, 91, 93, and 95 to be enabled, making the values N1 + Q, N1 + 1,

Ni + 2 and \ +3 can be passed to the second inputs of adders 90, 92, 94 and 96, respectively. Therefore, the value produced by the adder of XQ line is :, N ,, N i ten u 1 + 1 i +2 'Nit3 value and corresponding ρί + ϋ, pi + 1, p] +2 and pi + Sum of 3 values. The first and first inputs of §90 of addition 1 are both logical value 1, so the output § will be a logical value of 0; and the carry signal generated by adder 90 on output C0 is received by the first input of adder 92 It is a logic 1 value, and the second input also receives a logic 1 value. In addition, the carry signal bit on the input CI is a logic value 0 (and the gate 90A prevents the carry generated by the adder 90 from being missing, and is transferred to The output S of the adder 9 ... the adder 92 becomes: logical progression = carry on C 0 彳 § number is a logical value 1 ^ It must be noted that the gate 9 2 a blocks the carry signal generated by the adder 92 , Pass to the adder 94. " The first input of the adder 94 receives a logic 1 and the second input receives a logic 0 from the AND gate 93, and its input signal The output S of the logic 0 adder 94 has a logic value i; and the carry input ^

48376 V. Description of the invention (21) The carry output signal on C 0 is said to be a logical value 0. Similarly, the first input of the adder 9 6 receives a logic 1 and the second input receives a logic 1 from the AND gate 9 5, and its carry signal is a logic value 0. . The output signal on the output S of the adder 96 has a logic value of 0; and the carry output signal on the carry output C0 has a logic value of 1. According to the Foster-Montgomery reduction algorithm ', if the specific bit position has a logical value of 1, that is, the least significant bit position on the terminal 80 is input, then the value of ν will be lined up and added to the value of ρ. According to the Foster-Montgomery reduction algorithm, the > 'expected value' generated by the adder of the χ] line will depend on the data at the particular data bit position. In this example, 'the special data bit position is the output S of the adder 92. It must be noted that what is received by the input of the AND gate 134 is a logic 0 signal from the output s of the adder 92. The latch 132 is not set, so its output Q remains at a logic value of zero. And the gates 9 9, i 〇 丨, i 3 and 105 will respectively leave the logical value 0 on the second input terminals of the adders 100, 102, 104, and 06. The first and second inputs of the adder 100 are both logical values 0 ', so the output S produced by the adder 100 is a logical value zero. Similarly, the first and second inputs of the adder 102 are both logic values 0, so the output S produced by the adder 102 is logic value 0. The first input of the adder 104 is a logical value 1, and the second round input is a logical value 0, so the output S produced by the adder is a logical value 1. Both the first and second rounds of the adder 106 are logical values 0, so the output S produced by it is a logical value 0. Therefore, the adders 10, 10, 10, and 100, which are in the X-line, are each generated by the following values: 〇 1 〇 (}. The value of the data also depends on the special

Page 25 4483 76_ 5. Description of the invention (22) '' ---- It depends on the data in the data bit position. In this example, the special data bit position is the output S of the adder 104. It must be noted that what is received by the input of ON 38 is a logic 信号 signal from the output s of the adder 04. The output value of the AND gate 138 is logic [1], which causes the latch 136 to be set, so its output Q becomes a logic value of 1. The sum gates 109'1Π, 113, and 115 are all enabled by the logic value 1 generated by the latch 1 3 6. Therefore, the data at the outputs of the adders 100, 102, 104, and 106 are transferred to the second inputs of the adders 110'112, 114, and 116, respectively. The first and second inputs of the adder 11 are both logical values 0, so the output S produced by the adder 11 is a logical value 0. Similarly, the first and second inputs of the 'adder 112' are both logical values 0, so the output S produced by them is a logical value 0. The first and second inputs of the adder 114 are both logic 1's, so the output S produced by it is a logic 0, and the carry output signal of its output CO is a logic 1. The value of 1 of the carry output signal is blocked by the AND gate U 4 and cannot be passed to the adder 6. The first input of the adder 116 is a logic value 0 'and the second input is a logic 1 value and the carry input is a logic value 0. At the output δ of the adder 116, a logical j value is generated. That is, the values generated by the adders U 6, 1, 14, 11 2 and 11 ′ of the row X2 are respectively arranged as follows: 1 000. The value of the data generated by the adders 120, 122, 124, and 126 is also determined by the data at the particular data bit position. In this example, the position of the special data bit is the output s ^ of the adder 丨 6 and the input of the closed 142 receives the logic 1 signal from the output s of the adder 丨 6. The AND gate 1 42 has a logical value 1 from the adder 116 and a logical 1 value of the signal T ', so that the latch 1 40 is set. Q output of latch 1 4 0

Page 26 4483 76 V. Explanation of the invention (23) The logic 1 value has enabled the gates 119, 121, 123 and 125. The data at the outputs of the adders 11 0, 11 2, 114 and 1 16 will be transferred to the first inputs of the adders 120 '122, 124, and 126, respectively. The first and second inputs of the adder 120 are both logical values 0 ', so the output S produced by the adder 12 is a logical value 0. Similarly, the first and second inputs of the adder 122 are both logic 0, so the output S produced by the adder 122 is logic 0. The first and second inputs of the adder 124 are also logic 0, so the output S produced by the adder 124 is logic 0. The first and second inputs of the adder 126 both have a logic value of 1, so a logic 0 value is generated at the output terminal S, and a carry output signal of a logic i value is generated at the carry output terminal. And the gate 1 2 6 A prevented the carry signal from being transmitted to the interlock 162 »So the adders 126, 124, 122, and 120 of the row χ3 generate the respective values on the output terminals 164-170: 〇〇 〇〇π During the first multiplication cycle of the reduction process, the first N bits of the product of the 'number' and the part of & will be reduced to zero. The latches Kg, 132, 136, and 140 are set to contain the value U 〇1, which will be used in subsequent pipelined multiplication operations to determine the product of operands A and B. As the product of the first part is reduced to zero, the signal T will change from logical to logical 0, and the value of \ will be stored in latches 128, 132, 136, and 140. The value of the store; the value of N (it3) 'N (if2)' and its value of 00; and the value of p (〖3), P (i + 2), P (m) and P (i + 0) The value 0 0 0 0 will be taken by the multiplier structure j 71 to complete the reduction of the unitary polynomial. After the completion of the second multiplication cycle, the signals on the output terminals 170, 168, 166, and 164 are 〇111, such as' is the value a of the polynomial form (XHX + 1). Refer briefly to the circle 4 t (A * R mod N) and (B * R mod N)

Μ: Page 27 44837 ^ V. Explanation of the invention (24) The binary product produced by the type multiplication is the same as that produced by the circuit of FIG. When multiplying the basis of a polynomial of different modes, the sum of 90j \ -g6A, i00a-106A, 110A-116A, and 120A-126A is disabled. Therefore, the adders 90-96, the adders 100-106, the adders 110-116, and the adders 12〇_126 cannot pass the carry signals to the adjacent adder units. These AND gate disables' will cause each CI terminal to receive a logic zero value. During the first multiplication cycle, the reduction processing will generate operands \ and 8 on the output terminals 170, 168, 166, and 164. The first part of the product is 0 0 0 0. In addition, during the generation of the product of the first part, the latches 224 ′ 220 ′ 216 and 212 are set and the value iioi is locked. This value will be used in the subsequent pipeline multiplication. During the second multiplication period, the signals on the output terminals 170'168'166 and 164 are binary values of 0111 (or values in polynomial form (χΗχ + 1)). It must be noted that the multiplier structure 1 71 architecture can determine the value of \ and store it in the flash locks 212, 216, 220, and 224. In other words, the value of \ before multiplication of the operands 80 and 3 £! Has not been calculated, and the value is determined and latched during the period in which the product of the operands AQ and B0 is determined. In the pipeline processing for determining the total product of the operands A and B, the multiplication period of the other operands' will use the value of the latch. Fig. 5 is a part of a circuit diagram of a multiplier 232 for calculating a basis polynomial multiplication. Briefly refer to FIG. 4 'When the multiplier structure 1 71 is used to calculate the modulus polynomial basis multiplication, and the gate 9 (^ -96 eight, 10 (^ -10614, 110 six -116 eight and 120 eight-1 2 6 A It is disabled. Therefore, the adder unit cannot receive the carry-in signal from the carry output (C0) terminal of the adjacent adder unit.

Page 28 448376 V. Description of the Invention (25). Thus, all of the adder units 90-96, 100-106, 110-116, and 120-126 can be replaced by the half adder unit shown in FIG. The letters “H " are added to the reference numbers of the mutex or gate used as the half adder unit.

For the example of mod N) = XHX4 mod N, (B * R mod N) = (X6) mod N 'A = (X2 + 1), B = (X2), R = (X4), (A to The polynomial multiplication of R mod N) and (B * R mod N) during the first multiplication period will produce a value of 0.0000 on the output terminals 170, 168, 166, and 164. Therefore, the product of the first part is reduced to zero, and the \ value is determined to be 1101 and the numbers are stored in the latches 224, 220, 216, and 212, respectively. This stored \ value will be used in a later multiplication cycle to generate the total product of operands A and b. During this second multiplication period, the signals on the output terminals 170, 168, 166, and 164 are binary values of 0ln, for example, in the polynomial form (χ2 + χ + ι). Second, used to calculate the multiplication or modular polynomial basis multiplication = —: block diagram; where M is the number of multiplier units. Multiplier element; factory temporary operand ... temporary register 242,-used to store the operation ..., and-used to store the heart; = two times ". The register is out of the reset line, but before entering the first multiplication temporary .Although 246 is not shown in the figure, it must be cleared to zero. Θ must be noted, too. For 3, you need to first multiply the c temporary register module -N, and N is temporarily stored; Is the integer _ generator 240 calculates the binary value of a unitary / number of a modulus polynomial, and the multiplication is the binary value of the reduced polynomial, the value stored in the N register 248. The register 242 in FIG. 6 248 M

4483 76

In the preferred embodiment, the B register 242 is a shift register that can shift the lean material stored therein to the left or right. For example, when the volume multiplier 240 calculates an integer-modular-N multiplication, the B register 242 shifts the & material to the right, that is, the B register 242 starts with its least significant bit first Step by step, the bit data is transferred to the multiplexer 25. On the other hand, when the multiplier 240 calculates modulo polynomial basis multiplication, the B register 242 shifts the data to the left, that is, the B register 242 starts with its most significant bit first. The bit data is transferred to the multiplexer 25 in steps. The clock signals for the values in the latch register 242, the a register 244, the c register 24β, and the N register 248 are not shown in FIG. Similarly, the inputs and outputs of each register are connected so that data can flow into and out of the register's bus line, which is not shown in Figure 6. The multiplier 240 determines whether to perform an integer-modular-N multiplication or a modular polynomial base multiplication based on the signal at the NT / POLY input. The INT / POLY input is connected to the selection input of the multiplier 25, the input of the B register 242, and the adder unit of the C register 246 (see the INT / POLY in Figures 7 and 8). So when! The signal at the NT / P0LY input causes the multiplier 240 to perform a modular polynomial basis multiplication. The B register 242 performs a leftward shift of the data, starting with the data in its most significant data bit position. 'Through the multiplier 250, the data is sent to the input of the C register 246. When the multiplier 240 performs an integer-modulo-N multiplication, the B register 242 performs a right shift of the data, starting from the data between its least significant data bit position t, and through the multiplier 250 ', The data is input to the C register 246. °

Page 30 448376 V. Description of the invention (27). Circle 7 operates in a single multiplication cycle. It is two circuit diagrams of unit 270 in multiplier 24o (Figure 6 redundantly stores ^ 246). Although the multiplier carry multiplier used in multiplier 24o of FIG. 7 must be It is understood that the multiplier 24 can be implemented as a carry-save multiplier. Therefore, the unit of the C register 246 (: (η_υ, C (n_2)), two, and the unit 27 combined with G are used to calculate the modulus polynomial basis and Integer_modulus, multiplying. If the I NT / POLY input of unit 270 is a logical zero, unit 27 will perform the operation of the base of the modular polynomial. The latch 262 in unit 27 will lock the "quoti" The single bit stores the value of ⑽㊉ CARRY I), where the positive and negative values are respectively stored in the specific bit positions of the a register 2 to 44, the B register 242 and the N register 248 (labeled as Bit 1 in position 1). CH [GH is the most significant bit of the value stored in the c register 246. It is the " i1, one-bit register unit stored in the adjacent c register 246 On the other hand, when multiplier 240 is selected to perform an integer-modulus J multiplication calculation, latch 262 in unit 270 What is locked is (Α.η.φ '⑽㊉CARRYIN㈣㊉value' wherein ', β and \ are stored in specific bit positions of A register 244, B register 242, and N register 248 (labeled Is the value of the bit position 丨). The dagger is the least significant bit of the value stored in the C register 246. CARRYIN, "" is the "quote" bit from the neighboring C register 246 The carry signal from the adder unit of the adder unit ^ CARRY INu_2) is the carry signal from the adder unit of the first, second, and third units of the C register 246, which is stored: The value of the first product in the latch of the " i " bit in the adjacent C register 246.

448376 V. Description of the invention (28) ---- During operation, multiplying the integer of operand A and operand B of integer_modulus-N multiplication will be completed in multiple multiplication cycles. The data in the β register 242 will be moved to the c register 246 in a manner that one is multiplied by one. Therefore, (: register 246 performs a multiplication of operands A and β, and reduces the product value by an integer multiple of ν 'to produce a value of (A * B * R-1 mod Ν). Therefore, in the first multiplication In the cycle, the least significant data bit of the operand β will first pass through the multiplier by 0, and then move to the C register 246. □ In the next multiplication cycle, the B register 2-42 will be shifted out to the right. So that the next least significant data bit το passes through the multiplier 250 first, and then moves to the c register 246. This multiplication process will continue until the value of operand 8 stored in the β register 242 is all The method of shifting one data bit by one multiplication period is moved to the C register 246 through the multiplier 250, and the C register 246 produces a product mod N). It must be noted that the multiplication of operand A in the form (A; icR m〇d N) and operand B in the form (bm mod N) results in a reduced form of (a * b * r mod N) Of the product. In other words, the product is reduced by R times. For example, the value of the (A * R mod N) item 1011 is stored in the A register 244, and the value of the (B * R m〇dn) item 1010 is stored in the 3 register 242. The value of the item 111 〇1 is stored in N, temporary register 248. Initially, the 'c register 246 is cleared to zero so that the value of the previous injury product becomes zero. In this example, the product value of (An * R mod N) produced by the multiplication SMO is (1001). Details ... field · month We multiply the value stored in the A register 2 4 4 by the least significant data bit from the k B # register 2 4 2 to get the first Partial product. So the value in the A register 244 (1010) will be the same as B (〇) _

Page 32 / ΐ 483 76 V. Description of the invention (29) That is, the least significant bit (100) of B is multiplied. (1) 10110 &lt; == value stored in register A 244 (2) xl01〇i &lt; = = β (〇), the least significant bit of b (3) 10110 &lt; == first bit The meta product is based on the Foster-Like Gomery reduction algorithm. The logical value data in the specific bit position of the partial product determines whether the N value should be aligned with the partial product and added to it to reduce the Partial product values are in mOd N. If the data in that particular bit position is a logical zero, then the value of N will not be added to the product of that part. Conversely, if the data in the specific bit position is a logical 1 value, the value of N is added to the product of the part. In this example, the specific bit position is the least significant bit (10 Π ^) of the first bit product. The data in this position is a logical value of zero, so the value of N is not added to the first bit product (3). The multiplication of the second bit is the multiplication of the value stored in the A register 244 and the next least significant bit in the B register 242. Therefore, the value (10110) in the A register 244 is multiplied by B (l), and β?) Is the next least significant data bit of b-a logical value of 0 (101 ^ 1). (1) 10110 <== value stored in A register 244 (4) x l01 male 1 0 = B (l), the least significant bit below B (5) 00000 &lt; == second bit Multiplication result The second bit product (5) is added to the previously stored result (3) to produce the second partial product (6) ^ (5) 00 00 0 &lt; == 第Two-bit multiplication result (3) + 10110 &lt; == product of the first part (6) 10110 &lt; two = product of the second part

Page 448 376

V. Explanation of the invention (30) According to the Foster-Montgomery reduction algorithm, the logical value in the specific bit position of the product of the second part determines whether the product of the second part should be reduced. In this example, the specific bit position is the leftmost position of the least significant data bit (10110). The second data bit has a logical 1 value, so the / value is aligned and added to the second partial product. In other words, the partial product is reduced by aligning the 1 ^ value with the specific bit position and adding it to the second partial product '. $ (6) 1011 0 &lt; == product of the second part (7) + 11101 &lt; == aligned N value C8) 1010000 &lt; == product of the reduced third part of the product of the second part, Then, the value stored in the A register 244 is multiplied by the party; β (2) is the data bit value (1 〇i〇) in the third bit position of the B register 242 from the right. i). (1) 1 0 1 1 0 &lt; == value stored in A register 244 (9) xl101l &lt; = = β (2), next least significant bit (10) 10110 &lt; == Third-bit multiplication result Then 'the second-bit product (丨 〇) should be added to the previous result (8) to provide the third partial product (Π). (8) 1 0 1 0 000 &lt; == previous result (10) + I0I1Q &lt; == third bit multiplication result (11) 10101000 &lt; == product of the third part 忒A logical value in a particular bit position determines whether the second injury product should be reduced. In this example, the specific bit position is the third bit position (1 0 1 0 1P 0) from the right. The third data bit

4483 7 e V. Description of the invention (31)-It has a logical value of 0, so ‘the product of the third part does not need to add the value of N. The multiplication of the fourth bit is the value stored in the A register 244, and B (3) is the fourth bit of the data from the β register 242 that counts from the right. Value (1P1 01). (I) &lt; == Value stored in A register 244 (12) xlpl01 &lt; = = β (3), next least significant bit (13) 〇〇〇〇〇 &lt; == 4th Bit multiplication result Next, the fourth bit product should be added to the third partial product (u) to provide a fourth partial product (1 4). (II) 10101000 &lt; 2 = product of the third part (13) + Q 〇〇〇〇〇 &lt; == result of the fourth bit multiplication (14) 10101000 &lt; == product of the fourth part The logical value in the specific bit position of the product of the shares determines whether the fourth product should be reduced. In this example, the specific bit position is the (10 1 0 1 0 0) fourth bit position from the right. The fourth data bit has a logical value of 1, so the N value needs to be aligned and added to the fourth partial product. (14) 1 0 1 0 1 0 0 0 &lt; == Fourth partial product (15 ) +11101 &lt; == aligned N value (16) 110010000 &lt; == multiplication of the fifth part of the reduced fourth product multiplied by the fifth bit 'is the value stored in the A register 244 and β ( 4) Multiplication; B (4) is the data bit value Q0101 in the fourth bit position of the β register 242 from the right. (1) 丨 ❶11 ^ Value stored in A register 244

Page 35 ^ 483 7 6

(17) xi〇101 0 = B (4), the next least significant bit (18) 10110 〇 = the result of the fifth bit product Next, the product of the fifth bit should be the product of the reduced fourth part (16) Add 'to provide the fifth partial product (19). (16) 110010000 &lt; == product of reduced fourth part (18) + 10110 <== result of the fifth bit multiplication (1 9) 1 0 1 1 1 1 0 0 0 0 &lt; == Five-Part Product Again, the logical value of a particular bit in the fifth-part product determines whether the fifth-part product should shrink. In this example, the specific bit position is the fifth bit position from the right of the value (1011110000). The fifth data bit has a logical value of 1 '. Therefore, the N value needs to be aligned and added to the fifth partial product. (19) 1011110000 〇 = product of the fifth part (20) + 11101 &lt; == positive green aligned N value (21) 10011000000 &lt; == product of the reduced fifth part (A * R mod N) and (B * R mod N) 'is the product of (10110) and (ι〇ι〇1), which is greater than the value of N. If the final reduced product value is greater than N, the final product value is subtracted from the N value. In other words, the value of n (1 1 1 〇 1) is aligned with the product of the reduced part (1 00 1 1 0 0 0000) and then subtracted. It must be noted that the 1 XN multiplier 240 has been used to calculate the final product of the mod N), and the calculation is 1001. Before performing the multiplication of operands A and B, the \ value in the Foster-Montgomery reduction algorithm has not yet been calculated; but as can be seen from the previous example, the \ value is the product of the reduced elements Ao and BG It's decided. Should pay attention

Page 36 a 76 5. Invention Description (33) is that the value of N is odd, that is, the logical value of the least significant bit of N is 1. Therefore, if the total value added by N has a value of a specific bit of logic i ', then the value of the lower bit of mod N) will be zero. From another perspective, when the Foster-Montgomery reduction algorithm generates a product of K times reduction, the value of the least significant bit will be logic 0. Referring to Figures 6 and 7, the product of (A * B) mod N supporting ECC (polynomial basis is F2M) can be generated, where a and B represent the finite field units of the elliptic curve coordinates, and N is the approximation or basis Polynomial. The number of multiplication cycles' required to produce a product is determined in part by the number of bits stored in the B register 242. The data is shifted from the β register 242 to the C register 246 one at a time. Therefore, the multiplication of the operands A and 6 reduces the multiplied value by an integer multiple of N when the value of (A * B) N is obtained. These operations are performed in the C register 246. Because the carry signal cannot be transferred between the adder units when the multiplier 240 calculates the modulo polynomial basis multiplication, we can design the multiplication of the modulo polynomial basis as: the most significant data bit of the A register 2 4 4 Multiplication of the most significant data bit in the B register 242 ° This method eliminates the need to make the operand into Montgomery format (ie, A — AR mod N). The B register 242 starts from the most significant data element and passes the multiplier 250 to shift the data bits one by one into the ◦ register 246. Multiplying the most significant data bit (ie, the value of B (4)) in the B register 242 by the value of the a register 244, produces the first partial product. So, for example, ‘multiply B (4) —that is, the value of 11010 (the polynomial form is X4) by 1 into the binary value of 10110 (the polynomial form gXHXHX). The reduced polynomial N has a value of 100ι01 (the polynomial form is χΗχΗ1).

Page 37 4483 7f V. Description of the invention (34) Π) 10110 &lt; == value stored in A register 244 (2) χ1Π01 &lt; = = β (4), most significant bit (3) 10110 &lt; == The product of the first part of the product is added to the value of the product of the first part and the sum of the product of the previous part. 'The C register 246 is cleared to zero at the beginning of the previous part. The value of the ^ product is zero, and it is still the product value of the first part 10101. In the next multiplication cycle, the data in the 'B temporary storage H 242 will be shifted to the left &' so that the highest data bit under the memory 242 passes through the multiplier 25 and is transferred to the c memory 246. The C register 246 stores the order in the A register 244 to the next highest data bit. That is 1011 (polynomial form X) multiplied by β (3)-that is, the binary value of m 0 1 (polynomial form X3)}. (1) 1 011 〇 &lt; == value stored in A register 244 (4) XUl01 &lt; = = B (3), next most significant bit (5) 1 0Π0 &lt; == Second bit multiplication result The second bit product (5) is added to the previously stored result to produce the second partial product (6). ° C 3) 10110 &lt;==; product of the first part (5) + 1QJJ 0 &lt; == result of the second bit multiplication (6) 111010 &lt; = two product of the second part to measure a specific bit The logical value in the position 'determines whether the product of the part should be reduced. If the specific bit has a logical value of 1, then the N value is aligned with the specific bit position of the partial product and then added. In this example, the two bits are the most significant data bits of the product of the second part. Here: The value of the specified bit is the logical value l (ill〇l〇). Therefore, 4483 7 6 V. Invention Description (35) N) must be aligned with the most significant data bit and subtracted.

It should be noted that the multiplier 240 does not pass the carry signal when calculating the multiplication of the modulo polynomial basis. Therefore, the "addition" or "subtraction" action is only a mutual exclusion or logical operation on the two values. It should also be noted that after adding to N, the most significant bit of the product of the second part is reduced to zero. 0 (6) 111 〇〇 = product of the second part (7) -10-01 01 &lt; == aligned NUHXHX3) value (8) 011111 〇 = reduced second part product (χ7 + χ + χ5 + χΗχ3) The multiplication of the third bit is the value stored in the A register 244 and By multiplying β (2), B (2) is the data bit value (11 丄 01) in the third bit position of the B register 242 from the left. (1) m 1 〇 &lt; == value stored in A register 244 (9) Xlli〇l &lt; = = b (2), next most significant bit (10) 10110 &lt; == No. The result of the three-bit multiplication followed by 'the third-bit product (10) should be added to the previous result (that is, the reduced second-part product (8)) to provide a third-part product ( 11) 〇 (8) 011111 0 = the product of the reduced second part (10) + 10110 &lt; = the second and third digit multiplication (XHXHX3) (Π) 0 1 0 1 0 0 0 〇 = the third part Partial product (X7 + X5) The logical value in the specific bit position of the product of the third part determines whether the product of the third part should be reduced. In this example, the specific bit position is

Page 39 Outline 376 V. Description of the invention (36) (〇_! Ο 1 ο ο 〇) The position of the second digit from the left. The second data bit has a logical value of 1 ', so the N value (X2 * N) must be aligned with the product of the third part and subtracted. (1 1) 0 1 0 1 000 &lt; == product of the third part (χ7 + χ5) (12)-100101 &lt; == aligned N (XUX4 + X2) value (1 3) 000 1 1 0 1 <== The product of the reduced third part (χ5 + χ4 + χ2) The multiplication of the fourth bit is the multiplication of the value stored in the A register 244 by B (l); B (l) That is the data bit value (111 male 1) in the fourth bit position of the B register 242 from the left. (1) 101 10 &lt; == value stored in A register 244 (14) X111 male 1 &lt; = = B (l), next most significant bit (15) 〇〇〇〇〇 &lt; == Fourth bit multiplication result Next, the fourth bit multiplication result (丨 5) should be added to the reduced third part product (1 3) to provide the fourth part product (丨 6). (13) 0001101 &lt; == product of the reduced third part (15) + 〇〇〇〇〇〇 &lt; == result of the fourth bit multiplication (16) 00011010 &lt; == product of the fourth part ( χΗχ4 + χ2) The logical value in the specific bit position of the product of the fourth part determines whether the product of the fourth part should be reduced. In this example, the specific bit position is (0 1 1 0 1 0) the third bit position from the left. The third data bit is a logical value 0, so the fourth partial product need not be added to the N value. The multiplication of the fifth bit is the multiplication of the value stored in the A register 244 and 8 (〇); B (l) is the fifth bit position of the B register 242 counting from the left The data bit value in (11 1 〇1).

Page 40 4483 76 V. Description of the invention (37) (1) 101 10 <2 = value stored in A register 244 (17) xlll〇i &lt; = = β (〇) 'Next most significant bit (18) 101 10 &lt; == fifth bit multiplication result followed by 'the fifth bit multiplication result (18) should be added to the reduced fourth part product C1 6) to provide the The fifth part of the product (1 9). (1 6) 0 0 0 1 1 0 1 0 〇 = the product of the reduced fourth part (18) + 10110 &lt; == the fifth multiplication result (1 9) 0 0 0 1 0 0 0 10 &lt; == Fifth Part Product (XYZ) The logical value in the special bit position of the fifth part product determines whether the fifth part product should be reduced. In this example, the specific bit position is (G00100010) the fourth bit position from the left. The fourth data bit has a logical value of 1, so the N value must be aligned with the product of the fifth part and subtracted. (19) 0 0 0 1 0 0 0 1 0 &lt; = product of the second and fifth parts (20)-1 〇0 1 0 1 <== correctly aligned N value (21) 000000111 &lt; == reduced first Five-part product (χ2 + χ + 1) The multiplication process will continue 'until the values stored in the B register 242 are shifted by one data bit in a multiplication cycle, and transferred by the multiplier 2 50 Until the C register 246 and the C register 246 produce a product (A * B mod N). The boundary value is a (A mod N) term with a binary polynomial form of χΗχ2 + χ1), which is multiplied by a (B mod Ν) term with a binary value of 111〇1 (polynomial form of χ4 + χ3 + χ2 + 1) , Which yields 100,000 (the polynomial form is XHX + 1). The circuit diagram of Figure 8 is another example of a two-cycle multiplication operation.

Page 41 448376 V. Description of the invention (38) is a unit of all bit positions in the C register 246 of the multiplier 24 (Fig. 6). With reference to the figure δ 'unit 28 (Figure 8) describes the logical situation of the units C (n_n, c (n "' ... 'and C0) of the C register 246. The INT / POLY input terminal of the multiplier 240 is logic 0 'is used to select the multiplier 240 for the multiplication of the modulus polynomial basis. Referring to FIG. 8' the latch in unit 280 locks (ΑθΒίΦΝ, ㊉ 值 'where \ κ and the meaning are stored in a respectively In register 244 'B register 242 and N register 248 in a specific bit position (labeled as bit position 丨) ° CKIGH is the value of the most significant bit in C register 246. C (1- u is the 1-bit adder unit adjacent to the C register 246, and the previous partial product value stored in it. In addition: On the other hand, when the multiplier 24o (Figure 6) is selected to function To perform an integer-modular N multiplication of sixty, the unit 280 locks the value of (AJBi ®CARRYIN0 (i_1) ㊉) where 乂 and A are stored separately in a temporary storage piano 244 disk β temporary f M The specific bit (labeled as the bit. The value in .c_N〇㈣ 疋 is the carry ^ from the adjacent C register 246, the adder unit of the Γ units. Cn-υ is the She is next to C The adder unit of the &quot; i &quot; unit of the device 246 stores the previous partial product value. = The least significant data bit (LSB) latched by the C register 246 (Figure 6) 22 Then, you must enter the second multiplication cycle to determine the C-shoulder value and reduce the partial product generated. If the special signal is a logical 1 value, it is executed. Νί is stored in N Temporary storage: 248 special bit positions (labeled as bit positions.), So the weekly period first calculates the partial product of W, and then the second multiplication period is performed on the calculated partial product. Reduction. There is a feedback

Page 148 376

V. Description of the invention (39) The path can provide the value of C; to the multiplier 282, s, the guide can be detailed in the second multiplication cycle, ^ month's month & for the Ni value through the multiplier 284 And to the input of the full adder 286. It is equivalent to 卞. It takes about 50% of the flute—multiplying the cycle time to produce the reduced product (A * B * Ri m0d Ν). It should be at this moment. For the cryptographic multiplication system implemented as an integrated circuit of the present invention, the high efficiency, low cost, and low power achieved are highly appreciated. The hardware ^ means can simultaneously support the two operands of the RSA and ECC algorithms The multiplication operation has high performance. The multiplication system can be modified to suit large calculation points + _ π 7U &lt; operation difference 'and modified to perform calculations with fewer clock cycles than the prior art system.

Page 43

Claims (1)

^ 48376 1. An integrated circuit (24) for processing cryptographic functions, including: an arithmetic processor (22), which has a connection for receiving data input from a source, and a connection for receiving a selection signal (INT / POLY). Select input, ^ in M = when the selection signal has the first value 'the arithmetic processor processes the data according to the Leavist ^ Samuel-Adolman (RSA) algorithm; when the selection signal has the second value When it is a numerical value, the arithmetic processor processes the data according to the elliptic curve cryptographic calculation ^; (ECC). 2. For example, the integrated circuit of the scope of the patent application still includes an analog-to-digital reducer (60), which includes: ^ a first adder unit (90), which has a connection to receive the respective First and second input terminals of the first and second data signals; a logic gate (90A) * which has a first input connected to receive an enable signal (iNT / P0LY) and connected to the first A second input of a carry output terminal (CO) of an adder unit; and a second adder unit (92) having first and second round-in terminals connected to receive respective third and fourth data signals And a carry input (CI) terminal connected to the logic gate output. 3. If the integrated circuit of item 2 of the patent application scope, wherein the enable signal UNT / POLY with the first value) 'blocks the first output unit (9) from the carry output terminal (C0) The carry round-out signal enters the carry input (CI) terminal of the second adder unit (92). 4 _ An array of elements used to calculate the Ecc algorithm, where the first element contains: a first multiplexer (172) which has a connection to receive the respective first, ^ 40376 Six 'patent application scope second' first, second, third and fourth inputs of third and fourth data signals' and first and second inputs connected to receive respective first and second selector inputs Two selector signals, the selector signals selecting one of the data signals' to be transferred to the output of the first multiplexer; and a first mutex OR gate (90H) having a connection to the first multiplexer A first round-in of a multiplexer output is 'a connection to receive a second input of the first data bit P (0)' and an output for providing an output signal of the first unit. 5. The cell array according to item 4 of the patent application scope, wherein the fourth data signal is the sum of the second and third data signals. 6. The cell array according to item 4 of the patent application scope, wherein the second cell in the same column of the array and adjacent to the first cell includes: a second multiplexer (182) having a connection to receive the respective Fifth, sixth 'seventh and eighth data signals first, second' third and fourth rounds', and first and second selectors connected to receive respective third and fourth selector inputs Signal, the selector signals select the output of the data signal to be transferred to the output of the second multiplexer; and a second mutex or gate (100H) having a connection to the second multiplexer Rotating first round-in '-Connected to the second input of the first mutex or gate (90H) round-out, and a round-out to provide the output signal of the second unit. 7 · —A method for using a common arithmetic processor (24) in the integrated cryptographic circuit to calculate the integer-module-N multiplication and the elliptic curve cryptography (ECC) algorithm, including the following steps: Provide A, B And N value; the arithmetic processor (240) operates to generate A * B * R-] mod N value, where A Page 45 448376 VI. The scope of patent application and β are integers' R is a power of two greater than N, and N is an odd modulus; and the arithmetic processor (240) operates to generate A * B * R-1'mod The value of Ν, where A and B are polynomials, R is a power of 2 greater than N, and N is a reduced polynomial. 0_ A multiplier (171) with multiple interconnected multiplier units, such multipliers The first one in the unit includes: an adder (92) '#has a connection to receive the first data signal „say two inputs, a connection to receive the second input of the carry input signal' and: An output; and a circuit (90A) 'which has a connection to receive the carry input connected to the output of the second-adder's second input, and q ^ * to receive the control input of the selection number (INT / P0LY). The second 'value' multiplier of the 8th item, where-^ of the selection signal is passed through the u round signal to the first input of the first adder (9 2) 'and the selection is made ... ^ ^ Enter The first-adder sibling: the value blocks the carry input signal 1 〇. 如 申The scope of the patent is No. 8 and No. 2. Including ...- the No.-logic, the multiplier of 1 and j 'where the first input of the blocking circuit package,-connection;; a connection to receive the carry-in signal-a connection To the first addition, the second input of the selection signal and the second input of the left state are rotated out.