A compact microelectronic device for performing modular multiplication and exponentiation over large numbers

[Industrial Application] The present invention relates to a method for performing modular processing on a large number in the Galois region composed of a plurality of types of prime numbers and composite prime number modules. More specifically, the present invention is a modulation for large numbers.<u style="single">La</u> Multiplication<u style="single">Arithmetic</u>And mod<u style="single">La</u>-It refers to ultra-small electronic devices for performing exponentiation and methods for performing them. Mods like this<u style="single">La</u> Multiplication and modulation<u style="single">La</u>Exponentiation is suitable for performing public key cryptographic authentication and operations essential to encryption protocols (Protocols). This type of operation cannot be performed within normal processing time by a small microprocessor.

[0002] Conventional Techniques and Problems to be Solved by the Invention The present invention performs a procedure known as "a method of multiplying Montgomery with multiple precision by an interleaving method" by hardware. Related to doing. This Montgomeri multiplication method is often used in software-oriented systems of cryptography. Here, the only original way is provided to promote modular exponentiation. In addition, it is an essential proof to simplify the architecture for performing this modular exponentiation and to expand the scope of devices that perform modular exponentiation within a number of commonly used areas. Is used.

[0003] The basic processing relating to the above procedure is performed by any one of three known methods, such as those related to techniques for performing modular multiplication based on Montgomeri's methodology. The first of these known methods is PL Montgomery's "Modular Multiplication without trial division" {Mathematics of Computation, Vol. 44, 519-521. Page, published in 1985}. From this point onward, the first method described above will be simply referred to as Montgomeri's method. The second known method is "A Cryptographic Library for the Motorola DSP 56000" by SR Dusse and BS Kaliski Jr. {90. Minutes of European Cryptography of the 1980s (Proc. Eurocrypt '90), published by Springer-Verlag in Berlin in 1990}. From this point onward, the above second method will be simply referred to as the Dusse method.

[0004] When the above procedure is performed by hardware, a security mechanism, on-the-fly addition, subtraction, and digit movement are added. In addition, processing that causes inappropriate overall output is eliminated. Furthermore, based on the design using silicon, means that can be carried out relatively easily will be developed and integrated. The device realized by this integration is actually added to the internal data / address bus as a slave device of an 8-bit, 16-bit or 32-bit central processing unit (CPU).

[0005] The multiplication / squared device according to the present invention can operate at clock speeds many times higher than those achieved so far due to its simple synchronous, single-digit feed design. It is possible. This clock speed is achieved by a CPU mounted on the board and supporting a non-volatile storage device (memory). The method using the multiplication / square device does not require a design change in the CPU memory architecture. This type of architecture is defined for performing high-speed modular multiplication over large numbers by using parallel multipliers and dual-port memory, such as Philip circuits. The third of several methods for performing this modular multiplication is the Philip electronic component "83C852 (8-bit microcontroller with confidentiality for conditional access applications)" {1990 8 8 It is a method implemented by} announced at Einhoven in May. From this point onward, the above third method will be simply referred to as Philip's method.

[0006] The basic architecture as described above is applied to a device that can be integrated in the design of an arbitrary microcontroller and can be mapped to a memory. In addition, this type of equipment must also be able to operate in parallel with a microcontroller that needs to constantly load commands and operands and retrieve and transfer the final response result.

A novel solution to such a requirement is to use only two series / parallel multipliers and to adopt a fully serial pipeline approach. By adopting such a pipeline approach, it is possible to reduce the area of silicon. According to a well-known technique commonly used at present, a device having a microcontroller with a memory and completely satisfying the above solution is integrated on an electronic circuit having a size of 4 × 4.5 × 0.2. It is possible to do. The electronic circuit obtained in this way satisfies the ISO7816 standard. Here, ISO is an abbreviation for International Organization for Standardization, and is specified in an authentication card, that is, an integrated circuit card (IC card). ISO7816 in the above ISO is composed of the following three parts.

[0008] 1 Part 1 ... ISO7816-1 (physical characteristics), established in 1987 2 Part 2 ... ISO7816-2 (dimensions of contact position), established in 1988 3 Part 1 Part 3 ... ISO / IEC7816-3 (electronic signal and communication protocol), established in 1989. From now on, these three parts will be collectively referred to as ISO7816.

[0009] The present invention is directed to realizing the architecture of the novel solutions described above based on the mathematical innovations disclosed by Montgomeri. In the present invention, as will be described later, the time required to perform the modular exponentiation is reduced to a value that is almost the same as half the processing time required when using the known processing method and Montgomeri's method. For this purpose, some modifications, improvements and functional methods are provided.

[0010] Here, before describing the apparatus and method for performing the modular multiplication and the modular power of the present invention, a general calculation mathematics will be roughly described.<u style="single">Mathematical definitions, general rules and processing methods</u>In the area of numbers consisting of prime numbers and complex basic modules, we define A and B as multiplicands and multipliers, respectively. In addition, N is usually defined as a number greater than A or B. However, in some cases, N can be a smaller number than A. In addition, each of A, B, and N is defined as an operand of m × k (the product symbol may be represented by · or * instead of ×) = n bit length. Each k-bit group is called a character. Therefore, each of A, B and N consists of an operand of m character length. Here, in order to facilitate an understanding of the initial process of performing modular multiplication and modular power, and to explain the procedure for performing modular multiplication and modular power step by step, we have A, B and Each of N is defined as an operand of 512 bit length (n = 512). In addition, set k to 32 bits long. This 32-bit can now be considered a length of k commensurate with the cost of the multiplier. Furthermore, set the value of m with m = 16. The value 16 of m is the number of characters in one operand and the number of repetitions of the square loop or multiplication loop for the 512-bit operand. In this case, obviously both operands are integers.

[0011] Furthermore, we use the symbol "" to represent the congruence of the number of modules. For example, if 162mod7 is described, it means that 16 is congruent with 2 modulo 7, and the remainder when 16 is divided by 7 is 2. Also, if YmodNXmodN is stated, both X and Y may be greater than N. Moreover, when X and Y are positive, their remainders will be the same value. Furthermore, it should be noted that if Y is a negative integer, the congruence of Y is represented by Y + uN. In this case, if the congruence of Y is less than N, u will be set as the minimum number to make the congruence of Y a positive value.

[0012] Furthermore, we use the symbol "\" to represent congruence in a more limited sense. In the processing process described here, the various values are often the desired values or the sum of the desired values and the module. For example, if X \ 2mod7 is stated, X is equal to either 2 or 9. At this time, X is defined as having a limited congruence to 2mod7.

[0013] Further, when X = AmodN, we define X as the remainder when A is divided by N. For example, it is expressed as 3 = 45 mod6. Modular / reciprocal is the basic concept in the theory of numbers. For example, the modular reciprocal of X is X^-1It is expressed as. In this case, the modular reciprocal X^-1Is XX^-1It is defined by the relational expression of modN = 1. If the value of X is equal to 3 (X = 3) and the value of N is equal to 13 (N = 13), then X^-1The value of is 9 (X^-1= 9). That is, the value obtained by dividing the product 3 and 9 by 13 is 1.

[0014] In this case, the acronyms MS and LS may be used to display the most significant or least significant value for the bits, characters, and all operands to be referenced, respectively. As used herein, N means both the value N and the name of the shift register that contains this value N. A and N are constant values throughout the exponentiation process. Further, A is the value of the number of powers to be processed. In the first iterative operation of the exponentiation process, B is equal to A. A is also the name of the register where the accumulated values reside. In this case, the accumulated values are ultimately equal to the desired result of the exponentiation process. S indicates a temporary value and a register in which a value having a limited congruence (\) relationship with respect to the value S is stored. S (i-1) means the value of S at the beginning of the i-th repetitive operation. S₀Indicates the lowest (LS) character of the value of S (i).

[0015] Here, we have a ρ region (this ρ should be displayed as a vector, but in the form of an electronic application, ρ cannot be displayed as a vector, so it is unavoidable to use ordinary Greek letters. The processing process of multiplication ρ (A · B) N in (to be displayed) will be briefly described. The detailed definition of multiplication ρ (A B) N will be given later.

[0016] Symbols other than ρ (A · B) N are usually used in arithmetic calculations.<u style="single">Montgomery modular multiplication</u>In the classical approach for performing modular multiplication A / B modN, the remainder of the products A / B is calculated by using division processing. However, performing such a division operation is more difficult than performing a multiplication operation.

By using Montgomeri's modular reduction method, the above division process is substantially replaced by a multiplication process using precomputed constants. Montgomeri's function ρ (A · B) N performs the multiplication modulo N of the products A · B within the ρ domain. The search process from the ρ region to the region of the normal module is performed by defining ρ based on the result of ρ (A · B) N and the pre-calculated constant H. Here, if P is congruent with ρ (A · B) N (Pρ (A · B) N), then ρ (A · B) N is equal to A · B mod N (ρ (A · B)). N = A BmodN). Therefore, normal modular multiplication is performed by the two multiplication processes in the ρ region.

