Ciphering device, cryptographic key generation method and method of managing cryptographic key, and prime number generation device and method therefor

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to an encryption device for generating an encryption key used for encryption processing, decryption processing, authentication processing, etc., an encryption key generation method and an encryption key management method, and a prime number generation device and a prime number generation method.

【0002】

[Conventional technology]

In recent years, as information processing technology has advanced, it has become common practice to digitize and handle information. In addition to simply digitizing data, new services such as an electronic money system and a distribution system for digitized information related to copyright are being developed. When handling such digitized information, only specific people can view it, such as corporate secrets, private data, electronic currency information, and digitized information related to copyright, and the contents are kept secret from other people. Cryptography is used to store and communicate the information you want.

【0003】

For example, when performing encrypted communication between host computers, the sender encrypts the data with the common key or the public key of the other party, and the receiver decrypts this with the common key or its own private key to obtain specific key information. Only the person who has can decrypt the encrypted data. Further, for example, the validity of the information can be verified by the authentication process using the key information.

【0004】

By the way, in secret key cryptography, it is possible to easily generate a common key only by having a random number generation function. On the other hand, the generation of the public key and the private key of the public key cryptography is not as simple as the common key generation of the private key cryptography. In particular, in order to generate a public key and a private key, a prime number with a large bit length is required, so an increase in the amount of calculation is unavoidable. As a method for generating prime numbers with a large bit length at high speed, there is table processing using memory, but in this case, it is necessary to store a very large number of prime numbers, and memory resources are limited. It has been considered that this table processing is not appropriate for a cryptographic device (for example, one that uses an IC card having a processing function as a cryptographic device). For this reason, conventionally, it has been necessary to generate a public key and a private key for public key cryptography in an environment in which a high-speed CPU such as a personal computer and sufficient memory exist.

【0005】

In addition, when the center that manages and publishes the public key of each user generates the public key and the private key and delivers the private key to each user, a key distribution mechanism in consideration of security is indispensable. Therefore, it was a considerable burden for the center to deliver and manage a large number of private keys.

【0006】

Further, when an individual user generates a public key and a private key on a personal computer or the like and transfers and holds the private key to an external storage device, the generated key is stored in the memory of the personal computer even temporarily. If it exists and it is online, the key can be destroyed or tampered with. In addition, the key that has already been generated may be destroyed or tampered with due to an erroneous operation of the private key generation function. Further, there is a problem that it is not possible to detect that the key has been destroyed or tampered with.

【0007】

[Problems to be Solved by the Invention]

Conventionally, when an encryption key (public key, private key, common key) is generated based on a prime number, there is a problem that a large amount of computer resources are required because it is necessary to generate a prime number with a large bit length. ..

【0008】

Further, conventionally, there is a problem that the already generated key may be destroyed by restarting the private key generation function. Further, conventionally, there is a problem that it is not possible to detect that the key has been destroyed or tampered with.

【0009】

The present invention has been made in consideration of the above circumstances, and is an encryption device capable of generating a sufficiently large prime number that is a source of encryption key generation by using less computer resources in the own device. The purpose is to provide a method for generating an encryption key.

【0010】

Another object of the present invention is to provide a cryptographic device capable of securely managing a cryptographic key, a cryptographic key generation method, and a cryptographic key management method. Another object of the present invention is to provide a prime number generator and a prime number generation method capable of generating a larger prime number by utilizing less computer resources.

【0011】

[Means for solving problems]

The present invention (claim 1) is an encryption device that generates an encryption key based on a prime number in its own device, and has 2 n bits or less based on all prime numbers having a predetermined value of n bits or less. A first prime number generating means for generating a first prime number, and a second prime number having a predetermined bit length larger than 2n bits based on all the prime numbers of n bits or less and the first prime number. It is characterized by including two prime number generation means and an encryption key generation means for generating an encryption key using the second prime number having a predetermined bit length.

【0012】

The present invention (claim 2) is an encryption device that generates an encryption key in its own device, and determines a predetermined prime number of 2 n bits or less by using all predetermined prime numbers of n bits or less. To generate a first prime number of 2 n bits or less, and a prime number candidate larger than the first prime number based on the first prime number, and at least all of the n bits or less. If it is determined that the prime number candidate is not a composite number by the prime number determination using the prime number, the prime number candidate is set as a new first prime number, and a new prime number candidate larger than the prime number candidate is used based on the new first prime number. The process of generating prime number candidates is recursively repeated, and when it is determined that the prime number candidate is a composite number, the prime number candidate is generated based on the first prime number at the time when the prime number candidate is determined to be the composite number. By repeating the process recursively, a second prime number generating means for generating a second prime number having a predetermined bit length larger than 2n bits and a prime number having the predetermined bit length are used to generate an encryption key. It is characterized by having a means for generating an encryption key.

【0013】

