JP7286239B2 - Arithmetic processing method, arithmetic processing device, and semiconductor device - Google Patents

Description

The present invention relates to an arithmetic processing method, an arithmetic processing device, and a semiconductor device.

In the field of cryptographic processing, processing for calculating a remainder of multiplication is performed. For example, Non-Patent Documents 1 to 3 disclose the Montgomery modular multiplication. Non-Patent Document 1 discloses the basic content of the Montgomery multiplication modulo. Non-Patent Document 1 describes that the calculation of the Montgomery multiplication remainder involves combining several multiplications and shift operations. Montgomery modulo multiplication does not require division and can be performed very quickly compared to other modulo multiplication algorithms. For this reason, the Montgomery modular multiplication is widely used in the field of cryptographic processing.

Non-Patent Documents 2 and 3 disclose a method of calculating a 2n-bit Montgomery multiplication remainder using an n-bit Montgomery multiplication remainder.

Montgomery, Peter L. "Modular multiplication without trial division." Mathematics of computation 44.170 (1985): 519-521. Yoshino, Masayuki, Katsuyuki Okeya, and Camille Vuillaume. "Montgomery multiplication with twice the bit-length of multipliers." IEICE transactions on fundamentals of electronics, communications and computer sciences 91.1 (2008): 203-210. Yoshino, Masayuki, Katsuyuki Okeya, and Camille Vuillaume. "Recursive Double-Size Modular Multiplications from Euclidean and Montgomery Multipliers." IEICE transactions on fundamentals of electronics, communications and computer sciences 93.1 (2010): 180-187.

Here, a method of calculating a 2n-bit Montgomery multiplication remainder using an n-bit Montgomery multiplication remainder in conventional cryptographic processing will be described. FIG. 16 is a diagram showing an example of the configuration of a conventional arithmetic processing device that performs cryptographic processing. The arithmetic processing device 1001 includes a CPU (Central Processing Unit) 10 , an arithmetic unit 1020 and a memory 30 . The CPU 10 reads out the program held in the memory 30 and transmits an instruction based on the program to the calculator 1020 . In addition, the CPU 10 reads out data necessary for computation in the computing unit 1020 from the memory 30 and transmits the data to the computing unit 1020 .

The calculator 1020 performs multi-calculation (MultMonDiv) including calculation of Montgomery modular multiplication, etc. based on the instructions and data received from the CPU 10 .

The memory 30 includes a RAM (Random Access Memory) or the like, and holds data such as programs to be executed by the CPU 10, calculation results in the CPU 10 and the arithmetic unit 1020, and setting information of the arithmetic processing unit 1001.

FIG. 17 is a diagram showing an algorithm for calculating a 2n-bit Montgomery multiplication remainder in conventional cryptographic processing. FIG. 18 is a diagram showing a multi-operation algorithm. FIG. 19 is a flow diagram corresponding to the algorithm of FIG. As shown in FIGS. 17 and 19, in calculating the 2n-bit Montgomery multiplication remainder, six multi-operations (Step 1 to Step 6) are sequentially executed for each input value. Then, a 2n-bit Montgomery multiplication residue is calculated as an output value (Output) using the calculation result in each step. 19 correspond to those in FIG. 3 and the like, which will be described later.

As shown in FIG. 18, in each multi-operation (MultMonDiv), for example, "x", "y" and "w" are input and "q" and "r" are output. As shown in FIG. 18, in each multi-operation, calculation of an n-bit Montgomery multiplication remainder (MultMon) is performed on the first and fourth lines. That is, in order to calculate the 2n-bit Montgomery multiplication (2n-bit Montgomery multiplication remainder), it is necessary to calculate the n-bit Montgomery multiplication remainder 12 times.

FIG. 20 is a diagram for comparing the amount of computation involved in calculating the n-bit Montgomery multiplication remainder and the amount of computation involved in n-bit multiplication. As shown in FIG. 20, the amount of calculation required to calculate the n-bit Montgomery multiplication remainder is greater than the amount of calculation required for the n-bit multiplication, and the calculation of the n-bit Montgomery multiplication remainder requires 1.5 times or more of the n-bit multiplication. of calculation time is required. Then, calculation of the 2n-bit Montgomery multiplication remainder requires an operation time that is 18 times longer than the n-bit multiplication.

Other problems and novel features will become apparent from the description of the specification and the accompanying drawings.

Although the arithmetic processing method and the like of a plurality of embodiments are described in this specification, the arithmetic processing method of one embodiment is as follows. The arithmetic processing method is an arithmetic processing unit comprising a CPU, an arithmetic unit that switches between n-bit Montgomery multiplication remainder or n-bit multiplication according to instructions from the CPU, and a memory. An arithmetic processing method for calculating a Montgomery multiplication remainder of a number. The arithmetic processing method includes a first step in which the CPU selects an arithmetic method from n-bit Montgomery multiplication remainder calculation or n-bit multiplication based on a program read from the memory, and the CPU performs an arithmetic operation according to the selected arithmetic method. and a second step causing the device to perform the second step.

