Лабораторная работа 3

Тема: поточные шифры.

Шифр Вернама. Моделирование работы разрядного скремблера.

Простейшей и в то же время наиболее надежной из всех схем шифрования является так называемая схема однократного гаммирования, изобретение, которое чаще всего связывают с именем Г.С. Вернама.

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

В данной лабораторной работе алфавитом A, в котором записываются открытые и шифрованные тексты, является поле Z₂, то есть открытые и шифрованные тексты рассматриваются как двоичные последовательности. В этом случае "наложение" гаммы - не что иное, как выполнение операции сложения Å по модулю 2 (xor), которая, например, в языке программирования Си обозначается знаком ^.

Стандартные операции над битами: 0 Å 0 = 0, 0 Å 1 = 1, 1 Å 0 = 1, 1 Å 1= 0.

Скремблером называется программная или аппаратная реализация алгоритма, позволяющего шифровать побитно непрерывные потоки информации.

Рассмотрим сдвиговый регистр с обратной связью (Linear Feedback Shift Register, сокращенно LFSR) – логическое устройство, схема которого изобра­жена на рис. 3.1.

Сдвиговый регистр представляет собой последовательность битов. (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n -битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит.

Рис. 3.1. Схема LFSR

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

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

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

Приведем пример 7 разрядного скремблера, генерирующего последовательность с периодом равным : . Начальное значение (начальный ключ) возьмем равным . Для этого сдвигового регистра новый бит генерируется с помощью XOR седьмого и третьего битов (см. рис 3.2).

Рис. 3.2. Схема LFSR для многочлена , начальное состояние .