Тема 5. Поточные шифры

5.1. Принципы построения поточных шифрсистем

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

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

Пусть А – алфавит открытых сообщений, совпадающий с множествами шифрвеличин и шифробозначений, {_а : АА} – совокупность из r биекций множества А, х=а₁,а₂…,а_l – произвольный открытый текст, kK – выбранный ключ зашифрования. Пусть

(k,l)=а₁^(k)...а_l^(k), (a_j^(k)N_r, j=1,…,l) (5.1)

является распределителем, отвечающим данным значениям kK, lN , где  : К  N —> N_r. — некоторое отображение в множество N_r = {1,2,. ..,r} . Тогда правило зашифрования определяется формулой Е_k(х)=у, где y=b₁b₂ …b_l и (5.2)

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

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

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

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

Достаточно, чтобы в каждом такте шифрующий блок обеспечивал возможность зашифрования лишь текущего знака a_j открытого текста в соответствии с (5.2). При этом совсем не обязательно строить целиком подстановочное преобразование a_j^(k) на всем алфавите А.

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

x(i +m)=f(х((i),..., x(i + т -1)), i > 0,

в которой f : А ^m —> А – некоторая функция от т переменных.

Для получения рекуррентных последовательностей используются различные датчики псевдослучайных чисел. Наиболее известным таким датчиком с хорошо изученными свойствами является линейный конгруэнтный генератор над конечным кольцом или полем. Закон его функционирования представляется в виде

х(i +1) = а • х(i) +b, i > 0.

Обобщением линейного конгруэнтного генератора являются конгруэнтные генераторы, определяемые формулой вида

x(i+1)=f(x(i)), i > 0, (5.3)

в которой f : A —> A – произвольное отображение, легко вычисляемое для любого аргумента. Достаточно полно исследованы свойства таких генераторов, задаваемых полиномиальными преобразованиями f .

Изучались также генераторы, определяемые неполиномиальной рекуррентной зависимостью. Примером является целочисленный генератор, основанный на ''методе середины квадратов", для которого вычисление х(i+1) с помощью (3) сводится к отбрасыванию определенного числа знаков из десятичной (или двоичной) записи числа х(i)².

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

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

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

Если множество шифрующих преобразований {_а} достаточно велико, то можно обеспечить стойкость шифрования даже при повторном использовании ключей. Для этого достаточно, чтобы в множестве {_а} содержались npeo6paзования, переводящие любую пару букв открытого текста в любую пару букв шифрованного текста. Тогда по паре текстов, зашифрованных на одном и том же ключе, нельзя получить информацию об открытых текстах, поскольку любой паре букв шифртекстов может соответствовать произвольная пара букв открытых текстов.

Следует отметить, что указанные качества шифрующего блока повышают криптографическую стойкость, но достигаются за счет избыточности числа простых замен, составляющих данный шифр замены. Действительно, если исключить возможность повторного использования ключей и обеспечить необходимые свойства управляющей последовательности, то можно ограничиться множеством из А подстановок {_а}, нижние строки которых образуют латинский квадрат. В этом случае мы приходим к введенному ранее шифру табличного гаммирования.

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

Требования к управляющему блоку:

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

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

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

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

Требование к шифрующему блоку:

– применение алгоритма шифрования должно носить универсальный характер и не зависеть от вида шифруемой информации.

Иногда выдвигается дополнительное требование:

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

Заметим, что выполнение перечисленных требований является необходимым, но не достаточным условием криптографической стойкости поточного шифра.