The intent of using an effective modular reduction method is to avoid a series of multiplication and division operations on n-bit and 2n-bit length operands. Avoiding such multiplication and division operations involves performing a series of multiplications, additions, and subtractions on operands whose original value is n bits long and whose maximum value is n bits long to produce the final result. It is realized by. To prove Montgomeri's guidelines as described above, we have given A, B, and an odd N (this odd module is always either a simple large prime or a complex large prime. It should be noted that the following Q finally exists for (yes). That is, there is a Q that satisfies the condition that A, B + Q, and N are numbers such that the value of the lowest n bits becomes 0. More specifically, such a condition is shown in the following equation (1).

[0019] [Number 1]<img file="JP3636740B2_D0001.tif" />[0020] This equation (1) means that it is possible to express a 2n-bit length such that the value of the least significant n-bit becomes 0. Here, I 2ⁿIs congruent with ImodN (I 2)ⁿ ImodN) is assumed. In this case, I exists for all odd N's. By multiplying both sides of the above equation (1) by I, a congruent relationship as shown in the following equation (2) is derived on the left side of the equation (1).

[0021] [Number 2]<img file="JP3636740B2_D0002.tif" />On the other hand, on the left side of Eq. (1), a congruent relationship as shown in Eq. (3) below is derived.

[0023] [Number 3]<img file="JP3636740B2_D0003.tif" />[0024] As a result, the following equation (4) is derived from the above equations (2) and (3).

[0025] [Number 4]<img file="JP3636740B2_D0004.tif" />[0026] Unfortunately, from this equation (4), it can be seen that the parasitic factor (parasitic function) I is introduced every time the multiplication of the ρ region is executed. Here, the ρ operator is defined as in the following equation (5).

[0027] [Number 5]<img file="JP3636740B2_D0005.tif" />[0028] Further, P in Eq. (5) is called multiplication of A and B in the ρ region. The search process from the ρ region is performed by calculating ρ for P and H as shown in the following equation (6).

[0029] [Number 6]<img file="JP3636740B2_D0006.tif" />[0030] The value of H is derived by replacing P in the congruent relationship as in Eq. (6) with P in Eq. (4). This process is shown in the following equation (7).

[0031] [Number 7]<img file="JP3636740B2_D0007.tif" />Here, H is I²If it is congruent with the reciprocal of, then Eq. (7) is valid and Eq. (8) below holds.

[0033] [Number 8]<img file="JP3636740B2_D0008.tif" />[0034] In order to specify the ρ operator for A and B, the following processes from step 1) to step 5) are performed using the previously calculated constant J. In this case, finally, in step 5), the following equation (9) is established.

[0035] [Number 9]<img file="JP3636740B2_D0009.tif" />[0036] Following these processes, the following equation (10) is derived.

[0037] [Number 10]<img file="JP3636740B2_D0010.tif" />[0038] Further, the following equation (11) is derived.

[0039] [Number 11]<img file="JP3636740B2_D0011.tif" />[0040] Where Z is 2ⁿIn order to be divisible by (the least significant n bits of Z must be 0), the congruence shown in Eq. (12) below must exist.

[0041] [Number 12]<img file="JP3636740B2_D0012.tif" />[0042] Furthermore, in order for a congruence such as this equation (12) to exist, N · Jmod2ⁿMust be congruent with -1. That is, the following equation (13) must hold.

[0043] [Number 13]<img file="JP3636740B2_D0013.tif" />[0044] The constant J can be obtained by this equation (13). Here, since J is a function of N only, it is a pre-computed constant. Moreover, as is clear, we must choose a positive value J that is less than N. As will be apparent to those skilled in the art from the above description, in the above processing process, three multiplication processes, one addition process, and one addition process are performed on the predetermined A, B, N, and the pre-calculated constants. By performing the best subtraction process, ρ (A · B) N is obtained. Furthermore, A and BmodN can be obtained by using the result obtained in this way, a similar processing process, and a previously calculated constant H (a function of module N). In this case, A is equal to B, so it is possible to use such an operator for devices for squaring or multiplying by modular arithmetic.

【0045】<u style="single">Montgomeri's modular multiplication by interleaving method</u>In the previous section, we have described a method of modular multiplication that requires multiplication for multiple operands, all n-bit length, and multiple calculation results that require 2n + 1-bit storage. It was. Here, in addition, by utilizing Montgomeri's interleaving reduction method (described in the previously described Dusse paper), multiplication operations using shorter operands, registers, and hardware multipliers can be performed. Can be executed. As a result, processing by an electronic device having a relatively small number of logic gates becomes possible.

[0046] Further, by using a k-bit multiplier, it is possible to easily define a character having a k-bit length. In this case, there are m characters in n bits (m · k = n). J as the last character of J_OBy defining, the following equation (14) is derived.

[0047] [Number 14]<img file="JP3636740B2_D0014.tif" />[0048] Here, by carrying out the following steps 1) to 5) using the reduction method by the above-mentioned Montgomeri's interleaving method, after m repeated operations under the following initial conditions, ρ (A / B) N is specified. The circuit of the present invention executes these plurality of steps in a parallel manner. Initial condition: S (0) = 0 (value having a limited congruence relationship with S at the beginning of the first (first) repetitive operation) [0049] [Equation 15]<img file="JP3636740B2_D0015.tif" />[0050] Here, the division process in step 5) corresponds to a k-bit digit shift (shift operation) to the right when the lowest k-bit in Z is always 0. Alternatively, the least significant k-bit in Z is simply ignored, as seen in division processing circuits. As mentioned above, equation (15) is obtained after the last iterative operation. Alternatively, if necessary, Eq. (15) is obtained after subtracting N. To derive F = A · BmodN, we have to perform the calculation of ρ (C · H) N in the ρ region.

Here we prove that for all S (i), the value of S (i) is less than 2N (not included in Montgomeri's proof). It should be noted that three inequalities such as the following equation (16) hold for the operands used in the processing process here.

[0052] [Number 16]<img file="JP3636740B2_D0016.tif" />(The first two in these inequalities are from these S (i-1) and B at the beginning of the iterative operation if S (i-1) and B are equal to or greater than N. It holds when N is subtracted. In addition, 2^kIs a k + 1 bit length number such that the most significant (MS) bit is 1, and A_i-1The third inequality holds when is an operand of k-bit length. ) By definition, the above equation (17) holds.

[0054] [Number 17]<img file="JP3636740B2_D0017.tif" />[0055] By substituting in the above-mentioned set of equations, the following equation (18) is established.

[0056] [Number 18]<img file="JP3636740B2_D0018.tif" />[0057] Here, by incorporating the highest value of each element in the equation (18), the inequality with respect to Z as in the following equation (19) is established.

[0058] [Number 19]<img file="JP3636740B2_D0019.tif" />From this inequality, the following equation (20) is surely established.

[0060] [Number 20]<img file="JP3636740B2_D0020.tif" />[0061] Here, both sides of the inequality of equation (20) are set to 2^KEq. (21) is obtained by dividing by.

[0062] [Number 21]<img file="JP3636740B2_D0021.tif" />[0063] From the inequality in Eq. (21), it was proved that in any case, N needs to be subtracted only once in order to adjust S (i) or B.<u style="single">Example 1</u><u style="single">Modular multiplication by interleaving method</u>By using a manual computer in hexadecimal mode, the effectiveness of calculation using modular multiplication by the interleaving method is easily proved. First, set the numbers using the hexadecimal format as follows:

[0064] N = a59 (modulo), A = 99b (multiplier), B = 5c3 (multiplicand), n = 12 (bit length of N), k = 4 (bit size of multiplier, character size) (Also), and m = 3 (n = k m), and J₀= 7 (7.9-1mod16) and H2^2x12moda5944b is set.

[0065] The result required here is FA BmodN99b 5c3moda59375811moda59 = 220₁₆Is. The processing process of calculation using modular multiplication by the interleaving method is shown below. Initial condition: S (0) = 0 [0066] [Number 22]<img file="JP3636740B2_D0022.tif" />[0067] [Number 23]<img file="JP3636740B2_D0023.tif" />[0068] The finally obtained value is 99b · 5c3moda59, which is consistent with the above-mentioned required result. The validity of the above multiplication operation is basically 2 for the upper n bits when ignoring the lowest 0 k bits in each step.^kIt can be intuitively understood when we realize that it will be multiplied. In addition, in each step, the i-th part of the multiplier is 2^ikIs a number that is multiplied by. By such multiplication processing, the above part has the same rank as S (i).

【0069】<u style="single">Modular / reduction method within one multiplication process in Montgomer's equipment</u>For example, in many cryptographic processes such as NIST's standardization of digital symbols and modular / exponentiation using the Chinese Remainder Theorem, numbers larger (usually more than double) than the second modulo. Is required to reduce. These modular / reduction methods can be effectively performed in a single modular multiplication process with an interleaving method. This modular multiplication process utilizes the equipment of the present invention and functional extensions to Montgomeri's algorithm.

[0070] In some of the above examples, it is implied that the n bits of an operand, such as the modulo length, are also the exact length of N. Such relationships are very effective for normal exponentiation and multiplication. However, if the magnitude of the number needs to be reduced, a second constant I^-1=2ⁿIt is effective to use modN. This second constant reduces the scale of one multiplication process to the minimum level when it is required to reduce the Montgomeri number multiplied by a given number. The above constant I^-1Is calculated by the same mechanism as when calculating the constant H (see the section on calculating the H parameter). More specifically, this I^-1The calculation of is performed by placing module N in the most significant part of the operand of the divisor so that the most significant bit of the divisor register has a bit value of 1. Here, the number of digit moves / trial subtractions must clearly be n ÷ IL. Where L is the number of bits N is involved in. In this case, I^-1Note that is an L-bit length operand.

To prove the above preconditions, first of all, we have a congruent relationship with A, B, Imod N by Montgomeri's multiplication of A, B modN (ρ (A, B) N). It is stated repeatedly that is generated. B is I^-1Is equal to (B = I)^-1), The following equation (24) holds.

[0072] [Number 24]<img file="JP3636740B2_D0024.tif" /> 【0073】<u style="single">Example 2</u><u style="single">Montgomeri's reduction method by interleaving method</u>To prove that t can be reduced to modulo q (t mod q), set the length of the multiplier register to be greater than the length of q. Here, t stored first has a length of 24 bits.

[0074] Further, it is assumed that the word length (magnitude of the device multiplier) is 8 bits and the following variables are assumed. n = 24, k = 8, t = 0af59b, q = 2b13, and R = I^-1=2²⁴modq = 141d By comparing using a simple division calculation process, we can see that tmodq is equal to 5c8 (tmodq = 5c8). Such a processing process is shown below.

[0075] In this case, it should be noted that the reduction and retrieval are performed in one Montgomeri multiplication process.

[0076] [Number 25]<img file="JP3636740B2_D0025.tif" />Finally, as mentioned above, it is confirmed that tmodq is equal to 5c8.<u style="single">Exponentiation</u>Here, "The Art of Computer Programming" by D. Nuth {Seminumerical Algorithms, Volume 2, Addison-Wesley, Reading Based on the method of processing procedure by the Association (Reading Mass), published in 1981}, the processing procedure of square and multiplication for performing modular power is explained. From this point onward, the above method will be referred to as the Nous method.

[0078] First, we assume that we have pre-computed the constants in the previous section. We also assume that the devices of the present invention can perform both square and multiplication within the ρ region. At this time, we will perform the calculation as shown in equation (26) below.

[0079] [Number 26]<img file="JP3636740B2_D0026.tif" />[0080] The calculation processing process of this equation (26) is shown below. Here, E (i) indicates the i-th bit when the binary bit is displayed for the exponent E. This i-th bit starts with the most significant bit with an index of 1 and ends with the least significant bit with an index of q.

[0081] [Number 27]<img file="JP3636740B2_D0027.tif" />[0082 ] When moving from one step to the next, whenever B is equal to or greater than N, N is subtracted from B. After the last repetitive action, the value of B is A^EHave a limited congruence relationship with modN (B ¥ A)^EmodN). There are a plurality of patented protocols that can be used more effectively when performing modular powers using the circuits of the present invention. Here, we list two cryptographic protocols in the method described in the present invention that double the speed of normal exponentiation.

The first cryptographic protocol is "A Method for Obtaining Digital Signatures and Public Key Cryptosystems" by RL Rivest et al. {ACM Committee (Comm. Of) the ACM), Vol. 21, pp. 120-126, published in 1978}. From this point onward, the above-mentioned first protocol will be referred to as the RSA method. The second cryptographic protocol is "New Directions in Cryptography" by W. Diffie and ME Hellman {IEEE Trans. On Inform. Theory ), VOL.IT-22, pp. 644-654, published in 1976}. From now on, the above second protocol will be referred to as the Diffi-Hermann method. In these two methods, most difficult powers are performed using constant exponents.

[0084] The method described in the next section (an effective method for searching from the ρ region) refers to reducing the computational time required for computational processing by using a constant exponent. When this method is used, the exponentiation process (multiplication of all ρ (A · B) N) in step b)'is removed. In addition, the final value of B obtained after the qth iterative operation for exponentiation is multiplied by the precomputed constant T in the Montgomeri ρ region.

[0085] For those engaged in the above cryptographic protocols, the calculation time can be calculated by operating the RSA symbols in a circuit using the Chinese Remainder Theorem (described in the Nous literature above). It is clear that the value can be reduced to less than 70%.<u style="single">An effective way to search from the ρ region</u>Here, the protocols for exponentiation and multiplication in the previous section can be improved. Further, by incorporating a newly calculated constant T while the repetitive operation is performed, it is possible to reduce the number of multiplications in the ρ region. In this case, T is a function of modulo N and exponent E. Such a method is shown in the following processing process.

[0086] [Number 28]<img file="JP3636740B2_D0028.tif" />[0087] In this case, the modular exponentiation is carried out according to the following procedure.

[0088] [Number 29]<img file="JP3636740B2_D0029.tif" />[0089] Here, it is assumed again that N is subtracted from B whenever B is equal to or greater than N when moving from one step to the next. Furthermore, it should be noted again that all multiplications within the ρ domain correspond to modular multiplication by the same factor I (eg, ρ (X · Y) = X · Y · ImodN).

【0090】<u style="single">Example 3</u>This example 3 is A^EThis is to prove the usefulness of T in the calculation of modN and to clarify the definition of T. The processing process of Example 3 is shown below.

[0091] [Number 30]<img file="JP3636740B2_D0030.tif" />[0092] Further, the following processing process is performed.

[0093] [Number 31]<img file="JP3636740B2_D0031.tif" />[0094] A^E If the following steps are performed in succession to calculate<u style="single">Pa</u>The introduction of Lameter T can be avoided. Here, we assume that there is a pre-computed Montgomeri constant, and that the device of the present invention performs both square and multiplication processes within the P region, the calculation below. To execute.

[0095] C = A^EmodN In this case, E (j) indicates the jth bit when the binary bit is displayed for the exponent E. This j-th bit starts with the most significant bit with an index of 1 and ends with the least significant bit with an index of q. For odd exponents, the power can be performed by the following processing process.

[0096] [Number 32]<img file="JP3636740B2_D0032.tif" />[0097] When moving from one step to the next, whenever B is equal to or greater than N, N is subtracted from B. After the last repetitive action, the value of B is A^ELimited congruence to modN (B ¥ A)^Ewill have modN). Then, C is obtained as the final value.

On the other hand, for even exponents, the last step described above is replaced by equation (33) below.

[0099] [Number 33]<img file="JP3636740B2_D0033.tif" />[0100] Furthermore, in order to clarify the processing process here, the following specific examples will be posted.

[0101] [Number 34]<img file="JP3636740B2_D0034.tif" /> 【0102】<u style="single">Calculation of H parameters</u>The H parameter is indispensable for calculations within the Montgomeri region and is a constant value. With some protocols, H becomes a constant that is pre-computed on a relatively large computer. Alternatively, using other protocols, H can be a useful constant, such as the first-stage parameter used in calculating more valid constants. See the section above in this regard.

[0103] In normal communication, it is assumed that H is calculated in advance. However, for some protocols, such as symbol encryption during random communication in RSA, it is also necessary to calculate H using the device of the invention, such as the SMART card. The H parameter is calculated by the following equation (35).

[0104] [Number 35]<img file="JP3636740B2_D0035.tif" />This equation (35) means that the H parameter is the remainder of the normal division operation. In this case, the bit string consisting of the most significant bit and the following 2n bits (operand with a length of 2n + 1 bits) with the lowest bit value 0 is divided by the radix N of the module. .. Performing a binary division by divisor N on a divisor consisting of one bit with a bit value of 1 and a bit string with a bit value of 0 is equivalent to performing sequential trial subtraction with N. That is, the above division process is equivalent to subtracting N from the remainder of the remaining trial process when the most significant n + 1 bit is greater than N (see example below).

[0106] In this case, the original dividend is 2n + 1 bit long, but the division in the remaining trial process generated by the division process clearly does not exceed n + 1 bit length. Furthermore, it is clear that the lowest digit is 0. For example, the following example is given. That is, N = 11₁₀=1011_n(Therefore, the bit length of N is 4, so n = 4), we give an example of finding H.

[0107] A long division is manually executed, with the radix of division being 2.

[0108] [Number 36]<img file="JP3636740B2_D0036.tif" />Finally, H = 3₁₀It was confirmed that. In the above division process, there are n + 1 trial subtractions. Furthermore, it should be noted that the division obtained by trial subtraction is also n + 1 bit long. The procedure of such subtraction processing will be described in detail in the description of the hardware of the present invention described later.

[Means and Actions for Solving Problems] The present invention relates to microprocessors and microprocessors for performing modular multiplication and modular powers on large numbers. It consists of compact, synchronous electronic ultra-compact peripherals for standard microprocessors with means.

[0111] Further, the ultra-small electronic device of the present invention is multiplexed and multiplexed with a plurality of types of shift registers, each of which is subdivided and can be switched and controlled, and is controlled by the clock means. It has only two multiplexers in series / parallel, a borrow detector, an auxiliary subtractor and adder, a delay register and a switching element.

[0112] Such an ultra-small electronic device is formed by integrating all the above-mentioned components in order to perform modular multiplication, modular square and modular power in a simultaneous processing and synchronous manner. Preferably, the microelectronic device of the present invention is a novel, complex and synchronous hardware device developed based on Montgomeri's method designed for hardware multiplication, square and exponentiation. Is realized by.

[0113] Further, preferably, the ultra-small electronic device of the present invention is a composite form of a large number of simultaneous processes and serial processes in which a series operation method is incorporated into a parallel operation method by developing the method of Montgomeri, that is, , Multiply, subtract, add, memorized delay and 2^kFunctions as a device for performing division by. Further, preferably, the ultra-small electronic device of the present invention performs a large number of serial processes for modular multiplication, modular square and modular power by developing Montgomeri's method, and is enormous. It is possible to avoid the use of an internal bus.

[0114] Further, preferably, the microelectronic device of the present invention performs a number of serial processes for modular multiplication, modular square and modular power by developing Montgomeri's method. It is compact enough to be formed on a microchip defined by the ISO7816 standard for SMART cards using general 1 μm technology.

[0115] Further, preferably, the microprocessor of the present invention performs a number of serial processes for modular multiplication, modular square and modular power by developing Montgomery's method. Controlled by any microprocessor with one internal bus, without changing the basic architecture, especially without redesigning the memory for dual-port access and with low firmware requirements. Is possible.

[0116] Further, preferably, the microelectronic device of the present invention uses a microprocessor to specify a procedure for processing squares and multiplications within a cascaded ρ region. Further, the ultra-small electronic device includes a shift register having an n-bit length, and includes a multiplexing unit that performs modular multiplication, modular square, and modular power. Since it is not necessary to store the exponent E in this multiplexing section, it is easy to control by this multiplexing section, and on the other hand, only a small amount of additional microcontroller ROM code is required.

[0117] Further, preferably, the ultra-small electronic device of the present invention uses a squared multiplicand by an on-the-fly method while the register of B is rotating._iAs a result of loading the register of A_iWhen the register of B is reloaded by the register of B, the possibility that the final value of the previous calculation process of B and / or BN is fetched by the microcontroller is avoided.

[0118] This saves RAM for this microcontroller and makes it possible to eliminate at least n clocks of effective clock cycles in each of the squared repetitive operations. According to the configuration of the present invention, Z / 2^kFrom a simple device by Montgomeri's method, two by determining whether is greater than or equal to N and achieving a relatively small N operand such that only one series subtraction is performed. Z / 2 with storage registers and independent series subtraction processing removed^kAllows single series detection for -N.

Further, according to the configuration of the present invention, the circuits are synchronized in a semi-parallel manner so that only two series / parallel multipliers are used when performing three simultaneous multiplication processes. There is. For this reason, the ratio of the area occupied by the series / parallel multiplier to the total silicon region in the silicon-based device can be suppressed to 40%.

Further, according to the configuration of the present invention, a series of X additions and a series of multipliers are used using one digital delay element consisting of a k-bit shift register.<u style="single">Form multiplication</u>Synchronize with the results<u style="single">Ru</u>This prevents double storage of serial / parallel multiplier product or iterative processing. Further, in a preferred embodiment of the invention, the shift register is composed of n-bit or n / 2-bit length, and a power of n / 2 length for the module is required for the power of n-bit length. It is performed in somewhat less than one-eighth of the effective clock cycle period that is expected to be achieved.

[0121] Further, in a preferred embodiment of the present invention, the register A is loaded by the on-the-fly method, the size of the register contents of the S is predicted by the on-the-fly method, and some operands are further operated by the on-the-fly method. By synchronizing, the multiplication process ρ (A · B) N of the number of n bits is completely performed in an effective m (n + 2k) clock cycle.

[0122] Further, in a preferred embodiment of the present invention, it is used for Montgomeri's multiplication process in which a small-scale borrow detection circuit is added and a simple addition is added to the control mechanism. The H parameter can be calculated in the second mode using the same register of the same equipment as. In the method for performing modulo multiplication of the present invention, each of the multiplicand A, the multiplier B, and the modular N is composed of m characters of k-bit length, and the multiplier B is set to a value not larger than the modulo N. To.

[0123] The method is performed by the following steps. In the first step, the H parameter and at least the lowest character J of the other parameters₀And this character J₀Is loaded into a k-bit register, and in the second step, the multiplier B and the modulus N are loaded into the corresponding n-bit length registers, where n = m · k, expressed as n = m · k. In step 3, all the bit values of the n-bit length register S are set to 0, and in the fourth step, the i-th iterative operation is performed m times, where i is a number from 0 to m-1. In addition, each of the i-th repetitive actions includes the following actions: (a) The i-th character A of the multiplicand A._i, A_iTransfer from the register means of, to the storage means selected from the register and latch means, and generate the value of X represented by (b) X = S (i-1) + A (i-1) * B. Here, S (i-1) is the updated value of S, and the update of S is defined as follows: 1 The register of B is periodically shifted to the right with respect to the multiplication means. Then, 2 B to A in series format_iMultiply by 3 Modulo N is periodically shifted to the right, and if 4 S (i-1) is not greater than N, then S after the (i-1) th repetitive operation The value stored in the register is determined as the updated value of S (i-1), and if S (i-1) is greater than N, by subtracting N from S (i-1) in series form. The obtained value is determined as the updated value of S (i-1), and the updated value of S (i-1) obtained as a result is set, and the register of 5 S is periodically set. Shifts to the right, and for each bit, adds multiplication A (i-1) * B to the updated value of S (i-1), and (c) X (X)₀) The lowest character is J₀Multiply by, and while N and X are delayed by k clock cycles, X₀* J₀mod2^kValue of Y₀Put it in the register means of (d) Z = X + Y₀The value of Z of * N is calculated, and this calculation is performed as follows, Y with the register of 1 N delayed and shifted to the right.₀Is multiplied by N, and at the same time, the above-mentioned periodic shift to the right is made for this multiplication result, and 2 X is changed to Y.₀Add to the value of * N, (e) ignore the lowest character of Z, put the remaining characters in the register of S, at this time Z / 2 except for the last repetitive operation^k(F) Z / 2 for each bit in order to determine the updated value of S (i-1) by the same method as described above.^kAnd N are compared, and (g) the i-th character A of the multiplicand A._iIs loaded into the register means of A in the above operation period, and in the fifth step, in the last (mth) repetitive operation, Z / 2^kIgnore the lowest character of, put the remaining characters in the register of B as C \ ρ (A * B) N, and in the 6th step, repeat the 3rd and 4th steps, where If C is greater than N, then C or CN replaces B, and H replaces A to calculate P = ρ (C * H) N, and in the seventh step, the final iteration. The value of P obtained by is assumed to be A * B modN.

[0124] Further, according to the method of the present invention, modular square and modular multiplication are performed when the multiplicand A and the multiplier B are the same number. Further, according to the method of the present invention, D = A^E Modular multiplication and modular exponentiation represented by modN are performed. Further, the method of the present invention is 1. Mod.<u style="single">B</u>Is stored in register N, 2. Register S is set to 0<u style="single">Configuration</u>3. The process of storing the base A to be powered in the register B, 4. The process of storing the power index E in the register of the computer, 5. The process of shifting the power index E to the left, 6. Prior to the first 1 bit<u style="single">all</u>Ignore the 0 bit of, and with the exponent E<u style="single">The following process</u>7<u style="single">And</u>And 8 operations<u style="single">For</u>The process of ignoring the first 1 bit for everything following the bit of 7. For each of the bits<u style="single">Tsu</u>And regardless of 0 or 1<u style="single">Said step</u>The contents of the register B are changed by the multiplication method defined in<u style="single">2</u>At the same time as riding, the base<u style="single">A</u>Consecutive characteristic values of are from register B to register A_{<u style="single">i</u>}<u style="single"></u>Process stored in, 8.<u style="single">Also</u>And the current bit for power index E is 1 or to 1<u style="single">Su</u>If you can't<u style="single">Said</u>A step of multiplying the contents of the register B by the base A after the operation of the step 7 is completed.<u style="single">And</u>And 9. For all bits of power index E<u style="single">Tsu</u>Being<u style="single">Said</u>After the operations in steps 6-8 have been performed<u style="single">D ¥ A</u>^{<u style="single">E</u>}<u style="single"></u><u style="single">modN</u>To the last operation as<u style="single">Tsu</u>It is composed of a step of storing the result in the register B.

