Patent Description:
Random numbers are widely used in the fields of information security and statistical sampling. Random numbers generation is generation of a sequence of unpredicted and independent numbers conforming to a specified distribution. A pseudo-random number generator generates the sequence of numbers using a seed. An insufficient random seed may result in an insufficient random sequence, leading to insecure cryptographic systems or inaccurate sampling results.

Reference D1 (<CIT>) discloses a random number generator for generating random numbers using an SRAM PUF and dynamically generated data. However, the SRAM PUF holds a fixed set of PUF bits, leading to the possibility of data breach.

The present disclosure aims at providing a random number generator and a method of generating an output random number. This is achieved by a random number generator according to claim <NUM> and a method of generating an output random number according to claim <NUM>.

The dependent claims pertain to corresponding further developments and improvements.

According to an embodiment of the invention, a random number generator includes a static random number generator, at least one dynamic entropy source, a counter and a combining circuit. The static random number generator includes an initial random number pool and a static random number pool, and is used to output a static random number sequence from one of the initial random number pool and the static random number pool. The at least one dynamic entropy source is used to generate a dynamic entropy bit. The counter is coupled to the at least one dynamic entropy source and used to generate a dynamic random number sequence according to the dynamic entropy bit. The combining circuit is coupled to the static random number generator and the counter, and is used to receive the static random number sequence, and output a true random number sequence to a lively random number pool according to the static random number sequence and the dynamic random number sequence. The static random number pool is updated when the lively random number pool is fully updated.

According to another embodiment of the invention, a method of generating an output random number including: during an initialization phase, generating an initial static random number sequence from an initial random number pool, generating an initial true random number sequence according to the initial static random number sequence and an initial dynamic random number sequence, and initiating the static random number pool according to the initial true random number sequence; and during an operation phase, outputting the output random number, generating a subsequent static random number sequence from the static random number pool, generating a subsequent true random number sequence according to the subsequent static random number sequence and a subsequent dynamic random number sequence, and updating the static random number pool according to the subsequent true random number sequence.

As used herein, the term "truly random" or "true random" refers to a bit stream or a data sequence that is substantially <NUM>% in a hamming weight and an inter-device (ID) hamming distance, and is substantially <NUM> in a minimum entropy (min-entropy). The hamming weight measures an expected value of non-zero symbols in the bit stream in a percentage form. The ID hamming distance measures a hamming distance between two static entropy bit streams produced by two static entropy sources in response to an identical challenge. The min-entropy is a lower bound of entropy of the bit stream, measuring unpredictability of the bit stream.

<FIG> is a block diagram of a random number generator <NUM> according to an embodiment of the invention. The random number generator <NUM> may initially update a lively random number pool according to data from an initial random number pool, and then update a static random number pool according to data from the lively random number pool on a continuous and iterative basis. Further, the random number generator <NUM> may extract an output random number Srno from the lively random number pool upon request of an external circuit, e.g., a deterministic random bit generator or a cryptographic system. The initial random number pool may contain fixed data for all devices employing the random number generator <NUM>. The devices may be field programmable gate arrays (FPGA). The static random number pool may be constantly changing and unique to all the devices.

The random number generator <NUM> may include a static random number generator <NUM>, dynamic entropy sources <NUM>(<NUM>) to <NUM>(N), a counter <NUM>, a combining circuit <NUM>, a lively random number pool <NUM> and an update circuit <NUM>, N being a positive integer. The static random number generator <NUM> may include an initial random number pool <NUM>, a static random number pool <NUM> and a multiplexer <NUM>. The dynamic entropy sources <NUM>(<NUM>) to <NUM>(N) may be coupled to the counter <NUM>. The initial random number pool <NUM> and the static random number pool <NUM> may be coupled to the multiplexer <NUM>. The multiplexer <NUM> and the counter <NUM> may be coupled to the combining circuit <NUM>. The combining circuit <NUM> may be coupled to the lively random number pool <NUM>. The update circuit <NUM> is coupled to the lively random number pool <NUM> and the static random number pool <NUM>. While a plurality of dynamic entropy sources <NUM>(<NUM>) to <NUM>(N) are used in the embodiment, adopting only one dynamic entropy source <NUM>(<NUM>) in the random number generator <NUM> is also within the scope of the invention.

