Random Number Generation in VHDL

I think Jenny tried using ring oscillators to get a seed, but found that given enough time the ring oscillators sync'ed up thanks to parasitics. I was hoping she'd post here and maybe provide a link to her thesis.

That would always be a risk, but you could use multiple ring-osc, and run them one at a time ?

I did find them to be very good thermometers :)

Targeting the metastable window would be another approach, but that seems to be very narrow. Be interesting to see plots of time/aperture width ..

-jg

I think one approach she was looking at was a high order LFSR seeded by a state machine that divined the phase difference between a pair of ring oscillators. The idea was to obtain a random seed before the ring oscillators got a chance to sync up, and then use the LFSR to get the random sequence. The seeding is necessary to get a random start point in the LFSR. Still, that doesn't give a true random. I know she was looking for techniques that would pass a battery of randomness tests, and very few approaches actually did. I'll give her a call to try to get her to speak up here, and maybe put her thesis up on the 'net somewhere.

Have 'hash functions' been investigated? E.g.:

(Converting the code in the reference from Java to VHDL isn't difficult but I am not allowed to post my version).

For instance, use an LFSR to generate the inputs to the hash function, an use the output of the hash function as the 'random'.

But the referenced article does suggest using the Mercenne Twister...

Hi I am new to this group. I am an undergraduate student working on an implementation of RSA on an FPGA. I am using a LFSR for random number generation, but I also need a random state of the LFSR to begin with, don't I? How do I get that? What does one do in such a case? I don't want to restart the whole random no. generation business with a new method!!

I want the user to get a different key each time he uses the key generation system.

Thanks

Generally speaking, you need some source of entropy external to the FPGA. For instance, if you put a counter in the FPGA that is clocked at a fairly high frequency, and use it to measure the time between switch presses by a human operator, the low bits of the counter can be used as a source of entropy.

Another approach I've seen used is to measure how long it takes an analog PLL to lock.

With any timing-based method, you can't get too many bits of entropy per event, or they won't be sufficiently random.

Make a ring counter which nearly oscillates at 1/1024th (say) frequency as your off-chip clock.

Divide the external clock by 1024, then compare and count the phase difference in clock cycles.

Hey presto a random number ! (well nearly) which is different every time you switch on.

You have to be careful using a ring oscillator on-chip, as chip parasitics will cause it to sync up to other clocks on the chip, and you will lose randomness. That said, as long as you use the ring oscillator right at start-up before it has an opportunity to lock to the system clock, you will probably be OK.

Alternatively, if you have two independent external clocks, you can use a divided version of one to capture the state of a toggle flip-flop clocked by the other (or a divided version of the other) to determine if there are an even or odd number of clocks between successive edges. Assuming the two clocks are truely asynchronous to one another, you will get a good quality one bit random for each event. Use successive events to assemble a parallel seed value (note for an LFSR you can just clock the bits in as they occur, so there is no need to deserialize it.

Additionally, the LFSR only produces one new pseudo-random bit for each clock, so if you need more than a 1 bit random, you need to operate the LFSR for the number of clock cycles equal to number of bits you need. Obviously, the LFSR has to have a long enough sequence so that only a small fraction of the cycle is completed within your longest observation window in order for the bits to appear random.

If your clocks really are de-correlated, then you don't need the LFSR at all, you can just use the odd/even timing measurement of the successive edges between the two clocks and get a good random.