Python implementation of the Approximate Entropy cryptographic test for randomness
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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