JP5387291B2 - Arithmetic program, arithmetic method, and arithmetic device - Google Patents

Description

  The present invention relates to an arithmetic program, an arithmetic method, and an arithmetic device that execute arithmetic processing.

  A CPU (Central Processing Unit) installed in an embedded device such as a mobile phone, an in-vehicle device, or a hard disk device has a lower processing capacity than a CPU installed in a PC (Personal Computer). Also, the amount of memory mounted is generally low. Furthermore, in an embedded device, in order to confirm whether a task has stopped abnormally, the existence of the task may be confirmed by responding to a control unit such as an OS (Operating System) at regular intervals. As a response destination, in addition to a control unit in the apparatus, there is a case of responding to another apparatus via a network.

  On the other hand, RSA (Rivest-Shamir-Adleman) encryption processing used in the field of information security has a large calculation load, and the CPU of an embedded device with a low processing capacity takes a long time to occupy the CPU. May not be able to finish the RSA encryption process within. If the process cannot be completed within a certain time, the task executing the RSA encryption process cannot respond to the control unit, and the control unit misrecognizes that the task is abnormally stopped. . In order to prevent the recognition, it is necessary to interrupt the RSA encryption process halfway and to respond to the control unit, and then restart the RSA encryption process.

  Regarding the above-described problem of dividing the RSA encryption process, a technique is disclosed in which the modular multiplication process that should constitute most of the RSA encryption process is divided into predetermined partial multiplications (for example, the following patent documents) 1). In addition, a technique is disclosed in which Montgomery multiplication remainder calculation processing, which is a method for speeding up the modular exponentiation, is executed by being divided into a plurality of times (for example, see Patent Document 2 below).

JP 2003-29627 A JP-A-8-169322

  However, in the above-described prior art, when the RSA encryption process is divided, equal division is performed so that each divided RSA encryption division process has the same length. For this reason, there is a problem that idle time is generated in the CPU and there is wasted time.

  In addition, when performing partial multiplication, as a pre-processing in advance, there is a case where a pre-calculation table for storing a power residue calculation result is generated for a certain range of power, and the pre-calculation table is referred to. However, the size of the pre-computation table is always a fixed size, and if the remainder calculation process that should refer to the fixed pre-computation table is performed within the free time of the CPU, not all of the free time can be used, There was a problem that free time might remain.

  In order to solve the above-described problems due to the prior art, the present invention can divide RSA encryption processing non-uniformly according to CPU idle time and improve processing efficiency, an arithmetic method, and an arithmetic operation. An object is to provide an apparatus.

  In order to solve the above-described problems and achieve the object, the present calculation program, calculation method, and calculation apparatus detect the CPU idle time and process required for the multiplication remainder calculation process that constitutes the idle time and the exponentiation remainder calculation process The number of bits that can be processed within the free time is calculated based on the time and the number of times of use of the modular multiplication operation in the predetermined partial operation processing, and the bit string is calculated from the target data based on the calculated number of bits that can be processed. It is necessary to perform extraction and give an extracted bit string to execute a predetermined partial operation process.

  According to the calculation program, the calculation method, and the calculation device, there is an effect that the RSA encryption processing is divided non-uniformly in accordance with the CPU idle time, and the processing efficiency can be improved.

FIG. 2 is a block diagram illustrating a hardware configuration of the arithmetic device according to the first embodiment. 2 is a block diagram showing a functional configuration of the arithmetic device 100. FIG. It is a figure which shows the execution state by a prior art example and Embodiment 1. FIG. It is a figure which shows the outline | summary description of a binary method. It is a figure which shows the execution state by the RSA encryption non-uniform | heterogenous division process by a binary method. It is a figure which shows the outline | summary description of the window method. It is a figure which shows the processing time of a window method. It is a figure which shows the execution state by the RSA encryption non-uniform | segmentation process by a window method. It is a figure which shows the example of processing time which performed the RSA encryption non-uniform | segmentation process by the window method. It is a flowchart which shows a RSA encryption non-equal split process. 5 is a flowchart showing an optimal mounting method acquisition and a processable bit number calculation process according to the first embodiment; 10 is a flowchart showing an optimal mounting method acquisition and a processable bit number calculation process according to the second embodiment; 10 is a flowchart showing an optimal mounting method acquisition and a processable bit number calculation process according to the third embodiment; 10 is a flowchart showing an optimal mounting method acquisition and a processable bit number calculation process according to the fourth embodiment;

  Exemplary embodiments of a calculation program, a calculation method, and a calculation device according to the present invention will be described below in detail with reference to the accompanying drawings.

(Embodiment 1)
(Hardware configuration of arithmetic device 100)
FIG. 1 is a block diagram of a hardware configuration of the arithmetic device according to the first embodiment. In FIG. 1, a computing device 100 includes a CPU 101, a ROM (Read-Only Memory) 102, a RAM (Random Access Memory) 103, a magnetic disk drive 104, a magnetic disk 105, an optical disk drive 106, an optical disk 107, and the like. A display 108, an I / F (Interface) 109, a keyboard 110, a mouse 111, a scanner 112, and a printer 113. Each component is connected by a bus 114.

  Here, the CPU 101 governs overall control of the arithmetic device 100. In addition to the CPU, a DSP (Digital Signal Processor) used in an embedded device that requires real-time processing may be used.

  The ROM 102 stores a program such as a boot program. The RAM 103 is used as a work area for the CPU 101. The magnetic disk drive 104 controls reading / writing of data with respect to the magnetic disk 105 according to the control of the CPU 101. The magnetic disk 105 stores data written under the control of the magnetic disk drive 104. Further, a flash ROM may be used instead of the magnetic disk 105 for the purpose of reducing the size of the arithmetic unit 100.

  The optical disk drive 106 controls reading / writing of data with respect to the optical disk 107 according to the control of the CPU 101. The optical disc 107 stores data written under the control of the optical disc drive 106, and causes the computer to read data stored on the optical disc 107.

  The display 108 displays data such as a document, an image, and function information as well as a cursor, an icon, or a tool box. As this display 108, for example, a CRT, a TFT liquid crystal display, a plasma display, or the like can be adopted.

  The I / F 109 is connected to a network 115 such as a LAN (Local Area Network), a WAN (Wide Area Network), and the Internet through a communication line, and is connected to other devices via the network 115. The I / F 109 controls an internal interface with the network 115 and controls input / output of data from an external device. For example, a modem or a LAN adapter may be employed as the I / F 109.

  The keyboard 110 includes keys for inputting characters, numbers, various instructions, and the like, and inputs data. Moreover, a touch panel type input pad or a numeric keypad may be used. The mouse 111 performs cursor movement, range selection, window movement, size change, and the like. A trackball or a joystick may be used as long as they have the same function as a pointing device.

  The scanner 112 optically reads an image and takes in the image data into the arithmetic device 100. The scanner 112 may have an OCR (Optical Character Reader) function. The printer 113 prints image data and document data. For example, a laser printer or an ink jet printer can be employed as the printer 113. In an embedded device environment, the magnetic disk drive 104, magnetic disk 105, optical disk drive 106, optical disk 107, display 108, I / F 109, keyboard 110, mouse 111, scanner 112, printer 113, part of the network 115, or A configuration in which everything does not exist may be used.

