01.10.2007 Многоалфавитная замена в шифре RC4

Наиболее общий способ описания используемых в криптографии преобразований потенциально бесконечных последовательностей M=M[i],i=0,1,... символов n-символьного алфавита, называемых в зависимости от контекста сообщениями, текстами или шифрограммами, основан на применении потенциально бесконечных последовательностей Tab=Tab[i][0..n-1],i=0,1,... таблиц перестановок (не обязательно различных) n символов алфавита, называемых также таблицами подстановок, или S-таблицами (Substitution).

Не ограничивая общности, можно считать символы n-символьного алфавита [0..n–1] цифрами 0..n–1, а любую конечную последовательность M=M[i],i=0,1,... таких цифр — позиционной записью неотрицательного целого числа M по основанию n.

Число перестановочных таблиц для n-символьного алфавита всегда конечно и равно n!=n*(n-1)*...*1. А вот последовательность Tab=Tab[i][0..n-1],i=0,1,... таких таблиц не обязательно должна быть конечной или иметь конечный период.

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

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

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

В то же время процедура зашифровывания совершенно не зависит от способа получения таблиц Tab=Tab[i][0..n-1],i=0,1,... и описывается как C=C[i],i=0,1,...=Tab[i][P[i]],i=0,1..., где С=C[i],i=0,1,... и P=P[i],i=0,1,... есть соответ-ственно зашифровываемое сообщение и результат шифрования, т.е. криптограмма.

Традиционно употребляющиеся для открытого сообщения и шифрограммы обозначения P и C происходят от английских слов Plain (ясный, открытый) и Cipher (цифра, зашифрованный).

Обратимость процедуры зашифровывания есть следствие обратимости таблиц перестановок. Таблица InvTab[i], обратная к Tab[i], i=0,1,... и называемая инверсной, определяется соотношением InvTab[i][Tab[i][j]]=j,j=0,1,...,n-1.

Легко видеть, что замена InvTab[i]<>Tab[i], i=0,1,... не изменяет вид соотношения, и значит, прямая таблица Tab[i] и ей инверсная InvTab[i],i=0,1,... являются взаимообратными.

В частности, инверсная таблица — это также перестановка, и совершенно безразлично, в каком порядке будут выполняться процедуры зашифровывания/расшифровывания при переводе открытого сообщения P в шифрограмму C.

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

Механический, а затем и электромеханический способ получения таблиц перестановок применялся в многочисленных шифраторах, последними из которых стали японский Purple (“Пурпур”) и немецкий Enigma (“Загадка”).

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

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

Как бы то ни было, известно, что шифраторы Enigma продолжали использоваться еще в 60-х годах прошлого века и, может быть, даже позднее, пока не были окончательно вытеснены электронными, применяемыми и сейчас. И это происходит независимо от того, что там вещают “компетентные” специалисты органов такого же профиля.

Последовательность Tab=Tab [i][0..n-1], i=0,1,... таблиц перестановок по официальной терминологии называется электронным шифроблокнотом, или ECB (Electronic Codebook). Тем же термином обозначается и соответствующий способ шифрования.

Если число n=2k символов в алфавите является точной степенью k>0 числа 2 и Г=Г[i],i=0,1,... — некоторая последовательность чисел Г[i],i=0,1,... такого алфавита, то при Tab[i][j]=j xor Г[i] всякая табличная подстановка C[i]=Tab[i][P[i]],i=0,1,... может быть дешевле и проще вычислена как C[i]=Г[i] xor P[i], i=0,1,... Обратимость последнего преобразования следует из обратимости операции xor (исключающее “ИЛИ”) сложения чисел по модулю 2. В частности, P[i]=Г[i] xor C[i], i=0,1,...

Используемая для шифрования последовательность чисел Г=Г[i],i=0,1,... носит название гаммы шифра. Каждое из значений Г[i],i=0,1,... принадлежит диапазону 0..n-1 и станет гаммой только при n, равном точной степени числа 2.

Ясно видно, что число различных значений гаммы совпадает с числом n символов алфавита и гораздо меньше возможного числа n!=n*(n–1)*...*1 перестановок. Например, для n=32 позиционная запись n! содержит 36 десятичных знаков.

