Введение в современную криптографию



Pdf көрінісі
бет159/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   155   156   157   158   159   160   161   162   ...   249
Криптография Катц

Атака с восстановлением . Результат 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 с максимальной длиной и 
так, чтобы результат имел хорошие статистические свойства.


Достарыңызбен бөлісу:
1   ...   155   156   157   158   159   160   161   162   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет