---

import itertools
import numpy as np

# Данные из output.txt
seed = [
    1,
    0,
    0,
    1,
    1,
    1,
    1,
    1,
    0,
    0,
    1,
    0,
    0,
    0,
    0,
    0,
    1,
    1,
    0,
    1,
    0,
    0,
    1,
    1,
    0,
    1,
    1,
    1,
    0,
    0,
    1,
    0,
]
hex_enc = "0a9e47b25066fedf5d59d26b0701223e3f1010c84ac95f51021bb0242f833480797984c4f5c33d0cc9aa9bc5654be281f9b72595dbacc309e1deea7f174858e849d31df30dea39f1"

# Переводим hex в биты шифротекста
num_of_bits = len(hex_enc) * 4
bin_enc = bin(int(hex_enc, 16))[2:].zfill(num_of_bits)
enc_bits = [int(b) for b in bin_enc]

# Известный префикс флага для получения первых бит гаммы
known_text = "DUCKERZ{"
known_bits = [int(b) for char in known_text for b in format(ord(char), "08b")]
target_keystream = [known_bits[i] ^ enc_bits[i] for i in range(len(known_bits))]


class Cipher:

  def __init__(self, polynom, seed):
    self.state = np.array(seed, dtype=np.uint8)
    self.polynom = np.array(polynom, dtype=np.uint8)

  def step(self):
    feedback = np.bitwise_xor.reduce(self.state[self.polynom])
    output = self.state[-1]
    self.state[1:] = self.state[:-1]
    self.state[0] = feedback
    return output

  def generate_keystream(self, length):
    return [self.step() for _ in range(length)]


print("[*] Поиск полинома обратной связи...")
found_polynom = None

# Перебираем комбинации индексов полинома (обычно в таких тасках длина невелика)
for r in range(1, 6):
  for combo in itertools.combinations(range(len(seed)), r):
    c = Cipher(list(combo), seed)
    ks = c.generate_keystream(len(target_keystream))
    if ks == target_keystream:
      found_polynom = list(combo)
      break
  if found_polynom:
    break

if found_polynom:
  print(f"[+] Полином найден: {found_polynom}")

  # Генерируем полную гамму для всего шифротекста
  c = Cipher(found_polynom, seed)
  full_keystream = c.generate_keystream(len(enc_bits))

  # Расшифровываем биты с помощью XOR
  decrypted_bits = [enc_bits[i] ^ full_keystream[i] for i in range(len(enc_bits))]

  # Превращаем биты обратно в символы текста
  byte_list = []
  for i in range(0, len(decrypted_bits), 8):
    byte_bits = decrypted_bits[i : i + 8]
    if len(byte_bits) < 8:
      break
    byte_val = int("".join(map(str, byte_bits)), 2)
    byte_list.append(byte_val)

  flag = "".join(map(chr, byte_list))
  print(f"\n[+] ФЛАГ УСПЕШНО РАСШИФРОВАН:\n{flag}")
else:
  print("[-] Не удалось найти полином среди комбинаций небольшой длины.")