***** Google.Поиск по сайту:


Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.4.2. Слабые места линейных регистров сдвига с обратной связью

Схема шифрования, в которой для порождения ключевого потока применяются линейные регистры сдвига с обратной связью (linear feedback shift register — LFSR), является очень уязвимой по отношению к атакам. Чтобы определить отводы обратной связи, начальное состояние регистра и всю последовательность кода, криптоаналитику требуется всего 2п бит открытого текста и соответствующий им шифрованный текст. Как правило, 2n намного меньше периода 2n-1. Проиллюстрируем эту уязвимость с помощью примера регистра, изображенного на рис. 14.13. Пусть криптоаналитику, который ничего не знает о внутренних связях регистра, удалось получить 2п = 8 бит шифрованного текста и их открытый эквивалент.

Открытый текст: 01010101

Шифрованный текст: 00001100

Здесь крайний правый бит получен первым, а крайний левый — последним.

Чтобы получить фрагмент ключевого потока 01011001 (рис. 14.14), криптоаналитик складывает обе последовательности по модулю 2. Ключевой поток показывает содержание регистров в различные моменты времени. Крайние правые четыре ключевых бита показывают содержание регистра сдвига в момент t1. Если последовательно «сдвигать» эту четверку на один символ влево, то получим содержимое регистра в моменты t2, t3, t4. Используя линейную структуру регистра сдвига, можно записать следующее.

g4x4 + g3x3 + g2x2 + gixi= x5 (14.27)

Рис. 14.14. Пример уязвимости линейного регистра сдвига с обратной связью

Здесь x5цифра, которая через контур обратной связи подана обратно на вход, а gi (i= 1 или 0) определяет i-e соединение обратной связи. Таким образом, изучая содержание регистра в четыре момента времени, изображенных на рис. 14.14, можно написать следующие четыре уравнения с четырьмя неизвестными.

g4 (1) + g3 (0) + g2 (0) + g1 (1) = 1

g4 (1) + g3 (1) + g2 (0) + g1 (0) = 0

g4 (0) + g3 (1) + g2 (1) + g1 (0) = 1 (14.28)

g4 (1) + g3 (0) + g2 (1) + g1 (1) = 1

Решение уравнений (14.28), соответствующих регистру, изображенному на рис. 14.13, является g1 = l, g2 = l, g3 = 0, g4 = 0. Таким образом, криптоаналитик узнал связи регистра, а также его начальное состояние в момент t1. Следовательно, он может узнать последовательность в любой момент времени [3]. Обобщив этот пример на любой регистр сдвига с п разрядами, можно переписать уравнение (14.27) следующим образом.

(14.29)

Уравнение (14.29) можно записать в матричной форме.

х = Хg (14.30)

где

x = g =

и

Х = .

Можно показать [3], что столбцы X линейно независимы; таким образом, матрица X невырождена (ее определитель отличен от нуля) и имеет обратную. Следовательно,

g = X-1 x (14.31)

Обращение матрицы требует порядка n3 операций и, таким образом, легко выполняется на компьютере для любого разумного значения п. Например, если n = 100, то n3 = 106, и компьютеру со скоростью работы одна операция за 1 мкс для обращения матрицы понадобится 1с. Слабость регистра сдвига с обратной связью обусловлена линейностью уравнения (14.31). Использование нелинейной обратной связи в регистре сдвига делает задачу криптоаналитика гораздо сложнее, если не вычислительно трудноосуществимой.




***** Яндекс.Поиск по сайту:



© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.