According to one embodiment, it is possible to shorten the operation time required to calculate the Montgomery multiplication remainder having the number of bits that is an integral multiple of n bits using the n-bit Montgomery multiplication remainder.

FIG. 1 is a diagram showing an example of the configuration of an arithmetic processing device according to Embodiment 1 of the present invention. FIG. 2 is a diagram illustrating an algorithm for calculating a 2n-bit Montgomery modular multiplication according to Embodiment 1 of the present invention. FIG. 3 is a flow diagram corresponding to the algorithm of FIG. FIG. 4 is a diagram illustrating an algorithm for calculating a 2n-bit Montgomery modular multiplication according to the modification of the first embodiment of the present invention. FIG. 5 is a flow diagram corresponding to the algorithm of FIG. FIG. 6 is a diagram showing an example of the configuration of an arithmetic processing device according to Embodiment 2 of the present invention. FIG. 7 is a diagram illustrating an algorithm for 3n-bit Montgomery modular multiplication calculation according to the third embodiment of the present invention. FIG. 8 is a flow diagram corresponding to the algorithm of FIG. FIG. 9 is a diagram showing an example of the configuration of an arithmetic processing device according to Embodiment 4 of the present invention. FIG. 10 is a diagram showing an example of a procedure for parallel execution of multi-operation and n-bit multiplication according to Embodiment 4 of the present invention. FIG. 11 is a diagram showing another example of a procedure for parallel execution of multi-operation and n-bit multiplication according to Embodiment 4 of the present invention. FIG. 12 is a diagram showing an example of a configuration of an arithmetic processing device according to Embodiment 5 of the present invention. FIG. 13 is a diagram illustrating an algorithm for multi-operation according to Embodiment 5 of the present invention. FIG. 14 is a flow diagram corresponding to the algorithm of FIG. FIG. 15 is a flow diagram corresponding to the algorithm of FIG. FIG. 16 is a diagram showing an example of the configuration of a conventional arithmetic processing device that performs cryptographic processing. FIG. 17 is a diagram showing an algorithm for calculating a 2n-bit Montgomery multiplication remainder in conventional cryptographic processing. FIG. 18 is a diagram showing a multi-operation algorithm. FIG. 19 is a flow diagram corresponding to the algorithm of FIG. FIG. 20 is a diagram for comparing the amount of computation involved in calculating the n-bit Montgomery multiplication remainder and the amount of computation involved in n-bit multiplication.

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In all the drawings for explaining the embodiments, the same parts are basically denoted by the same reference numerals, and repeated explanations thereof will be omitted.

(Embodiment 1)
In the present embodiment, the 2n-bit Montgomery multiplication remainder is calculated by the CPU appropriately selecting the multi-operation (MultMonDiv) including the calculation of the n-bit Montgomery multiplication remainder and the n-bit multiplication.

<Configuration of arithmetic processing unit>
FIG. 1 is a diagram showing an example of the configuration of an arithmetic processing device according to Embodiment 1 of the present invention. FIG. 1 is similar to FIG. 16, except that calculator 1020 is replaced with calculator 20. FIG. The calculator 20 switches between calculation of an n-bit Montgomery multiplication remainder (MultMon) and n-bit multiplication according to instructions from the CPU 10 .

FIG. 2 is a diagram illustrating an algorithm for calculating a 2n-bit Montgomery modular multiplication according to Embodiment 1 of the present invention. In the calculation of the 2n-bit Montgomery multiplication remainder in the present embodiment, arithmetic processing such as Steps 1 to 6 shown in FIG. 2 is executed. As shown in FIG. 2, Step 1, Step 2, Step 4, and Step 6 execute n-bit multiplication, and Step 3 and Step 5 execute n-bit Montgomery multiplication remainder calculation and multi-operation (MultMonDiv) including addition and subtraction.

Specifically, in the algorithm of FIG. 2, A=a ₁ m+a ₀ , B=b ₁ m+b ₀ , N=n ₁ m+n ₀ are input, and 2n-bit values {r ₀ , q ₀ }, { r ₁ , q ₁ }, (q ₂ , r ₂ ), {r ₃ , q ₃ }, (q ₄ , r ₄ ), {r ₅ , q ₅ } are calculated. Note that m:=2 ⁿ and M:=m ² =2 ²ⁿ . a ₁ , b ₁ , n ₁ are upper bits (n bits) in each value (A, B, N), a ₀ , b ₀ , n ₀ are lower bits (n bits) in each value (A, B, N) ). Also, r is the upper bit (n bits) of each calculated value, and q is the lower bit (n bits) of each calculated value.

In Step 1, [a ₁ , b ₁ ] are input and their multiplication is executed. Thereby, a 2n-bit value {r ₀ , q ₀ } is calculated. In Step 2, [a ₁ +a ₀ , b ₁ +b ₀ ] are input and their multiplication is calculated. Thereby, a 2n-bit value {r ₁ , q ₁ } is calculated. In Step 3, [a ₀ , b ₀ , n ₀ ] are input and multi-operation (MultMonDiv) is executed. As a result, a 2n-bit value (q ₂ , r ₂ ) is calculated.

In Step 4, [q ₂ , n ₁ ] are input and these multiplications are executed. Thereby, a 2n-bit value {r ₃ , q ₃ } is calculated. In Step 5, [-q ₀ +q ₁ +r ₂ -q ₃ , 1, n ₀ ] are input and multi-operation (MultMonDiv) is executed. As a result, a 2n-bit value (q ₄ , r ₄ ) is calculated. In Step 6, [q ₄ , n ₁ ] are input and these multiplications are executed. As a result, a 2n-bit value {r ₅ , q ₅ } is calculated.

Then, using these calculation results, a 2n-bit Montgomery multiplication residue is calculated as an output value according to the following equation (1).

A*B*M ⁻¹ (mod N)=(r ₀ +r ₃ −r ₅ )m+(q ₀ −r ₀ +r ₁ −r ₂ +q ₃ −r ₃ +r ₄ −q ₅ ) (1)
<Arithmetic processing method>
FIG. 3 is a flow diagram corresponding to the algorithm of FIG. The flow diagram of FIG. 3 includes steps S101-S108. In step S101, the CPU 10 initializes the count value in the memory 30 and sets the count value to "1". Here, the count value is a value that identifies the progress of processing in the algorithm of FIG. Although details will be described later, the count value is updated each time the processing of each step is completed. For example, if the count value is set to "4", it indicates that the processing up to Step 3 in FIG. 2 has been completed.

In step S102, input values corresponding to each step in FIG. 2 are prepared. The CPU 10 creates input values for each step based on the program read from the memory 30 . For example, in Step 1, the CPU 10 creates input values [a ₁ , b ₁ ]. In Steps 2 and 5, the CPU 10 performs addition and subtraction to create an input value.

In step S103, a calculation method is selected according to the count value. Specifically, when the count value is "3, 5" (Yes), the CPU 10 selects multi-operation (MultMonDiv), that is, calculation of n-bit Montgomery multiplication remainder, and the process of step S104 is executed. On the other hand, if the count value is any other value (No), the CPU 10 selects multiplication, and the process of step S105 is executed.

The CPU 10 transmits the input value created in step S102 and instructs the computing unit 20 to execute the selected computing method.

For example, in Step 1, the count value is set to "1", so the CPU 10 selects multiplication. The CPU 10 then transmits the input values [a ₁ , b ₁ ] and commands the calculator 20 to perform multiplication.

In step S<b>105 , the calculator 20 performs multiplication using the received input value according to the command from the CPU 10 . For example, in Step 1, the calculator 20 performs n-bit multiplication using input values [a ₁ , b ₁ ] to calculate 2n-bit values {r ₀ , q ₀ }. The calculated value is held in the memory 30 .

In step S104, calculation of an n-bit Montgomery multiplication residue in the arithmetic unit 20 and processing such as addition and subtraction by the CPU 10 are executed. Step S104 has steps S104a to S104c, as shown in FIG.

In step S104a, an n-bit Montgomery multiplication residue corresponding to the first line in FIG. 18 is calculated. Based on the read program, the CPU 10 instructs the calculator 20 to calculate the n-bit Montgomery multiplication remainder, and transmits the input values [x, y, w] shown in FIG. The input values are [a ₀ , b ₀ , n ₀ ] in Step 3 of FIG. 2 and [−q ₀ +q ₁ +r ₂ −q ₃ , 1, n ₀ ] in Step 5. Based on a command from the CPU 10, the arithmetic unit 20 uses the input value to calculate an n-bit Montgomery multiplication remainder, and calculates the value r of the high-order bits of the output value. The value r calculated here is held in the memory 30 .

In step S104b, an n-bit Montgomery multiplication residue corresponding to the fourth line in FIG. 18 is calculated. Note that the calculations on the second and third lines in FIG. 18, which are the inputs in step S104b, are executed by the CPU 10, for example. Based on the program, the CPU 10 instructs the calculator 20 to calculate the n-bit Montgomery multiplication remainder, and transmits the values corresponding to the second and third lines in FIG. 18 as input values. The calculator 20 calculates an n-bit Montgomery multiplication remainder using the input value, and calculates a value r' for calculating the lower bits of the output value.

