JP2001154580A - Prime number generation method and apparatus, and storage medium storing prime number generation program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a prime number generation method and apparatus capable of guaranteeing uniqueness of a large number of generated prime numbers and reducing the amount of memory used therefor, and a storage medium storing a prime number generation program. provide. The present invention provides a storage area having a length of k bits and m bits, wherein k is a positive integer, m is a positive integer less than k, w is a positive integer less than 2 ^m. In the case of preparing, an initial value given in advance is set in an m-bit storage area, the cycle is w, and the value range is {1, 2,.
^m- 1} is calculated, and when a request for generation of a prime number is received from the outside via the communication means, the next value of the input value in the sequence is calculated using the m-bit storage area as an input value, and m
The bit value is copied to a predetermined location in a k-bit storage area, a km-bit random number is generated, and the remaining k-m bits in the k-bit storage area are copied to a k-bit integer. And if it is a prime, the k-bit data is returned to the outside via the communication means. If it is not a prime, a random number is generated again.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and an apparatus for generating prime numbers and a storage medium storing a program for generating prime numbers, and more particularly to a method and apparatus for generating prime numbers used in cryptography and a storage medium storing a program for generating prime numbers. .

[0002]

2. Description of the Related Art An encryption technique is effective for concealing data. Data encryption includes common key encryption and public key encryption. In public key cryptography, a key for encrypting data and a key for decrypting data are different. Usually, a key used for encryption is made public, and a key used for decryption is kept secret by a user. Determining a key for decryption from a publicly available key for encryption is believed to be incomplete in a practical time even with current mathematical theories and the computing power of the computer.

There are several concrete methods for realizing public key cryptography having the above properties.
There is SA encryption. The RSA cipher was first announced as a public key cipher in 1977, and uses the difficulty of factorization as the basis for security (Okamoto, Yamamoto, "Hyundai Cipher",
See Industrial Books, p. 110, 1997). The difficulty of prime factorization means that when there are prime numbers p and q, it is easy to perform multiplication n = qp, but conversely it is difficult to find p and q from n. As the number of digits of n increases, the calculation time required increases. For example, in order to factorize a 129-digit number that is a result of multiplying a 64-digit and a 65-digit prime, 1 is required.
It has been reported that 600 computers were used for eight months in 994 (see Okamoto and Ota, ed., "Cryptography / Zero Knowledge Proof / Number Theory", Kyoritsu Shuppan, p.150, 1995). In addition, public key cryptography based on the difficulty of the discrete logarithm problem has been proposed, but the public key cryptography based on the difficulty of factorization is most used because it is easy to handle.
SA encryption is most often used.

Since the RSA encryption is based on the security of the factorization as described above, if the factorization of n is successful, the ciphertext using the n is decrypted by a third party. I will. Therefore, the factorization of n must be difficult. Among existing prime factorization methods, many of the methods that may be used to break the RSA encryption take processing time in proportion to the bit size of the prime factor. Therefore, even if n is 1024 bits, if p is 24 bits and q is 1000 bits, there is a high possibility that factorization is performed because p is small in size. Therefore, the size of n is 1024
If it is a bit, it is recommended that each of p and q is set to about 512 bits.

[0005] In general, when p and q are prime numbers and the bit size of n = pq is 1 (el), "l (el) bits RS
It is called "A cipher". At present, 1024 bits are recommended for commercial purposes, and 2048 bits are recommended in situations requiring higher security such as military purposes. Therefore, it is required that the prime numbers have a length of 512 bits or 1024 bits.

In order to generate a prime number, first, a random number is generated, an odd number having a required bit size is obtained, and it is checked whether the value is a prime number. If the determination of the prime number fails, another odd number is generated again by a random number, and the inspection is continued. There are several methods for determining the prime number, for example, the Rabin method (Rabin, MO, "Probabilistic Alg
orithm for Testing Primality, "J.Number Theory 12,
pp.128-138, 1980).

Further, the prime number is guaranteed to exist infinitely by the prime number theorem, and the process ends in a finite number of times if the next candidate when the determination fails is appropriately selected (for the prime number theorem, see Mathematics Seminar Readings, World of Numbers, Nihon Hyoronsha, p. 97, 1982). Here, a deterministic method is often used to generate random numbers. That is, the initial values of the random number sequence, generating a sequence {r _n} using a function f with that value.

[0008]

However, when a prime number is generated by the above-described method and an encryption key is created, there are the following problems. In other words, when a large number of encryption keys must be created in a certain network system,
It is necessary to guarantee the uniqueness of the encryption key. If the same prime is generated, the random numbers used in the process may be the same, and if the random number generation is deterministic, the subsequently generated primes may also be the same Therefore, it is possible that the same RSA encryption key results. In such a situation, if the key is used for cryptographic processing, there is a risk that others will be able to decrypt the ciphertext, and if it is used for signature processing, impersonation to others is possible as a result. Become. In particular, if the signature key is duplicated inside the system, the reliability is not satisfied even if encryption processing is used as a means for confirming the identity. Performing electronic commerce or the like requires a secure identity check, that is, the system is required to avoid duplication of keys.

SUMMARY OF THE INVENTION The present invention has been made in view of the above points, and provides a method and apparatus for generating prime numbers and a prime number capable of guaranteeing the uniqueness of a large number of generated prime numbers and reducing the amount of memory used therefor. It is an object to provide a storage medium storing a generation program.

[0010]

FIG. 1 is a diagram for explaining the principle of the present invention. The present invention (claim 1) provides a prime generation method for generating a prime used in a cryptographic technique for concealing data, wherein k is a positive integer,
When m is a positive integer less than k, w is a positive integer less than 2 ^m, and a storage area having a length of k bits and m bits is prepared, the storage area of m bits is given in advance. An initial value is set (step 1), a sequence having a period of w and a range of {1, 2,..., 2 ^m -1} is calculated (step 2), and a request for generation of a prime number from outside via a communication means is made. (Step 3), the next value of the input value in the sequence is calculated using the m-bit storage area as an input value (step 4), and the m-bit value is transferred to a predetermined location in the k-bit storage area. Copy (step 5), generate a random number of km bits, and store the remaining km within the k-bit storage area.
Is copied to bits (step 6), and is judged as a k-bit integer to determine a prime number (step 7).
The k-bit data is returned to the outside via the communication means (step 8), and if it is not a prime number, a random number is generated again (step 6).

According to the present invention (claim 2), n is a positive integer equal to or less than k, and m + n <k is satisfied.
In the case of preparing a storage area having a length of n bits and n bits, respectively, an initial value given in advance is set in the storage area of n bits, and the calculated value of n bits is replaced with a predetermined value of the storage area of k bits. To generate a km-n-bit random number, copy it to the remaining km-n-bit of the k-bit storage area, and perform a prime number judgment by regarding it as a k-bit integer. If it is a prime number, the k-bit data is returned to the outside via the communication unit. If it is not a prime number, the process of generating a random number is repeated.

FIG. 2 is a diagram showing the principle of the present invention. The present invention (claim 3) is a prime number generation device for generating a prime number used in encryption technology for concealing data, where k is a positive integer and m is a positive integer less than k. , W
Was a positive integer less than 2 ^m, in the case of preparing the storage area 1 ₁ having a length of k bits and m bits, 1 _2, respectively, set the initial value given in advance in the storage area 1 ₂ m-bit Initial value setting means 2 for performing calculation, a calculating means 3 for calculating a sequence having a period w and a range of {1, 2,..., 2 ^m -1}, and a request for generating a prime number from outside via a communication means. If it is received, the next value of the input value in the above sequence is calculated using the m-bit storage area as the input value, and the m-bit value is calculated as
and copying means (4) for copying the k bits of the storage area 1 ₁ of a predetermined location, to generate a k-m bit random number, among the storage region of k bits, then copied to the remaining k-m bits, k
There is a random number generating means 5 which performs a prime determination assuming that it is a bit integer, returns the k-bit data to the outside via a communication means if it is a prime number, and generates a random number again if it is not a prime number.

According to a fourth aspect of the present invention, there is provided a prime number generating apparatus for generating a prime number used in an encryption technique for concealing data, wherein n is a positive integer equal to or less than k, and m +
initial value setting means for setting an initial value given in advance to the n-bit storage area when n <k is satisfied and a storage area having a length of k bits of m bits and n bits is prepared. , The calculated n-bit value to k
A copy means for copying to a predetermined location in the bit storage area, generating a kmn bit random number, and copying to the remaining kmn bits in the k bit storage area;
A prime number determination is performed assuming that the integer is a bit, and if it is a prime number, the k-bit data is returned to the outside via the communication unit.
If it is not a prime number, there is provided a random number generating means for generating a random number again.

The present invention (claim 5) is a storage medium storing a prime generating program for generating a prime used in encryption technology for concealing data, wherein k is a positive integer, m Is a positive integer less than k, w is a positive integer less than 2 ^m, and a storage area having a length of k bits and m bits is prepared. An initial value setting process for setting a value, a calculation process for calculating a sequence having a period of w and a range of {1, 2,..., 2 ^m -1}, and a request for generation of a prime number from outside via a communication process. A copy process of calculating the next value of the input value in the above sequence using the m-bit storage area as an input value, and copying the m-bit value to a predetermined location in the k-bit storage area; -Generate an m-bit random number , The remaining k-m bits of the k-bit storage area are copied, and a prime number is determined by considering the k-bit integer. If it is a prime number, the k-bit data is returned to the outside via a communication process. , If not a prime,
And a random number generation process for generating random numbers again.

The present invention (claim 6) is a storage medium storing a prime generating program for generating a prime used in encryption technology for concealing data, wherein n is k
The following positive integer shall satisfy m + n <k, and k
An initial value setting process of setting an initial value given in advance to the n-bit storage area when preparing storage areas each having a length of m bits and n bits of bits;
A copy process of copying the calculated n-bit value to a predetermined location in a k-bit storage area; generating a km-n-bit random number; -Copy to n bits, judge it as a k-bit integer, judge a prime number. If it is a prime number, return the k-bit data to the outside via the communication unit. If it is not a prime number, generate a random number again. Process.

As described above, when an m-bit sequence is used as the sequence {s _i }, the individual values are 0 to 2 ^m
2 ^m patterns up to -1 are conceivable. The period of this sequence is w
And At this time, sequence generated using the initial value s _1, when put i-th values as s _i, values of up to s _w are all different values. By considering each s _i as part of a prime number, it is possible to guarantee that the values returned by this device are not duplicated for the first w values.

Next, regarding the storage capacity, this sequence is:
By using the value s _i-1 immediately preceding, the following values s _i is obtained. Therefore, the value s _i-1 of the immediately preceding sequence may be stored. Therefore, irrespective of the number of generated prime numbers, m bits are sufficient for the storage area. Generally, in order to ensure uniqueness, a previously generated prime number and an encryption key generated from the prime number are stored in a storage device, and the uniqueness is determined by comparing the generated key with a previously generated one. Can be performed, but as the number of storages increases,
According to the present invention, the search time is increased. However, according to the present invention, the value of a sequence that can obtain the next value from the immediately preceding value is a part of a prime number. Without storing the generated prime numbers, it is possible to ensure uniqueness and prevent an increase in the storage device and generation time.

[0018]

FIG. 3 shows a configuration of a prime number generating apparatus according to the present invention. The prime number generation device shown in FIG.
Data storage unit 20, communication units 30, 50, arithmetic operation unit 40
Consists of In the figure, a dotted frame indicates the control unit 10.
Is a range in which each processing unit in the processing of the present invention is controlled.

The arithmetic operation unit 40 generates a random number, LFSR
Performs the Rabin method of calculating the prime number and determining the prime number. A linear feedback shift register (hereinafter, LFSR) is used to generate a sequence performed by the arithmetic operation unit 40. LFS
R is an algorithm for generating a sequence, and outputs the next value by inputting the immediately preceding value in the sequence. The LFSR for inputting / outputting an m-bit number outputs a value from 1 to 2 ^m -1 and its cycle is 2 ^m -1. Note that L
For the structure of the FSR, see Bruce Schneier, Applied
Cryptography, 2nd edition, John-Wiley and Sons, p.
372, 1996 ".

The data storage unit 20 stores the LFSR
Previous output value or initial value s _i-1Is stored.
At the end of processing, output data s_iIs stored. The above configuration
The arithmetic operation unit 40 in FIG.
Each of the stage 2, the calculating means 3, the copying means 4, and the random number generating means 5
Including means. In the arithmetic operation unit 40, k is a positive integer.
And m is a positive integer less than k and w is 2^mLess than positive integer
U is an integer greater than or equal to 0, and v is an integer greater than or equal to 0.
It is assumed that u + v = km is satisfied. m-bit number
s₁Is the initial value of the sequence, and when the system is first started
And the initial value s₁Is set. Also, each of the sequence
Has a length of m bits.

When the arithmetic operation unit 40 acquires a request for generating a prime number via the communication unit 30, first, the value s _i-1 of the immediately preceding sequence is obtained.
, The next value m-bit number s _i is obtained. Then generates a random number r _u and v-bit random number r _v of u bits. Then, as the number of k bits, the ^{_{R = r u 2 m + v}} + s i 2 v + r v. Each value on the right side is u, m, v bits, and u + v + m = k.

Finally, it is verified whether or not R is a prime number by using the Rabin method. If R is a composite number,
Generation of random number r _v, or again perform the above process returns to the generation of the random number r _u. However, re-generation of the s _i is not performed.
If R is a prime number, this value is returned to the outside via the communication unit 50.

[0023]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 4 shows an internal configuration of a k-bit prime in one embodiment of the present invention, and FIG. 5 shows an internal configuration (including a unique value) of a k-bit prime in one embodiment of the present invention. In FIG. 4, LFS
The configuration when the output value of R is embedded in a part of the random number is shown. Generally, when generating a k-bit prime number,
A value having a length of truly k bits, that is, a value in which 1 stands in the most significant bit, is obtained. Therefore, in FIGS. 4 and 5,
Each has a 1 in the most significant bit.

There is no particular limitation on in which part of the prime number R the LFSR output value is embedded. Also, instead of embedding as one integrated part, it may be decomposed into several parts and embedded in R. However, in the vicinity of the least significant bit, as shown by the random number part (r _v ) of the v-bit sentence in the drawing, it is recommended to embed a random number component as one unit as a reliable prime number generation. .
That is, according to the prime number theorem, for example, in the case of 512 bits, the probability is a prime number from about 500 minutes of 1, v around the relatively large take in Aru value r ⁰ _v a, r ⁰ _v ± M
(Where M is a positive integer), the probability that a prime number falls within the search range increases as a result.

In FIG. 5, not only the output of the LFSR but also a unique value is embedded in R. This is effective when there are a plurality of servers that generate prime numbers and encryption keys composed of prime numbers in a certain network system, and the system must guarantee uniqueness of prime numbers and encryption keys. As the unique value, for example, a server manufacturing ID may be assigned. Also in this case, as described above, instead of embedding the unique value as a single unit, it may be divided into several parts and embedded in R.

As an example, k = 512, m = 64, n = 3
2, v = 352, and the LFSR performs 64-bit input / output. As a result, first, as a unique value

[0027]

(Equation 1)

Can be inserted. In this field, for example, a server manufacturing ID can be entered. The output bits of the LFSR are m = 64 bits. Therefore,

[0029]

(Equation 2)

The generation of a number of different prime numbers can be guaranteed. At system startup, you have specified defines the initial value s _1. When there is a request for prime generation, first, obtain a new output value s _i from the output value s _i-1 of the immediately preceding use the LFSR. At the same time storing them in the data storage unit 20 copies the s _i in position of R. Also, the 32-bit unique value is copied to an appropriate position of the same R.

For the remaining u-bit area and v-bit area, u-bit and v-bit random numbers (r _u ,
r _v ) and copy it in place. here,
As in Figure 5, a region to copy r _v is a region including the lowest R as portion collectively of one. However, in these processes, the most significant bit of R is set to 1. Since prime numbers are odd except for 2, the least significant bit is also set to 1 similarly.

Therefore, it may be assumed that the least significant bit of the random number r _v copied to the v-bit area is always “1”. The obtained R is subjected to a prime number test using the Rabin method. If it is determined to be a composite number,
Rv is _incremented by 2, or 2 is subtracted to represent an adjacent odd number, and is copied again to a v-bit area.
Is repeated for the prime number judgment by the Rabin method. Here, if 2 is added to or subtracted from R itself, carry up or carry down may affect the area for m bits or the area for n bits. It should be limited to an area of v bits. Also, as a result of performing such an operation, r
_{If v} exceeds v bits or becomes negative, 2
An operation such as subtracting ^v or adding 2 ^v is performed to keep the value in the range of 1 to 2 ^v −1. If it passes the prime number test, return R.

Further, according to the present invention, the operation of the arithmetic operation unit 40 is a process of setting an initial value in a k-bit and m-bit storage area as shown in the flowchart of FIG.
Process of calculating a sequence whose value range is {1, 2,..., 2 ^m -1}, and calculating the next value of the input value in the sequence calculated using the m-bit storage area as an input value at the time of a prime number generation request Then, a process of storing the calculated value of m bits in the storage area of m bits, a process of copying the calculated value of m bits to the storage area of k bits, and generating a random number of k−m bits. It consists of a process of copying to the remaining km-bit area, a process of outputting k-bit data as a prime if it is a prime, and a process of generating a random number again if it is not a prime. Build a program. Further, a disk device connected to a computer that uses the program as a prime number generating device, a floppy disk, a CD-R
The present invention can be easily realized by storing it in a portable storage medium such as OM and installing it when implementing the present invention.

It should be noted that the present invention is not limited to the above-described embodiment, and various modifications and applications are possible within the scope of the claims.

[0035]

As described above, according to the present invention, it is possible to reduce the used storage area while easily assuring the uniqueness of the generated prime numbers in the prime number generation processing mainly used in the encryption technology. it can.

[Brief description of the drawings]

FIG. 1 is a diagram for explaining the principle of the present invention.

FIG. 2 is a principle configuration diagram of the present invention.

FIG. 3 is a configuration diagram of a prime number generation device of the present invention.

FIG. 4 shows an internal structure of a k-bit prime number according to an embodiment of the present invention.

FIG. 5 shows an internal structure (including a unique value) of a k-bit prime number according to an embodiment of the present invention.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 Storage area 1 ₁ k-bit storage area 1 ₂ m-bit storage area 2 Initial value setting means 3 Calculation means 4 Copy means 5 Random number generation means 10 Control unit 20 Data storage unit 30, 50 Communication unit 40 Arithmetic operation unit

Claims (6)

[Claims] 1. A prime generation method for generating a prime used in encryption technology for concealing data, wherein k is a positive integer, m is a positive integer less than k, and w is 2
^When a storage area having a length of k bits and m bits is prepared as a positive integer less than ^m , a predetermined initial value is set in the storage area of m bits, and the period is w and the range is 域1, 2,..., 2 ^m -1}, and when a request for generation of a prime number is received from outside via a communication means, an m-bit storage area is used as an input value and the next input value in the sequence is calculated. Is calculated, the m-bit value is copied to a predetermined location in a k-bit storage area, a random number of km is generated, and the remaining km bits of the k-bit storage area are calculated. It is copied and regarded as a k-bit integer, and a prime determination is performed. If the prime is a prime, the k-bit data is returned to the outside via the communication means. If the prime is not a prime, a random number is generated again. Prime number generation method. 2. n is a positive integer equal to or less than k, and m + n <k
In the case of providing a storage area having a length of k bits of m bits and n bits, a predetermined initial value is set in the storage area of n bits, and the calculated value of n bits Is copied to a predetermined place in a k-bit storage area, a km-n-bit random number is generated, and the remaining k-mn bits in the k-bit storage area are copied, and 2. The prime number generation method according to claim 1, wherein the prime number is determined as an integer, and if it is a prime number, the k-bit data is returned to the outside via a communication unit, and if not, a random number is generated again. 3. A prime generating apparatus for generating a prime used in a cryptographic technique for concealing data, wherein k is a positive integer, m is a positive integer less than k, and w is 2
^When a storage area having a length of k bits and m bits is prepared as a positive integer less than ^m, initial value setting means for setting an initial value given in advance to the storage area of m bits; a calculating means for calculating a sequence having a range of {1, 2,..., 2 ^m -1} at w; Calculating means for calculating the next value of the input value in the above sequence, and copying the m-bit value to a predetermined location in a k-bit storage area; generating a k-m-bit random number; In the storage area, the remaining k-m bits are copied, and a prime determination is performed assuming that the k-bit is an integer. If the prime is a prime, the k-bit data is returned to the outside through the communication means and must be a prime. If you want to generate random numbers again, Prime generating apparatus characterized by having and. 4. A prime number generation device for generating a prime number used in encryption technology for concealing data, wherein n is a positive integer equal to or less than k, m + n <k is satisfied, and k bits When each of the storage areas having the length of m bits and n bits is prepared, initial value setting means for setting a predetermined initial value in the storage area of n bits; copy means for copying to a predetermined location in a k-bit storage area; generating km-n-bit random numbers; and copying to the remaining km-n bits in the k-bit storage area, And a random number generating means for returning the k-bit data to the outside via the communication unit if the prime number is a prime number, and generating a random number again if the prime number is not a prime number. Prime number generator. 5. A storage medium storing a prime generation program for generating a prime used in a cryptographic technique for concealing data, wherein k is a positive integer, and m is a positive integer less than k. And w is 2
^When a storage area having a length of k bits and m bits is prepared as a positive integer less than ^m, an initial value setting process of setting a predetermined initial value in the storage area of m bits; Is a calculation process that calculates a sequence with a range of {1, 2,..., 2 ^m -1}, and when a request for generating a prime number is received from outside via a communication process, a storage area of m bits is input. A copy process of calculating the next value of the input value in the above sequence as a value and copying the m-bit value to a predetermined location of a k-bit storage area; generating a k-m-bit random number; Is copied to the remaining km bits of the storage area, and the prime number is determined by considering the integer as a k-bit integer. If the prime number is a prime number, the k-bit data is returned to the outside via a communication process, and the prime number is determined. If not, re-ran Storage medium storing a prime number generation program, characterized in that it comprises a random number generation process to perform generation. 6. A storage medium storing a prime generating program for generating a prime used in a cryptographic technique for concealing data, wherein n is a positive integer equal to or less than k and m + n <k is satisfied. In the case where a storage area having a length of k bits of m bits and n bits is prepared, an initial value setting process of setting a predetermined initial value to the storage area of n bits; A copy process of copying a bit value to a predetermined location in a k-bit storage area, generating a km-n-bit random number, and replacing the remaining km-n-bit in the k-bit storage area A random number generation process of performing a prime number judgment by considering the copied data as a k-bit integer, returning the k-bit data to the outside via the communication unit if the data is a prime number, and generating a random number again if the data is not a prime number. Storage medium storing a prime number generation program characterized Rukoto.