(Functional configuration of arithmetic device 100)
Next, a functional configuration of the arithmetic device 100 will be described. FIG. 2 is a block diagram illustrating a functional configuration of the arithmetic device 100. The arithmetic device 100 includes a control unit 201, a process control unit 202, a reception unit 203, a calculation unit 204, a timer 205, a free time calculation unit 206, a reference required time storage table 207, and a processing time acquisition unit 208. It is the structure containing these. Specifically, the functions (control unit 201 to processing time acquisition unit 208) serving as the control unit are, for example, programs stored in a storage device such as the ROM 102, RAM 103, magnetic disk 105, and optical disk 107 shown in FIG. Is executed by the CPU 101. Alternatively, the function may be realized by another CPU executing via the I / F 109.

  The control unit 201 is an OS that controls the arithmetic device, and has a function of instructing the processing control unit 202 to perform processing in order to execute all tasks including the arithmetic unit 204. Specifically, for example, the control unit 201 instructs the process control unit 202 to execute the task B after the process control unit 202 finishes executing the task A.

  The process control unit 202 has a function of executing a task in accordance with an instruction from the control unit 201. Also, after executing a task other than the calculation unit 204, the free time until the response is returned to the OS is acquired from the free time calculation unit 206. Specifically, for example, when the cycle of returning a response to the OS is 30 [msec] (milliseconds) and the CPU 101 executes another task for 10 [msec], the process control unit 202 sets the free time as 20 [msec]. msec]. The acquisition result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The receiving unit 203 has a function of receiving data to be subjected to power-residue calculation processing. Specifically, for example, when encryption is performed, the target data is plaintext, and information on the public key is also received as target data corresponding to the exponent part of the power-residue calculation process. The reception result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The calculation unit 204 is one of the functions executed by the process control unit 202, and has a function of performing a power-residue calculation process in the RSA encryption process. Specifically, for example, a ciphertext is generated from plaintext by performing a power-residue calculation process of ciphertext = plaintext ^ public key (modN). Also, plain text is generated from the ciphertext by performing a power-residue calculation process of plaintext = ciphertext ^ cryptographic key (modN). Details of the inside of the calculation unit 204 will be described later. The calculation result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The timer 205 has a function of causing the CPU 101 to generate interrupts at regular intervals. Specifically, for example, when an interrupt is generated by the timer 205, the internal time is updated by incrementing a counter managed by the control unit 201. The counter is stored in a register held by the CPU 101, for example.

  The free time calculation unit 206 has a function of calculating the free time from the internal time of the timer 205. Specifically, for example, the idle time can be obtained by subtracting the current time from the time when the response is returned to the OS next time. The calculation result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The reference required time storage table 207 is an area in which the time required for the modular multiplication operation is calculated or measured in advance and stored. The multiplication residue calculation process may be a Montgomery multiplication residue calculation process, which is a method for speeding up the power residue calculation process. Specifically, for example, when plaintext is converted into ciphertext, the bit length of the data subject to the remainder calculation process that should be plaintext, the bit length of the power that should be the secret key, and the bit length of the modulus that is the public key As an index, the time required for Montgomery multiplication remainder calculation processing is stored.

  Also, the index may include whether the processing method is CRT (Chinese Reminder Theorem) or non-CRT. The reference required time storage table 207 is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107. Or you may hold | maintain the result measured beforehand in ROM102. In addition, the result of the 1024-bit multiplication residue calculation process without an index may be stored and handled implicitly as 1024 bits when used.

  The processing time acquisition unit 208 has a function of acquiring the processing time required for the modular multiplication operation that constitutes the modular exponentiation processing. Specifically, for example, the arithmetic unit 100 specifies the bit length of the data to be subjected to the power-residue calculation process, the bit length of the power, and the bit length of the modulus from the reference required time storage table 207, Get the processing time when the above is true. The acquisition result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  Next, functional details of the arithmetic unit 204 according to the first embodiment will be described. The calculation unit 204 includes a detection unit 209, a calculation unit 210, an extraction unit 211, an execution unit 212, a setting unit 213, a table generation unit 214, and a table acquisition unit 215.

  The detection unit 209 has a function of detecting an idle time until processing having a higher priority than power residue calculation processing is performed. Specifically, for example, the idle time calculating unit 206 detects the idle time up to the time when a response is returned to the next OS when processing of another task is completed. The detection result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The calculation unit 210 calculates the number of bits that can be processed within the vacant time based on the processing time required for the modular multiplication operation process, the number of times the modular multiplication operation is used in the partial arithmetic process of the power modular arithmetic process, and the vacant time. Has the function of The processing time is detected from the processing time acquisition unit 208, and the idle time is detected from the detection unit 209. The partial calculation processing is a binary method or window method described later. Furthermore, the number of bits that can be processed within the free time may be calculated based on the bit string of the target data received by the receiving unit 203.

  When the binary method is implemented in the partial arithmetic processing, the following formula (1) may be used as a calculation formula for the number of bits that can be processed. Hereinafter, this calculation method is referred to as “processable bit number calculation method 1”. In the first embodiment, the processable bit number calculation method 1 is applied.

  Kb = Floor ((T / t-1) / 2) (1)

  Here, Kb represents the number of bits that can be processed, Floor () represents the floor function, T represents the idle time, and t represents the processing time required for the modular multiplication operation.

  When the window method is implemented in the partial arithmetic processing, the following formula (2) may be calculated as a calculation formula for the number of bits that can be processed. Hereinafter, this calculation method is referred to as “processable bit number calculation method 2”. In the second embodiment to be described later, the processable bit number calculation method 2 is applied.

  Kb = Floor ((T / t−2 ^ n) / (n + 1)) * n (2)

  Where Kb is the number of bits that can be processed, Floor () is the floor function, T is the idle time, t is the processing time required for the modular multiplication operation, and n is the window method. Indicates the number of bits of interest. Hereinafter, the window width is used.

  When the binary method is implemented in the partial operation processing, the number of usable operations that is the number of times that the modular multiplication operation processing can be used within the vacant time is obtained by the following equation (3). Then, by adding the number of times the operation has been performed according to the value of the target bit, the target bit is sequentially read out until the number of times the operation has been performed reaches the number of usable operations, and the number of read target bits can be processed. It may be calculated as a number. Specifically, if the target bit is 0, the number of times is added by 1, and if the target bit is 1, the number of times is added by 2. Hereinafter, this calculation method is referred to as “processable bit number calculation method 3”. In the third embodiment to be described later, the processable bit number calculation method 3 is applied.

  a = Floor (T / t-1) (3)

  Here, “a” indicates the number of usable operations, “Floor ()” indicates the floor function, “T” indicates the idle time, and “t” indicates the processing time required for the modular multiplication operation processing.

  In the binary method, when the target bit is 0, the modular multiplication process is performed once, and when it is 1, the modular multiplication process is performed twice. Therefore, the number of bits that can be processed can be calculated by calculating the number of times of performing the modular multiplication operation along the value of the target bit.

  When the window method is implemented in the partial operation processing, the number of usable operations, which is the number of times that the modular multiplication operation processing can be used within the free time, is obtained by the following equation (4). Then, the number of times of calculation is added according to the bit pattern that can be taken by the bit string corresponding to the window width. The bit string may be sequentially read out until the number of times that the calculation has been performed becomes the number of times the calculation can be used, and the number of bits constituting the read bit string may be calculated as the number of bits that can be processed. Specifically, if the bit strings are all 0, the number of times is added by the window width, and if the bit string contains 1 the number of times is added by the window width + 1. Hereinafter, this calculation method is referred to as “processable bit number calculation method 4”. In the fourth embodiment to be described later, the processable bit number calculation method 4 is applied.

  a = Floor (T / t-2 ^ n) (4)

  Here, “a” represents the number of usable operations, “Floor ()” represents the floor function, “T” represents the idle time, “t” represents the processing time required for the modular multiplication operation, and “n” represents the window width.

  In the window method, when the n-bit bit string is all 0, the modular multiplication process is performed n times, and when the bit string includes 1 the modular multiplication process is performed n + 1 times. Therefore, the number of bits that can be processed can be calculated by calculating the number of times of performing the modular multiplication operation along the value of the n-bit bit string.

  For the window width n in the second or fourth embodiment, the number of bits that can be processed is calculated for each possible window width, and the extraction unit 211 described later extracts the longest number of bits. It may be executed by the executing unit 212. Further, it may be calculated including the generation time of the table set by the setting unit 213 described later at the time of calculation.

  Moreover, the form which has multiple Embodiment 1-4 simultaneously may be sufficient. Specifically, for example, the binary method according to the first embodiment and the binary method according to the second embodiment are simultaneously provided, and the number of bits that can be processed is calculated. Then, a partial calculation process that maximizes the number of bits that can be processed and the number of bits that can be processed may be used.

  As a specific example of the calculation, for example, consider a case where the processing time required for the modular multiplication operation is 0.1 [msec], the partial operation processing is the binary method, and the free time is 20 [msec] in the first embodiment. The number of times of use of the modular multiplication operation in the binary method is twice for one bit. Under the above-described conditions, it is possible to calculate that 99 bits can be processed in the free time by using Kb = Floor ((20 / 0.1-1) / 2) by using Equation 1 described later. The calculation result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The extraction unit 211 has a function of extracting a bit string corresponding to the number of bits calculated by the calculation unit 210 from the target data received by the reception unit 203. In addition, the start bit position for starting the partial operation processing is read from the storage device, and the bit string corresponding to the calculated number of bits is extracted from the start bit position of the target data. Thereafter, for the next calculation, a new start bit position may be obtained based on the start bit position and the calculated number of bits and stored in the storage device as the start bit position.

  Specifically, for example, when the calculation unit 210 receives a calculation result indicating that 99 bits can be processed, the extraction unit 211 reads the bit string of 99 bits from the start of the target data or the start bit position stored in the storage device. To extract. The calculation result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The execution unit 212 has a function of executing a partial calculation process on the bit string extracted by the extraction unit 211. Specifically, for example, in the first or third embodiment, the binary method is executed. In the second or fourth embodiment, the window method is executed. The outline of the binary method will be described later with reference to FIG. 4, and the outline of the window method will be described later with reference to FIG.

  The setting unit 213 has a function of setting, using the processing time acquisition unit 208, a table creation time generated by the table generation unit 214 described later for each window width when the partial calculation processing is a window method. Specifically, for example, if the window width is 2, the table creation time can be set to 2 ^ 2 × (remainder operation processing). The setting result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The table generation unit 214 stores, as a process to be performed in advance when the partial calculation process is the window method, a value obtained by performing the power residue for each bit pattern that can be taken by the bit string of the window width as the data to be subjected to the power residue calculation process. It has a function to generate a table to do. Specifically, for example, when the window width is 4 bits, the target data is X, and the modulus is Z, X ^ 0 (modZ), X ^ 1 (modZ), ..., X ^ 15 (modZ) Is obtained and stored in a table. The generation result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  The table acquisition unit 215 has a function of acquiring, from the table generated by the table generation unit 214, a value obtained by performing a power residue on the target data in the bit pattern from the table generated by the table generation unit 214 when the partial calculation processing is the window method. Have. Specifically, for example, when the window width is 4 bits, the target data is X, the modulus is Z, and the bit pattern in the window is 9, X ^ 9 (modZ stored in the table) ) Value. The acquisition result is stored in a storage area such as the RAM 103, the magnetic disk 105, and the optical disk 107.

  Using the above devices and functions, the arithmetic device 100 performs a modular exponentiation operation. Next, the execution state according to the conventional example and the first embodiment will be described.

(Overview of Embodiment 1)
FIG. 3 is a diagram showing an execution state according to the conventional example and the first embodiment. As a precondition, a response is returned to the OS every 10 [msec]. The execution state 301 in the conventional example shows a state in which a divided RSA encryption process is performed after another task is executed. In the case of equally dividing the RSA encryption process, the free time 303, 20-30 in other intervals, for example, 0-10 [msec], in order to match the interval of 10-20 [msec] with the shortest free time. Free time 304 occurs in the [msec] section.

  In the first embodiment, the RSA encryption processing is divided into processes by dynamically calculating each idle time and efficiently using the CPU. In the execution state 302 according to the first embodiment, the RSA encryption processing is performed in the partial arithmetic processing 305 in the interval of 0 to 10 [msec], and in the partial arithmetic processing 306 and 20 to 30 [msec] in the interval of 10 to 20 [msec]. In this section, the partial calculation processing 307 is not equally divided.

  FIG. 4 is a diagram showing an overview of the binary method. In the first embodiment, the binary method is implemented in the partial arithmetic processing. The binary method is a method in which a power part is expressed in a binary number, and a power-residue calculation process is performed for each bit on the obtained bit string. When there is a plaintext X, a public key d, and a modulus Z, a ciphertext Y to be obtained can be expressed as Y = X ^ d (modZ).

  Here, a specific example of the binary method is shown with d = 21. When d = 21 is expressed in binary notation, (10101) is obtained, and Expression 401 is obtained. In Equation 401, reference numerals 402, 403, 405, and 406 represent multiplication by two, and reference numerals 404 and 407 represent multiplication. These multiplications and double multiplications indicated by reference numerals 402 to 407 correspond to the respective bits in the binary notation (10101) of d = 21. The double multiplication of the code 402 corresponds to 0 which is the second most significant bit in the binary notation (10101). Hereinafter, in order, the multiplication by 2 of the reference numeral 403 and the multiplication by the reference numeral 404 correspond to 1 which is the third bit from the most significant bit. The double multiplication of the reference numeral 405 corresponds to 0 which is the fourth bit from the most significant bit. In the multiplication by 406 and the multiplication by 407, 1 which is the least significant bit corresponds.

  Therefore, X ^ 21 can be obtained by performing multiplication by 2 when the target bit other than the head of the bit string is 0, and by performing multiplication after performing 2 multiplication when the target bit is 1. In addition, because of the property of the congruence formula, A * B (modZ) = (A (modZ)) * (B (modZ)) (modZ). Therefore, by further multiplying the results of the multiplication remainders, The same result as the power residue can be obtained.

  FIG. 5 is a diagram showing an execution state by the RSA encryption non-uniform division processing by the binary method. In the execution state 501 of the RSA encryption non-division process, a response cannot be returned to the OS at the stage of 10 [msec]. The execution state 502 of the conventional example is an example in which the binary method is divided at two multiplications. By providing a timer, RSA encryption processing is assigned according to the free time.

  In the execution state 503 of the conventional example using Montgomery multiplication remainder, pre-processing necessary for using Montgomery multiplication remainder is performed. Therefore, in the interval from 0 to 10 [msec], the RSA cipher division processing 505 is 10 [msec]. ] Has been exceeded. Similarly, the RSA cipher partitioning process 506 has exceeded each section in the section of 10 to 20 [msec], and the RSA cipher partitioning process 507 has exceeded each section in the section of 20 to 30 [msec]. It cannot be returned.

  In the execution state 504 in the first embodiment, the number of bits that can be processed is calculated including the time for the preprocessing of the Montgomery multiplication remainder. For this reason, the RSA cipher partitioning process is assigned so as to end in each section of 0 to 10 [msec], 10 to 20 [msec], 20 to 30 [msec], and 30 to 40 [msec]. The formula for calculating the bits that can be processed within the free time is formula (1).

