JP5179933B2 - Data processing device - Google Patents

Description

  The present invention relates to a data processing apparatus that executes a Fermat test, and relates to generation of prime numbers for a tamper resistant apparatus such as a highly confidential IC card.

  An IC card is an apparatus mainly used for holding information that cannot be rewritten without permission, encrypting data using an encryption key that is secret information, and decrypting a ciphertext.

  Since the IC card does not have a power source, when it is inserted into the reader / writer, it is supplied with power and becomes operable. When it becomes operable, it receives a command from the reader / writer and transfers data according to the command.

  In the IC card chip, programs and important information are sealed in the IC card chip, and such information cannot be directly accessed from the outside. Communication with the outside is performed entirely under the control of the IC card chip only through the I / O pins, and normal information is transmitted and received in an encrypted state, thereby realizing confidentiality of information. In order to perform encrypted communication, it is necessary to share an encryption key with a communicating party. There is a method of sharing the key with the communication partner in advance, but once the key is found, the encrypted communication content is decrypted. Therefore, there is a method in which an encryption key used for communication is randomly generated, the key is transmitted to the other party, and communication is performed using the key.

  When sending a key to the other party, if the key is sent in plaintext, the encrypted communication using that key will be easily deciphered next time. Therefore, public key cryptography is used. Public key cryptography is an encryption method in which the key used for encryption is different from the key used for decryption, and it is difficult to calculate the key used for decryption from the key used for encryption.

  In key exchange using the public key cryptosystem, you send your public key to the other party, and the other party generates a key to be used for communication encryption from random numbers, etc., encrypts it with the sent public key, and then encrypts it. Returns the converted key. The returned encryption key is decrypted with the private key corresponding to the public key sent to the other party and used for the next communication.

  The RSA encryption method is the most widely used public key encryption method. This encryption method is an encryption that utilizes the fact that a composite number that is a product of two large prime numbers cannot be easily factorized. The factorization itself can be obtained algorithmically by a trial division method, a number field sieve, or the like, but as the number increases, it becomes difficult to obtain the factor in terms of time. Currently, keys with a length of 1024 to 2048 bits are used. The key is generated by a computer outside the IC card, and the key of the public key cryptosystem is stored in the IC card by writing the generated key to the IC card.

  This method has a problem that, in principle, a secret key for public key cryptography exists outside the IC card, and security cannot be secured unless the secret key can be properly managed. Thus, a private key / public key pair for public key cryptography has been generated inside the IC card. As a result, although security is improved, RSA encryption key generation is a time-consuming process to be performed by an IC card, and it is necessary to increase the speed. The process that takes the most time for generating the RSA encryption key is a process for generating two large prime numbers. Prime number generation is realized by generating an odd random number, determining whether the next generated random number is a prime number, and if it is not a prime number, generate a new prime number and repeat the process of determining the prime number Has been.

  Various methods are used for prime number determination, but the method of performing the first prime number determination by Fermat test based on 2 and applying the passed random number to the more exact prime number determination processing is suitable for speeding up. ing. This is because doubling can be performed by shift.

  However, depending on whether the exponent part is 1 or not, there is a possibility that a prime number which is secret information may be estimated by estimating a difference in processing such as presence / absence of remainder multiplication from a difference in power consumption. It was.

As a method for performing the Fermat test securely at high speed, there is an m-ary method (also referred to as a window method) described in Non-Patent Document 1, in which exponents are processed m bits at a time. In the m-ary method, the exponent part is divided every m [bit], and m times of modular multiplication and 1 time of modular multiplication are performed for each section. When the number of bits of the exponent is n [bits], it is necessary to perform n modular multiplication and n / m modular multiplication. The procedure of the m-ary method in the case of calculating ^xy mod N is shown. Here, e [i] is a value obtained by dividing y every m bits, and when J is the smallest integer such that J ≧ n / m, (Equation 1)
y = 2 ^{(J-1) m} · e [J-1] +2 ^{(J-2) m} · e [J-2] +... +2 ^m · e [1] + e [0] (Formula 1)
Meet. The procedure of the m-ary method is, for example,
result: = 1;
for i: = J-1 downTo 0 do
for j: = 1 to m do
result: = result ² mod N
end for
result: = result * x ^ (e [i]) mod N
end for
return result
It is said.

In this method, there is no difference in the processing contents according to the bit pattern, and by increasing the value of m, the number of remainder multiplications required for processing decreases in inverse proportion to m. However, since it is necessary to calculate in advance values from x ^ 1 to x ^ (2 ^m -1), there is a problem that increasing ^m increases the work area in proportion to 2 ^m . . This becomes a big bottleneck particularly in an IC card with a limited RAM size.

  Although it is conceivable that the value of x ^ (e [i]) is dynamically calculated when it becomes necessary, a coprocessor using a Montgomery remainder multiplication algorithm (Non-patent Document 2) often used particularly in an IC card. However, since it is necessary to convert from normal numerical expression to Montgomery expression multiplied by 2 ^ n mod N, there is a problem that dynamically calculating the number of operations of remainder multiplication causes a decrease in speed.

Alfred J. et al. Menezes, Paul C.M. van Oorschot and Scott A. Vanstone, “HANDBOOK of APPLYED CRYPTOGRAPHY”, CRC Press, pp. 615-616, ISBN 0-8493-8523-7, (1997) Darrel Hankerson, Alfred Menezes and Scott Vanstone, “Guide to Elliptic Curve Cryptography”, Springer, pp. 38, ISBN 0-387-95273-X, (2004)

  To generate an RSA encryption key at high speed, it is necessary to generate primes at high speed. However, when it is necessary to perform prime number determination at high speed with the conventional method, speed and storage capacity are in a trade-off relationship. It was difficult to increase the speed of memory with an IC card.

  An object of the present invention is to provide a data processing apparatus capable of performing prime number determination by Fermat test at high speed without consuming memory capacity.

  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.

  The following is a brief description of an outline of typical inventions disclosed in the present application.

That is, according to the present invention, when the bit length of the coprocessor is n, m is the maximum integer satisfying m ≦ log ₂ (n), and an exponent is processed for each m bits. Reduce the number of remainder multiplications and increase the speed. Further, in the m-ary method, it is necessary to pre-calculate 2 ^m −1 types of values from x ¹ to x ^{2 ^ m−1} in advance and store them in a memory. In the present invention, x = 2. To increase the required storage capacity by dynamically generating the number of operations used for remainder multiplication during processing and eliminating the need for pre-calculation and storage capacity to store pre-calculated values. It aims to realize high speed. In this specification, the symbol ^ means a power operation, and the symbol · means a multiplication operation.

When the remainder multiplication is performed by the Montgomery processor, it is necessary to use a value obtained by remainder multiplication of R (= 2 ⁿ mod N) to a power of 2. R is also a power number of 2, but since it is a value larger than the modulus N, it becomes a complicated bit pattern, and it is necessary to perform pre-calculation or multiply R ² mod N every time a remainder multiplication is performed. Here, e [i] is a value obtained by dividing (N−1) every m bits, and when J is the smallest integer such that J ≧ n / m (Expression 2)
N-1 = 2 ^{(J-1) m} · e [J-1] +... +2 ^m · e [1] + e [0] (Formula 2)
Shall be satisfied.

A processing algorithm for calculating 2 ^N−1 mod N by a method of multiplying R ² mod N for each remainder multiplication using a Montgomery remainder multiplication coprocessor is as follows:
result: = R mod N
for i: = J-1 downTo 0 do
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
result: = result · 2 ^{e [i]} · R ⁻¹ mod N
result: = result · R ² · R ⁻¹ mod N
end for
result: = result · 1 · R ⁻¹ mod N
return result
It is.

Even with the method of multiplying by R ² mod N, the number of multiplications can be reduced to 2 · n / m times without increasing the required memory capacity. However, when the exponent is handled every m bits by the m-ary method, Compared with n / m times, the number of times of remainder multiplication is doubled.

To solve this problem, from which R is multiplied by each operand and operands of modular multiplication, consider a method of multiplying the R ² only operands of one. By doing so, the value to be multiplied becomes Hamming weight 1, and no prior calculation is required. However, if the value is multiplied as it is, the result after the remainder multiplication is simply multiplied by R. Prior to the remainder calculation of the power-residue, the fact that the remainder is multiplied m times is used, and the correction value is multiplied at the time of the remainder multiplication so that the result of the remainder is multiplied by R ^2. .

In order to multiply the operand by R ² = 2 ²ⁿ when performing modular multiplication, the operand after multiplication is multiplied by 2 ^n, so that 2 after m modular multiplication. ^What is necessary is just to multiply the value which becomes ⁿ . And ^{2 n} being multiplied already, together with ^{2 n} to be multiplied by an ^{additional, 2 2n} is multiplied constantly. Therefore, the following equation (3)
a ^ (2 ^m ) = 2 ⁿ (Formula 3)
The correction value a satisfying the above may be multiplied.

This is easy to solve,
a = 2 ^ (n / (2 ^m )) (Formula 4)
Where a is given. When n is a power number of 2, since 2 ^m = n from the definition of ^m , a = 2 immediately (formula 5)
Is obtained.

On the other hand, if n is not a power of 2,
a = 2 · 2 ^ (n · (2 ^m ) −1) (Formula 6)
Since 2 ^{(n / (2 ^ m) -1)} is not an integer, it cannot be used as a correction value as it is. Therefore, the correction is divided into a part a ′ performed before m times of modular multiplication and a part b performed after m times of modular multiplication. Here, a ′ = 2. That is, the correction is performed by 2 before the modular multiplication, and the corrected value after the modular multiplication is expressed as (Equation 7).
b = (2 ^ (n / ( ^2m ) -1)) ^ ( ^2m ) (Formula 7)
Consider b that satisfies

According to the power law, b is
b = 2 ^ (n- ^2m ) (Formula 8)
It becomes. Therefore, the correction value a ′ · b when n is not a power of 2 is
a ′ · b = 2 · 2 ^ (n−2 ^m ) = 2 ^ (1 + n−2 ^m ) (Formula 9)
It becomes. When n is a power number of 2, since n−2 ^m = 0, (Equation 9) is equal to (Equation 5). Further, in (Expression 7), b = 1.

In the remainder multiplication in which N−1 is divided every m bits, 2 ^ (e [i]), which is a power of 2 with the correction value of (Equation 9) and the value obtained by dividing the exponent every m bits as an exponent. 2 ^ (e [i] + 1 + n- ^2m ) which is the product (Formula 10)
Will be multiplied. Since e [i] is an m-bit value, the maximum value is 2 ^m −1. Substituting this value into (Equation 10) yields 2 ⁿ . This is a value of n + 1 bit length, which exceeds the bit length n of co-pro. Such bit overflow occurs only when e [i] is 2 ^m −1 which is the maximum value, otherwise, the value of (Equation 10) is less than 2 ⁿ and is a value of n bits or less. Therefore, calculation can be performed with an n-bit coprocessor.

Therefore, when the value of e [i] is 2 ^m −1, R mod N is used as the number of operations, and when the value of e [i] is less than 2 ^m −1, the number of operations is represented by (Equation 10). 2 ^ (e [i] + 1 + n−2 ^m ) is used.

In the first step of the calculation, the number of operands is initialized with R ² mod N in advance, so that the correction value b is not necessary. Therefore, in the first step of processing the top of the exponent, it is determined whether or not the value of e [i] +1 is equal to 2 ^n, and if so, R mod N is used as the number of operations and less than 2 ⁿ In this case, 2 ^ (e [i] +1) is used. If n is not a power of 2, e [i] +1 is always less than 2 ⁿ , so if it is known in advance that n is not a power of 2, then the first e [i] +1 is 2 ⁿ It is not necessary to check whether or not the same.

When performing computation by Montgomery modular multiplication, it is necessary to remove R from the final result. Usually, by performing Montgomery modular multiplication with ¹ , R- ¹ is multiplied to return to the normal expression.

In the present invention, since R ² is multiplied by the result, correction is performed modulo multiplication of the last two. First, when processing the second e [1] from the end, correction for multiplying R ^{2 in} the next remainder multiplication is unnecessary, and a ′ · What is necessary is just to multiply the correction value of only b of b. Therefore, as the number of operations,
2 ^ (e [1] + n- ^2m ) (Formula 11)
Multiply The value of e [1] + n-2 ^ m , since always less than ^{2 n,} no comparison with the ^{2 n} need. After multiplying this value, if m square operations are performed, the number of operands is multiplied by R, so when processing the last lowest exponent e [0],
2 ^ (e [0]) (Formula 12)
By multiplying, the final result is not a Montgomery form, but a normal numerical expression. When the above procedure is expressed as an algorithm,
result: = R ² mod N
if e [J-1] +1 <2 ⁿ then
result: = result · 2 ^ (e [i] +1) · R ⁻¹ mod N
else
result: = result · (R mod N) · R ⁻¹ mod N
end if
for i: = J-2 downTo 2 do
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
if e [i] + 1 + n-2 ^m <2 ⁿ then
result: = result · 2 ^ (e [i] + 1 + n−2 ^m ) · R ⁻¹ mod N
else
result: = result · (R mod N) · R ⁻¹ mod N
end if
end for
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
result: = result · 2 ^ (e [1] + n−2 ^m ) · R ⁻¹ mod N
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
result: = result · 2 ^ (e [0]) · R ⁻¹ mod N
return result
It can be expressed as.

In addition, the number of operations shown in (Equation 11) has a Hamming weight of 1, and the Montgomery remainder multiplication co-pro is normally operated from the lower side, so that the portion where the number of operations is 0 is processed. There is a possibility that current consumption is greatly increased in a portion where the current ground is small and the bit is 1. In that case, it is possible to estimate the index value to some extent by measuring the current consumption. In order to solve such a problem, the fact that the operation is a modular multiplication modulo N and the fact that a modular multiplication is performed after the modular multiplication is used, the number of operations is replaced with the value of (Equation 11). ,
N ± 2 ^ (e [i] + 1 + n- ^2m ) (Formula 13)
Can be used. However, in (Equation 13), carry due to addition / subtraction occurs, and there is a possibility that a delay due to carry transmission or overflow due to the occurrence of carry from the most significant bit may occur. there,
N xor 2 ^ (e [i] + 1 + n−2 ^m ) (Formula 14)
By using this form, no carry occurs. (Equation 14) is equivalent to performing either addition or subtraction depending on whether the bit of the (e [i] + 1 + n−2 ^m ) bit of N is 1 or 0, and the corresponding bit of N is 1 Is subtracted, and if the corresponding bit of N is 0, addition is performed. In the exclusive OR (xor) operation, carry propagation does not occur, there is no delay associated with carry propagation, and the circuit can be small.

When the transformation according to (Equation 14) is performed, the Hamming weight of the number of operations is approximately half the bit length, and tamper resistance is enhanced compared to the attack method using current consumption. When the procedure that introduces the transformation of (Equation 14) is expressed as an algorithm,
result: = R ² mod N
if e [J-1] +1 <2 ⁿ then
result: = result · (N xor 2 ^ (e [J−1] +1)) · R ⁻¹ mod N
else
result: = result · (R mod N) · R ⁻¹ mod N
end if
for i: = J-2 downTo 2 do
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
if e [i] + 1 + n-2 ^m <2 ⁿ then
result: = result · (N xor 2 ^ (e [i] + 1 + n−2 ^m )) · R ⁻¹ mod N
else
result: = result · (R mod N) · R ⁻¹ mod N
end if
end for
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
result: = result · 2 ^ (e [1] + n−2 ^m ) · R ⁻¹ mod N
for j: = 1 to m do
result: = result ² · R ⁻¹ mod N
end for
result: = result · 2 ^ (e [0]) · R ⁻¹ mod N
return result
It can be expressed as.

  According to this procedure, a Fermat test based on 2 can be implemented at high speed using Montgomery modular multiplication co-pro.

A similar method can be used even when a remainder multiplication coprocessor using a normal expression that is not the Montgomery remainder multiplication method is used. In the remainder multiplication coprocessor using the normal expression, no correction value is required for the number of operations.
N xor 2 ^ (e [i]) (Formula 15)
Is used as the number of operations.

The modification of the number of operations of the remainder multiplication expressed by (Equation 14) is based on the premise that the sign of a negative value becomes positive by the remainder multiplication after the remainder multiplication. Therefore, the least significant m bits, that is, e [0 ] Cannot be used. Therefore, in the case of e [0], the transformation of (Equation 14) is not performed. When the above procedure is expressed as an algorithm,
result: = N xor 2 ^ (e [J-1])
for i: = J-2 downTo 1 do
for j: = 1 to m do
result: = result ² mod N
end for
result: = result · (N xor 2 ^ (e [i])) mod N
end for
for j: = 1 to m do
result: = result ² mod N
end for
result: = result · 2 ^ (e [0]) mod N
return result
It can be expressed as.

  By using the above procedure, it is possible to perform prime number determination by performing a Fermat test at high speed without consuming a memory capacity, regardless of whether a Montgomery type remainder multiplier or a remainder multiplier is used.

  The effects obtained by the representative ones of the inventions disclosed in the present application will be briefly described as follows.

  That is, it is possible to provide a data processing apparatus that can perform prime number determination by a Fermat test at high speed without consuming memory capacity.

1. First, an outline of a typical embodiment of the invention disclosed in the present application will be described. Reference numerals in the drawings referred to in parentheses in the outline description of the representative embodiments merely exemplify what are included in the concept of the components to which the reference numerals are attached.

[1] A data processing apparatus according to the present invention (FIGS. 1, 7, 9, 10, and 11) includes a coprocessor including a Montgomery residue multiplier that performs Montgomery residue multiplication, a program, A central processing unit that controls the processor, and by processing data under the control of the central processing unit, 2 ^(N-1) mod N is calculated for a prime number candidate N given from the outside. Run the Fermat test. The data processing is
Storing the prime candidate N;
A process of storing a bit length n of N;
processing to calculate and store the largest integer m not exceeding log ₂ (n) (step 7010 in FIG. 9);
When N-1 is calculated from the prime candidate N and J is the smallest integer such that J ≧ n / m (step 7020 in FIG. 9), (N−1) is set every m bits from the least significant bit. Dividing into J sections, (N−1) = 2 ^{(J−1) m} · e [J−1] +2 ^{(J−2) m} · e [J−2] +... +2 ^m · e [1] Exponential part cutout processing for dividing (N−1) into partial exponents e [0], e [1],..., E [J−1] so as to satisfy the expression + e [0] (Step 7030 in FIG. 9) ),
A power-of-two generation process for generating 2 ^ (e [i] + 1 + n−2 ^m ) from the m-bit value e [i] cut out by the exponent part cut-out process (part of step 7060 in FIG. 9);
When e [J-1] +1, which is obtained by adding 1 to the highest value of the partial exponent extracted by the exponent segmentation processing, is equal to 2 ⁿ (step 7050 in FIG. 9), R mod N = 2 ⁿ mod A first process of performing Montgomery residue multiplication on the prime candidate N modulo the operation result of N and the operation result of R ² mod N = 2 ²ⁿ mod N and storing the operation result in a first storage area; Step 7070 in FIG.
When e [J-1] +1 is less than 2 ^{n, the} calculation of 2 ^ (e [J-1] +1) calculated by the power-of-two generating unit and R ² mod N = 2 ²ⁿ mod N A second process for performing Montgomery modular multiplication on the result modulo N and storing the calculation result in the first storage area (step 7060 in FIG. 9);
A third process in which an internal state variable i is set to J-2 after either the first process or the second process (step 7080 in FIG. 9);
After the third process, the prime candidate N is used as a modulus, and the operation of performing the Montgomery modular multiplication of the values stored in the first storage area and writing the calculation result back to the first storage area is repeated m times. The fourth process (step 7090 in FIG. 10);
After the fourth process, when the partial index e [i] cut out by the exponent part cut-out process is less than 2 ^m −1 (step 7100 in FIG. 10), it is generated by the power-of-two generation process. Montgomery modular multiplication modulo N of 2 ^ (e [i] + 1 + n−2 ^m ) and the value stored in the first storage area is performed, and the calculation result is stored in the first storage area The fifth process (step 7110 in FIG. 10);
After the fifth process, a value obtained by subtracting 1 from the internal state variable i is stored in the internal state variable i (step 7130 in FIG. 10). If the value of i is 2 or more, the fourth process is performed. Return, and repeat the process until the value of i becomes 1 or less,
After the sixth process, the prime candidate N is used as a modulus, and the operation of performing the Montgomery remainder multiplication of the values stored in the first storage area and writing the calculation result in the first storage area is repeated m times. 7 processing (step 7150 in FIG. 11),
After the seventh process, the prime candidate N of 2 ^ (e [1] + n-2 ^m ) calculated by the power-of-two generation process and the value stored in the first storage area is modulo An eighth process of performing a Montgomery modular multiplication and storing the calculation result in the first storage area (step 7160 in FIG. 11);
After the eighth processing, the Montgomery residue multiplication device modulo the prime candidate N, performs Montgomery residue multiplication between the values stored in the first storage area, and stores the calculation result in the first storage area. A ninth process of repeating the storing operation m times (step 7170 in FIG. 11);
After the ninth process, the Montgomery residue modulo the prime candidate N between 2 ^ (e [0]) calculated by the power-of-two generation process and the value stored in the first storage area And a tenth process of performing multiplication (step 7180 in FIG. 11) and outputting the calculation result as a Fermat test result.

  [2] The data processing apparatus according to item 1, further including a memory storing the program, formed on one semiconductor substrate.

[3] A data processing apparatus (FIGS. 4, 7, 12, 13, and 14) according to another aspect executes a program, a coprocessor including a Montgomery residue multiplier for performing Montgomery residue multiplication, A central processing unit that controls the processor, and by processing data under the control of the central processing unit, 2 ^(N-1) mod N is calculated for a prime number candidate N given from the outside. Run the Fermat test. The data processing is
Storing the prime candidate N;
A process of storing a bit length n of N;
processing to calculate and store the largest integer m not exceeding log ₂ (n) (step 7010 in FIG. 12);
When N−1 is calculated from the prime candidate N and J is set to the smallest integer satisfying J ≧ n / m (step 7020 in FIG. 12), (N−1) is set every m bits from the least significant bit. Dividing into J sections, (N−1) = 2 ^{(J−1) m} · e [J−1] +2 ^{(J−2) m} · e [J−2] +... +2 ^m · e [1] Exponential part cutout processing for dividing (N−1) into partial exponents e [0], e [1],..., E [J−1] so as to satisfy the expression + e [0] (step 7030 in FIG. 12). ),
From the m-bit value e [i] cut out by the exponent part cut-out process, 2 ^ (e [i] + 1 + n−2 ^m ).
Generating a power of 2 to generate
When e [J−1] +1, which is obtained by adding 1 to the highest value of the partial exponent extracted by the exponent segmentation process, is equal to 2 ⁿ (step 7050 in FIG. 12), R mod N = 2 ⁿ mod The Montgomery remainder multiplication is performed on the prime candidate N modulo the operation result of N and the operation result of R ² mod N = 2 ²ⁿ mod N (step 7070 in FIG. 12), and the operation result is stored in the first storage area. A first process stored in
When e [J-1] +1 is less than 2 ⁿ , an exclusive OR of 2 ^ (e [J-1] +1) calculated by the power-of-two generating means 2 and the prime candidate N (see FIG. 4 and 3032) and the operation result of R ² mod N = 2 ²ⁿ mod N is subjected to Montgomery modular multiplication modulo N, and the operation result is stored in the first storage area. 2 processing (step 8060 in FIG. 12),
A third process in which the internal state variable i is set to J-2 after either the first process or the second process (step 7080 in FIG. 12);
After the third processing, the prime candidate N is used as a modulus, and Montgomery modular multiplication of the values stored in the first storage area is performed, and the operation result of storing the four calculation results in the first storage area is m times. A fourth process to repeat (step 7090 in FIG. 12);
After the fourth process, when the partial index e [i] cut out by the exponent part cut-out process is less than 2 ^m −1 (step 7100 in FIG. 13), it is generated by the power-of-two generation process. 2 ^ (e [i] + 1 + n−2 ^m ) and the value obtained by the exclusive OR (3032 in FIG. 4) of the prime candidate N and the value stored in the first storage area A fifth process of performing Montgomery modular multiplication modulo the prime candidate N (step 8110 in FIG. 13) and storing the calculation result in the first storage area;
After the fourth process, when the partial index e [i] cut out by the exponent part cutout process is equal to 2 ^m −1, the R mod N = 2 ⁿ mod N is stored in the first storage area. A sixth process of performing a Montgomery residue multiplication modulo the prime candidate N with the obtained value (step 7120 in FIG. 13) and storing the calculation result in the first storage area;
After either one of the fifth process and the sixth process, a value obtained by subtracting 1 from the internal state variable i is stored in the internal state variable i (step 7130 in FIG. 13), and the value of i is 2 In the above case, the process returns to the third process (step 7140 in FIG. 13), and repeats until the value of i becomes 1 or less,
After the seventh process, the prime candidate N is used as a modulus, and the operation of performing Montgomery modular multiplication of the values stored in the first storage area and storing the calculation result in the first storage area is repeated m times. 8 processing (step 7150 in FIG. 14),
After the eighth process, the prime candidate N of 2 ^ (e [1] + n-2 ^m ) generated by the power-of-two generation process and the value stored in the first storage area is modulo A ninth process for performing a Montgomery residue multiplication and storing the calculation result in the first storage area (step 7160 in FIG. 14);
After the ninth process, the prime candidate N is used as a modulus, and the operation of performing Montgomery modular multiplication of the values stored in the first storage area and storing the calculation result in the first storage area is repeated m times. The tenth process (step 7170 in FIG. 14);
After the tenth processing, Montgomery modular multiplication is performed modulo N of 2 ^ (e [0]) generated by the power-of-two generation processing and the value stored in the first storage area. (Step 7180 in FIG. 14), and an eleventh process for outputting the calculation result as a Fermat test result.

  [4] The data processing apparatus according to item 3, further including a memory storing the program, formed on a single semiconductor substrate.

