Hacker News Reader

Comment by amenghra | Hacker News Reader

Flip a penny twice, if you get heads followed by tails, write down 0. If you get tails, followed by heads, write down 1. Otherwise ignore the two flips. Rinse and repeat until you have enough bits.

The purpose of flipping twice is that it offsets any potential static bias (caused eg by weight difference) between the two sides.

View on HN

Common ways to generate entropy in a way that’s friendly to computers include: measuring noise from a zener (or other electronic component), delta between two or more oscillators, or timing between external events (eg keystrokes, packets, etc). These are all super cheap to manufacture (~$1). If you want to go high end, you can spent ~$1000 and get a generator based on some quantum property (photon spin or background radiation detector).

Computers will typically combine two or more sources of entropy. In newer tls version handshakes, the entropy from both, the server and client comes into play. So there’s ways to build defense in depth.

Truerng claims this on 100MB of generated data:

Entropy = 7.999998 bits per byte.

If you can fit this quality on a usb, why didn’t motherboards contain a circuit like that?

Maybe they do on server boards?

That's what RDRAND is - well, it's not the same physical mechanism as TrueRNG, but it is a fast hardware random number generator built into the CPU.

There is a fun generalization of the game. Assume the penny has (unknown) bias p. You want to output a new flip with bias some function f(p). So f(p)=1/2 is what you described, ie how to get a fair flip. For some functions it can be even easier, e.g. f(p)=p^2 - definitely only requires two flips.

How about:

f(p)=p^2/(p^2+(1-p)^2)

f(p)=2p(1-p)

f(p)=3p(1-p)

f(p)=sqrt(p)

The last two are tricky, I took them from a paper "functions arising from coin flipping" by Wastlund. (The quantum generalization is even more fun, but this text box is too small to contain it.)

Wasn’t there a paper that showed it is basically impossible to load a physical coin?

AKA von Neumann debiasing, or the von Neumann trick.

Reply on news.ycombinator.com