Cryptographic Random Number Generator Using Finite Field Operations

Abstract

An apparatus and method are provided in various illustrative embodiments for an integrated circuit chip that provides a fast, compact, and cryptographically strong random number generator. In one illustrative embodiment, an apparatus includes an initial random source, and a post-processing block in communicative connection with the initial random source. The post-processing block is configured to receive signals from the initial random source, to apply one or more finite field operations to the signals to generate an output, and to provide an output signal based on the output via an output channel, in this illustrative embodiment.

1 . An apparatus comprising:
 an initial random source; and   a post-processing block in communicative connection with the initial random source, where the post-processing block is configured to receive an input signal selected based on the initial random source, to apply one or more finite field operations to the input signal to generate a randomized output, and to provide an output signal via an output channel wherein the output signal is based at least in part on the randomized output.   
     
     
         2 . The apparatus of  claim 1 , wherein the one or more finite field operations the post-processing block is configured to apply to the input signal comprise at least one operation selected from among a group consisting of: finite field addition, finite field multiplication, and finite field squaring. 
     
     
         3 . The apparatus of  claim 2 , wherein the one or more finite field operations the post-processing block is configured to apply to the input signal further comprise at least one additional operation selected from among: finite field addition, finite field multiplication, and finite field squaring. 
     
     
         4 . The apparatus of  claim 3 , wherein the one or more finite field operations the post-processing block is configured to apply to the input signal comprise both finite field multiplication and finite field squaring. 
     
     
         5 . The apparatus of  claim 1 , wherein the one or more finite field operations the post-processing block is configured to apply to the input signal comprise finite field operations over a Galois field of a prime number to the nth power, where n is a prime integer. 
     
     
         6 . The apparatus of  claim 5 , the post-processing block is further configured such that n is selected from a group consisting of: 17, 19, 23, 29, and 31. 
     
     
         7 . The apparatus of  claim 5 , wherein the prime number is 2. 
     
     
         8 . The apparatus of  claim 1 , wherein the post-processing block is further configured to provide the output signal as a subset of bits from the randomized output. 
     
     
         9 . The apparatus of  claim 1 , wherein the initial random source comprises a ring oscillator. 
     
     
         10 . The apparatus of  claim 9 , wherein the ring oscillator comprises a plurality of series-connected elements, wherein the elements comprise at least one element type selected from a group consisting of: inverters, buffers, logic-OR gates, and logic-AND gates. 
     
     
         11 . The apparatus of  claim 9 , wherein the initial random source comprises a plurality of ring oscillators. 
     
     
         12 . The apparatus of  claim 1 , wherein the initial random source comprises a pseudo-random source. 
     
     
         13 . The apparatus of  claim 12 , wherein the pseudo-random source comprises a linear feedback shift register. 
     
     
         14 . The apparatus of  claim 1 , wherein the initial random source and the post-proces sing block are comprised in a first random number generator, wherein the apparatus further comprises one or more additional random number generators operating in parallel to the first random number generator, wherein the apparatus is configured such that the output signal comprises random bits from each of the first random number generator and the one or more additional random number generators. 
     
     
         15 . The apparatus of  claim 1 , further comprising one or more additional elements in communicative connection with the post-processing block and configured to receive the output signal from the post-processing block and to perform one or more additional transformations of the output signal. 
     
     
         16 . A method comprising:
 generating an initial random signal;   using the initial random signal as a control signal to select from among a plurality of optional input signals;   performing one or more finite field operations on the input signals; and   providing an output signal based at least in part on a result of the one or more finite field operations.   
     
     
         17 . The method of  claim 16 , wherein the finite field operations comprise one or more operations selected from among a group consisting of: finite field addition, finite field multiplication, and finite field squaring. 
     
     
         18 . An integrated circuit device comprising:
 a ring oscillator;   a multiplexer comprising two data signal inputs, a control signal input, and an output, where the control signal input is communicatively connected to an output of the ring oscillator;   a finite field multiplication component comprising first and second inputs and an output, wherein the first input of the finite field multiplication component is communicatively connected to the output of the multiplexer;   a finite field squaring component comprising an input and an output, wherein the output of the finite field squaring component is communicatively connected to the second input of the finite field multiplication component; and   an accumulator comprising an input and an output, wherein the input of the accumulator is communicatively connected to the output of the finite field multiplication component, and the output of the accumulator is communicatively connected to both the input of the finite field squaring component, and to an output channel.   
     
     
         19 . The integrated circuit device of  claim 18 , wherein the finite field multiplication component is configured to multiply over a finite field of 2 to the nth power, where the finite field multiplication component comprises approximately 7n 2  logic NAND gates. 
     
     
         20 . The integrated circuit device of  claim 18 , wherein the finite field squaring component is configured to perform a cyclic shift of an input binary vector.