Не совсем понятно, что такое "определенный временной код", но я буду понимать его как последовательность конечной длины. $s_0, s_1, \ldots, s_{N-1}$ из $N$ биты. Сама последовательность может быть или не быть сгенерирована LFSR — мы не знаем — но мы хотели бы найти (Fibonacci) LFSR, который генерирует последовательность.
Давайте немного подготовим сцену. LFSR Фибоначчи длины $n$
представляет собой массив $n$ биты с начальным значением
$$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ и последовательные значения
$$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\
\Кнопка "Стрелка вниз\
(s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\
\Кнопка "Стрелка вниз\
(s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\
\Кнопка "Стрелка вниз\
\cdots\quad \cdots$$
где содержимое массива сдвигается влево на каждом шаге (тактовый цикл)
так что биты падают
с левого конца (LFSR вывод) — заданная последовательность, а
биты показаны как въезд в ЛФСР справа
находятся вычисляется как линейная комбинация (также известная как сумма исключающего ИЛИ) некоторый ЛССР
содержимое на предыдущем шаге. В частности, для $i\geq 0$,
в переход состояния можно выразить как
$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\
\Кнопка "Стрелка вниз\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad {\Large{\oplus}}_{j=0}^ {n-1}c_{n-j} s_{i+j}\biggr),$$
где $c_i$имеют значение $0$ или же $1$, таким образом линейный комбинация
$c_ns_i\oplus c_{n-1}s_{i+1} \oplus \cdots \oplus c_1s_{i+n-1}$ предыдущего
Содержимое LFSR вернули в правый конец LFSR
как $s_{n+i}$ на самом деле является суммой исключающего ИЛИ нескольких выбранных битов предыдущего содержимого (тех, для которых соответствующие $c_i$ иметь значение $1$).
Отсюда и название сдвигового регистра с линейной обратной связью, который инициализируется в LFSR.
Имея в виду приведенное выше описание, один ответ на вопрос о LFSR тривиален в одном смысле: $N$ ступень LFSR с коэффициентами обратной связи $(c_N,c_{N-1}, \cdots, c_1) = (1,0,0,\cdots, 0)$ и начальная загрузка $\big(s_0, s_1, \ldots, s_{N-1}\big)$ будет производить бесконечные повторения
$$s_0, s_1, \ldots, s_{N-1},s_0, s_1, \ldots, s_{N-1}, s_0, s_1, \ldots, s_{N-1}, \cdots$$
заданного временного кода
$s_0, s_1, \ldots, s_{N-1}$ на всю вечность. Альтернативно, Любые другой выбор $(c_N,c_{N-1}, \cdots, c_1)$ заполнит сдвиговый регистр чем-то другим, но первым $N$ биты все равно будут $s_0, s_1, \ldots, s_{N-1}$ и то, что последует за этим, будет другим. Это явно не то, что нам нужно, и поэтому мы ищем лучший критерий: находим самый короткий LFSR (и его начальная загрузка), который будет генерировать $s_0, s_1, \ldots, s_{N-1}$, и это именно то, что находит алгоритм Берлекэмпа-Месси.
Алгоритм Берлекэмпа-Месси представляет собой итеративный процесс, состоящий из поиска кратчайшего LFSR, который генерирует первый $t$ биты
$s_0, s_1, \ldots s_{t-1}$ и проверка, если LFSR
находит $s_t$ правильно. Если так, $s_{t+1}$ проверено,
а если нет, то $c_i$обновлены так, что
пересмотренный LFSR генерирует $s_t$. Часто, но не всегда длина LFSR увеличивается. Итеративный процесс продолжается до последнего доступного бита. $s_{N-1}$ была обработана, так что, когда алгоритм Берлекэмпа-Масси завершает работу, синтезированный LFSR создает всю последовательность $s_0, s_1, \ldots, s_{N-1}$ на его выходе. Если синтезированный LFSR имеет $n\leq N$ стадий, то его первоначальная загрузка
$\big(s_0, s_1, \ldots, s_{n-1}\big)$ (которые первые $n$ выходных битов), и LFSR правильно вычисляет $s_n, s_{n+1}, \cdots, s_{N-1}$ (то есть остальная часть данной последовательности). Длина LFSR, синтезированного алгоритмом Берлекэмпа-Месси, гарантированно равна минимальный: нет LFSR, который генерирует $s_0, s_1, \ldots, s_{N-1}$ может иметь короче длина. Однако, есть нет утверждают, что $n$ гарантированно меньше, чем $N$; вполне может оказаться, что тривиальные решения, описанные выше, являются минимальными решениями. Действительно, я утверждаю, что это действительно так для наиболее последовательности; LFSR имеет длину $N$. Колмогоровская теория сложности говорит, что самая короткая программа для вывода большинства строк длины $N$ имеет длину $N+c$, или, в просторечии, для большинства строк можно сделать немногим лучше, чем просто сохранить строку и распечатать ее; "$с$" - это просто длина команды "Распечатать следующую строку". В контексте сдвиговых регистров для большинства последовательностей длины $N$, кратчайший регистр сдвига, выход которого представляет собой заданную последовательность длины $N$ это просто сдвиговый регистр длины $N$ инициализируется заданной последовательностью. Какая обратная связь (если она вообще есть) не имеет значения.
- Если последовательность действительно была создана
$n$-стадия LFSR, как описано выше, где $n \leq \frac N2$, затем Берлекамп-Месси
алгоритм находит все $n$ коэффициенты $c_i$ после
изучение $s_0, s_1, \ldots, s_{2n-1}$. Начальная загрузка синтезированного LFSR, конечно же, всего лишь $\big(s_0, s_1, \ldots, s_{n-1}\big)$. Из этого
далее алгоритм Берлекампа-Месси может
продолжайте проверять остальную часть последовательности (если это так
желательно), но не требует обновления $c_i$х
потому что каждая проверка следующего символа просто сообщает
назад, что все в порядке; текущий LFSR также генерирует следующий бит. Однако, в общем, у криптоаналитика есть нет представление о том, был ли временной код вообще сгенерирован LFSR; это просто последовательность $N$ биты неизвестного происхождения, поэтому для целей криптоаналитика все $N$ биты должны быть проверены, чтобы найти самый короткий LFSR, который может генерировать $s_0, s_1, \ldots, s_{N-1}$. Если дополнительные биты $s_N, s_{N+1}, \ldots$ доступны, то нет гарантии, что LFSR обнаружит после проверки $N$ биты также будут генерировать эти дополнительные биты. На самом деле, вся идея алгоритма Берлекэмпа-Месси заключается в том, что если тест «Генерирует ли текущий LFSR также $s_n$?" не удается, алгоритм синтезирует модифицированный LFSR из текущего LFSR, так что модифицированный LFSR генерирует $s_0, s_1, \ldots, s_{n-1},s_n$. В этом процессе длина LFSR может (а может и нет) увеличиться.
- Если последовательность действительно была создана
$n$-стадия LFSR, как описано выше, где $\frac N2 < n \leq N$, то алгоритм Берлекэмпа-Месси находит кратчайший LFSR, который генерирует $s_0, s_1, \ldots, s_{N-1}$. Он может генерировать, а может и не генерировать одинаковые значения для $s_N, s_{N+1}, \cdots, s_{2n-1}$ как это делает настоящий LFSR.
Имея в виду вышеупомянутую длинную обличительную речь, давайте ответим на вопросы ОП. В заголовке ОП спрашивает
Какие инструменты доступны для обратного проектирования LFSR помимо BMA?
Ну, расширенный алгоритм Евклида для многочленов можно использовать наибольшие общие делители, но в некотором смысле это эквивалентно алгоритму Берлекэмпа-Месси; это можно рассматривать как обработку последовательности в обратном порядке $s_{N-1}, s_{N-2}, \cdots, s_1, s_0$ по сравнению с заказом $s_0, s_1, \cdots, s_{N-2}, s_{N-1}$ используется алгоритмом Берлекампа-Месси.
В теле вопроса ОП жалуется
этот код, кажется, имеет линейную сложность 110, что никоим образом не практично.Его также нельзя восстановить с помощью 110-битного неприводимого полинома, который находит BMA. Как и ожидалось, только первые несколько битов, а затем биты, кажется, переворачиваются.
Вполне вероятно, что эта проблема связана с ошибками в реализации BMA. «Ни в коем случае не практично» предполагает, что, возможно, было выделено недостаточно памяти для хранения различных полиномов, используемых внутри BMA, или что буферы переполнились и т. д. Как указывает @kodlu, если временной код имеет длину $220$ биты, затем проверяя все $220$ битов может привести к LFSR длины $110$. В противном случае, как обсуждалось выше, если временной код имеет длину $110$ или более (возможно $128$ биты $= 16$ байт?), BMA вполне может синтезировать LFSR длины $110$. Наконец, у меня нет другого объяснения, кроме ошибки программиста, для наблюдения ОП о том, что в синтезированном выводе LFSR «первые несколько битов» верны, а остальные перевернуты.
Кто-нибудь знает, при каких условиях BMA обнаруживает такой чрезвычайно длинный полином?
См. материал над пунктирной линией в этом ответе.