[0125] Further, the method of the present invention is 1. Mod.<u style="single">B</u>Is stored in register N, 2. Register S is set to 0<u style="single">Configuration</u>Step, 3. Primitive root A to be stored in register B, 4. Exponentiation E<u style="single">Computer</u>Stored in a register and set the pre-operation parameter T defined below.<u style="single">CPU memory</u>Store in<u style="single">Process,</u>5. The step of shifting the power index E to the left, 6. preceding the first bit.<u style="single">all</u>Ignore the 0 bit of, and with the exponent E<u style="single">The following process</u>7<u style="single">And</u>And 8 operations<u style="single">For</u>The process of ignoring the first 1 bit for everything following the bit of 7. For each of the bits<u style="single">Tsu</u>And regardless of 0 or 1<u style="single">Said step</u>Regarding the multiplication method defined in<u style="single">Said</u>Process 4<u style="single">And</u>And 5 are executed, and at the same time, the multiplier and the multiplier are the base A, and the continuous characteristic values of the base are from the register B to the register A._{<u style="single">i</u>}<u style="single"></u>Process stored in, 8.<u style="single">Also</u>And the current bit for power index E is 1 or to 1<u style="single">Su</u>If there is no problem, after the operation in step 7 is completed,<u style="single">Said step</u>Steps 4 and 5 are performed with respect to the multiplication method defined in, wherein the multiplicand is the contents of register B and the multiplier is base A.<u style="single">And</u>And 9. For all bits of power index E<u style="single">Said</u>Process 7<u style="single">and</u>After the operation of 8 is executed, the contents of register B are additionally multiplied by the above parameters, and TD = A.^E For the last operation as modN<u style="single">Tsu</u>It consists of a process of storing the result in the register B.<u style="single">thing</u>Features<u style="single">And the method described in paragraph number [0123]</u>Modular exponentiation by performing repetitive operations with<u style="single">D ¥ A</u>^{<u style="single">E</u>}<u style="single"></u><u style="single">modN</u>To run<u style="single">Including process</u>。

[0127] Further, the method of the present invention is:<u style="single">CPU</u>Consists of control means including a multiplication circuit<u style="single">In paragraph number [0123]</u>A device that performs modular multiplication by the method described, wherein the multiplication circuit is a multiplier.<u style="single">n bits</u>shift<u style="single">Of shape</u>Register B, mod<u style="single">B</u>As<u style="single">n bits</u>shift<u style="single">Form register N, value S</u>As<u style="single">n bits</u>shift<u style="single">Of shape</u>Register N, shift of k bits as a multiplicand<u style="single">Shape register A</u>_{<u style="single">i</u>}<u style="single"></u><u style="single">, Value J</u>_{<u style="single">0</u>}<u style="single"></u><u style="single">And</u>And Y_{<u style="single">0</u>}<u style="single"></u>As<u style="single">k-bit</u>Register means, the contents of the register B and the register A_{<u style="single">i</u>}<u style="single"></u>Multiply by multiplying with the contents of<u style="single">vessel</u>Means, additional<u style="single">n bits</u>Multiplier means<u style="single">, And</u>And<u style="single">、</u>Addition<u style="single">means</u>, Subtraction<u style="single">means</u>,Multiplexing<u style="single">Means and</u>And<u style="single">delay</u>Including means.

[0128] Further, the method of the present invention is the same.<u style="single">n-bit shift type</u>Connections between registers and other components,<u style="single">And</u>Connections between components other than the latch circuit<u style="single">But,</u>It is a 1-bit connection. Further, the method of the present invention 1.<u style="single">Computer</u>Process of storing in storage means, 2. Mod<u style="single">Register b</u>Process to store in N, 3.<u style="single">register</u>Step to set S to 0, 4.A * = ρ (AH)_N The process of performing the multiplication operation of, (where A is the operand to be exponentiated.<u style="single">, H are precomputed parameters</u>And<u style="single">Ru)</u>5. The<u style="single">Register A *</u>Process to store in B, 6.<u style="single">The register</u>For the contents of B<u style="single">2</u>Step to execute the multiplier operation, 7. Step to shift the exponent E to the left, 8. Prior to the first bit<u style="single">all</u>Ignore the 0 bit of, and with the exponent E<u style="single">The following process</u>9<u style="single">And</u>And perform 10 operations<u style="single">For</u>The process of ignoring the first bit for everything following a bit of, 9.<u style="single">Corresponds to power index E</u>On each of the bits<u style="single">Tsu</u>And regardless of 0 or 1<u style="single">The above steps 1 to 8</u>By the square method defined in<u style="single">Said</u>It is a process of executing the operations of steps 4 and 5.<u style="single">Multiplicand and multiplier</u>Are both derived from the register B and<u style="single">Montgomeri multiplier</u>To<u style="single">O</u>Consecutive characteristic values from register B to register A_{<u style="single">i</u>}<u style="single"></u>Process stored in, 10.<u style="single">Also</u>And the current bit for power index E is 1 or to 1<u style="single">Su</u>If not, after the operation of step 9 is completed, as defined above.<u style="single">2</u>Regarding how to ride<u style="single">Said</u>Process 4<u style="single">And</u>And 5, at which time, the multiplicand is the contents of register B, and the multiplier is the base A *.<u style="single">And</u>And 11. For all bits of power index E<u style="single">Tsu</u>Being<u style="single">Said</u>After the operations of steps 8 to 10 are executed, the contents of register B are original.<u style="single">Said</u>Multiply by base A additionally<u style="single">D ¥ A</u>^{<u style="single">E</u>}<u style="single"></u><u style="single">modN</u>To the last operation as<u style="single">Tsu</u>It is composed of a step of storing the result in the register B.

[0129] Further, the method of the present invention has two numerical values having an average effective length of n / 2 bits.<u style="single">Tsu</u>Be<u style="single">general</u>In a way to perform multiplication<u style="single">Ah</u>What<u style="single">The method</u>Is<u style="single">In paragraph number [0123]</u>Modular multiplication processing is executed on the numerical value by the multiplication method defined by the described method.<u style="single">Ah</u>What<u style="single">Modulo N</u>Is all<u style="single">1</u>Consists of (ffffffff ...... fff)<u style="single">n bits</u>In number, J_{<u style="single">0</u>}<u style="single"></u><u style="single">Is</u>To 1<u style="single">Be equal</u>The multiplicand is stored in register B and<u style="single">Said</u>It handles A according to the multiplication method.<u style="single">Yes,</u><u style="single">Everything</u>To 1<u style="single">Has become</u>Preloading<u style="single">For</u>Register N<u style="single">To use</u>Or a series<u style="single">hard</u>Output 1<u style="single">for</u>N<u style="single">The value of the</u>To output<u style="single">Multiplexer</u>By setting<u style="single">Value of N</u>Is all 1<u style="single">Na</u>Ri<u style="single">Gain</u>It is a thing.

[Examples] An ultra-small electronic device for performing modular multiplication and modular power of the present invention and a method for carrying out the same are described in a preferred embodiment of the present invention with reference to the accompanying drawings (FIGS. 1 to 9). It will be better understood by explaining the example concretely. These accompanying drawings show a plurality of logical concepts necessary for a general understanding of the apparatus of the present invention. In all cases, the circuit operates according to the clock signal. Then, when there is a reset signal, this reset signal is intended to bring the circuit to the zero state.

Hereinafter, examples of the present invention will be described in detail with reference to the accompanying drawings of FIGS. 1 to 9. FIG. 1 is a block diagram showing an apparatus configuration according to an embodiment of the present invention. Here, a block diagram of a monolithic circuit in which the apparatus of the present invention is integrated is illustrated. In FIG. 1, the multiplexing unit (sometimes referred to as the MULT unit) includes the hardware device on which the present invention is based. The state machine constitutes a control unit for driving the circuit of the multiplexing unit. The ROM (read-only circuit) section is entirely composed of non-volatile memory (ROM and EPROM). This ROM section contains a program for controlling the SMART card, a public key consisting of three highly reliable groups, and a program for driving the multiplexing section and the state machine. The RAM (random access circuit) section is composed of volatile memory for storing temporary operands. Examples of this type of operand include a message to be exponentiated, a public key to be encrypted, data to be transferred to the multiplexing unit, and the like. A CPU (Central Processing Unit) is actually any microcontroller that has an internal bus of 8 bits or more.

FIG. 2 is a block diagram showing a modular multiplication circuit according to an embodiment of the present invention. In this case, the modular multiplication circuit is used to perform modular squares and modular powers. In FIG. 2, reference numerals 10, 11 and 12 indicate three registers having an n-bit length (n = k · m) such as constituting the B, S and N registers, respectively. Each of these registers is loaded with a multiplier value S and a modulo value. The register is preferably divided into two n / 2 registers. Further, the register preferably contains the least significant bit portion of k bits with respect to the N and B registers. The multiplexers 13, 14 and 15, respectively, are arranged at the front of the register. In this case, if these multiplexers are subdivided and formed as individual components, each multiplexer is placed in front of each register. In addition, the three registers are intended to be loaded in series, as shown in the block diagram of FIG. However, loading in parallel format is also possible.

