Random number generator

Patent metadata

Field	Value
Publication number	US-9928036-B2
Application number	US-201514865009-A
Country	US
Kind code	B2
Filing date	Sep 25, 2015
Priority date	Sep 25, 2015
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

Abstract

A processor includes an execution unit to generate a random number. The execution unit includes entropy source circuits, correlation circuits, and an extractor circuit. The entropy source circuits include all-digital components and are to generate an initial randomized bit stream. The correlation circuits are to remove correlations from the initial randomized bit stream to yield an intermediate randomized bit stream. The extractor circuit is to select a subset of the intermediate randomized bit stream as a random output of the execution unit.

First claim

What is claimed is:

1. A processor, comprising:
a front end to decode an instruction, the instruction to generate a random number;
an execution unit;
an allocator to assign the instruction to the execution unit to execute the instruction;
wherein the execution unit includes:
a plurality of entropy source circuits, wherein each of the plurality of entropy source circuits comprises all-digital components, and each of the plurality of entropy source circuits is to generate a respective initial randomized bit stream;
a plurality of correlation circuits to generate a plurality of intermediate randomized bits streams from the initial randomized bit streams generated by the plurality of entropy source circuits, wherein each of the correlation circuits is to receive a respective one of the initial randomized bit streams and remove correlations from the received initial randomized bit stream to yield a respective intermediate randomized bit stream; and
an extractor circuit to:
receive the plurality of intermediate randomized bit streams; and
generate, from the plurality of intermediate randomized bit streams, a random output of the execution unit, wherein the random output is to fulfill at least part of the instruction execution.

2. The processor of claim 1 , wherein each of the plurality of entropy source circuits includes a tunable delay circuit, the tunable delay circuit to adjust randomness output of the entropy source circuit.

3. The processor of claim 1 , wherein each of the entropy source circuits includes a cross-coupled inverter pair to generate random output.

4. The processor of claim 1 , wherein each of the plurality of correlation circuits is to:
combine an element from the corresponding initial randomized bit stream with previous bits received from the entropy source circuit; and
randomize the element with respect to a corresponding element from the previous bits to remove correlation.

5. The processor of claim 1 , wherein generating the random output comprises selecting bits from bit ranges of the plurality of correlation circuits that do not overlap with each other in order to select a subset of the plurality of intermediate randomized bit streams.

6. The processor of claim 1 , wherein the extractor circuit is further to apply a reduction with a polynomial to the plurality of intermediate randomized bit streams to yield the random output.

7. The processor of claim 1 , wherein the extractor circuit is further to apply a Galois Field multiplication and addition operations to the plurality of intermediate randomized bit streams to yield the random output.

8. A method, comprising:
generating a plurality of initial randomized bit streams using a plurality of entropy source circuits, wherein each of the plurality of entropy source circuits includes all-digital components;
removing correlations in the plurality of initial randomized bit streams using a plurality of correlation circuits to yield a plurality of intermediate randomized bit streams; and
generating a random output of an execution unit from the plurality of intermediate randomized bits streams using an extractor circuit.

9. The method of claim 8 , further comprising adjusting randomness output of the entropy source circuits with one or more tunable delay circuits.

10. The method of claim 8 , wherein generating the plurality of initial randomized bit streams comprises routing outputs of each of a cross-coupled inverter pair to the respective inputs of each other.

11. The method of claim 8 , further comprising, wherein generating the plurality of intermediate randomized bits streams comprises:
combining an element from one of the initial randomized bit streams with previous bits received from a corresponding one of the entropy source circuits; and
randomizing the element with respect to a corresponding element from the previous bits to remove correlation.

12. The method of claim 8 , wherein generating the random output comprises selecting bits from bit ranges of the plurality of correlation circuits that do not overlap with each other in order to select a subset of the plurality of intermediate randomized bit stream.

13. The method of claim 8 , further comprising, with the extraction circuit, wherein generating the random output comprises applying a Galois Field multiplication and addition operations to the intermediate randomized bit streams to yield the random output.

14. A random number generator logic unit, comprising:
a plurality of entropy source circuits, wherein each of the plurality of entropy source circuits comprises all-digital components, and each of the plurality of entropy source circuits is to generate a respective initial randomized bit stream;
a plurality of correlation circuits to generate a plurality of intermediate randomized bits streams from the initial randomized bit streams generated by the plurality of entropy source circuits, wherein each of the correlation circuits is to receive a respective one of the initial randomized bit streams and remove correlations from the received initial randomized bit stream to yield a respective intermediate randomized bit stream; and
an extractor circuit to:
receive the plurality of intermediate randomized bit streams; and
generate, from the plurality of intermediate randomized bit streams, a random output of the execution unit.

15. The random number generator logic unit of claim 14 , wherein each of the plurality of entropy source circuits includes a tunable delay circuit, the tunable delay circuit to adjust randomness output of the entropy source circuit.

16. The random number generator logic unit of claim 14 , wherein each of the entropy source circuits includes a cross-coupled inverter pair to generate random output.

17. The random number generator logic unit of claim 14 , wherein each of the plurality of correlation circuits is to:
combine an element from the corresponding initial randomized bit stream with previous bits received from the entropy source circuit; and
randomize the element with respect to a corresponding element from the previous bits to remove correlation.

18. The random number generator logic unit of claim 14 , wherein the extractor circuit is further to select bits from bit ranges of the correlation circuit that do not overlap with each other in order to select the subset of the intermediate randomized bit stream.

19. The random number generator logic unit of claim 14 , wherein generating the random output comprises applying a reduction with a polynomial to the plurality of intermediate randomized bit stream to yield the random output.

20. The random number generator logic unit of claim 14 , wherein the extractor circuit is further to apply a Galois Field multiplication and addition operations to the plurality of intermediate randomized bit streams to yield the random output.

Assignees

• Intel Corp

Inventors

• Mathew Sanu K
• Johnston David
• Satpathy Sudhir K

Classifications

• G06F7/588 Primary

  Random number generators, i.e. based on natural stochastic processes · CPC title

• G06F2207/58

  Indexing scheme relating to groups G06F7/58 - G06F7/588 · CPC title

• G06F7/483

  Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)} · CPC title

• H04L9/0637

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• H04L9/0869

  involving random numbers or seeds · CPC title