Skip to content

Instantly share code, notes, and snippets.

# StuartGordonReid/LinearComplexity.py Last active Feb 13, 2019

Python implementation of the linear complexity cryptographic test for randomness. This includes the Berklekamp Massey algorithm.
 def linear_complexity(self, bin_data, block_size=500): """ Note that this description is taken from the NIST documentation   http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf The focus of this test is the length of a linear feedback shift register (LFSR). The purpose of this test is to determine whether or not the sequence is complex enough to be considered random. Random sequences are characterized by longer LFSRs. An LFSR that is too short implies non-randomness. :param bin_data: a binary string :param block_size: the size of the blocks to divide bin_data into. Recommended block_size >= 500 :return: """ dof = 6 piks = [0.01047, 0.03125, 0.125, 0.5, 0.25, 0.0625, 0.020833] t2 = (block_size / 3.0 + 2.0 / 9) / 2 ** block_size mean = 0.5 * block_size + (1.0 / 36) * (9 + (-1) ** (block_size + 1)) - t2 num_blocks = int(len(bin_data) / block_size) if num_blocks > 1: block_end = block_size block_start = 0 blocks = [] for i in range(num_blocks): blocks.append(bin_data[block_start:block_end]) block_start += block_size block_end += block_size complexities = [] for block in blocks: complexities.append(self.berlekamp_massey_algorithm(block)) t = ([-1.0 * (((-1) ** block_size) * (chunk - mean) + 2.0 / 9) for chunk in complexities]) vg = numpy.histogram(t, bins=[-9999999999, -2.5, -1.5, -0.5, 0.5, 1.5, 2.5, 9999999999])[::-1] im = ([((vg[ii] - num_blocks * piks[ii]) ** 2) / (num_blocks * piks[ii]) for ii in range(7)]) chi_squared = 0.0 for i in range(len(piks)): chi_squared += im[i] p_val = spc.gammaincc(dof / 2.0, chi_squared / 2.0) return p_val else: return -1.0 def berlekamp_massey_algorithm(self, block_data): """ An implementation of the Berlekamp Massey Algorithm. Taken from Wikipedia   - https://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse. :param block_data: :return: """ n = len(block_data) c = numpy.zeros(n) b = numpy.zeros(n) c, b = 1, 1 l, m, i = 0, -1, 0 int_data = [int(el) for el in block_data] while i < n: v = int_data[(i - l):i] v = v[::-1] cc = c[1:l + 1] d = (int_data[i] + numpy.dot(v, cc)) % 2 if d == 1: temp = copy.copy(c) p = numpy.zeros(n) for j in range(0, l): if b[j] == 1: p[j + i - m] = 1 c = (c + p) % 2 if l <= 0.5 * i: l = i + 1 - l m = i b = temp i += 1 return l
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.