[6] A data processing apparatus (FIGS. 3, 7, 12, 13, and 14) according to another aspect executes a program, a coprocessor having a Montgomery residue multiplier for performing Montgomery residue multiplication, A central processing unit that controls the processor, and by processing data under the control of the central processing unit, 2 ^(N-1) mod N is calculated for a prime number candidate N given from the outside. Run the Fermat test. The data processing is
Storing the prime candidate N;
A process of storing a bit length n of N;
processing to calculate and store the largest integer m not exceeding log ₂ (n) (step 7010 in FIG. 12);
When N−1 is calculated from the prime candidate N and J is set to the smallest integer satisfying J ≧ n / m (step 7020 in FIG. 12), (N−1) is set every m bits from the least significant bit. Dividing into J sections, (N−1) = 2 ^{(J−1) m} · e [J−1] +2 ^{(J−2) m} · e [J−2] +... +2 ^m · e [1] Exponential part cutout processing for dividing (N−1) into partial exponents e [0], e [1],..., E [J−1] so as to satisfy the expression + e [0] (step 7030 in FIG. 12). ),
2 power generation processing for generating 2 ^ (e [i] + 1 + n−2 ^m ) from the m-bit value e [i] cut out by the exponent part cut-out processing;
When e [J−1] +1, which is obtained by adding 1 to the highest value of the partial exponent extracted by the exponent segmentation process, is equal to 2 ⁿ (step 7050 in FIG. 12), R mod N = 2 ⁿ mod Montgomery modular multiplication modulo the prime candidate N of the operation result of N and the operation result of R ² mod N = 2 ²ⁿ mod N is performed (step 7070 in FIG. 12), and the operation result is stored in the first storage area. A first process to store;
When e [J-1] +1 is less than ^2n, a value obtained by inverting the value of the e [J-1] +1 bit of N by a designated bit inverter (3020) and the R ² mod N = 2 ^A second process of performing a Montgomery remainder multiplication modulo the prime candidate N with the ²ⁿ mod N operation result and storing the operation result in the first storage area (step 8086 in FIG. 12);
A third process in which the internal state variable i is set to J-2 after either the first process or the second process (step 7080 in FIG. 12);
After the third process, the prime candidate N is used as a modulus, and Montgomery modular multiplication of the values stored in the first storage area is performed and the operation result is stored m times in the first storage area. The fourth process (step 7090 in FIG. 13),
When the partial index e [i] cut out by the exponent part cut-out process after the fourth process is less than 2 ^m −1 (step 7100 in FIG. 13), the e [i] + 1 + n−2 ^{m of} N A Montgomery residue multiplication is performed on the prime candidate N modulo the value obtained by inverting the value of the bit by the designated bit inverter (3020) and the value stored in the first storage area, and the operation result is obtained as the first result. A fifth process for storing in one storage area (step 8110 in FIG. 13);
When the partial index e [i] cut out by the exponent part cutout process after the fourth process is equal to 2 ^m −1, the calculation result of the R mod N = 2 ⁿ mod N and the first storage area A sixth process of performing a Montgomery residue multiplication modulo the prime candidate N with the value stored in the value and storing the calculation result in the first storage area (step 7120 in FIG. 13);
After one of the fifth process and the sixth process, a value obtained by subtracting 1 from the internal state variable i is stored in the internal state variable i (step 7130 in FIG. 13). In the case of 2 or more, the process returns to the third process (step 7140 in FIG. 13), and the seventh process is repeated until the value of i becomes 1 or less,
After the seventh process, the prime candidate N is used as a modulus, the Montgomery modular multiplication of the values stored in the first storage area is performed, and the operation of storing the calculation result in the first storage area is repeated m times. The eighth process (step 7150 in FIG. 14);
After the eighth process, modulo the prime candidate N between 2 ^ (e [1] + n-2 ^m ) calculated by the power-of-two generating means and the value stored in the first storage area A ninth process for performing a Montgomery modular multiplication and storing the calculation result in the first storage area (step 7160 in FIG. 14);
After the ninth process, the prime candidate N is used as a modulus, and the operation of performing Montgomery modular multiplication of the values stored in the first storage area and storing the calculation result in the first storage area is repeated m times. The tenth process (step 7170 in FIG. 14);
After the tenth processing, the Montgomery residue modulo the prime candidate N between 2 ^ (e [0]) generated by the power-of-two generation processing and the value stored in the first storage area A data processing apparatus including an eleventh process of performing multiplication (step 7180 in FIG. 14) and outputting the calculation result as a Fermat test result.

  [6] The data processing apparatus according to item 5 further includes a memory storing the program, and is formed on one semiconductor substrate.

2. Details of Embodiments Embodiments will be further described in detail. DESCRIPTION OF EMBODIMENTS Hereinafter, embodiments for carrying out the present invention will be described in detail with reference to the drawings. Note that components having the same function are denoted by the same reference symbols throughout the drawings for describing the embodiments for carrying out the invention, and the repetitive description thereof will be omitted.

<< First Embodiment >>
FIG. 1 shows a functional block diagram of a data processing apparatus 1 according to the present invention that executes a Fermat test, and implements the Fermat test high-speed calculation procedure according to the present invention shown in FIGS. The data processor 1 executes a program together with the Montgomery multiplier coprocessor (6040) including the Montgomery remainder multiplier (6050) and the arithmetic registers (6060, 6070, 6080) illustrated in FIG. A central processing unit (6010) for controlling the processor 6040 and the like, a memory (6020) and the like are connected to each other via a bus 6030. The memory (6020) includes an electrically rewritable nonvolatile memory for storing a program (PGM) and a random access memory such as an SRAM used for storing variables, data (DAT), and the like. The data processing apparatus 1 is realized, for example, as an IC card microcomputer 107 formed on one semiconductor substrate as shown in FIG. In FIG. 17, the IC card microcomputer 107 is mounted on the IC card substrate 108. The IC card microcomputer 107 stores programs and important information in an on-chip memory, and cannot directly access such information from the outside. It is like that. Communication with the outside is performed entirely under the control of the IC card chip only through the I / O pin (106), and normal information is transmitted and received in an encrypted state, thereby realizing information confidentiality. . In order to perform encrypted communication, it is necessary to share an encryption key with a communicating party. There is a method of sharing the key with the communication partner in advance, but once the key is found, the encrypted communication content is decrypted. Therefore, a method is generally used in which an encryption key used for communication is randomly generated, the key is transmitted to the other party, and communication is performed using the key. As external interface terminals, a Vcc pin 101, a reset pin 102, a clock input pin 103, a ground pin 104, a nonvolatile memory program power supply pin 105, and an I / O pin 106 are provided.

  The IC card microcomputer 107 has a function of generating an encryption key to be used for encryption communication by using limited calculation resources such as an on-chip memory. A prime number having a large number of bits is used for the encryption key, and a first example of arithmetic processing for determining the prime number will be described.

In FIG. 1, the modulus register N (1000) receives and stores a prime number candidate N from the outside, and the bit n register (1010) inputs and stores the bit number n of the prime number candidate N from the outside. The log ₂ largest log ₂ computing device that provides an integer not exceeding (n) (1030), the maximum integer m not exceeding _log 2 (n) of is obtained. Since the type of the value output by 1030 is log ₂ (maximum value of n), the table is not actually calculated, and it is obtained from the position of the most significant bit among the non-zero bits of n. be able to. For example,
n0: = n
m: = 0
while n0> 1
m: = m + 1
n0: = n0 >> 1
end while
It is good. This process corresponds to step 7010 in FIG. M obtained in 1030 is stored in a register (1020) for storing m. A value obtained by rounding up the decimal point of n / m is obtained by the integer divider (1040), the output of 1040 is selected by the selector (1050), and set to the counter i (1060). This process corresponds to step 7020 in FIG. The counter i is used to designate the (N−1) th partial bits to be extracted every m bits. On the other hand, R ² mod N = 2 ²ⁿ mod N is calculated by the computing unit (1100) and stored in the result register (1160). In FIG. 1, the storage path is not shown. This process corresponds to step 7040 in FIG. "Result" in FIG. 9 means the result register '1160). Next, R mod N = 2 ⁿ mod N is calculated and stored in the register (1110). This process corresponds to the preparation of RmodN used in step 7070 of FIG. According to the value of i, the exponent cutout unit (1080) cuts out the most significant of (N−1), and the operation number generation device (1090) generates 2 ^ (e [i] +1). Next, the comparator (1130) compares the value of the 2 ^m -1 generator (1120), which produces a value in which all bits of the m-bit length value are 1, and the exponent extracted by 1090, If they are equal, the selector (1140) selects the register (1110), and if not, the output of the operation number generator (1090) is selected. The Montgomery remainder multiplier (1150) performs Montgomery remainder multiplication between the value of the result register (1160) and the value selected by the selector (1140) and stores the result in the result register (1160). This process corresponds to steps 7050, 7060, and 7070 in FIG. The value of the counter i (1060) is decremented by the subtracter (1070), the decremented result is selected by the selector (1050), and the counter i (1070) is updated. This process corresponds to Step 7080 in FIG.

