RANDOM NUMBER GENERATION METHOD

Abstract

A random number generator is implemented within a digital processor by: a) searching an internal timestamp register which counts clock pulses for sequencing the processor; b) extracting at a given time n bits from the least significant bits of the register, n>1; c) using the n bits extracted at step b) as constituent bit(s) of a N-bit random number (34) to be generated; d) reiterating steps a) to c) until obtaining the N bits of the random number; and e) providing the random number to an application circuit or software.

Claims

1. A random number generation method implemented by means of a digital processor, the method comprising: a) searching an internal timestamp register which counts clock pulses for sequencing the processor; b) extracting at a given time n bits from the least significant bits of the register, n>1; c) using the n bits extracted at step b) as constituent bit(s) of a random number of N bits to be generated; d) reiterating steps a) to c) until obtaining the N bits of the random number; and e) providing the random number to an application circuit or software.

2. The method of claim 1, wherein the timestamp register is a register counting pulses directly outputted from an oscillator of the clock.

3. The method of claim 1, wherein steps a) to d) are carried out within a firmware of the processor.

4. The method of claim 1, wherein the n bits extracted at step b) are the least significant bit(s) of the timestamp register.

5. The method of claim 4, wherein n=1 and the bit extracted at step b) is the least significant bit of the timestamp register.

6. The method of claim 1, wherein the given time of extraction of the n bits at step b) is a time controlled by a random or pseudo-random generator.

7. The method of claim 1, wherein the given time of extraction of the n bits at step b) is a time determined in response to a request received from the application circuit or software.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

[0037] The accompanying drawings, which are incorporated in and constitute part of this specification, illustrate embodiments of the invention and together with the description, serve to explain the principles of the invention. The embodiments illustrated herein are presently preferred, it being understood, however, that the invention is not limited to the precise arrangements and instrumentalities shown, wherein:

[0038] FIG. 1 schematically illustrates a digital processor with the various blocks to which it is interfaced, the whole being used for implementing the method of the invention.

[0039] FIG. 2 explains how to generate a random number by searching a register of the system of FIG. 1.

[0040] FIG. 3 is a block diagram showing the successive steps of implementation of the method of the invention.

DETAILED DESCRIPTION OF THE INVENTION

[0041] FIG. 1 schematically shows a per se conventional architecture of a system with a digital processor.

[0042] A microprocessor or microcalculator 10 is interfaced by data bus 12, address bus 14, and control bus 16 respectively to memory circuits 18, external peripherals 20, and internal resources 22.

[0043] The general sequencing of the processor 10 is provided by a clock circuit 24 that includes an oscillator 26 driven by a crystal 28. The ticks of the oscillator 26 feed a timestamp register 30 counting the pulses that will be used to define the rate of the successive CPU cycles of the processor 10 after reduction of the frequency by a divider 32. The content of the timestamp register 30 is an evolutive content, constantly changing with the rhythm of the sequencing clock 24 pulses.

[0044] The principle of the invention, schematized in FIG. 2, consists in reading one or several bits (n bits, with n 1) of the timestamp register 30, and using these n bits to form the N bits of a random number 34 of N bits (N n).

[0045] If n<N, the process is reiterated until completion the N bits of the number 34.

[0046] It is possible to extract, indifferently, for example one bit (n=1), a nibble (n=4), a byte (n=8), etc., at a time to obtain the N bits of the random number 34, without specific limitation on the number N, and hence on the length of the random number obtained.

[0047] However, to maximize the entropy of the process, it is preferred that only one bit (n=1) is extracted, more precisely the least significant bit of the register.

[0048] In most microprocessors, the timestamp register is an accessible and searchable register. For example, in Intel™ processors, this timestamp register is a 64-bit register called TSC (TimeStamp Counter), and it can be searched by a low-level instruction RDTCP (Read TSC and Processor ID). This counter can reflect the number of pulses produced by the sequencing clock since the initial reset of the register.

[0049] The extracted bit(s) are the least significant bits (LSBs) of the timestamp register, which are bits whose value is deterministic but totally unpredictable at a given time, given the very high clock frequencies of current processors, typically several gigahertz, that is to say that the last bits of the timestamp register are changed several times at each nanosecond.

[0050] Now, the time of execution of the register search instruction is itself subject to an unpredictable randomness, which creates randomness on the value of the bit(s) read when this search is effectively carried out. Indeed, the hardware-level architecture of the microcalculators induces irregularities in the sequencing of execution of the micro instructions due to hardware interrupts (external events that trigger the execution of specific software programs and interrupt the execution of other software programs in an imperative way), but also due to the necessary coordination of several cores that execute tasks in parallel.

[0051] In addition, above the hardware layer are added several software layers that run themselves with different priority levels and in constant competition with external events and other software programs running at the same time.

[0052] It is hence impossible to predict when a particular micro-instruction of an application software will actually be executed, and consequently, to determine in advance the value of the timestamp register bits at that time, especially that of the least significant bits, at the time when the register reading instruction will be actually executed.

[0053] FIG. 3 shows a block diagram 100 schematically illustrating the successive steps of the method for obtaining the random number 34 following the receipt (block 110) of a random number generation request: [0054] a) searching the timestamp register 30 (block 120); [0055] b) extracting the n bit(s) from the register (block 130); [0056] c) using this or these bits to form the random number (block 140); [0057] d) if the random number is not complete (test 150), reiterating steps 120 to 130; and finally [0058] e) providing the random number (block 160) as a response to the request at step 110.

[0059] It should be noted that the just-described method has several particularly significant advantages: [0060] no addition of hardware element to the preexisting circuits of the digital processor, because no interaction with the outside (to use a physical phenomenon) or with the user is necessary; [0061] simple and versatile implementation, the timestamp register existing on all the digital processors; [0062] very high degree of entropy; and possibility to obtain very long random numbers in a very short time.

[0063] In practice, the generation method can be implemented at several levels: [0064] entirely and directly within the processor firmware; [0065] from this firmware to feed a higher level application software layer, thus from the processor to the application layer (which avoids the difficulties due to the microprocessor access protections because, in this case, that is the latter that generates internally and provides the random number); or [0066] conversely, from the application layer to the processor, upon request from the application. Since a high-level application (User Mode) generally has no privilege to access directly the processor registers, the implementation can be made at two levels with i) a module running at a high privilege level to access the processor registers and ii) a second module communicating with the first one and interfaced with the high-level program through a suitable API.

[0067] The above-described embodiment, by repeated extractions of n bits from the timestamp register and concatenation of the n successive bits until obtaining the N bits of the random number, may have many alternatives.

[0068] These alternatives, which make it possible in particular to further increase the degree of entropy of the random number generated, are not exclusive and may be combined with each other.

[0069] A first alternative consists in controlling the issuance of the register reading instruction command under the control of a pseudo-random generator included in the internal software of the processor, which introduces between each reading of the register an unpredictable waiting time.

[0070] A second alternative consists in varying the number n and/or the order of the bits extracted from the searched register, also randomly or pseudo-randomly, at each search step. In other words, the value n is in this case itself random instead of being predefined, just as the order in which the n bits (if more than one bit) are used to form the random number.

[0071] A third alternative consists, instead of simply copying the n bits extracted to form the N bits of the random number, in using these n bits by changing them, for example by reversing or swapping them according to a random or pseudo-random process, by summing all of them or some of them, etc.

[0072] Of note, the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “includes”, and/or “including,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof

[0073] As well, the corresponding structures, materials, acts, and equivalents of all means or step plus function elements in the claims below are intended to include any structure, material, or act for performing the function in combination with other claimed elements as specifically claimed. The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the invention. The embodiment was chosen and described in order to best explain the principles of the invention and the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.

[0074] Having thus described the invention of the present application in detail and by reference to embodiments thereof, it will be apparent that modifications and variations are possible without departing from the scope of the invention defined in the appended claims as follows: