Created
September 13, 2015 13:13
-
-
Save StuartGordonReid/e2d036d9d90ac67f73c0 to your computer and use it in GitHub Desktop.
Python implementation of the NIST random excursions variant 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 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