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

• US 7,130,422 B2
• Filed: 04/12/2002
• Issued: 10/31/2006
• 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
• Primary Examiner(s): Smithers, Matthew
• Application Number:
  US10/120,489
• Publication Number:
  US 20020176573A1
• Time in Patent Office: 1,663 Days
• Field of Search: 380/28, 708/250, 708/490
• US Class Current: 380/28
• 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, said device comprising:

an acquiring unit operable to acquire 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 unit operable to generate 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 unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime,

wherein the generating unit is operable to generate the number N that satisfies N=1 mod L_i (i=1, 2, . . . , n), and

wherein the generating unit includes;

a random number generating unit operable to generate 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 operable to (a) generate a number R

R=L₁×

L₂×

. . . ×

L_n×

R′

using the random number R′ and

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

N=2×

R×

q+1

using the prime q and the number R, and

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

2. The information security device of claim 1,

wherein the judging unit (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.

3. 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, said device comprising:

an acquiring unit operable to acquire 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 unit operable to generate 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 unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime,

wherein the generating unit includes;

a partial information generating unit operable to generate a number u that satisfies

2×

u×

q1≠

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

using the prime q;

a random number generating unit operable to generate a random number R′

; and

a judgement target generating unit operable to (a) generate 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) generate the number N

N=2×

R×

R×

q+1

using the prime q and the number R, and

wherein the judging unit 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 partial information generating unit includes:

an integer generating unit operable to (a) generate integers N₁ (1≦

N₁≦

L₁−

1), N₂ (1≦

N₂≦

L₂−

1), . . . , N_n (1≦

N_n≦

L_n−

1), and (b) calculate 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 operable to calculate 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.

5. The information security device of claim 4,

wherein the judging unit (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.

6. 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, said IC card comprising:

an acquiring unit operable to acquire 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 unit operable to generate 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 unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime,

wherein the generating unit is operable to generate the number N that satisfies N=1 mod L_i (i=1, 2, . . . , n),

wherein the generating unit includes;

a random number generating unit operable to generate 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 operable to (a) generate a number R

R=L₁×

L₂×

. . . ×

L_n×

R′

using the random number R′ and

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

N2×

R×

q+1

using the prime q and the number R, and

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

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

an acquiring unit operable to acquire a known prime q and n number of known primes L₁, L₂, . . . , L_n, where L₁, L₂, . . . , Ln are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod Li (i=1, 2, . . . , n);

a generating unit operable to generate 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 unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime,

wherein the generating unit is operable to generate the number N that satisfies N=1 mod L_i(i=1, 2, . . . , n),

wherein the generating unit includes;

a random number generating unit operable to generate 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 operable to (a) generate a number R

R=L₁×

L₂×

. . . ×

L_n×

R′

using the random number R′

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

N=2×

R×

q+1

using the prime q and the number R, and

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

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

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 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 primality of the number N, and outputting the number N as a prime if the number N is judged as being prime,

wherein said step of generating comprises;

generating the number N that satisfies N=1 mod Li (i=1, 2, . . . , n);

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

generating a number R, where R=L₁×

L₂×

. . . ×

L_n×

R′

, using the random number R′ and

the primes L₁, L₂, . . . , L_n, and generating the number N, where N=2×

R×

q+1, using the prime q and the number R, and

wherein said step of judging comprises judging the primality of the number N, using the number N and the number R generated in said step of generating.

9. A prime number generation program embodied on a computer-readable medium, and used in a computer for generating a prime, said program causing the computer to execute a method comprising:

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 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 primality of the number N, and outputting the number N as a prime if the number N is judged as being prime,

wherein said step of generating comprises;

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

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

generating a number R, where R=L₁×

L₂×

. . . ×

L_n×

R′

, using the random number R′ and

the primes L₁, L₂, . . . , L_n, and generating the number N, where N=2×

R×

q+1, using the prime q and the number R, and

wherein said step of judging comprises judging the primality of the number N, using the number N and the number R generated in said step of generating.

10. 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, said IC card comprising:

an acquiring unit operable to acquire 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 unit operable to generate 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 unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime,

wherein the generating unit includes;

a partial information generating unit operable to generate 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 operable to generate a random number R′

; and

a judgement target generating unit operable to (a) generate 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) generate the number N

N=2×

R×

q+1

using the prime q and the number R, and

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

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

an acquiring unit operable to acquire 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 unit operable to generate 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 unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime,

wherein the generating unit includes;

a partial information generating unit operable to generate 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 operable to generate a random number R′

; and

a judgement target generating unit operable to (a) generate 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) generate the number N

N=2×

R×

q+1

using the prime q and the number R, and

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

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

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 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₂, . . . , Ln are excluded from the generation of the number N; and

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

wherein said step of generating comprises;

generating a number u that satisfies 2×

u×

q+1≠

0 mod L_i (i=1, 2, . . . , n), using the prime q;

generating a random number R′

; and

generating a number R, where R=u+L₁×

L₂×

. . . ×

L_n×

R′

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

, and generating the number N, where N=2×

R×

q+1, using the prime q and the number R, and

wherein said step of judging comprises judging the primality of the number N, using the number N and the number R generated in said generating step.

13. A prime number generation program embodied on a computer-readable medium, and used in a computer for generating a prime, said program causing the computer to execute a method comprising:

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 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 primality of the number N, and outputting the number N as a prime if the number N is judged as being prime,

wherein said step of generating comprises;

generating a number u that satisfies 2×

u×

q+1≠

0 mod L_i (i=1, 2, . . . , n), using the prime q;

generating a random number R′

; and

generating a number R, where R=u+L₁×

L₂×

. . . ×

L_n×

R′

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

, and generating the number N, where N=2×

R×

q+1, using the prime q and the number R, and

wherein said step of judging comprises judging the primality of the number N, using the number N and the number R generated in said generating step.