METHOD OF GENERATING PRIME NUMBERS PROVEN SUITABLE FOR CHIP CARDS

• US 20140355758A1
• Filed: 12/12/2012
• Published: 12/04/2014
• Est. Priority Date: 12/15/2011
• Status: Active Grant

• Current Assignee: Rambus Inc.
• Original Assignee: Inside Secure SA
• Inventors: Feix, Benot, Paillier, Pascal, Clavier, Christophe, Thierry, Loc
• Granted Patent: US 9,596,080 B2
• Time in Patent Office: Days
• US Class Current: 380/46
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds

Abstract

The invention relates to a method for generating a prime number, implemented in an electronic device, the method including steps of calculating a candidate prime number having a number of bits, using the formula: Pr=2P·R+1, where P is a prime number and R is an integer, applying the Pocklington primality test to the candidate prime number, rejecting the candidate prime number if it fails the Pocklington test, generating the integer from an invertible number belonging to a set of invertible elements modulo the product of numbers belonging to a group of small prime numbers greater than 2, so that the candidate prime number is not divisible by any number of the group, the prime number P having a number of bits equal, to within one bit, to half or a third of the number of bits of the candidate prime number.

Claims

1. An encryption method implemented in an electronic device, the method comprising steps of:

generating a prime number,

generating an integer,

generating a candidate prime number having a desired number of bits, using the following formula;

Pr=2P·

R+1,

Pr being the candidate prime number, P being the prime number and having a number of bits lower than the number of bits of the candidate prime number and R being the integer, and

supplying the candidate prime number as proven prime number if it passes the Pocklington primality test,

wherein it comprises steps of;

storing a group of small prime numbers greater than 2,

calculating and storing a product of the prime numbers of the stored group, and

generating an invertible number belonging to a set of invertible elements modulo the stored product, the integer being generated from the invertible number so that the candidate prime number is not divisible by any number of the stored group, the prime number having a number of bits equal, to within one bit, to half or a third of the number of bits of the candidate prime number.

2. Method according to claim 1, wherein the integer R is chosen equal to:

R=(X−

(2P)<sup>−

1</sup> mod Π

v)+Z·

Π

v

R being the integer, X being an invertible number modulo the stored product, Π

v being the stored product, P being the prime number, and Z being an integer chosen so that the integer has a size such that the candidate prime number has the desired number of bits.

3. Method according to claim 1, comprising steps of:

generating a new candidate prime number from the invertible number multiplied by 2 modulo the stored product, if the candidate prime number does not pass the Pocklington primality test, and

applying the Pocklington primality test to the new candidate prime number.

4. Method according to claim 1, wherein the invertible number is generated so as to be lower than the product stored using the following equation:

X<sup>λ

Π

v</sup>=1 mod Π

v

X being the invertible number generated, Π

v being the stored product, and λ

Π

v being the Carmichael number of the set of invertible elements modulo the stored product.

5. Method according to claim 4, wherein the invertible number is generated by randomly choosing an invertible candidate number lower than the stored product, and by incrementing it by one until it verifies the equation X^λ

Π

v=1 mod Π

v, in which X is the invertible candidate number, Π

v is the stored product, λ

Π

v is the Carmichael number of the set of invertible elements modulo the stored product Π

v.

6. Method according to claim 4, wherein an invertible candidate number X is randomly chosen at a value lower than the stored product and incremented by the quantity:

B·

(1−

X<sup>λ

Π

v</sup> mod Π

v),

in which B is an integer randomly chosen between one and the stored product, X is the invertible candidate number, Π

v is the stored product, λ

Π

v is the Carmichael number of the set of invertible elements modulo the stored product Π

v, until it verifies the equation, the integer B being chosen randomly at a value lower than the stored product.

7. Method according to claim 1, wherein the size in number of bits of the candidate prime number is equal to three times the size of the prime number, to within one unit, the method comprising a step of calculating the quotient of an integer division of the integer by the prime number, the generated candidate prime number being retained as candidate prime number only if the quotient is odd.

8. Method according to claim 1, wherein the integer is chosen in the interval [I+1,2I] with:

9. Method according to claim 1, comprising several steps of generating a new prime number, a first generation step supplying a prime number from a first prime number, each subsequent generation step supplying a prime number from the prime number obtained in the previous generation step, until a prime number formed of the desired number of bits is obtained, each generation step comprising the steps of generating a candidate prime number and of the Pocklington test.

10. Method according to claim 9, wherein the first steps of generating a new prime number comprise:

a—

calculating a candidate prime number having a number of bits, using the following formula;

Pr=2P·

R+1

P being a proven prime number having a number of bits equal, to within one bit, to half or a third of the number of bits of the candidate prime number, and R being a randomly chosen integer,

b—

a test of the divisibility of the candidate prime number by the prime numbers of the stored group,

c—

if the candidate prime number is not divisible by the prime numbers of the stored group, applying the Pocklington primality test to the candidate prime number Pr,

d—

if one of the divisibility and Pocklington tests fails for the candidate prime number, incrementing the integer by one, incrementing the candidate prime number by twice the prime number, and executing the steps b to d again as long as the incremented candidate prime number fails the divisibility and Pocklington tests.

11. Method according to claim 10, wherein testing the divisibility of the candidate prime number by numbers of the stored group comprises steps of:

storing as first remainders, the remainders of integer divisions of the candidate prime number by each of the numbers of the stored group, the candidate prime number not being a prime number if one of the first remainders is zero,

storing as second remainders, the remainders of integer divisions of twice the prime number by each of the numbers of the stored group, and

if a new candidate prime number is calculated from the candidate prime number by adding twice the prime number thereto, updating each of the first remainders by adding thereto the second remainder corresponding to the same prime number of the stored group modulo the same prime number of the stored group.

12. Method according to claim 11, wherein each of the second remainders is updated by receiving the double of the first remainder corresponding to the same prime number of the stored group modulo the same prime number of the stored group, when a new candidate prime number is generated from the prime number obtained in the previous generation step.

13. Method according to claim 12, wherein the first prime number is obtained by randomly choosing a number formed of a number of bits lower than a maximum number of bits, and by successively applying thereto a limited number of primality tests comprising several Miller-Rabin tests (MR_A, A=2, 7, 61;

3, 5, 7, 11, 13,

     17) applied in different bases, until a number passing the Miller-Rabin tests is obtained, the maximum number of bits and the values of the bases being chosen to prove the primality of the first prime number.

14. Method according to claim 13, wherein the Miller-Rabin tests applied to the randomly chosen number, are performed in bases 2, 7 and 61 with a maximum number of bits chosen lower than or equal to 32, or in bases 2, 3, 5, 7, 11, 13 and 17, with a maximum number of bits chosen lower than or equal to 48.

15. Method according to claim 13, wherein the Miller-Rabin tests applied to the randomly chosen number are preceded by a divisibility test of the number randomly chosen by numbers of a list of the smallest prime numbers.

16. Method according to claim 1, comprising steps of generating an encryption key from proven prime numbers.

17. An electronic device comprising a calculation block to execute multiplications of large numbers and/or modular exponentiation operations,

wherein it is configured to implement the method according to claim 1.

18. An integrated circuit on semiconductor chip, comprising a device according to claim 17.