The Montgomery residue multiplication operation mode control unit (1200) then changes the operation mode of the Montgomery residue multiplier (1150) to double multiplication, and initializes the counter j (1180) via the selector (1170). The Montgomery remainder multiplication operation mode control unit (1200) uses the Montgomery remainder multiplier (1150) to decrement the value of the result register (1160) every time the counter j (1180) is decremented once by the subtracter (1190). Is multiplied by the Montgomery remainder and stored in the result register (1160) until the counter j (1180) becomes zero. This corresponds to Step 7090 in FIG. Next, according to the value of the counter i (1060), the exponent cutout unit (1080) cuts out the partial bits of (N−1) and compares them with 2 ^m −1 by the comparator (1130). Based on the comparison result, the selector (1140) selects the output of the operation number generator (1090) or the register (1110) storing R mod N, and performs the remainder multiplication with the value of the result register (1160). This corresponds to the processing of steps 7100, 7110, and 7120 in FIG. When the remainder multiplication is completed, the value of the counter i (1060) is decremented by the computing unit (1070). When the value of the counter i (1060) is 1 or more, the processing is repeated from the processing corresponding to step 7090 in FIG.

  When the value of the counter i (1060) is 1, the operation mode of the Montgomery remainder multiplier (1150) is changed to double multiplication, and the counter j (1180) is initialized via the selector (1170). The Montgomery remainder multiplication operation mode control unit (1200) uses the Montgomery remainder multiplier (1150) to decrement the value of the result register (1160) every time the counter j (1180) is decremented once by the subtracter (1190). Is multiplied by the Montgomery remainder and stored in the result register (1160) until the counter j (1180) becomes zero. This corresponds to step 7150 in FIG.

  Next, according to the value of the counter i (1060), the exponent mute unit (1080) extracts the second m bits from the least significant bit of (N-1). When the counter i (1060) is 1, the operation number generation device (1090) is always selected, and the value of the result register (1160) is subjected to modular multiplication. This corresponds to the processing of step 7160 in FIG. When the modular multiplication is completed, the value of the counter i (1060) is decremented by the calculator (1070) and set to the counter i (1060).

  The operation mode of the Montgomery remainder multiplier (1150) is changed to double multiplication, and the counter j (1180) is initialized via the selector (1170). The Montgomery remainder multiplication operation mode control unit (1200) uses the Montgomery remainder multiplier (1150) to decrement the value of the result register (1160) every time the counter j (1180) is decremented once by the subtracter (1190). Is multiplied by the Montgomery remainder and stored in the result register (1160) until the counter j (1180) becomes zero. This corresponds to Step 7170 in FIG.

  Finally, according to the value of the counter i (1060), the exponent cutout unit (1080) extracts the least significant m bits of (N−1). When the counter i (1060) is 0, the operation number generation device (1090) is always selected, and the value of the result register (1160) and the remainder multiplication are performed. This corresponds to the processing in step 7180 in FIG. When the remainder multiplication is completed, the value 2 ^ (N-1) mod N is stored in the result register (1160), and the process is terminated.

FIG. 2 shows details of a computing unit (1100) for calculating R ² mod N. When the modulus N (1000) and the bit length n (1010) are input to the computing unit (1100), 2RmodN is calculated by the computing unit (2010). Here, 2R = ^{2n + 1} . N is left-bit shifted until the n-th bit becomes 1, and the value of N shifted left from 2 ^{n + 1} is subtracted and stored in the 2RmodN register (2020). Since N is an odd number because it is a prime number candidate, the n-1th bit or less always includes a non-zero bit. Therefore, since the value obtained by shifting N to the left is greater than 2 ^n, the result of subtracting the value of N shifted left from 2 ^{n + 1} is a value smaller than 2 ⁿ . If the value stored in 2RmodN (2020) is less than ^2n, it is not necessary to accurately calculate modN.

2 ⁿ -N = R is assigned to the 2 ^S modN register (2060). R is equivalent to 1 in Montgomery modular multiplication. Value stored in 2RmodN register (2020) ^is equivalent to t = 1 when expressed as 2 t RmodN. When the Montgomery remainder double multiplication is performed once using the Montgomery remainder multiplier, t is doubled. After performing Montgomery modular multiplication, the result is stored in the operation number register (2030). Since R ² modN is equal to 2 ⁿ RmodN, in ^order to calculate R ² modN, Montgomery modular multiplication is performed, and whenever t changes, the logical product (AND) of t and n is taken, If it is not zero, the operation number 2030 and the 2 ^S mod ^N register 2060 are input, the Montgomery remainder multiplier 2050 performs the remainder multiplication, and the result is stored in the 2 ^S mod ^N register 2060. Do. Then, again performs value process of Montgomery modular squaring the operand register (2030), taking the AND of the values of t and n, if non-zero, operand (2030) and ² S modN register (2060) , The Montgomery remainder multiplier (2050) performs the remainder multiplication, and stores the result in the 2 ^S modN register (2060) until 2t> n. When this process ends, R ² modN is stored in the 2 ^S modN register (2060).

<< Second Embodiment >>
FIG. 3 is a functional block diagram showing the data processing apparatus 2 according to the present invention for executing the Fermat test, and implements the Fermat test high-speed calculation procedure according to the present invention shown in FIGS. 12, 13 and 14. The data processing apparatus 1 executes a program together with the Montgomery multiplier coprocessor (6040) including the Montgomery remainder multiplier (6050) and the arithmetic registers (6060, 6070, 6080) and the like as described with reference to FIG. A central processing unit (6010) for controlling the multiplication coprocessor 6040 and the like, a memory (6020), and the like are realized, for example, as an IC card microcomputer 107 as illustrated in FIG. The IC card microcomputer 107 configured by the data processing device 2 has a function of generating an encryption key used for encryption communication using limited computing resources such as an on-chip memory, and is a random number used as a seed for the encryption key. A second example of the arithmetic processing for determining the prime number of will be described.

In FIG. 3, the modulus register N (1000) inputs and stores a prime number candidate N from the outside, and the modulus bit n register (1010) inputs and stores the bit number n of the prime number candidate from the outside. The log ₂ largest log ₂ computing device that provides an integer not exceeding (n) (1030), the maximum integer m not exceeding _log 2 (n) of is obtained. This process corresponds to step 7010 in FIG. M obtained in 1030 is stored in a register (1020) for storing m. A value obtained by rounding up the decimal point of n / m or less is obtained by the integer divider (1040), and the output of 1040 is selected by the selector (1050) and set in the counter i (1060). This process corresponds to step 7020 in FIG. The counter i is used to designate the (N−1) th partial bits to be extracted every m bits. On the other hand, R ² modN = 2 ²ⁿ modN is calculated by the computing unit (1100) and stored in the result register (1160). In FIG. 3, the storage path is not shown. This process corresponds to step 7040 in FIG. Next, RmodN = 2 ⁿ modN is calculated and stored in the register (1110). This process is equivalent to preparing RmodN used in step 7070 of FIG. According to the value of i, the most significant e [J−1] of (N−1) is cut out by the exponent cutout unit (1080), N is selected by the selector (3010), and the designated bit inverter (3020). , E [J-1] +1 bit is inverted and stored in the operation number generator (1090). In the designated bit inverter (3020), when e [J−1] +1 is n or more, no bit is inverted. Next, a comparison of the value of the 2 ^m -1 generator (1120) that produces a value in which all bits of the m bit length value are 1 and the exponent extracted by 1090 is compared by the comparator (1130), If they are equal, the selector (1140) selects the register (1110), and if not, the output of the operation number generator (1090) is selected. The Montgomery remainder multiplier (1150) performs a Montgomery remainder multiplication between the value of the result register (1160) and the value selected by the selector (1140), and the operation result is stored in the result register (1160). This processing corresponds to steps 7050, 8060, and 7070 in FIG. The value of the counter i (1060) is decremented by the subtracter (1070), the decremented result is selected by the selector (1050), and the counter i (1070) is updated. This process corresponds to Step 7080 in FIG.

The Montgomery residue multiplication operation mode control unit (1200) then changes the operation mode of the Montgomery residue multiplier (1150) to double multiplication, and initializes the counter j (1180) via the selector (1170). The Montgomery remainder multiplication operation mode control unit (1200) uses the Montgomery remainder multiplier (1150) to decrement the value of the result register (1160) every time the counter j (1180) is decremented once by the subtracter (1190). Is multiplied by the Montgomery remainder and stored in the result register (1160) until the counter j (1180) becomes zero. This corresponds to Step 7090 in FIG. Next, according to the value of the counter i (1060), the exponent cutout unit (1080) cuts out the partial bit e [i] of (N−1). N is selected by the selector (3010), the e [i] + 1 + n-2 ^m-th bit is inverted by the designated bit inverter (3020), and is stored in the arithmetic number generator (1090). In the designated bit inverter (3020), when e [i] + 1 + n−2 ^m is n or more, no bit is inverted. The value cut out by the exponent cutout unit (1080) is compared with 2 ^m −1 by the comparator (1130). Based on the comparison result, the selector (1140) selects the output (1090) of the operation number generator (1090) or the register (1110) storing R mod N, and the selected value is the value of the result register (1160) and the remainder. Multiplication is performed. This corresponds to the processing of steps 7100, 8110, and 7120 in FIG. When the remainder multiplication is completed, the value of the counter i (1060) is decremented by the computing unit (1070). When the value of the counter i (1060) is 1 or more, the processing corresponding to step 7090 in FIG. 13 is repeated.

  When the value of the counter i (1060) is 1, the operation mode of the Montgomery remainder multiplier (1150) is changed to double multiplication, and the counter j (1180) is initialized via the selector (1170). The Montgomery remainder multiplication operation mode control unit (1200) uses the Montgomery remainder multiplier (1150) to decrement the value of the result register (1160) every time the counter j (1180) is decremented once by the subtracter (1190). , And the result of storing the result of the operation in the result register (1160) is performed until the counter j (1180) becomes zero. This corresponds to Step 7150 in FIG.