[0133] 16, 17 and 18 are all k-bit lengths and A._i, J₀, And Y₀It shows three registers that each accept the value of. Registers 16 and 17 are a series load / parallel output type shift register and a series and parallel load / parallel output type shift register, respectively. The register 18 is preferably a series input / parallel output type shift register. The contents of these registers are intended to be processed by multiplication means 19 and 20, respectively, via components 21 and 22, respectively. These components 21, 22 are preferably k-bit latches. If these components 21, 22 are latches, then these components 21, 22 are loaded from registers 16, 17 and 18 through the k-bit bus. On the other hand, if the above components 21 and 22 are registers, these components 21 and 22 may be loaded in series through a 1-bit connection.

Reference number<u style="single">23、</u>24, 25, 25', 26, 36, 37 and 38 indicate multiplexers. Multiplying means (multipliers) 19 and 20 are multiplying means having series input A, parallel input B, and series output, or other multiplying means having series / parallel input and series output. The multiplexer 38 forces the modulo N bit values to be all 1s (all 1s) in order to perform the multiplication process within the normal number of regions.

Reference numerals 27, 28, 29, 30 and 31 indicate 1-bit full addition / subtraction means or half addition / subtraction means. Of these, 31 indicates a total addition / subtraction means. Reference numbers 32, 33 and 34 indicate k-bit and k-clock cycle delay means capable of delaying digital signals. These delay means may be composed of either an analog element or a digital element, but it is preferably composed of an analog element. 35 indicates a borrow detector. This borrow detector is a 2-bit latch / storage means. As can be seen from FIG. 2, the device of the present invention is intended to handle large numbers, for example 512 bits, but has a small number of k-bit buses as an option. Does not have a bus. Therefore, in the device of the present invention, hardware can be saved. If the B, S and N registers have n / 2 bit parts, the device of the invention can be used to perform multiplication and exponentiation operations on 256-bit numbers. For this reason, the present invention has the advantage of providing flexibility when using the device.

[0136] FIG. 3 is a block diagram showing a special modular multiplication circuit according to an embodiment of the present invention. Here, the modular multiplication circuit according to the embodiment of the present invention is composed of logic cells. In FIG. 3, the operand is A via the series connection DI._iLatch and J₀It is supplied to the register of, the register of B, and the register of N. Then, the processing result by the operand is fetched from the register B or the register N via the series connection DO.

Signals X are B and A_iProduct of S and B A_i-It corresponds to the result (sum) of the sum of the bit flows of S (assuming that the product of S and B is smaller than N). Signal Y₀Is J₀Product of X and J₀-Corresponds to the flow of the lowest k bits in X. Signal Z is Y₀Product of N and Y₀ Corresponds to the sum of N and X. Here, the least significant k-bit in Z is all 0, so this least significant k-bit is ignored. As a result, only the most significant n bits are supplied in series with S or B.

The borrow detector is Z / 2.^kThis is a logic circuit for detecting whether or not the value of is greater than N. The subtractor (usually abbreviated as Sub, simply referred to as subtraction in Figure 3) 1 and subtractor 2 are always from the bit stream of B and S whenever the values of B and S are greater than N. It works to subtract the flow of N bits.

Adder (usually abbreviated as Ad, simply referred to as addition in FIG. 3) 1 and adder 2 are to add the flow of bits to generate the flow of X and the flow of Z. Works on. The delay element (simply referred to as a delay in FIG. 3) 1 and the delay element 2 are composed of shift registers. These delay elements are necessary to provide a storage means for synchronizing mathematical processing.

[0140] In FIG. 3, clock control is not shown. Here, it is assumed that the clock is supplied by the state machine. This clock supply is provided whenever data must be sent from one of the above-mentioned series input / series output type logic circuits or data must be provided to one of these logic circuits. Other controls, such as multiplexer address control, latch transfer signal control, etc., are also not disclosed in detail. This is because these controls will be apparent to those skilled in the art from the description contained herein.

Further, it will be apparent to those skilled in the art how the devices of FIGS. 2 and 3 perform a plurality of operations related to the method of multiplication of the present invention. However, the timing relationship of these plurality of operations is shown in FIG. 4 below just in case. FIG. 4 is a diagram showing a temporal relationship between a repetitive operation (iteration) and a multiplication operation according to an embodiment of the present invention. In this figure, all the various operations as performed in an effective and continuous clock cycle according to an embodiment of the present invention are shown graphically. In this case, n = 512 and m = 16 are set. Such setting conditions are relatively common conditions in encryption technology. When the present invention is carried out according to the examples illustrated in FIG. 3 above, the same apparatus as in FIG. 4 is used to carry out the present invention under the condition of n = 256.

[0142] In FIG. 4, a series of various operations is illustrated as a function of an effective clock cycle. The horizontal axis is graduated for this effective clock cycle (effective clock). At the beginning of each operation and at the timing before all repetitive operations, the values of B, S, and N are loaded into the corresponding registers. The repetitive operation described above forms part of the multiplication method of the present invention. The first character of A is also loaded into the corresponding register. As soon as the repetitive operation starts in the period of the k clock cycle, the contents of the B and S registers are shifted. A value of X occurs during the effective clock cycle of n + k. The first k clock cycle is X₀It is occupied by incorporating the value of. During the first effective k-clock cycle, Y₀The value of is taken in. During the next effective n + k clock cycle, the adder 31 either shifts the value of X already incorporated in the multiplier 20 or delays this value of X by the delay element 34. Incorporated in. The value of N is used in three different time phases. The first phase is used to update S and B. The second phase is Y after the delay period of the effective k clock cycle.₀Used to perform multiplication by. The second phase is used to detect how the next value of S or B is updated after the delay period of the second effective k-clock cycle. In a similar effective n + k clock cycle period, Z is calculated and Z / 2^kIs calculated. At the beginning of the first effective k-clock cycle, A_iLoad begins. Furthermore, while the repetitive movement is continuous, A_iWill continue to be loaded. Z / 2^kThe final value of is taken into the S (or B) register during the n-clock cycle period after the first effective 2k clock cycle period.

[0143] FIG. 5 is a schematic showing the configuration of cells in a series / parallel multiplier (although they have been assisted by skilled engineers in creating this schematic). Is not involved in the study of cell configurations of series / parallel multipliers related to the present invention). Each of these cells comprises a multiplier (usually abbreviated as MPL) as shown in FIG. 6 below.

FIG. 6 is a circuit diagram showing the configuration of an 8-bit series / parallel multiplier. This series / parallel multiplier runs a Booth's multiplication algorithm for unsigned series / parallel multiplier operations. The series / parallel multipliers shown in Multiplier 1 (usually abbreviated as ML, simply referred to as Multiply in FIG. 3) 1 and Multiplier 2 in FIG. 3 are k-bit long. In this case, it should be noted that the MS cell, that is, the cell of the most significant bit, is degenerated. A parallel 8-bit multiplicand is input to the XI connection. In addition, an n-bit long series multiplier is input to the Y connection (all the least significant k-bit columns that appear after the most significant 1-bit of the multiplier are 0). Further, in the product which is the result of multiplication by the multiplier, the least significant bit appears first and the most significant bit appears last in the connection MO on the output side. In this case, the entire product is n + k bits long.

FIG. 7 is a circuit diagram showing the configuration of a series adder. Here, a series adder for adding the flows of two bits appearing at the connection part of A and the connection part of B is illustrated. In this series adder, the sum of the bit flows is output at the connection portion S on the output side. In FIG. 7, the least significant bit is input first. Furthermore, the output flow for the m-bit length operand is m + 1 bit length. At the end of m effective clock cycles, the output of CI corresponds to the m + 1th bit in the number of bits.

FIG. 8 is a circuit diagram showing the configuration of a series subtractor. Here, a series subtractor for outputting the difference between the flows of two bits appearing at the connection part of A and the connection part of B is illustrated. In this series subtractor, the difference in bit flow is output at the connection portion D on the output side. In FIG. 7, the least significant bit is input first. Furthermore, the output flow for the m-bit length operand is m-bit length. At the end of m effective clock cycles, the output of BI corresponds to the m + 1th bit in the number of bits. Similarly, the output of this BI serves as a borrow display means for displaying the borrow.

FIG. 9 is a block diagram showing an architecture for calculating H parameters. Here, an n-bit length module<u style="single">(Ie, modulo)</u>The hardware configuration for calculating the H parameter for N is illustrated. In such an operation mode period, the N register performs the rotation operation n + 1 times for the n-bit length module. This rotation operation is performed in a state synchronized with the rotation operation of the S register. In this case, the register of S performs a rotation operation with the delay of the least significant bit via subtractor 1 {the least significant bit value 0 is the multiplexer (M2 1; 1) in the first clock cycle. Will be inserted into}. The borrow detector recognizes whether or not N is subtracted from the flow of S in the next rounding at the final timing when the rotation operation is completed. In addition, the borrow detector switches between previous subtraction multiplexers in response to the next rounding.

[0148] As described above, FIG. 1 shows a device for carrying out the method of the present invention in the form of a block diagram. The control unit in the device of FIG. 1 includes the following components. (1) Complete CPU (Central Processing Unit) (2) Counter (3) State Machine In addition, the CPU has non-volatile memory and volatile memory. Some of these non-volatile and volatile memories can be used in the multiplication process. Furthermore, the CPU controls the computational function block of the module in the circuit.

[0149] More specifically, the CPU has the following functions. (1) Communicating with the host (2) Loading and retrieving data from the chip (3) Instructing the circuit to perform a series of mathematical actions (4) Others Performing data processing operations in response to encrypted and unencrypted systems Counters generate addresses for real state machines.

[0150] The state machine decodes the address and generates a plurality of types of control signals for the multiplexing unit (MULT unit). These control signals instruct the multiplexing unit to perform the appropriate operating procedures required to perform the calculation of the ρ (A · B) N transformation (where A tells B). equal). FIG. 3 shows a hardware device for carrying out the physical form (multiplexing unit) of the present invention in the form of a block diagram. In addition, FIG. 3 is intended to be an aid in focusing on some concepts of architecture that should be protected by the patents of the present invention. At the same time, the block in FIG. 3 carries out the procedure specified by equations (1) to (5) as described in Montgomeri's modular multiplication. Further, the block of FIG. 3 carries out the above procedure without changing the synchronous clock and without converting S and B having a limited congruent relationship. In this section we have a constant (function of N) J₀And H are assumed to be calculated in advance. The circuit of FIG. 3 carries out ρ (A · B) N. By utilizing the features of this circuit, this circuit can be used to perform the following calculations.

[0151] (1) B AmodN (2) B²modN However, in any case, B must be less than N. Here, the procedure for carrying out C = B · AmodN will be described in detail. (1) First, the processor preloads operand B into the register of B. Similarly, the processor preloads operand N into the register of N.

(2) Every time the circuit in the multiplexing section starts to calculate the value of S next time, the circuit will change to A next time._iTells the CPU to preload (by flagging). After S (m) iterations, a number with a limited congruence to B remains in B's register. (3) The multiplexing unit calculates F = ρ (B · H) N. Where the processor is H_iH is a pre-computed constant in the procedures described in steps (1) and (2) above, except when pre-loading the processing procedure for the character in (processor A)._iThe same is true if you pre-load your character).

On the other hand, C = B²The procedure for performing modN will be described in detail. (1) First, suppose that B's registers hold a number that is known to have a limited congruence to B. Furthermore, it is assumed that the register of N holds the module N (which is generally the case in square processing). Here, the multiplexing part is B₀And B₀With the lowest character of A_iBy loading the register of, the square processing can proceed.

(2) The calculation process of B = ρ (B · B) N proceeds in the same processing process as the second step (step (2)) in the above multiplication operation. However, when the register of B is rotating, B_iThis is not the case when the continuous loading operation of the character is performed in series and on-the-fly from the register of B.

(3) If necessary, the calculation of ρ (B · H) is performed in the same manner as in the third step (step (3)) in the above multiplication operation. As will be apparent to those skilled in the art, the inventor does not dare to claim that series / parallel multipliers and general components form part of the present invention itself. The following explanation is made to clarify that the standard logical cells that are widely used are used. However, some of the logical cells may be less commonly used. The gate configuration illustrated here is merely exemplified for the proof of the present invention. A skilled technician will optimize these logical cells.

Operands A, B, and N are all n-bit long and consist of m groups of k-bit long characters. Therefore, n = k · m holds. In a hardware device with k = 32, m is an 8-bit or 16-bit binary bit length.<u style="single">Multiplier 1 and Multiplier 2</u>These multipliers (ML) perform Booth's multiplication algorithms for unsigned multiplication operations. In this case, the parallel operands have a k-cell (bit) length, and the serially loaded operands have an arbitrary desired bit length.

Each series / parallel multiplier consists of k-1 MPL cells (see Figure 5). The highest-level cell corresponding to the MS bit consists of only AND gates. Each MPL cell performs a multiplication operation between the Y series input bits and the XI parallel input bits. Further, this multiplication operation generates the series output of the MPL unit in the previous stage and the carry output bit of its own previous cycle. The MPL cell above sums these output results.

As can be seen in FIG. 5, each MPL cell is a 2-bit multiplier adder. The block of MPL cells multiplies the input bits of XI by the input bits of Y in series. Further, this block performs addition processing of the multiplication result from DI (data input) and CI (carry input) from the previous cycle. The final result is a DO (data output) and a CO (carry output) for the next cycle. This carry output CO is stored in the D flip-flop. The data output DO is expressed by the following equation (37).

[0159] [Number 37]<img file="JP3636740B2_D0037.tif" />The carry output CO stored in this way becomes the carry input CI for the next cycle. This carry output CO is represented by (38) below by the sum of Booleans.<u style="single">Adder 1 and adder 2</u>Each adder (Ad) used here is a simple 1-bit full adder consisting of a D flip-flop. This adder is used to store the carry bits that will be output in the next clock cycle (see Figure 7).

As shown in FIG. 7, the two inputs A, B are added together with the carry input CI from the previous clock cycle. As a result, the sum of modulo 2 is generated. This sum is stored in the D flip-flop to take out the output signal S. When the adder is reset, the carry bit will be 0.<u style="single">Subtractor 1, subtractor 2 and subtractor 3</u>As shown in FIG. 8, each block of the subtractor (Sub) is a total subtractor composed of D flip-flops for storing the previous borrow. This block has almost the same configuration as the block of the adder described above. However, the subtractor differs from the adder in that the flow of B is drawn in series from the flow of A.

【0162】<u style="single">Delay element 1, delay element 2 and delay element 3</u>These delay elements (Delay) are composed of storage elements in a connected state of k1 bits. These delay elements are used in mathematical processing to synchronize various operands. These synchronous operations will become apparent if the circuit is described.

【0163】<u style="single">A</u>_{<u style="single">i </u>}<u style="single">, J</u>_{<u style="single">0 </u>}<u style="single">, And Y</u>_{<u style="single">0 </u>}These blocks are k-bit long series input / parallel output type shift registers. In this case, the k-bit input bits are input in series. After an effective clock cycle period of k bits, these k bits appear on the output side in parallel form.

[0164] In FIG. 2, a thin line indicates a series of 1-bit conductor wires, and a thick line indicates a parallel k-bit conductor wire.<u style="single">M4 1; x, M3 1; x, and M2 1; x</u>These blocks are 1-bit output multiplexers. M4 1; x takes one output from four inputs. M3 1; x takes one output from three inputs. M2 1; x takes one output from two inputs. x indicates a clear index for a particular component.<u style="single">B (0: k-1), B (k: n1-1), B (n1: n2), S (0: n1-1)</u><u style="single">), S (n1: n2), N (0: k-1), B (k: n1-1), and B (n1: n2)</u>These blocks are shift registers. The size and position of the bit string of a register with a relatively long bit length is indicated by the number in parentheses (). For example, X (s: t) is a t-s + 1 bit length shift register. Where s is the index of the first bit of register X (s: t) and t is the index of the last bit of register X (s: t). For example, B (0: 511) consists of three relatively short cascaded registers: That is, it is composed of B (0:31), B (32: 255), and B (256: 511).

[0165] n1 is generally equal to n / 2 (eg 256). n1 must be a multiple of k. n2 is equal to n-1. k is the length of the instrument character, i.e. the size of the series / parallel multiplier. Therefore, in the first processing process, the next value is predicted.

[0166] n1 = 256, n2 = 511, n = 512, and k = 32<u style="single">Latch 1 and latch 2</u>These two latches are k-bit registers. These latches are used to hold parallel data in the multiplier. The operation of such a latch enables parallel conversion using a single clock in the multiplication process.

【0167】<u style="single">Operation of multiplexing part (MULT part) ... Multiplication and power in ρ area</u>For simplicity, we will only specify the clock cycle in which the data in the register actually moves. That is, we define the cycle in which data moves in this way as an effective clock cycle.<u style="single">Multiplication of ρ (A · B) N</u><u style="single">Stage 1: Initial loading</u>At this stage, the following registers are loaded via DI.

(1) J₀J in the register of₀(Calculated in advance by the CPU) (2) Load B into register B (3) Load N into register N (4) A₂A, A in the register of₀At the same time as loading the first character of, in step (2), the bit value 0 is loaded into register S.

After loading predetermined values into these five registers, the two unsigned series / parallel multipliers ML1 and ML2, the series adders Ad1 and Ad2, and the series subtractors Sub1, Sub2 and Sub3 It will be reset.<u style="single">Second stage: B / A</u>_{<u style="single">0 </u>}<u style="single">Execution of repetitive operation of</u>Register A_iData loaded into A₀Is transferred to latch 1. Register B periodically shifts to the right. At the beginning of the repetitive operation, the control signal of the borrow detector 2 has a bit value of 0. Therefore, the content of B remains unchanged even after passing Sub1. Furthermore, the content of B is A in ML1.₀Is multiplied by. The output of register B is input unchanged.

The result of such multiplication is added in series to the contents of register S in Ad1. At the first repetitive operation, the contents of register S are all 0. By this operation, X is generated as described above. While the above processing process is in progress, the CPU is the next character of A, A.₁Is preloaded on latch 1.

[0171] Furthermore, J₀J from register to latch 1₀Is loaded. X is input in series with ML2, J₀Is multiplied by. Register Y after the effective k clock cycle has elapsed₀The content of is the product X₀ J₀It becomes the lowest k-bit of. In addition, ML2 is reset after the first effective k-clock cycle. Here, the series input type multiplexer M3 1; 4 switches the flow of X to the flow of N. Register Y₀The data in is J₀Is replaced by and loaded in parallel with latch 2. In addition, the output of latch 2 is Y₀ Switch to N flow. In the next n + k clock cycle period, the serial output from ML2 will be Y₀ Become N. X delayed by the effective k clock cycle period is now added in Ad2 to generate the product of ML2. As a result, Z = X + Y₀ N is obtained. Here, Z is a number such that the lowest k bits are all 0s.

[0172] Since the first k bits of Ad2 are all 0, this first k bit is ignored. Then, the next n bits are returned in series to the S register. The final value of the iterative operation is equal to or greater than N (in this case it is necessary to subtract this value from N). That is, S (1) \ S (1) modN holds. In Sub3, n-bit length (Z / 2) to detect whether S is greater than N.ⁿ) Is subtracted from N. However, in this case, only the nth borrow bit is stored in the borrow holding flip-flop.

If the bit value of this borrow bit is 0 or the bit value of the final carry bit CO of Ad2 is 1, the latest value in the register of S is greater than N. At the beginning of the first iterative operation, there is a number in the register of S that has a limited congruence to S (1) modN. J₀, B and N registers hold the original values loaded first. And A to hold the data in advance_iRegister is A₁To hold.

【0174】<u style="single">Stage 3: Subsequent B / A</u>_{<u style="single">i </u>}<u style="single">Execution of repetitive operation of</u>A, the next character after A₁Is transferred to the parallel inputs of latch 1 and ML1. Next B / A_iAt the end of each repetitive motion, there is a number S with a limited congruent relationship to S (i) modN during the repetitive motion of and subsequent repetitive motions. If S (i) is greater than N, then N is subtracted from S (i) in Sub2.

[0175] At the beginning of each repetitive operation, the CPU is the next character of A, A.₁A to hold the data in advance_iLoad it into the register of.<u style="single">ρ (B B) N squared operation</u>The first action of normal exponentiation is the squared action. This square operation is the multiplier A loaded in the register of B and A._iThe procedure is similar to the normal multiplication with the multiplicand loaded in the register of. However, in this case, the number of bits increases by k bits as described above. Further subsequent square operations are performed by operands (multiplicands and multiplicands) that have a limited congruence relationship, such as those that exist in B's registers.

[0176] While a squared motion such as ρ (B · B) N above is being performed, J₀, S, B and N registers are loaded as-is on their output side without changing the values obtained by the previous multiplication and square processing. However, in this case, in the repetitive operation, A_iThe register of must load a new character derived from the k-bit character that resides in the register of B.

[0177] In the above continuous square operation, A_iRegisters are preloaded from register B on the fly. Once the CPU gives an instruction to perform the square processing, the subsequent square operations are performed without any problem. B (i) loaded into the register of B is a part of B flowing through Sub1 (B)._iThe part that is already smaller than N)<u style="single">Stage 1: BB</u>_{<u style="single">0 </u>}<u style="single">Repeated operation of</u>First, it is assumed that the latest number having a limited congruence relationship with S, as derived from the previous calculation process, exists in the register of B.

[0178] The lowest k bits of registers B and N periodically shift to the right. Furthermore, after an effective k-clock cycle, registers B and N return to their original state. The value in register B is either the appropriate B value or the BN value used to perform the multiplication in the next ρ region. Therefore, in the first rounding, register A_iIs B₀Or it must be preloaded with the least significant k-bit of BN. Where B₀Is a value that exists in register B.

The purpose of this rotation operation of the first k-bit is that the first k-bit of the preload to the register Ai is Sub.<u style="single">(Ie, subtractor)</u>This is to allow it to flow through 1. Immediately after being loaded in series, Ai Latch<u style="single">(Ie, latch)</u>Unloaded to 1, the Ai preload register is the second letter of B, B₁ Be free to load. Borrow during this and subsequent operations<u style="single">(Ie Borrow)</u>2 The output from Sub 1 is positive when the signal is set or reset and is always less than N.

[0180] When all the values are loaded into the register, B will rotate when B is rotated as explained.₁Except for the point that is loaded in the Ai register (remember that the CPU loads in the Ai register in multiplication), this first multiplication is B · A as explained earlier.₀Is executed against. Second k-bit character B₁This first BB because it originates from the B stream₀B during processing₁The segment is the next square root extraction, that is, B / B.₁Switched on-the-fly in series in the Ai preload register for repetition. Second stage: BB₁Repeat operation A_iValue B loaded into the register of₁Is transferred to the output latch Latch 1. B · B during the next n + 2k (ie n + 64) clock cycle₁The multiplication process for is executed as described above.

As before, the Borrow 1 and Borrow 2 signals determine whether N can be subtracted from the flow generated from the B and S registers. If the value in the S register is greater than or equal to N, Borrow 1 is set and N is subtracted from S in the subtractor Sub 1. If necessary, N is subtracted from S during the completion of the m iterative multiplication loop. Such a situation is detected by Borrow2 at the end of the preceding multiplication or square root extraction operation.

Flip-flops Borrow 1 and Borrow 2 are conditional rags from Sub 3.<u style="single">-</u>The final value of the output is memorized. Borrow1 is set or reset after each S iteration. Borrow2 is set or reset after the last S (m) iteration where B is loaded into S (m). This conditional rag<u style="single">-</u>The output is a signal indicating whether S (i) is greater than N.

[0183] B / B₁During processing, letter B₂Character B if is present in the subtractor Sub 1₂Is loaded into the Ai preload register on the fly. Stage 3: Next BB₁Multiply repeat character B₁Character B when is in the subtractor Sub 1₁The remaining m-2 iterations are performed in preparation for the next loop while the value of is loaded into the Ai register.

The final result of the limited match is in the S and B registers. This data is output in series through DO and will be modified in Sub 1 if necessary. Multiply Block Manipulation-H Parameter Calculation To calculate H, the machine is reconfigured to use registers S and N as shown in Figure 9. The operation of the operator will be described using the numerical examples already used above. This configuration executes the operation of H n + 1 times. In each run, both S and N are rotated, and each rotation is n clocks. At each execution time, N rotates and returns unchanged. In the i-th run, the S and the Next Subtract signals contain the equivalent of a limited \ match of S (i). Initial Condition-First Execution At the beginning of the first execution, N is loaded into the N register, the borrow detection flag indicating that the first trial subtraction was successful is reset, and Sub The output flip-flop of 1 is reset to zero. During the first execution, the nth MS bit of trial division is 1. This bit is stored by inferring the next subtraction flip-flop (there is no space in S). The next subtraction commands the SN subtraction in the first execution. Illustrated using the n = 4-bit numerical example above.<img file="JP3636740B2_D0038.tif" /><img file="JP3636740B2_D0039.tif" /> 【0185】<img file="JP3636740B2_D0040.tif" /><img file="JP3636740B2_D0041.tif" /> 【0186】<img file="JP3636740B2_D0042.tif" /> 【0187】<img file="JP3636740B2_D0043.tif" /> 【0188】<img file="JP3636740B2_D0044.tif" />BRIEF DESCRIPTION OF THE DRAWINGS [Fig. 1] Fig. 1 is a block diagram showing an apparatus configuration according to an embodiment of the present invention.

FIG. 2 shows an embodiment of the present invention.<u style="single">Modular</u>-It is a block diagram showing a multiplication circuit.

FIG. 3 is a special embodiment of the present invention.<u style="single">Modular</u>-It is a block diagram showing a multiplication circuit.

FIG. 4 is a diagram showing a temporal relationship between a repetitive operation and a multiplication operation according to an embodiment of the present invention.

FIG. 5 is a circuit diagram showing a cell configuration of a series / parallel multiplier.

FIG. 6 is a circuit diagram showing a configuration of an 8-bit series / parallel multiplier.

FIG. 7 is a circuit diagram showing a configuration of a series adder.

FIG. 8 is a circuit diagram showing a configuration of a series subtractor.

FIG. 9 is a block diagram showing an architecture for calculating H parameters.

[Explanation of sign] 10 ~ 12 ... Register 13 ~ 15 ... multiplexer 16 ~ 18 ... Register 27 ~ 31 ... Addition / subtraction means 32 ~ 34 ... Delay means 35 ... Borrow detection vessel