Итак, в этом задании флаг просто ксорится с некой ключевой последовательностью, которую выдаёт класс Stream.
Известно, что функция XOR обладает простым свойством — a xor b xor b = a. Это означает, что таск решается предельно просто — запустим тот же скрипт, но для зашифрованного файла — и файл расшифруется. Но не тут-то было.
Что ж, воспользуемся предложенным сайтом. Попробовав зашифровать одно и то же сообщение несколько раз, видим, как шифротекст меняется. Дело в том, что переменная value глобальная, и она меняется после каждого шифрования.
Алгоритм, по которому генерируется ключевая последовательность, довольно стандартный и известный. Называется он LFSR, или регистр сдвига с линейной обратной связью. Значение value в нём и обозначает этот самый регистр. Для решения задания даже необязательно разбираться, как работает алгоритм. Достаточно заметить две вещи:
valueникогда не превысит 218- следующий бит и новое значение
valueзависит только от текущегоvalue
Следовательно, если значение value совпадет с каким-то из предыдущих, вся дальнейшая последовательность value будет циклическим повтором. При этом value гарантированно хотя бы раз за 218 шагов повторится — потому что всего различных возможных чисел у нас 218.
Интересно то, что для данного секрета длина такого цикла — 262143 — максимально возможная. Это связано с тем, что под неприметным числом 174807 скрывается примитивный многочлен степени 17.
Осталось перебрать все эти 262143 возможных значений value и для каждого узнать, не начинается ли флаг с ugra.
Флаг: ugra_lfsr_is_so_cyclic_dbf6deae053a5be4