The present invention (claim 3) is an encryption device that generates an encryption key in its own device, and determines a predetermined prime number of 2 n bits or less by using all predetermined prime numbers of n bits or less. The first prime number generation means that generates the first prime number of 2n bits or less, the first prime number of 2n bits or less generated by the first prime number generation means, and all the prime numbers of n bits or less. A second prime number generating means for generating a second prime number having a predetermined bit length larger than 2n bits, and a 0.4 m-bit second prime number generated by using the first and second prime number generating means. And a third prime number generating means that generates a third prime number of 0.5 m bits based on the second prime number, and another 0.4 m bit generated by using the first and second prime number generating means. A fourth prime number of m bits is generated based on the second prime number of the above, the third prime number of 0.5 m bits generated by the third prime number generation means, and all the prime numbers of n bits or less. The prime number generation means of the above and the encryption key generation means for generating the encryption key by using the fourth prime number of the m bits generated by the fourth prime number generation means are provided.

【0014】

The present invention (claim 4) is an encryption device that generates an encryption key in its own device, and whether or not the encryption key is generated by the encryption key generation means for generating the encryption key and the encryption key generation means. It is provided with a means for storing the control information indicating the above, and a means for disabling the generation of the encryption key by the encryption key generation means while the control information indicates that the encryption key has been generated. It is characterized by that.

【0015】

The present invention (claim 5) is a cryptographic device that generates an encryption key in its own device, and the encryption key is generated by the encryption key generation means for generating the encryption key and the encryption key generation means. , A check sum generating means for immediately generating a check sum of the generated encryption key, and a storage means for storing the encryption key and the check sum in association with each other are provided.

【0016】

The present invention (claim 6) is a cryptographic key generation method for generating a cryptographic key based on a prime number in a cryptographic device, and is 2n bits based on all prime numbers having a predetermined n-bit or less value. The following first prime number is generated, and a second prime number having a predetermined bit length larger than 2n bits is generated based on all the prime numbers of n bits or less and the first prime number, and the predetermined bit length is generated. It is characterized in that an encryption key is generated using the second prime number of.

【0017】

The present invention (claim 7) is a method for generating a cryptographic key based on a prime number in a cryptographic device, which is a predetermined 2 n-bit or less using all prime numbers of n-bit or less predetermined. A first prime number generation step that generates a first prime number of 2 n bits or less by determining a prime number of the above, and a prime number candidate larger than the first prime number is generated based on the first prime number, and at least If it is determined that the prime number candidate is not a composite number by the prime number determination using all the prime numbers of n bits or less, the prime number candidate is set as a new first prime number and based on the new first prime number. When the process of generating a new prime number candidate larger than the prime number candidate is recursively repeated and the prime number candidate is determined to be a composite number, the time when the prime number candidate is determined to be a composite number in the first prime number generation step. With the second prime number generation step to generate a second prime number with a predetermined bit length larger than 2n bits by regenerating a prime number candidate based on the first prime number in and repeating the process recursively. It is characterized by having an encryption key generation step of generating an encryption key using the prime number of the predetermined bit length.

【0018】

The present invention (claim 8) is a method for generating a cryptographic key based on a prime number in a cryptographic device, which is a predetermined 2 n-bit or less using all prime numbers of n-bit or less predetermined. The first prime number generation step that generates a first prime number of 2n bits or less by determining the prime number of the above, the first prime number of 2n bits or less generated in the first prime number generation step, and the n A second prime number generation step that generates a second prime number with a predetermined bit length larger than 2n bits based on all prime numbers below the bit, and 0.4m generated by the first and second prime number generation steps. A third prime number generation step that generates a 0.5 m-bit third prime number based on the second prime number of the bit and the second prime number, and the other generated by the first and second prime number generation steps. Based on the 0.4m-bit second prime number, the 0.5m-bit third prime number generated by the third prime number generation step, and all the n-bit or less prime numbers, the m-bit fourth prime number is calculated. It is characterized by having a fourth prime number generation step to be generated and a cryptographic key generation step to generate a cryptographic key using the fourth prime number of the m bits generated in the fourth prime number generation step. ..

【0019】

The present invention (claim 9) is a method for generating a cryptographic key in a cryptographic device including a cryptographic key generating means for generating a cryptographic key, wherein the cryptographic key is generated prior to being generated by the cryptographic key generating means. The encryption key generation means refers to the control information indicating whether or not the encryption key has been generated by the key generation means, and the encryption key generation means only indicates that the encryption key has not been generated by the control information. When an encryption key is generated and the encryption key is generated by the encryption key generation means, the control information is set to a state indicating that the encryption key has been generated.

【0020】

The present invention (claim 10) is an encryption key management method in an encryption device that generates an encryption key in its own device, and is generated by generating the encryption key and immediately generating a checksum of the encryption key. It is characterized in that the encryption key and the check sum are stored in association with each other.

【0021】

The present invention (claim 11) comprises a first prime number generating means for generating a prime number of 2 n bits or less based on all prime numbers of a predetermined value of n bits or less, and all prime numbers of n bits or less. A second prime number generating means for generating a prime number having a predetermined bit length larger than 2n bits based on the prime number of 2n bits or less is provided.

【0022】

According to the present invention (claim 12), a first prime number of 2 n bits or less is generated by determining a predetermined prime number of 2 n bits or less using all predetermined prime numbers of n bits or less. A prime number generation means and a prime number candidate larger than the first prime number are generated based on the first prime number, and the prime number candidate is not a composite number by a prime number determination using at least all the prime numbers of n bits or less. If it is determined, the prime number candidate is set as a new first prime number, and the process of generating a new prime number candidate larger than the prime number candidate based on the new first prime number is recursively repeated, and the prime number candidate is generated. If is determined to be a composite number, a prime number candidate is regenerated based on the first prime number at the time when is determined to be a composite number, and the process is recursively repeated from 2n bits. It is characterized by being provided with a second prime number generation means for generating a second prime number having a large predetermined bit length.

【0023】

According to the present invention (claim 13), a first prime number of 2 n bits or less is generated by determining a predetermined prime number of 2 n bits or less using all predetermined prime numbers of n bits or less. A second prime number with a predetermined bit length larger than 2n bits based on the prime number generation means, the first prime number of 2n bits or less generated by the first prime number generation means, and all the prime numbers of n bits or less. The second prime number generating means for generating the above, the second prime number of 0.4 m bits generated by using the first and second prime number generating means, and the second prime number of 0.5 m bits based on the second prime number. A third prime number generating means for generating a prime number of 3 and another 0.4 m-bit second prime number generated using the first and second prime number generating means, generated by the third prime number generating means. It is characterized by including a third prime number of 0.5 m bits and a fourth prime number generation means for generating a fourth prime number of m bits based on all the prime numbers of n bits or less.

【0024】

The present invention (claim 14) generates a first prime number of 2 n bits or less based on all prime numbers having a predetermined value of n bits or less, and all prime numbers of n bits or less and the 2 n bits. It is characterized in that a prime number having the predetermined bit length larger than 2n bits is generated based on the following prime numbers.

【0025】

According to the present invention (claim 15), a first prime number of 2 n bits or less is generated by determining a predetermined prime number of 2 n bits or less using all predetermined prime numbers of n bits or less. A prime number candidate that is larger than the first prime number is generated based on the prime number generation step and the first prime number, and the prime number candidate is not a composite number by a prime number determination using at least all the prime numbers of n bits or less. If it is determined, the prime number candidate is set as a new first prime number, and the process of generating a new prime number candidate larger than the prime number candidate based on the new first prime number is recursively repeated, and the prime number candidate is generated. When is determined to be a composite number, a prime number candidate is generated based on the first prime number at the time when it is determined to be a composite number in the first prime number generation step, and the process is recursively performed. It is characterized by having a second prime number generation step of generating a second prime number having a predetermined bit length larger than 2n bits by repeating.

【0026】

According to the present invention (claim 16), a first prime number of 2 n bits or less is generated by determining a predetermined prime number of 2 n bits or less using all predetermined prime numbers of n bits or less. A second prime number generation step and a second prime number with a predetermined bit length larger than 2n bits based on the first prime number of 2 n bits or less and all the prime numbers of n bits or less generated in the first prime number generation step. A second prime number generation step that generates a prime number, a 0.4 m-bit second prime number generated by the first and second prime number generation steps, and a 0.5 m-bit third based on the second prime number. The third prime number generation step to generate the prime number of, the other 0.4 m-bit second prime number generated by the first and second prime number generation steps, and 0.5 generated by the third prime number generation step. It is characterized by having a third prime number of m bits and a fourth prime number generation step of generating a fourth prime number of m bits based on all the prime numbers of n bits or less.

【0027】

According to the present invention (claim 17), a procedure for generating a first prime number of 2 n bits or less based on all prime numbers of a predetermined n bits or less and a procedure of generating a first prime number of 2 n bits or less and all the prime numbers of n bits or less are described. The gist is a computer-readable recording medium on which a program for executing a procedure for generating a second prime number having a predetermined bit length larger than 2n bits based on the prime number and the first prime number is executed.

【0028】

The present invention (claim 18) generates a first prime number of 2 n bits or less by determining a predetermined prime number of 2 n bits or less using all predetermined prime numbers of n bits or less in a computer. A prime number candidate larger than the first prime number is generated based on the first prime number generation step and the first prime number, and the prime number candidate is synthesized by a prime number determination using at least all the prime numbers of n bits or less. If it is determined that it is not a number, the prime number candidate is set as a new first prime number, and the process of generating a new prime number candidate larger than the prime number candidate based on the new first prime number is recursively repeated. If it is determined that the prime number candidate is a composite number, the prime number candidate is regenerated based on the first prime number at the time when it is determined to be a composite number in the first prime number generation step. A computer-readable recording medium containing a program for executing a second prime number generation step of generating a second prime number having a predetermined bit length larger than 2n bits by recursively repeating ..

