Skip to content

Instantly share code, notes, and snippets.

@StuartGordonReid
Last active May 20, 2020 15:34
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save StuartGordonReid/a4b1bc69bb52bb9343fa to your computer and use it in GitHub Desktop.
Save StuartGordonReid/a4b1bc69bb52bb9343fa to your computer and use it in GitHub Desktop.
Python implementation of the Serial cryptographic test for randomness
def serial(self, bin_data, pattern_length=16, method="first"):
"""
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 test is the frequency of all possible overlapping m-bit patterns across the entire
sequence. The purpose of this test is to determine whether the number of occurrences of the 2m m-bit
overlapping patterns is approximately the same as would be expected for a random sequence. Random
sequences have uniformity; that is, every m-bit pattern has the same chance of appearing as every other
m-bit pattern. Note that for m = 1, the Serial test is equivalent to the Frequency test of Section 2.1.
: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
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 + 1):
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)
vobs_thr = numpy.zeros(int(max_pattern[0:pattern_length-2:], 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
vobs_thr[int(bin_data[i:i + pattern_length-2:], 2)] += 1
vobs = [vobs_one, vobs_two, vobs_thr]
sums = numpy.zeros(3)
for i in range(3):
for j in range(len(vobs[i])):
sums[i] += pow(vobs[i][j], 2)
sums[i] = (sums[i] * pow(2, pattern_length-i)/n) - n
# Calculate the test statistics and p values
del1 = sums[0] - sums[1]
del2 = sums[0] - 2.0 * sums[1] + sums[2]
p_val_one = spc.gammaincc(pow(2, pattern_length-1)/2, del1/2.0)
p_val_two = spc.gammaincc(pow(2, pattern_length-2)/2, del2/2.0)
# For checking the outputs
if method == "first":
return p_val_one
else:
# I am not sure if this is correct, but it makes sense to me.
return min(p_val_one, p_val_two)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment