Cracking_LFSR_with_know_plain_text_attack

## https://www.root-me.org/en/Challenges/Cryptanalysis/LFSR-Known-plaintext?action_solution=voir#ancre_solution
import os
from collections import deque
import numpy as np
import copy

DIR = os.path.dirname(os.path.realpath(__file__))
key1=[]
def berlekamp_massey(data):
    """
   Implementation of berlekamp-massey algorithm that finds the minimal LFSR and minimal polynomial to generate given
   data
   :param data: list of 1s and 0s
   :type data: list[int]
   :return:
   """
    n = len(data)
    c_x, b_x = np.zeros(n, dtype=np.int), np.zeros(n, dtype=np.int)
    c_x[0], b_x[0] = 1, 1
    l, m, i = 0, -1, 0
    while i < n:
        v = data[(i - l):i]
        v = v[::-1]
        cc = c_x[1:l + 1]
        delta = (data[i] + np.dot(v, cc)) % 2
        if delta == 1:
            temp = copy.copy(c_x)
            p = np.zeros(n, dtype=np.int)
            for j in range(0, l):
                if b_x[j] == 1:
                    p[j + i - m] = 1
            c_x = (c_x + p) % 2
            if l <= 0.5 * i:
                l = i + 1 - l
                m = i
                b_x = temp
        i += 1
    c_x = c_x.tolist()
    ind = 0
    for x in c_x[::-1]:
        if x == 0:
            ind += 1
        else:
            break
    c_x = c_x[:-ind]
    return len(c_x)-1, c_x

def generate_key(polynomial, init_state=None):
    """
   Create key using given polynomial and determine whether the polynomial by counting number of states generated
   :param polynomial: Binary string representing the connection polynomial
   :type polynomial: str
   :param init_state: binary string representing initial state of the key generation
   :type init_state: str
   :raises ValueError if init_state doesn't match polynomial degree or any of the strings are not binary
   :return:
   """
    degree = len(polynomial) - 1

    ini = init_state if init_state is not None else '0' * (degree - 1) + '1'
    ini = [int(x) for x in ini]
    if len(ini) != degree:
        raise ValueError("Degrees don't match")

    xor_indices = []
    for i, n in enumerate(polynomial[1:]):
        if n == '1':
            xor_indices.append(i)

    key = []
    ini_deque = deque(ini)
    cur_state = deque(ini)
    while True:
        el = sum(cur_state[x] for x in xor_indices) % 2  # xor the elements in the indices determined by the polynomial

        key.append(cur_state.pop())
        cur_state.appendleft(el)
        if ini_deque == cur_state:  # full cycle completed
            break
    return key

def break_partially_known(cipher, ends_with):
    """
   Extract plain text, connection polynomial and initial state from partially known cipher text
   :param cipher: integer array of 1s and 0s representing message
   :type cipher: list[int]
   :param ends_with: string that is known to be end of message
   :type ends_with: str
   :return:
   """
    binary_str = ''.join(format(ord(x), 'b').zfill(8) for x in ends_with)
    len_of_known = len(binary_str)
    partial_cipher = cipher[-len_of_known:]
    partial_key = [(partial_cipher[i] + int(binary_str[i])) % 2 for i in range(len(partial_cipher))]
    print (partial_key)
    l, c_x = berlekamp_massey(partial_key)
    key = deque(generate_key(''.join(str(x) for x in c_x), ''.join(str(x) for x in partial_key[l-1::-1])))

    key.rotate(-len_of_known)
    key1=list(key)
    key = list(key)[-len(cipher):]

    extracted_plain_binary = ''.join([str((cipher[i] + key[i]) % 2) for i in range(len(cipher))])
    print (extracted_plain_binary)
    return key1,''.join(str(x) for x in c_x), key,''.join(chr(int(extracted_plain_binary[i:i+8], 2)) for i in range(0, len(extracted_plain_binary), 8))

def show_image(input__):
    try :
        image = Image.open(io.BytesIO(input__))
        image.show()
        return 1
    except :
        return 0

cipher=[0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,0,0,0,1,1,1,0,1,0,0,0,0,1,0,1,0,0]

ends_with = 'IHDR'
key1,con_pol, key, plain_text = break_partially_known(cipher, ends_with)

pos=len(key1)-len(cipher)
lenkey=len(key1)
print("start pos:=",pos)
fin=open(f"{DIR}/challenge.png.encrypt","rb")
datain=fin.read()
print(len(datain))
# fout=open("challenge.png","wb")
inbinary_str = ''.join(format(datain[x], 'b').zfill(8) for x in range(len(datain)))
plain_binary = ''.join([str((int(inbinary_str[i]) + key1[(i+pos)%lenkey]) % 2) for i in range(len(inbinary_str))])
dataout=''.join(chr(int(plain_binary[i:i+8], 2)) for i in range(0, len(plain_binary), 8))
## Password is LSFRNGAG
fout.write(dataout.encode("Latin-1"))
fout.close()
fin.close()