【0029】

The present invention (claim 19) generates a first prime number of 2 n bits or less by determining a predetermined prime number of 2 n bits or less using all the predetermined prime numbers of n bits or less in a computer. A predetermined bit length larger than 2n bits based on the first prime number generation step, the first prime number of 2n bits or less generated in the first prime number generation step, and all the prime numbers of n bits or less. A second prime number generation step that generates a second prime number, a 0.4 m-bit second prime number generated by the first and second prime number generation steps, and a 0.5 m-bit based on the second prime number. A third prime number generation step for generating the third prime number of the above, and another 0.4 m-bit second prime number generated by the first and second prime number generation steps, generated by the third prime number generation step. A computer that records a program for executing a third prime number of 0.5 m bits and a fourth prime number generation step of generating a fourth prime number of m bits based on all the prime numbers of n bits or less. The gist is a readable recording medium, preferably the program may include a procedure for generating an encryption key using the prime numbers generated by a computer.

【0030】

Preferably, the program may include a procedure for encrypting data to be encrypted using the encryption key generated by a computer.

【0031】

According to the present invention (claim 20), a procedure for referring to a control information indicating whether or not an encryption key is generated before generating an encryption key to a computer, and the fact that the encryption key is not generated by the control information. A computer that records a program for executing a procedure for generating an encryption key only when is indicated and a procedure for setting the control information in a state indicating that the encryption key has been generated when the encryption key is generated. The gist is a readable recording medium.

【0032】

The present invention (claim 21) associates a computer with a procedure for generating an encryption key, a procedure for generating a checksum of the encryption key immediately after generating the encryption key, and the generated encryption key and the checksum. The gist is a computer-readable recording medium in which a program is recorded to execute a procedure of storing in a predetermined storage area.

【0033】

The invention relating to the above device is also valid as an invention relating to the method, and the invention relating to the method is also valid as an invention relating to the device. In addition, the present invention relating to an apparatus or method provides a function for causing a computer to perform a procedure corresponding to the present invention (or for causing the computer to function as a means corresponding to the present invention, or for causing the computer to perform a function corresponding to the present invention. It can also be used as a computer-readable recording medium on which a program (to be realized) is recorded.

【0034】

In the present invention (claims 1, 2, 3, 6, 7, 8, 11 to 16), n bits are preferably a multiple of 2. For example, n bits = 256 = 2⁸ In the case of, there are 53 prime numbers of 256 or less in total. The predetermined bit length is, for example, 256 bits or 384 bits. Also, m is, for example, 256 or 384.

【0035】

Further, in the second to fourth prime number generation, it is preferable to perform at least the Fermat test after the primality test (Eratosthenes sieving) using all the prime numbers of n bits or less.

【0036】

Further, preferably, the encryption device or the prime number generation device may include a program storage means, a calculation means for executing a program, a memory means capable of reading and writing data, and a means for communicating with the outside.

【0037】

Further, the encryption device and the prime number generation device can be realized by, for example, a personal computer. Alternatively, it can be realized with an IC card. According to the present invention (claims 1, 2, 3, 6), a deterministic primality test method and a method used when determining a first prime number (first prime number).^1/2 By combining with the prime number table that stores the following prime numbers, it is possible to use a table of a size corresponding to the memory capacity of the encryption device.

【0038】

Therefore, even if it is not a cryptographic device such as a personal computer having abundant memory but a cryptographic device having a limited memory capacity (for example, an IC card), a key (for example, a public key in public key cryptography) can be easily installed on the device. It becomes possible to implement a function to generate a private key).

【0039】

Moreover, since the amount of data to be handled is small, the key can be generated at high speed. Moreover, since a deterministic primality test method is used, a prime number can be reliably obtained and a secure key can be obtained.

【0040】

Further, by providing the device with a key generation function, it is possible to improve the security of the key and facilitate the management of the key. Further, if the key is generated in each encryption device and the encryption processing and decryption processing are performed in the encryption device, the key never goes out of the encryption device, so that high security for the key can be maintained. ..

【0041】

Further, in public key cryptography, since each cryptographic device generates a private key and a public key, the center that manages the key does not need to generate and deliver the key to each cryptographic device, and key generation and management. The processing load associated with this is reduced.

【0042】

According to the present invention (claims 11 to 16), a deterministic primality test method and a method used when determining a first prime number (first prime number).^1/2 By combining with the prime number table that stores the following prime numbers, it is possible to use a table of a size corresponding to the memory capacity of the device.

【0043】

