Need help with a Cryptology / Cryptography problem using Python:

(Breaking an LFSR) You've been playing with a 4-register LFSR; when you turned it on, it started a keystream:

so 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, etc.in that order (i.e. starting with s0). Reconstruct the wiring on the LFSR, i.e. determine (p3, p2, p1, p0).

Hint: set up systems of equations by instantiating (s4, s3,s2,s1,s0) from your output in s4 = p3*s3 + p2*s2 + p1*s1 + p0*s0 (mod 2). 4 equations should be sufficient to break the system. (If you have trouble solving the system using elimination techniques, then try solving it using brute force, that is, simplify it by assuming that p0=0 or p0=1 and see what happens.)

Example code for an LFSR (lfsr.py):

from random import *

reg = {}

#Registers s_{n-1} ... s_0 are stored in list reg: # # reg[n-1] reg[n-2] ... reg[0] # s_{n-1} s_{n-2} s_0 # #when displaying reg, we need to reverse order, so reg[0] is rightmost #seed is written in order s_0 s_1 s_2...s_{n-1}

def seed_reg(): global reg reg = seed[:] #create copy of seed

#implements s_{n+3} = s_{n+2} + s_{n} def s(): global reg new_bit = (reg[2] + reg[0]) % 2 out_bit = reg[0] reg = reg[1:] reg.append(new_bit) return out_bit

#implements s_{n+5} = s_{n+4} + s_{n+3} + s_{n+1} + s_{n} def s(): global reg new_bit = (reg[4]+reg[3]+reg[1] + reg[0]) % 2 out_bit = reg[0] reg = reg[1:] reg.append(new_bit) return out_bit

def cur_reg(): 'display current state of register reg' return ''.join(map(str, reg[::-1])) #or use loop; displaying reg

f = s #or some other linear feedback shift register seed = [1,0,0,0,0] #for s0s1...

seed_reg()

for i in range(40): print('Index: {} Register: {} Output: {}'.format(i,cur_reg(),f()))

Python 3.5.2 Shell File Edit Shell Debug Options Window Help Register 0011 Output 1 Register 1001 Output 1 Register 1100 Output 0 Register 1110 Output 0 Register 0111 Output 1 Register 1011 Output 1 Register 0101 Output 1 Register 0010 Output 0 Register 1001 Output 1 Register 1100 Output 0 Register 1110 Output 0 Register 0111 Output 1 Register 1011 Output 1 Register 0101 Output 1 Register 0010 Output 0 Register 1001 Output 1 Register 1100 Output 0 Register 1110 Output 0 Register 0111 Output 1 Register 1011 Output 1 Ln: 25 Col 4 Python 3.5.2 Shell File Edit Shell Debug Options Window Help Register 0011 Output 1 Register 1001 Output 1 Register 1100 Output 0 Register 1110 Output 0 Register 0111 Output 1 Register 1011 Output 1 Register 0101 Output 1 Register 0010 Output 0 Register 1001 Output 1 Register 1100 Output 0 Register 1110 Output 0 Register 0111 Output 1 Register 1011 Output 1 Register 0101 Output 1 Register 0010 Output 0 Register 1001 Output 1 Register 1100 Output 0 Register 1110 Output 0 Register 0111 Output 1 Register 1011 Output 1 Ln: 25 Col 4