Скляр Б. Цифровая связь (2003) (1151859), страница 217
Текст из файла (страница 217)
Статистические свойства двоичных псевдослучайных последовательностей подобны получаемым при случайном подбрасывании симметричной монеты. В то же время, разумеется, эти последовательности являются детерминистическими (см. раздел 12.2). Данные технологии популярны, поскольку алгоритмы шифрования и дешифрования воплощаются с использованием регистров сдвига с обратной связью. На первый взгляд может показаться, что поточный псевдослучайный ключ может обеспечивать ту же зашишенность, что и метод одномоментного заполнения, поскольку период последовательности, порожденной линейным регистром сдвига, составляет 2" ' бит, где а — количество разрядов в регистре. Если псевдослучайная последовательность воплошается с помошью 50- разрядного регистра и дискретности в 1 МГц, последовательность будет повторяться каждые 2" — 1 микросекунды, или каждые 35 лет.
В эпоху больших интегральных схем совсем несложно реализовать схему с 100 разрядами. В этом случае последовательность будет повторяться каждые 4 х 10" лет. Следовательно, можно предположить, что поскольку псевдослучайная последовательность не повторяется в течение такого длительного периода, она может казаться действительно случайной и давать совершенную секретность.
Но все же существует одно важное отличие псевдослучайной последовательности от действительно случайной последовательности, используемой в методе одномоментного заполнения. Псевдослучайная последовательность генерируется алгоритмом. Таким образом, если известен алгоритм, то известна и сама последовательность. В разделе!4.4.2 будет показано, что из-за этой особенности схема шифрования, которая использует линейный регистр сдвига с обратной связью, слишком уязвима к атаке известного открытого текста. 14.4.1.
Пример генерирования ключа с использованием линейного регистра сдвига с обратной связью В технологии поточного шифрования для генерации псевдослучайной ключевой последовательности обычно используются регистры сдвига. Регистр сдвига может быть превращен в генератор псевдослучайной последовательности путем введения контура обратной связи, который вычисляет новый элемент для первого разряда, основываясь на предыдуших а элементах. Говорят, что регистр является линейным, если линейна операция, производимая в контуре обратной связи.
В разделе 12.2 мы уже рассматривали пример генератора псевдослучайной последовательности. На рис. 14.13 этот генератор приведен повторно. В данном случае разряды регистра удобно нумеровать так, как показано на рис. 14.13, где а = 4, а выходы разрядов 1 и 2 суммируются по модулю 2 (линейная операция) и передаются обратно на разряд 4.
Если начальное состояние разрядов (хз, х,, х., х,) — это 1000, то следуюшие состояния будут выглядеть как 1000, 0100, 0010, 1001, 1!00 и тд. Выходная последовательность составлена из битов, снимаемых с крайнего правого разряда регистра, т.е. 111101011001000, где крайний правый бит в последовательности является самым ранним, а крайний левый— наиболес поздним. При данном произвольном и-разрядном линейном регистре сдвига с обратной связью выходная последовательность в конечном счете периодична. Выход Рис.
14.1Х Пример яииейиого регисюра сдвига с обраюиой связью 14.4.2. Слабые места линейных регистров сдвига с обратной связью Схема шифрования, в которой для порождения ключевого потока применяются линейные регистры сдвига с обратной связью (!шеаг !ее!)Ьас)с зЬ!з! ге8!з!ег — ЕГБК), является очень уязвимой по отношению к атакам. Чтобы определить отводы обратной связи, начальное состояние регистра и всю последовательность кода, криптоаналитику требуется всего 2и бит открытого текста и соответствующий им шифрованный текст. Как правило, 2и намного меньше периода 2" — 1.
Проиллюстрируем эту уязвимость с помощью примера регистра, изображенного на рис. 14.13. Пусть криптоаналитику, который ничего не знает о внутренних связях регистра, удалось получить 2и = 8 бит шифрованного текста и их открытый эквивалент. Открытый текст: 01010101 Шифрованный текст: 00001100 Здесь крайний правый бит получен первым, а крайний левый — последним.
Чтобы получить фрагмент ключевого потока 01011001 (рис. 14.14), криптоаналитик складывает обе последовательности по модулю 2. Ключевой поток показывает содержание регис~ров в различные моменты времени. Крайние правые четыре ключевых бита показывают содержание регистра сдвига в момент гн Если последовательно "сдвигать" эту четверку на один символ влево, то получим содержимое регистра в моменты г,, г,, г,. Используя линейную структуру регистра сдвига, можно записать следующее: 84х4'! 8зхз ~ 8гхг+ 8!х! хз' (14.27) Здесь х, — цифра, которая через контур обратной связи подана обратно на вход, а 8, (= 1 или 0) определяет 1-е соединение обратной связи. Таким образом, изучая содержание регистра в четыре момента времени, изображенных на рис. 14.14, можно написать следующие четыре уравнения с четырьмя неизвестными. 84(1) + Хз(0) '! Хг(0) + Хз(1) 1 Ы1)+хз(1)+хг(0)+Хз(0) =0 84(0) + Яз(1) + хг(1) + 8~(0) = 1 бь(1)+8!(о)+8,(И+8,(И =о (14.28) л х„е,= ) бхг (14.29) з=! 933 14.4.
Погонное щизьооиянив Решение уравнений (14.28), соответствующих регистру, изображенному на рис. 14.13, является 8!=1, 8!=1, 8!=0, 8,=0. Таким образом, криптоаналитик узнал связи регистра, а также его начальное состояние в момент ги Следовательно, он может узнать последовательность в любой момент времени [3[. Обобщив этот пример на любой регистр сдвига с и разрядами, можно переписать уравнение (14.27) следующим образом: И 4кво Шифрованный текат оооо!!оо ап бнт Кпючввоа поток: О Рис.
14. 14. Пример уатвимости гинейного регистра сдвига с обратной сватью Уравнение (14.29) можно записать в матричной форме. (14.30) х= Хя, где ха+! аз Хн+ 2 Х! Х2 ... Х„ Х2 ХЗ ... Хнн! Х= Х» Хет! " Х2н-! Можно показать (3), что столбцы Х линейно независимы; таким образом, матрица Х невырождена (ее определитель отличен от нуля) и имеет обратную, Следовательно, (14.31) Обре!пение матрицы требует порядка и' операций и, таким образом, лепсо выполняется на компьютере для любого разумного значения и. Например, если и = 100, то и'= 10', и компьютеру со скоросп ю работы одна операция за 1 мкс для обре!ценил матрицы понадобится 1 с.
Слабость регистра сдвига с обратной связью обусловлена линейностью уравнения (14.31). Использование нелинейной обратной связи в регистре сдвига делает задачу криптоа- налитика гораздо сложнее, если не вычислитехьно невозможной. 14.4.3. Синхронные и самосиихрониаирующиеся системы поточиого шифрования Системы поточного шифрования можно разделить на синхронные и самосинхронизирующиесл. В первых ключевой поток генерируется независимо от сообщения; так что потеря символа во время передачи неизбежно требует повторной синхронизации передачи и генераторов ключей приемника. Синхронный поточный шифр изображен на рис. 14.15.
Начальное состояние генератора ключа инициализируется с помощью известного входа 1о. Шифрованный текст получается путем сложения по модулю 2 1-го символа ключа к, и 1-го символа сообщения т,. Такие синхронные шифры обычно создаются для смешения (см. раздел 14.3.1), но не диффузии. Иными словами, шифрование символа не распространяется вдоль некоторого блока сообщения. По этой причине синхронные поточные шифры не имеют накопления ошибки. Шифрование Дешифрование т, о, т, Рис. 14.!5. Синхронный поточный шифр При самосинхронизирующвмсл поточном шифре каждый ключевой символ определяется из фиксированного числа и предшествующих символов шифрованного текста (отсюда и название обратнан связь по шифру).
В таких системах происходит следующее: если символ шифрованного текста теряется во время передачи, ошибка накапливается для и символов, но после получения и верных символов шифрованного текста система восстанавливается. В разделе 14.1.4 приводился пример обратной связи для шифрования с помощью автоматического ключа Вигнера. Показывалось, что преимуществом такой системы является: (1) генерация неповторяющегося ключа и (2) диффузия статистик открытого сообщения в шифрованном тексте. В то же время был и недостаток — ключ проявлялся в шифрованном тексте. Этой проблемы можно избежать, если при получении ключа пропустить символы шифрованного текста через нелинейный блок шифрования. На рис. 14.16 изображен регистр сдвига генератора ключа, работающий в режиме обратной связи по шифру. Каждый выходной символ шифрованного текста с, (образованный путем сложения по модулю 2 символа сообщения т, и символа ключа й,) подается обратно на вход регистра сдвига.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
