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 и только после этого выпустить. Иначе непонятно ксор чего с чем производится в начальном цикле, в то время как для дешифрования эта задержка вроде как не нужна?

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

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

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

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