Агентство национальной безопасности США рассекретило изумительные письма, которое знаменитый математик Джон Нэш отправил им в 1955 году.
Джон Нэш предложил для тех времён совершенно революционную идею: использовать в криптографии теорию сложности вычислений. Если прочитать это письмо, то вызывает восхищение, насколько пророческим оказался анализ Нэша о вычислительной сложности и криптостойкости. Именно на этих принципах основана современная криптография. Первая работа в этой области была опубликована только в 1975 году.Отсканированные копии рукописных писем Джона Нэша
В своё время власти так и не проявили интереса к работе чудаковатого профессора математики. Или, что тоже возможно, использовали идеи Нэша втайне от него.
В своём письме Джон Нэш развивает идеи теории связи в секретных системах Клода Шэннона (1949), не упоминая её, но идёт значительно дальше. Он предлагает основать безопасность криптосистем на вычислительной сложности — в точности на том принципе, который в 1975 году спустя два десятилетия лёг в основы современной криптографии. Далее Нэш чётко описывает различие между полиномиальным временем и экспоненциальным временем, что является базисом теории вычислительной сложности. Этот принцип первые описан в 1965 году, хотя о нем речь идёт в знаменитом письме Гёделя к фон Нейману от 1956 года, но не применительно к криптографии.
Джон Нэш:
«Так что логичным способом классифицировать процессы шифрования будет по способу, которым сложность вычисления ключа возрастает с увеличением длины ключа. Он в лучшем случае экспоненциальный, а в худшем, вероятно, как минимум относительно небольшая степень ar2 или ar3, в шифрах подстановки».
В другом месте он, судя по всему, говорит об односторонней функции, хотя таких терминов, конечно, тогда ещё не было:
«Моя общая гипотеза выглядит следующим образом: почти для всех достаточно сложных типов шифрования, особенно там, где действуют инструкции, данные различными частями ключа, на взаимодействие комплексных чисел друг с другом в определении их влияния на конечный итоге шифрования, средняя сложность вычисления ключа растёт экспоненциально с длиной ключа».
Математик хорошо понимает важность своей гипотезы для практической криптографии, потому что использование новых методов положит конец извечной «игре» шифровальщиков и взломщиков кода.
«Важность этой общей гипотезы, если предположить её истинность, легко видна. Она значит, что вполне вероятным становится создание шифров, которые будут фактически невзламываемыми. По мере увеличения сложности шифра игра по взлому шифров между умелыми командами и др., станет достоянием истории».
Собственно, так оно и произошло.
Интересно также, что Джон Нэш открыто говорит об использовании методов, теоретический базис которых он не может доказать (P = NP). Более того, он прямо говорит в письме, что «не ожидает его доказательства», что необычно для математика.
Лауреат Нобелевской премии 1994 года Джон Нэш известен широкой публике по биографическому фильму «Игры разума».
P.S. Профессор по компьютерным наукам, американский криптограф Рональд Ривест сделал криптосистему Нэша на Python.
via Turing’s Invisible Hand