Then, in step S104c, the CPU 10 performs each operation such as addition corresponding to the 6th to 8th lines in FIG. 18, and calculates the lower bit value q of the output value. Then, the CPU 10 creates a 2n-bit value (q, r) as an output value. The calculated value is held in the memory 30 .

For example, in Step 3, the CPU 10 causes the arithmetic unit 20 to twice calculate the n-bit Montgomery multiplication residue based on the input values [a ₀ , b ₀ , n ₀ ], and performs an operation such as addition to obtain 2n-bit Calculate the values (q ₂ , r ₂ ). In Step 5, the CPU 10 causes the arithmetic unit 20 to twice calculate the n-bit Montgomery multiplication remainder based on the input value [-q ₀ +q ₁ +r ₂ -q ₃ , 1, n ₀ ], An operation is performed to calculate a 2n-bit value (q ₄ , r ₄ ).

In step S106, it is determined whether the count value is "6". If the CPU 10 determines that the count value is not "6" (No), it performs a process of adding "+1" to the count value in step S107. For example, when the process of Step 1 is performed, the CPU 10 updates the count value to 1+1=2 and causes the memory 30 to retain the updated count value. Then, the process returns to step S102, and the processes after step 2 are continuously executed.

On the other hand, in step S106, when the CPU 10 determines that the count value is "6" (Yes), it determines that the processes of Steps 1 to 6 are all completed, and the process of Step S108 is executed. In step S108, the CPU 10 calculates an output value using the calculation results in steps 1-6. The CPU 10 reads the value of each operation result held in the memory 30, and calculates the 2n-bit Montgomery multiplication residue shown in Equation (1) as an output value. The calculated output value may be held in the memory 30 or may be transmitted to the outside.

<Main effects of the present embodiment>
According to the present embodiment, the CPU 10 selects the calculation of the n-bit Montgomery multiplication remainder or the n-bit multiplication based on the program read from the memory 30 and causes the calculator to execute it.

According to this configuration, the number of multi-operations including the n-bit Montgomery multiplication remainder having a long operation time is reduced, and the multiplication having a short operation time is used. It is possible to shorten the calculation time related to.

The reduced computation time is determined by the difference in computation time between n-bit multiplication and n-bit Montgomery multiplication remainder. Specifically, the slower the operation time of the n-bit Montgomery multiplication remainder with respect to the n-bit multiplication, the greater the effect. If the n-bit Montgomery multiplication remainder takes k times as long as the n-bit multiplication, the calculation time for the 2n-bit Montgomery multiplication remainder is as follows. When k=3, the computation time in this embodiment is about 44.4% of the conventional one. When k=2, the computation time in this embodiment is about 50% of the conventional one. When k=1.5, the computation time in this embodiment is about 55.6% of the conventional one. When k=1, the computation time in this embodiment is about 66.7% of the conventional one. Thus, when the operation time of the n-bit Montgomery multiplication remainder is longer than the operation time of the n-bit multiplication, the effect of reducing the operation time of the 2n-bit Montgomery multiplication remainder becomes greater.

[Modification]
Calculation of the 2n-bit Montgomery multiplication remainder is also possible with an algorithm other than that shown in FIG. Therefore, here, an algorithm other than that shown in FIG. 2 is illustrated as a modified example. FIG. 4 is a diagram illustrating an algorithm for calculating a 2n-bit Montgomery modular multiplication according to the modification of the first embodiment of the present invention. Steps 1 to Srep5 in FIG. 4 are the same as in FIG. 2, but Step 6 in FIG. 4 is replaced with multi-operation. FIG. 5 is a flow diagram corresponding to the algorithm of FIG.

In Step 6 of FIG. 4, [q ₄ , n ₁ , m−1] are input and multi-operation (MultMonDiv) is executed. As a result, a 2n-bit value (q ₅ , r ₅ ) is calculated. The 2n-bit multiplication remainder, which is the output value, is calculated using equation (1) already described.

FIG. 5 differs from FIG. 3 only in the processing content of step S103. As shown in FIG. 4, multi-operation is also executed in Step 6. FIG. Therefore, in step S103, when the count value is "3, 5, 6" (Yes), the CPU 10 selects multi-operation (MultMonDiv), and the process of step S104 is executed. On the other hand, if the count value is other value "1, 2, 4" (No), the CPU 10 selects multiplication, and the process of step S105 is executed.

Also in this modification, it is possible to reduce the computation time for the 2n-bit Montgomery multiplication remainder compared to the conventional computation method.

(Embodiment 2)
Next, Embodiment 2 will be described. In addition, below, description is abbreviate|omitted in principle about the part which overlaps with the content already described.

FIG. 6 is a diagram showing an example of the configuration of an arithmetic processing device according to Embodiment 2 of the present invention. In an arithmetic processing device 101 shown in FIG. 6, the arithmetic unit 20 of FIG. 1 is replaced with an arithmetic unit 120 . The calculator 120 switches between calculation of an n-bit Montgomery multiplication remainder, n-bit multiplication, and addition/subtraction based on instructions sent from the CPU 10 .