Therefore, it is possible to easily implement the prime number generation function on the device even if the device has a limited memory capacity (for example, an IC card) instead of a device such as a personal computer having abundant memory.

【0044】

Moreover, since the amount of data to be handled is small, prime numbers can be generated at high speed. Moreover, since a deterministic primality test method is used, a prime number can be surely obtained. In the present invention (claims 4 and 9), the control information is, for example, at least 1 bit of memory.

【0045】

According to the present invention (claims 4 and 9), since the encryption key generation means cannot be restarted while the control information is in the state after the encryption key is generated, the encryption key generation means is used for the key generated in the encryption device. It is possible to prevent the already generated key from being destroyed by restarting the key.

【0046】

According to the present invention (claims 5 and 10), the check sum is calculated immediately after the encryption key is generated and is stored together with the encryption key in the own device. Therefore, the encryption key stored when using this key is used. By calculating the checksum of the key and comparing it with the stored checksum, the validity of the key is verified, and the encryption process or decryption process by the encryption key that has been tampered with or destroyed for some reason is avoided. Can be done.

【0047】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, embodiments of the invention will be described with reference to the drawings. FIG. 1 is a diagram showing a configuration of a cryptographic device according to an embodiment of the present invention. The encryption device 1 of the present embodiment includes a CPU 2, a program storage unit 3, an arithmetic unit 4, a random number generation unit 5, a randomly accessible non-volatile memory 6, a non-volatile memory 7, an address and a data bus 8.

【0048】

In the present embodiment, each function is realized by executing the program stored in the program storage unit 3 on the CPU 2. This program includes at least a subprogram for prime number generation and a subprogram for key generation. It is also possible to independently implement the subprogram for prime number generation and the subprogram for key generation.

【0049】

Further, in the present embodiment, the calculation unit 4 is used for a predetermined calculation in order to increase the processing speed. For the arithmetic unit 4, for example, a coprocessor is used. However, it is not necessary to provide the calculation unit 4.

【0050】

Further, although the random number generation unit 5 is clearly shown in FIG. 1, the random number generation unit 5 may be realized by independent hardware or may be realized by a program and CPU2. In the present embodiment, the latter is assumed. The random number may be input from an external device.

【0051】

The program storage unit 3 is, for example, a ROM. It is also possible to adopt a configuration in which a program (a program including a procedure for realizing the present embodiment) is installed from the outside (for example, read from a recording medium or acquired via a network). In such a case, for example, EEPROM, RAM, a hard disk device, or the like can be used for the program storage unit 3.

【0052】

The randomly accessible non-volatile memory 6 is, for example, RAM. In this memory 6, data necessary for calculation, data in the middle of calculation, and the like are stored. The non-volatile memory 7 is, for example, an EEPROM. The generated key and the like are stored in this memory 7.

【0053】

Further, the encryption device 1 inputs data from the outside via a desired interface (not shown) and outputs the data to the outside. Various types of interfaces such as a user interface and a communication interface can be considered. For example, when the encryption device 1 is an IC card, data is exchanged with an external computer via a predetermined communication interface.

【0054】

Then, the encryption device 1, a desired encryption function, that is, processing such as encryption or decryption of data input via this interface, or data authentication processing, and an external display device, It shall have a function to output input data or processed data to a communication line or a storage device. This function is realized, for example, by a program. It is also possible to incorporate this function as a subprogram into a program including the above-mentioned subprogram for prime number generation and the subprogram for key generation.

【0055】

By the way, in this embodiment, a prime number table storing prime numbers used for primality test is used. This prime number table is stored in a randomly accessible non-volatile memory 6. Here, on the premise that a prime number with a bit length twice the word size is first generated, and then a prime number with a predetermined size larger than that is generated based on the prime number, the prime number table contains prime numbers smaller than the word size. It shall be stored. For example, if the word size is 8 bits, all prime numbers of 256 or less (53 prime numbers) are stored.

【0056】

FIG. 2 shows a flowchart of a prime number generation process for generating a prime number used for public key and private key generation. Process 1: First, the random number generator 5 randomly generates an odd number with a bit length twice the word size (step S1).

【0057】

Process 2: For the generated odd numbers, trial division (Eratosthenes sieving) is performed in the calculation unit 4 using prime numbers smaller than the word size stored in the prime number table (step S2).

【0058】

Process 3: If the generated odd number is not divisible by all the prime numbers in the prime number table, determine this odd number as a prime number and F₀ Substitute in. If it is divisible by any of the prime numbers in the prime number table, it returns to process 1 (step S3).

【0059】

Process 4: Set the parameter i = 0 for the following processing loop (step S4). Process 5: Prime number F_i In the random number generator 5, R_i <F_i Random number R that satisfies_i (Step S5), N_i = 2R_i F_i Prime number candidate N represented by +1_i (Step S6).

【0060】