(Overview of the second embodiment)
FIG. 6 is a diagram showing an outline description of the window method. The hardware configuration of the second embodiment is the same as that shown in the first embodiment and the functional configuration is the same, but the partial arithmetic processing is implemented with the window method. Further, the calculation unit 210 also has a function according to the partial calculation process. The bit string 601 is obtained by expressing d in binary notation with Y = X ^ d (modZ). Next, the bit string is divided into k bits in FIG. 6 for a predetermined window width, and a power residue calculation process is performed on the k bit bit string obtained by the division. A window b _m−1 , a window b _{m− 2} ,..., A window b ₁ , and a window b ₀ are divided, and the result obtained by the division is Expression 602.

Also, w [0] = X ^ 0 (modZ), w [1] = X ^ 1 (modZ),..., W [2 ^ (k-1)] = X ^ (2 ^ (k-1 )) Up to (modZ) is prepared in advance as a pre-calculation table. Using the defined w [], the window b _m-1 is replaced with w [1111]. Similarly, the window b _m-2 is replaced with w [0110], b ₁ is replaced with w [1001], and b ₀ is replaced with w [1101]. After the replacement, Y = X ^ d (modZ) can be obtained by repeating 2 multiplications k times for each window and further performing 1 multiplication with w [] once.

  In an environment with abundant memory, a pre-calculation table with a data amount of about 23 to 25 bits is prepared by pre-calculation, and high-speed processing can be performed by referring to this pre-calculation table when executing a power-residue calculation. realizable. However, in the embedded environment, the pre-calculation table cannot be kept inside from the viewpoint of the amount of installed memory, etc., so the table is generated each time execution is performed, and overhead is applied. Therefore, if a table with a large bit width to be referred to at one time is prepared, the power-residue calculation process can be executed at a high speed, but the time for generating the pre-calculation table increases.

  FIG. 7 is a diagram illustrating the processing time of the window method. The window method is divided into two processes, that is, a process for generating a pre-calculation table and a process for performing a power-residue calculation process. FIG. 7 shows the processing time for generating the pre-calculation table and the processing time for the power-residue processing in accordance with the respective window widths.

  For example, when the window width is 2 bits, it takes 2 ^ 2 × (remainder operation processing) for table generation, and (b + b / 2) × (remainder operation processing) for power residue operation processing. It will be. Here, b is the bit length of the target data. If the window width is n bits, it takes 2 ^ n × (remainder operation processing) for table generation, and (b + b / n) × (remainder operation processing) for power residue operation processing. Become.

  FIG. 8 is a diagram showing an execution state by the RSA encryption non-uniform division processing by the window method. In the window method execution state 801 in which the window width is fixed at 4 bits, a free time 803 is generated in a section of 10 to 20 [msec], and a free time 804 is generated in a section of 20 to 30 [msec]. . The reason why the idle time occurs is that the window method performs processing all at once compared to the binary method, and thus there is a case where an empty space is generated.

  Next, in the execution state 802 of the second embodiment, the window width can be dynamically changed in accordance with the free time so that the free time can be used as much as possible. Specifically, the window width is 4 bits in the interval of 0 to 10 [msec]. Similarly, in the interval of 10 to 20 [msec], the window width is 2 bits, in the interval of 20 to 30 [msec], the window width is 5 bits, and in the interval of 30 to 40 [msec], the window width is 4 bits. The window width is variable. The formula for calculating the bits that can be processed within the free time is formula (2).

  FIG. 9 is a diagram illustrating an example of processing time when the RSA encryption non-uniform division processing by the window method is performed. The number of bits of the target data for RSA encryption processing is 1024 bits. Further, an interval for returning a response to the OS is set to 30 [msec], and each field of the number of times of obtaining the optimum mounting method corresponds to another task processing time. For example, the first time is 12 [msec] and the second time is 10 [msec]. The surplus time T is a difference between an interval 30 [msec] for returning a response to the OS and another task processing time. The number of times a that can be subjected to the modular multiplication operation is a quotient of the remaining time T and the required time t required for one modular multiplication operation.

  Under the preconditions described above, Expression (2) is performed up to a window width of 1 to 5 bits, and the maximum Kb is acquired as the optimum mounting method. For example, in the first case, Kb (1) is 89 bits when the window width is 1 bit, similarly, Kb (2) is 116 bits, Kb (3) is 129 bits, Kb (4) is 128 bits, Kb (5) is 120 bits, and the maximum Kb is Kb (3). Therefore, the number of unprocessed bits is 895 bits, which is the difference between 1024 bits and 129 obtained by Kb (3). Thereafter, the same processing is performed for the second and subsequent times, and the remaining processing bits are repeated as 751 bits, 721 bits,. Since there are no remaining processing bits at the ninth time, the processing is terminated.

  Since the RSA encryption processing is completed in the ninth division processing, the processing time required for the RSA processing is 270 [msec] including the time of another task. If processing is performed in the conventional example, the processing time of the RSA cipher splitting process, which has the shortest remaining time, is set to 5 [msec]. When 4 bits are used as the window width, 24 bits can be processed at a time, and when the RSA encryption processing bit is 1024 bits, the process ends for the 43rd time at 1290 [msec].

(Functional description of Embodiments 1 to 4)
FIG. 10 is a flowchart showing RSA encryption non-uniform division processing. FIG. 10 is used in all the first to fourth embodiments, and corresponding processing is performed in each mode in step S1004 and step S1008 described later.

  The arithmetic device 100 detects the free time after execution of another task from the detection unit 209 and stores it in T (step S1001). Subsequently, the processing time of the modular multiplication operation process is acquired by the processing time acquisition unit 208 and stored in t (step S1002). The arithmetic device 100 uses T and t to calculate a = T / t (step S1003), and executes the optimum mounting method acquisition and the processable bit number calculation process using a as an argument (step S1004). Specific processing contents will be described later with reference to FIG. 11 in each embodiment, Embodiment 1 in FIG. 12, Embodiment 2 in FIG. 12, Embodiment 3 in FIG. 13, Embodiment 4 in FIG.

  If the optimal mounting method and the number of bits that can be processed have been acquired, the arithmetic unit 100 confirms whether this is the first RSA encryption process (step S1005). If it is the first time (step S1005: Yes), the target data received by the receiving unit 203 is acquired as input data (step S1006). If it is not the first time but the second time or later (step S1005: No), the RSA encryption process intermediate result stored in the storage device is acquired (step S1007). Next, the acquired optimum mounting method is executed for the acquired target data by the calculated number of processable bits (step S1008). As the optimum mounting method, the binary method is used in the first or third embodiment, and the window method is used in the second or fourth embodiment.

  After performing the optimal mounting method for the number of processable bits, the arithmetic device 100 confirms whether the RSA encryption processing is completed (step S1009). If completed (step S1009: Yes), the RSA encryption processing result is output (step S1010). If it has not been completed but is in progress (step S1009: No), the RSA encryption processing result is stored in the storage device (step S1011).

(Functional Description of Embodiment 1)
FIG. 11 is a flowchart of the optimum mounting method acquisition and processable bit number calculation processing according to the first embodiment. A flowchart of the processable bit number calculation method 1 is shown in FIG. The computing device 100 calculates Kb = Floor ((a-1) / 2) using a passed as an argument (step S1101). Kb obtained in step S1101 is the number of bits that can be processed, the binary method is output as the optimum mounting method, Kb is output as the number of bits that can be processed (step S1102), and the process is terminated.

(Functional Description of Embodiment 2)
FIG. 12 is a flowchart of optimal mounting method acquisition and processable bit number calculation processing according to the second embodiment. A flowchart of the processable bit number calculation method 2 is shown in FIG. The arithmetic device 100 initializes i to 1 (step S1201). Subsequent steps use i as the window width.

  Next, the computing device 100 calculates a-2 ^ i using a passed as an argument, and checks whether it is greater than 0 (step S1202). If it is larger than 0 (step S1202: Yes), Kb (i) = Floor ((a-2 ^ i) / (i + 1)) * i is calculated (step S1203). The calculated Kb (i) is held (step S1204), i is incremented in order to calculate with the next window width (step S1205), and the process proceeds to step S1202.

  When a-2 ^ i is 0 or less (step S1202: No), the arithmetic unit 100 sets the maximum value to Kb_max for Kb (1),. The window width value is set to i_max (step S1206). Finally, as an optimal mounting method, a window method with a window width of i_max is output, Kb_max is output as the number of processable bits (step S1207), and the process ends.

  Further, when the variable i has a window width that is not supported by the arithmetic device 100, the processing may be performed on the corresponding window width without performing the calculation process at the corresponding window width. Similarly, in step S1202, even if a-2 ^ i is larger than 0, if the table cannot be generated with the corresponding window width or more due to hardware limitations of the arithmetic device 100, step S1202: No route You may enter.

(Functional Description of Embodiment 3)
FIG. 13 is a flowchart of the optimum mounting method acquisition and processable bit number calculation processing according to the third embodiment. A flowchart of the processable bit number calculation method 3 is shown in FIG. The hardware configuration of the third embodiment is the same as that shown in the first embodiment and the functional configuration is the same. However, the calculation unit 210 determines the number of times that the modular multiplication operation can be used within the free time. The number of processable bits calculation method 3 is used as a calculation method.

  The computing device 100 sets Floor (a-1) to a using a passed as an argument (step S1301). A variable m indicating the number of times of use of the modular multiplication operation is prepared and initialized to 0 (step S1302). Subsequently, the processing start position s is set in the RSA encryption processing target bit string (step S1303). Then, a position p is prepared as a pointer indicating the RSA encryption processing target bit string, and is set to the same position as the position s (step S1304).

  The arithmetic device 100 confirms whether the position p is the head of the RSA encryption processing target bit string (step S1305). In the case of the head (step S1305: Yes), m = m + 1 is performed (step S1306), and it is confirmed whether m> a is satisfied (step S1310). If it is not the head (step S1305: No), it is confirmed whether the value of the bit at the position p is 1 (step S1307). If 1 (step S1307: Yes), m = m + 2 is performed (step S1309). If 0 (step S1307: No), m = m + 1 is performed (step S1308), and the process proceeds to step S1310.

  In step S1310, if m> a is not satisfied (step S1310: No), the arithmetic unit 100 subsequently checks whether the position p is at the end of the RSA encryption target bit string (step S1311). If it is not at the end (step S1311: No), the position p is moved downward by one (step S1312), and the process proceeds to step S1305. If it is at the end (step S1311: Yes), it means that the RSA encryption process has ended, and the process proceeds to step S1314 described later.

  If m> a in step S1310 (step S1310: Yes), the arithmetic unit 100 means that m has exceeded the number of bits that can be processed within the free time, and therefore the position p is set in the upper direction. (Step S1313). Subsequently, Kb is set to the number of bits from position s to position p (step S1314), the binary method is output as the optimum mounting method, and Kb is output as the number of processable bits (step S1315). In the case of the route of step S1311: Yes, it means that RSA encryption processing can be performed up to the lowest bit string, and therefore step S1313 is not performed but step S1314 is performed.