Next, according to the value of the counter i (1060), the exponent mute unit (1080) extracts the second m bits from the least significant bit of (N-1). When the counter i (1060) is 1, 0 is selected by the selector (3010), and the value of e [1] + n-2 ^m-th bit is inverted by the designated bit inverter (3020), that is, e [1]. The value in which the (+ n-2 ⁾ -th ^m-th bit is set is stored in the operation number generation device (1090), and the value of the result register (1160) is subjected to modular multiplication. This corresponds to the processing of step 7160 in FIG. When the modular multiplication is completed, the value of the counter i (1060) is decremented by the calculator (1070) and set to the counter i (1060).

  Subsequently, the operation mode of the Montgomery remainder multiplier (1150) is changed to double multiplication, and the counter j (1180) is initialized via the selector (1170). The Montgomery remainder multiplication operation mode control unit (1200) uses the Montgomery remainder multiplier (1150) to decrement the value of the result register (1160) every time the counter j (1180) is decremented once by the subtracter (1190). Is multiplied by the Montgomery remainder and stored in the result register (1160) until the counter j (1180) becomes zero. This corresponds to Step 7170 in FIG.

  Finally, according to the value of the counter i (1060), the exponent cutout unit (1080) extracts the least significant m bits of (N−1). When the counter i (1060) is 0, 0 is selected by the selector (3010), and the designated bit inverter (3020) sets the value obtained by inverting the e [0] bit, that is, the e [0] bit. The calculated value is stored in the operation number generation device (1090), and the operation number generation device (1090) is always selected, and the value of the result register (1160) and the remainder multiplication are performed. This corresponds to the processing of step 7180 in FIG. When the remainder multiplication is completed, the value 2 ^ (N-1) mod N is stored in the result register (1160), and the process is terminated.

<< Third Embodiment >>
FIG. 4 shows a functional block diagram of the data processing apparatus 3 according to the present invention for executing the Fermat test, and implements the Fermat test high-speed calculation procedure according to the present invention shown in FIGS. 12, 13 and 14. In the data processing apparatus 2 of FIG. 3, the designated bit inverter (3020) is used. However, in FIG. 4, the power unit (3031) of 2 and the exclusive OR circuit (3032) are used instead. Other configurations are denoted by the same reference numerals, and detailed description thereof is omitted. The power unit of 2 (3031) converts the exponent extracted by the exponent segmentation unit (1080) into a power of 2. The exclusive OR circuit (3032) takes an exclusive OR for the output of the power-of-two calculator (3031) and the output of the selector (3010). The calculation result is the same as the output of the designated bit inverter (3020) in FIG.

<< Fourth Embodiment >>
FIG. 5 is a functional block diagram showing the data processor 4 according to the present invention for executing the Fermat test, and implements the Fermat test high-speed calculation procedure shown in FIG. In this example, the Montgomery remainder multiplier is not used. The data processing device 4 executes a program together with the remainder multiplication coprocessor (6140) including the remainder multiplier (6150) and the operation registers (6160, 6170, 6180) illustrated in FIG. A central processing unit (6010) for controlling 6140 and the like, a memory (6020) and the like are connected to each other via a bus 6030. The memory (6020) includes an electrically rewritable nonvolatile memory for storing a program (PGM) and a random access memory such as an SRAM used for storing variables, data (DAT), and the like. The data processing device 4 is realized, for example, as an IC card microcomputer 107 formed on one semiconductor substrate as shown in FIG.

In FIG. 5, prime number candidate N is input from the outside and stored in modulus register N (1000), and bit number n of prime number candidate N is input and stored from outside in modulus bit n register (1010). The log ₂ largest log ₂ computing device that provides an integer not exceeding (n) (1030), the maximum integer m not exceeding _log 2 (n) of is obtained. Since the type of the value output by 1030 is log ₂ (maximum value of n), the table is not actually calculated, and it is obtained from the position of the most significant bit among the non-zero bits of n. be able to. This process corresponds to step 9010 in FIG. The value m obtained by the log ₂ calculation device (1030) is stored in the register (1020). A value obtained by rounding up the decimal point of n / m or less is obtained by the integer divider (1040), and the output of 1040 is selected by the selector (1050) and set in the counter i (1060). This process corresponds to Step 9020 in FIG. The counter i is used to designate the (N−1) th partial bits to be extracted every m bits. According to the value of i, the exponent cutout unit (1080) cuts out the most significant of (N-1), and the operation number generation device (1090) generates 2 ^ (e [J-1]). Initially, the value of the operation number generator (1090) is stored as it is in the result register (4020) without performing multiplication by the remainder multiplier (4010). This process corresponds to Step 9040 in FIG. The value of the counter i (1060) is decremented by the subtracter (1070), and the decremented result is selected by the selector (1050), whereby the counter i (1070) is updated. This process corresponds to Step 9050 in FIG.

  The remainder multiplication operation mode control unit (4030) then changes the operation mode of the remainder multiplier (4010) to double multiplication, and initializes the counter j (1180) via the selector (1170). Every time the counter j (1180) is decremented once by the subtracter (1190), the remainder multiplication operation mode control unit (4030) uses the remainder multiplier (4010) to set the value of the result register (4020) to the remainder of the two. The process of multiplying and storing in the result register (4020) is performed until the counter j (1180) becomes zero. This corresponds to Step 9060 in FIG. Next, according to the value of the counter i (1060), the exponent cutout unit (1080) cuts out the (N-1) partial bits, and outputs the operation number generator (1090) and the result register (4020). A remainder multiplication with the value is performed. This corresponds to the processing of step 9070 in FIG. When the remainder multiplication is completed, the value of the counter i (1060) is decremented by the computing unit (1070). When the value of the counter i (1060) is 0 or more, the processing corresponding to step 9060 in FIG. 15 is repeated.

  When the value of the counter i (1060) is 0, the value of 2 ^ (N-1) mod N is stored in the result register (4020), and the process ends.

<< Fifth Embodiment >>
FIG. 6 is a functional block diagram showing the data processor 5 according to the present invention for executing the Fermat test, and realizes the Fermat test high-speed calculation procedure shown in FIG. In this example, the Montgomery remainder multiplier is not used. The data processor 4 executes a program together with the remainder multiplier coprocessor (6140) including the remainder multiplier (6150) and the operation registers (6160, 6170, 6180) exemplified in FIG. A central processing unit (6010) for controlling the processor 6140 and the like, a memory (6020) and the like are connected to each other via a bus 6030. This data processing device 5 is realized, for example, as an IC card microcomputer 107 formed on one semiconductor substrate as shown in FIG.

In FIG. 6, the modulus register N (1000) receives and stores a prime number candidate N from the outside, and the modulus bit n register (1010) inputs and stores the bit number n of the prime number candidate from the outside. The log ₂ largest log ₂ computing device that provides an integer not exceeding (n) (1030), the maximum integer m not exceeding _log 2 (n) of is obtained. Since the type of the value output by 1030 is log ₂ (maximum value of n), the table is not actually calculated, and it is obtained from the position of the most significant bit among the non-zero bits of n. be able to. This process corresponds to step 9010 in FIG. The value m obtained in 1030 is stored in the register (1020). A value obtained by rounding up the decimal point of n / m or less is obtained by the integer divider (1040), and the output of 1040 is selected by the selector (1050) and set in the counter i (1060). This process corresponds to Step 9020 in FIG. The counter i is used to designate the (N−1) th partial bits to be extracted every m bits. According to the value of i, the exponent cutout unit (1080) cuts out the most significant (e [J-1]) of (N-1), the selector (3010) selects 0, and the designated bit inverter (3020). ) Inverts the (e [J-1])-th bit, so that 2 ^ (e [J-1]) is set in the operation number generator (1090). At first, without performing multiplication by the remainder multiplier (4010), the value of the operation number generator (1090) is stored in the result register (4020) as it is. This process corresponds to Step 9040 in FIG. The value of the counter i (1060) is decremented by the subtracter (1070), the decremented result is selected by the selector (1050), and the counter i (1070) is updated. This process corresponds to step 9050 in FIG.

  The remainder multiplication operation mode control unit (4030) then changes the operation mode of the remainder multiplier (4010) to double multiplication, and initializes the counter j (1180) via the selector (1170). Every time the counter j (1180) is decremented once by the subtracter (1190), the remainder multiplication operation mode control unit (4030) uses the remainder multiplier (4010) to set the value of the result register (4020) to the remainder of the two. The process of multiplying and storing in the result register (4020) is performed until the counter j (1180) becomes zero. This corresponds to Step 9060 in FIG. Next, according to the value of the counter i (1060), the exponent cutout unit (1080) cuts out the partial bit (e [i]) of (N−1), the selector (3010) selects N, and designates it. When the bit inverter (3020) inverts the (e [i])-th bit, N xor 2 ^ (e [i]) is set in the arithmetic number generation device (1090). A modular multiplication is performed between the output of the operation number generator (1090) and the value of the result register (4020), and the operation result is stored in the result register (4020). This corresponds to the processing of step 10070 in FIG. When the modular multiplication is completed, the value of the counter i (1060) is decremented by the computing unit (1070). When the value of the counter i (1060) is 1 or more, the processing corresponding to step 9060 in FIG. 16 is repeated.

  When the value of the counter i (1060) is 0, the exponent segmentation unit (1080) extracts the least significant partial bit (e [0]) of (N−1) and the selector (3010) selects 0. Then, the designated bit inverter (3020) inverts the (e [i])-th bit, so that 2 ^ (e [0]) is set in the operation number generator (1090). A modular multiplication is performed between the output of the operation number generator (1090) and the value of the result register (4020), and the operation result is stored in the result register (4020). Since the value of 2 ^ (N-1) mod N is stored in the result register (4020), the process ends.

  Although the invention made by the present inventor has been specifically described based on the embodiments, it is needless to say that the present invention is not limited thereto and can be variously modified without departing from the gist thereof. A preferred example of the present invention is an IC card microcomputer, but the circuit module to be on-chip is not limited to the above description, and other circuit modules may be added. Further, the IC card microcomputer is not limited to being certified by an evaluation / certification organization of ISO / IEC15408, which is a security evaluation standard.