Process 6: Prime candidate N_i On the other hand, as a preprocessing for the primality test, the arithmetic unit 4 performs trial division using the prime numbers stored in the prime number table (step S7). Process 7: Prime candidate N_i Is a prime number candidate N if it is divisible by any of the prime numbers in the prime number table_i Is determined to be a composite number, and the process returns to process 5 (step S8). And F_i The value of R remains the same, and in the random number generator 5, R_i (R_i <F_i ) Is regenerated, and a new prime number candidate N_i To generate.

【0061】

Process 8: Prime candidate N_i About the prescribed a_i Is calculated in the calculation unit 4 whether or not the equation (1) is satisfied (Fermat test) (step S9). If not satisfied, the process returns to process 5 (step S10).

【0062】

[Number 1]

<img file="JPH10240128A_D0001.tif" />【0063】

Process 9: Prime candidate N_i About the prescribed a_i Is calculated in the calculation unit 4 whether or not the equation (2) is satisfied (step S11). If not satisfied, the process returns to process 5 (step S12).

【0064】

[Number 2]

<img file="JPH10240128A_D0002.tif" />【0065】

Process 10: Prime candidate N_i If does not reach the specified bit size, then F_i = N_i , I + = 1 (i is incremented by 1) (steps S13, S14), and the process returns to process 5. Prime number candidate N_i R to reach the specified bit length_i Bit length increased (R_i&lt;F_i ) To adjust.

【0066】

Process 11: Prime candidate N as above_i When the specified bit size is reached, the prime number N_i To get. In process 8 and process 9 above, a_i It is preferable to use = 2. In the above trial division, the prime number table containing prime numbers smaller than the word size is used, but F.₀ It is possible to remove most composite numbers by performing trial division with the following prime numbers as preprocessing. Therefore, by narrowing down the prime number candidates to be subjected to the primality test, the primality test can be performed efficiently.

【0067】

In addition, in the above judgment formula, a_i The calculation is easy because it is processed with a small bottom calculation of = 2. Usually bottom a_i Performs primality test processing using not only 2 but also small prime numbers in order, but a_i There is no problem even if is not changed in this way. It is a_i This is because when = 2, there are very few cases where it is determined that a prime number candidate is not a prime number even though it is a prime number.

【0068】

Therefore, as a bottom with efficiency and practicality, a_i Use = 2. Assuming that the bit size of the obtained prime number is n bits in the execution up to the above process 11, (prime number-1) can have a prime number of about n / 2 bits. As a result, the p-1 method, which is one of the prime factorization methods, can be avoided.

【0069】

Furthermore, in order to deal with the p + 1 method, it is necessary to give (prime number + 1) a prime number with a large bit size. The process shown in Fig. 2 is used to generate a prime number, and the process shown in Fig. 3 is used to generate a prime number that can handle the p ± 1 method.

【0070】

Process 12: First, a 0.4 n-bit prime number (s, t) is generated using the process shown in Fig. 2 (steps S21 and S22). Process 13: Generate 0.5n-bit prime number candidates so that r = 2at + 1 (step S23).

【0071】

Process 14: For prime number candidates, trial division is performed in the calculation unit 4 using the prime numbers stored in the prime number table as preprocessing for primality test (step S24). If the prime number candidate is divisible by any of the prime numbers in the prime number table, the prime number candidate N is determined to be a composite number, the value of a is adjusted as in a + = 1, and the process returns to process 13 (step S25). ..

【0072】

Process 15: For the prime number candidate, the calculation unit 4 calculates whether or not the equation (3) is satisfied (step S26). If not satisfied, adjust the value of a as in a + = 1, and return to process 13 (step S27).

【0073】

[Number 3]

<img file="JPH10240128A_D0003.tif" />【0074】

Process 16: For the prime number candidate, the calculation unit 4 calculates whether or not the equation (4) is satisfied (step S28). If not satisfied, adjust the value of a as in a + = 1, and return to process 14 (step S29).

【0075】

[Number 4]

<img file="JPH10240128A_D0004.tif" />【0076】

Processing 17: N-bit prime number N, N = 1 + 2 (bs-r)^-1 (mod s)) Generate so that it becomes r (step S30), and perform the same processing as the trial division and judgment of the above process 14, the calculation and judgment of the process 15, and the calculation and judgment of the process 16 (step S31 ~). S36). If the prime number candidate N is determined to be a composite number by this trial division, or if the prime number determination formula does not hold in any of the calculations, adjust the value of b as in b + = 1, and then perform the above series of processes again. Do it.

【0077】

Process 18: End if the generated prime number N has a predetermined bit length (step S37). If the predetermined bit length has not been reached, the process returns to process 17, and the value of b is adjusted like b + = 1 so that the prime number candidate N has a predetermined bit length, and the primality test is performed.

【0078】

Now, after the prime numbers are generated as described above, next, the public key and the private key are generated based on these prime numbers. Hereinafter, the generation of the public key and the private key in each encryption method will be described.

【0079】

When generating the public key and private key in RSA cryptography, two prime numbers p and q are generated using the above processing, n = pq is the public divisor, and ed = 1 (mod lcm (p-1, q). -1)) e and d are used as a secret index and a public index, respectively (lcm represents the least common multiple).

【0080】

Since the prime numbers p and q used in the public key and private key in Rabin cryptosystem have restrictions in equations (5) and (6), each of p and q is processed up to the above process 16 and then instead of process 17. The next process 17 ́ is performed.

【0081】

[Number 5]

<img file="JPH10240128A_D0005.tif" />【0082】

Processing 17 ́: p = 2F_p R_p +1, q = 2F_q R_q +1 , (p, q are n-bit prime candidates), F_p , F_q Is a 0.5n-bit prime number, R_p , R_q Is a 0.4n-bit random number. F_p , R_p Is each of the processes 17 (bs-r^-1 (mod s)), corresponds to r. F_p R_p And F_q R_q About 4 | F_p R_p -1, 4 | F_qR_q Find one that meets -3. Then, for p and q, the same processing as the trial division and judgment of the above processing 14, the calculation and judgment of the processing 15, and the calculation and judgment of the processing 16 is performed (steps S31 to S36).

【0083】

Using p and q generated in process 17 ́, let n = pq be a public divisor, and let e and d such that ed = 1 (mod (1/2) · lcm (p-1, q-1)) be, respectively. , Used as a secret index and a public index.

【0084】

The plum integer m = pq used in the public key cryptosystem has restrictions on the prime numbers p and q in equations (7) and (8), so F in the above process 17 ́_p R_p And F_q R_q About 2 | F_p R_p -1, 2 | F_q R_q Find one that meets -1. Then, for p and q, the same processing as the trial division and judgment of the above processing 14, the calculation and judgment of the processing 15, and the calculation and judgment of the processing 16 is performed (steps S31 to S36).

【0085】

[Number 6]

<img file="JPH10240128A_D0006.tif" />【0086】

The prime number required for the DSA key is that the prime number candidate is p = 2R in the above process 17 ́._p Generate a prime number q ́ so that qq ́ + 1, give p-1 two prime numbers, and perform a primality test. As a result, from p and q that satisfy q | p-1, g = h^{(p-1) / q}(mod p)&gt; 1 using g and random number x, y = g^x Calculate (mod p) and use p, q, g, y as the public key and x as the private key.

【0087】

As described above, according to the present embodiment, the deterministic primality test method and the prime number F₀ Is used to determine a prime number (F)₀ )^1/2 By combining with the prime number table that stores the following prime numbers, it is possible to use a table of a size corresponding to the memory capacity of the encryption device.

【0088】

Therefore, even if the cryptographic device has a limited memory capacity (for example, an IC card) instead of a cryptographic device such as a personal computer having abundant memory, the public key and the private key in public key cryptography can be easily installed on the device. It becomes possible to implement the generation function.

【0089】

Moreover, since the amount of data to be handled is small, the key can be generated at high speed. Moreover, since a deterministic primality test method is used, a prime number can be reliably obtained and a secure key can be obtained.

【0090】

In addition, a strong key can be obtained against attacks by prime factorization. Further, by providing the device with a key generation function, it is possible to improve the security of the key and facilitate the management of the key.

【0091】

Further, if the key is generated in each encryption device and the encryption processing and decryption processing are performed in the encryption device, the key never goes out of the encryption device, so that high security for the key can be maintained. ..

【0092】

In addition, instead of providing the prime number table in the memory 6 as described above, a prime number table equivalent may be created in the program. Further, in the present embodiment, the one that generates the private key and the public key in public key cryptography based on the prime number has been described, but the common key may be generated based on the prime number generated by the above-mentioned method. ..

【0093】

Next, the execution control of the key generation program will be described. In the encryption device 1, the key generation program is started, and once the key is generated, the key is stored in the non-volatile memory 7. In the present embodiment, at the same time, the key generation control bit also existing in the non-volatile memory 7 is set.

【0094】

The key generation control bit controls the execution of the key generation program. That is, before executing the key generation program, the key generation control bit is examined, and if the key generation control bit is in the off state, the key generation program is executed, and if it is in the on state, the key generation program is not started.

【0095】

As a result, it is possible to prevent the key generated by the encryption device 1 from being destroyed by restarting the key generation program or the like. As another method of controlling the execution of the key generation program, a method of starting the key generation program only when the same code as the secret authentication code stored in the encryption device 1 is input in advance can be considered. In this method, the authentication code is written in the mask or written in the initial stage at the time of issuance, and the same code is input at the later key generation to start the key generation program. This key generation program execution control method can also be used when changing an already generated encryption key. That is, the key generation program can be executed only when the correct authentication code is entered, and the generated encryption key can be stored in the non-volatile memory 7.

