Catch up on stories from the past week (and beyond) at the Slashdot story archive

 



Forgot your password?
typodupeerror
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 Internet speed test! ×
Education Security Privacy Programming Software News Science

Theoretical Breakthrough Made In Random Number Generation (threatpost.com) 152

msm1267 quotes a report from Threatpost: Two University of Texas academics have made what some experts believe is a breakthrough in random number generation that could have longstanding implications for cryptography and computer security. David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, published a paper in March that will be presented in June at the Symposium on Theory of Computing. The paper describes how the academics devised a method for the generation of high quality random numbers. The work is theoretical, but Zuckerman said down the road it could lead to a number of practical advances in cryptography, scientific polling, and the study of other complex environments such as the climate. "We show that if you have two low-quality random sources -- lower quality sources are much easier to come by -- two sources that are independent and have no correlations between them, you can combine them in a way to produce a high-quality random number," Zuckerman said. "People have been trying to do this for quite some time. Previous methods required the low-quality sources to be not that low, but more moderately high quality. We improved it dramatically." The technical details are described in the academics' paper "Explicit Two-Source Extractors and Resilient Functions."
This discussion has been archived. No new comments can be posted.

Theoretical Breakthrough Made In Random Number Generation

Comments Filter:
  • by Anonymous Coward

    And the secret algorithm is... multiplication!

    Note: IANAM

    • by Anonymous Coward

      Multiplication and other arithmetic operators are indeed secret as far as the average American high schooler is concerned.

      • Re: Multiplication (Score:5, Informative)

        by Ol Olsoc ( 1175323 ) on Tuesday May 17, 2016 @09:27PM (#52131671)

        Multiplication and other arithmetic operators are indeed secret as far as the average American high schooler is concerned.

        Well, a Mathematician was interrogated because some woman on a plane saw him........

        doing math, which in today's America is a sign of trrsm.

        • by sjames ( 1099 )

          Yes, a woman from Wales.

          • Yes, a woman from Wales.

            As much as people like to point out that this woman was form Wales, was she in Wales at the time she accused the Mathematician of being a terrorist?

            We are so fearful in America, ready to panic over stupid shit like alarm clock innards and math symbols, and it is engouraged to be in that state of fear, as witnessed by commercials I here very day commanding that citizens call authorities if they see or hear anything (their emphasis, not mine) out of place.

            They were in America, in Philadelphia - and she

            • by sjames ( 1099 )

              So did she get her math education while she was here or do you suppose she got it in Wales?

              • So did she get her math education while she was here or do you suppose she got it in Wales?

                She got the reaction to her stupidity in Philadelphia. Which happens to be in the US.

                • by sjames ( 1099 )

                  Absolutely. We are now a fear based society. The Chicken Little of the world.

    • And the secret algorithm is... multiplication!

      No, then zero will occur more often than other numbers.

      I suppose xor ought to work if the two sources are totally unrelated. But then you have to be sure that they really are completely unrelated. For example, feed it the same source twice and all you get is zero.

      So I imagine they must have done something a lot more clever than that.

  • by jlechem ( 613317 )
    FP Also I tried to read the brief and as a CS major it was above my head. Must be a math thing.
    • by Anonymous Coward

      It could just be that it's high quality randomness.

    • I read it too, and I fail to see the breakthrough. There are plenty of pseudo random number generators, such as the Mersenne Twister [wikipedia.org], with very long periods, so just occassionally XORing even a poor quality random number into the feedback loop, is enough to make it completely unpredictable.

      • by Anonymous Coward

        Pseudo

      • That's more or less the basis for CryptMT...

      • Re:FP (Score:5, Informative)

        by macklin01 ( 760841 ) on Tuesday May 17, 2016 @06:50PM (#52130831) Homepage

        I read it too, and I fail to see the breakthrough. There are plenty of pseudo random number generators, such as the Mersenne Twister, with very long periods, so just occassionally XORing even a poor quality random number into the feedback loop, is enough to make it completely unpredictable.

        Mersenne Twister is pretty much the standard for simulating a uniform distribution in a lot of scientific computing. These depend not only upon unpredictability (useful for avoiding biases, and clearly important in the security realm), but also upon properties of the uniform distribution.

        But when we test it out, we find it's still not as great as we'd like: look at a histogram of outputs, and you'll see that until you get really large numbers of function calls, the histogram isn't particularly uniform. (In particular, numbers near the bottom and top of the range don't get called quite as often.) This means that simulation properties that rely upon uniform distributions over both long and short time periods may be thrown off, and short- and mid-time simulation results may well stem from the MT rather than from the mathematical model. Moreover, low-probability events may have artificially smaller probabilities in the simulations (because of the non-uniformity of the distributions near the bottom and top ends of the range).

        Over very short numbers of function calls (a few hundred to a few thousand), the outputs can even tend to cluster in a small neighborhood. So suppose that you are simulating a tissue with many cells, and calling MT as your uniform distribution to decide if the cells divide or stay dormant (each with independent probability p, so each cell divides if PRNG/max(PRNG) < p). The math says that for a uniform distribution, you don't need to worry about what order you evaluate your decision across all the cells. But if the PRNG outputs cluster over several sequential calls, then a neighborhood of cells may simultaneously divide if they are all evaluated close to one another sequentially. In analyzing the spatial behavior of such a simulation, you may draw incorrect conclusions in smaller spatial structures that, again, derive from non-uniformity of the PRNG, rather than problems with predictability. (And then you may accept/reject a particular hypothesis or mathematical model pre-maturely.)

        So, there's definitely more to it than just unpredictability, depending upon where the code is being used.

        • If you are doing biological simulations, I'm pretty sure you'd want to use an actual random source, rather than psuedo-random. You even state yourself, the result isn't what you would want. Leave PRNG to things like computer game AI and song playlist randomization.
          • by Fwipp ( 1473271 )

            Well sure, if you're fine with your simulation being rate-limited by /dev/random.

            Affordable hardware entropy sources output on the order of hundreds of kbps, which is, you know, abysmally slow for the amount of calls that are required for meaningful simulation. Without hardware entropy sources (remember, many of these are running on grad students' laptops), using 'true' randomness drops from "embarrassingly" to "unusably" slow.

            • Is there a reason why using the hardware entropy source to change the state of a quality PRNG those few hundred thousand times per second wouldn't work?
              • Is there a reason why using the hardware entropy source to change the state of a quality PRNG those few hundred thousand times per second wouldn't work?

                That is a normal construct. It's even codified in SP800-90A with the additional input option on the Reseed() function.

              • by Anonymous Coward

                > Is there a reason why using the hardware entropy source to change the state of a quality PRNG those few hundred thousand times per second wouldn't work?

                That's actually how /dev/urandom works: http://www.2uo.de/myths-about-urandom/ ...and yes, it's fine.

              • by Fwipp ( 1473271 )

                You mean other than short-range non-uniformity in the Mersenne Twister (perhaps the most commonly used quality PRNG), which this thread of comments is about?

          • Re:FP (Score:5, Interesting)

            by JanneM ( 7445 ) on Tuesday May 17, 2016 @08:05PM (#52131219) Homepage

            For large-scale simulations you need them to be pseudo-random, as in repeatable. If you are running a parallel simulation across hundreds or thousands of nodes, you can't send random data to all the nodes. You'd spend all your time sending that, not getting anywhere with your simulation.

            Instead, what you do is that each node runs its own random generator, but seeded with the same state. That way they all have the same random source, with no need to flood the interconnect with (literally) random data.

            Another reason is repeatability of course. You may often want to run the exact same simulation many times when you're developing and debugging your code.

          • by Bengie ( 1121981 )
            The Universe is just varying degrees of pseudo-random. With the Avalanche effect, even small amounts of "entropy" mixed into psuedo-random. The biggest issues with making strong random numbers isn't creating high quality 50/50 distribution of 1s and 0s, but making sure the RNG isn't susceptible to some form of malicious "entropy" from a compromised entropy source or leaking data about the state of the RNG.
        • Re:FP (Score:5, Informative)

          by TechyImmigrant ( 175943 ) on Wednesday May 18, 2016 @06:53AM (#52133437) Homepage Journal

          Mersenne Twister is pretty much the standard for simulating a uniform distribution in a lot of scientific computing.

          No. Permuted Congruential Generators are. There's no contest. MT is slower and doesn't pass TestU01.
          MT is used for reasons of inertia.

          • Re:FP (Score:5, Informative)

            by serviscope_minor ( 664417 ) on Wednesday May 18, 2016 @08:42AM (#52133935) Journal

            Mersenne Twister is pretty much the standard for simulating a uniform distribution in a lot of scientific computing

            kind of is, for the reason as you say of:

            MT is used for reasons of inertia.

            MT19937 is pretty good. Much better than the LCGs that were popular before it. Those have some really serious pitfalls and you can hit them awfully easily. MT19937 is generally pretty good, though not perfect. It has far fewer pitfalls than LCGs and you're actually pretty unlikely to hit them (it doesn't fail TestU01, it passes almost all of the tests and fails a few). It's also fast enough that you have to try quite hard to make the RNG the limiting factor (it is possible though).

            You can go wrong with MT19937, but it's hard to. That makes it pretty decent. Prior to C++11, xorshift used to be my go-to generator that didn't suck because it was a 5 line paste. These days, it's MT19937 simply because it's in the standard library and good enough for almost all tasks.

      • Sure, lots of people can do that, but can they do the math behind it well enough to get a paper out of it?

      • Re:FP (Score:5, Interesting)

        by TechyImmigrant ( 175943 ) on Wednesday May 18, 2016 @06:51AM (#52133435) Homepage Journal

        I read it too, and I fail to see the breakthrough. There are plenty of pseudo random number generators, such as the Mersenne Twister [wikipedia.org], with very long periods, so just occassionally XORing even a poor quality random number into the feedback loop, is enough to make it completely unpredictable.

        This proof is about proving mathematically that an algorithm is a good entropy extractor. MT has no such proof. It doesn't even meet the definition of an entropy extractor and isn't cryptographically secure. For algorithms in the same class, PCGs [pcg-random.org] are currently top of the pile, but they still aren't secure.

        They claim to have an algorithm for a secure two input extractor (where the two inputs are independent) which can extract from low entropy source. 'low' means less than 0.5. Single input extractors suffer from an absence of proofs that they can extract from sources with min-entropy less than 0.5.

        I fail to see it as new because the Barack, Impagliazzo, Wigdersen extractor from 2007 did the same trick using three sources (A*B)+C where values from A,B and C are treated as elements in a GF(2^P) field and can operate with low min-entropy inputs. This is so cheap that the extractor is smaller than the smallest entropy sources. Intel published this paper using the BIW extractor for what is probably the most efficient (bits/s/unit_area and bits/s/W) to date. [deadhat.com]

        I fail to see that it is useful, because real world sources have min-entropy much higher that 0.5. Low entropy inputs is a problem mathematicians think we have, but we don't. We engineer these things to be in the 0.9..0.999 range.

        On top of it, these two papers are as clear as mud. I tried and failed to identify an explicit construct and ether I'm too dumb to find it or they hid it well. I did find an implication that the first result uses a depth-4 monotone circuit that takes long bit strings and compresses them to 1 bit and the second paper extends this with a matrix multiply. That sounds both inefficient and more expensive than an additional small source needed to use the cheaper 3-input BIW extractor.

        My take is that there have been two breakthroughs in extractor theory in recent years. Dodis's papers on randomness classes and extraction with cbc-mac and hmac for single input extractors and the BIW paper for three input extractors. Both useful in real world RNGs.

        I may be wrong though. I've asked a real mathematician to decode the claims.

      • The contribution here is to provide a solid theoretical footing for your "just occassionally XORing", which if done informally as you propose is more than likely to lead to surprising statistical defects. Not that I follow the proofs either, but I understand the value of the work.

    • by Livius ( 318358 )

      All I got out of it was a function of independent random variables, and that level of math was in my very first stats course.

      I'll give them the benefit of the doubt and assume I missed something.

    • It could be both. Remember that computer science and mathematics very often overlap with each other, especially with cryptography. If you couldn't understand it then maybe you had the wrong focus in computer science. I knew a lot of CS grad students and profs who were essentially mathematicians who couldn't program but who focused on a theoretical computer science area.

      • Remember that computer science and mathematics very often overlap with each other

        Yes, especially if you realize you can put all the computer science on top of the lambda calculus, which is mathematics. Then it turns out that computer science is a proper subset of mathematics. Which indeed is a specific form of overlap (although the common usage of the word "overlap" could create a mistaken impression that there is a part of computer science which isn't in mathematics).

  • Wow! David Zuckerman [wikipedia.org], the writer/producer of Family Guy is also a noted Computer Science professor...Man, a lot of the jokes make more sense now!
    • by Anonymous Coward

      This is a failure to make a good a random FullNameGenerator from two less good generators (FirstNameGenerator, SurnameGenerator). David is a common name. Zuckerman is a common name. David Zuckerman is not uncommon enough.

  • Why not just use analog hardware to do it; i.e. sampling of white noise?
    • Re:Why not hardware (Score:5, Informative)

      by Anonymous Coward on Tuesday May 17, 2016 @06:50PM (#52130829)

      Hardware random number generation based on stochastic random processes (e.g. Johnson noise across a resistor) is a real thing.

      There is the minor difficulty that it requires that you actually add the hardware to do the sampling - sure HP didn't mind dropping a /dev/hwrng into my new $3500 laptop, but most people don't buy top-of-the-line hardware, and nobody likes hardware dongles.

      The REAL difficulty is that you're now subject to all the usual threats to analog processes. We like to just *assume* that all the noise sources in our analog devices are uncorrelated because that makes our analyses tractable, but that's not the case. In other words, you want to believe that the 20th bit of the noise-sampling ADC is independently flapping in the breeze and providing 1/0 randomly and in equal measure, but that doesn't make it so. This is especially the case inside a box packed with high-speed digital circuitry, which will be coupling nonrandom, nonwhite signals into anything it can. Worst of all, these signals will tend to be correlated with the ADC: Its conversion clock, like almost every other clock signal in a modern computer, is probably either phase-locked to or derived directly from the same crystal in order to provide reliable, synchronous timing between circuits.

      • by Bengie ( 1121981 )
        Intel has a high quality HW-RNG, but no one trusts it. That's the bigger issue with anything hardware, it can't be verified, only software can.
      • A problem with the hardware RNGs is that they very often don't just give you a random number on demand. They often require you to have a delay between starting and ending the operation for example, and the longer you wait the more entropy is generated. Not bad drawbacks for the occasional crypto input, but could be a problem for running simulations.

      • by Agripa ( 139780 )

        There are things which can be done to improve the situation. Build two (or three) symmetrical noise sources and subtract one from the other to remove common mode influences; three sources allow for redundancy and cross checking. For a simple design, a complex ADC is not required; use a comparator followed by a flip-flop or latch. Use the average DC level of the noise to set the comparator's trip point. Or use an ADC instead of the comparator so that the noise source can also be fully characterized in it

        • by mlts ( 1038732 )

          I wonder about using something like AES or a standard encryption algorithm on the stream of numbers coming from the RNG/PRNG, with the encryption key coming from a different RNG pool. This might help with the unpredictability aspect.

    • by GuB-42 ( 2483988 )

      1- Maybe you prefer a repeatable pseudo-random sequence to real random data. Like for testing, or to make stream ciphers.
      2- Hardware RNGs are often biased, they may for example output a "0" 70% of the time and a "1" 30% of the time. The output needs processing to remove the bias. Combining a biased but truly random generator with an unbiased PRNG can be an effective way to archive this.

    • Why not just use analog hardware to do it; i.e. sampling of white noise?

      Did you read the papers? That's what it is about.

  • by Anonymous Coward

    to be sure: http://dilbert.com/strip/2001-10-25

  • by wierd_w ( 1375923 ) on Tuesday May 17, 2016 @06:57PM (#52130855)

    I see this very salient question raised earlier-- why not use a dedicated white noise generator for random picks?

    Most places you are going to need a good random integer are going to be in places where a dedicated diode based noise source is going to add cost to the system, and thus not be ideal. Things like an ATM machine, a cellphone, a laptop, whatever.

    The cost is not in the actual component cost (a diode costs what, a few cents?) but in a standardized interface to that noise source.

    Conversely, there are several very low quality sample sources that have no physical correlation with each other on such systems that can be leveraged, which have well defined methods of access, which add zero additional cost to the system.

    Say for instance, microphone input + radio noise floor on a cellphone. Perhaps even data from the front and rear cameras as well. (EG, take Foo miliseconds of audio from the microphone, get an snr statistic from the radio, and have a pseudorandom shuffle done on data from the front and rear cameras. These sources are, independently, horrible sources of random. They are however, independent of each other. If this guy has found a really good way of getting good random from bad sources, then a quality random sequence can be generated quickly and cheaply this way. This would allow the device to rapidly produce quality encrypted connections without a heavy computational load, vastly improving the security of the communication, and do so without any additional OS level support, or extra hardware.)

    When deriving a key pair for the likes of GPG, it can take several minutes of "random" activity on the computer to generate a sufficiently high quality entropy pool for key generation. That is far too slow to have really good, rapidly changing encryption on a high security connection. Something like this could let you generate demonstrably random AES 256 keys rapidly on the fly, and have a communication channel not even the NSA can crack.

    The trick here is for them to reliably demonstrate that the rapidly produced sequences are indeed quality random sequences with no decernable pattern.

    • All those white noise sources are affected by radio signals from the outside and EMR from digital processing circuits on the same board.
      • This will be true of all digital sources, unless you want to export part of the key synthesis to an external device that different local em biases.

        If you do that, then you have to trust that source implicitly not to have a subtly poisoned distribution (See the NSA's backdoored random source that caused such controversy in the past few years.)

        Perfection is likely not attainable, even with hardware RNGs. This lets you get reasonably good samplings from wholly local, but less robust sources. To effectively exp

        • The point was people are talking about PRNGs (guaranteed known distribution, can mimic high-quality random data, can provide cryptographic security e.g. in a key scheduling algorithm) or noise-based RNGs (unknown distribution, often provide poor-quality random data, can be influenced by other operations inside the machine). Noise-based RNGs aren't magically high-quality, flat-distribution, unpredictable number sources; they can be the worst random number sources available.

          To effectively exploit the unifying em bias of the device, you would need to know very specific features of the device, and how ambient signals interact with it to shape the distributions, THEN introduce very strong EM signals to the system to get the predictable patterns needed to assault the resulting encryption based on those distributions.

          You'd only have to know about t

          • by Bengie ( 1121981 )
            Minor context addition to AES down to 126bits of entropy. Ballparking numbers. Practical attacks only remove about 2-4 bits, reducing 256bits to 252bits and 128bits to 126bits. There are some non-practical attacks that require sampling petabytes of encrypted data from the same key where you know what the underlying unencrpyted data is. Then you can theoretically reduce AES256 down to something around 100bits, which is still nearly impossible for our solar system regardless of the hypothetical far future tec
            • It's enough for cryptographers to tell you to worry about the entropy source you're using and not magically assume that we can break 96 bits of encryption now but your 128-bit encryption key is fine because we're like 90 billion years off cracking that and maybe 8-12 years off developing newer technology to crack it reasonably fast.
              • by Bengie ( 1121981 )
                Breaking perfect 128bit encryption is not feasible limited to our solar system. It would require having a perfectly efficient computer and converting several Earth masses into pure energy to power that computer. 256bit is right out, can't be done in our Universe with current understanding of basic physics. The only way is to find a flaw in the encryption. AES does have some flaws, but they all require having partial control of the entropy source for generating the keys or having access to both unencrypted a
                • A flaw in the entropy will give you a 60-bit key if you can guess that much. That's how researchers recover keys from AES just by running on the same machine as an unprivileged user.
      • by Bengie ( 1121981 )
        In theory, 256bits of entropy is enough to be impossible to break. Pretty much a lifetime of "random" numbers can be created from 256bits, it doesn't take much. The problem is our algorithms and systems are not perfect and data gets leaked for various reasons. As long as you can seed the system with something like 256bits of strong entropy, you can slowly collect additional entropy over time, even if very slowly, and just keep mixing it in. All that matters is you acquire entropy some factor faster than you
        • The problem is any set of random data generated *right* *now* has a pattern. If you know something about that pattern, you can limit the amount of entropy someone could possibly derive from a random number source.
          • by Bengie ( 1121981 )
            That's why you whiten the output, that way you can't predict the pattern without knowing all of the entropy. Whitening gets rid of the patterns. Think crypto strong hashes. Difficult to reverse. Very good whiteners in that sense.
    • by AmiMoJo ( 196126 )

      The problem with hardware RNGs is that it can be difficult to detect errors and difficult to trust them. If some part of the system fails and introduces bias the only practical way of detecting that is to run expensive randomness tests on the output.

      Intel does include an RNG in many of its CPUs, but how far can we trust it? It seems like the NSA has had its claws in Intel for a while, extent unknown. The RNG is an obvious target for them, along with the AES instructions found in i5 and i7 series CPUs.

      In com

      • by Bengie ( 1121981 )
        What we need are hardware RNG sources that provably do not have any ability to read state from the system, only input into the system.
  • "two sources that are independent and have no correlations between them"

    I TOLD you mot to look. Now thanks to the observer effect,.there IS something they both have in common! Co-relationships are now inevitable unless we can find a recipient that has nothing in common with you - anyone got a spare alien around to read the message?

  • The importance of random numbers in Crypto is that encryption keys must be prime for most if not all of the encryption algorithms to work. It is very hard to generate large prime numbers (e.g. 4000 bits) using an exact methods but it is somewhat easy to calculate the probability that a large number is prime. So what we can do is generate a highly probable prime number by simply generating random numbers and checking to see if they are probably prime. If the random numbers you use to generate keys in this wa
    • by slew ( 2918 )

      The importance of random numbers in Crypto is that many symmetric encryption protocols rely on efficiently generating random numbers (e.g., nonces, symmetric keys).

      The quality of the random numbers you use to generate prime keys for RSA are of course important too, but generally generating primes isn't done as frequently (because testing them is relatively slow) so efficiently combining two low-entropy sources isn't as critical because you can combine sources of low-entropy and achieve high quality random n

      • by gweihir ( 88907 )

        Nonces do not need to be random or unpredictable. A counter produces perfectly acceptable nonces, see, for example, the counter-mode for block ciphers. The defining characteristic of a nonce is that it gets used only once with respect to a given larger context.

    • by gweihir ( 88907 )

      This is not it. In crypto, you need "secrets" that an attacker cannot easily guess. These need to be "unpredictable" for the attacker, they do not need to be "random" or even "unpredictable" for the defender. (They can then, for example, be fed into a prime-number generator, but there are numerous other uses.) For simplicity, "unpredictable" is usually called "random", but that is not strictly true. Most "random" numbers for crypto are generated using CPRNGs (Cryptographic-PSEUDO-Random-Number-Generators).

  • by _Shorty-dammit ( 555739 ) on Tuesday May 17, 2016 @07:16PM (#52130963)

    As long as Apple gets it and shuffle stops jumping back to the same area many, many times a day then I'll be happy. That shit gets on my nerves, yo!

    • You don't want a true random number generator then.

      Take 23 random people, and there will be a better than 50% chance that two of them will have the same birthday.

      Apple actually had to make its "random" shuffle less random when people complained about hearing the same songs too often. A bit like picking 23 people but making sure they don't have a common birthday. The more random you make it, the more people will complain about it not being random enough.

      Maybe your shuffle still has the old, truly random shuf

  • I think their idea is to skip the bits in 1st source based on the bits in the 2nd source. So, on average, 2n bits from the 1st source and 2n bits from the 2nd source would produce n random bits.
    • Having thought about it for a few mins, that can't be what they are saying. It would not produce random sequence from 2 sequences with cycles m and n. It would have a cycle of the length, at most, m*n. I guess that's why they talk about a monotone increasing sequence. So maybe if p_i digits from 1st seq are picked only if i in the 2nd seq is a 1 (and skipped if i in the 2nd seq is a 0)? If p_i is the i'th prime number, this would knock out any cycles (because it randomly picks or drops bit spans whic
  • by slew ( 2918 ) on Tuesday May 17, 2016 @08:16PM (#52131291)

    One way to think about this is to understand how to get a unbiased number out of a biased coin? A simplistic Von-Neumann extractor.
    Basically, flip the coin twice, discard HH/TT and assign HT and TH to 0 and one. This throws away alot of flips (depending on how biased the coin is) but gets you what you want if the flips are independent.

    Now imagine instead of a 2x2 matrix, a really large matrix that takes in a sequence of flips that depends on the minimum entropy of the source so that you avoid throwing away flips. How do you fill the elements of this matrix?

    You can watch here [youtube.com] and learn something...

    • If you know which way the coin is biased, you can predict existence (and frequency of occurring) of spans of 0's or 1's just as you would if the coin was unbiased.
      • Yes but those get discarded. That's the whole point. You only take the pairs of HT or TH which cannot be predicted. The more biased a coin is, the more flips you throw away and the slower you acquire entropy. But what you acquire is unbiased.
  • I.e. in situations where you are entropy-starved (so not on regular computers) and getting the, say, 256 bits of entropy to seed a CPRNG is hard to come by. This only applies to really small embedded systems that have no A/D converters or the like. (With an AD converter, just sample some noisy source or even an open input and you get something like > 0.1 bit entropy per sample. Needs careful design though.) Whether such a very small embedded system can the use the math needed here is a different question

  • Setec Astronomy
  • We used to use Yarrow for this purpose, but it suffered from the problem that you needed to estimate the entropy of your sources. Fortuna was introduced to address this, and allows you to combine entropy sources without estimating the amount of entropy that they contain. What does this add beyond that?
  • "if you have two low-quality random sources...you can combine them in a way to produce a high-quality random [result]

    So if you combine a Trump speech with a Palin speech, you get random Shakespeare?

Prototype designs always work. -- Don Vonada

Working...