FIG. 1 is a functional block diagram illustrating a data processing apparatus according to the first embodiment. FIG. 2 is a block diagram showing an example of an arithmetic unit that calculates R ² modN used in the first embodiment. FIG. 3 is a functional block diagram illustrating a data processing apparatus according to the second embodiment. FIG. 4 is a functional block diagram illustrating a data processing apparatus according to the third embodiment. FIG. 5 is a functional block diagram illustrating a data processing apparatus according to the fourth embodiment. FIG. 6 is a functional block diagram illustrating a data processing apparatus according to the fifth embodiment. FIG. 7 is a block diagram illustrating the hardware configuration of the data processing apparatus according to the first or second embodiment. FIG. 8 is a block diagram illustrating the hardware configuration of the data processing apparatus according to the third or fourth embodiment. FIG. 9 is a flowchart illustrating a processing procedure by the data processing apparatus according to the first and second embodiments. FIG. 10 is a flowchart showing a continuation of FIG. FIG. 11 is a flowchart showing the continuation of FIG. FIG. 12 is a flowchart illustrating a processing procedure performed by the data processing apparatus according to the third embodiment. FIG. 13 is a flowchart showing the continuation of FIG. FIG. 14 is a flowchart showing a continuation of FIG. FIG. 15 is a flowchart illustrating a processing procedure performed by the data processing apparatus according to the fourth embodiment. FIG. 16 is a flowchart illustrating a processing procedure by the data processing apparatus according to the fifth embodiment. FIG. 17 is an external view illustrating the configuration of an IC card.

Explanation of symbols

107: IC card chip 1000: register 1010 for storing the modulus N 1010: register for storing the bit length of the modulus N 1020: register for storing the bit length m for extracting the exponent 1030: maximum not exceeding log ₂ of the input value Log ₂ calculator 1040: integer divider 1050: selector for selecting the output of the integer divider and subtractor 1060: register 1070 for storing counter i: subtractor 1080: delimiter N-1 every m bits The exponent cutout unit 1090 for outputting the i-th value from the lower side: the operation number generator 1100 for generating the operation number in which only the bit position of the input value is 1 and the other bits are 0: R mod N or R ² mod N calculator 1110 to calculate the: register 1120 calculator stores the R or ^{R 2} were calculated: m bits Values all ² bits to generate a value that is 1 m -1 generator 1130: comparator 1150: Montgomery modular multiplier 1160: the result stores the result of the modular multiplication register 1180: register for storing a counter value j 1190 : Subtractor 1200: Montgomery remainder multiplication mode control device 2010: arithmetic unit 2020 for calculating 2 ^{n + 1} modN from bit length N of modulus N and modulus N: register 2030 for storing 2 ^{n + 1} modN Operation number register 2060: Montgomery remainder multiplier 3020: Designated bit inverter 3032 that inverts and outputs only designated bits: Exclusive OR circuit 4010: Residue multiplier 4020: Register 4030: Residue multiplication Controller 6010 for controlling the operation mode of the controller: CPU
6020: Memory 6030: Bus 6040: Remainder Coprocessor 6050: Montgomery Remainder Multiplier 6060: Register for storing the number of operations 6070: Register for storing the number of operations 6080: Register for storing the modulus N 6140: Remainder multiplication coprocessor 6150: Residue multiplier 6160: Register 6170: Register 6170: Register 6180: Modulus N register 7010: Maximum integer not exceeding log ₂ (n) is substituted for m 7020: n / Substituting a value obtained by rounding up the decimal point of m into J Step 7030: Dividing N−1 into m bits and substituting into e [0]... e [J−1] Step 7040: Substituting R ² modN into result Step 7050: Step 7 for determining whether e [J−1] +1 is equal to n 060: Multiply the number of operations corresponding to the highest index when the highest index is less than 2 ^m −1 Step 7070: Equivalent to the highest index when the highest index is equal to 2 ^m −1 Step 7080: Substituting J-2 into the counter i Step 7090: Multiplying the result m times by the remainder and substituting it into the result Step 7100: e [i] + n-2 ^m is equal to n or conditional judgment to step 7110: e [i] + n -2 m to modular multiplication of the number of operations corresponding to the i-th exponent m bits when less than n steps 7120: e [i] + n -2 m and the n Step 7130: Subtract the value of the counter i by 1 Step 7140: Conditionally determine if i is greater than 1 Branching step 7150: multiplying the result by m times the remainder and substituting it in the result Step 7160: multiplying the operation number corresponding to the last m-bit exponent by the last step 7170: dividing the result by m times Step 7180 of multiplying by 2 and substituting in result: Multiplying the number of operations corresponding to the last m-bit exponent by the lowest one Step 7190: Outputting the result Step 8060: The highest exponent is 2 ^m −1 If the number is less than n, the number of operations corresponding to the most significant exponent is masked with modulus N and remainder multiplication is performed. Step 8110: e [i] + n-2. If ^m is less than n, it corresponds to the i-th m-bit exponent. step for modular multiplication while masking the operand by law n 9010: step 9020 of substituting _log 2 largest integer not exceeding (n) in m Step 9030 for substituting a value obtained by rounding up the decimal point of n / m into J: Step 9030: Dividing N−1 into m bits and substituting into e [0]... e [J−1] Step 9040: For the highest index Step 9050 for substituting the corresponding number of operations into result is Step 9060 for substituting J-2 into counter i Step 9060: Multiplying result by m times and substituting into result Step 9070: Corresponding to the i-th m-bit exponent Step 9080: Multiplying the number of operations by step 9080: Subtract 1 from the value of the counter i Step 9090: Determine whether the counter i is 0 or more and branch the conditional step 9100: Output the result Step 10070: Exponent of the i-th m-bit Step 10090: Multiplying the number of operations corresponding to modulo N while masking with the modulus N Step 10100: Step of multiplying the number of operations corresponding to the lowest m-bit exponent

Claims (6)

