id: Гость   вход   регистрация
текущее время 07:09 11/08/2020
Владелец: unknown (создано 30/01/2012 15:19), редакция от 31/01/2012 15:39 (автор: unknown) Печать
Категории: криптография, разное, события, личности
https://www.pgpru.com/Новости/2012/АНБОпубликовалоШифрДжонаНэша
создать
просмотр
редакции
ссылки

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. Интересно, какой самый простой вид криптоанализа для неё возможен?


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


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


 
— SATtva (30/01/2012 16:58)   профиль/связь   <#>
комментариев: 11550   документов: 1036   редакций: 4094
АНБ утверждает, что никогда не использовало идей из этой схемы.

Разумеется, у нас нет оснований им не доверять.
— Гость (30/01/2012 20:10)   <#>
Шифртекст зависит не только от ключа, но и от внутреннего состояния, зависящего от всех предыдущих открытых текстов


Ребенок умер не родившись.. Обратная связь по открытому тексту – нехорошо, учитывая качество инфокоммуникационных систем того времени..
— Гость (31/01/2012 15:25)   <#>
решений по крайней мер в плане производительности.
— unknown (31/01/2012 15:45, исправлен 31/01/2012 15:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

fixed.


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


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

— Elis (31/01/2012 22:55)   профиль/связь   <#>
комментариев: 4   документов: 0   редакций: 0
Вопросы по п. 6: Судя по письму, начальное заполнение битами устройства P — это и есть ключ

Кажется, одно только начальное заполнение не может быть ключом – весь вход блока P известен, значит, известно движение бит в блоке P и то, какие биты ключа передаются на блок А (так по известному ОТ можно восстановить ключ). А когда неизвестные биты ключа в P закончатся, то сложение будет осуществляться с известным прежним выходом схемы.
— Elis (31/01/2012 23:08)   профиль/связь   <#>
комментариев: 4   документов: 0   редакций: 0
точно, там так и написано – "the key is the choice of the permutations", сорри
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3