The arithmetic unit 120 performs addition and subtraction to calculate the output value in step S108 of FIG. 3, for example. In this way, the computing unit 120 can perform the computation that the CPU 10 was performing instead. In addition to the calculation of the output value, the calculator 120 may also calculate the input value by addition and subtraction instead of the CPU 10 .

_{Specifically ,} in Step ₂ of FIG _. [a ₁ +a ₀ , b ₁ +b ₀ ] may be calculated. Then, the operator 120 can perform n-bit multiplication using the input value calculated by itself.

2 and 3, the calculator 120 can perform addition and subtraction instead of the CPU 10. FIG.

According to the present embodiment, the computing unit 120 switches between calculation of the n-bit Montgomery multiplication remainder, n-bit multiplication, and addition/subtraction according to instructions from the CPU 10 . This configuration reduces the load on the CPU 10 and speeds up the processing in the arithmetic processing unit 101 . Further, since it is not necessary to read out the operation result to the CPU 10, the operation time for the 2n-bit Montgomery multiplication remainder is further shortened.

(Embodiment 3)
Next, Embodiment 3 will be described. By using the conventional method, it is possible to calculate Montgomery multiplication remainders of 2n, 4n, 8n bits, etc., but in order to calculate the 3n-bit Montgomery multiplication remainders, it is necessary to first calculate the 4n-bit Montgomery multiplication remainders. . However, in this method, the number of calculations of the n-bit Montgomery multiplication remainder increases, the calculation time increases, and a memory area of 4n bits is required. Therefore, in the present embodiment, a method of calculating an n-bit Montgomery multiplication remainder and a 3n-bit Montgomery multiplication remainder using n-bit multiplication will be described.

FIG. 7 is a diagram illustrating an algorithm for 3n-bit Montgomery modular multiplication calculation according to the third embodiment of the present invention. In the calculation of the 3n-bit Montgomery multiplication remainder in the present embodiment, arithmetic processing such as Steps 1 to 14 in FIG. 7 is executed. As shown in FIG. 7, in Steps 1-2, Steps 4-8, Steps 10-11, and Steps 13-14, n-bit multiplication is performed, and in Steps 3, 9, and 12, multi-operations ( MultMonDiv) is executed. Thus, in this embodiment, the 3n-bit multiplication remainder is directly calculated by increasing the number of Steps.

Specifically, in the algorithm of FIG. 7, with A=a ₂ m ² +a ₁ m+a ₀ , B=b ₂ m ² +b ₁ m+b ₀ , N=n ₂ m ² +n ₁ m+n ₀ as input, 2n bits Each value of {r ₀ , q ₀ } to {r ₁ , q ₁ }, (q ₂ , r ₂ ), {r ₃ , q ₃ } to {r ₇ , q ₇ }, (q ₈ , r ₈ ) , {r ₉ , q ₉ } to {r ₁₀ , q ₁₀ }, (q ₁₁ , r ₁₁ ), {r ₁₂ , q ₁₂ } to {r ₁₃ , q ₁₃ } are calculated. Note that m:=2 ⁿ and M:=m ³ =2 ³ⁿ .

In Step 1, [a ₂ , b ₂ ] are input and their multiplication is executed. Thereby, a 2n-bit value {r ₀ , q ₀ } is calculated. In Step 2, [a ₁ , b ₁ ] are input and their multiplication is executed. Thereby, a 2n-bit value {r ₁ , q ₁ } is calculated. In Step 3, [a ₀ , b ₀ , n ₀ ] are input and multi-operation (MultMonDiv) is executed. As a result, a 2n-bit value (q ₂ , r ₂ ) is calculated.

In Step 4, [a ₂ +a ₁ , b ₂ +b ₁ ] are input, and these multiplications are executed. Thereby, a 2n-bit value {r ₃ , q ₃ } is calculated. In Step 5, [a ₂ +a ₀ , b ₂ +b ₀ ] are input and these multiplications are executed. Thus, a 2n-bit value {r ₄ , q ₄ } is calculated. In Step 6, [a ₁ +a ₀ , b ₁ +b ₀ ] are input and these multiplications are executed. As a result, a 2n-bit value {r ₅ , q ₅ } is calculated.

In Step 7, [q ₂ , n ₂ ] are input and these multiplications are executed. Thus, a 2n-bit value {r ₆ , q ₆ } is calculated. In Step 8, [q ₂ , n ₁ ] are input and these multiplications are executed. Thus, a 2n-bit value {r ₇ , q ₇ } is calculated. In Step 9, [-q ₁ +r ₂ +q ₅ -q ₇ , 1, n ₀ ] are input and multi-operation (MultMonDiv) is executed. As a result, a 2n-bit value (q ₈ , r ₈ ) is calculated.