The random number generator <NUM> may operate in an initialization phase and an operation phase. During the initialization phase, the initial random number pool <NUM> may generate an initial static random number sequence Ssrn(<NUM>), the multiplexer <NUM> may select the initial static random number sequence Ssrn(<NUM>) from the initial random number pool <NUM> as the static random number sequence Ssrn according to a selection signal Sel. The initialization phase may be adopted upon power-up or activation of the random number generator <NUM>. The selection signal Sel may be generated from an external control circuit. During the operation phase, the static random number pool <NUM> may generate a subsequent random number sequence Ssrn(<NUM>), the multiplexer <NUM> may select according to the selection signal Sel the subsequent random number sequence Ssrn(<NUM>) from the static random number pool <NUM> as the static random number sequence Ssrn. The operation phase may be adopted upon initiation or update of the static random number pool <NUM>. While the multiplexer <NUM> is adopted in the embodiment to select between data from the initial random number pool <NUM> and data form the static random number pool <NUM>, it is also within the scope of the invention that the multiplexer <NUM> is eliminated from the random number generator <NUM>, and instead a selection circuit may be included to enable one of the initial random number pool <NUM> and the static random number pool <NUM> according to an appropriate timing, so as to output the static random number sequence Ssrn therefrom.

The initial random number pool <NUM> may be a physically unclonable function (PUF) cell array, a non-volatile memory, a volatile memory or a fixed logic circuit containing a plurality of static entropy bits. The plurality of static entropy bits may be independent and identically distributed random variables (IID). The initial static random number sequence Ssrn(<NUM>) may have a predetermined data length, e.g., <NUM>-bit. For example, the initial random number pool <NUM> may be <NUM>-bit-by-<NUM>-bit one-time programmable (OTP) memory cells, and each row, column or diagonal line of the memory cells may contain truly random entropy bits. The OTP memory cells may be antifuse-based and the truly random entropy bits may be programmed into the OTP memory cells during manufacturing setup. When the initial random number pool <NUM> is a volatile memory such as a static random access memory (SRAM) or a register bank, the truly random entropy bits may be programmed into the initial random number pool <NUM> upon receiving requests for generating the initial static random number sequence Ssrn(<NUM>). The truly random entropy bits may be fixed in values and identical to all devices employing the random number generator <NUM>. The initial random number pool <NUM> may output the initial static random number sequence Ssrn(<NUM>) according to a predetermined selecting algorithm. For example, the initial static entropy source <NUM> may select <NUM>-bit entropy bits from rows of memory cells in a predetermined row order to serve as the initial static random number sequence Ssrn(<NUM>). In some embodiments, the initial random number pool <NUM> may be a deterministic random bit generator (DRBG) generating a set of initial random numbers upon power-up or activation.

The static random number pool <NUM> may be a register bank and may have a size equal to or different from that of the initial random number pool <NUM>. In some embodiments, both the static random number pool <NUM> and the initial random number pool <NUM> may be <NUM> bits in size.

The dynamic entropy sources <NUM>(<NUM>) to <NUM>(N) may generate dynamic entropy bits E(<NUM>) to E(N), respectively and in real time. The dynamic entropy bits E(<NUM>) to E(N) may each be <NUM> bit in length.

The counter <NUM> may generate an dynamic random number sequence Sd according to at least one of the dynamic entropy bits E(<NUM>) to E(N). The counter <NUM> may be a linear feedback shift register (LFSR) or a digital counter, e.g., a <NUM>-bit LFSR. The dynamic random number sequence Sd may have a data length equal to that of the static random number sequence Ssrn, e.g., <NUM>-bit. During the initialization phase, the counter <NUM> may generate an initial dynamic random number sequence Sd, and during the operation phase, the counter <NUM> may generate a subsequent dynamic random number sequence Sd. In some embodiments, the counter <NUM> may be seeded by a seed sequence generated by the initial random number pool <NUM> upon power-up or activation, and the seed sequence may be <NUM>-bit in length. In other embodiments, the counter <NUM> may be initialized by a fixed seed sequence upon power-up or activation, and the fixed seed sequence may be <NUM>-bit in length. The counter <NUM> may receive the dynamic entropy bits E(<NUM>) to E(N) from the dynamic entropy sources <NUM>(<NUM>) to <NUM>(N), receive a predetermined bit in the true random number sequence Strn from the combining circuit <NUM> via a feedback path Pfb, combine the dynamic entropy bits E(<NUM>) to E(N) and the predetermined bit in the true random number sequence Strn to generate a reseeding control bit, and control reseeding of the counter <NUM> according to the reseeding control bit. For example, the counter <NUM> may perform an XOR operation on the dynamic entropy bits E(<NUM>) to E(N) and the predetermined bit in the true random number sequence Strn to generate the reseeding control bit. When the reseeding control bit is a logic level "<NUM>", the counter <NUM> may proceed counting, and when the reseeding control bit is a logic level "<NUM>", the counter <NUM> may be reseeded by a new seed sequence. In some embodiments, the new seed sequence may be generated by the initial random number pool <NUM>. In other embodiments, the new seed sequence may be provided by an output data sequence of the combining circuit <NUM>. As the result, the counter <NUM> may be reseeded in a random manner. In some embodiments, the counter <NUM> may employ a portion of the dynamic entropy bits E(<NUM>) to E(N) to generate the reseeding control bit.

The combining circuit <NUM> may combine the static random number sequence Ssrn and the dynamic random number sequence Sd in a bitwise manner to generate a true random number sequence Strn. The combining circuit <NUM> may be an XOR gate or a processor employing a data encryption standard (DES) algorithm, an advanced encryption standard (AES) algorithm or a hash function. For example, the combining circuit <NUM> may combine the <NUM>-bit static random number sequence Ssrn and the <NUM>-bit dynamic random number sequence Sd in a bitwise manner to generate a <NUM>-bit true random number sequence Strn. Since combining a truly random number with a random number may produce a truly random number, and the static random number sequence Ssrn is truly random, the true random number sequence Strn may be truly random regardless of the dynamic random number sequence Sd being truly random or not. In addition, the dynamic random number sequence Sd may be used to randomize the static random number sequence Ssrn to generate the true random number sequence Strn unique to the device.

During the initialization phase, the static random number sequence Ssrn may be the initial static random number sequence Ssrn(<NUM>), and the combining circuit <NUM> may generate an initial true random number sequence Strn by combining the initial static random number sequence Ssrn(<NUM>) and the initial dynamic random number sequence Sd. During the operation phase, the static random number sequence Ssrn may be the subsequent static random number sequence Ssrn(<NUM>), and the combining circuit <NUM> may generate a subsequent true random number sequence Strn by combining the subsequent static random number sequence Ssrn(<NUM>) and the subsequent dynamic random number sequence Sd.

The lively random number pool <NUM> may be updated according to the true random number sequence Strn. During the initialization phase, the lively random number pool <NUM> may be updated according to the initial true random number sequence Strn. During the operation phase, the lively random number pool <NUM> may be updated according to the subsequent true random number sequence Strn, and may output an output random number Srno upon request, thereby enhancing data security. The lively random number pool <NUM> may sequentially receive a plurality of true random number sequences Strn from the combining circuit <NUM> and store the same until it is fully updated. In some embodiments, the lively random number pool <NUM> is fully updated when a quantity of random numbers in the lively random number pool <NUM> reaches a target quantity, e.g., <NUM> bits. In other embodiments, the lively random number pool <NUM> is fully updated when a time period of updating the lively random number pool <NUM> reaches a target time period, e.g., <NUM> clock cycles. The lively random number pool <NUM> may be a register bank and may have a size equal to or different from that of the initial random number pool <NUM>. In some embodiments, both the lively random number pool <NUM> and the initial random number pool <NUM> may be <NUM> bits in size.

