Multi-word arithmetic device for faster computation of cryptosystem calculations6963644Abstract A multi-word arithmetic device, capable of executing a variety of types of multi-word arithmetic required for elliptic curve cryptology, includes the following. A memory 40, formed from two dual-port memories 41 and 42, temporarily stores n-word integers on which calculation is performed, and a calculation result. An arithmetic unit 20 executes two or more types of calculation, including addition and multiplication, on each word, and outputs a one-word result. A memory input/output unit 30 supplies a maximum of three pieces of one-word data from the memory 40 to the arithmetic unit 20, while simultaneously storing a one-word calculation result from the arithmetic unit 20 in the memory 40. A control unit 10 controls the arithmetic unit 20 and the memory input/output unit 30 so as to have the arithmetic unit execute one of modular addition and Montgomery reduction on n words. Claims 1. A multi-word arithmetic device for executing modular arithmetic on multi-word integers, in accordance with instructions from an external device, the multi-word arithmetic device comprising: Description This application is based on an application No. 11-099657 filed in Japan, the content of which is hereby incorporated by reference.
During one clock cycle, the arithmetic unit 20 either multiplies two pieces of one-word data or adds three pieces of one-word data, according to instructions from the control unit 10, and outputs 34-bit data including a piece of one-word data showing the result or part of the result of this calculation, and a 2-bit carry. The arithmetic unit 20 is connected to the memory input/output unit 30 by three data buses 61 to 63 for outputting and one data bus 64 for inputting. The memory 40 temporarily stores integers on which multi-word arithmetic is performed by the multi-word arithmetic device 100, and intermediate data and calculation results generated by this calculation process. The memory 40 is formed from two separate dual-port memories, a first memory 41 and a second memory 42, each of which can be accessed in word units, and is connected to the memory input/output unit 30 via four data buses 65 to 68 and four address buses 71 to 74. Each of the first and second memories 41 and 42 has a storage capacity of 256 words, and is capable of reading a piece of one-word data (partial integer) simultaneously from a maximum of two different storage areas via two input/output ports during one clock cycle. The memory input/output unit 30 is an interface circuit performing data transfer between the arithmetic unit 20 and the memory 40, and between an external device and the memory 40, according to instructions from the control unit 10. The control unit 10 includes ROM for storing a control program, a logic circuit for outputting control signals according to this program, and RAM. The control unit 10 performs, for example, one of modular addition of two five-word integers stored in the memory 40 and Montgomery calculation on a ten-word integer, by controlling the arithmetic unit 20 and the memory input/output unit 30, based on instructions (indicating computation type, length of multi-word integers which are to be computed and the like) from an external device. FIG. 2 is a circuit drawing showing a detailed construction of the arithmetic unit 20 in FIG. 1. The arithmetic unit 20 includes a multiplier 21, a three-input adder 22, a register 23 and three selectors 24 to 26. The notation [n:m] in the drawing indicates the nth to mth bits of a specified bit sequence, when the least significant bit is the 0 th bit. The multiplier 21 multiplies two pieces of one-word data transmitted from the memory input/output unit 30 via two data buses 61 and 62, and outputs the result of this multiplication as a piece of two-word data. The three-input adder 22 adds (a) a piece of two-word data input into a first input port in1 from the selector 24, (b) a piece of two-word data input into a second input port in2, the lower word being a piece of one-word data transmitted from the memory input/output unit 30 via the data bus 62, and the upper word being '0', (c) a piece of two-word data input into a third input port in3 from the selector 25, and (d) a 2-bit carry input into a carry input terminal (marked 'carry in' in the drawing) from the selector 26. The obtained 66-bit data (the upper 2 bits being a carry and the following bits a piece of two-word data) is output to the register 23. The three-input adder 22 can add negative numbers (numbers represented by a two's complement), so that a carry can be output when there is an underflow (borrow), and not just when there is an overflow. The register 23 stores the 66-bit data output from the three-input adder 22 for only one clock cycle. In the next clock cycle, the 66-bit data held in the register 23 is output as follows. An upper 2-bit carry [65:64] and a middle 2-bit carry [33:32] are transferred to the selector 26, and the lower two words of data are transferred to the selector 25, with the lower 34 bits being output to the memory input/output unit 30 via the data bus 64. The selector 24 selects, according to an instruction from the control unit 20, one of (i) a piece of two-word data produced by zero-extending the one-word data transmitted from the memory input/output unit 30 via the data bus 61, and (ii) a piece of two-word data output from the multiplier 21, and outputs the selected data to the first input port in1 of the three-input adder 22. The selector 25 selects, according to an instruction from the control unit 10, one of (i) a piece of two-word data produced by zero-extending a piece of one-word data transmitted from the memory input/output unit 30, (ii) a piece of two-word data output from the register 23, and (iii) two-word data produced by zero-extending the upper word of the piece of two-word data output from the register 23, and outputs the selected data to the third input port in3 of the three-input adder 22. The selector 26 is a circuit for propagating a carry generated by the addition performed in a certain clock cycle by the three-input adder 22 to the addition occurring in a next clock cycle. The selector 26 selects, according to instructions from the control unit 10, one of the 2-bit carries (i) [65:64] and (ii) [33:34] transmitted from the register 23, and transmits the selected carry to the carry input terminal of the three-input adder 22. FIG. 3 is a circuit drawing showing a detailed construction of the memory input/output unit 30 of FIG. 1. The memory input/output unit 30 has a bus switch 31, an input/output control unit 32 and an address generating unit 33. The bus switch 31 combines a plurality of selector circuits, and connects each of the four data buses 61 to 64 connected to the arithmetic unit 20 to one of the four data buses 65 to 68 connected to the memory 40, according to instructions from the input/output unit 30. The address generating unit 33 includes four separate address registers and an incrementer, and generates four sets of access control signals (each containing an address signal, a read/write signal and the like) and outputs the four sets of signals to four address buses 71 to 74, according to instructions from the input/output control unit 32. The input/output control unit 32 controls the bus switch 31 and the address generating unit 33 based on instructions from the control unit 10 to perform the following operations. The arithmetic unit 20 performs a maximum of four separate accesses of the memory 40 simultaneously. It also performs data transmission between a connected external device and the memory 40 via the data bus 69 and an address bus 75, and transfers to the control unit 10, as a carry signal, information relating to a carry transmitted from the arithmetic unit 20. The following is an explanation of the operation of the multi-word arithmetic device 100. FIG. 4 is a flowchart showing the general operating procedure for the multi-word arithmetic device 100. First, the memory input/output unit 30 receives input data from the external device via the data bus 69 or the address bus 75, the input data being integers which are to be computed, integers resulting from precomputation and the like. Received integers are stored in a designated area in the memory 40 (step S200). Next, the control unit 10 receives an instruction from the external device indicating which of modular addition and Montgomery calculation should be performed (step S201). Upon receiving an instruction indicating that modular addition should be performed, the control unit 10 transmits preprogrammed control signals to the arithmetic unit 20 and the memory input/output unit 30, thereby having the arithmetic unit 20 execute modular addition on two five-word integers A and B stored in the memory 40, and having the result of this calculation C stored in the memory 40 (step S202). Upon receiving an instruction indicating that Montgomery calculation should be performed, the control unit transmits preprogrammed control signals to the arithmetic unit 20 and the memory input/output unit 30, thereby having the arithmetic unit 20 execute steps 1 to 3 of the above-described Montgomery calculation in sequence, using an integer A stored in the memory 40, or similar, and having a final result M stored in the memory 40 (step S203 to 205). Note that the modular addition result C and Montgomery calculation result M are read by the external device via the memory input/output unit 30. The following is an explanation of an actual example of computation performed by the multi-word arithmetic device 100. First, modular addition (C=A+B mod P) performed by the multi-word arithmetic device 100 is explained with reference 10) to FIGS. 5 to 9. FIG. 5 shows a calculation formula for modular addition and examples of input data transferred to the multi-word arithmetic device 100 from the external device when modular addition is performed, in this case examples of input data A, B, P and Q stored in the memory 40 via the memory input/output unit 30. Integer A is one calculation object for modular addition, and is a five-word integer in which five words a4, a3, a2, a1 and a0 are arranged in sequence starting with the most significant digit (this kind of multi-word integer is hereafter written as [a4, a3, a2, a1, a0] or similar). Integer B is another calculation object for modular addition, and is a five-word integer [b4, b3, b2, b1, b0]. Integer P is a modulus used for modular addition, and is a five-word integer [p4, p3, p2, p1, p0]. Integer Q is a five-word integer [q4, q3, q2, q1, q0] equal to a value -P produced by inverting the sign for integer P. FIG. 6 shows a memory map of the memory 40 when modular addition is performed by the multi-word arithmetic device 100. Here, the above four pieces of input data A, B, P and Q are shown along with an five-word integer C [c4, c3, c2, c1, c0] for storing the calculation result and intermediate data W [w4, w3, w2, w1, w0] generated by the modular addition. The first memory 41 stores integers A, P and Q, and the second memory 42 stores integers B and C and intermediate data W. A memory map like the one in the drawing enables the arithmetic unit to simultaneously transfer two words selected from the integers A, P and Q, and two words selected from the integers B, C and W, during one clock cycle. FIG. 7 is a flowchart showing the operating procedure by which the multi-word arithmetic device 100 executes modular addition, in other words the detailed procedure for step S202 in FIG. 4. The modular addition performed by the multi-word arithmetic device 100 can be broadly divided into three processes. In a first process, modular addition of an individual word is repeated five times (steps S210 to S212). In a second process, modular addition for an individual word is repeated five times (a recovery operation) when a carry has been generated by the first process. (steps S214 to S216). In a third process, data transmission for substituting the intermediate data W into the calculation result C is repeated five times, when a carry has not been generated by the first process (steps S217 to S219). FIGS. 8A to 8C show the operating state (calculation function) and input data for the arithmetic unit 20 for the first process (step S210 to S216), second process (step S217 to S219) and third process (step S217 to S219) of FIG. 7 respectively. In the first process, the arithmetic unit 20 operates as a one-word three-input adder, adding three pieces of data ai, bi and qi, and substituting the result of the addition into a piece of data wi. In the second process, the arithmetic unit 20 operates as a one-word two-input adder, adding two pieces of data pi and wi and substituting the result of the addition into a piece of data ci. In the third process, the arithmetic unit operates as a one-word data transfer unit, substituting the piece of data wi into the piece of data ci. The operating state of the arithmetic unit 20 is determined by control signals output to the arithmetic unit 20 from the control unit 10. The input data for the arithmetic unit 20 is determined by control signals output to the memory input/output unit 30 from the control unit 10. Moreover, the output of a fixed value '0' to one of the input ports of the three-input adder 22 is realized by controlling the selectors 24 and 25 or the memory input/output unit 30 to output a piece of data that contains '0' in all its bit positions. FIGS. 9A to 9C are timecharts showing pipeline processing performed by the arithmetic unit 20 for the first process (steps S210 to S212), the second process (steps S214 to 216) and the third process (steps S217 to S219) respectively. The register 23 in the arithmetic unit 20 holds the output from the three-input adder 22, so that two stages of the pipeline, calculation performed by the three-input adder 22 and storage in the memory 40 of the previous calculation result obtained by the three-input adder 22, can be executed in parallel during one clock cycle. In the first process, as is shown in FIG. 7, the control unit 10 first transmits control signals to the arithmetic unit 20 and the memory input/output unit 30, thereby putting the arithmetic unit 20 in the operating state shown in FIG. 8A. Next, the control unit 10 outputs an initializing control signal to the arithmetic unit 20, thereby setting both a value Reg held in the register 23 and a carry Car (Reg [33:32]) at an initial value of '0' (step S210). Then, the arithmetic unit 20, during each clock cycle, repeats in parallel (i) the operation for adding two pieces of data ai and qi transmitted from the first memory 41 via the memory input/output unit 30, the piece of data bi transmitted from the second memory 42 and the carry Car generated during the previous calculation, and storing the result of the addition in the register 23, and (ii) the operation for writing a lower word from the held value Reg in the register 23 into a storage area wi in the second memory 42 (step S211). This means that the arithmetic unit 20 repeats the pipeline processing as shown in FIG. 9A in the following way. During a first clock cycle, the arithmetic unit 20 adds three pieces of data a0, b0 and q0, and stores the result of this addition as the value Reg in the register 23. Then in a subsequent second clock cycle, the arithmetic unit 20 adds three pieces of data a1, b1 and q1 and a carry Car generated by the calculation in the first clock cycle, and stores the result as the value Reg in the register 23, while simultaneously writing the value Reg held in the register 23 as a result of the previous calculation in a storage area w0 in the second memory 42. The arithmetic unit 20 repeats calculation and storage of a calculation result in the second memory 42 five times in total, i.e for five words, under the control of the control unit 10 (steps S211 and S212). As a result, the computation for W=A+B+Q, in other words W=A+B-P, is completed. Next, the control unit 10 determines whether a carry Car (here a borrow) has been generated by the addition in a fifth clock cycle (step S213). If a carry Car has been generated, the control unit 10 has the arithmetic unit 20 execute the second process (steps S214 to S216), but if not, it has the arithmetic unit 20 execute the third process (steps S217 to S219). The reason for this is that, if the intermediate data W obtained in the first process is a negative value, the final result C (A+B mod P) is obtained by adding the modulus P to the intermediate data W (value for performing recovery operation). If, however, the intermediate data W is a positive value, this piece of data is used directly as the final result C. In the second process, the control unit 10 first transmits control signals to the arithmetic unit 20 and the memory input/output unit 30, thereby putting the arithmetic unit 20 in the operating state shown in FIG. 8B. Next, the control unit 10 outputs an initializing control signal to the arithmetic unit 20, thereby setting both a value Reg held in the register 23 and a carry Car (Reg [33:32]) at an initial value of '0' (step S214). Then, the arithmetic unit 20, during each clock cycle, repeats in parallel (i) the operation for adding a piece of data pi and a piece of data wi, transmitted via the memory input/output unit 30 from the first memory 41 and the second memory 42 respectively, to the carry Car generated during the previous calculation, and storing the result of the addition as the value Reg in the register 23, and (ii) the operation for writing a lower word from the value Reg held in the register 23 into a storage area ci in the second memory 42 (step S215). This means that the arithmetic unit 20 repeats the pipeline processing as shown in FIG. 9B in the following way. During a first clock cycle, the arithmetic unit 20 adds two pieces of data p0 and w0, and stores the result of this addition as the value Reg in the register 23. Then in a subsequent second clock cycle, the arithmetic unit 20 adds the two pieces of data P1 and w1 and a carry Car generated by the computation in the first clock cycle, and stores the result as the value Reg in the register 23, while simultaneously writing the value Reg held in the register 23 as a result of the previous calculation in a storage area c0 in the second memory 42. The arithmetic unit 20 repeats calculation and storage of a calculation result in the second memory 42 five times in total, i.e for five words, under the control of the control unit 10 (steps S215 to S216). As a result, the computation for C=W+P, in other words C=A+B mod P, is completed. In the third process, the control unit 10 transmits control signals to the arithmetic unit 20 and the memory input/output unit 30, thereby initializing the arithmetic unit 20 so that it is in the operating state shown in FIG. 8C (step S217). Then, the arithmetic unit 20, during each clock cycle, repeats in parallel (i) the operation for storing the piece of data wi transmitted from the first memory 42 directly in the register 23, and (ii) the operation for writing a lower word from the value Reg held in the register 23 into the storage area ci in the second memory 42 (step S218). This means that the arithmetic unit 20 repeats the pipeline processing as shown in FIG. 9C in the following way. During a first clock cycle, the arithmetic unit 20 stores the piece of data w0 in the register 23 as it is. Then in a subsequent second clock cycle, the arithmetic unit 20 stores the piece of data w1 as the value Reg in the register 23, while simultaneously writing the value Reg held in the register 23 from the previous cycle into the storage area c0 in the second memory 42. The arithmetic unit 20 repeats data transfer five times in total, i.e for five words, under the control of the control unit 10 (steps S218 and S219). As a result, the computation for C=W, in other words C=A+B mod P, is completed. Using the above processing method, the multi-word arithmetic device 100 can complete modular addition of five words during just ten clock cycles, despite being equipped with a small arithmetic unit 20 which is only capable of performing calculation on one word during each clock cycle. Moreover, if no carry has been generated upon completion of the first process, a result W for the modular addition of five words can be obtained after only five clock cycles. The following is an explanation of the operating procedure used when Montgomery calculation (M=A·R^(-1) mod P) is executed by the multi-word arithmetic device 100, with reference to FIGS. 10 to 16. FIG. 10 shows a Montgomery calculation algorithm and examples of input data transmitted to the multi-word arithmetic device 100 from the external device when Montgomery calculation is performed, in other words input data A, P and V stored in the memory 40 via the memory input/output unit 30. The integer A is data on which Montgomery calculation is performed, and consists of a ten-word integer [a9, a8 . . . a1, a0]. The integer P is a modulus used in modular arithmetic and is a five-word integer [p4, p3, p2, p1, p0]. The integer Q is a five-word integer [q4, q3, q2, q1, q0] produced by inverting the sign of the integer P (-P). The integer V is a five-word integer [v4, v3, v2, v1, v0] forming a calculation result for the above-mentioned precomputation performed by the external device. FIG. 11 shows a memory map for the memory 40 when Montgomery calculation is performed by the multi-word arithmetic device 100. Here, five-word intermediate data B. [b4, b3, b2, b1, b0] generated by calculation processing, six-word intermediate data C [c5, c4, c3, c2, c1, c0], a one-word fixed value E [e0] required for the calculation processing (O×ffffffff; a word containing all ones) and five-word integers M [m4, m3, m2, m1, m0] and N [n4, n3, n2, n1, n0] for storing the final result of the Montgomery calculation are shown in addition to the four pieces of input data A, P, Q and V. Integers A, P, Q and M are stored in the first memory 41, and integer V, intermediate data B and C, fixed value E and integer N in the second memory 42. Using this kind of memory map, the arithmetic unit 20 can simultaneously transfer two words selected from the four pieces of data A, P, Q and M and two words selected from two of the three pieces of data V, B, C and E, during one clock cycle. Step 1 The following is a detailed explanation of operations executed in step 1 of the Montgomery calculation performed by the multi-word arithmetic device 100, in other words step S203 in FIG. 4, with reference to FIGS. 12A, 12B and 13. FIGS. 12A and 12B show the operating state and input data for the arithmetic unit 20 when step 1 of the Montgomery calculation is executed. The arithmetic unit 20 multiplies each word ai forming the integer A with each word vj forming the integer V, obtaining partial products with a same digit position (in this case, one digit is equivalent to one word) which it then accumulates (totals), and substitutes the cumulative result into the integer B. FIG. 12A shows the operating state of the arithmetic unit 20 when a first addition is performed for accumulating partial products with a same digit position. Here, the selector 25 in the arithmetic unit 20 selects a piece of two-word data, by zero-extending the upper word of a piece of two-word data output from the register 23. This operation is performed to add the upper word of a two-word cumulative value, obtained by accumulating partial products with a same digit position, to a sum of its upper partial products, in other words to a sum of the partial products that are positioned shifted one word to the left of the originally accumulated partial products. FIG. 12B shows the operating state of the arithmetic unit 20 when addition of cumulative values for partial products with the same digit position is performed for the second time onwards. Here, the selector 25 in the arithmetic unit 20 selects a piece of two-word data output from the register 23. FIG. 13 shows the calculating procedure when step 1 of the Montgomery calculation is executed by the arithmetic unit 20. The upper part of the drawing shows the integers A [a4, a3, a2, a1, a0] and V [v4, V3, v2, v1, v0] on which multiplication is performed, the central part shows partial products arranged in order of calculation and the lower part is a representation of a process in which a sum of partial products having a same digit position is substituted into a word in the integer B [b4, b3, b2, b1, b0]. The reason for multiplying only the lower five words of the ten-word integer A is that, as shown in FIG. 10, step 1 of the Montgomery calculation only needs to compute a residue for the integer R (mod R). The actual operation performed in step 1 by the arithmetic unit 20 is as follows. First, the control unit 10 initializes the arithmetic unit 20 by transmitting control signals to the arithmetic unit 20 and the memory input/output unit 30. In a first clock cycle, after a control signal from the control unit 10 puts the arithmetic unit 20 in the operating state shown in FIG. 12A, the arithmetic unit 20 uses the multiplier 21 to multiply a piece of data a0 and a piece of data v0 transmitted via the memory input/output unit 30 from the first memory 41 and the second memory 42 respectively, and stores the result of the multiplication in the register 23. In a second clock cycle, the arithmetic unit 20 uses the multiplier 21 to multiply a piece of data a1 and a piece of data v0, transmitted from the first memory 41 and the second memory 42 respectively, adds the result of this multiplication to a value obtained by downshifting the multiplication result obtained in the first clock cycle by one word, and stores the result of the addition in the register 23. Simultaneously, the arithmetic unit 20 writes the lower word of the multiplication result from the first clock cycle held in the register 23 into a storage area b0 in the second memory 42. In a third clock cycle, after being put in the operating state shown in FIG. 12B by a control signal transmitted from the control unit 10, the arithmetic unit 20 uses the multiplier 21 to multiply the piece of data a0 and a piece of data v1 transmitted from the first memory 41 and the second memory 42 respectively, adds the result of this multiplication to the two-word cumulative value stored in the register 23 and stores the result of the addition in the register 23. In a fourth clock cycle, after being put in the operating state shown in FIG. 12A by a control signal transmitted from the control unit 10, the arithmetic unit 20 uses the multiplier 21 to multiply a piece of data a2 and the piece of data v0 transmitted from the first memory 41 and the second memory 42 respectively, adds the result of this multiplication to a value obtained by downshifting the multiplication result from the third clock cycle by one word, and stores the result of the addition in the register 23. Simultaneously, the arithmetic unit 20 writes a lower word from the multiplication result of the third clock cycle held in the register 23 into a storage area b1 in the second memory 42. Subsequently, the arithmetic unit 20 repeats calculation of and accumulation of partial products with the same digit position, for all combinations of data ai and vj where the sum of i and j is n0 greater than 4, and stores the results of these calculations in the storage areas b0, b1, b2 and b4. This completes the processing for step 1. The upper five words remaining in the register 23 after the multiplication and accumulation in the fifteenth clock cycle have been completed are rounded down. Step 2 The following is a detailed explanation of step 2 of the Montgomery calculation performed by the multi-word arithmetic device 100, in other words step S204 in FIG. 4, with reference to FIGS. 14A, 14B, 14C and 15. FIGS. 14A and 14B show the operating state and input data for the arithmetic unit 20 when the first half of the processing (B×P) for step 2 of the Montgomery calculation is executed. The arithmetic unit 20 multiplies each word bi of the integer B obtained in step 1 with each word pj of the integer P, while accumulating the partial products with the same digit position obtained from this process and substituting the upper six words of the cumulative result into the integer C. FIG. 14A shows the operating state of the arithmetic unit 20 when a first addition of a cumulative value for partial products with the same digit position is performed. FIG. 14B shows the operating state of the arithmetic unit 20 when addition of cumulative values for partial products with a same digit position is performed for the second time onwards. FIG. 14C shows the operating state and the input data for the arithmetic unit 20 when the second half of the processing (addition of the result of the first half of the processing B×P and integer A) in step 2 of the Montgomery calculation is executed. The arithmetic unit 20 adds the integer C obtained from the first half processing, the one-word fixed integer E and the upper six words of the integer A, and substitutes the upper five words of this addition result into the integer M. FIG. 15 shows the calculating procedure when step 2 of the Montgomery calculation is executed by the arithmetic unit 20. The upper part of the drawing shows the integer B [b4, b3, b2, b1, b0] and the integer P [p4, p3, p2, p1, p0] on which multiplication for the first half of the processing is performed. Partial products are arranged in order of calculation from top to bottom in the central part of the drawing. The lower part of the drawing is a representation of a process in which an upper six words of cumulative results for partial products with the same digit position are substituted into each word of an integer C [C5, c4, c3, c2, c1, c0] and the integer C, the integer E and the upper six words of the integer A are added, the result of the addition being substituted into the upper five words of the integer M. Note that the reason for storing only the upper five words from the result of the above multiplication and addition (B×P+A) in the integer M is that the relation B×P+A mod R=0, makes it clear that the lower half of the calculation result (B×P+A), i.e. the lower five words, must be all zeros. Therefore, in step 2, the required calculation is executed focusing only on the upper five words of the calculation result. However, since a carry from the sixth word (the sixth from the most significant digit, other words referred to below also being so defined) to the fifth word is considered when computing (B×P+A), the multiplication of integers B and P and the addition of integer A are performed on the upper six words of the integer. Furthermore, a word containing all ones is also added when performing additions for the sixth word. This enables any carry propagated to the fifth word from the seventh word via the sixth word to be considered when computing (B×P+A). Since it has been ascertained, as described above, that the sixth word for the calculation (B×P+A) must be '0', the carry from the seventh word only needs to be considered if the result of adding the data c0 and the data a4 not '0'. If the result of adding the data c0 and the data a4 is '0', there is no need to check for a carry, as any carry can be propagated simply by adding the integer E (e0). Note that incorporating the addition of the data e0, having ones in all its bit positions, in the addition of the data c0 and the data a4 is equivalent to performing one of the following processing (1) to (4). (1) When the addition result of data c0 and data a4 is '0', and the carry is also '0', a carry '0' is added to the computed data m0 (c1+a5). (2) When the addition result of data c0 and data a4 is '0', but the carry is '1', a carry '1' is added to the computed data m0 (c1+a5). (3) When the addition result of data c0 and data a4 is not '0', but the carry is '0', a carry '1' is added to the computed data m0 (c1+a5). (4) When the addition result of data c0 and data a4 is not '0', and the carry is '1', a carry '2' is added to the computed data m0 (c1+a5). The following is an explanation of the actual operation performed by the arithmetic unit 20 in step 2. In a first clock cycle, after being put in the operating state shown in FIG. 14A by a control signal transmitted from the control unit 10, the arithmetic unit 20 uses the multiplier 21 to multiply two pieces of data b3 and p0, transmitted via the memory input/output unit 30 from the second memory 42 and the first memory 41 respectively, and stores the multiplication result in the register 23. In a second clock cycle, after being put in the operating state shown in FIG. 14B by a control signal transmitted from the control unit 10, the arithmetic unit 20 uses the multiplier 21 to multiply two pieces of data b2 and p1, transmitted from the second memory 42 and the first memory 41 respectively, accumulates the obtained multiplication value with the value stored in the register 23 in the first cycle and stores the cumulative result in the register 23. Subsequently, the arithmetic unit 20 computes partial products (with the same digit position) for all combinations of b1 and pj where the sum of and is 3, and accumulates the partial products (third and fourth clock cycles). In a fifth clock cycle, after being put in the operating state shown in FIG. 14A by a control signal transmitted from the control unit 10, the arithmetic unit 20 uses the multiplier 21 to multiply two pieces of data b4 and p0 transmitted via the memory input/output unit 30 from the second memory 42 and the first memory 41 respectively, adds the multiplication result and a value obtained by downshifting the value held in the register 23 by one word, and stores the result in the register 23. Simultaneously, the arithmetic unit 20 writes a lower word from the result of the multiplication and accumulation from the fourth cycle held in the register 23 in a storage area c0 in the second memory 42. In a sixth clock cycle, after being put in the operating state shown in FIG. 14B by a control signal transmitted from the control unit 10, the arithmetic unit 20 uses the multiplier 21 to multiply two pieces of data b3 and p1, transmitted from the second memory 42 and the first memory 41 respectively, accumulates the obtained multiplication value with the value stored in the register 23 and stores the cumulative result in the register 23. Subsequently, the arithmetic unit 20 computes partial products for all combinations of bi and pj where the sum of i and j is from 4 to 8, accumulates the partial products, and stores the results in the storage areas c1, c2, c3, c4 and c5. Next, after being put in the operating state shown in FIG. 14C by a control signal transmitted from the control unit 10, the arithmetic unit 20 arranges the digits in integers C [c5, c4, c3, c2, c1, c0] and E [-, -, -, -, -, e0] transmitted from the second memory 42 and integer A [a9, a8, a7, a6, a5, a4] into words, and performs addition of corresponding words from each of the integers, substituting each of the results into an integer M [m4, m3, m2, m1, m0, -] in a first memory 41. This means that the arithmetic unit 20 adds the pieces of data c0 and a4 during the first clock cycle, adds the piece of data c1, the piece of data a5 and a carry, and substitutes this result into data m0 during the second clock cycle, and adds the piece of data c2, the piece of data a6 and a carry, and substitutes this result into data m1 in a third clock cycle. Subsequent processing is performed in a similar manner. This completes the processing for step 2. Note, that in step 2, calculation for partial products of integers B and P is not performed for partial products having complements whose sum is less than 2, for example b0*p0, and b1*p0. This means that the processing time required to compute partial products in this invention is less than that for conventional processing in which all of the partial products are multiplied. Step 3 The following is a detailed explanation of the operations performed by the multi-word arithmetic device 100 in step 3 of the Montgomery calculation, in other words the processing in step S205 in FIG. 4. FIGS. 16A and 16B show operating states and input data for the arithmetic unit 20 when step 3 of the Montgomery calculation is performed. The arithmetic unit 20 uses the first memory 41 (integer M) and the second memory 42 (integer N) alternately as temporary working areas (buffers), and computes a residue of the integer M obtained in step 2 modulo an integer P (M mod P), storing the result in integer M or integer N. FIG. 16A shows the operating state of the arithmetic unit 20 when the first half of processing for step 3 is performed. In this first half, the arithmetic unit 20 alternates (i) addition of integer M and integer Q (=-P), and substitution of the result into integer N, and (ii) addition of integer N and integer Q and substitution of the result into integer M, until an obtained integer M (or N) is negative. FIG. 16B shows the operating state of the arithmetic unit 20 when the second half of processing for step 3 is performed. The arithmetic unit 20 adds the negative integer M (or N) obtained in the first half to integer P, and substitutes the result into the integer N (or M). The following is an explanation of the actual processing performed by the arithmetic unit 20 in step 3. In a first clock cycle, after being put in the operating state shown in FIG. 16A by a control signal transmitted from the control unit 10, the arithmetic unit 20 adds two pieces of data m0 and q0, transmitted via the memory input/output unit 30 from the first memory 41, and stores the addition result in the register 23. In a second clock cycle, the arithmetic unit 20 adds two pieces of data m1 and q1, transmitted from the first memory 41, and stores the result of the addition in the register 23, whilst simultaneously storing a lower word from a value held in the register 23 from the first cycle in a storage area n0 in the second memory 42. Repetition of addition and storage in this way changes the value of integer N in the second memory 42 to M+Q, in other words M-P. Next, the control unit 10 determines the code of the most-recently stored integer N, by receiving a carry generated from the last calculation performed in the above described addition from the memory input/output unit 30. If integer N is determined to be positive, each word of integer N is added to each word of integer Q and the result substituted into integer M, and the control unit 10 determines the code of this integer M. The two types of addition above (M+Q→N, N+Q→M) are alternated until integer M (or N) is negative. When a resulting integer M (or N) is negative, the control unit 10 transmits a control signal to the arithmetic unit 20 via the memory input/output unit 30, thereby setting the operating state of the arithmetic unit 20 to that shown in FIG. 16B. Then, the arithmetic unit 20 adds integer M (or N) and integer P, and substitutes the result into integer N (or M) by repeating addition and storage for each word, in the same way as in the first half. Thus, the residue of integer M modulo integer P (M mod P), in other words the final result of the Montgomery calculation, is stored in the integer M in the first memory 41 or in the integer N in the second memory 42, completing step 3. In this way, the multi-word arithmetic device 100 can execute two types of multi-word arithmetic, modular addition and Montgomery calculation, required for elliptic curve cryptology and the like, despite being provided with just one arithmetic unit 20. Furthermore, the two-word multiplication and the three-word addition performed respectively by the multiplier 21 and the three-input adder 22, and the storing of a previous multiplication and addition result in the memory 40 can be executed in parallel as different stages in a pipeline. This enables multi-word arithmetic to be performed at high speed. The multi-word arithmetic device 100 of the present invention has been described based on the embodiment, but the limitations set out thus far need not apply. For example, the multi-word arithmetic device 100 in this invention performs multi-word arithmetic on five-word integers, and the arithmetic unit 20 uses 32-bit word units, but the invention need not be limited to these numerical values. Furthermore, the multi-word arithmetic device 100 subtracts a modulus P from a given integer by using a method which involves adding an integer Q (=-P) already obtained from an external device, but a method in which the modulus P is subtracted directly may be used. FIG. 17 is a circuit showing a construction of an arithmetic unit 50 in a modification of the invention enabling the modulus P to be subtracted directly. The arithmetic unit 50 has a similar construction to the arithmetic unit 20 in the embodiment, into which a sign inverting unit 51 has been inserted immediately prior to the second input port in2 of the three-input adder 22. The sign inverting unit 51 is capable of inverting signs for n-word integers, and has a circuit construction and operating function shown respectively in FIGS. 18A and 18B. This means that, when a least significant word for an n-word integer is input, the sign inverting unit 51 inverts each bit of the word and then adds '1' to the result before outputting it. When a higher word is input, the sign inverting unit 51 inverts each bit of the word and outputs it. Inputting each word of integer P consecutively into such a sign inverting unit 51 has the same effect as inputting each word of integer Q (=-P) consecutively into the second input port in2 of the three-input adder 22. As a result, using this arithmetic unit 50 instead of the arithmetic unit 20 makes the processing in which integer Q is generated beforehand by an external device and passed to the multi-word arithmetic device 100 unnecessary. Furthermore, the multi-word arithmetic device 100 includes a memory input/output unit 30 for transferring data between the arithmetic unit 20 and the memory 40 and between an external device and the memory 40, but the invention need not have such a limitation. These two types of data transfer may be performed by an external device and another data transfer circuit or similar, rather than by including the memory input/output unit 30 in the multi-word arithmetic device 100. Alternatively, the two types of data transfer may be performed by separate circuits, included in each of the arithmetic unit 20 and the memory 40. Here, first and second memories 41 and 42 are each dual-port memories on which two separate accesses can be performed during one clock cycle. Alternatively, single-port memories operated by a clock signal provided at double the frequency may be used. The multi-word arithmetic device 100, in step 2 of the Montgomery calculation, adds six-word intermediate data C, the upper five words of the integer A and the one-word integer E, computing the five-word integer M. Alternatively, an integer AA may be taken as the upper (n+1) words of the integer A, and the following four values added: This enables the multi-word arithmetic device 100 to complete step 2 of the Montgomery calculation without needing to obtain integer E from an external device. Furthermore, the multi-word arithmetic device 100 completes step 3 of the Montgomery calculation by storing a final result in one of the first memory 41 (integer M) and the second memory 42 (integer N). Alternatively, a processing similar to the third process in the modular addition may be added, so that an integer N in which the final result is stored is transferred to integer M. This ensures that the final result of the Montgomery calculation will be stored in the integer M. In the arithmetic unit 20, multiplication by the multiplier 21 and accumulation by the three-input adder 22 are described as being performed during the same clock cycle, but a register may be provided between the multiplier 21 and the three-input adder 22, so that multiplication and addition are performed during two clock cycles. In other words, the pipeline of the arithmetic unit 20 may be divided into three stages (multiplication, addition, and writing into the memory 40). This reduces the maximum burden generated by the pipeline processing during a single clock cycle, and shortens its critical path, enabling the operating frequency of the arithmetic unit 20 to be raised. When performing Montgomery calculation in the embodiment, the multi-word arithmetic device 100 selects sets of word pairs, each set formed from all the pairs of words that generate a partial product with a same digit position, sets input values in the multiplier, and adds the result of a multiplication to an accumulated value stored in the register 23. Alternatively, however, the result of the multiplication may be added to an accumulated partial product value via the memory 40. In this case, the memory 40 is already provided with an area for storing an accumulated value. The multi-word arithmetic device 100 may update accumulated values by (a) calculating a partial product, while simultaneously reading a one-word accumulated value from the memory 40, (b) adding the one-word accumulated value to a corresponding word in the partial product, and (c) storing the addition result in the corresponding area in the memory 40. This enables selection of the pairs of data to be multiplied to be performed with greater flexibility. Although the present invention has been fully described by way of examples with reference to accompanying drawings, it is to be noted that various changes and modifications will be apparent to those skilled in the art. Therefore, unless such changes and modifications depart from the scope of the present invention, they should be construed as being included therein.
|
Same subclass Same class Consider this |
||||||||||