JP2003114618A - Data processing device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To make fast processing conventionally actualized by operating two computing elements in parallel in a Montgomery residue arithmetic circuit. SOLUTION: The mentioned processing can be mathematically composed and actualized by a single computing element.

Description

Detailed Description of the Invention

[0001]

TECHNICAL FIELD The present invention relates to a modular multiplication operation (mod).
ular multiplication) and modular exponentiation (modular exp)
onentiation) and decoding (d
ecryption) is effective when applied to devices, especially IC
The present invention relates to a technique effectively applied to a data processing device having high security such as a smart card.

[0002]

GSM widely used in Europe
(Global Systems for Mobile communications) standard mobile phones such as mobile phones and IC cards (s
mart card), user authentication (user authenticity
n) and electronic commerce can be performed. Generally, when used as electric money, it takes the form of an IC card,
In the case of an M mobile phone (GSM mobile radiotelephone system), a form called SIM (Subscriber Identification Module) is used. Both SIMs and IC cards are semiconductor chips with terminals attached to a plastic plate, and the device itself is the same semiconductor chip in both cases, so the IC card will be described below. An IC card holds private information that cannot be rewritten without permission, and a cryptographic key (cryptographic k) that is secret information.
ey) for data encryption (encryption) and ciphertext (ciph
er text) is a device for performing decryption. The IC card itself does not have a power supply, and when it is inserted into a reader / writer for IC cards, it receives power supply and becomes operable. When it becomes operable, it receives a command transmitted from the reader / writer and performs processing such as data transfer according to the command. A general explanation of IC cards can be found in "IC Card" by Junichi Mizusawa, edited by The Institute of Electronics, Information and Communication Engineers, Ohmsha. As shown in FIG. 1, the configuration of the IC card is such that the IC card chip 1 is placed on the card 101.
It is equipped with 02. As shown in the figure, an IC card generally has a supply voltage terminal Vcc, a ground terminal GND, a reset terminal RST, an input / output terminal I / O, and a clock terminal CLK at the positions defined in the ISO7816 standard, and these terminals are connected through these terminals. , Power supply from the reader / writer and data communication with the reader / writer (W. Rankl and Effing: SMARTCARD H
ANDBOOK, John Wiley & Sons, 1997, pp.41). The configuration of the IC card chip is basically the same as that of a normal microcomputer. As shown in FIG. 2, the configuration is such that a central processing unit (CPU) 20
1, a memory device 204, an input / output (I / O) port 207, and a coprocessor 202 (there may be no coprocessor). The CPU 201 uses logical operations (logical o
The storage device 204 is a device that stores programs and data, and is a device that performs peration and arithmetic operation. The input / output port is a device that communicates with the reader / writer. The co-processor is a device that performs high-speed cryptographic processing itself or computations required for cryptographic processing. For example, a special computing device for performing a remainder operation of RSA cryptography or DES (Data Encryption Standard) processing. There is a cryptographic device for performing. Many IC card processors do not have a co-processor. The data bus 203 is a bus that connects each device. The storage device 204 is a ROM (Read Only Memory) or a RAM (Random Access).
Memory), EEPROM (Electrical Erasable Programmable
Read Only Memory). ROM is a memory that cannot be changed, and is a memory that mainly stores programs. RAM is a memory that can be rewritten freely, but if the power supply is interrupted, the stored contents will be lost. When the IC card is removed from the reader / writer, the power supply is interrupted and the RAM contents are no longer retained. E
EPROM is a memory that can retain its contents even when power supply is interrupted. This memory needs to be rewritten and is used to store the data to be held even if the IC card is removed from the reader / writer. For example, the usage frequency of the prepaid card is rewritten each time it is used, and since it is necessary to retain the data even if it is removed from the reader / writer, it is retained in the EEPROM. In order to realize user authentication and electronic money payment, public key cryptography technology is required. Public key cryptography is used by embedding secret information in public information, and since different keys are used on the transmission side and the reception side, it is also called asymmetric key cryptography. As a public key cryptosystem that is currently widely used,
There is RSA encryption. The RSA cryptography is based on the fact that it is easy to generate a product of large prime numbers, but it is difficult to factor a given composite number. In RSA cryptography, for a public modulus N and a given cipher text Y, a secret expo
nent) X is used to calculate Y ^ X mod N (Y ^ X means Y to the Xth power) to obtain plain text M
And vice versa. This operation is called modular exponentiation. Here, X, Y, N, as of 2001, since a very large number of 1024 bits to 2048 bits is used,
How to execute “Y ^ X mod N” at high speed has been a problem in the fields of applied mathematics and engineering. In particular,
In a device such as an IC card in which the capacity of a storage device is limited and the capacity of a CPU is low, the power-residue calculation is a very large task, and its high-speed calculation is a very important issue. Various power-residue calculation algorithms are known, but for example, the following ones are widely used. This is an addition chain
n method). In this algorithm, n corresponds to the bit length of X, and (X [n-1] X [n-2] ... X [1] X [0]) is the binary representation of X. . This algorithm is roughly the squared modular multiplication "A ^ 2 mod N" (step 4) and the modular multiplication "A = A * B.
mod N ”(step 5) is executed in combination and X [n-
If the number of 1's in 1], X [n-2], ..., X [1], X [0] is H (X), then the squared modular multiplication "A ^ 2 mod N" is repeated n times. The remainder multiplication "A = A * B mod N" is repeated H (X) times. It is confirmed by a numerical example that the correct result is obtained by the above algorithm 1. In terms of confirming the algorithm, it is sufficient to materialize the index X, so Y
And N will be used as they are. Calculate S = Y ^ 45 mod N according to Algorithm 1. Where the index 45
Can be written in binary as 45 = 101101 (binary). Therefore, when the exponent is expressed using the symbol of Algorithm 1, X [5] = 1, X [4] = 0, X [3] = 1, X [2] = 1, X [1] = 0,
X [0] = 1. The number of bits n is 6. The initial value of S is 1. (1) Since the initial value of S is 1 when j = 5, even if this is squared and the remainder is divided by N, it is 1 (step 4). Since X [5] = 1, step 5 is executed and S = 1 * Y mod N = Y mod N is obtained. (2) When j = 4, the value of S at this time is initially S = Y mod N, so if you take the square of this and take the remainder, you get S = Y ^ 2 mod N. Since X [4] = 0, step 5 is not executed and S
= Y ^ 2 mod N remains. (3) When j = 3, the value of S at this time is S = Y ^ 2 mod N at first.Therefore, if this is squared and divided by N, the remainder is S = Y ^ 4 mod N. Become. Since X [3] = 1, step 5 is executed and S = Y ^ 4 * Y mod N = Y ^ 5 mod N. (4) When j = 2, the value of S at this time is initially S = Y ^ 5 mod N, so if you take the remainder by squaring this and dividing by N, S = Y ^ 10 mod N
Becomes Since X [2] = 1, step 5 is executed and S = Y ^ 10 * Y mod N = Y ^ 11 mod N. (5) When j = 1, the value of S at this time is initially S = Y ^ 11 mod N, so
Square this and take the remainder divided by N, S = Y ^ 22 mod
N. Since X [1] = 0, step 5 is not executed and S = Y ^ 22 mod N remains. (6) When j = 0, the value of S at this time is S = Y ^ 22 mod N at first.Therefore, if this is squared and the remainder is divided by N, S = Y ^ 44 mod N
Becomes Since X [0] = 1, step 5 is executed and S = Y ^ 44 * Y mod N = Y ^ 45 mod N, and the desired result is obtained. As described above, in the algorithm 1, the power-residue calculation is decomposed into the modular multiplication (including the square) and executed, so that an arithmetic device having an arithmetic function of “A * B mod N” may be used. However, A, B, and N are all very large values. For example, assuming that the data length is 1024 bits, which is the current mainstream, the intermediate result A * B is 2048 bits.
There is the problem of a large number of bits. Furthermore, the value obtained by dividing A * B by N is the final result, so division that handles a large value of 2048 bits ÷ 1024 bits must be executed. Here, the multiplication can be performed in parallel by a microprocessor or the like by dividing the multiplier and the multiplicand, but it is difficult to parallelize the division, which has been a factor that impedes speeding up. Such modular multiplication "A * B mod N"
Algorithm for executing "A * B * R ^ (-1) mod N" without dividing by N to solve the problem of division in 2
It has been known. Here, R is 2 ^ n (n is a bit length of N, for example), and is a positive integer that satisfies R> N. Further, in the following, it is assumed that N is an odd number. This assumption is R
Elliptic curve cryptography (elliptic curl) on SA and prime field
ve cryptography) is a valid assumption. In fact
In RSA, N is a product of large prime numbers, and in prime field,
Modular arithmetic op modulo large prime
N is an odd number as well, since N. Algorithm 2 below is based on the mathematician Peter Montgomery (Pete
r Montgomery). The details of the argument leading to Algorithm 2 are omitted here, but for example, the paper PL Montgomery, “Modular Multiplication wit written by Montgomery himself.
hout Trial Division ”, Math. Comp., vol. 44, 1985,
pp.519-521, or the standard handbook in cryptography A. Menezes, PCvan Oorschot, S.
A. Vanstone, “Handbook of Applied Cryptography”,
CRC-press, 1997, pp. 602-603. Algorithm 2 requires that A * B * R ^ (-1) mod N
Therefore, in order to execute the modular exponentiation operation in the RSA cryptography using the device that performs this operation, it is necessary to use a modified algorithm such as the following algorithm 3. [Algorithm 3] input Y, X = (X [n-1] X [n-2] ... X [1] X [0]), N output Y ^ X mod NA = R mod N Step 1 B = Y * R mod N Step 2 For j = n-1 to 0 step 1 {Step 3 A = (A ^ 2) * R ^ (-1) mod N Step 4 If X [j] = 1 then A = A * B * R ^ (-1) mod N step 5} A = A * R ^ (-1) mod N step 6 output A step 7 In algorithm 3 during steps 1-5, a multiplier (mul
The tiplier) and the multiplicand are multiplied by R mod N. Hereinafter, this data format will be referred to as Montgomery format. The above Montgomery multiplication "ABR ^ (-
1) In "mod N", the Montgomery form is kept unchanged. Actually, Mont (A) = A * R mod
If you write like N, Mont (A) * Mont (B) * R ^ (-1) mod N = A * R * B * R * R ^ (-1) mod N = A * B * R mod N = Mont (A * B). Therefore, for example, "A * B * R ^ (-1) mod N", "(A
^ 2) * R ^ (-1) mod N ”,“ A * R ^ (-1) mod N ”If there is a computing unit, the procedure of Algorithm 3 above can be performed using the CPU and these computing units. It can run fast.
"(A ^ 2) * R ^ (-1) mod N" and "A * R ^ (-1) mod N" are B = in "A * B * R ^ (-1) mod N", respectively. Since A and B = 1, it can be seen that the modular exponentiation operation can be realized by configuring an arithmetic unit "A * B * R ^ (-1) mod N". Next, in step 2, "A * B * R ^ (-1)
Here is a brief summary of what has been done so far on how to speed up the algorithm for calculating "mod N". For the sake of explanation, Algorithm 2 is shown again. Known typical speed-up methods can be classified as follows. First speed-up method: A method that reduces the number of loop iterations including steps 3, 4, and 5 Second speed-up method: A method that parallelizes the processing of steps 3, 4, and 5 Third speed-up method: Replacing the processing in step 6 with a simpler method A typical one of the first speed-up methods is to execute addition processing collectively for a plurality of bits. For example, a method for collectively executing k-bit processing is shown in Algorithm 4 below. [Algorithm 4] For j = 0 to 2 ^ k 1 step +1 {Step 1 TBL (j, B) = j * B Step 2 TBL (j, N) = j * N Step 3} W = 0 Step 4 For j = 0 to n / k-1 step +1 {Step 5 T = W + TBL (A [j, k], B) Step 6 U = T mod 2 ^ k Step 7 M [j, k] = -U * N [0, k] ^ (-1) mod 2 ^ k Step 8 W = T + TBL (M [j, k], N) Step 9 W = W / 2 ^ k Step 10} If W> = N then W = WN Step 11 Output W Step 12 Here, for simplicity, k is assumed to be a divisor of n. For example, when n = 1024, k = 2, 4, 8, etc. may be selected. A [j,
k] indicates the value of the j-th k-bit block from the bottom of A. Similarly, M [j, k] indicates the value of the j-th k-bit block from the bottom of M, and N [0, k] indicates the value of the lowest k-bit block of N. In addition, the calculation in step 8 is performed so that the value becomes positive. In the algorithm 4, if k = 1, then N is an odd number, so that M matches U and algorithm 2 is obtained. Based on this method,
A method of performing modular multiplication is disclosed in Japanese Patent Laid-Open No. 7-20778, Masahiko Takenaka et al., "Residual Calculator, Table Creating Device and Multiplicative Residual Calculator". Algorithm 4 is a little complicated, so its mechanism will be briefly described. Before explaining the contents of the algorithm 4, it is necessary to briefly understand the principle of the Montgomery method. The Montgomery method is, in principle, equivalent to solving the indefinite equation (Diophantine equation) in which M and W are unknowns: (Equation 1) A * B + M * N = W * R. First, N is an odd number and R = 2 ^ n
Note that (Equation 1) has an integer solution, since The assumption that N is odd is essential, as (Equation 1) does not necessarily have an integer solution when N is even. In order to understand the meaning of (Equation 1), FIG. 3 is a diagram expressing this. Since R = 2 ^ n, the lower n bits of the right side of (Equation 1) are all 0. Therefore, finding M that satisfies (Equation 1) means that the lower n bits of AB and MN are 0. It is nothing but the operation of choosing M. This upper half bit string is the value of A * B * R ^ (-1) mod N to be obtained. However, the sum of the number of 2n bits and the number of 2n bits becomes 2n + 1 bits, and the most significant bit may be 1 (hereinafter, this bit is referred to as an OV bit). This is resolved in step 11 of Algorithm 4. R = 2 ^ on both sides of (Equation 1)
Taking the remainder divided by n gives (Equation 2) (A * B mod 2 ^ n) + (M * N mod 2 ^ n) = 0. (Equation 2) is transformed to obtain (Equation 3) M = -A * B * N ^ (-1) mod 2 ^ n. Since the modulus is power of 2, this M can be obtained in order for each bit block. This is the meaning of Algorithm 4. In Algorithm 4, since the number of loops is 1 / k, roughly speaking, the speed of the loop portion is about k times. However, in this case, if k is increased, there is a problem that the size of the multiplication table is increased. As the size increases, the RAM area gets under pressure. Generally, in devices such as IC cards, since the RAM area is small, it is often impossible to make k large.
This is the first problem. The second speed-up method can be used together with the first speed-up method. Note that in Algorithm 4, the value of M is determined when the lower k bits of T are determined (step 8), and it can be seen that the process of step 9 can be executed immediately after the determination. Therefore, if two n-bit adders are installed and a circuit is configured to execute step 6 and step 9 in parallel, the speed is almost doubled. However, this method requires twice the number of adders. Not only does this mean that the number of computing units is doubled, but it also reduces the power consumption during execution.
(power consumption) also means doubling. This is the second problem. The third speed-up method is
It is independent of the first and second speed-up methods. As is well known, the comparison process, such as step 11 of Algorithm 4, actually performs the subtraction and the negative flag (negative fl
Achieved by examining ag). Since this is a subtraction process between large numbers such as 1024 bits, the processing time may not be ignored. On the other hand, in the computer, R = 2 ^
Comparison with n is easy. Therefore, the last comparison / subtraction processing unit (step 11) can be speeded up by using the following modified algorithm 5. Regarding speeding up by this change, Japanese Patent Laid-Open No.
-21057, Kunihiko Nakada "Data Processor and Microcomputer", Kunihiko Nakada: DATA PROCESSOR AND MICR
OPROCESSOR, United States Patent, US005961578A. [Algorithm 5] For j = 0 to 2 ^ k 1 step +1 {Step 1 TBL (j, B) = j * B Step 2 TBL (j, N) = j * N Step 3} W = 0 Step 4 For j = 0 to n / k-1 step +1 {Step 5 T = W + TBL (A [j, k], B) Step 6 U = T mod 2 ^ k Step 7 M [j, k] = -U * N [0, k] ^ (-1) mod 2 ^ k Step 8 W = T + TBL (M [j, k], N) Step 9 W = W / 2 ^ k Step 10} If W> = R then W = WN Step 11 Output W Step 12 Here, the comparison processing in Step 11 can be realized only by determining whether or not the OV bit in FIG. 3 is 1. This is much lighter and faster than the subtraction process. However, the value obtained by Algorithm 5 is A * B *
It may be A * B * R ^ (-1) mod N + N rather than R ^ (-1) mod N itself. However, since the bit length remains n bits, in the modular exponentiation operation, it is only necessary to finally modify the value. The present invention is irrelevant to this speed-up method and is related to the first and second speed-up methods. The problems 1 and 2 above are elliptic curve cryptography.
to system) Galois field of characteristic 2 (Galois field of
It also occurs in characteristic 2). Let me briefly explain the concept of the Galois field. The Galois field itself is a purely mathematical concept, but a suitable isomorphism (homom
Orphism) can be translated into a specific operation. The simplest method to implement a Galois field on a computer is modular polynomial
arithmetic operation) is used. First, consider an entire polynomial whose coefficient is 0 or 1, and let this set be POLY. It is an element of POLY and is an irreducible polynomial of degr
ee n) F (X), and for the two elements of POLY, A (X) and B (X), the sum (which is synonymous with the difference) is the sum of the coefficients in the normal polynomial sum. It is defined to be performed in the meaning of exclusive OR, and the product is defined by A (X) * B (X) mod F (X). As is well known in algebra, F
Elements of POLY that are not multiples of (X) have the inverse of the product operation described above. In POLY, A (X) and B
The fact that (X) is equivalent means that these differences A (X) -B
(X) is defined as a multiple of F (X), and POLY is defined by this equivalence relation.
Write GF (2 ^ n) that is divided into valent class). This is,
It is a Galois field with characteristic 2. Algebraic structure of GF (2 ^ n) (algebrai
It is well known that (c structure) does not depend on how to select the irreducible polynomial F (X) of degree n. In terms of implementation, 3 terms
And a polynomial consisting of 5 terms is often chosen. This polynomial F
(X) is sometimes called reduction polynomial. The Galois field product operation is realized by performing addition processing that appears in a normal product operation in the sense of exclusive OR. In the adder, if carry propagation is not performed, the value becomes the same as that of performing bitwise exclusive OR, and the Galois field product operation is realized. In the Montgomery method, essentially the same operation is performed. The condition that "the modulus N is an odd number", which was necessary in the ordinary Montgomery method, is replaced by the condition that the constant term of F (X) is 1, which means that F (X) is irreducible. Therefore, it follows automatically and there is no problem in applying the Montgomery method. R = 2 ^ n in normal Montgomery method
Is replaced by R (X) = X ^ n. Further, the process of determining M, which is important in the Montgomery method, can also be realized by not carrying carry. Therefore, the processing of the Montgomery method in the Galois field can be realized as follows. [Algorithm 6] W (X) = 0 Step 1 For j = 0 to n-1 step +1 {Step 2 T (X) = W (X) + A [j] * B (X) Step 3 If T ( X) mod X is 1 then W (X) = (T (X) + F (X)) / X Step 4 Else W = T / X Step 5} where A [j] is A (X) It is the coefficient of the j-th term. Also,
The sum is used to mean an exclusive OR for each coefficient. The algorithm 6 does not require the subtraction process that is used in the ordinary Montgomery method because the Galois field does not have a size relation except the order, and the order of A (X) and B (X) is n.
If less than (for GF (2 ^ n) this is always true),
This is because W (X) configured in the above algorithm 6 is less than the nth order, and is therefore the remainder to F (X) as it is. Therefore, the third problem that occurs when performing the Montgomery method in ordinary modular multiplication does not exist in the Galois field. It is confirmed by a numerical example that a correct answer can be obtained by this algorithm 6. GF (2 ^ 4) for simplicity
In, F (X) = X ^ 4 + X + 1. A (X) = X ^ 3 + X
^ 2 + 1, B (X) = X ^ 3 + X + 1 for A in GF (2 ^ 4)
And B are calculated, that is, A (X) * B (X) mod F (X) is calculated.
In this case, note that A [0] = 1, A [1] = 0, A [2] = 1, A [3] = 1, and the processing of Algorithm 6 is sequentially executed. (1) W (X) = 0, A [0] = 1 when j = 0, so in step 3, W (X) = 0 + 1 * (X ^ 3 + X + 1) = X ^ 3 + X + 1 and this constant term is 1, so execute step 4 and write W (X) = (X ^ 3 + X + 1 + X ^ 4 + X + 1) / X = (X ^ 4 + X ^ 3 + 2 * X + 2) / X = (X ^ 4 + X ^ 3) / X = X ^ 3 + X ^ 2. Note that the double is 0. (2) W (X) = X ^ 3 + X ^ 2, A [1] = 0 when j = 1, so in step 3, W (X) = X ^ 3 + X ^ 2 + 0 * (X ^ 3 + X + 1) = X ^ 3 + X ^ 2. Since this constant term is 0, step 5 is executed and W (X) = (X ^ 3 + X ^ 2) / X = X ^ 2 + X. (3) W (X) = X ^ 2 + X, A [2] = 1 when j = 2, so in step 3, W (X) = X ^ 2 + X + 1 * (X ^ 3 + X + 1) = X ^ 3 + X ^ 2 + 2 * X + 1 = X ^ 3 + X ^ 2 + 1. Since this constant term is 1, execute step 4, and W (X) = (X ^ 3 + X ^ 2 + 1 + X ^ 4 + X + 1) / X = (X ^ 4 + X ^ 3 + X ^ 2 + X + 2) / X = (X ^ 4 + X ^ 3 + X ^ 2 + X) / X = X ^ 3 + X ^ 2 + X + 1. (4) When j = 3, W (X) = X ^ 3 + X ^ 2 + X + 1, A [3] = 1, so in step 3, W (X) = X ^ 3 + X ^ 2 + X + 1 + 1 * (X ^ 3 + X + 1) = 2 * X ^ 3 + X ^ 2 + 2 * X + 2 = X ^ 2. Since the constant term is 0, step 5 is executed and W (X) = X ^ 2 / X = X. W (X) obtained by the above calculation is A (X) * B (X) * R (X)
It should be ^ (-1) mod F (X), so R (X) ^ (-
1) Multiplying R (X) = X ^ 4 to remove mof F (X), X * X ^ 4 mod (X ^ 4 + X + 1) = X * (X + 1) = X ^ 2 + X. To confirm whether this result is correct, A
(X) * B (X) mod F (X) is calculated in the usual way. A (X) * B (X) = (X ^ 3 + X ^ 2 + 1) * (X ^ 3 + X + 1) = X ^ 6 + X ^ 5 + X ^ 4 + 3 * X ^ 3 + X ^ 2 + X + 1 = X ^ 6 + X ^ 5 + X ^ 4 + X ^ 3 + X ^ 2 + X + 1, so A (X) * B (X) mod F (X) = X ^ 6 + X ^ 5 + X ^ 4 + X ^ 3 + X ^ 2 + X + 1 mod (X ^ 4 + X
+ 1) = (X ^ 2 + X + 1) * (X ^ 4 + X + 1) + X ^ 2 + X mod (X ^ 4 +
X + 1) = X ^ 2 + X, and certainly the same polynomial as the value calculated by Algorithm 6 multiplied by R (X) is obtained. In the above calculation in the Galois field, the operation of replacing 2 with 0 is performed, but this is because the calculation of the sum is executed by the exclusive OR. Modification of this algorithm to process every k bits can be realized in the same manner as in the case of normal modular multiplication. The algorithm of Montgomery method in GF (2 ^ n) is shown. [Algorithm 7] For j = 0 to 2 ^ k 1 step +1 {Step 1 TBL (H [j] (X), B (X)) = H [j] (X) * B (X) Step 2 TBL (H [j] (X), F (X)) = H [j] (X) * F (X) Step 3} W (X) = 0 Step 4 For j = 0 to n / k-1 step + 1 {Step 5 T (X) = W (X) + TBL (A [j, k] (X), B (X)) Step 6 U (X) = T (X) mod X ^ k Step 7 M [ j, k] (X) = U (X) * F [0, k] (X) ^ (-1) mod X ^ k Step 8 W (X) = T (X) + TBL (M [j, k ] (X), F (X)) Step 9 W (X) = W (X) / X ^ k Step 10} where polynomial H [j] (X) in Algorithm 7 is j
H [j] (X) = j [k-1] * X when the binary expansion of is j = (j [k-1] j [k-2] ... j [0]) ^ (k-1) + j [k-2] * X ^ (k-2) +
... + j [0] are associated with each other. Also, A [j,
k] (X) is a polynomial corresponding to the j-th k-bit block when the polynomial A (X) is expressed as a bit string, and F [0, k]
The same applies to (X) and M [j, k] (X). Furthermore, the sum of steps 6 and 9 means the exclusive OR of each term. Numerical examples are omitted.

[0003]

SUMMARY OF THE INVENTION The present invention relates to a microcomputer for performing modular multiplication and modular exponentiation on a large number, and a method of executing the same. The method of Montgomery PL Montgomery, ”Modul
ar Multiplication without Trial Division ”, Math.
Comp., Vol. 44, 1985, pp.519-521), the above-mentioned when mounting this on the microcomputer.

2. Description of the Related Art Two problems explained in the prior art, namely, (first problem) enlargement of multiplication table necessary for simultaneously processing a plurality of bits (second problem) A * B, M * When the processing of N is executed simultaneously and the double speed is realized, it solves the problem that the amount of the arithmetic unit and the power consumption are doubled, and the product operation of Galois field GF (2 ^ n) is solved. On the other hand, it tries to solve the same problem. The above and other objects and novel features of the present invention will be apparent from the description of this specification and the accompanying drawings.

[0004]

The outline of the invention disclosed in the present application is as follows. Consider Algorithm 4 (repost) of the Montgomery method below. [Algorithm 4 (repost)] For j = 0 to 2 ^ k 1 step +1 {Step 1 TBL (j, B) = j * B Step 2 TBL (j, N) = j * N Step 3} W = 0 Step 4 For j = 0 to n / k-1 step +1 {Step 5 T = W + TBL (A [j, k], B) Step 6 U = T mod 2 ^ k Step 7 M [j, k] = -U * N [0, k] ^ (-1) mod 2 ^ k Step 8 W = T + TBL (M [j, k], N) Step 9 W = W / 2 ^ k Step 10} If W > = N then W = WN Step 11 Output W Step 12 First

2. Description of the Prior Art Algorithm 4
The processing steps 6 and 9 in 1. are large number addition processes, and most of the hardware can be considered to be this adder. The processing of steps 6 and 9 is processing for k * bit blocks of A * B processing and M * N processing. Therefore, these are combined and addition processing is performed for k * bit blocks of A * B + M * N. I know I can go. Since the addition process corresponding to each loop is of the form "k-bit number x B" and "k-bit number x N", the required new table has the following form. You can see. TBL (j, t) = j * B + t * N (j, t = 0, 1, 2, ..., 2 ^ k
1) Two parameters, j and t, are needed to select this table. These parameters can be selected so that when added to W, the lower k bits of the sum will be zero. In other words, if you select TBL (A [j, k], M [j, k]) = A [j, k], * B + M [j, k] * N as a table in the processing of the j-th step, Good. M [j, k] is a value that also depends on A [j, k]. The following algorithm 8 is one in which the tables are rearranged in advance so that the calculation of M is unnecessary. [Algorithm 8] For j = 0 to 2 ^ k-1 step 1 {Step 1 For s = 0 to 2 ^ k-1 step 1 {Step 2 U = (s + j * B [0, k]) mod 2 ^ k step 3 M = −U * N [0, k] ^ (-1) mod 2 ^ k step 4 TBL [j, s] = j * B + M * N step 5}} W = 0 step 6 For i = 0 to n / k-1 step 1 {Step 7 W = W + TBL (A [i, k], W [0, k]) Step 8 W = W / 2 ^ k Step 9} If W> = N then W = WN Step 10 Output W Step 11 The above algorithm 8 represents the essence of the present invention. The addition process that appears in two places in Algorithm 4, that is, the processes of steps 6 and 9 in Algorithm 4 are one addition process in Algorithm 8. If the processes of steps 6 and 9 in the algorithm 4 are sequentially calculated, the calculation speed is approximately doubled by adopting the algorithm 7. Also, when the processes of steps 6 and 9 in algorithm 4 are executed in parallel as many coprocessors do, two adders are required, but when algorithm 7 is adopted, the number of adders is increased. Can be halved, and
As a direct result of this, the power consumption is reduced. In this algorithm 7, if carry propagation is not performed, the product operation of GF (2 ^ n) is realized as

This is as described in "Prior Art". Therefore, GF (2
The effect of the present invention that occurs in the above normal modular multiplication also appears for the product operation circuit of (^ n).

[0005]

BEST MODE FOR CARRYING OUT THE INVENTION The above-mentioned algorithm 8 will be described below again. Hereinafter, a method of forming a circuit according to this algorithm will be described. [Algorithm 8 (repost)] For j = 0 to 2 ^ k-1 step 1 {Step 1 For s = 0 to 2 ^ k-1 step 1 {Step 2 U = (s + j * B [0, k] ) mod 2 ^ k step 3 M = −U * N [0, k] ^ (-1) mod 2 ^ k step 4 TBL [j, s] = j * B + M * N step 5}} W = 0 Step 6 For i = 0 to n / k-1 step 1 {Step 7 W = W + TBL (A [i, k], W [0, k]) Step 8 W = W / 2 ^ k Step 9} If W> = N then W = WN Step 10 Output W Step 11 The processing of Algorithm 7 is roughly divided into three parts. In other words, there are three: the "table generation unit" from Step 1 to Step 5, the "addition processing unit" from Step 6 to Step 9, and the "value correction unit" from Steps 10 and 11. First, the "addition processing unit", which has high generality
And then the “value correction unit” and finally the “table generation unit”, and the circuit configuration in which these are integrated will be described. There are various known adder construction methods.
Here, a typical one will be described. Adder is 1
It is configured by arranging adders for each bit. Now, a circuit for adding two m-bit numbers S and T is constructed. In the following description, each binary number S = (S [m-1] S [m-
2] ... S [1] S [0]), T = (T [m-1] T [m-2] ... T [1] T [0]) and their sum Z = (Z [ m] Z [m-1] ... Z [1] Z [0]) is used. When the addition process is broken down into bit units, the values required for the addition of the jth bit are S [j], T [j] and the carry C [j-1] generated in the previous calculation. is there. However, C [-1] = 0 and Z
[m] = C [m-1]. FIG. 4 is an example of a full adder that adds 1 bit. The j-th 1-bit full adder has S [j], T [j] and the carry signal C [j-
[1] can be regarded as a circuit which outputs the value z [j] of the j-th bit of Z and the carry signal C [j]. The circuit of FIG. 4 has a logical formula: (Formula 4) Z [j] = (S [j] AND T [j] AND C [j-1]) OR (S
[j] AND NOT (T [j]) AND NOT (C [j-1])) OR (NOT (S [j]) A
ND T [j] AND NOT (C [j-1])) OR (NOT (S [j]) AND NOT (T
[j]) AND C [j-1]), (Equation 5) C [j] = NOT ((S [j] AND NOT (T [j]) AND NOT (C
[j-1])) OR (NOT (S [j]) AND T [j] AND NOT (C [j-1])) OR
(NOT (S [j]) AND NOT (T [j]) AND C [j-1]) OR (NOT (S
[j]) AND NOT (T [j]) AND NOT (C [j-1])). 401, 402, 403, 404 of FIG.
405 is an AND circuit, 406, 407 are OR circuits, 409, 410,
411, 412, 413, 414, 415, 416, 417 are inverters (N
OT circuit). These correspond to AND, OR, and NOT in (Equation 4) and (Equation 5), respectively. Each of AND, OR, and NOT is a logic gate composed of several transistors.
(logic gate). AND is only when all inputs are 1
It is a logic gate that outputs 1 and outputs 0 otherwise.OR is a logic gate that outputs 1 if any one of them is 1 and outputs 0 only when all 0s are input. is there.
NOT (inverter) is a logic gate that outputs 1 for an input 0 and outputs 0 for an input 1. By arranging 1-bit full adders, a multi-bit full adder can be created. FIG. 5 shows a 4-bit full adder. 50
Reference numerals 1, 502, 503, and 504 are 1-bit full adders shown in FIG. 4, and are calculated according to (Equation 4) and (Equation 5). Carry is set to 0 in the least significant bit. The last carry is Z [4]. Although the case of 4 bits is shown here, it is obvious that any number of bits can be added by increasing the number of 1-bit full adders. The configuration method of the full adder shown here is the simplest one called "carry propagation adder", and carry propagation time (carry propagation time)
Is a circuit with a large ratio and takes the longest addition time. The hardware algorithm for faster addition is
Although there are many, the method of constructing the adder has nothing to do with the essence of the present invention, and therefore, further explanation is omitted. Next, the processing of the value correction unit will be described. In the value correction section,
A subtraction process is used. Subtractor
er) has a structure similar to that of an adder, and can be configured by using a carry propagation adder. Therefore, an ordinary computer has an adder circuit but not a subtractor circuit. FIG. 6 is a configuration example of a 4-bit subtraction circuit (Z = ST) using a full adder. Although 601, 602, 603, and 604 are 1-bit full adders, the first carry (borrow) is 1 at the time of input, and T is the inverter 605, 6
It is different in that it is inverted depending on 06, 607, 608. In subtraction, when the last carry (borrow) becomes 1, it means that the result is negative. This phenomenon is called underflow. A configuration example of the value correction unit will be described using the concept of the subtractor described above. Figure 7
FIG. 4 is a block diagram of the value correction circuit. n
The + 1-bit register 702 contains the value W and the n-bit register 703 contains the value of the modulus N, both of which
WN is calculated by the n + 1-bit subtractor 704. This value WN, a borrow selection signal (selection signal) generated as a result of this operation, and the value of W are selected by the selector 705.
If the selection signal is 0, the selector 705
If N is selected and output, and the selection signal is 1, W is selected and output. Here, W and N have been described as dedicated registers, but it goes without saying that they can be arranged in the RAM used for CPU processing. Next, the circuit of the table generation unit will be described. K = 2 for simplicity
Only shown in case of. When the values generated by the table generation unit when k = 2 are listed, the table shown in FIG. 8 is obtained. In this configuration example, the multiples N, 2 * N, 3 * N of the modulus value N independent of the input values A, B are calculated in advance and stored in the registers 909, 910, 911. , Use this. Since the input value B is the input value itself,
No need to calculate. B is held in the register 906. Eleven values other than 0 and the above four values B, N, 2 * N, 3 * N must be calculated each time. Here, the configuration has been shown in which the 11 values are calculated using only the adder. The size of the register must be at least (k + 1 =) 3 bits larger. Each register has a data bus 92
The data bus 921 is connected to 1 and is used as a signal line for supplying data to the addition processing unit. Reference numeral 904 denotes an adder that adds the number of n + 2 bits, and sends the value of the sum of n + 3 bits to the selector 903. Upon receiving the calculation start signal determined from the clock signal, the control device 905 initializes the internal counter to 0001 in binary notation, and inputs the value of B to the adder 904 (both) via the selector 901. As adder 904
To operate. Immediately before the calculation is started in the adder 904, a control signal is sent from the adder 904 to the control device 905. Control device
905 receives the control signal, increments a counter therein, and obtains a value of 0010 in binary notation,
These lower 2 bits 00 and upper 2 bits are respectively j * B + t *
As j and t in N, the selector 903 determines the position of the register 907 in which the answer of the adder 904 is written, and writes the addition result. Next, the calculation start signal is transmitted again to the control device 905, and the control device 905 sends a control signal to the selector 901, reads B and 2 * B, inputs them to the adder 904, and performs the same operation as before. Write the value 3 * B to register 908. By the operation up to here, the value for composing the table, B, 2 * B, 3 * B,
N, 2 * N, 3 * N are all available. Similarly, the register to be read and the register to be written are determined from the value of the counter of the control device, and the same operation is repeated. However, when the lower 2 bits of the counter are 00, the addition operation is skipped. In this way, after all the values are set,
Register 906, 907, 908, 909, 910, 911, 912, 913, 91
4, 915, 916, 917, 918, 919, 920 are used as read-only registers. Next, FIG. 10 shows a block diagram of a circuit in which these are combined to calculate A * B * R ^ (-1) mod N and the result is written in the A register. However, the value adjusting section is omitted to avoid complication. In general, the subtraction processing required by the value adjusting unit is realized by changing the input value of the adder 1015. FIG. 10 includes all the important components of the present invention. Hereinafter, the same variable names as those used in Algorithm 8 are used. In FIG. 10, first, the value of A stored in the A register 1003 is sequentially read from the lower order. The structure of the A register is shown in FIG. At this time, the control device 1007 receives the number i of the 2-bit block to be read from the 9-bit register 1006,
The value of the corresponding 2-bit block is read out and transmitted to the register 1008. The lower 2 bits of W are stored in the register 1009. The values of 1008 and 1009 are transmitted to the value selection and signal control device 1011, and 1011 reads the corresponding data from the value table of 1002 via the data bus 1001, and adds the values of 1027 bit and 1026 bit. Send to adder 1015. However, dedicated registers 1013 and 1014 are connected to the adder 1015, and the value read from the table is temporarily held in the 1027-bit register 1014. Reference numeral 1013 is a 1026-bit register in which W appearing in Algorithm 7 is stored. It is cleared to 0 at the start of operation. J * B + t * N in value table 1002
The sum of the data of the form and W is added by the adder 1015. Since the lower 2 bits of this addition result are 00 in binary notation, they are cut off by the 2-bit right shifter 1016 and input to the control device 1017. Meanwhile, the adder 1015
Simultaneously with the calculation start, the value 1 is sent to the adder 1018, and the adder sums the value of the 9-bit register 1019 and the calculation start signal “1” and sends the result to the 9-bit register 1019. Initially 0 is stored in 1019. This sum is sent to the control device 1017, and the control device 1017 determines that the sum is 51
If it has not reached 2, the output result of 1016 is written to the register 1013 as it is, and as for the value of 1013, only the lower 2 bits of W are extracted at 1011 and written to the register 1009. Further, at this time, a signal is sent from 1017 to 1007 via 1011, the value of i is incremented by the adder 1005, and the next 2-bit block of the A register is read,
The addition with the value in the table is performed through the same process as described above. If the value of 1019 has reached 512, it sends a signal to the selective transmission circuit 1012 and sends the value of W in 1013 to the A register. The value of the A register at this point is A * B * R ^ (-1) mo
d N or A * B * R ^ (-1) mod N + N. The latter requires the process of subtracting N from A. The subtraction processing unit is omitted. This is one of the embodiments of claims 1 and 7 of the present invention. The above embodiment can be variously modified without departing from the scope of the present invention. For example, the following changes are possible. (1) The adder 1015 is configured to add 1027 bits at the same time here, but it can also be realized by dividing this into a plurality of blocks and sequentially adding these for each block. it can. In this case, the amount of hardware decreases, but the speed decreases. (2) Without using the 2-bit left shifter 1016, only the bits higher than the lower 2 bits can be directly connected to the register of 1013. (3) Change the number of bits of the values A, B, N. For example, 2048
It can be changed to bits, 512 bits, 768 bits, etc. (4) The value of k can be changed to a value other than 2, for example, 1, 3, 4 or the like. However, if n is not a multiple of k, a logic circuit for correction is required. (5) In the table, eliminate 0, and instead, when the value added to W is 0, add a logic circuit that directly inputs the value of W to the shifter without inputting it to the adder. The above changes can be made independently of "synthesis of addition tables" which is essentially the gist of the present invention. Next, different from the above-mentioned changes, those requiring some attention will be described. Again, Algorithm 8 is shown. [Algorithm 8 (repost)] For j = 0 to 2 ^ k-1 step 1 {Step 1 For s = 0 to 2 ^ k-1 step 1 {Step 2 U = (s + j * B [0, k] ) mod 2 ^ k step 3 M = −U * N [0, k] ^ (-1) mod 2 ^ k step 4 TBL [j, s] = j * B + M * N step 5}} W = 0 Step 6 For i = 0 to n / k-1 step 1 {Step 7 W = W + TBL (A [i, k], W [0, k]) Step 8 W = W / 2 ^ k Step 9} If W> = N then W = WN Step 10 Output W Step 11 Here, the maximum value of the table TBL [j, s] is (2 ^ k-1) * B.
+ (2 ^ k-1) * N. Since this value has a maximum of n + k + 1 bits, the bit length of TBL [j, s] must be increased according to the value of k. Since the number of data is 4 ^ k, k
The amount of data increase with is up to k * 4 ^ k bits. Generally k
Is not a large value, so it does not pose a big problem in implementing the present invention, but it is not a desirable phenomenon. There are ways to avoid this problem. Attention is paid to steps 8 and 9. The value of TBL (A [i, k], W [0, k]) in step 8 is selected so that the lower k bits of the sum in step 8 are always 0. Then, in step 9, that k
Bits are cut off by right shifting. this is,
It shows that the calculation of the lower k bits is completely unnecessary. Therefore, it is understood that the table values themselves need only be prepared by cutting off the lower k bits (shifted by k bits to the right). Specifically, the value “j * B +
Instead of using "t * N", a value "(j * B + t * N) >>k" obtained by shifting this by k bits is defined as a new table, and the same calculation as algorithm 8 is performed. However, the value of W is right-shifted by k bits before the addition processing. That is, the calculation is performed according to the following algorithm. [Algorithm 9] For j = 0 to 2 ^ k-1 step 1 {Step 1 For s = 0 to 2 ^ k-1 step 1 {Step 2 U = (s + j * B [0, k]) mod 2 ^ k Step 3 M = −U * N [0, k] ^ (-1) mod 2 ^ k Step 4 NTBL [j, s] = (j * B + M * N) >> k Step 5}} W = 0 Step 6 For i = 0 to n / k-1 step 1 {Step 7 W = W / 2 ^ k Step 8 W = W + NTBL (A [i, k], W [0, k]) Step 9 } If W> = N then W = WN Step 10 Output W Step 11 Here, step 8 does not need to use a shifter in terms of implementation. The right shift is always performed by k bits, so this is wired so as to directly correspond to the k bit shift. The sum of the lower k bits is not calculated. However, lower than W
When at least one of the k bits becomes 1, that is, when the logical OR of each of the lower k bits is 1, this is input to the adder as a carry C [-1]. In fact, if the OR is 0, all k bits are
It is shown that 0, and the corresponding lower k bits of M must also be 0. However, when the logical sum is 1, all the lower k bits of the sum with M are 0. This is because a carry always occurs when M is selected. FIG. 15 shows an embodiment of a circuit for addition processing in consideration of these. In this embodiment, k = 2. In the circuit shown in FIG. 15, an NTBL register 1504 for storing the value of NTBL and a W register 1503 for storing the value of W are connected to the adder 1502. The lower two bits of the W register are not connected to the adder 1502, but instead to the value selection and signal controller, which two bits are used to select the value of NTBL. Further, each of the two bits is connected to an OR gate 1501 that calculates a logical sum. The calculated value of the OR gate 1501 is input to the adder 1502 as the carry signal C [-1]. The carry signal C [-1] is used as an initial value of carry when performing addition. This is one of the embodiments of the present inventions 4 and 7. Next, an embodiment of the present invention which operates according to the following algorithm 7 (reprinted) for the Galois field GF (2 ^ n) will be described. [Algorithm 7 (repost)] For j = 0 to 2 ^ k 1 step +1 {Step 1 TBL (H [j] (X), B (X)) = H [j] (X) * B (X) Step 2 TBL (H [j] (X), F (X)) = H [j] (X) * F (X) Step 3} W (X) = 0 Step 4 For j = 0 to n / k- 1 step +1 {step 5 T (X) = W (X) + TBL (A [j, k] (X), B (X)) step 6 U (X) = T (X) mod X ^ k step 7 M [j, k] (X) = U (X) * F [0, k] (X) ^ (-1) mod X ^ k Step 8 W (X) = W (X) + TBL (M [ j, k] (X), F (X)) Step 9 W (X) = W (X) / X ^ k Step 10} For operations in the Galois field GF (2 ^ n),

As described in "Prior Art". Therefore,
This is realized by changing all the addition processing in the circuit in the first embodiment of the present invention described above to exclusive OR for each bit. Since the process of the product operation is composed of the shift process and the addition process, it is only necessary to replace the part of the addition process with the process of the exclusive OR for each bit. Needless to say, the sum may be replaced with an exclusive OR in the table configuration. However, unlike the normal Montgomery method, which has a modulus N of n bits, a polynomial of degree n is used, and therefore an expression of n + 1 bits is required. Further, in the case of the Galois field GF (2 ^ n), the final value correction processing is unnecessary. Other configurations may be exactly the same as those of the circuit of the normal Montgomery method. This is shown in FIG.
Shown in. However, here, k = 2 and reduction polynom
The degree of ial F (X) shall be 257. Hereinafter, the same variable names as those used in Algorithm 7 are used. In FIG. 12, first, the value of A stored in the A register 1203 is sequentially read from the lower order. The configuration of the A register is the same as that shown in FIG. At this time, the control device 1207 controls the number i of the 2-bit block to be read.
Is read from the 7-bit register 1206, the value of the corresponding 2-bit block is read, and this is transmitted to the register 1208. The lower 2 bits of W are stored in the register 1209. The values of 1208 and 1209 are the value selection and signal control device 1211.
1211 sends the appropriate data to the data bus 1201
Via the value table of 1202 (the table generation will be described later), and sends the value to the exclusive OR calculator 1215 which performs the exclusive OR of the values of 258 bits and 256 bits. However, dedicated registers 1213 and 1214 are connected to the exclusive OR calculator 1215, and the value read from the table is temporarily held in the 258-bit register 1214. Reference numeral 1213 is a 258-bit register in which W (X) appearing in Algorithm 7 is stored. At the start of operation
It is cleared to 0. Included in the value table 1202 "(polynomial of less than or equal to 1) * B (X) + (polynomial of less than or equal to 1)
The exclusive OR calculator 1215 calculates the exclusive OR of the data in the form of * F (X) (see FIG. 13) and W (X). In this result, the lower 2 bits are 00 in binary notation.
Is cut off and input to the control device 1217. On the other hand, the exclusive OR calculator 1215 sends the value 1 to the adder 1218 at the same time as the calculation is started, and the adder sums the value of the 7-bit register 1219 and the calculation start signal “1” and outputs the result. Send to 7-bit register 1219. In 1219, 0 is initially stored. This sum is sent to the controller 1217 and the controller 1217
If the above sum does not reach 128, the output result of 1216 is directly written to the register 1213, and the value of 1213 is
At 1211, only the lower 2 bits of W (X) are extracted and written to the register 1209. Also, at this time, from 1217 to 12
Signaled to 1207 via 11 and exclusive OR calculator
The value of i is incremented by 1205, the next 2-bit block of the A register is read, and the exclusive OR with the value of the table is calculated through the same process as the above. If the value of 1219 reaches 128, it sends a signal to the selective transmission circuit 1212 and sends the value of W (X) in 1213 to the A register. The value of the A register at this point is A (X) * B (X) * R
(X) ^ (-1) mod F (X). The table generation circuit is also realized by replacing the addition process with the exclusive OR process. This is shown in FIG. In this configuration example, input value A
For F (X), XF (X), and (X + 1) F (X), which are multiples of reduction polynomial F (X) that do not depend on (X) and B (X), they are calculated in advance. It is held in registers 1409, 1410, 1411 and used. The input value B (X) does not need to be calculated because it is the input value itself. B (X) is held in the register 1406. 0 and the above four values B (X),
Eleven values other than F (X), XF (X), and (X + 1) F (X) must be calculated each time. Here, the configuration for calculating the 11 values using only the exclusive OR calculator has been shown.
The size of the register must be at least (k =) 2 bits larger. Each register is connected to a data bus 1421, and the data bus 1421 is used as a signal line for supplying data to the exclusive OR processing unit. 1404 is 25
It is an adder that adds 8-bit numbers, and sends the value of the sum of 258 bits (note that the number of bits does not increase because no carry occurs in GF (2 ^ n)) to the selector 1403. The control device 1405 receives the calculation start signal determined from the clock signal, initializes the internal counter in binary notation to 0001, and inputs the value of B (X) to the adder 1404 via the selector 1401. The exclusive OR calculator 1404 is operated as (both). Immediately before the calculation starts in the exclusive OR calculator 1404, a control signal is sent from the exclusive OR calculator 1404 to the control device 1405. Upon receiving the control signal, the control device 1405 increments the internal counter, and displays 00 in binary.
A value of 10 is obtained, and the lower 2 bits 00 and the upper 2 bits are set as j (X) and t (X) in j (X) * B (X) + t (X) * F (X), respectively. 1403 determines the position of the register 1407 in which the result of the exclusive OR calculator 1404 is written, and writes the result of the exclusive OR. Next, the calculation start signal is again transmitted to the control device 1405, and the control device 1405 sends a control signal to the selector 1401, reads B (X) and XB (X), and inputs them to the exclusive OR calculator 1404. And register 14
Write the value (X + 1) B (X) to 08. By the operation up to here, the value for composing the table, B (X), XB (X), (X + 1) B (X), F
(X), XF (X), (X + 1) F (X) are all complete. Similarly, the register to be read and the register to be written are determined from the value of the counter of the control device, and the same operation is repeated.
However, when the lower 2 bits of the counter are 00, the addition operation is skipped. In this way, after all values are set, registers 1406, 1407, 1408, 1409, 1410, 14
11, 1412, 1413, 1414, 1415, 1416, 1417, 1418, 141
9 and 1420 are used as read-only registers. This is one of the embodiments of claims 2 and 7 of the present invention.
The above embodiment can be variously modified without departing from the scope of the present invention. For example, the following changes are possible. (1) The exclusive OR calculator 1215 is configured to add 258 bits at the same time here, but by dividing this into a plurality of blocks and sequentially adding these for each block It can also be realized. In this case, the amount of hardware decreases, but the speed decreases. (2) Without using the 2-bit left shifter 1216, only the bits higher than the lower 2 bits can be directly connected to the register 1213. (3) Change the number of bits of the values A (X), B (X), F (X). (4) The value of k can be changed to a value other than 2, for example, 1, 3, 4 or the like. However, if n is not a multiple of k, a logic circuit for correction is required. (5) In the table, eliminate 0 and use W (X) instead
When the value added to is 0, the value of W (X) is not input to the exclusive OR calculator, but a logic circuit is directly input to the shifter. The above changes can be made independently of the "value table composition" that is essentially the subject matter of the present invention. Also in the Galois field, the table size can be reduced by k bits in the same manner as in the case of the normal Montgomery method processing.
The concept is exactly the same as Algorithm 9 except for carry and subtraction processing for the final value adjustment. The algorithm is shown below. [Algorithm 10] For j = 0 to 2 ^ k 1 step +1 {Step 1 NTBL (H [j] (X), B (X)) = H [j] (X) * B (X) >> k Step 2 NTBL (H [j] (X), F (X)) = H [j] (X) * F (X) >> k Step 3} W (X) = 0 Step 4 For j = 0 to n / k-1 step +1 {Step 5 T (X) = W (X) + TBL (A [j, k] (X), B (X)) Step 6 U (X) = T (X) mod X ^ k Step 7 M [j, k] (X) = U (X) * F [0, k] (X) ^ (-1) mod X ^ k Step 8 W (X) = W (X) + NTBL (M [j, k] (X), F (X)) Step 9 W (X) = W (X) / X ^ k Step 10} Here, regarding the determination of M [j, k] (X) above. Is processing W
Unlike the normal Montgomery method, the carry bit does not occur as long as the lower k bits of (X) are retained (however,
Mathematical expression is almost the same). A Galois field calculation circuit corresponding to FIG. 15 is shown in FIG. The difference from the circuit in FIG. 15 is that the adder is an exclusive OR calculator 1601 and there is no OR circuit that generates a carry signal. This is one of the embodiments of claims 4 and 7 of the present invention. So far, an embodiment of the present invention for modular multiplication, and
Although the examples of the present invention for the Galois field G (2 ^ n) are shown separately, they can be combined. The data length required by the RSA encryption and the elliptic curve encryption are significantly different. In general,
The number of N bits in the RSA encryption needs to be about 1024 bits to 2048 bits in order to have sufficient security. On the other hand, the data length in elliptic curve cryptography having the same strength as the RSA cryptography is about 160 to 256 bits. Therefore, it is possible to use a part of the RSA circuit as a GF (2 ^ n) calculator. It can be seen that the sum operation of GF (2 ^ n) is the same as the carry operation with all carry values set to 0 in the normal addition process, as follows. For example, among the logical expressions corresponding to the circuit of FIG. 4, those expressing the j-th bit: (Equation 4 (repost)) Z [j] = (S [j] AND T [j] AND C [j-1 ])
OR (S [j] AND NOT (T [j]) AND NOT (C [j-1])) OR (NOT (S
[j]) AND T [j] AND NOT (C [j-1])) OR (NOT (S [j]) AND NO
In T (T [j]) AND C [j-1]), if C [j-1] = 0, then (Equation 6) Z [j] = (S [j] AND T [j] AND 0) OR (S [j] AND
NOT (T [j]) AND NOT (0)) OR (NOT (S [j]) AND T [j] AND N
OT (0)) OR (NOT (S [j]) AND NOT (T [j]) AND 0) = (S [j] AND NOT (T [j])) OR (NOT (S [j]) AND T [j]) = S [j] EXOR T [j] is obtained. Here, S [j] EXOR T [j] is the exclusive OR of S [j] and T [j]. That is, if all the carry is set to 0, it is understood that it is an exclusive OR for each bit. The bitwise exclusive OR is the polynomial expression of the element A of GF (2 ^ n): A (X) = A [n-1] * X ^ (n-1) + A [n-2] * X ^ (n-2) +…
+ A [1] * X + A [0] as the bit string: (A [n-1] A [n-2]… A [1] A
It can be seen that it corresponds to the operation of the sum in GF (2 ^ n) when corresponding to [0]). Therefore, in the adder,
It is possible to add GF (2 ^ n) (exclusive OR) by adding a circuit that sets the carry to 0. This embodiment is shown in FIG. FIG. 17 shows the adder of FIG. 4 with a selector. The adders are connected in a chain, and the carry C [j] propagates to the next adder. Each selector selects carry or 0 depending on the carry from the pre-adder and the value 0 depending on whether the control signal is 1 or 0. For example, if the control signal is 1, the carry is selected, and if the control signal is 0, the value 0 is selected. In the former case, a normal adder and in the latter case, a GF (2 ^ n) adder (exclusive OR calculator)
Function as. FIG. 18 shows the configuration of an adder which combines these circuits and shares the circuits of FIGS. The adder with carry control function in FIG. 18 is the same as that in FIG. 17, and functions as an adder for modular multiplication or an adder for product operation of Galois field GF (2 ^ n) depending on the switching signal. Is decided. This is one of the embodiments of claims 6 and 7 of the present invention. The gist of the present invention is irrelevant to the value of k, but in implementation, it is not possible to take k as large as possible. In particular, in a microcomputer for an IC card, the size of RAM is about several kilobytes to ten and several kilobytes, and the value of k is greatly restricted. The inventors have found that the advantage of the present invention is highest when k = 2 in comparison with other methods. Therefore, this is included in the claim, and the claim is defined as claim 7. Also, the modular exponentiation operation or Galois field GF (2
It is needless to say that the hardware configuration for implementing the product operation of ^ n) is not limited to the above-mentioned various embodiments and can be changed appropriately.

[0006]

The effects obtained by the typical ones of the inventions disclosed in the present application will be briefly described as follows. That is, the modular exponentiation operation "Y ^
X mod N ”and the processing of the elliptic curve cryptography on the Galois field GF (2 ^ n) can be realized. Further, in the implementation of the above dedicated hardware for the modular exponentiation operation or the product operation on the Galois field GF (2 ^ n), the logic circuit scale can be minimized. Furthermore, the above-mentioned dedicated hardware is mounted on the same semiconductor chip as the IC card microcomputer, and encryption using the modular exponentiation operation "Y ^ X mod N" is performed.
Decryption '(encryption / decryption), or Galois field GF (2 ^
n) A microcomputer for encryption / decryption of the above elliptic curve cryptography can be realized at low cost and with ease of use. Needless to say, the same effect can be expected not only for IC cards but also for devices that require cryptographic processing with low power consumption, such as mobile terminals such as GSM.

[Brief description of drawings]

[Figure 1] Overview of IC card and terminals.

FIG. 2 is a configuration of a microcomputer.

FIG. 3 Principle of Montgomery method.

FIG. 4 shows an example of a 1-bit full adder.

FIG. 5 is a 4-bit full adder.

FIG. 6 is a 4-bit subtraction circuit using a full adder.

FIG. 7 is a value correction circuit.

FIG. 8 is a value table when k = 2.

FIG. 9 is a value table generation circuit when k = 2.

FIG. 10 is an embodiment of the present invention.

FIG. 11 is an A register.

FIG. 12 is an example of the present invention for Galois field GF (2 ^ n).

FIG. 13 is a value table for Galois field GF (2 ^ n) when k = 2.

FIG. 14 is a value table generation circuit for Galois field GF (2 ^ n) when k = 2.

FIG. 15 is an example of an addition processing device in Montgomery modular multiplication.

FIG. 16 is an embodiment of an addition processing device in the Montgomery method for Galois field GF (2 ^ n).

FIG. 17 is an adder with a carry control function.

FIG. 18 is a shared circuit of a modular multiplication adder and a Galois field GF (2 ^ n) product calculation adder.

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Takashi Watanabe             1-280, Higashi Koikekubo, Kokubunji, Tokyo             Central Research Laboratory, Hitachi, Ltd. (72) Inventor Kunihiko Nakata             5-20-1 Kamimizuhonmachi, Kodaira-shi, Tokyo Stock             Ceremony Company within Hitachi Semiconductor Group (72) Inventor Takashi Tsukamoto             5-22-1 Kamimizuhonmachi, Kodaira-shi, Tokyo Stock             Ceremony Company Hitachi Cho-LS System             Within (72) Inventor Seiji Kobayashi             5-20-1 Kamimizuhonmachi, Kodaira-shi, Tokyo Stock             Ceremony Company within Hitachi Semiconductor Group F-term (reference) 5J104 AA21 NA17

Claims (8)

[Claims] 1. A modular multiplication A * B * R ^ (-1) m for non-negative integers A, B and an n-bit odd number N.
od N or A * B * R ^ which is congruent with it N
(-1) modN + s * N (s is a non-negative integer, R = 2 ^ n, or less, X ^ Y
Represents the power of X to the power of Y), which is the process required when the value W of () is obtained by the method of Montgomery, where the integer M and the integer W that are equivalent to the remainder multiplication are the unknowns. Diophantine equation A * B +
In the process of obtaining W by sequentially obtaining M from k bits (k is a divisor of n) from the lower bits in M * N = W * R, in A * B of each k-bit block of A. Partial multiplication result j * B (j = 0, 1, 2, ..., 2 ^ k 1) and M * N multiplication result t * N (t = 0, 1, 2 , ...,
2 ^ k 1) and the combined table value TBL (j, t) = j * B + t
* N (j, t = 0, 1, 2, ..., 2 ^ k 1) is prepared, and (1) W + TBL (j, t) of the table value TBL (j, t) is used. A first process for selecting j, t such that the lower k bits are all 0, (2) W + TBL (j, t) for j, t defined in the first process
A second process for obtaining the value of (3) a value obtained by dividing the value of W + TBL (j, t) in the second process by 2 ^ k, or k bits equivalent to 2 ^ k When the right-shifted value is obtained, and this is the third process for updating the value with the next W, the first, second, and third processes are repeatedly executed in that order n / k times, The remainder multiplication result A * B * R ^ (-1)
A data processing device characterized by obtaining mod N + s * N. 2. The data processing apparatus according to claim 1, further comprising means for setting the value of a carry signal generated in the addition processing appearing in the first and second processings to 0. 3. The value TBL (j, t) = j * B + t * N in the table.
Instead of (j, t = 0, 1, 2, ..., 2 ^ k 1), the table value NTBL (j, t) = j * B + t * N (j, t = 0, 1, 2 , ..., 2 ^ k
1) is prepared as a value obtained by shifting TBL (j, t) to the right or in the lower direction by k bits, and the processing for performing the first processing on the original TBL is processing (A), Instead of the second process, when the lower k bits of W are all 0, the value obtained by shifting W to the right or lower by k bits is C (W, k).
If at least one of the lower k bits of W is 1 or more, W is shifted to the right or in the lower direction by k bits, and 1 is added to C (W, k). Then, the process of obtaining the value of C (W, k) + NTBL (j, t) for j, t determined in the process (A) is defined as process (B), and C (W, k) ) + NTBL (j, t)
When the process of updating the value of W as the next W is the process (C), the above processes (A), (B) and (C) are repeatedly executed in that order n / k times to obtain modular multiplication (modular multipli).
cation) A * B * R ^ (-1) mod N or congruent with mod N
The data processing apparatus according to claim 1, wherein a (congruent) A * B * R ^ (-1) mod N + s * N (s is a non-negative integer, R = 2 ^ n) is obtained. 4. The data processing apparatus according to claim 3, further comprising means for setting the value of the carry signal generated in the addition process appearing in the middle of the processes (A) and (B) to 0. 5. The data processing apparatus according to claim 1, wherein k is 2. 6. The data processing apparatus according to claim 3, wherein k is 2. 7. A polynomial A (X) having only 0 and 1 as coefficients,
B (X) and also an irreducible polynomial of degree n with only 0 and 1 in its coefficient and whose constant term is 1.
ial) F (X), modulo multiplication A (X) * B (X) * R (X) ^ (-1) mod F
(X) (however, R (X) = X ^ n) is a process required when the value of Montgomery's method is obtained. M (X), W (X) equivalent to the remainder multiplication are Indefinite equation with unknown polynomial
A (X) * B (X) + M (X) * F (X) = W (X) * R (X) In the process of obtaining the W (X), the M (X) is set to a low degree (degree). K terms
The W is obtained by sequentially obtaining for each (term) (k is a divisor of n).
(X), which is a partial multiplication result j (X) * B (X) of A (X) * B (X) for each k-term block of A (X) (or B (X)). (j (X)
Is a polynomial of order k-1 or less) and M (X) * F for each k-term block of M (X)
The table value TBL (j (X), t (X)) = j (combined with the multiplication result of (X) t (X) * F (X) (t (X) is a polynomial of degree k-1 or less) X) * B (X) +
Prepare t (X) * F (X) (j (X), t (X) is a polynomial of degree less than or equal to k-1), and (1) the table value TBL (j (X), t (X)) Using W
(X) + TBL (j (X), t (X)) The first process that selects j (X), t (X) so that all the coefficients less than or equal to the k-1th degree become 0, (2) For j (X), t (X) determined in the first processing, W (X) + TBL (j (X), t
(3) A second process for obtaining the value of (X), (3) A value obtained by dividing the value of W (X) + TBL (j (X), t (X)) in the second process by X ^ k Alternatively, a value obtained by right-shifting the value of W (X) + TBL (j (X), t (X)) by k bits is obtained, and this value is set as the next W (X) to be the third processing for updating the value. At this time, the remainder multiplication result A (X) * B (X) * R (X) ^ (-1) is obtained by repeatedly executing the first, second and third processes in that order n / k times. A data processing device for obtaining mod F (X), wherein the sum and product here are sums and products in Galois field GF (2 ^ n). 8. The TBL (j (X), t (X)) = j (X) * B (X) + t (X)
* F (X) (j (X), t (X) is a polynomial of degree less than or equal to k-1), instead of the table value NTBL (j (X), t (X)), TBL (j (X (X ), t (X)) values below the k-1 order are set to 0, and this is divided by X ^ k to prepare this, and the process (A) is performed on the original TBL. Processing (A '), C (W (X), k) is replaced by the processing (A'), and the part less than the k-1 order of W (X) is set to 0. As a polynomial divided by k, C (W (X), k) + NTBL (j (X), t (X) for j (X), t (X) determined in the process (A ') ) Processing the calculation of the sum value (B '), C (W (X), k) + NT
When the process of updating the value of BL (j (X), t (X)) as the next W (X) is the process (C '), the process (A'), (B ') and (C') By repeating n / k times in that order, the remainder multiplication (m
odular multiplication) A (X) * B (X) * R (X) ^ (-1) mod F
(X) or A (X) * congruent therewith in law F (X) *
B (X) * R (X) ^ (-1) mod F (X) + S (X) * F (X) (S (X) is any 0
8. The data processing device according to claim 7, wherein a polynomial having only 1 and 1 as a coefficient) is obtained, and the sum here is a sum in a Galois field GF (2 ^ n).