Указание к работе

Лабораторная работа № 4

Поточные шифры. Моделирование работы

И 16-разрядного скремблера

Цель работы

Исследовать побитное непрерывное шифрование данных. Ознакомиться с кодированием информации при помощи скремблера.

Указание к работе

Шифр Вернама [4] можно считать исторически первым поточным шифром. Так как поточные шифры осуществляют поэлементное шифрование потока данных без задержки в криптосистеме, их важнейшим достоинством является высокая скорость преобразования, соизмеримая со скоростью поступления входной информации. Таким образом, обеспечивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока преобразуемых данных [10].

Поскольку каждый знак открытого текста в архитектуре поточного шифра не рассматривается как независимая единица, возникает вопрос о том, что будет происходить, если при передаче сообщения в него вкрадется ошибка. Будет ли она распространяться дальше и если да, то насколько далеко? Больше всего программистов может заинтересовать вопрос, будут ли все последующие символы расшифрованы правильно, если один из них был изменен в цепочке шифротекста [5].

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

В синхронных поточных шифрах (рис. 3.1) гамма формируется случайно, равновероятно и независимо от входной последовательности текста. Вследствие этого шифротекст не содержит информации об открытом тексте и криптосистема является совершенно криптостойкой (по Шеннону [3]).

Для обеспечения условия идеальной криптостойкости предполагается использование одноразовых ключей, длина которых совпадает с длиной обрабатываемых данных, что зачастую трудно осуществимо. На практике используется генератор псевдослучайных кодов, который обычно состоит из одного или нескольких генераторов рекуррентных последовательностей, начальные значения которых определяются ключом k [7].

Рис. 3.1. Шифрование информации методом гаммирования

(схема синхронного поточного шифра):

G – генератор псевдослучайных кодов; F – линейная или нелинейная

функция гаммирования; F ^–1 – функция, обратная F; g – гамма шифра

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

В самосинхронизирующихся поточных шифрах элементы входной последовательности зашифровываются с учетом N предшествующих элементов (рис. 3.2), которые принимают участие в формировании ключевой последовательности.

В самосинхронизирующихся шифрах имеет место эффект размножения ошибок, в то же время в отличие от синхронных восстановление синхронизации происходит автоматически через N элементов зашифрованной последовательности [10].

Скремблером называется программная или аппаратная реализация алгоритма, позволяющего шифровать побитно непрерывные потоки информации. Сам скремблер представляет собой набор бит, изменяющихся на каждом шаге по определенному алгоритму. После выполнения каждого очередного шага на его выходе появляется шифрующий бит – либо 0, либо 1, который на-

Рис. 3.2. Шифрование информации методом гаммирования

с обратной связью (схема самосинхронизирующегося

поточного шифра):

ГПК – генератор псевдослучайных кодов; Q – элементы памяти ГПК;

FB – функция обратной связи ГПК; F – линейная или нелинейная функция;

F ^–1 – функция, обратная F

кладывается на текущий бит информационного потока операцией XOR.

Суть скремблирования заключается в побитном изменении проходящего через систему потока данных. Практически единственной операцией, используемой в скремблерах, является XOR – «побитное исключающее ИЛИ». Параллельно прохождению информационного потока в скремблере по определенному правилу генерируется поток бит – кодирующий поток. Как прямое, так и обратное шифрование осуществляется наложением по XOR кодирующей последовательности на исходную [9].

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

Генерация кодирующей последовательности бит производится циклически из небольшого начального объема информации – ключа k (k ₀,..., k_N _–1). В очередном такте работы регистра значения, содержащиеся в ячейках его накопителя (k_i,..., k_i+N _–1, где ), умножаются на соответствующие значения скремблера (g ₀,..., g_N _–1) и суммируются, после чего происходит сдвиг информации (левый) в регистре, а в освободившийся крайний бит записывается вычисленное значение суммы. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом (рис. 3.4) [11].

Рис. 3.3. Схема линейного регистра сдвига

Исходный текст

Рис. 3.4. Шифрование текста с помощью полученного ключа

Из теории передачи данных криптография заимствовала для записи подобных схем двоичную систему записи. По ней изображенный на рис. 3.4 скремблер записывается комбинацией «10011₂» – единицы соответствуют разрядам, с которых снимаются биты для формирования обратной связи.

Рассмотрим пример кодирования информационной последовательности 010111₂ скремблером 101₂ с начальным ключом 110₂.

скремблер код.бит инф.бит рез-т 1 1 0 _ \ \ \_ 1 1 1 _ \_ \ \ \_ 0 XOR 0 = 0 0 1 1 _ \_ \ \ \_ 1 XOR 1 = 0 1 0 1 \_ \ \ 1 XOR 0 = 1и т.д.

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

1. Сбалансированность: для каждого интервала последовательности количество двоичных единиц должно отличаться от числа двоичных нулей не больше чем на один элемент.

2. Цикличность: циклом называют непрерывную последовательность одинаковых двоичных чисел. Появление иной двоичной цифры автоматически начинает новый цикл. Длина цикла равна количеству в нем одинаковых двоичных чисел. Необходимо, чтобы половина всех «полосок» (подряд идущих идентичных компонентов последовательности) имела длину 1, одна четвер-
тая – длину 2, одна восьмая – длину 3 и т.д.

3. Корреляция: если часть последовательности и ее циклично сдвинутая копия поэлементно сравниваются, желательно, чтобы число совпадений отличалось от числа несовпадений не более чем на 1.

Благодаря применению только операции XOR, декодирование заскремблированных последовательностей происходит по той же самой схеме, что и кодирование.

При достаточно долгой работе скремблера неизбежно возникает его зацикливание. По выполнении определенного числа тактов в ячейках скремблера создастся комбинация бит, которая в нем уже однажды оказывалась, и с этого момента кодирующая последовательность начнет циклически повторяться с фиксированным периодом. Данная проблема неустранима по своей природе, так как в N разрядах скремблера не может пребывать более 2 ^N комбинаций бит, и, следовательно, максимум, через 2 ^N – 1 циклов повтор комбинации обязательно произойдет. Последовательность бит, генерируемая таким скремблером, называется последовательностью наибольшей длины (ПНД).

Чтобы построить N -разрядный скремблер, создающий ПНД, пользуются неприводимыми многочленами [9] (такими, которых нельзя представить в виде произведения никаких других многочленов). Найденный неприводимый многочлен степени N записывается в двоичном виде, затем отбрасывается единица, соответствующая самому старшему разряду.

Для 8-разрядного скремблера можно привести такие примеры схем, которые позволяют сгенерировать ПНД: 10110001и 10111000, которым соответствуют простые неприводимые полиномы x ⁸ + x ⁶ + x ⁵ + x ¹и x ⁸ + x ⁶ + x ⁵ + x ⁴, соответственно. Период последовательности кодирующих бит в случае использования этих схем скремблирования равен максимуму – 255.

Работа скремблера осуществляется через операции сдвига (>> или <<) и сложения по модулю 2 (^).

Алгоритм генерации последовательности шифротекста при использовании 8- и 16-битовых ключей одинаков.

Приведем пример работы 8-разрядного скремблера, генерирующего последовательность с периодом равным T = 9 (рис. 3.5). Этот скремблер имеет вид «11111111». Начальный ключ имеет вид: «10000000». Последовательность генерируемых ключей имеет вид: