Abstract:
A method of generating non-deterministic and non-periodic random bits including the steps of providing a plurality of noise generators; providing a trigger based upon an outside world input; sampling the output signal of one of the noise generators upon the provision of the trigger; generating a first random number based upon the value of the sampled signal; and wherein the identity of the noise generator to be sampled is determined based upon a previous random number generated.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    The present application is related to, and claims priority from, U.S. provisional Patent Application No. 60/917,096 filed on May 10, 2007, herein incorporated by reference. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The invention relates to non-deterministic statistical data generation. More specifically, the invention relates to a truly random, entropy generator. 
       BACKGROUND OF THE INVENTION 
       [0003]    Non-deterministic data generation is an avid pursuit in science dating back one and a half centuries. In some scientific circles truly random data is considered to be a representation of the essence of life and matter itself. Clandestine techniques of capturing non-deterministic data although slow, are currently in practice in college courses ranging from the study of statistics to physics to the ebb and flow of tides and the mutation of genes throughout human evolution. As humankind further adapts the modern computer to aid in scientific study, the appetite for randomness increases proportionally. 
         [0004]    When random numbers are pulled from truly non-deterministic data, they can be used in a wide range of business applications ranging from fair lotteries, stochastic studies in finance, poker machines and security applications for business. 
         [0005]    In his famous quote on the subject of randomness, John von Neumann clearly states “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number—there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.” John von Neumann, “Various techniques used in connection with random digits,” in A. S. Householder, G. E. Forsythe, and H. H. Germond, eds.,  Monte Carlo Method , National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38. 
         [0006]    Computers are purposely designed to be stateful machines. An average desktop computer today can execute 100 million instructions per second. Computer programs are fundamentally based on mathematical calculations. Producing truly random data from computer algorithms, no matter how tricky or seemingly complex the algorithm may be, is not possible. Computer programs are able to produce data that appears statistically random in every way and for some applications this pseudo-random data will suffice. Other applications require data to be truly random. Truly random data is distilled from truly random physical events. This distillation process need not be solely based upon “whitening” or software compensation for biased distribution. If captured from more than one type of physical source and in a plurality of each type of source, the entropy can be allowed to choose its own path in terms of random distribution. The strength of a random stream of bits of this nature is derived from the diversity of the origin of its seeds and the freedom of the seeds to interact with non-deterministic, non-periodic timing throughout the sampling process. 
       SUMMARY OF THE INVENTION 
       [0007]    A method of generating non-deterministic and non-periodic random statistical data comprising the steps of providing a plurality of noise generators; providing a trigger based upon an outside world input; sampling the output signal of one of the noise generators upon the provision of the trigger; generating a first random number based upon the value of the sampled signal; and wherein the identity of the noise generator to be sampled is determined based upon a previous random number generated. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]      FIG. 1  is a generalized diagram of a preferred embodiment of the present invention; 
           [0009]      FIG. 2  is a detailed diagram of a preferred embodiment of the present invention; 
           [0010]      FIG. 3  is a diagram of a system incorporating a non-deterministic statistical data generator for delivered non-deterministic statistical data to a client computer located remotely from the non-deterministic statistical data generator and for storage by the client for use at a later time in accordance with an embodiment of the invention; and 
           [0011]      FIG. 4  is a circuit diagram of the construction of a device according to an embodiment of the present invention. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0012]    While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail preferred embodiments of the invention with the understanding that the present disclosure is to be considered as an exemplification of the principles of the invention and is not intended to limit the broad aspect of the invention to the embodiments illustrated. 
         [0013]    The present invention comprises a method, system, and device for capturing statistically unbiased entropy using multiple non-deterministic, asynchronous sources, distilling random bits using microprocessors and multiple hashing algorithms, and distributing random bits for use by remote computer systems for any software process. In the preferred embodiment, the system employs three separate, electronic, asynchronous clocking mechanisms. Two of the separate, electronic, asynchronous clocking mechanisms comprise of gamma radiation detectors (Geiger Mueller counters). The two electronic, asynchronous clocking mechanisms serve as safeguards to provide the overall system with redundancy and added insurance that random bits selected are truly random and maintain non-deterministic qualities for the life span of the bits generated. The two electronic, asynchronous clocking mechanisms serve as triggers to start and stop the flow of entropy from multiple random noise generators in a non-deterministic fashion. A third electronic, asynchronous clocking mechanism may also be provided for changing the overall state of the system in a non-deterministic way thereby increasing the difficulty of guessing the state of the system at any given time. 
         [0014]    In a preferred embodiment, the invention employs a plurality of random number generating elements and a plurality of random number sources. In addition, the disclosure contains a system of two interdependent microcontrollers to collect the data from the random number sources. 
         [0015]    In that regard and referring to  FIG. 1 , there is provided a first processor  10  and a second processor  12 . The first processor  10  comprises an eight bit timer  24  counting from 0-255. The processors  10  and  12  are preferably PICmicro 18F4xxx microcontrollers. The microcontrollers sample the noise generators using their on-board A/D converters and respond to interrupts generated by detected nuclear decay events. 
         [0016]    Inputs  14 - 18  to the timer  24  are two Gtubes  20 , which comprise Geiger Mueller tubes, and four Nboxes  22  which comprise semiconductor noise generators. It will be understood by one of ordinary skill in the in art that while the preferred embodiment is described with respect to Geiger Mueller tubes, any outside world input could be used in place of the Geiger Mueller counters, such as inputs from detected radio frequency or from various weather systems. The input could be from quantum or chaotic system. The Gtubes  20  are exposed to a radioactive isotope, preferably Cs-137 which is a primary beta emitter and secondary gamma emitter. 
         [0017]    The Nboxes  22  preferably comprise eight zener diodes that are AC coupled to a high-gain operational amplifier with a gain of about 2000×. When a Gtube  20  detects a radioactive event, the other Gtube  20  is cancelled out by an OR function. Upon an event detection in one of the Gtubes  20 , a value is sampled from the eight bit timer  24  and the value of the timer  24  is sent to the second processor  12 . 
         [0018]    The first processor samples a 10 bit value from one of the Nboxes  22 , and the eight lowest bits are trimmed from the 10 bit value and become the next initial state of the timer  24 . 
         [0019]    The second processor  12  operates as with the first processor  10  except it comprises only a single Gtube  20 , as the processor  12  is also responsible for forwarding random numbers to a requesting source. As a result, the timer  24  of the second processor  12  comprises only one input  26 . Moreover, the values from the first processor  10  and the second processor  12  are passed through an XOR function to determine whether a random number from the first processor  10  or the second processor  12  will be output. 
         [0020]    An embodiment of the present invention is shown in even greater detail in  FIG. 2 . The four Nboxes  22  of the first processor  10  all supply analog random noise signals to an Nbox shift logic  30 , which determines which of the Nbox outputs will be used by the first processor  10 , and samples and converts the analog signal to a 10 bit digital value. The lower 8 bits of the sampled analog signal are stored at adresl  32  and the top two bits are stored at adresh  34 . The top byte, adresh  34 , contains only two bits, but is still referenced as a byte with the top six bits always equal to zero. 
         [0021]    The Gtubes  20  utilizes a timer, known as tmr 0  in the graphic, whose current state is stored as a sixteen bit value available as two bytes, tmr 0   h    36  and tmr 0   l    38 . 
         [0022]    The Nbox shift logic  30  continuously samples data from the four Nboxes  22 , one at a time. The Nbox  22  to be selected as the next source is determined by the bottom two bits of the previous result. 
         [0023]    Several registers are assigned values by the Nbox shift logic  30 . analog-pick  40  assumes the verbatim value of adresl  32 , and this register is used to pick the next Nbox  22  source, as discussed above. analog-reg  42  stores the xored product of itself and adresl  32 . topbits  44  is an 8-bit register that updates two bits at a time from adresh. buffer-pick  46  takes the value of adresl  32 . A modulus operation is then performed to produce a value between zero and BUF-LEN minus 1, as described below. 
         [0024]    Upon the low to high signal of a Gtube  20 , the first processor  10  immediately interrupts what it is doing and records the corresponding timer values in to tmrl-reg  48  and tmrh-reg  50 . In this manner, the Gtube  20  logic works asynchronously to update its state. They update their state via the timer shift logic. tmr 0   130  updates via tmr 0   l _output xor&#39;d ciphertext, while tmr 0   h    50  is updated by tmr 0   h _output xor&#39;d with ciphertext. After the timer values, tmr 0   l    36  and tmr 0   h    38  are stored, they are randomized using analog-reg  42  xored with two contingent bytes (one for each register) that is referenced by buffer-pick  46 . The first byte is at the location described by buffer-pick  46 , the second byte pulled from the previous location. 
         [0025]    The EFB register system  52  contains a register that holds limited number of transformed previous outputs. The length of this register is determined by the constant BUF_LEN. The EFB  52  is updated after every new adresl  32  and adresh  34  result. The EFB  52  does not depend on a new Geiger value, as one can never be guaranteed. 
         [0026]    The EFB  52  utilizes three registers and one buffer. The registers are named regl  54 , reg 2   56 , and ciphertext  58 . The data moves in a circular manner and is transformed on each cycle, unless it is held in buffer  60 . regl  54  and reg 2   56  are used to transform data that is moving through the cycle, regl  54  contains the xored product of itself, tmrl reg  48  and analog_reg  42 . reg 2   56  contains the xored product of itself, tmrh reg  50  and topbits  44 . ciphertext  58  is the output register. The data flow starts with the byte contained in the end of the buffer  60 . This byte is xored with reg 2   56  and stored in ciphertext  58 . ciphertext  58  is then xored with reg 1   54  and stored in the beginning of the buffer. 
         [0027]    In  FIG. 2 , the second processor  12  operates in the same manner as the first processor  10  except that only a single Gtube  20  is preferably used in the second processor  12  and the second processor receives the output of the first processor  10  as an input and XORs the output of the first processor  10  with the output of the second processor  12  and outputs the result. 
         [0028]    In  FIG. 3 , the random number generating device described above is shown diagrammatically as reference numeral  100 . The non-deterministic statistical data generator  100  communicates with a host server  102  which delivers non-deterministic statistical data to various client server  104  who request non-deterministic statistical data through a local or wide area network  106 , such as the internet. Software  108  then stores the received non-deterministic statistical data in a random pool  110  until they are requested. 
         [0029]    The transmission of random data is accomplished using a standard RS232 serial interface. The baud rate on the interface is preferably variable between 1.2 Kb/s to 230 Kb/s. 
         [0030]    The second half of the Invention is a separate, single board, embedded computer that serves as a dedicated host. The host collects the raw entropy from the invention and uses this stream in conjunction with an arbitrary symmetric-key cipher in CBC mode. Based upon the raw data a key is derived and an arbitrary amount of data is collected and encrypted. Also based upon the raw data is a value known as the compounding factor. This value is arbitrary. For the reference design this value can be any whole number between 0 and 31, inclusive. The use of the compounding factor is implemented by recycling previous states of the entropy pool for the number of times the value holds. Each compounding is performed by a rekeying of the cipher, the collection of original data, and the encryption of both the original data and the previous state of the machine. After the number of iterations equals that of the compounding factor, the internal state of the program is reinitialized and the previous state is flushed. 
         [0031]    When transmitting data to its clients, the server  102  maintains a series of interrelated entropy pools. No one pool can contain a contiguous set of data generated by the non-deterministic statistical data generator  100 . Instead, blocks for each pool are sampled non-deterministically using raw data from the non-deterministic statistical data generator  100 . The blocks are also transmitted out of order. In effect, no one (or n multiples) of users can effectively reconstruct the data and extrapolate any usable structure from the data. The mechanism is designed to make it impossible to determine to any degree of certainty what state the machine was in when the entropy was produced. 
         [0032]    A non-deterministic statistical data generator according to the preferred embodiment can supply  100  servers enough entropy to generate at least 359,424 128 bit non-deterministic integers per server per 24-hour period. 
         [0033]    In an alternative embodiment, the design splits the single printed circuit board of the first embodiment into 2 separate boards. A first board acts as an instrumentation board and comprises two noise generators, for example Geiger counters, rather than the eight noise generators of the first embodiment. By reducing the number of noise generators, faster sampling rates and processing speeds are achieved. In the second embodiment, many more asynchronous elements can easily be added when needed and in this way, the new design is modular. The second printed circuit board is the processor board. It uses one processor rather than two as in the first embodiment. The processor board handles the data coming in from the instrumentation board and treats the data in a mathematically optimized manner as described in the first embodiment. When data is ready for output, the data is carried over a single 10/100 Ethernet port at a rate of about 6-7 megabits per second. 
         [0034]    An exemplary device according to the present invention may be constructed from the embodiment shown in  FIG. 4  with the components described below. 
         [0000]    
       
         
               
               
               
               
               
               
             
           
               
                   
               
               
                 Qty 
                 RefDes 
                 Part # 
                 Description 
                 Package 
                 Type 
               
               
                   
               
             
             
               
                 2 
                 R1, R2 
                 263-10M-RC 
                 Xicon 1206 Resistor 10 MΩ 
                 “1206” 
                 SMT 
               
               
                 2 
                 C1, C2 
                 0603YC105KAT2A 
                 AVX 0603 Ceramic 1.0 uF 
                 “0603” 
                 SMT 
               
               
                 1 
                 IC3 
                 MC14049UBDR2G 
                 ON Semi 4049 Inverter 
                 SOIC-16 
                 SMT 
               
               
                 2 
                 Q1, Q2 
                 BCW66G 
                 Fairchild Transistor 
                 SOT-23 
                 SMT 
               
               
                 2 
                 R5, R6 
                 CRCW0603100KJNEA 
                 Vishay 0603 100K 
                 “0603” 
                 SMT 
               
               
                 1 
                 U7 
                 AP1117Y33L-13 
                 Diodes Inc 3.3 V Lin Reg 
                 SOT-89 
                 SMT 
               
               
                 4 
                 C4, C5, 
                 C2012X5R1A225K 
                 TDK 0805 Ceramic 2.2 uF 
                 “0805” 
                 SMT 
               
               
                   
                 C6, C7 
               
               
                 1 
                 IC4 
                 MC7812AECT 
                 Fairchild 12 Lin Reg 
                 TO-220 
                 Thru 
               
               
                 2 
                 R3, R4 
                 RK73H2ATTD4703F 
                 KOA 0805 470 KΩ 
                 “0805” 
                 SMT 
               
               
                 1 
                 U3 
                 4824-6000-CP 
                 3M 24 pin DIP Socket 
                 DIP24 
                 Thru 
               
               
                 1 
                 J1 
                 90130-1240 
                 Molex 40 Pin C-Grid 
                 Thru 
                 Thru 
               
               
                   
                   
                   
                 Header 
               
               
                 2 
                 U1, U2 
                 AD7276BRM 
                 Analog Device A/D 
                 MSOP-8 
                 SMT 
               
               
                 2 
                 IC1, IC2 
                 SMN7103H 
                 Micronetics Noise Gen 
                 Atypical 
                 Leadless 
               
               
                   
               
             
          
         
       
     
         [0035]    The above examples show that the invention, as defined by the claims, has far ranging application and should not be limited merely to the embodiments shown and described in detail. Instead the invention should be limited only to the explicit words of the claims, and the claims should not be arbitrarily limited to embodiments shown in the specification. The scope of protection is only limited by the scope of the accompanying claims, and the Examiner should examine the claims on that basis.