Атака с восстановлением . Результат LFSR максимальной длины степени n
имеет хорошие статистические свойства; например, каждая n-битная строка появ-
ляется с относительно равной частотой в выходном потоке LFSR. Тем не менее,
LFSR являются не очень хорошими псевдослучайными генераторами для крипто-
графических целей, потому что их результат предсказуем. Это проистекает из того
факта, что атакующий может рекоснтруировать целое состояние степени-n LFSR
после получения максимум 2n выходных битов. Чтобы в этом убедиться, предпо-
ложим, что и начальное состояние и коэффициенты обратной связи какого-то LFSR
неизвестны. Первые n выходных бит y1, . . . , yn LFSR точно отражают начальное
сотояние. Учитывая следующие n выходных бит yn+1, . . . , y2n, атакующий может
установить систему n линейных уравнений в n неизвестных c0, . . . , cn−1:
yn+1 = cn−1 yn ⊕ • • • ⊕ c0 y1
y2n = cn−1 y2n−1⊕ • • • ⊕c0 yn.
Можно показать, что вышеописанные уравнения линейно независимые (по
модулю 2) для LFSR максимальной длины, и таким образом, однозначно уста-
новить коэффициенты обратной связи. (Решение может быть с легкостью най-
дено при помощи линейной алгебры.) При известных коэффициентах обратной
связи все последующие выходные биты LFSR могут быть легко вычислены.
6.1.2 Добавление нелинейности
Линейные отношения между выходными битами LFSR - это то, что упрощает
атаку. Чтобы предотвратить такую атаку мы должны ввести некоторую нели-
нейность, то есть некоторые операции отличные от XOR. Существует несколь-
ко различных подходов для этого, но мы здесь изучим только некоторые из них.
Нелинейная обратная связь. Очевидный способ изменить LFSR является
- это сделать петлю обратной связи нелинейной. Регистр сдвига с нелинейной
обратной связью (FSR) будет состоять из массива регистров, каждый из кото-
рых содержит одиночный бит. Как и ранее, состояние FSR обновляется каждые
несколько «тика часов» путем движения значений во всех регистрах вправо;
теперь, однако, новое значение самого левого регистра является нелинейной
функцией текущих регистров. Другими словами, если состояние в какой-то
промежуток времени t - s0(t), . . . , sn-1(t), тогда состояние после следующего
тика часов - s0(t+1), . . . , sn-1(t+1) с
для какой-то нелинейной функции g. Как и ранее, FSR выводит значение самого
правого регистра s0 при каждом тике часов.
216
Есть возможность разработать нелинейные FSR с максимальной длиной и
так, чтобы результат имел хорошие статистические свойства.
Достарыңызбен бөлісу: |