30.01 // АНБ опубликовало шифр Джона Нэша

Агентство Национальной Безопасности США рассекретило переписку с математиком Джоном Нэшем (который стал широко известен за пределами своей области деятельности после выхода фильма "Игры разума").

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

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

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

Конкретные причины отказа его рассмотрения являлись секретными (возможно предположить, что АНБ не хотело разглашать ни своих методов криптоанализа, ни способствовать правильным догадкам о методах создании стойких шифров). Интерес ведомства вызвала и теория игр Джона Нэша, которая впоследствии и принесла ему известность и Нобелевскую премию по экономическим наукам.

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

Идеи Нэша сводятся примерно к таким пунктам:

1. Шифр работает с двоичным представлением информации (в современной терминологии в виде битов).
2. Шифртекст зависит не только от ключа, но и от внутреннего состояния, зависящего от всех предыдущих открытых текстов: Y_i = F (α₁, α₂, … α_r; X_i, X_i-1, X_i-2, … X_i-n). Для этого копии битов шифртекста подаются обратно на циклическую обработку алгоритмом.
3. Ввод открытого текста и вывод шифртекста (шифрование/расшифрование) осуществляются побитово (один бит за один цикл).
4. Ввод открытого текста осуществляется сложением по модулю два в устройстве A (в современной терминологии XOR).
5. В зависимости от того, какой бит находится в текущем потоке, устройство D выбирает путь перестановки в устройстве P.
6. Основу алгоритма составлет перестановщик P. Устройство P меняет текущий бит в зависимости от состояния битов по пути перестановки. При этом пути могут быть, как неизменяющие бит, так и инвертирующие его. Количество ключей зависит от количества точек в устройсте (не считая первой, которая не даёт выбора) и составляет [ n! 2ⁿ⁺¹ ]².
7. Расшифрование происходит аналогично, только добавляется устройство R для задержки одного цикла.

Некоторые моменты могут вызвать не вполне однозначное толкование.

Вопросы по п. 6: Судя по письму, начальное заполнение битами устройства P — это и есть ключ. Или этим можно считать характер связей-переходов между точками хранения битов в P? Можно однако считать, что имеют право на одновременое сосуществование оба варианта (хотя правила перестановок должны представлять собой сбалансированную функцию — это скорее вариант долговременной секретной таблицы). Не очень понятно, как при прохождении бита меняются эти биты в перестановщике P. В соответствии с правилом прохождения, взаимно? Т.е. и проходящий бит и те, через которые он проходит. Инвертируются (или в зависимости от сочетания не изменяются) и всегда замещаются? Или замещаются только когда инвертируются? Одна из красных стрелок не помечена знаком "+" или "-" — означает ли это что-нибудь?

Вопросы по п. 7: почему задерживающее устройство R помещено в расшифровывающую часть схемы, а не наоборот — в зашифровывающую? Можно было бы пропустить один бит открытого текста через D-P, а затем его уже поксорить снова с открытым текстом в A и только после этого выпустить. Иначе непонятно XOR чего с чем производится в начальном цикле, в то время как для дешифрования эта задержка вроде как не нужна?

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

Сама по себе схема предельно простая и вместо внесения дополнительных усложнений Нэш предлагал увеличивать размер P. Интересно, какой самый простой вид криптоанализа для неё возможен?

АНБ утверждает, что никогда не использовало идей из этой схемы. А если в этой схеме заменить битовые операции на байтовые? Возможно ли было бы получить что-то близкое к современным шифрам?

Источник: Агентство Национальной Безопасности США — Центр по связям с прессой / Национальный музей криптологии