MATLAB code for using a Markov chain for evaluating an entropy noise source

Question

I am trying to integrate page 68 of this PDF into MATLAB code:

http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90b.pdf#page=68

I have included these instructions as an image here:

As I know nothing or very little of Markov chains, I am first confused by the instructions signifying what o_i is. "o_i denotes the number of times that state i has occurred in the sample". What is state i?

Step 4 is probably the most difficult of them all. I have no idea how to calculate S or anything like that.

Here is my beginning code:

function minEntropy = markovTest(points, bitSize)
if bitSize > 6
    err('Maximum of 6 bits are allowed for Markov test, re-map inputs as in 7.2')
end
k = 128;
alpha = 0.05;
alpha = min(alpha^(bitSize^2),alpha^k);
% Estimate the initial state probability distribution:
e = sqrt(log(1./(1-alpha))./(2*N));
N = length(points);
oi == ?
Pi = min(1, oi./N + e);
??? Hat to do next?
end

Answer 1

The NIST has integrated all of these tests into a nice Python library, which can be found on GitHub. If for some reason the library is gone, you can try contacting Tim Hall at the NIST, who also has ported this library to C code, if that should suit you better. [email protected]