【0096】

Next, verification of the key stored in the encryption device 9 will be described with reference to FIG. First, when a key is generated, the hash value of the generated key is calculated immediately, and the generated key (11 in the figure) is associated with the hash value (10 in the figure) to be associated with the non-volatile memory. Save to 7.

【0097】

Then, before using the key in the encryption process, decryption process, or authentication process, the hash value of the key (11 in the figure) stored in the non-volatile memory 7 is calculated (12 in the figure), and the non-volatile memory is pre-calculated. The hash value (10 in the figure) stored in the memory 7 is compared with the match determination unit 13. If they match, a control signal indicating success is output to enable execution of encryption processing or decryption processing, and if they do not match, a control signal indicating failure is output to disable execution of encryption processing or decryption processing.

【0098】

Then, the encryption process is started only when the control signal is successful, that is, the hash value is matched, and the encryption process is not started when the control signal is unsuccessful, that is, the hash value is not matched.

【0099】

When performing encryption processing or decryption processing using the key generated by the encryption device 9 in this way, by verifying the stored key, encryption processing or decryption processing using the key destroyed for some reason can be performed. It can be avoided.

【0100】

Next, confirmation of the validity of the user's key between the user side and the center side that manages and publishes the public key will be described with reference to FIG. For the public and private keys generated by the cryptographic device 19, the center 17 needs a means to confirm their validity. As one of the methods, there is the method shown in FIG.

【0101】

First, the center 17 receives the public key k generated by the cryptographic device 19 from the information processing device 18. Next, the center 17 generates a random number R (20 in the figure), encrypts the random number R using the public key k generated by the encryption device 19 (21 in the figure), and transmits the random number R to the information processing device 18. (22 in the figure).

【0102】

The information processing device 18 transmits a random number R encrypted with the public key k to the encryption device 19 via the external interface 30. The encryption device 19 decrypts the random number R encrypted with the public key k using the private key paired with the public key (23 in the figure).

【0103】

The decrypted random number R is transmitted from the encryption device 19 to the center via the information processing device 18 (25 in the figure). Then, the center 17 verifies the random numbers generated by the match determination unit 26 and the random numbers transmitted from the encryption device 19.

【0104】

If they match, the cryptographic device 19 holds a valid private key for the public key owned by the center 17, and the center 17 issues a public key certificate to the cryptographic device 19.

【0105】

In this way, since each cryptographic device generates a private key and a public key, the center that manages the key does not need to generate and deliver the key to each cryptographic device, and the processing associated with the key generation and management. The burden on the user is reduced.

【0106】

It should be noted that the present invention is a computer-readable record of a program for causing a computer to perform a predetermined procedure (or for making the computer function as a predetermined means, or for causing a computer to perform a predetermined function). It can also be implemented as a medium. The present invention is not limited to the above-described embodiment, and can be implemented with various modifications within the technical scope thereof.

【0107】

[Effect of the invention]

According to the present invention, a prime number of 2 n bits or less is generated based on all prime numbers of a predetermined value of n bits or less, and a predetermined prime number is sequentially generated based on the generated prime number. Since a second prime number with a bit length is generated, the required memory capacity can be reduced.

【0108】

Therefore, it is possible to implement the key generation function in an encryption device having a limited memory capacity. Moreover, since the amount of data to be handled is small, the key can be generated at high speed.

【0109】

Further, since the key is generated in the encryption device without communication with the outside, the security of the key can be improved and the management of the key can be facilitated. Further, according to the present invention, when the key has already been generated in the encryption device, the key is not generated again, so that the already generated key is destroyed by the newly generated key. Can be prevented.

【0110】

Further, according to the present invention, when performing encryption processing or decryption processing using a key generated in a cryptographic device, encryption by a key destroyed for some reason is performed by verifying the stored key. Processing and decryption processing can be avoided.

[Simple explanation of drawings]

[Figure 1]

The figure which shows the structure of the encryption apparatus which concerns on one Embodiment of this invention. [Figure 2]

A flowchart showing a prime number generation procedure according to the same embodiment. [Fig. 3]

A flowchart showing a prime number generation procedure according to the same embodiment. [Fig. 4]

The figure which shows an example of the key verification in the encryption device which concerns on the same embodiment. [Fig. 5]

The figure which shows an example of the correctness verification of the key which concerns on the same embodiment. [Explanation of symbols]

1 ... Cryptographic device 2 ... CPU 3 ... Program storage 4 ... Arithmetic unit 5 ... Random number generator 6 ... Randomly accessible non-volatile memory 7 ... Non-volatile memory 8 ... Bus 9 ... Cryptographic device 12 ... Hash value calculation unit 13,26 ... Match judgment unit 17 ... Center 18 ... Method processing equipment 19 ... Cryptographic device