METHOD FOR ON-BOARD PRIME NUMBER GENERATION

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 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.

2. Method according to claim 1, including a preliminary step of 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.

3. Method according to claim 2, wherein the predefined number of pre-calculated prime numbers is determined depending on calculation resources of the portable device and generation duration constraints from an application requesting the generation.

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

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

6. Method according to claim 5, 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.

7. Device configured to produce cryptographic material based on at least one prime number, said device implementing a method of claim 1 and comprising, a derivation calculation module to perform derivation calculation to converge towards a prime number, a timer, a memory to store prime numbers, a monitoring module to monitor the derivation calculation and to stop such calculation after a predetermined amount of time.

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

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0047] The following description and the annexed drawings set forth in details certain illustrative aspects and are indicative of but a few of the various ways in which the principles of the embodiments may be employed. Other advantages and novel features will become apparent from the following detailed description when considered in conjunction with the drawings and the disclosed embodiments are intended to include all such aspects and their equivalents.

[0048] FIG. 1 schematically shows the iterative process to obtain a prime number according to the prior art;

[0049] FIG. 2 schematically shows a flowchart of prime number generation according to the invention;

[0050] FIG. 3 shows a comparison of the distributions of key generation durations obtained with and without the invention;

[0051] FIG. 4 schematically shows a device according to the invention.

DETAILED DESCRIPTION OF EMBODIMENTS OP THE INVENTION

[0052] For a more complete understanding of the invention, the invention will now be described in details with reference to the accompanying drawing. The detailed description will illustrate and describe what is considered as a preferred embodiment of the invention as claimed hereinafter. It should of course be understood that various modifications and changes in form or details could readily be made without departing from the spirit of the invention.

[0053] For clarity, only those elements and steps which are useful to the understanding of the present invention have been shown in the drawings and will be described.

[0054] FIG. 2 shows a prime number generation process according to the invention. As soon as a request for at least one prime number is received, a timer T is triggered in a step S00 in order to track the duration of the prime number generation.

[0055] Then in a step S10, it is verified if a candidate p.sub.c is available in memory from previous calculation. Typically at the first use of the device implementing the method, none is available. It is here noted that candidate p.sub.c is Intermediary result from derivation.

[0056] In the case where no intermediary result is available in memory (case N), in a step S11, a random number p.sub.s is generated by a random number generator RNG. This random number p.sub.s is a start point for derivation calculation in a step S2.

[0057] In the case intermediary result is available in memory (case Y), the candidate p.sub.c is output from memory towards derivation calculation in step S2. While derivation calculations are processed, according to the invention, the duration is tracked. If the timer T reaches a predetermined amount of time T.sub.PG as schematically shown by step S21 on FIG. 2 (case Y), the intermediate result, here at least a candidate p.sub.c, is stored in a step S22 in memory to be later retrieved for pursuing iterative derivation process. Intermediate results are candidates under derivation and elements linked to the derivation algorithm used. Typically in case of generation of FIPs keys, candidates are two small prime numbers but any other intermediate data (unit . . . ) depending on the algorithm are here stored.

[0058] As long as the timer has not reached the predetermined amount of time T.sub.PG, the candidate p.sub.c is submitted to a primality test PrT in a step S3. If the candidate is a prime number p (case Y), it is stored in memory in a step S31. Meanwhile the timer T is still monitored as schematically shown by step S32. If the time limit T.sub.PG not yet reached (case N), the method is looped and a new random number p.sub.s is then generated in a new step S11. As soon as the time limit T.sub.PG has been reached in step S21 or step S32, in a step S4, a prime number is extracted from memory to be used by the requesting application.

[0059] The illustrative figure refers to a case where one prime number is requested. The invention also applies of course to cases whatever is the number of primes to generate. It thus clearly applies to cases where precisely two prime numbers have to be generated for RSA key generation.

[0060] FIG. 3 illustrates the effect of the invention. In dashed line is shown the repartition of the number NB of obtained prime numbers in relation with the necessitated time duration T. Such a repartition is spread around an average time T.sub.M of generation. In general, a critical time T.sub.O is the maximal admissible duration for a random number generation. It can be seen on FIG. 3 that some prime number generations are longer than this critical time T.sub.O.

[0061] While choosing a predetermined amount of time T.sub.PG between the average time and the critical time, the prime number generation is regularly maintained.

[0062] With the invention the time generation for a prime number is centered on the predetermined time limit T.sub.PG as shown in plain line.

[0063] It is seen here that the invention enables to narrow the statistical distribution of the calculation duration around the predetermined amount of time T.sub.PG chosen to interrupt the prime number generation. If the predetermined amount of time is too close or below the average time T.sub.M, the reserve of previously stored prime number will be too quickly consumed and there will be an important risk for the prime number generation duration to exceed the critical time T.sub.O.

[0064] When T.sub.PG is chosen above the average time T.sub.M but below the critical time T.sub.O, the quantity of prime number can be maintained and the duration of the prime number generation will be systematically below the critical time T.sub.O.

[0065] In relation with awaited behaviors in specific cases/applications, strategic choice concerning the prime numbers and candidates provision can be elaborated.

[0066] FIG. 4 schematically shows a device D according to the invention. It comprises a calculation module DERIV to perform derivation calculators, a memory MEM to store candidates p.sub.s and generated prime numbers p. The prime number generation is monitored by a monitoring module MON which operates while using a timer T enabling to track the duration of the prime number generation according to the invention. It stops the derivation calculation as soon as the predetermined amount of time is reached, triggers the storage of intermediary results and extracts at least a prime number from memory to perform operations necessitated by the prime numbers requesting application.

[0067] The invention is advantageous as few production constraints are generated. Only a pre-provisioning of some prime numbers is necessitated. The invention is indeed technically easy to implement. Furthermore the invention is interoperable and compatible with existing APIs. If the pre-provisioning is sufficient and if the time parameters are well chosen, the generation on board of the device has no limitation in time.

[0068] Based on a better process time management on board, the invention does not require important cooperation from external parties contrarily to the prior art's solutions.

[0069] In the above detailed description, reference is made to the accompanying drawings that show, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention. It is to be understood that the location or arrangement of individual elements within each disclosed embodiment may be modified without departing from the spirit and scope of the invention. The above detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims, appropriately interpreted, along with the full range of equivalents to which the claims are entitled.