Last visit was: Wed May 22, 2024 6:02 pm
It is currently Wed May 22, 2024 6:02 pm



 [ 12 posts ] 
 Random seed generation 
Author Message

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
Pondering over random number generation, what is needed is a random seed generator which can then be used by the typical random number generator. I was viewing a hardware device, but it is quite expensive.

For random number seed generation, I am thinking that a typical random number generator can be used, if it is continuously running and powered from time of manufacture. Only one seed at the very beginning is needed; the seed could be programmed when the device is built. Once power is applied to the generator if it is never removed then the number output by the generator likely won’t be predictable by the time it is used in a circuit.

I wonder if a PRNG can be built using the FPGA and the RNG value periodically saved to battery backed up RAM in a real-time-clock module. The backed up, value in the RAM could then later be used to seed the generator in the FPGA when the circuit is restarted after power-on.

_________________
Robert Finch http://www.finitron.ca


Sat Feb 18, 2023 4:09 am WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1786
I think this story very much depends on the threat model. Is the user merely concerned that they should never see the same series of numbers when they run their application? Or are these numbers intended for cryptographic purposes such that they could never be guessed?

In the ordinary case, using the current time would be enough, and the RTC is a good story there. Simply using the number of cycles since boot (or the number of video frames, or the number of milliseconds, or the number of RAM refresh cycles) would be enough in most cases.

But in the cryptographic case, again depending on threat model, you might need to be even more careful. It's well-known that it's unwise to create your own cryptographics primitives - unless, of course, you're only doing it for fun.

In all cases, it's the amount of entropy which matters, and so the capacity of the RTC's non volatile memory is going to be important. A couple of bytes would probably only be useful for theoretical interest, whereas 256 bytes would probably be enough for almost any purpose.


Sat Feb 18, 2023 7:53 am
User avatar

Joined: Sun Dec 19, 2021 1:36 pm
Posts: 75
Location: Michigan USA
Hardware Random Number Generators (RNG) are an interesting topic. About 10 years ago I was experimenting with building a simple RNG using a reverse-biased bipolar transistor junction. I sampled the noise with a PIC microcontroller, selected the most random bit, and transmitted the data sample using a serial port output. I attached a photo of the device and the circuit diagram. Here is a link to the short writeup:

http://www.mtmscientific.com/rng.html

Slightly off topic, I am writing an RND function for my LANG language and decided what I would do for the seed is prompt the user to hit a key while a really fast counter is running. Seems like I have seen somewhere a simple algo for using that seed that was easy to implement but don't remember the trick(s)?

Random numbers can be a real rabbit hole. In the course of building my hardware RNG I happened across some old tests for random numbers called DIEHARD. The documentation is really interesting to read. I put that in the zip file on the documentation at my website.


You do not have the required permissions to view the files attached to this post.


Sat Feb 18, 2023 11:12 am WWW

Joined: Sun Oct 14, 2018 5:05 pm
Posts: 62
If the system is interactive why not increment a counter while it's waiting for a keypress? Then the first call to the random function can use this counter as the initial seed and off you go.

Or a simpler hardware solution with no interactive input - a reverse biased diode will generate noise - amplify/clip/schmitt the signal and fed it into a 1-bit input. Make N samples of this signal to use as the seed?

-Gordon


Sat Feb 18, 2023 3:02 pm

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1786
There's a simple trick in case the initial random stream might be biased, which is to take 01 as a zero, 10 as a one, and ignore any 00 or 11 pair. I think that's how it goes. (It's by von Neumann, apparently.)


Sat Feb 18, 2023 5:39 pm
User avatar

Joined: Sun Dec 19, 2021 1:36 pm
Posts: 75
Location: Michigan USA
I see the Von Neumann trick you mention is called the Von Neumann Correction. Here is a link to the original paper where he mentions this approach, which he explains by the example of flipping a coin that is biased. This paper also contains the quote I have seen elsewhere "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin." Those guys really had a sense of humor.

https://dornsifecms.usc.edu/assets/site ... p36-38.pdf


Sat Feb 18, 2023 7:04 pm WWW
User avatar

Joined: Sun Dec 19, 2021 1:36 pm
Posts: 75
Location: Michigan USA
drogon wrote:
If the system is interactive why not increment a counter while it's waiting for a keypress? Then the first call to the random function can use this counter as the initial seed and off you go.

Or a simpler hardware solution with no interactive input - a reverse biased diode will generate noise - amplify/clip/schmitt the signal and fed it into a 1-bit input. Make N samples of this signal to use as the seed?

-Gordon


I agree with both your points! In the circuit I posted the transistor is doing exactly what you describe, it is a reverse biased PN junction generating noise.


Sat Feb 18, 2023 11:09 pm WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
One of my plans is to build the following on perfboard, the partial circuit is copied from this article

https://makezine.com/projects/really-really-random-number-generator/

Once again a reverse biased PN junction is generating noise.

The out signal(s) would go into an FPGA pin. My thought is to build four copies of the circuit to get four bits generated at once, then set it up as a PMOD.
As a PMOD it would need a boost regulator to go from 3.3V to 5V and 12V.

Attachment:
hrng.png


You do not have the required permissions to view the files attached to this post.

_________________
Robert Finch http://www.finitron.ca


Sun Feb 19, 2023 1:20 am WWW

Joined: Mon Oct 07, 2019 2:41 am
Posts: 599
The original random noise generator?
https://hackaday.com/2015/08/16/hackada ... generator/


Mon Feb 20, 2023 1:41 am

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1786
Nice pair of articles on lwn:
Random numbers for embedded devices
LCE: Don't play dice with random numbers

New random numbers every minute from NIST, signed and chained, here. (via hackaday, via Ben's link)

The concept of mixing inputs into an entropy pool is very important: if you have several random sources, you can mix in some which are untrusted and some which are unbalanced, and it won't be a problem. So user input, disk response times, network activity, noise diodes, webcam pointed at lava lamps, uninitialised RAM, it's all useful.


Mon Feb 20, 2023 8:07 am

Joined: Mon Oct 07, 2019 2:41 am
Posts: 599
https://web.archive.org/web/20160501000 ... index.html
Old tech can be interesting if not lost.
https://web.archive.org/web/20160501000 ... m/products
Thank you. Wayback machine.


Tue Feb 21, 2023 7:20 am

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1786
Thanks Ben - looks like Tom Jennings' Atomic Number Generator has a new home on the web:
https://www.sr-ix.com/Objects/ANG/


Tue Feb 21, 2023 7:42 am
 [ 12 posts ] 

Who is online

Users browsing this forum: CCBot and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software