Information security device, prime number generation device, and prime number generation method

• US 20020176573A1
• Filed: 04/12/2002
• Published: 11/28/2002
• Est. Priority Date: 04/17/2001
• Status: Active Grant

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Ono, Takatoshi, Futa, Yuichi, Ohmori, Motoji
• Granted Patent: US 7,130,422 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• 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 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

An information security device receives an input of prime q, and generates prime N that is larger than prime q. In the information security device, a partial information setting unit generates number u such that 2×u×q+1≠0 mod L_i (i=1, 2, . . . , n). A random number generating unit generates random number R′. A judgement target generating unit generates R=u+L₁×L₂×. . . ×L_n×R′ and N=2×R×q+1, using number u and random number R′. A primality judging unit judges the primality of number N, using numbers N and R generated by the judgement target generating unit.

Claims

1. An information security device that handles predetermined information securely and reliably based on an intractability of factorization, by generating two primes and using a multiplication of the two primes, comprising:

acquiring means for acquiring a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , L_n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L_i (i=1, 2, . . . , n);

generating means for generating a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L₁, L₂, . . . , L_n are excluded from the generation of the number N; and

judging means for judging primality of the number N, and outputting the number N as a prime if the number N is judged as being prime.

2. The information security device of claim 1,

wherein the generating means generates the number N that satisfies N=1 mod L_i (i=1, 2, . . . , n).

3. The information security device of claim 2,

wherein the generating means includes:

a random number generating unit for generating a random number R′

whose bit length is (Lenq−

LenL−

1), where Lenq is the bit length of the prime q and LenL is a bit length of (L₁×

L₂×

. . . ×

L_n); and

a judgement target generating unit for (a) generating a number R

R=L₁×

L₂×

. . . ×

L_n×

R′

using the random number R′ and

the primes L₁, L₂, . . . , L_n, and (b) generating the number N

N=2×

R×

q+1

using the prime q and the number R, and

the judging means judges the primality of the number N, using the number N and the number R generated by the judgement target generating unit.

4. The information security device of claim 3,

wherein the judging means (a) judges, for the number N, whether a first judgement formula

2^N−

1=1 mod N

holds true, (b) further judges, for the number N and the number R, whether a second judgement formula

2^2R≠

1 mod N

holds true, and (c) judges the number N as being prime if both of the first judgement formula and the second judgement formula hold true.

5. The information security device of claim 1,

wherein the generating means includes:

a partial information generating unit for generating a number u that satisfies

2×

u×

q+1≠

0 mod L_i (i=1, 2, . . . , n)

using the prime q;

a random number generating unit for generating a random number R′

;

a judgement target generating unit for (a) generating a number R

R=u+L₁×

L₂×

. . . ×

L_n×

R′

using the primes L₁, L₂, . . . , L_n, the number u, and the random number R′

, and (b) generating the number N

N=2×

R×

q+1

using the prime q and the number R, and

the judging means judges the primality of the number N, using the number N and the number R generated by the judgement target generating unit.

6. The information security device of claim 5,

wherein the partial information generating unit includes:

an integer generating unit for (a) generating integers N₁ (1≦

N₁≦

L₁−

1), N₂ (1≦

N₂≦

L₂−

1), . . . , N_n (1≦

N_n≦

L_n−

1), and (b) calculating a number u_i that satisfies

u_i=(N_i−

1)/(2×

(q mod L_i)) mod L_i (i=1, 2, . . . ,n)

and

an information combining unit for calculating the number u that satisfies

u=u_i mod L_i (i=1, 2, . . . , n)

using the number u_i (i=1, 2, . . . , n) calculated by the integer generating unit.

7. The information security device of claim 6,

wherein the judging means (a) judges, for the number N, whether a first judgement formula

2^N−

1=1 mod N

holds true, (b) further judges, for the number N and the number R, whether a second judgement formula

2^2R mod N

holds true, and (c) judges the number N as being prime if both of the first judgement formula and the second judgement formula hold true.

8. An IC card that handles predetermined information securely and reliably based on an intractability of factorization, by generating two primes and using a multiplication of the two primes, comprising:

acquiring means for acquiring a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , L_n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L_i (i=1, 2, . . . , n);

generating means for generating a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L₁, L₂, . . . , L_n are excluded from the generation of the number N; and

judging means for judging primality of the number N, and outputting the number N as a prime if the number N is judged as being prime.

9. A prime number generation device for generating a prime, comprising:

acquiring means for acquiring a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , L_n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L_i (i=1, 2, . . . ,n)

generating means for generating a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L₁, L₂, . . . , L_n are excluded from the generation of the number N; and

judging means for judging primality of the number N, and outputting the number N as a prime if the number N is judged as being prime.

10. A prime number generation method used in a prime number generation device for generating a prime, comprising:

an acquiring step for acquiring a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , L_n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L_i (i=1, 2, . . . , n);

a generating step for generating a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L₁, L₂, . . . , L_n are excluded from the generation of the number N; and

a judging step for judging primality of the number N, and outputting the number N as a prime if the number N is judged as being prime.

11. A prime number generation program used in a computer for generating a prime, comprising:

an acquiring step for acquiring a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , L_n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L_i (i=1, 2, . . . , n);

a generating step for generating a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L₁, L₂, . . . , L_n are excluded from the generation of the number N; and

a judging step for judging primality of the number N, and outputting the number N as a prime if the number N is judged as being prime.

12. A computer-readable recording medium that stores a prime number generation program used in a computer for generating a prime, comprising:

an acquiring step for acquiring a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , L_n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L_i (i=1, 2, . . . , L_n)

a generating step for generating a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L₁, L₂, . . . , L_n are excluded from the generation of the number N; and

a judging step for judging primality of the number N, and outputting the number N as a prime if the number N is judged as being prime.