Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-03-10
2001-12-11
Decady, Albert (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S030000, C380S044000, C380S001000
Reexamination Certificate
active
06330332
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a prime number generation apparatus for generating prime numbers to be strong public keys in cipher communication, for example, and relates to a B-smoothness judgment apparatus.
2. Description of the Prior Art
In cryptosystem such as a RSA cryptosystem whose security is based on the difficulty of factoring, it is difficult due to computational complexity to obtain prime factors p and q which satisfies n=pq (n is public) in the case where n is about 1024 bits. Moreover, it is a condition of security in cryptography that an attacker cannot obtain p and q from n. Therefore, the security in the cipher communication depends on the quality of the prime numbers p and q to be generated (whether or not they are easily solved into prime factors).
In a conventional method, since prime numbers are generated by using the probable primality test method such as Miller-Rabin, composite numbers which are not prime numbers may be possibly generated in very low probability.
According to “Cryptographic Theory” (written by Eiji Okamoto, published by Kyoritsu Shuppan), etc., in the case where with respect to the prime number p, p−1 or p+1 is the product of only small prime numbers, n can be solved into prime factors comparatively easily by prime factorization algorithm such as a p−1 method or p+1 method. Therefore, in the conventional prime number generating method, a measure is taken to cope with the prime factorization in such a manner that large prime factors p
1
and p
2
are given respectively to p−1 and p+1.
Further, the encryption is repeated u-times so that a cipher text X
e
(X: plain text, e: encryption key) of RSA cryptosystem is encrypted into X
e
, (X
e
)
e
, ((X
e
)
e
)
e
, . . . , and thus a plain text X is obtained as represented by the following equation (1). This attack, namely, iterated encryption attack is known. In the conventional prime number generating method, a measure is taken to cope with such an attack in such a manner that a large prime number p
1
′ is included in p
1
−1 as for a large prime factor p
1
included in p−1.
X
e
u
≡X
(mod
n
) (1)
In addition, as a concrete conventional example of the prime number generating method, the following method is known. U.S. Pat. No. 4,633,036 discloses a probable prime number generating method in which p−1 and p+1 respectively include large prime numbers p
1
and p
2
, p
1
−1 and p
2
−1 respectively include large prime numbers p
1
′ and p
2
′, and a total bit lengths of p
1
and p
2
cannot exceed a bit length of p. Moreover, Japanese Patent Application Laid-Open 0-73269 (1997) discloses a probable prime number generating method in which p−1 and p+1 respectively include large prime numbers p
1
and p
2
, p
1
−1 includes a large prime number p
1
′ and bit lengths of p
1
and p
2
exceed ½ of the bit length of p.
The conventional prime number generating method has the following problems which is to be solved by the present invention.
(Problem 1) In the conventional prime number generating method, a composite number is generated in very low probability.
(Problem 2) In the conventional method, p−1 and p+1 include large prime numbers, but besides that it is known that in the case where one of the polynomial F (p) which is a factor of p
s
−1 (s: arbitrary integer) such as p
2
+p+1, p
2
−p+1, . . . is composed of the product of only small prime numbers, the prime factors can be solved comparatively easily. Here, a number composed of the product of prime numbers not larger than integer B is called B-smooth. In other words, that F(p) is not B-smooth with respect to a small B is a measure to cope with the prime factorization utilizing F(p). However, in the conventional method, since what integer B in t-polynomial F(p) becomes B-smooth is not considered, there is such a problem that a maximum order of F(p) to which a measure is taken is not found. In order to check as to whether or not F(p) is B-smooth, F(p) is practically divided by a prime number not larger than B many times, but in the case where a judgment is made whether or not a certain F(p) is B-smooth, when B is large, prime number data become enormous and thus a lot of time is required. Namely, it takes time to judge whether or not F(p) is B-smooth, and it is very difficult to factorize an arbitrary F(p) into prime factor as long as a maximum order of F(p) to which a measure is taken is not found. Because of these, in the conventional method, the measure of the prime factorization is taken to F(p)=p−1, p+1, but the measure is not taken to F(p) of the second order or higher.
(Problem 3) In the conventional prime number generating method, as for a measure against iterated-encryption attack, a method in which a large prime number p″ is included in p′−1 as to a prime number p′ included in p−1 is used. In this measure against the iterated-encryption attack, generation of a very weak key can be avoided, but there is a possibility that attack will be successful.
As an effective measure against the iterated-encryption attack which is conventionally known, there is the Maurer judging method (Fast generation of secure RSA-moduli with almost maximal diversity, Advances in Cryptology-EUROCRYPT '89, Lecture Notes in Computer Science, Vol.434, pp.636-647). The following simply describes the Maurer judging method.
Maurer Judging Method
As for a prime number p, the following conditions (2) are satisfied.
p=
2
h
p
p′+
1(
p′>h
p
, p
′:prime number)
and
p′=
2
h
p
′p″+
1(
p″>h
p
′,p
″: prime number) (2)
In the case where p and q which satisfy these two conditions are used for secret keys of RSA and an encryption key of RSA is e, when the following condition (3) is satisfied, it is assured that the probability f that a number of repetition u of encryption required for obtaining a plain text X from a cipher text X
e
satisfies the following condition (4) (with respect to the plain text X) is as the following condition (5).
e
p′−1
≡1 (mod
p
′) and (mod
q
′)
e
(p′−1)/p″
≢1 (mod
p
′) and (mod
q
′) (3)
e
is a primitive element in (mod
p
′) and (mod
q
′)
u≧
min(
p′−
1,
q′−
1) (4)
f≧
1−
l
/(
p′q′
) (5)
More specifically, in the case where n=1024 bits, p=q=512 bits and p′=q′=260 bits, it is assured that unless encryption is not repeated at least 2
260
times for all the plain texts except for 2
504
{=2
1024
÷(2
260
×2
260
)} plain texts in the universal set of 2
1024
plain texts, the original text cannot be obtained.
In the Maurer judging method, since the Pocklington provable prime number judging method, to be mentioned later, is carried out on a basis of the encryption key e of RSA, the Maurer judging method is a measure against the iterated-encryption attack and at the same time is a method for performing a provable prime number judgement.
BRIEF SUMMARY OF THE INVENTION
It is one object of the present invention to provide a prime number generation apparatus which is capable of generating provable prime numbers.
It is another object of the present invention to provide a prime number generation apparatus which is capable of determining an upper limit of an order to which a measure against the prime factorization is necessary to be taken and of taking a suitable measure against the prime factorization.
It is still another object of the present invention to provide a prime number generation apparatus which is capable of generating strong prime numbers against iterated-encryption attack.
The prime number generation apparatus of the present invention has a prime num
Itoh Koichi
Takenaka Masahiko
Torii Naoya
Yokoyama Kazuhiro
De'cady Albert
Fujitsu Limited
Kabakoff Steve
Staas & Halsey , LLP
LandOfFree
Prime number generation apparatus B-smoothness judgement... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prime number generation apparatus B-smoothness judgement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prime number generation apparatus B-smoothness judgement... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2577528