A coprocessor having a Montgomery modular multiplier for performing Montgomery modular multiplication; and a central processing unit that executes a program and controls the coprocessor, and performs data processing under the control of the central processing unit, so that external processing is performed. A data processing device that performs a Fermat test by calculating 2 ^(N−1) mod N for a given prime candidate N, wherein the data processing includes:
Storing the prime candidate N;
A process of storing a bit length n of N;
processing to calculate and store the largest integer m not exceeding log ₂ (n);
When N−1 is calculated from the prime candidate N and J is the smallest integer such that J ≧ n / m, (N−1) is divided into J intervals every m bits from the least significant bit, (N-1) = 2 ^{(J-1) m} · e [J-1] +2 ^{(J-2) m} · e [J-2] +... +2 ^m · e [1] + e [0] Exponential part cutout processing for dividing (N−1) into partial exponents e [0], e [1],..., E [J−1] to satisfy
2 power generation processing for generating 2 ^ (e [i] + 1 + n−2 ^m ) from the m-bit value e [i] cut out by the exponent part cut-out processing;
When e [J−1] +1, which is obtained by adding 1 to the highest value of the partial exponent extracted by the exponent segmentation process, is equal to 2 ⁿ , the calculation result of R mod N = 2 ⁿ mod N, and R ^A first process of performing Montgomery modular multiplication modulo the prime candidate N with the operation result of ² mod N = 2 ²ⁿ mod N and storing the operation result in a first storage area;
When e [J-1] +1 is less than 2 ^{n, the} calculation of 2 ^ (e [J-1] +1) calculated by the power-of-two generating unit and R ² mod N = 2 ²ⁿ mod N A second process for performing Montgomery modular multiplication on the result modulo N and storing the operation result in the first storage area;
A third process in which an internal state variable i is J-2 after either the first process or the second process;
After the third process, the prime candidate N is used as a modulus, and the operation of performing the Montgomery modular multiplication of the values stored in the first storage area and writing the calculation result back to the first storage area is repeated m times. A fourth process;
After the fourth process, when the partial index e [i] cut out by the exponent part cut-out process is less than 2 ^m −1, 2 ^ (e [i] generated by the power-of-two generation process of 2 + 1 + n−2 ^m ) and a value stored in the first storage area, performing a Montgomery modular multiplication modulo the N, and storing the calculation result in the first storage area;
After the fifth process, a value obtained by subtracting 1 from the internal state variable i is stored in the internal state variable i. When the value of i is 2 or more, the process returns to the fourth process, and the value of i A sixth process that repeats until it is less than or equal to 1,
After the sixth process, the prime candidate N is used as a modulus, and the operation of performing the Montgomery remainder multiplication of the values stored in the first storage area and writing the calculation result in the first storage area is repeated m times. 7 treatments,
After the seventh process, the prime candidate N of 2 ^ (e [1] + n-2 ^m ) calculated by the power-of-two generation process and the value stored in the first storage area is modulo An eighth process of performing a Montgomery modular multiplication and storing the operation result in the first storage area;
After the eighth processing, the Montgomery residue multiplication device modulo the prime candidate N, performs Montgomery residue multiplication between the values stored in the first storage area, and stores the calculation result in the first storage area. A ninth process of repeating the storing operation m times;
After the ninth process, the Montgomery residue modulo the prime candidate N between 2 ^ (e [0]) calculated by the power-of-two generation process and the value stored in the first storage area And a tenth process for performing multiplication and outputting the calculation result as a Fermat test result.   The data processing apparatus according to claim 1, further comprising a memory storing the program, and formed on a single semiconductor substrate. A coprocessor having a Montgomery modular multiplier for performing Montgomery modular multiplication; and a central processing unit that executes a program and controls the coprocessor, and performs data processing under the control of the central processing unit, so that external processing is performed. A data processing device that performs a Fermat test by calculating 2 ^(N−1) mod N for a given prime candidate N, wherein the data processing includes:
Storing the prime candidate N;
A process of storing a bit length n of N;
processing to calculate and store the largest integer m not exceeding log ₂ (n);
When N−1 is calculated from the prime candidate N and J is the smallest integer such that J ≧ n / m, (N−1) is divided into J intervals every m bits from the least significant bit, (N-1) = 2 ^{(J-1) m} · e [J-1] +2 ^{(J-2) m} · e [J-2] +... +2 ^m · e [1] + e [0] Exponential part cutout processing for dividing (N−1) into partial exponents e [0], e [1],..., E [J−1] to satisfy
From the m-bit value e [i] cut out by the exponent part cut-out process, 2 ^ (e [i] + 1 + n−2 ^m ).
Generating a power of 2 to generate
When e [J−1] +1 obtained by adding 1 to the highest value of the partial exponent extracted by the exponent segmentation process is equal to 2 ⁿ , the calculation result of R mod N = 2 ⁿ mod N, and R ^A first process of performing Montgomery modular multiplication modulo the prime candidate N with an operation result of ² mod N = 2 ²ⁿ mod N, and storing the operation result in a first storage area;
When e [J−1] +1 is less than 2 ⁿ , an exclusive OR of 2 ^ (e [J−1] +1) calculated by the power-of-two generating unit and the prime candidate N is calculated. A ^second process of performing a Montgomery modular multiplication modulo N of the calculated value and the calculation result of R ² mod N = 2 ²ⁿ mod N and storing the calculation result in the first storage area;
A third process in which the internal state variable i is set to J-2 after either the first process or the second process;
After the third processing, the prime candidate N is used as a modulus, and Montgomery modular multiplication of the values stored in the first storage area is performed, and the operation result of storing the four calculation results in the first storage area is m times. A fourth process to repeat;
After the fourth process, when the partial index e [i] cut out by the exponent part cut-out process is less than 2 ^m −1, 2 ^ (e [i] generated by the power-of-two generation process of 2 + 1 + n−2 ^m ) and the prime candidate N and the value stored in the first storage area are subjected to Montgomery residue multiplication modulo the prime candidate N. A fifth process for storing the calculation result in the first storage area;
After the fourth process, when the partial index e [i] cut out by the exponent part cutout process is equal to 2 ^m −1, the R mod N = 2 ⁿ mod N is stored in the first storage area. A sixth process of performing Montgomery modular multiplication modulo the prime candidate N with the obtained value and storing the operation result in the first storage area;
A value obtained by subtracting 1 from the internal state variable i after any one of the fifth process and the sixth process is stored in the internal state variable i, and when the value of i is 2 or more, Returning to 3 processing, and repeating the 7th processing until the value of i becomes 1 or less,
After the seventh process, the prime candidate N is used as a modulus, and the operation of performing Montgomery modular multiplication of the values stored in the first storage area and storing the calculation result in the first storage area is repeated m times. 8 treatments,
After the eighth process, the prime candidate N of 2 ^ (e [1] + n-2 ^m ) generated by the power-of-two generation process and the value stored in the first storage area is modulo A ninth process for performing a Montgomery modular multiplication and storing the operation result in the first storage area;
After the ninth process, the prime candidate N is used as a modulus, and the operation of performing Montgomery modular multiplication of the values stored in the first storage area and storing the calculation result in the first storage area is repeated m times. A tenth process;
After the tenth processing, Montgomery modular multiplication is performed modulo N of 2 ^ (e [0]) generated by the power-of-two generation processing and the value stored in the first storage area. And an eleventh process for outputting the calculation result as a Fermat test result.   The data processing apparatus according to claim 2, further comprising a memory storing the program, and formed on a single semiconductor substrate. A coprocessor having a Montgomery modular multiplier for performing Montgomery modular multiplication; and a central processing unit that executes a program and controls the coprocessor, and performs data processing under the control of the central processing unit, so that external processing is performed. A data processing device that performs a Fermat test by calculating 2 ^(N−1) mod N for a given prime candidate N, wherein the data processing includes:
Storing the prime candidate N;
A process of storing a bit length n of N;
processing to calculate and store the largest integer m not exceeding log ₂ (n);
When N−1 is calculated from the prime candidate N and J is the smallest integer such that J ≧ n / m, (N−1) is divided into J intervals every m bits from the least significant bit, (N-1) = 2 ^{(J-1) m} · e [J-1] +2 ^{(J-2) m} · e [J-2] +... +2 ^m · e [1] + e [0] Exponential part cutout processing for dividing (N−1) into partial exponents e [0], e [1],..., E [J−1] to satisfy
2 power generation processing for generating 2 ^ (e [i] + 1 + n−2 ^m ) from the m-bit value e [i] cut out by the exponent part cut-out processing;
When e [J−1] +1 obtained by adding 1 to the highest value of the partial exponent extracted by the exponent segmentation process is equal to 2 ⁿ , the calculation result of R mod N = 2 ⁿ mod N, and R ^A first process of performing Montgomery modular multiplication modulo the prime candidate N with the operation result of ² mod N = 2 ²ⁿ mod N and storing the operation result in a first storage area;
The e If [J-1] +1 is less than ^{2 n,} wherein N of e [J-1] the inverted value as the specified bit inverter values of +1 bit ^{R 2 mod N = 2 2n mod} N A second process of performing a Montgomery modular multiplication modulo the prime candidate N with the operation result of and storing the operation result in the first storage area;
A third process in which the internal state variable i is set to J-2 after either the first process or the second process;
After the third process, the prime candidate N is used as a modulus, and Montgomery modular multiplication of the values stored in the first storage area is performed and the operation result is stored m times in the first storage area. A fourth process;
If the partial index e [i] cut out by the exponent cutout process after the fourth process is less than 2 ^m −1, the value of the e [i] + 1 + n−2 ^m bit of the N is specified A fifth process for performing Montgomery modular multiplication on the prime candidate N modulo the value inverted by the bit inverter and the value stored in the first storage area, and storing the calculation result in the first storage area; ,
When the partial index e [i] cut out by the exponent part cutout process after the fourth process is equal to 2 ^m −1, the calculation result of the R mod N = 2 ⁿ mod N and the first storage area A sixth process of performing Montgomery modular multiplication modulo the prime candidate N with the value stored in, and storing the operation result in the first storage area;
After either one of the fifth process and the sixth process, a value obtained by subtracting 1 from the internal state variable i is stored in the internal state variable i, and when the value of i is 2 or more, Returning to the third process, the seventh process is repeated until the value of i becomes 1 or less,
After the seventh process, the prime candidate N is used as a modulus, the Montgomery modular multiplication of the values stored in the first storage area is performed, and the operation of storing the calculation result in the first storage area is repeated m times. An eighth process;
After the eighth process, modulo the prime candidate N between 2 ^ (e [1] + n-2 ^m ) calculated by the power-of-two generating means and the value stored in the first storage area A ninth process for performing Montgomery modular multiplication and storing the operation result in the first storage area;
After the ninth process, the prime candidate N is used as a modulus, and the operation of performing Montgomery modular multiplication of the values stored in the first storage area and storing the calculation result in the first storage area is repeated m times. A tenth process;
After the tenth processing, the Montgomery residue modulo the prime candidate N between 2 ^ (e [0]) generated by the power-of-two generation processing and the value stored in the first storage area And an eleventh process for performing multiplication and outputting the operation result as a Fermat test result.   The data processing apparatus according to claim 5, further comprising a memory storing the program and formed on one semiconductor substrate.

Images