Skip to content

Instantly share code, notes, and snippets.

@StuartGordonReid
Last active July 21, 2024 03:00
Show Gist options
  • Save StuartGordonReid/a514ed478d42eca49568 to your computer and use it in GitHub Desktop.
Save StuartGordonReid/a514ed478d42eca49568 to your computer and use it in GitHub Desktop.
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 [1]
[1] 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])[0][::-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 [1]
[1] - 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[0], b[0] = 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment