METHOD OF GENERATING PROVEN PRIME NUMBERS SUITABLE FOR BEING IMPLEMENTED IN A SMART CARD

• US 20140358980A1
• 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, Clavier, Christophe, Paillier, Pascal, Thierry, Loc
• Granted Patent: US 9,577,826 B2
• Time in Patent Office: Days
• US Class Current: 708/446
• 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 generating a prime number from another prime number using the formula Pr=2P·R+1, where P is a prime number having a number of bits lower than that of the candidate prime number, and R is an integer, and applying the Pocklington primality test to the candidate prime number, the candidate prime number being proven if it passes the Pocklington test. According to the invention, 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 generated candidate prime number being retained as candidate prime number only if the quotient of the integer division of the integer by the prime number is odd.

Claims

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

generating a candidate prime number from another prime number using the following formula;

Pr=2P·

R+1

where Pr is the candidate prime number, P is a prime number having a number of bits lower than a desired number of bits of the candidate prime number, and R is an integer,

applying the Pocklington primality test to the candidate prime number, and

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

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 steps of calculating a quotient of an integer division of the integer by the prime number, and of rejecting the generated candidate prime number if the quotient of the integer division of the integer by the prime number is even.

2. Method according to claim 1, wherein, if the candidate prime number is not retained as candidate prime number or if it does not pass the Pocklington test, the method comprises steps of:

incrementing the integer by one or a certain quantity as a function of the parity of the quotient so that the quotient is odd,

modifying the candidate prime number by adding twice the prime number thereto, and

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

3. Method according to claim 1, comprising a step of testing the divisibility of the candidate prime number by small prime numbers, the generated candidate prime number being retained as candidate prime number only if it is not divisible by the small prime numbers.

4. 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 a desired number of bits is obtained, each generation step comprising the steps of generating a candidate prime number and of applying the Pocklington test to the candidate prime number

5. Method according to claim 4, comprising steps of:

storing as first remainders, the remainders of the integer divisions of the candidate prime number by each of the small prime numbers, the candidate prime number being divisible by one of the small prime numbers if the corresponding remainder is equal to zero,

storing as second remainders, the remainders of the integer divisions of twice the prime number by each of the small prime numbers, 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 respectively adding thereto the second remainder corresponding to the same small prime number.

6. Method according to claim 5, wherein each subsequent step of generating a prime number comprises steps of:

randomly choosing a new integer, and

updating each of the second remainders with the double of the first remainder corresponding to the same small prime number, obtained in the previous generation step.

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

8. Method according to claim 1, comprising steps of generating the integer from an invertible number belonging to a set of invertible elements modulo a 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 a third of the desired number of bits of the candidate prime number.

9. Method of claim 8, wherein the integer is chosen equal to:

R=X−

((2P)<sup>−

1</sup> mod Π

v)+Z·

Π

v,

X being an invertible number modulo the product of the prime numbers of the group, P being the prime number, and Z being an integer chosen so that the number R has a size such that the candidate prime number has the desired number of bits.

10. Method according to claim 8, wherein the integer is chosen so as to be even and so that the remainder of its integer division by the prime number is odd.

11. Method according to claim 8, wherein the integer is chosen equal to:

R=K+(K mod

     2)P·

Π

v+2P·

Z·

Π

v,

where K=(((X−

(2P)<sup>−

1</sup>−

S)/P) mod Π

v)P+S, S being the remainder of the integer division of the integer R by the prime number P, X being an invertible number modulo the product Π

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

12. Method according to claim 8, wherein if the candidate prime number does not pass the Pocklington primality test, it comprises steps of generating a new candidate prime number by adding to the candidate prime number a multiple of the invertible number modulo the product, the multiple not being divisible by one of the numbers forming the product, and applying the Pocklington primality test to the new candidate prime number.

13. Method according to claim 8, wherein the invertible number is generated by searching for an invertible candidate number X lower than the product fly verifying the following equation:

X<sup>λ

Π

v</sup>=1 mod Π

v,

λ

Π

v being the Carmichael number of the set of invertible elements modulo the product Π

v.

14. Method according to claim 13, wherein an invertible candidate number is randomly chosen at a value lower than the product Π

v and incremented by one or the quantity B (1−

X<sup>λ

Π

v</sup> mod Π

v) until it verifies the equation;

X<sup>λ

Π

v</sup>=1 mod Π

v,

B being an integer randomly chosen between one and the product Π

v.

15. Method according to claim 14, wherein the generation of the first prime number comprises steps of:

randomly choosing a number formed of the reduced number of bits, and

applying to the chosen number a limited set of Miller-Rabin tests (MR_A, A=2, 7, 61;

3, 5, 7, 11, 13,

     17) in different bases, until the chosen number passes the set of Miller-Rabin tests, the maximum number of bits and the values of the bases being chosen to prove the primality of the first prime number.

16. Method according to claim 15, 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.

17. Method according to claim 1, comprising a step of generating an encryption key from the supplied proven prime number.

18. 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 of claim 1.

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