(Functional Description of Embodiment 4)
FIG. 14 is a flowchart of the optimum mounting method acquisition and processable bit number calculation processing according to the fourth embodiment. A flowchart of the processable bit number calculation method 4 is shown in FIG. The hardware configuration of the fourth embodiment is the same as that shown in the second embodiment and the functional configuration is the same. However, the calculation unit 210 determines the number of times that the modular multiplication operation can be used within the free time. The number of processable bits calculation method 4 is used as a calculation method. The arithmetic device 100 initializes i to 1 (step S1201). Subsequent steps use i as the window width.

  Next, the computing device 100 calculates a-2 ^ i using a passed as an argument (step S1402), and checks whether a> 0 (step S1403). If a> 0 (step S1403: Yes), a variable m indicating the number of times of use of the modular multiplication operation is prepared and initialized to 0 (step S1404). Subsequently, the processing start position s is set in the RSA encryption processing target bit string (step S1405). Then, a position p is prepared as a pointer pointing to the RSA encryption processing target bit string, and is set to the same position as the position s (step S1406).

  After setting the position p, the arithmetic unit 100 checks whether all the values of the bits from the position p to the (i−1) th bit are 0 (step S1407). If 0 (step S1407: Yes), m = m + i is performed (step S1409), and it is confirmed whether m> a is satisfied (step S1410). When a bit having a value of 1 is included (step S1407: No), m = m + i + 1 is performed (step S1408), and the process proceeds to step S1410.

  In step S1410, if m> a is not satisfied (step S1410: No), the arithmetic unit 100 subsequently checks whether the position p is at the end of the RSA encryption target bit string (step S1411). If it is not at the end (step S1411: No), the position p is moved in the lower direction by i (step S1412), and the process proceeds to step S1407. If it is at the end (step S1411: Yes), it means that the RSA encryption process has ended, and the process proceeds to step S1414 described later.

  If m> a in step S1410 (step S1410: Yes), the arithmetic unit 100 means that m has exceeded the number of bits that can be processed within the vacant time. To i (step S1413). Next, Kb (i) is held as the number of bits from position s to position p (step S1414), i is incremented (step S1415), and the process proceeds to step S1402.

  In step S1403, when a is 0 or less (step S1403: No), arithmetic device 100 sets the maximum value to Kb_max for Kb (1),. The window width value to be set is set to i_max (step S1416). Finally, as an optimal mounting method, a window method in which the window width is i_max is output, Kb_max is output as the number of processable bits (step S1417), and the process ends.

  Further, when the variable i has a window width that is not supported by the arithmetic device 100, the processing may be performed on the corresponding window width without performing the calculation process at the corresponding window width. Similarly, in step S1403, even if a is larger than 0, if the table cannot be generated with the window width or more due to hardware restrictions of the arithmetic device 100, the route of step S1403: No can be entered. Good.

  As described above, according to the arithmetic device 100, one-time RSA encryption processing can be completed in a short time by dividing the power-residue arithmetic processing non-uniformly according to the CPU idle time.

  When extracting a bit string, the bit string may be extracted sequentially. Thereby, the data from the beginning to the end of the target data of the power-residue calculation process can be divided into a plurality of non-uniformly divided processes. In the above embodiment, the method of scanning from the head to the tail is exemplified, but conversely, the scanning may be performed from the tail to the head.

  Further, when the number of bits that can be processed is calculated, if the partial calculation processing is a binary method, the number of bits that can be processed may be calculated based on the number of times of use of the modular multiplication operation in the binary method. Thereby, the number of bits that can be processed by the binary method can be calculated, the idle time of the CPU can be effectively used, and one RSA encryption process can be completed in a short time.

  Further, when calculating the number of bits that can be processed, when the partial arithmetic processing is a binary method, the equation (1) may be used. As a result, the number of bits that can be processed by the binary method can be calculated specifically, the idle time of the CPU can be effectively used, and one RSA encryption process can be completed in a short time.

  Further, when the number of bits that can be processed is calculated, when the partial operation processing is a binary method, the number of times that the modular multiplication operation processing can be used is obtained from Equation (3). Then, the number of times may be subtracted according to the value of the target bit of the target data, the target bits may be read sequentially until the number of times becomes zero, and the number of read target bits may be calculated as the number of bits that can be processed. As a result, when there are many 0s in the bit string of the target data and the modular multiplication operation process is often performed only once per bit by the binary method, a larger number of bits can be calculated.

  When calculating the number of bits that can be processed, if the partial calculation process is a window method, the number of bits that can be processed may be calculated based on the number of times of use of the modular multiplication operation in the window method. Thereby, the number of bits that can be processed by the window method can be calculated, the idle time of the CPU can be used effectively, and one RSA encryption process can be completed in a short time.

  Further, when calculating the number of bits that can be processed, when the partial calculation processing is a window method, the equation (2) may be used. As a result, the number of bits that can be specifically processed by the window method can be calculated, the CPU idle time can be used effectively, a table size suitable for the idle time can be created, and one RSA encryption process can be shortened. Can be completed in time.

  Further, when the number of bits that can be processed is calculated, when the partial operation processing is the window method, the number of times that the modular multiplication operation processing can be used is obtained from Equation (4). Then, the number of times is subtracted by the window width according to the bit pattern that can be taken by the bit string corresponding to the window width of the target data, the bit string is sequentially read out until the number becomes 0, and the number of bits constituting the read bit string can be processed It may be calculated as the number of bits. As a result, when there are many 0s in the bit string of the target data and the remainder calculation operation is often performed for the target bit string by the window method by the window method, a larger number of bits can be calculated. .

  When calculating the number of bits that can be processed, if the partial operation processing is a window method, calculate the number of bits for each possible window width, and extract the longest number of bits from among the calculated number of bits, A bit string may be extracted from the target data and the window method may be executed. As a result, the window width can be set in accordance with the change in the CPU idle time, and one RSA encryption process can be completed in a short time. In addition, since a pre-calculation table having an appropriate size is generated every time processing is divided non-uniformly according to CPU idle time, processing efficiency can be improved, and RSA encryption processing is completed in a short time. be able to.

  Also, RSA encryption processing has been taken as an example of a method for performing power-residue calculation processing, but other power-residue calculation processing and processing involving scalar multiplication of points on a curve, such as elliptic curve cryptography, EPOC (Efficient Probabilistic public) -Key (enCryption) encryption, Rabin encryption, El Gamal encryption, etc., can also use this embodiment.

  The calculation method described in this embodiment can be realized by executing a program prepared in advance on a computer such as a personal computer, a workstation, or an embedded device. The arithmetic program is recorded on a computer-readable recording medium such as a ROM, a nonvolatile memory, a hard disk, a flexible disk, a CD-ROM, an MO, and a DVD, and is executed by being read from the recording medium by the computer. The arithmetic program may be distributed via a network such as the Internet.

  The following additional notes are disclosed with respect to the embodiment described above.

(Appendix 1) Computer
Detecting means for detecting idle time until a response returned by the computer at regular intervals;
Based on the free time detected by the detecting means, the processing time required for the multiplication remainder calculation processing constituting the power residue calculation processing, and the number of times of use of the multiplication remainder calculation processing in a predetermined partial calculation processing, A calculation means for calculating the number of bits that can be processed;
Extraction means for extracting a bit string corresponding to the number of bits calculated by the calculation means from target data corresponding to an exponent part of the power-residue calculation process;
Execution means for giving the bit string extracted by the extraction means and executing the predetermined partial operation processing;
An arithmetic program characterized by functioning as

(Supplementary Note 2) The extraction means includes:
The arithmetic program according to appendix 1, wherein bit strings corresponding to the number of bits are sequentially extracted from the first bit of the target data.

(Supplementary Note 3) The calculation means includes:
When the predetermined partial calculation process is a partial calculation process related to a binary method, based on the idle time, a processing time required for the multiplication remainder calculation process, and the number of times the multiplication residue calculation process is used in the partial calculation process related to the binary method. And calculating the number of bits in the binary method that can be processed within the free time,
The extraction means includes
Extracting a bit string for the number of bits in the binary method calculated by the calculation means from the target data,
The execution means includes
The arithmetic program according to appendix 1 or 2, wherein a partial arithmetic process related to the binary method is executed by giving a bit string extracted by the extracting means.

(Supplementary Note 4) The calculating means includes:
The calculation program according to appendix 3, wherein the number of bits that can be processed is calculated by the following equation (1).
Kb = Floor ((T / t-1) / 2) (1)
Here, Kb represents the number of bits that can be processed, Floor () represents the floor function, T represents the idle time, and t represents the processing time required for the modular multiplication operation.

(Supplementary Note 5) The calculation means includes:
The number of usable operations, which is the number of times that the modular multiplication operation can be used, is calculated by the following formula (2), and the number of times that the operation has been performed is added according to the value of the target bit. Then, the target bits are sequentially read out until the number of times the calculation is executed becomes the number of times the calculation can be used, and the number of read target bits is calculated as the number of bits that can be processed. program.
a = Floor (T / t-1) (2)
Here, “a” indicates the number of usable operations, “Floor ()” indicates the floor function, “T” indicates the idle time, and “t” indicates the processing time required for the modular multiplication operation processing.

(Appendix 6)
When the predetermined partial calculation process is a partial calculation process related to the window method, a table for storing a power residue value for each bit pattern that can be taken by a bit string having a window width is generated for the target data to be subjected to the power residue calculation process. Generating means,
From the table generated by the generating means, based on the bit pattern, to function as an acquiring means for acquiring a value that is a power residue of the target data,
The calculating means includes
Based on the free time, the processing time required for the multiplication residue calculation processing, the number of times of use of the multiplication residue calculation processing in the partial calculation processing related to the window method, the generation time of the table generated by the generation means, and the window width , And calculate the number of bits in the window method that can be processed within the free time,
The extraction means includes
Extracting a bit string for the number of bits in the window method calculated by the calculation means from the target data,
The execution means includes
The supplementary note 1 or 2, wherein the partial arithmetic processing related to the window method is executed by giving a bit string extracted by the extracting unit and a value obtained by performing a power residue on the target data acquired by the acquiring unit. Arithmetic program.

(Supplementary note 7) The calculation means includes:
The arithmetic program according to appendix 6, wherein the number of bits that can be processed is calculated by the following equation (3).
Kb = Floor ((T / t−2 ^ n) / (n + 1)) * n (3)
Here, Kb represents the number of bits that can be processed, Floor () represents a floor function, T represents a free time, t represents a processing time required for the modular multiplication operation, and n represents a window width.

(Supplementary Note 8) The calculation means includes:
According to the following equation (4), the number of usable operations, which is the number of times the modular multiplication operation process can be used within the idle time, is obtained, and the number of operations performed according to the bit pattern that can be taken by the bit string corresponding to the window width. By adding a certain number of execution times based on the window width, the bit string is sequentially read out until the number of operation executions reaches the number of usable operations, and the number of bits constituting the read bit string is the number of bits that can be processed. The calculation program according to attachment 6, wherein the calculation program is calculated as follows.
a = Floor (T / t-2 ^ n) (4)
Here, “a” represents the number of usable operations, “Floor ()” represents the floor function, “T” represents the idle time, “t” represents the processing time required for the modular multiplication operation, and “n” represents the window width.

(Supplementary note 9) The calculation means includes:
Calculating the number of bits for each window width;
The extraction means includes
Of the number of bits for each window width calculated by the calculation means, extract the longest number of bits,
The execution means includes
9. The arithmetic program according to any one of appendices 6 to 8, wherein the partial arithmetic processing related to the window method is executed based on the longest number of bits extracted by the extracting means.

(Supplementary note 10)
For each window width, function as setting means for setting the generation time of the table based on the processing time required for the modular multiplication operation,
The calculating means includes
For each window width, calculate the number of bits based on the generation time set by the setting means,
The extraction means includes
Extract a bit string corresponding to the longest number of bits among the number of bits calculated for each window width,
The generating means includes
Based on the window width in which the number of bits is the longest, a table for storing a value that is a power residue for each bit pattern that can be taken by the bit string of the window width is generated.
The acquisition means includes
From the table generated based on the window width where the number of bits is the longest by the generating means, based on the bit pattern of the bit string of the window width, obtain a value that is a power residue of the target data,
The execution means includes
The calculation according to appendix 9, wherein a partial calculation process related to the window method is performed by giving a bit string extracted by the extraction unit and a value obtained by performing a power residue on the target data acquired by the acquisition unit program.

(Additional remark 11) The computer provided with a detection means, a calculation means, an extraction means, and an execution means,
A detection step of detecting an idle time until a response returned by the computer at regular intervals by the detection means;
Based on the free time detected by the detection step and the processing time required for the multiplication remainder calculation process constituting the power residue calculation process by the calculation means and the number of times the multiplication residue calculation process is used in a predetermined partial calculation process, A calculation step of calculating the number of bits that can be processed within the idle time;
An extraction step of extracting a bit string corresponding to the number of bits calculated by the calculation step from target data corresponding to an exponent part of the power-residue calculation process by the extraction unit;
An execution step of executing the predetermined partial operation processing by giving the bit string extracted by the extraction step by the execution means;
A calculation method characterized by executing

(Supplementary Note 12) Detection means for detecting idle time until a response to be returned at regular intervals;
Based on the free time detected by the detecting means, the processing time required for the multiplication remainder calculation processing constituting the power residue calculation processing, and the number of times of use of the multiplication remainder calculation processing in a predetermined partial calculation processing, A calculation means for calculating the number of bits that can be processed;
Extraction means for extracting a bit string corresponding to the number of bits calculated by the calculation means from target data corresponding to an exponent part of the power-residue calculation process;
Execution means for giving the bit string extracted by the extraction means and executing the predetermined partial operation processing;
An arithmetic device comprising:

DESCRIPTION OF SYMBOLS 100 Arithmetic apparatus 201 Control part 202 Process control part 203 Reception part 204 Operation part 205 Timer 206 Free time calculation part 207 Reference required time storage table 208 Processing time acquisition part 209 Detection part 210 Calculation part 211 Extraction part 212 Execution part 213 Setting part 214 Table generation unit 215 Table acquisition unit

Claims (8)

Computer
Detecting means for detecting idle time until a response returned by the computer at regular intervals;
Based on the free time detected by the detecting means, the processing time required for the multiplication remainder calculation processing constituting the power residue calculation processing, and the number of times of use of the multiplication remainder calculation processing in a predetermined partial calculation processing, A calculation means for calculating the number of bits that can be processed;
Extraction means for extracting a bit string corresponding to the number of bits calculated by the calculation means from target data corresponding to an exponent part of the power-residue calculation process;
Execution means for giving the bit string extracted by the extraction means and executing the predetermined partial operation processing;
An arithmetic program characterized by functioning as The extraction means includes
The arithmetic program according to claim 1, wherein a bit string corresponding to the number of bits is sequentially extracted from the first bit of the target data. The calculating means includes
When the predetermined partial calculation process is a partial calculation process related to a binary method, based on the idle time, a processing time required for the multiplication remainder calculation process, and the number of times the multiplication residue calculation process is used in the partial calculation process related to the binary method. And calculating the number of bits in the binary method that can be processed within the free time,
The extraction means includes
Extracting a bit string for the number of bits in the binary method calculated by the calculation means from the target data,
The execution means includes
The arithmetic program according to claim 1, wherein the partial arithmetic processing related to the binary method is executed by giving the bit string extracted by the extraction unit. The computer,
When the predetermined partial calculation process is a partial calculation process related to the window method, a table for storing a power residue value for each bit pattern that can be taken by a bit string having a window width is generated for the target data to be subjected to the power residue calculation process. Generating means,
From the table generated by the generating means, based on the bit pattern, to function as an acquiring means for acquiring a value that is a power residue of the target data,
The calculating means includes
Based on the free time, the processing time required for the multiplication residue calculation processing, the number of times of use of the multiplication residue calculation processing in the partial calculation processing related to the window method, the generation time of the table generated by the generation means, and the window width , And calculate the number of bits in the window method that can be processed within the free time,
The extraction means includes
Extracting a bit string for the number of bits in the window method calculated by the calculation means from the target data,
The execution means includes
3. The partial arithmetic processing related to the window method is executed by giving a bit string extracted by the extracting unit and a value obtained by performing a power residue on the target data acquired by the acquiring unit. The calculation program described. The calculating means includes
Calculating the number of bits for each window width;
The extraction means includes
Of the number of bits for each window width calculated by the calculation means, extract the longest number of bits,
The execution means includes
5. The arithmetic program according to claim 4, wherein the partial arithmetic processing related to the window method is executed based on the longest number of bits extracted by the extracting means. The computer,
For each window width, function as setting means for setting the generation time of the table based on the processing time required for the modular multiplication operation,
The calculating means includes
For each window width, calculate the number of bits based on the generation time set by the setting means,
The extraction means includes
Extract a bit string corresponding to the longest number of bits among the number of bits calculated for each window width,
The generating means includes
Based on the window width in which the number of bits is the longest, a table for storing a value that is a power residue for each bit pattern that can be taken by the bit string of the window width is generated.
The acquisition means includes
From the table generated based on the window width where the number of bits is the longest by the generating means, based on the bit pattern of the bit string of the window width, obtain a value that is a power residue of the target data,
The execution means includes
6. The partial arithmetic processing related to the window method is executed by giving a bit string extracted by the extracting unit and a value obtained by performing a power residue on the target data acquired by the acquiring unit. Arithmetic program. A computer comprising detection means, calculation means, extraction means, and execution means,
A detection step of detecting an idle time until a response returned by the computer at regular intervals by the detection means;
Based on the free time detected by the detection step and the processing time required for the multiplication remainder calculation process constituting the power residue calculation process by the calculation means and the number of times the multiplication residue calculation process is used in a predetermined partial calculation process, A calculation step of calculating the number of bits that can be processed within the idle time;
An extraction step of extracting a bit string corresponding to the number of bits calculated by the calculation step from target data corresponding to an exponent part of the power-residue calculation process by the extraction unit;
An execution step of executing the predetermined partial operation processing by giving the bit string extracted by the extraction step by the execution means;
A calculation method characterized by executing Detection means for detecting idle time until a response to be returned at regular intervals;
Based on the free time detected by the detecting means, the processing time required for the multiplication remainder calculation processing constituting the power residue calculation processing, and the number of times of use of the multiplication remainder calculation processing in a predetermined partial calculation processing, A calculation means for calculating the number of bits that can be processed;
Extraction means for extracting a bit string corresponding to the number of bits calculated by the calculation means from target data corresponding to an exponent part of the power-residue calculation process;
Execution means for giving the bit string extracted by the extraction means and executing the predetermined partial operation processing;
An arithmetic device comprising:

Images