Основанные на гамме шифры известны как шифры гаммирования. Способы получения гаммы по большей части остаются тайной, но известно, что использующие их шифры впервые были специально спроектированы для цифровых вычислителей и применялись еще во время Второй мировой войны. Правда, основой тех вычислителей были электромагнитные реле, хотя в усовершенствованных вычислителях Colossus (“Колосс”), построенных под руководством Алана Тьюринга для взлома шифров электромеханического шифратора Enigma, уже применялись тиратроны.

Официально шифры гаммирования называют шифрами с внешней обратной связью, или OFB (Output Feedback). К ним, в частности, относится шифр RC4, созданный Роном Ривестом — одним из разработчиков первой в мире системы шифрования RSA с открытым ключом. Кстати, RSA лежит в основе хорошо известной пользователям Интернета шифросистемы PGP Фила Циммермана, имевшего из-за нее столкновения с американским законом. Официально шифр RC4 никогда не публиковался. Сведения о нем впервые появились в Интернете. Предполагается, что анонимный автор восстановил алгоритм по кодам применяющих этот шифр приложений.

Основа RC4 — программно управляемый генератор гаммирующей последовательности “cлучайных” чисел из диапазона 0..255 с чудовищным периодом повторения 2562*256!=21700 (примерно). И при этом такой генератор вырабатывает только 256 различных значений. Для надежного шифрования степень “случайности” гаммы должна быть необычайно высока, но данные на сей счет отсутствуют. Во всяком случае предлагаемый далее режим использования данного шифра никак не может снизить его криптостойкости. Однако сначала рассмотрим сам
рекурсивный процесс порождения гаммы.

Вырабатываемая RC4 гамма определяется состоянием 256-байтовой таблицы Tab перестановок чисел 0..255 и двумя указателями P и Q к ней с нулевыми начальными значениями. Для получения очередного значения Г гаммы над таблицей Tab и указателями P и Q производятся такие действия.

1. Инкрементируется P =(P+1) mod 256;
2. Вычисляется Q =(Q+Tab[P]) mod 256;
3. Выполняется обмен Tab[P]<—>Tab[Q] элементов Tab[P] и Tab[Q] таблицы Tab с индексами P и Q;
4. Вычисляется Г = Tab[(Tab[P]+ Tab[Q]) mod 256].

Начальное заполнение таблицы Tab производится на этапе разворачивания ключа Key, содержащего от m=1 до m=256 произвольно выбранных символов Key[i], i=0..m-1. Разворачивание ключа предусматривает следующее.

1. Таблица Tab заполняется линейно Tab[i]=i, i=0..255;
2. Полагается j=0;
3. Для i от 0 до 255
   3.1. Вычисляется j=(j+Tab[i]+ Key[i mod m]) mod 256;
   3.2.В Tab переставляются элементы Tab[i]<—>Tab[j].

Как утверждается, примененный в шифре RC4 способ модификации таблицы обеспечивает все из 256! возможных перестановок чисел 0..255. Кроме того, сочетание различных значений указателей P и Q, используемых в RC4, дает еще 2562 различных вариантов.

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

В листинге 1 (см. приложение на диске, файл RC4.pas) представлен пример одной из возможных реализаций шифра RC4. Как следует из приведенного описания алгоритма RC4, таблица Tab представляет собой изменяющуюся на каждом шаге перестановку 256 чисел — 0..255. Иными словами, в процессе работы алгоритма сама собой возникает последовательность перестановочных таблиц
Tab=Tab[i][0..255],i=0,1,..., позволяющая использовать шифр RC4 в режиме электронного блокнота (ECB).

Такая реализация представлена в программе ECB.pas (см. приложение на диске). Главное ее отличие от предыдущей реализации состоит в применении инверсной таблицы InvTab, изменяемой синхронно с основной таблицей Tab шифра. Кроме того, вырабатываемое шифром RC4 “случайное” значение гаммы здесь не теряется, а служит дополнительным указателем к таблицам.

Полагаю, этого вполне достаточно для утверждения, что практическая стойкость шифра второй из программ не ниже, чем первой. А величины стойкости к взлому прямым перебором таблиц Tab и указателей к ним P и Q у программ, естественно, совпадают.