At Step 10, [q ₈ , n ₂ ] are input and these multiplications are executed. As a result, a 2n-bit value {r ₉ , q ₉ } is calculated. In Step 11, [q ₈ , n ₁ ] are input and these multiplications are executed. As a result, a 2n-bit value {r ₁₀ , q ₁₀ } is calculated. In Step 12, [-q ₀ +q ₁ -r ₁ -r ₂ +q ₄ +r ₅ -q ₆ +q ₇ -r ₇ +r ₈ -q ₁₀ , 1, n ₀ ] are input and multi-operation (MultMonDiv) is executed. be. As a result, a 2n-bit value (q ₁₁ , r ₁₁ ) is calculated.

In Step 13, [q ₁₁ , n ₂ ] are input and these multiplications are executed. As a result, a 2n-bit value {r ₁₂ , q ₁₂ } is calculated. In Step 14, [q ₁₁ , n ₁ ] are input and these multiplications are executed. As a result, a 2n-bit value {r ₁₃ , q ₁₃ } is calculated.

Then, using these calculation results, a 3n-bit Montgomery multiplication residue is calculated as an output value according to the following equation (2).

A*B*M ⁻¹ (mod N)=(r ₀ +r ₆ −r ₁₂ )m ² +(q ₀ −r ₀ −r ₁ +r ₃ +q ₆ +r ₆ +r ₇ −r ₉ −q ₁₂ −r ₁₃ ) m + (-q _{0 -r 0} -q ₁ +r ₁ -r ₂ +q ₃ +r ₄ +q ₆ -r ₆ +q ₇ +r ₇ -q ₉ -r ₁₀ +r ₁₁ -q ₁₃ ) (2)
FIG. 8 is a flow diagram corresponding to the algorithm of FIG. FIG. 7 differs from FIG. 3 in the processing contents of steps S103 and S106. As shown in FIG. 7, in this embodiment, multi-operations are executed in Steps 3, 9, and 12. FIG. Therefore, in step S103 of FIG. 8, when the count value is "3, 9, 12" (Yes), the CPU 10 selects the multi-operation (MultMonDiv), and the process of step S104 is executed. On the other hand, if the count value is other value "1 to 2, 4 to 8, 10 to 11, 13 to 14" (No), the CPU 10 selects multiplication, and the process of step S105 is executed.

In step S106, it is determined whether the count value is "14". When the CPU 10 determines that the count value is not "14" (No), the process of step S107 is executed. On the other hand, when the CPU 10 determines that the count value is "14" (Yes), the process of step S108 is executed.

According to the present embodiment, calculation of the 3n-bit Montgomery multiplication remainder is performed by appropriately switching between calculation of the n-bit Montgomery multiplication remainder and n-bit multiplication in the calculator 20 . Although the number of steps is increased compared to the calculation of the 2n-bit Montgomery multiplication remainder, the number of calculations of the n-bit Montgomery multiplication remainder is suppressed to 6 times, and the operation time required to calculate the 3n-bit Montgomery multiplication remainder is shortened. becomes possible. In addition, since the 3n-bit Montgomery multiplication remainder can be directly calculated without calculating the 4n-bit Montgomery multiplication remainder, there is no need to prepare a memory area of 3n bits or more, and the memory can be used effectively. becomes possible.

In the present embodiment, a method for calculating a 3n-bit Montgomery multiplication remainder has been described. However, by increasing the number of steps, it is possible to calculate a Montgomery multiplication remainder having a bit number that is an integer multiple of n bits, which is a large number of bits, in a short time. be.

(Embodiment 4)
Next, Embodiment 4 will be described. In the present embodiment, an arithmetic unit (first arithmetic unit) that performs n-bit Montgomery multiplication remainder and an arithmetic unit (second arithmetic unit) that performs n-bit multiplication are provided independently of each other. FIG. 9 is a diagram showing an example of the configuration of an arithmetic processing device according to Embodiment 4 of the present invention. In an arithmetic processing device 201 shown in FIG. 9, the arithmetic unit 20 of FIG. 1 is replaced with arithmetic units 221 and 222 . Arithmetic unit 221 calculates an n-bit Montgomery multiplication remainder based on instructions from CPU 10 . Arithmetic unit 222 executes n-bit multiplication based on instructions from CPU 10 .

Arithmetic processing device 201 according to the present embodiment can execute multi-operation including calculation of n-bit Montgomery multiplication remainder by arithmetic unit 221 and n-bit multiplication by arithmetic unit 222 in parallel. FIG. 10 is a diagram showing an example of a procedure for parallel execution of multi-operation and n-bit multiplication according to Embodiment 4 of the present invention. FIG. 10 shows a parallel execution procedure using the algorithm of FIG. 2 as an example.

Consider the algorithm of FIG. The multi-calculation in Step 3 can be executed using only the input value (Input). Therefore, the n-bit multiplication in Step 1 and the multi-operation in Step 3 can be executed in parallel. Also, during execution of Step 3, it is possible to parallelly execute Step 1 and then Step 2 of n-bit multiplication.

On the other hand, the n-bit multiplication of Step 4 requires the operation result "q ₂ " of Step 3, so Step 4 cannot be executed until the processing of Step 3 is completed. Further, since the multi-calculation of Step 5 requires the calculation result "q ₃ " of Step 4, Step 5 cannot be executed until the processing of Step 4 is completed. Further, since the n-bit multiplication in Step 6 requires the operation result "q ₄ " in Step 5, Step 6 cannot be executed until the processing of Step 5 is completed.

Therefore, in the arithmetic processing unit 201, Step 1 and Step 3, and Step 2 and Step 3 can be executed in parallel with respect to the algorithm of FIG.

FIG. 11 is a diagram showing another example of a procedure for parallel execution of multi-operation and n-bit multiplication according to Embodiment 4 of the present invention. FIG. 11 shows a parallel execution procedure using the algorithm of FIG. 7 as an example. As shown in FIG. 11, during multi-operation in Step 3, n-bit multiplications in Steps 2, 6, and 8 can be sequentially executed in parallel. At the time of multi-operation in Step 9, the n-bit multiplications in Steps 1, 5 and 7 can be sequentially executed in parallel.

The order of n-bit multiplication is partially changed, but this is due to consideration of the timing of obtaining the required value in each step. For example, the value “q ₀ ” obtained in Step 1 is not used until multi-operation in Step 12 . Therefore, Step 1 does not necessarily have to be executed first. On the other hand, since the multi-calculation in Step 9 requires the calculation result "q ₇ " in Step 8, it is desirable to be executed in parallel with Step 3. Then, Step 3 and Step 9 can be executed continuously. As for the other steps, the order of execution is appropriately determined according to the circumstances described here.

According to the present embodiment, it is possible to execute in parallel the multi-operation including the calculation of the n-bit Montgomery multiplication remainder by the arithmetic unit 221 and the n-bit multiplication by the arithmetic unit 222. The calculation time required for calculating the Montgomery multiplication remainder is further shortened.

(Embodiment 5)
Next, Embodiment 5 will be described. In this embodiment, a case of executing multi-operation by n-bit multiplication and addition/subtraction will be described. FIG. 12 is a diagram showing an example of a configuration of an arithmetic processing device according to Embodiment 5 of the present invention. A processor 301 shown in FIG. 12 has a calculator 320 instead of the calculator 20 in FIG. Arithmetic unit 320 executes n-bit multiplication based on instructions from CPU 10 . That is, in the present embodiment, calculation of the n-bit Montgomery multiplication remainder is not performed directly in the calculator.

FIG. 13 is a diagram illustrating an algorithm for multi-operation according to Embodiment 5 of the present invention. In the multi-operation of FIG. 13, "a, b, n, m, s" are input and "q, r" are output. Note that s is a value defined by n ⁻¹ (mod m) and is calculated in advance by the CPU 10 or the like before executing the multi-operation.

In Step 1, [a, b] are used as inputs and their multiplication is executed to calculate the values {c ₁ , c ₀ }. Note that when b=1, {c ₁ , c ₀ }=a. In Step 2, [c ₀ , s] is input and these are multiplied and the like to calculate the value "q". In Step 3, multiplication with [q, n] as input and addition/subtraction with [c ₀ , c ₁ ] as input are executed.

14 and 15 are flow diagrams corresponding to the algorithm of FIG. FIG. 14 is a flowchart relating to calculation of the 2n-bit Montgomery multiplication remainder, and corresponds to FIG. FIG. 15 is a flowchart relating to calculation of the 3n-bit Montgomery multiplication remainder, and corresponds to FIG.

14 and 15, step S104 of FIG. 3 is replaced with step S304. Step S304 includes steps S304a-S304e. In step S304a, it is determined whether the input value "b" is one. When the CPU 10 determines that b≠1 (No), the process of step S304b is executed. On the other hand, when the CPU 10 determines that b=1 in step S304a (Yes), the process of step S304c is executed.

In step S304b, the process of step 1 in FIG. 13 is executed. The CPU 10 sends the value "a,b" to the calculator 320 and instructs it to perform the multiplication. Arithmetic unit 320 executes multiplication (a*b) with [a, b] as input in accordance with an instruction from CPU 10 . The calculated values {c ₁ , c ₀ } are stored in the memory 30, for example.

In step S304c, the process of step 2 in FIG. 13 is executed. The CPU 10 sends the value [c ₀ , s] to the calculator 320 and commands it to perform the multiplication. The arithmetic unit 320 executes multiplication (c ₀ *s) with [c ₀ , s] as input according to the instruction of the CPU 10 . The calculated value “q” is held in the memory 30, for example.

