Entropy extractor used in μRNG
Yesterday I mentioned I1/4RNG, a true random number generator (TRNG) that takes physical sources of randomness as input. These sources are independent but non-uniform. This post will present the entropy extractor I1/4RNG uses to take non-uniform bits as input and produce uniform bits as output.
We will present Python code for playing with the entropy extractor. (I1/4RNG is extremely efficient, but the Python code here is not; it's just for illustration.) The code will show how to use the pyfinite library to do arithmetic over a finite field.
Entropy extractorThe I1/4RNG generator starts with three bit streams-X, Y, and Z-each with at least 1/3 bit min-entropy per bit.
Min-entropy is Ri(C)nyi entropy with I = a. For a Bernoulli random variable, that takes on two values, one with probability p and the other with probability 1-p, the min-entropy is
-log2 max(p, 1-p).
So requiring min-entropy of at least 1/3 means the two probabilities are less than 2-1/3 = 0.7937.
Take eight bits (one byte) at a time from X, Y, and Z, and interpret each byte as an element of the finite field with 28 elements. Then compute
X*Y + Z
in this field. The resulting stream of bits will be independent and uniformly distributed, or very nearly so.
Python implementationWe will need the bernoulli class for generating our input bit streams, and the pyfinite for doing finite field arithmetic on the bits.
from scipy.stats import bernoulli from pyfinite import ffield
And we will need a couple bit manipulation functions.
def bits_to_num(a): "Convert an array of bits to an integer." x = 0 for i in range(len(a)): x += a[i]*2**i return x def bitCount(n): "Count how many bits are set to 1." count = 0 while(n): n &= n - 1 count += 1 return count
The following function generates random bytes using the entropy extractor. The input bit streams have p = 0.79, corresponding to min-entropy 0.34.
def generate_byte(): "Generate bytes using the entropy extractor." b = bernoulli(0.79) x = bits_to_num(b.rvs(8)) y = bits_to_num(b.rvs(8)) z = bits_to_num(b.rvs(8)) F = ffield.FField(8) return F.Add(F.Multiply(x, y), z)
Note that 79% of the bits produced by the Bernoulli generator will be 1's. But we can see that the output bytes are about half 1's and half 0's.
s = 0 N = 1000 for _ in range(N): s += bitCount( generate_byte() ) print( s/(8*N) )
This returned 0.50375 the first time I ran it and 0.49925 the second time.
For more details see the I1/4RNG paper.
Related posts