When the lively random number pool <NUM> is fully updated, the update circuit <NUM> may update the random numbers Ssrn(<NUM>) from the lively random number pool <NUM> to the static random number pool <NUM>. In some embodiments, the update circuit <NUM> may directly forward the random numbers Ssrn(<NUM>) from the lively random number pool <NUM> to replace the data in the static random number pool <NUM>. In other embodiments, the update circuit <NUM> may apply a compression and a nonlinear function to the random numbers Ssrn(<NUM>) from the lively random number pool <NUM> to generate updated true random numbers Ssrn'(<NUM>), and update the updated true random numbers Ssrn'(<NUM>) into the static random number pool <NUM>. The compression may be a cryptographic hash function such as an MD5 algorithm, an SHA1 algorithm, an SHA2 algorithm and/or an SHA3 algorithm. The nonlinear function may be a substitution-box (S-box) and/or a block cipher. In this manner, the static random number pool <NUM> may be constantly updated. For example, the static random number pool <NUM> may be updated each time the lively random number pool <NUM> is fully updated.

When a device adopting the random number generator <NUM> enters a sleep mode or a low-power mode, the random numbers in the static random number pool <NUM> may be transmitted to a non-volatile memory for storage. Later when the device returns to a normal operation mode, the static random number pool <NUM> may restore the random numbers from the non-volatile memory to continue the operation.

The random number generator <NUM> generates in the initialization phase a unique set of truly random numbers in the static random number pool <NUM> from a fixed set of truly random numbers in the initial random number pool <NUM> via the lively random number pool <NUM>, and continues in the operation phase to generate a new set of truly random numbers using the random numbers from the static random number pool <NUM>, and update the new set of truly random numbers into the static random number pool <NUM> via the lively random number pool <NUM>, while outputting the output random number Srno from the via the lively random number pool <NUM>, saving random number resources while enhancing data security.

<FIG> is a block diagram of a random number generator <NUM> according to another embodiment of the invention. The random number generator <NUM> is different from the random number generator <NUM> in that a compression circuit <NUM> is further included, the following discussion will focus on the difference.

The compression circuit <NUM> may be coupled between the combining circuit <NUM> and the lively random number pool <NUM>. The compression circuit <NUM> may compress the true random number sequence Strn into a compressed true random number sequence Strn', further enhancing data security. The compression circuit <NUM> may include an XOR gate. In some embodiments, the compression circuit <NUM> may include <NUM><NUM>-input XOR gates compressing a <NUM>-bit true random number sequence Strn into an <NUM>-bit compressed true random number sequence Strn'. In other embodiments, the compression circuit <NUM> may include a <NUM>-bit buffer and <NUM><NUM>-input XOR gates coupled thereto. The <NUM>-bit buffer may store <NUM><NUM>-bit true random number sequences Strn sequentially in a buffering duration of <NUM> clock cycles. After the <NUM><NUM>-bit true random number sequences Strn are buffered, each of the <NUM><NUM>-input XOR gates may compress <NUM> corresponding bits of the <NUM><NUM>-bit true random number sequences Strn into <NUM> corresponding bit in the compressed true random number sequence Strn', thereby generating a <NUM>-bit compressed true random number sequence Strn'. The compressed true random number sequence Strn' is then transmitted to the lively random number pool <NUM> to update the same. While a particular quantity and type of the XOR gate are used in the embodiment, other quantities and/or types of the XOR gate may be used to implement the compression circuit <NUM>, e.g., <NUM><NUM>-input XOR gates may be used. Likewise, other sizes and buffering durations of the buffer may be adopted to meet the design requirements.

