Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 6.1.2 Добавление нелинейности
- Нелинейная обратная связь.
| Атака с восстановлением . Результат 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 с максимальной длиной и так, чтобы результат имел хорошие статистические свойства. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|