Method for on-board prime number generation

• US 10,447,477 B2
• Filed: 11/25/2015
• Issued: 10/15/2019
• Est. Priority Date: 12/18/2014
• Status: Active Grant

• Current Assignee: Thales DIS France SA
• Original Assignee: Thales DIS France SA
• Inventors: Coulier, Charles, Villegas, Karine, Hamzi, Nabil, Zeamari, Ali, Roussel, Nicolas
• Primary Examiner(s): Shaifer Harriman, Dant B
• Application Number:
  US15/534,079
• Publication Number:
  US 20170346632A1
• Time in Patent Office: 1,420 Days
• Field of Search: 380 46
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: G06F 7/64 Digital differential analysers, i.e. computing devices for differentiation, integration or solving differential or integral equations, using pulses representing increments; Other incremental computing devices for solving difference equations G06F7/70 takes precedence; differential analysers using hybrid computing techniques G06J1/02 ; DDA application in numerical control G05B19/18
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

The present invention relates to a method to generate prime numbers on board a portable device, said method comprising the steps of, each time at least one prime number is requested:

• • when available, retrieve results from previously performed derivation calculation or, if not, select a start point for derivation;
  • process derivation calculation to converge towards a prime number;
  • if a prime number is found, store it and restart derivation calculation from a new start point;
  • stop the derivation calculation after a predetermined amount of time;
  • store intermediate results to be used a next time a prime number will be requested;
  • output a stored prime number.

Claims

1. Method to generate prime number on board a portable computing device, said method comprising the steps of, each time at least one prime number is requested:

store, by the portable computing device, a predefined number of pre-calculated prime numbers, said pre-calculated prime numbers being available to be output in case no other calculated prime number is available, wherein the predefined number of the pre-calculated prime numbers is determined depending on calculation resources of the portable computing device and generation duration constraints from an application requesting the generation;

when available, retrieve, by the portable computing device, results from previously performed derivation calculation or, if not, select a start point for derivation;

process, by the portable computing device, derivation calculation to converge towards a prime number;

if a prime number is found, store, by the portable computing device, the prime number and restart derivation calculation from a new start point;

stop, by the portable computing device, continuation of the derivation calculation after one or more iterations of the derivation calculation and after a predetermined amount of time;

store, by the portable computing device, intermediate results to be used a next time a prime number will be requested; and

output, by the portable computing device, a stored prime number different from the intermediate results.

2. Method according to claim 1, said method being further implemented during non critical phases of functioning of the portable computing device even in absence of any request for a prime number.

3. Method according to claim 1, further including using the prime numbers for the generation of cryptographic material.

4. Method according to claim 3, wherein, cryptographic material being an RSA key pair and the generation of two prime numbers being requested, the predetermined amount of time is determined based on a double prime number generation.

5. Device configured to produce cryptographic material based on at least one prime number, said device comprising:

a timer;

a memory storing a predefined number of pre-calculated prime numbers, said pre-calculated prime numbers being available to be output in case no other calculated prime number is available, wherein the predefined number of the pre-calculated prime numbers is determined depending on calculation resources of the device and generation duration constraints from an application requesting the generation; and

computational hardware configured to cause the device to;

when available, retrieve results from previously performed derivation calculation or, if not, select a start point for derivation;

process derivation calculation to converge towards a prime number;

if a prime number is found, store the prime number and restart derivation calculation from a new start point;

stop continuation of the derivation calculation after one or more iterations of the derivation calculation and after a predetermined amount of time;

store intermediate results to be used a next time a prime number will be requested; and

output a stored prime number different from the intermediate results.

6. Device according to claim 5, said device belonging to the group constituted by smart cards, HSM, tokens, USB keys, and embedded secure elements.