In comparison to the random number generator <NUM>, the random number generator <NUM> employs the compression circuit <NUM> to increase data security.

<FIG> shows a block diagram of the counter <NUM> for use in the random number generators <NUM> and <NUM>. The counter <NUM> may include a conditional feedback circuit <NUM> and a linear feedback shift register (LFSR) <NUM>. The conditional feedback circuit <NUM> may be coupled to the dynamic entropy sources <NUM>(<NUM>) to <NUM>(N) and the combining circuit <NUM>. The LFSR <NUM> may be coupled between the conditional feedback circuit <NUM> and the combining circuit <NUM>.

The conditional feedback circuit <NUM> may receive an ith true random number sequence Strn from the combining circuit <NUM> via the feedback path Pfb, and generate the reseeding control bit Bc according to the ith dynamic entropy bits E(<NUM>) to E(N) and the predetermined bit of the true random number sequence Strn. The conditional feedback circuit <NUM> may include an XOR gate to perform the XOR operation on the ith dynamic entropy bits E(<NUM>) to E(N) and the predetermined bit, so as to generate the reseeding control bit Bc. The LFSR <NUM> may be reseeded according to the reseeding control bit Bc to generate an ith dynamic random number sequence Sd. The conditional feedback circuit <NUM> may generate the reseeding control bit Bc upon an update of the dynamic entropy bits E(<NUM>) to E(N) or the predetermined bit of the true random number sequence Strn. That is, the reseeding control bit Bc may be updated each clock cycle, and the LFSR <NUM> may be reseed each clock cycle depending on the value of the reseeding control bit Bc.

<FIG> is a block diagram of an exemplary dynamic entropy source <NUM>(n) in <FIG> and <FIG>, n is a positive integer ranging between <NUM> and N. The dynamic entropy source <NUM>(n) may include a first oscillator <NUM>, a second oscillator <NUM> and a combining circuit <NUM>. The combining circuit <NUM> may include a flip-flop <NUM>. The first oscillator <NUM> and the second oscillator <NUM> may be coupled to the flip-flop <NUM>.

The first oscillator <NUM> may generate a first oscillation signal OSC1 oscillating in a first frequency. The second oscillator <NUM> may generate a second oscillation signal OSC2 oscillating in a second frequency. The combining circuit <NUM> may combine the first oscillation signal OSC1 and the second oscillation signal OSC2 to generate an dynamic entropy bit E(n). The first oscillator <NUM> and the second oscillator <NUM> may be ring oscillators.

In some embodiments, the flip-flop <NUM> may sample the first oscillation signal OSC1 using the second oscillation signal OSC2, so as to generate the dynamic entropy bit E(n). In some embodiments, the first frequency and the second frequency are different, and each of the first frequency and the second frequency may be a multiple of a prime number, misaligning level transitions of the first oscillation signal OSC1 and the second oscillation signal OSC2. For example, the first frequency may be <NUM> and the second frequency may be <NUM>. Since one prime number multiple may not be fully divided by another prime number multiple, the flip-flop <NUM> may sequentially generate the dynamic entropy bit E(n). In other embodiments, the first frequency and the second frequency are substantially equal, e.g., the first frequency and the second frequency may both be <NUM>. Since the devices, the routing and the voltage and operating temperature environment of the first oscillator <NUM> and the second oscillator <NUM> may not be fully identical, the first oscillation signal OSC1 and the second oscillation signal OSC2 may continuously race with each other to arrive the flip-flop <NUM>, thereby sequentially generating an arbitrary logic level "<NUM>" or logic level "<NUM>" as the dynamic entropy bit E(n).

