I need to implement a true random number generator within a FPGA chip . I prefere NOT to rely on an external analog noise source . I ask your opnion on the following design idea I have in mind for this .
The basic idea is to sample a group of 16 bit vectors from a ring oscilator and to send out the vector that is most far from the last vector sent out before this one .
The algorythm might look like this :
1> Sample 10 vectors of 16 bit each from the ring oscilator
2> send out the most far vector from the last one sent
3> Sample again 10 vectors of 16 bit each from the ring oscilator
4> send out the most far vector from the last one sent
5... so on
Please express you opinion on this , is this a true random number generator ?
You are inducing a very, very, very large pair correlation if you insist on using the one that was furthest away from the previous one. So large that the result will be trivially bad.
A very good and readable introduction to random number generators - with specific examples of how horrible correlation is and a large number of "bad examples" - is in a book called "Numerical Recipes". Google it. Wikipedia has some accurate details on a broad range of pseudorandom generators but is not an especially good introduction for a newbie.
Mark of a newbie is insisting his pseudorandom generator is "pure random".
They generally combine multiple ring oscillators, of different length, with multiple pseudo-random sequence generators. The oscillators are random but have bad statistics; the sequencers have good stats but are not random. The idea is to combine them.
The "vector" you get by snapshotting bits of a ring oscillator will have a very bad distribution.
Make (N*2) ring oscillators that run much faster than 16x the reporting rate.
Make N shift register sets with an XOR input.
Wire a different ring oscillator to clock each shifter.
XOR one of the bits of the shifter with one oscillator to provide the data input to each shifter.
XOR combine randomly chosen bits of the different shifters to make the
16 bits of the output value.
This only works if the oscillators are not locking to each other etc. The noise on the inputs of the logic gates modulates the running frequency and phase making the oscillators noisy.
It is still not pure because there will be biases towards toggling or not toggling on given bits and noise from the bits flipping will get into the oscillators making different bits interact.
There is a significant difference in the requirements.
Bad idea, your generator will have stong statistical dependency.
Sample a ring oscillator for long enough period, then compute one way hash function from it. Make sure the size of the hash is less then the entropy of the source.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
There is the correlation with the power supply and the other activities of FPGA as well.
What happens if the RNG simply hangs up? What happens in the cases of EMI, ESD, mechanical shock, X-rays exposure, etc. ?
It is not very simple to make the cryptography grade RNG. In the actual designs that I have seen, there was a LOT of circuitry to verify and ensure the correct operation.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
In addition to the good points raised by others here, it's difficult to get truly random operation from two seemingly random oscillators. They tend to influence each other so don't give the randomness one would expect. Testing for randomness is required and non-trivial. To give a good distribution of results it's common to pass the outputs of the oscillators through an encryption box with a constant key.
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
-- John Von Neumann
Quoted in Chapter 3 of "The Art of Computer Programming" by Donald Knuth. Chapter three (the first chapter of Vol. 2) is dedicated to random numbers, including tests to apply to see if what you thing is random even comes close..
If you have an FPGA, look at XAPP052 from Xilinx, which gives implementations of long LFSR pseudo-random sequence generators, including taps for generators up to 168 bits in length. (2^168)-1 is a fairly large number. If that isn't long enough, combine one at 168 bits with one at 167 bits.
As Knuth points out in the start of Chapter 3, generally the more complex the mechanism, the worse the random number generator.
I believe a research project is in order on an observation commonly made about "new" random number generators on the net -- the cross product of generator quality and the decibel level of its proponent is a constant.
"Macroscopic processes described by classical physics can be used to generate random numbers. Typical chaotic processes include the monitoring of some electric noise current in a resistor or in a diode. This current is not random, but just very complex to describe. Determinism is hidden behind complexity. Although their random numbers are likely to pass randomness tests, these generators are difficult to model." (from
formatting link
) Strange no? The rest of the world considers these processes (shot noise etc) to be random, but these guys call it "Determinism"
There own process is not well described. How do they generate a single photon? And if they do generate single photons how do they get a 4 - 16 MB/s entropy rate. (IMO) It is not possible.
Their certificate of conformity
formatting link
is, while not bogus, is dubious. The Die Hard Tests are designed to test for apparent non-randomness in *Pseudo Random Number Generators* - passing these tests is insufficient to claim true randomness as the tests were never designed to test a true random number generator and even PRNG can pass if they are a little more sophisticated than average. The author of the Die Hard tests even provides several examples of PRNG's that will pass these tests.
They do not understand the significance of the probability tests. There stuff always passes the tests for randomness when set for a confidence level of 99%. If what they had was a TRNG then it would FAIL these tests
..and probability tests cannot "guarantee" randomness. Can a given value repeat? More than once? Then one might have a random source. Can any value repeat? More than once? Then one might have a random source. Is it a repeating sequence (never mind one might have to wait 10^20 years)? Then it is NOT random.
Is one value missing in the sequence (dead giveaway of a shift register implementation? Then it is NOT random.
IDQuantique specialise in quantum encryption using single photons. Whilst I wouldn't take their marketing material as gospel, I would assume that their products actually work.
That said, I am happy to use appropriately applied avalanche diodes or ring oscillators as entropy sources in my products.
Disclaimer: I sometimes work for a company that sometimes partners with IDQuantique.
Anything we make can be broken. Even a true random generator can fail. There always needs to be checks made.
If the X-rays are strong enough, the random generator stopping will be the least of the problems. The PCB turns into a plasma and flies outwards at relativistic speeds. There is likely to be some degradation of the communications link when this happens.
Yes, I very much agree. Even at well short of crypto, the effort to make sure the "random like" stuff is "random like" can take a little work. Just to model noisy data, you have to make sure that the "noise" and the method for removing it aren't somehow tuned to each other.
Are the odds for a given number unchanged by the numbers before and after it? Then one might have a random source. We need to rule out 1 1 2 2 3 3 4 4 5 5 .. 65536 65536 1 1 2 2 ... Unfortunately I remember reading that if you include the strongest version of this test, the logic leads to a contradiction.
There is a specific problem with the RNG applications: even if the generator is good by itself, it is hard to prove if the RNG is operating correctly or it is broken or has been tampered with. The consequences of that could be serious. The widely advertized ring oscillators seem to be very prone to tampering, malicious or just unintended.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.