In steps S304d to S304e, the process of step 2 in FIG. 13 is executed. In step S304d, the CPU 10 sends the value [q, n] to the arithmetic unit 320 and instructs it to perform multiplication. The arithmetic unit 320 executes multiplication (q*n) with [q, n] as input according to the instruction of the CPU 10 . The calculated value “q*n” is held in the memory 30, for example.

In step S304e, the CPU 10 calculates the value "r" using the value "q*n" calculated in step S304 and the value [ _c0 , _c1 ]. The calculated value "r" is held in the memory 30, for example. Thus, the value (q, r) is calculated by multi-operation. Thus, the value calculated by the multi-operation of step S304 including multiplication and addition/subtraction is the same as the value calculated by the multi-operation of S104 including calculation and addition of the n-bit Montgomery multiplication remainder.

In the multi-operations of FIGS. 14 and 15, two calculations of the n-bit Montgomery multiplication remainder are changed to three multiplications. Therefore, in the calculation of the 2n-bit Montgomery multiplication remainder, 6 (3×2) multiplications are executed in the multi-operation. Further, in the calculation of the 3n-bit Montgomery multiplication remainder, 9 (3×3) multiplications are executed in multi-operations. Also, the number of multiplications in the multi-operation is reduced according to the value of b.

According to this embodiment, multi-operations are executed by multiplication and addition/subtraction. According to this configuration, it is not necessary to calculate the n-bit multiplication remainder, so the operation time required for calculating the Montgomery multiplication remainder of 2n bits, 3n bits, or the like can be further shortened.

The arithmetic processing units according to the embodiments described so far are installed in, for example, network equipment, automobiles, industrial equipment, etc. that require security functions. Further, the arithmetic processing device may be configured as a semiconductor device including other functions.

The invention made by the present inventor has been specifically described above based on the embodiments, but the present invention is not limited to the above embodiments, and various modifications can be made without departing from the gist of the invention. Needless to say.

1, 101, 201, 301... Arithmetic processing unit 10... CPU 20, 120, 221, 222, 320... Arithmetic unit 30... Memory

Claims (7)

a CPU;
an arithmetic unit that switches between calculating an n-bit Montgomery multiplication remainder or n-bit multiplication according to instructions from the CPU;
memory;
An arithmetic processing method for calculating a Montgomery multiplication remainder having a number of bits that is an integral multiple of n bits by combining calculation of an n-bit Montgomery multiplication remainder and n-bit multiplication in time series, wherein
Based on the program read from the memory, the CPU selects the calculation of the n-bit Montgomery multiplication remainder as the calculation method when the count value is a predetermined value, and when the count value is not the predetermined value a first step of selecting n-bit multiplication as the method of operation;
a second step in which the CPU causes the arithmetic unit to execute an arithmetic operation according to the selected arithmetic method, updates the count value when the execution is completed, and returns to the first step;
having
Arithmetic method. In the arithmetic processing method according to claim 1,
The arithmetic unit is provided independently of a first arithmetic unit for calculating an n-bit Montgomery multiplication remainder and a second arithmetic unit for performing n-bit multiplication,
When the CPU selects the calculation of the n-bit Montgomery multiplication remainder in the first step, the CPU causes the first computing unit to perform an operation in the second step, and when the n-bit multiplication is selected in the first step, causing the second computing unit to perform computation in the second step;
Arithmetic method. In the arithmetic processing method according to claim 1,
The CPU uses the calculator to calculate a 2n-bit or 3n-bit Montgomery multiplication remainder,
Arithmetic method. a CPU;
an arithmetic unit that switches between calculating an n-bit Montgomery multiplication remainder or n-bit multiplication according to instructions from the CPU;
memory;
with
Based on the program read from the memory, the CPU selects calculation of an n-bit Montgomery multiplication remainder when the count value is a predetermined value, and n-bit multiplication when the count value is not the predetermined value. is selected and executed by the arithmetic unit, and when the execution is completed, the processing of updating the count value is repeated, so that the calculation of the n-bit Montgomery multiplication remainder and the n-bit multiplication are combined in time series to obtain n-bit Calculate the Montgomery multiplication remainder of the number of bits of the integer multiple,
Arithmetic processing unit. In the arithmetic processing device according to claim 4 ,
The arithmetic unit is provided independently of a first arithmetic unit for calculating an n-bit Montgomery multiplication remainder and a second arithmetic unit for performing n-bit multiplication.
Arithmetic processing unit. In the arithmetic processing device according to claim 4 ,
The CPU uses the calculator to calculate a 2n-bit or 3n-bit Montgomery multiplication remainder,
Arithmetic processing unit. Equipped with the arithmetic processing device according to claim 4 ,
semiconductor device.

Images