id: Гость   вход   регистрация
текущее время 21:30 28/03/2024
Владелец: unknown редакция от 30/01/2012 16:48 (автор: unknown) Печать
Категории: криптография, разное, события, личности
https://www.pgpru.com/Новости/2012/АНБОпубликовалоШифрДжонаНэша
создать
просмотр
редакции
ссылки

Это старая редакция страницы Новости / 2012 / А Н Б Опубликовало Шифр Джона Нэша за 30/01/2012 16:48.


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


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


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


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


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


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


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


Cipher (57 Кб)


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


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

P - bit permutator (193 Кб)
Bit operations (103 Кб)


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


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


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


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


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


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


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