Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python implementation of the Block Frequency cryptographic test for randomness
def block_frequency(self, bin_data: str, block_size=128):
"""
Note that this description is taken from the NIST documentation [1]
[1] http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf
The focus of this tests is the proportion of ones within M-bit blocks. The purpose of this tests is to determine
whether the frequency of ones in an M-bit block is approximately M/2, as would be expected under an assumption
of randomness. For block size M=1, this test degenerates to the monobit frequency test.
:param bin_data: a binary string
:return: the p-value from the test
:param block_size: the size of the blocks that the binary sequence is partitioned into
"""
# Work out the number of blocks, discard the remainder
num_blocks = math.floor(len(bin_data) / block_size)
block_start, block_end = 0, block_size
# Keep track of the proportion of ones per block
proportion_sum = 0.0
for i in range(num_blocks):
# Slice the binary string into a block
block_data = bin_data[block_start:block_end]
# Keep track of the number of ones
ones_count = 0
for char in block_data:
if char == '1':
ones_count += 1
pi = ones_count / block_size
proportion_sum += pow(pi - 0.5, 2.0)
# Update the slice locations
block_start += block_size
block_end += block_size
# Calculate the p-value
chi_squared = 4.0 * block_size * proportion_sum
p_val = spc.gammaincc(num_blocks / 2, chi_squared / 2)
return p_val
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment