Algorithms and Sources of entropy for PRNG and TRNG?

[dexterdev]

Hi PF,
I would like to implement different random number generators using AVR microcontroller (both PRNG and TRNG). So I would like to get suggestions about different sources of entropy for TRNG and algorithms for PRNG. Also wanted to test the randomness.

And What is chaos theory? Is it applicable for random number generation? Can I implement a chaos circuit for random number generator?

TIA

-Devanand T

 

[rbj]

need to define some acronyms. i know a bit about generating random numbers but don't know what the "P" or the "T" is.

 

[dexterdev]

ok here goes... PRNG - pseudo random number generator. (algorithms)
TRNG - true random number generator. (hardware generator)

 

[justsomeguy]

You can build something with known jitter/instability and read from that. Example: http://electronics.stackexchange.com/questions/18379/entropy-source-on-microchip-pic24f

 

[rbj]

ok here goes... PRNG - pseudo random number generator. (algorithms)
TRNG - true random number generator. (hardware generator)

so would a hardware generator using the same algorithm as a PRNG be a true RNG? if so, i fail to see any salient difference.

or is a TRNG an A/D converter that samples the noise from a noisy diode or resistor or some other noisy analog part? that might be fully unpredictable, in contrast to an algorithm.

 

[rbj]

You can build something with known jitter/instability and read from that. Example: http://electronics.stackexchange.com/questions/18379/entropy-source-on-microchip-pic24f

okay, so i looked at that, and it's essentially a noisy analog circuit that is sampled with a 1-bit A/D converter (that's what the comparator is).

okay, if you use that, and if the biasing scheme works as planned, then you should have some random bits coming out of that. there isn't a clock in the circuit, so i do not know how fast the bits might be toggling back and forth.

i can't say that they bits would be good and white because of that capacitor makes for a high-pass filter (a differentiator). so, if i understand it right, whatever is the value of the previous bit, the current bit will more likely be the complement than the same value. that's what high-pass noise is. if it were white, then the likelihood of the current bit being "1" is 50% no matter what the value of the previous bit was.

 

[justsomeguy]

so would a hardware generator using the same algorithm as a PRNG be a true RNG? if so, i fail to see any salient difference.

Hardware RNGs use true sources of randomness, like the LSB of a microphone input, phase jitter between out of sync clocks, background radiation, etc.

PRNGs are simply algorithms that eventually repeat. If you know the seed value, then you know all the random numbers it will generate when called, and in what order.

The difference between a good and bad PRNG is life and death to encryption, since the most secure encryption (a one time pad) depends entirely on the randomness of the keystream.

 

[Enthalpy]

Physical random generators tend to be very bad. They have bias like 1% or 0.1% which makes them totally unusable as is in cryptography, which wants 10^-9 to the very least.

So the next step is to hash by software the physical signal, and then you can begin to wonder if the physical source is really that useful.

Practical crypto programs use physical randomness only as seed for software random generators. Good choice.

 

[justsomeguy]

Physical random generators tend to be very bad. They have bias like 1% or 0.1% which makes them totally unusable as is in cryptography, which wants 10^-9 to the very least.

So the next step is to hash by software the physical signal, and then you can begin to wonder if the physical source is really that useful.

Practical crypto programs use physical randomness only as seed for software random generators. Good choice.

This is not quite correct. The main failing of hardware RNGs is not bias or anything to do with their randomness -- they are, when used correctly, perfectly random. The problem is they are generally just too slow. You need to wait for entropy to build up or you get a stream of identical or predictably oscillating values. PRNGs can go as fast as you want.

However, dedicated hardware RNGs are both fast and random. Their downside is simply that they are expensive (unless you DIY).

 

[rbj]

guy, i think that Enthalpy is completely correct.

 

[nsaspook]

Hi PF,
I would like to implement different random number generators using AVR microcontroller (both PRNG and TRNG). So I would like to get suggestions about different sources of entropy for TRNG and algorithms for PRNG. Also wanted to test the randomness.

A possible source of hardware randomness (a random seed for a good PRNG) in a microcontroller is the powerup bit state of the SRAM memory. What I've done in the past was to examine a large section of memory bits to see what bits usually power up as random instead of a steady 1 or 0. I would then mask out the fixed bits using a hamming code fuzzy extractor and then use a CRC of the unstuck random bits to generated a seed for a PRNG.

This describes a similar process:
https://www2.lirmm.fr/lirmm/interne/BIBLI/CDROM/MIC/2012/DATE_2012/PAPERS/2012/DATE12/PDFFILES/11.4_1.pdf
http://users.wpi.edu/~martin/MQP/edwardsetal.pdf

 

[0xDEADBEEF]

This one could be quite cool: http://warmcat.com/_wp/whirlygig-rng/ It passes the dieharder suite so there is definitely no bias and it has high quality randomness, but it is not clear to me if it is truly impossible to find a statistical model to kill it.

 

[nsaspook]

This one could be quite cool: http://warmcat.com/_wp/whirlygig-rng/ It passes the dieharder suite so there is definitely no bias and it has high quality randomness, but it is not clear to me if it is truly impossible to find a statistical model to kill it.

Ring oscillators can also be used to make PUFs for cryptographic key generation.

http://people.csail.mit.edu/devadas/pubs/puf-dac07.pdf