<FIG> is a flowchart of a method <NUM> of generating the output random number Srno for use in the random number generators <NUM> and <NUM>. The method <NUM> includes Steps S502 and S504 for generating the output random number Srno. Step S502 is used to update the lively random number pool <NUM> using the fixed and truly random numbers in the initial random number pool <NUM>. Step S504 is used to generate the output random number Srno and to constantly update the static random number pool <NUM>. Any reasonable step change or adjustment is within the scope of the disclosure. Steps S502 and S504 are explained as follows:.

The details of the method <NUM> have been provided in the preceding paragraphs, and will not be repeated here. The method <NUM> employs in the initiation phase the fixed set of truly random numbers in the initial random number pool <NUM> to generate the initial true random number sequence Strn and to initiate the static random number pool <NUM> with the initial true random number sequence Strn. Later in the operation phase, the method <NUM> employs the static random number pool <NUM> to output the output random number Srno while updating the static random number pool <NUM> in a constant manner, saving random number resources while ensuring data security.

<FIG> is a flowchart of a method for implementing Step S502 in <FIG>. The method includes Steps S602 to S612 for initiating the static random number pool <NUM> using the fixed set of truly random numbers in the initial random number pool <NUM>. Any reasonable step change or adjustment is within the scope of the disclosure. Steps S602 to S612 are explained as follows:.

The details of the method have been provided in the preceding paragraphs, and will not be repeated here. The method employs the fixed set of truly random numbers in the initial random number pool <NUM> to generate the initial true random number sequence Strn to update the static random number pool <NUM>. Therefore, devices employing the method may derive unique sets of truly random numbers from the fixed set of truly random numbers in the initial random number pool <NUM>, saving resources while ensuring data security.

<FIG> is a flowchart of a method for implementing Step S504 in <FIG>. The method includes Steps S701 to S712 for updating the static random number pool <NUM> in a continuous and iterative fashion and outputting the output random number Srno from the lively random number pool <NUM>. Step S701 is used to output the output random number Srno. Steps S702 to S710 are used to generate a new set of truly random numbers based on a previous set of truly random numbers. Step S712 is used to update the new set of truly random numbers into the lively random number pool <NUM>. Any reasonable step change or adjustment is within the scope of the disclosure. Steps S701 to S712 are explained as follows:.

Claim 1:
A random number generator (<NUM>, <NUM>), comprising:
a static random number generator (<NUM>) comprising an initial random number pool (<NUM>) and a static random number pool (<NUM>), and configured to output a static random number sequence (Ssrn) from one of the initial random number pool (<NUM>) and the static random number pool (<NUM>);
at least one dynamic entropy source (<NUM>(<NUM>) to <NUM>(N)) configured to generate an dynamic entropy bit (one of E(<NUM>) to E(N));
a counter (<NUM>) coupled to the at least one dynamic entropy source (<NUM>(<NUM>) to <NUM>(N)) and configured to generate a dynamic random number sequence (Sd) according to the dynamic entropy bit (one of E(<NUM>) to E(N)); and
a combining circuit (<NUM>) coupled to the static random number generator (<NUM>) and the counter (<NUM>), and configured to receive the static random number sequence (Ssrn), and output a true random number sequence (Strn) to a lively random number pool (<NUM>) according to the static random number sequence (Ssrn) and the dynamic random number sequence (Sd);
wherein the static random number pool (<NUM>) is configured to be updated when the lively random number pool (<NUM>) is fully updated;
during an operation phase, the static random number pool (<NUM>) is further configured to generate a subsequent static random number sequence (Ssrn(<NUM>)), and the combining circuit (<NUM>) is further configured to generate a subsequent true random number sequence (Strn) according to the subsequent static random number sequence (Ssrn(<NUM>)) and a subsequent dynamic random number sequence (Sd), and update the lively random number pool (<NUM>) according to the subsequent true random number sequence (Strn); and
the static random number sequence (Ssrn) has a hamming weight of substantially <NUM>%, a hamming distance of substantially <NUM>% and a min-entropy of substantially <NUM>.