Prime number generation apparatus B-smoothness judgement apparatus and computer memory product

• US 6,330,332 B1
• Filed: 03/10/1998
• Issued: 12/11/2001
• Est. Priority Date: 07/30/1997
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Itoh, Koichi, Takenaka, Masahiko, Torii, Naoya, Yokoyama, Kazuhiro
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): KABAKOFF, STEPHEN ERIC
• Application Number:
  US09/037,853
• Time in Patent Office: 1,372 Days
• Field of Search: 380/28, 380/1, 380/44, 380/30
• US Class Current: 380/28
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

One or a plurality of prime numbers p_i which are generated and a generated random number are used to calculate a larger prime number candidate, and a judgment is made as to whether or not the prime number candidate is a prime number by using a provable prime number judging method, and when the judgment is made that the candidate is a prime number, the prime number p is outputted. As for at least three polynomials F(p) which are factors of p^s−1 (s: arbitrary natural number) by a prime number p, a measure against prime factorization is taken. Moreover, when the prime number p is used for a secret key of RSA cryptosystem, a strong prime number p against the iterated-encryption attack on RSA cryptosystem is generated.

Claims

1. A prime number generation apparatus for generating a prime number larger than a predetermined prime number by using one or a plurality of prime numbers and a random number, comprising:

means for generating a random number;

means for obtaining a prime number candidate by using the generated random number and one or a plurality of prime numbers;

means for judging as to whether or not the obtained prime number candidate is a prime number by using a provable prime number judging method;

means for taking a measure to at least three polynomials F(p) which are prime factors of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) by a prime number p against prime factorization for obtaining p and q from n when n=pq (p and q are prime numbers);

means for determining a maximum order of the polynomial F(p) to which a measure should be taken and means for giving a prime factor larger than a prescribed value to the polynomial F(p) whose order is not more than the determined order;

wherein

said means for determining includes means for determining the size of each prime number included in the polynomials F(p), according to computational complexity required for the prime factorization using the respective polynomials F(p) as for the polynomials F(p) to which a measure should be taken, and means for obtaining respective prime numbers according to the determined respective sizes,

wherein when a prime number p of 512 bits is to be generated, p−

1, p+1, p²+p+1, p²+1 and p²−

p+1 which are the polynomials F(p) to which a measure should be taken have prime factors of 260, 51 50, 49, 48 bit respectively.

2. A prime number generation apparatus for generating a prime number larger than a predetermined prime number by using one or a plurality of prime numbers and a random number, comprising:

means for generating a random number;

means for obtaining a prime number candidate by using the generated random number and one or a plurality of prime numbers;

means for judging as to whether or not the obtained prime number candidate is a prime number by using a provable prime number judging method;

means for taking a measure to at least three polynomials F(p) which are prime factors of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) by a prime number p against prime factorization for obtaining p and q from n when n=pq (p and q are prime numbers);

means for determining a maximum order of the polynomial F(p) to which a measure should be taken and means for giving a prime factor larger than a prescribed value to the polynomial F(p) whose order is not more than the determined order;

wherein

said means for determining includes means for determining the size of each prime number included in the polynomials F(p), according to computational complexity required for the prime factorization using the respective polynomials F(p) as for the polynomials F(p) to which a measure should be taken, and means for obtaining respective prime numbers according to the determined respective sizes,

wherein when a prime number p of 1024 bits is to be generated, p−

1, p+1, p²+p+1, p²+1 and p²−

p+1 which are the polynomials F(p) to which a measure would be taken have prime factors of 515, 110, 109, 108 and 107 bits, respectively.

3. A prime number generation apparatus for generating a prime number p used for a secret key of an RSA cryptosystem, comprising:

calculation means for calculating a prime number candidate by using one or a plurality of prime numbers and a random number;

prime number judging means for judging as to whether or not the calculated prime number candidate is a prime number by using a provable prime number judging method; and

strength judging means for judging the strength of the number judged as a prime number against iterated-encryption attack on RSA cryptosystem,

wherein said strength judging means includes means for judging as to whether or not the following conditions are satisfied when numbers p and q judged as prime numbers are represented by p=2h_pp₁+1(h_p<

p₁, p₁;

prime number) and q=2h_qq₁+1(h_q<

q₁, q₁;

prime number);

1. p′

₁ and q′

₁ which satisfy p₁=2p′

₁+1 and q₁=2q′

₁+1 are prime numbers;

2. h_p and h_q are prime numbers;

3. as for x_p, y_p, x_q, y_q≧

1

prime numbers h′

_p and h′

_q which satisfy h_p=2^xp3^yph′

_p+1,h_q=2^xq3^yqh_q′

+1 exist; and

4. As for an encryption key e of RSA cryptosystem,

4. A prime number generation apparatus comprising:

means for taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number; and

means for determining the bit length of a prime number to be given to F(p) in view of a difference in the computational complexity required for the respective prime factorization methods, when the respective polynomials F(p) except for p−

1 have prime factors of the same bit length.

5. The prime number generation apparatus of claim 4, further comprising:

calculation means for calculating a probability that a prime factor of polynomial F(p) does not exceed a first prescribed value; and

judging means for judging that a measure should be taken to deal with a polynomial F(p) in which the calculated probability exceeds a second prescribed value.

6. The prime number generation apparatus of claim 5, wherein said calculation means further comprises:

first means for calculating the number of values composed of the product of prime numbers not larger than the first prescribed value included in the range of polynomial F(p) which is determined according to the range into which the prime number p falls; and

second means for calculating a probability that a prime factor of polynomial F(p) does not exceed the first prescribed value by dividing the number that is calculated by said first means by F(p_max)−

F(p_min).

7. A prime number generation apparatus of claim 5, wherein the second prescribed value is 1/p^0.5.

8. A computer readable storage medium, storing a program to instruct a computer to perform:

taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number; and

determining the bit length of a prime number to be given to F(p) in view of a difference in the computational complexity required for the respective prime factorization methods, when the respective polynomials F(p) except for p−

1 have prime factors of the same bit length.

9. The computer readable storage medium recited in claim 8, further performing:

calculating a probability that a prime factor of polynomial F(p) does not exceed a first prescribed value; and

judging that a measure should be taken to deal with a polynomial F(p) in which the calculated probability exceeds a second prescribed value.

10. The computer readable storage medium recited in claim 9, wherein said calculating further comprises:

calculating the number of values composed of the product of prime numbers not larger than the first prescribed value included in the range of polynomial F(p) which is determined according to the range into which the prime number p falls; and

calculating a probability that a prime factor of polynomial F(p) does not exceed the first prescribed value by dividing the number that is calculated by said first means by F(p_max)−

F(p_min).

11. The computer readable storage medium recited in claim 9, wherein the second prescribed value is 1/p^0.5.

12. A method comprising:

taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;

determining the bit length of a prime number to be given to F(p) in view of a difference in the computational complexity required for the respective prime factorization methods, when the respective polynomials F(p) except for p−

1 have prime factors of the same bit length; and

using the determining in order to improve encryption security.

13. The method recited in claim 12, further performing:

calculating a probability that a prime factor of polynomial F(p) does not exceed a first prescribed value; and

judging that a measure should be taken to deal with a polynomial F(p) in which the calculated probability exceeds a second prescribed value.

14. The method recited in claim 13, wherein said calculating further comprises:

calculating the number of values composed of the product of prime numbers not larger than the first prescribed value included in the range of polynomial F(p) which is determined according to the range into which the prime number p falls; and

calculating a probability that a prime factor of polynomial F(p) does not exceed the first prescribed value by dividing the number that is calculated by said first means by F(p_max)−

F(P_min).

15. The method recited in claim 13, wherein the second prescribed value is 1/p^0.5.

16. A prime number generation apparatus comprising:

means for taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;

said means including;

a first means for calculating an evaluation value for probability that the prime factor of F(p) does not exceed a first prescribed value determined in advance, by carrying out a first step of calculating, from the equation v=(F(p_max)−

F(p_min))*exp(−

uln(u)), the number v of natural numbers included in a range having prime factors smaller than the first prescribed value in which p_max and p_min are the maximum value and the minimum value of p respectively, u=t*p_b/log₂ B holds and t is the order of the polynomial F(p), p_b is the bit length of the prime number p to be generated and B is the first prescribed value, and by carrying out a second step of calculating v/(p_max−

p_min) to obtain an evaluation value for probability; and

a second means for taking a measure against F(p) whose obtained evaluation value for probability exceed a second prescribed value determined in advance.

17. The prime number generation apparatus of claim 16, wherein the second prescribed value is 1/p^0.5.

19. The prime number generation method of claim 16, wherein the second prescribed value is 1/p^0.5.

18. A prime number generation method comprising:

taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;

said taking a measure including;

calculating an evaluation value for probability that the prime factor of F(p) does not exceed a first prescribed value determined in advance, by carrying out a first step of calculating, from the equation v=(F(p_max)−

F(p_min))*exp(−

uln(u)), the number v of natural numbers included in a range having prime factors smaller than the first prescribed value in which p_max and p_min are the maximum value and the minimum value of p respectively, u=t*p_b/log₂ B holds and t is the order of the polynomial F(p), p_b is the bit length of the prime number p to be generated and B is the first prescribed value, and by carrying out a second step of calculating v/(p_max−

p_min) to obtain an evaluation value for probability; and

taking a measure against F(p) whose obtained evaluation value for probability exceed a second prescribed value determined in advance.

20. A computer readable storage medium storing a program to perform a prime number generation method, said program performing:

taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of p^s−

1 (s;

any arbitrary natural number which is set so that p^s−

1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;

said taking a measure including;

calculating an evaluation value for probability that the prime factor of F(p) does not exceed a first prescribed value determined in advance, by carrying out a first step of calculating, from the equation v=(F(p_max)−

F(p_min))*exp(−

uln(u)), the number v of natural numbers included in a range having prime factors smaller than the first prescribed value in which p_max and p_min are the maximum value and the minimum value of p respectively, u=t*p_b/log₂ B holds and t is the order of the polynomial F(p), p_b is the bit length of the prime number p to be generated and B is the first prescribed value, and by carrying out a second step of calculating v/(p_max−

p_min) to obtain an evaluation value for probability; and

taking a measure against F(p) whose obtained evaluation value for probability exceed a second prescribed value determined in advance.

21. The computer readable storage medium of claim 20, wherein the second prescribed value is 1/p^0.5.