Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithms and Sources of entropy for PRNG and TRNG?

  1. Dec 12, 2012 #1
    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
     
  2. jcsd
  3. Dec 12, 2012 #2

    rbj

    User Avatar

    need to define some acronyms. i know a bit about generating random numbers but dunno what the "P" or the "T" is.
     
  4. Dec 13, 2012 #3
    ok here goes... PRNG - pseudo random number generator. (algorithms)
    TRNG - true random number generator. (hardware generator)
     
  5. Dec 13, 2012 #4
  6. Dec 13, 2012 #5

    rbj

    User Avatar

    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.
     
  7. Dec 13, 2012 #6

    rbj

    User Avatar

    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.
     
  8. Dec 13, 2012 #7
    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.
     
  9. Dec 14, 2012 #8
    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.
     
  10. Dec 14, 2012 #9
    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).
     
  11. Dec 15, 2012 #10

    rbj

    User Avatar

    guy, i think that Enthalpy is completely correct.
     
  12. Dec 15, 2012 #11

    nsaspook

    User Avatar
    Science Advisor

    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 [Broken]
    http://users.wpi.edu/~martin/MQP/edwardsetal.pdf
     
    Last edited by a moderator: May 6, 2017
  13. Dec 15, 2012 #12
    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.
     
  14. Dec 17, 2012 #13

    nsaspook

    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Algorithms and Sources of entropy for PRNG and TRNG?
  1. MUSIC Algorithm (Replies: 1)

  2. Current source (Replies: 3)

Loading...