Skip to content

Instantly share code, notes, and snippets.

@StuartGordonReid
Created September 13, 2015 13:13
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save StuartGordonReid/e2d036d9d90ac67f73c0 to your computer and use it in GitHub Desktop.
Save StuartGordonReid/e2d036d9d90ac67f73c0 to your computer and use it in GitHub Desktop.
Python implementation of the NIST random excursions variant cryptographic test for randomness
def random_excursions_variant(self, bin_data):
"""
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 total number of times that a particular state is visited (i.e., occurs) in a
cumulative sum random walk. The purpose of this test is to detect deviations from the expected number of visits
to various states in the random walk. This test is actually a series of eighteen tests (and conclusions), one
test and conclusion for each of the states: -9, -8, …, -1 and +1, +2, …, +9.
:param bin_data: a binary string
:return: the P-value
"""
int_data = numpy.zeros(len(bin_data))
for i in range(len(bin_data)):
int_data[i] = int(bin_data[i])
sum_int = (2 * int_data) - numpy.ones(len(int_data))
cumulative_sum = numpy.cumsum(sum_int)
li_data = []
for xs in sorted(set(cumulative_sum)):
if numpy.abs(xs) <= 9:
li_data.append([xs, len(numpy.where(cumulative_sum == xs)[0])])
j = self.get_frequency(li_data, 0) + 1
p_values = []
for xs in range(-9, 9 + 1):
if not xs == 0:
den = numpy.sqrt(2 * j * (4 * numpy.abs(xs) - 2))
p_values.append(spc.erfc(numpy.abs(self.get_frequency(li_data, xs) - j) / den))
return p_values
def get_frequency(self, list_data, trigger):
"""
This method is used by the random_excursions_variant method to get frequencies
"""
frequency = 0
for (x, y) in list_data:
if x == trigger:
frequency = y
return frequency
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment