Свойства RC4

[Magazanik]

Отделено от Сложность по Арнольду.

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

Насколько я могу судить, это имеет отношение к данной теме (пояснение задним числом -- раньше этот пост продолжал тему Сложность по Арнольду), потому что программу можно рассматривать как генератор, порождающий длинные (неповторяющиеся) цепочки нулей и единиц, а ужас вызывает совершенно немыслимое сочетание простоты и сложности устройства этого генератора.

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

Сначала о простоте, потом о сложности.

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

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

То есть все в одном флакончике, выпивка и закуска, объекты и операции, а заодно изменения правил операций — таблица умножения переписывает сама себя, через 256 шагов алгоритма в ней уже ни один байт не остается на месте, теперь и операнды, взятые с $i$-той и $j$-той позиций уже другие, и результат действий над ними другой, потому что в таблице умножения вместо строки $a (+) b = c $ стоит строка $a (+) b = d$. Однако смена одной алгебры другой здесь ползучая, с полной достоверностью она влияет на вычисление далекого байта, отстоящего в выходной последовательности на $256 $ мест вправо, а на вычисление ближайшего байта влияет только с вероятностью $1/256$, потому что на каждом шагу итерации только$ 1/256$ часть ячеек таблицы умножения (таблицы Кэли) меняет свое содержимое. Время в алгоритме дискретно, в каждый момент времени действительна какая-то алгебра, только во всякий момент немножко другая.

Что это такое? Как это описывается?
Жуткая выдумка, это понятно, но какая-то теория должна быть и у нее. Как она должна выглядеть — хорошая математическая теория для этой процедуры и ее результатов? Какая ее сложность по Колмогорову, какая по Арнольду, а какая по другим известным критериям?

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

Из общих соображений видно, что выходная последовательность этой штуковины где-то должна иметь период — все же ее число состояний конечно. Но какой период, насколько он велик? Загадка. Также из общих соображений следует, что распределение символов выходного потока описывается довольно просто — этот статистика монеты, любой бит с равной вероятностью будет нулем или единицей. Практика это подтверждает (почти в точности, с некоторыми поправками для начальных байтов), но как в таких случаях принято рассуждать о сложности — этот вопрос тоже превышает мое разумение.

Да, пора наконец сказать, о каком алгоритме идет речь.
Это известный шифр RC4, многие годы он был благодаря простоте реализации и скорости как бы неофициальным стандартом в классе поточных (stream), его автор Ривест, большой человек в мировой криптографии, один из соавторов популярной системы RSA. Какую теорию он сам предложил, когда патентовал RC4, можно только гадать, потому что алгоритм был заявлен как коммерческая тайна, его описание появилось только лет через семь — и то незаконно, хакеры декомпилировали программу, выдали в свет реконструкцию алгоритма. А может, и у Ривеста не было никакой теории? Принято ли это вообще — обязательно представлять теорию при патентовании прикладных программ, или можно обойтись так?

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

(Оффтоп)

Об умножении в квазигруппе. Простейшая операция $ADD$ — сложение беззнаковых восьмиразрядных целых по модулю $256$, которую исполняет любой процессор, образует конечную группу порядка $256;$ таблицу умножения этой группы можно записать в виде квадратной матрицы $256*256$, каждая строка и каждый столбец этой матрицы будет перестановкой, и это свойство не изменится при умножении каждой строки на какую-то произвольную перестановку $A $— это по-прежнему будет латинский квадрат или таблица Кэли, только теперь это таблица умножения уже не группы, а квазигруппы: единицы нет, обратного элемента нет, ассоциативности нет, остается только единственность решения для каждого уравнения в этой алгебре. Разумеется, для программной реализации нет надобности строить эту таблицу целиком в явном виде, одна операция умножения в квазигруппе исполняется программой как последовательность двух операций — сначала сложение двух байтов, которое без всякой таблицы умеет выполнять процессор, затем замена суммы по таблице, которой является та самая произвольная перестановка: $i = A[i]$. То есть заданная тривиальным сложением матрица $256*256$ как бы скрыта, это предопределенный субстрат для множества различных квазигрупп, а фактически таблицей умножения для каждого случая является единственная строка $A $— произвольная перестановка.

Об алгоритме RC4 и его программной реализации. Реализация — всего десять строк на языке Си, но приводить этот код здесь не решаюсь, боюсь, что это нарушит права автора. Конечно, алгоритм взят из открытого источника, он есть где угодно, например, в Википедии, но его никогда не публиковал сам автор, поэтому законность любой публикации сомнительна.

С уважением,
Лев Магазаник