Metastable flip-flop based true random number generator (TRNG) structure and compiler for same

• US 10,599,796 B2
• Filed: 10/04/2017
• Issued: 03/24/2020
• Est. Priority Date: 04/28/2017
• Status: Active Grant

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Inventors: Zhou, Charlie, Huang, Tze-Chiang, Liu, Jack
• Primary Examiner(s): Jones, Hugh M
• Application Number:
  US15/724,671
• Publication Number:
  US 20180314781A1
• Time in Patent Office: 902 Days
• Field of Search: 703 14
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A true random metastable flip-flop (TRMFF) compiler generates an electrical architecture for a TRMFF chain. The compiler selects components for the TRMFF chain from a library of standard cells and logically connects these components in accordance with a primitive polynomial to generate the electrical architecture. The TRMFF chain provides a sequence of random numbers from one or more physical processes in accordance with the primitive polynomial. During operation, one or more microscopic phenomena inside and/or outside of the TRMFF chain can cause one or more low-level, statistically random entropy noise signals to be present within the TRMFF chain. The TRMFF chain advantageously utilizes the one or more low-level, statistically random entropy noise signals to provide the sequence of random numbers.

Claims

1. A computer system for generating a model of a true random metastable flip-flop (TRMFF) chain, the computer system comprising:

a memory that stores a compiler; and

a processor configured to execute the compiler, the compiler, when executed by the processor configuring the processor to;

receive one or more first standard cells corresponding to a metastable flip-flop and one or more second standard cells corresponding to a complement of the metastable flip-flop;

receive one or more third standard cells corresponding to logic circuitry; and

interconnect the one or more first standard cells, the one or more second standard cells, and the one or more third standard cells in accordance with a predefined primitive polynomial to generate a model of the TRMFF chain.

2. The computer system of claim 1, wherein the one or more first standard cells comprise:

a model of the metastable flip-flop in a software language, and

wherein the one or more second standard cells comprise;

a model of the complement of the metastable flip-flop in the software language.

3. The computer system of claim 1, wherein the compiler, when executed by the processor configures the processor to:

receive an equivalent number of the one or more first standard cells and the one or more second standard cells.

4. The computer system of claim 1, wherein the compiler, when executed by the processor configures the processor to:

interconnect the one or more first standard cells, the one or more second standard cells, and the one or more third standard cells in accordance with a plurality of coefficients of the predefined primitive polynomial.

5. The computer system of claim 4, wherein the compiler, when executed by the processor configures the processor to:

couple the one or more first standard cells and the one or more second standard cells to generate a metastable flip-flop chain, and

couple a plurality of signal pathways between the metastable flip-flop chain and the one or more third standard cells corresponding to the logic circuitry in accordance with the plurality of coefficients of the predefined primitive polynomial to generate the model of the TRMFF chain.

6. The computer system of claim 5, wherein the compiler, when executed by the processor configures the processor to:

couple a signal pathway from among the plurality of signal pathways to the one or more third standard cells corresponding to the logic circuitry when its corresponding, coefficient from among the plurality of coefficients is a one; and

not couple the signal pathway to the one or more third standard cells corresponding to the logic circuitry when its corresponding coefficient from among the plurality of coefficients is a zero.

7. The computer system of claim 1, wherein the compiler, when executed by the processor further configures the processor to:

import the model of the TRMFF chain into a library of standard cells as one or more fourth standard cells.

8. A true random metastable flip-flop (TRMFF) chain, comprising:

a plurality of TRMFFs configured to provide a plurality of random numbers in accordance with a plurality of degrees of a polynomial, each TRMFF from among the plurality of TRMFFs corresponding to a degree from among the plurality of degrees and a coefficient from among a plurality of coefficients of the polynomial; and

first logic circuitry configured to perform one or more logical operations on a digital input seed and random numbers from among the plurality of random numbers corresponding to TRMFFs from among the TRMFFs whose coefficients from among the plurality of coefficients are ones to provide a digital output seed to the plurality of TRMFFs.

9. The TRMFF chain of claim 8, wherein a first TRMFF from among the plurality of TRMFFs comprises:

a first metastable flip-flop configured to sense one or more statistically random entropy noise signals corresponding to one or more microscopic phenomena to provide a first random output bit;

second logic circuitry configured to perform one or more first logical operations on the first random output bit in accordance with, the digital output seed to provide a first random output sequence of bits; and

a first flip-flop configured to re-time the first random output sequence of bits in accordance with a clocking signal to provide a first random number from among the plurality of random numbers.

10. The TRMFF chain of claim 9, wherein the first metastable flip-flop is configured to adjust a bias of the first random output bit to be, on average, a similar number of logical ones and logical zeros over a given duration of time.

11. The TRMFF chain of claim 9, wherein the first TRMFF corresponds to a least significant degree from among the plurality of degrees of the polynomial.

12. The TRMFF chain of claim 9, wherein a second TRMFF from among the plurality of TRMFFs comprises:

a second metastable flip-flop configured to sense the one or more statistically random entropy noise signals corresponding to the one or more microscopic phenomena to provide a second random output bit;

third logic circuitry configured to perform one or more second logical operations on the second random output bit in accordance with the first random number to provide a second random output sequence of bits; and

a second flip-flop configured to re-time the second random output sequence of bits in accordance with the clocking signal to provide a second random number from among the plurality of random numbers.

13. The TRMFF chain of claim 8, wherein a number of TRMFFs of the plurality of TRMFFs corresponds to a number of degrees of the plurality of degrees of the polynomial.

14. The TRMFF chain of claim 8, wherein at least one TRMFF from among the plurality of TRMFFs is a complement of a second TRMFF from among the plurality of TRMFFs.

15. The TRMFF chain of claim 8, wherein the first logic circuitry is further configured to not perform the one or more logical operations on random numbers from among the plurality of random numbers corresponding to TRMFFs from among the TRMFFs whose coefficients from among the plurality of coefficients are zeros.

16. A true random metastable flip-flop (TRMFF) chain, comprising:

a plurality of TRMFF chains configured to provide a plurality of random numbers in accordance with a plurality of polynomials, each TRMFF chain from among the plurality of TRMFF chains comprising;

a plurality of TRMFFs configured to provide a corresponding set of random numbers from among the plurality of random numbers in accordance with a plurality of degrees of a corresponding polynomial from among the plurality of polynomials, each TRMFF from among the plurality of TRMFFs corresponding to a degree from among the plurality of degrees and a coefficient from among a plurality of coefficients of the corresponding polynomial, and

first logic circuitry configured to perform one or more logical operations on a digital input seed and random numbers from among the corresponding set of random numbers corresponding to TRMFFs from among the TRMFFs whose coefficients from among the plurality of coefficients are ones to provide a digital output seed to the plurality of TRMFFs.

17. The TRMFF chain of claim 16, wherein the plurality of polynomials are similar polynomials.

18. The TRMFF chain of claim 16, wherein a first TRMFF from among the plurality of TRMFFs comprises:

a first metastable flip-flop configured to sense one or more statistically random entropy noise signals corresponding to one or more microscopic phenomena to provide a first random output bit;

second logic circuitry configured to perform one or more first logical operations on the first random output bit in accordance with the digital output seed to provide a first random output sequence of bits; and

a first flip-flop configured to re-time the first random output sequence of bits in accordance with a clocking signal to provide a first random number from among the plurality of random numbers.

19. The TRMFF chain of claim 18, wherein a second TRMFF from among the plurality of TRMFFs comprises:

a second metastable flip-flop configured to sense the one or more statistically random entropy noise signals corresponding to the one or more microscopic phenomena to provide a second random output bit;

third logic circuitry configured to perform one or more second logical operations on the second random output bit in accordance with the first random number to provide a second random output sequence of bits; and

a second flip-flop configured to re-time the second random output sequence of bits in accordance with the clocking signal to provide a second random number from among the plurality of random numbers.

20. The TRMFF chain of claim 16, wherein the first logic circuitry is further configured to not perform the one or more logical operations on random numbers from among the plurality of random numbers corresponding to TRMFFs from among the plurality of TRMFFs whose coefficients from among the plurality of coefficients are zeros.