Вопрос № 35

12.4.3. Метод гаммирования.

 

Попытки приблизиться к совершенной секретности демонстрируют многие современные телекоммуникационные системы, использующие операцию скремблирования. Под скремблированием понимается процесс наложения на коды символов открытого текста кодов случайной последовательности чисел, которую называют также гаммой (по названию буквы g греческого алфавита, используемой в математических формулах для обозначения случайного процесса). Гаммирование относится к поточным методам шифрования, когда следующие друг за другом символы открытого текста последовательно превращаются в символы шифрограммы, что повышает скорость преобразования. Так, например, поток информационных бит поступает на один вход сумматора по модулю 2, изображенного на рис. 12.14, тогда как на второй – скремблирующая двоичная последовательность . В идеале последовательность должна быть случайной последовательностью с равновероятными значениями нулей и единиц. Тогда выходной шифрованный поток будет статистически независимым от информационной последовательности , а значит, будет выполняться достаточное условие совершенной секретности. В действительности абсолютная случайность не является необходимой, поскольку в противном случае получатель не сможет восстановить открытый текст. Действительно, восстановление открытого текста на приемной стороне должно производиться по правилу , так что на приемной стороне должна генерироваться точно такая же скремблирующая последовательность и с той же фазой. Однако вследствие абсолютной случайности данная процедура становится невозможной.

На практике в качестве скремблирующих широкое применение нашли псевдослучайные последовательности (ПСП), которые могут быть воспроизведены на приемной стороне. В технологии поточного шифрования для формирования ПСП обычно используют генератор на основе линейного регистра сдвига с обратной связью (linear feedback shift register (LFSR)). Типичная структура генератора ПСП, представленная на рис. 12.15, включает регистр сдвига, который состоит из – ичных элементов задержки или разрядов, имеющих возможных состояний и хранящих некоторый элемент поля в течение тактового интервала, схему обратной связи, включающей умножители элементов (состояний), хранящихся в разрядах, на константы , и сумматоров. Формирование ПСП описывается рекуррентным соотношением вида

где коэффициенты – фиксированные константы, принадлежащие , согласно которому каждый следующий элемент последовательности вычисляется на основании n предшествующих.

Поскольку число различных состояний регистра конечно (не более ) неизбежна ситуация, когда после некоторого числа тактов состояние повторится в виде одного из ранее случившихся. Однако, стартуя с некоторой начальной загрузки, т.е. фиксированного состояния, схема на рис. 12.15 сформирует только единственную последовательность, определяемую упомянутой рекурсией. Следовательно, повторение состояния регистра ведет к повторению всех последующих генерируемых символов, означающее, что любая ПСП периодична. Более того, в случае нулевого состояния регистра (наличия нулей во всех разрядах) всегда будет формироваться бесконечная вырожденная последовательность, состоящая только из одних нулей. Очевидно, что подобный случай абсолютно бесперспективен, так что нулевое состояние регистра должно быть исключено. В результате остается не более допустимых состояний регистра, что ограничивает максимально возможный период последовательности величиной, не большей .

Пример 12.4.1. На рис. 12.16, a, представлена реализация генератора на основе регистра сдвига с линейной обратной связью, формирующего двоичную псевдослучайную последовательность периода . Отметим, что в случае двоичной ПСП умножение на единицу эквивалентно простому соединению выхода разряда с сумматором. Рис. 12.16, b, иллюстрирует следующие друг за другом содержания регистра (состояния разрядов), а также состояния выхода обратной связи (точка ОС на схеме) при подаче тактовых импульсов. Последовательность считывается в виде последовательных состояний крайнего
правого разряда. Считывание состояний других разрядов приводит к копиям той же самой последовательности, сдвинутой на один или два такта. ÿ

На первый взгляд можно предположить, что использование ПСП большого периода может обеспечить достаточно высокую защищенность. Так, например, в сотовой системе мобильной связи стандарта IS-95 в качестве скремблирующей используется ПСП периода в числе элементарных чипов. При чиповой скорости 1.2288×10⁶ симв/сек ее период составляет:

.

Следовательно, можно предполагать, что поскольку последовательность не повторяется в течение такого длительного периода, то она может рассматриваться случайной и обеспечивать совершенную секретность. Однако существует коренное отличие псевдослучайной последовательности от действительно случайной последовательности: псевдослучайная последовательность формируется согласно некоторому алгоритму. Таким образом, если известен алгоритм, то будет известна и сама последовательность. В результате этой особенности схема шифрования, использующая линейный регистр сдвига с обратной связью, оказывается уязвимой к атаке известного открытого текста.

Для определения отводов обратной связи, начального состояния регистра и всей последовательности криптоаналитику достаточно иметь всего бит открытого текста и соответствующий им шифрованный текст. Очевидно, что величина 2 n значительно меньше периода ПСП, равного . Проиллюстрируем упомянутую уязвимость на примере.

Пример 12.4.2. Пусть в качестве скремблирующей используется ПСП периода , генерируемая с помощью рекурсии вида

,

при начальном состоянии регистра 0001. В результате будет сформирована последовательность . Предположим, что криптоаналитику, которому ничего неизвестно о структуре обратной связи генератора ПСП, удалось получить бит криптограммы и ее открытого эквивалента:

 

Открытый текст:
Криптограмма:
Скремблирующая ПСП:

 

Тогда, сложив обе последовательности по модулю 2, криптоаналитик получает в свое распоряжение фрагмент скремблирующей последовательности, который показывает состояние регистра сдвига в различные моменты времени. Так, например, первые четыре бита ключевой последовательности отвечают состоянию регистра в некоторый момент времени . Если теперь сдвигать окно, выделяющее четверку битов на одну позицию вправо, то будут получены состояния регистра сдвига в последовательные моменты времени . Учитывая линейную структуру схемы обратной связи, можно записать, что

,

где символ ПСП, который вырабатывается схемой обратной связи и подается на вход первого разряда регистра, а определяет отсутствие или наличие i –го соединения между выходом разряда регистра сдвига и сумматором, т.е. схему обратной связи.

Анализируя состояния регистра сдвига в четыре последовательные момента времени можно составить следующую систему четырех уравнений с четырьмя неизвестными:

Решение данной системы уравнений дает следующие значения коэффициентов:

.

Таким образом, определив схему соединений обратной связи линейного регистра и зная его состояние в момент времени , криптоаналитик способен воспроизвести скремблирующую последовательность в произвольный момент времени, а значит, способен дешифровать перехваченную криптограмму. ð

Обобщив рассмотренный пример на случай произвольного регистра сдвига памяти n, исходное уравнение может быть представлено в виде

,

а система уравнений записана в следующей матричной форме ,

где , а .

Можно показать, что столбцы матрицы линейно независимы и, значит, существует обратная матрица . Следовательно

.

Обращение матрицы требует порядка операций, так что при имеем , что для компьютера со скоростью работы одна операция за 1мкс потребует 1 сек на обращение матрицы. Очевидно, что слабость регистра сдвига обусловлена линейностью обратной связи.

Чтобы затруднить аналитику вычисление элементов ПСП при сопоставлении фрагментов открытого текста и шифровки, применяется обратная связь по выходу и шифротексту. На рис. 12.17 поясняется принцип введения обратной связи по шифротексту.

Рис. 12.17. Поточное шифрование с обратной связью.

Сначала передается преамбула, в которой содержится информация о параметрах генерируемой ПСП, в том числе и о значении начальной фазы Z ₀₀. По каждым n сформированным символам шифрограммы вычисляется и устанавливается в генераторе новое значение фазы . Обратная связь делает метод гаммирования чувствительным к искажениям криптограммы. Так, из-за помех в канале связи могут исказиться некоторые принятые символы, что приведет к вычислению ошибочного значения фазы ПСП и затруднит дальнейшую расшифровку, но после получения n правильных символов шифрованного текста система восстанавливается. В то же время такое искажение можно объяснить попыткой злоумышленника навязать ложные данные.