Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python implementation of the Approximate Entropy cryptographic test for randomness
def approximate_entropy(self, bin_data: str, pattern_length=10):
"""
Note that this description is taken from the NIST documentation [1]
[1] http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf
As with the Serial test of Section 2.11, the focus of this test is the frequency of all possible overlapping
m-bit patterns across the entire sequence. The purpose of the test is to compare the frequency of overlapping
blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence.
:param bin_data: a binary string
:param pattern_length: the length of the pattern (m)
:return: the P value
"""
n = len(bin_data)
# Add first m+1 bits to the end
# NOTE: documentation says m-1 bits but that doesnt make sense, or work.
bin_data += bin_data[:pattern_length + 1:]
# Get max length one patterns for m, m-1, m-2
max_pattern = ''
for i in range(pattern_length + 2):
max_pattern += '1'
# Keep track of each pattern's frequency (how often it appears)
vobs_one = numpy.zeros(int(max_pattern[0:pattern_length:], 2) + 1)
vobs_two = numpy.zeros(int(max_pattern[0:pattern_length + 1:], 2) + 1)
for i in range(n):
# Work out what pattern is observed
vobs_one[int(bin_data[i:i + pattern_length:], 2)] += 1
vobs_two[int(bin_data[i:i + pattern_length + 1:], 2)] += 1
# Calculate the test statistics and p values
vobs = [vobs_one, vobs_two]
sums = numpy.zeros(2)
for i in range(2):
for j in range(len(vobs[i])):
if vobs[i][j] > 0:
sums[i] += vobs[i][j] * math.log(vobs[i][j] / n)
sums /= n
ape = sums[0] - sums[1]
chi_squared = 2.0 * n * (math.log(2) - ape)
p_val = spc.gammaincc(pow(2, pattern_length-1), chi_squared/2.0)
return p_val
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment