Письмо Джона Нэша в АНБ от 1955 года

    Агентство национальной безопасности США рассекретило изумительные письма, которые знаменитый математик Джон Нэш отправил им в 1955 году.

    Джон Нэш предложил для тех времён совершенно революционную идею: использовать в криптографии теорию сложности вычислений. Если прочитать письмо от 18 января 1955 года, то вызывает восхищение, насколько пророческим оказался анализ Нэша о вычислительной сложности и криптостойкости. Именно на этих принципах основана современная криптография. Первая работа в этой области была опубликована только в 1975 году.

    Отсканированные копии рукописных писем Джона Нэша

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

    В своём письме Джон Нэш развивает идеи теории связи в секретных системах Клода Шэннона (1949), не упоминая её, но идёт значительно дальше. Он предлагает основать безопасность криптосистем на вычислительной сложности — в точности на том принципе, который в 1975 году спустя два десятилетия лёг в основы современной криптографии. Далее Нэш чётко описывает различие между полиномиальным временем и экспоненциальным временем, что является базисом теории вычислительной сложности. Этот принцип первые описан в 1965 году, хотя о нем речь идёт в знаменитом письме Гёделя к фон Нейману от 1956 года, но не применительно к криптографии.

    Джон Нэш:

    «Так что логичным способом классифицировать процессы шифрования будет по способу, которым сложность вычисления ключа возрастает с увеличением длины ключа. Он в лучшем случае экспоненциальный, а в худшем, вероятно, как минимум относительно небольшая степень ar2 или ar3, в шифрах подстановки».

    В другом месте он, судя по всему, говорит об односторонней функции, хотя таких терминов, конечно, тогда ещё не было:

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

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

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

    Собственно, так оно и произошло.

    Интересно также, что Джон Нэш открыто говорит об использовании методов, теоретический базис которых он не может доказать (P = NP). Более того, он прямо говорит в письме, что «не ожидает его доказательства», что необычно для математика.

    Лауреат Нобелевской премии 1994 года Джон Нэш известен широкой публике по биографическому фильму «Игры разума».

    P.S. Профессор по компьютерным наукам, американский криптограф Рональд Ривест сделал криптосистему Нэша на Python.

    via Turing’s Invisible Hand
    Поделиться публикацией
    Комментарии 43
      +3
      > Или, что тоже возможно, использовали идеи Нэша втайне от него.
      Обычно в таких случаях с автором «связываются и просят» не афишировать идею метода.
        +1
        Если сложность процесса расшифровки зависит от длины ключа, а не знания метода, то смысл? Разве что только чтобы у конкурентов такого метода пока не было.
          +2
          Именно. Так как если этим будут пользоваться и конкуренты, то это усложнит работу АНБ.
            0
            И АНБ США, и вообще все спецслужбы серьезных государств достаточно нервно реагируют на работы по криптографии не под крышей государственных структур.
          0
          Или «связываются и убивают».
            0
            Ну, в этом не было необходимости. Нэш в письме сам пишет, что, так как США не выгодно, чтобы другие страны использовали потенциально невзламываемые шифры, то нужно изучать эту область, но держать все в секрете.
              0
              В 1954 году Джона Нэша выгнали из RAND и скомпрометировали на прощание участием в «гомосексуальном эпизоде». Чуть позже началась история с шизофренией, так что всерьёз человека перестали воспринимать. Да и вообще, как Вы думаете, сколько людей в мире могут адекватно воспринимать тексты Нэша, а в 54 году?

              RAND — это корпорация, которая занимается вопросами национальной безопасности на неофициальном уровне. Так что в 1955 году он уже был под плотной внешней опёкой, потерял все допуски и АНБ перестало с ним держать контакты. Он был явно «неуправляемым». Судя по всему стал разглашать информацию, к которой его допустили в RAND.

              –36
              > Джон Нэш известен широкой публике по биографическому фильму «Игры разума».

              А мне казалось, что за вклад в теорию игр. Фильм мало кто даже из знакомых смотрел, но Нэша знают почти все.
                +76
                Какой тонкий намёк на собственную элитарность.
                  –32
                  Скорее, на копипаст автора из википедии.
                    +62
                    Да я про ваш комментарий. Очевидно же, что о фильме знает большее количество людей чем о теории игр.
                      –38
                      Дык мне очевидно как раз обратное, потому и написал.
                        +25
                        Фильм входит в топ 250 imdb и кинопоиска, это не спроста))
                          +2
                          imdb?
                            +4
                            без айрони нельзя такое писать на хабр
                            +3
                            Фильм?
                        +1
                        Я вот о фильме не знал, о Нэше тоже (ну, то есть слышал краем уха что-то где-то, что к ИТ он отношение имеет), а вот о теории игр слышал и даже поверхностно изучал. Пошел фильм качать.
                          +9
                          Фильм прекрасный.
                          Пожалуй лучший из тех, что я смотрел за всю жизнь.
                          Кстати, Нэш жив до сих пор.
                            +4
                            Смотрел фильм, знал про Нэша из теории игр, но эти два факта не были как-то связаны. Не знал что он жив.
                              0
                              Странно, а я его знал из рестлинга… новый мировой порядок и все такое.
                              0
                              Книга Сильвии Назар (по которой фильм сняли) кстати тоже очень даже ничего. Журналистка вообще неплохо пишет, у нее и про Перельмана есть крупная статья.
                              0
                              В фильме об этом не говорится, но: Нэш получил премию по экономике, так как за вклад в математику нобелевку не дают. Теория игр применяется в бизнесе. Её основной цинус в том, что в «игре» нет проигравших, т.е. конкурент не проигрывает, но сотрудничает.
                              –5
                              А я соглашусь с Boba Fett. Думаю на этом ресурсе о теории игр в той или иной степени известно почти всем, хотя и фильм великолепный и о нем тоже много кому известно.
                              В то же время для многих личностей нынешнего поколения этот фильм может быть неизвестен, т.к. для них он будет ни о чем или как минимум скучным
                                +8
                                «Известно почти всем» — это такое глупое заблуждение, если честно. Применительно к чему угодно, а не только к вопросу этого топика.
                                У Хабра очень разношерстная аудитория — и далеко не все знакомы с теорией игр, а даже и те кто знаком, не всегда помнят важные имена.
                                  +2
                                  Вы меня простите, но равновесие нэша в теории игр это самая элементарная еденица знания. Проще нее в теории игр нет ничего. Тоесть, если кто-то знает про теорию игр больше чем просто название «теория игр», то он знаком с нэшем.
                                  –7
                                  На этом ресурсе Мицгол — один из топовых людей по карме. Это хорошо показывает, что инакомыслящих гнобят и иные точки зрения тут не приемлют. Что доказывают минуса к комментариям выше. Да и к этому тоже.
                              +4
                              Бросьте. Это полезный обществу снобизм.
                              А с другой стороны, действительно есть группы людей которым имя учёного ближе чем фильм.
                                +2
                                Вы чего на человека набросились? Ну не смотрел он этого фильма, и знакомые его не смотрели. Вот и все что он хотел написать. И даже если считать его комментарий бессмысленным, то ваш выглядит не менее глупо.

                                И вообще, это еще не известно, кто тут заяц хваста.
                                  +1
                                  Я действительно впервые о Джоне Нэше услышал на курсе по теории игр в институте почти 10 лет назад.
                                    0
                                    Ну фильм вышел в 2001 году, как раз лет десять назад. Поэтому неудивительно, что вы в частности узнали о Нэше не из фильма. Я сначала посмотрел фильм, а только через несколько лет в курсе тигров узнал что же это такое, равновесие по Нэшу.
                                    Речь ведь идет о том, что большинство (вне хабра, по крайней мере) видели фильм, но никогда не изучали теорию игр.
                                  +14
                                  Не повод для гордости, ибо фильм на самом деле отличный.
                                    0
                                    Никакой гордости. Фильм как раз после этой новости и собрался посмотреть.
                                      +7
                                      Да, фильм классный. Наверно, самая лучшая работа Рассела Кроу.
                                        0
                                        Мне кажется, эта работа у него конкурирует с ролью в фильме «Хороший год». Но там про высококачественное бухло и про любовь.
                                    +4
                                    на взаимодействие комплексных чисел друг с другом

                                    В оригинале, конечно, ни о каких комплексных числах речи нет. Сказано о сложном взаимодействии инструкций (вычислений), производимых над разными частями ключа.
                                      0
                                      Прошу прощения, исправляю…
                                      +1
                                      Это в очередной раз доказывает, что знания и технологии становятся достоянием общественности, только после того, как военные выжали из них все что смогли.
                                        0
                                        Какое совпадение! Утром ехал в электричке, смотрел «Игры разума», зашел на хабр, а тут статья.
                                          0
                                          Гм. Если я не ошибаюсь, современные методы шифрования с открытым ключом, к сожалению, не основаны на NP-трудных задачах. Пока что подходящей схемы, основывающейся на P ≠ NP не придумали.
                                            0
                                            Насколько я понимаю, принадлежность задачи факторизации натуральных чисел на простые множители к NP-трудным задачам — вопрос открытый. В RSA именно факторизация используется. Мне гражданин Циммерманн (который PGP разработал) на вопрос об этой проблеме ответил, что вместо того, чтобы тратить силы на математические доказательства, криптографы поощряют всех желающих заниматься атакой на конкретные алгоритмы. Устанавливаются серьезные премии, проводятся конкурсы. И если даже представители академических кругов не могут в течение десятилетий пошатнуть надежность конкретного алгоритма, то этот алгоритм начинают использовать в практических приложениях.
                                            Ведь не происходит такого, чтобы вчера алгоритм был полностью надежным, а сегодня все уже читали шифрованные при его помощи сообщения. Сначала выдвигаются математические теории, которые утверждают снижение надежности алгоритмов, затем на их основе разрабатываются конкретные методы. Проходят годы, прежде чем появляется реальная угроза.
                                              0
                                              Проблема в том, что если кто-то внезапно придумает логарифмический (полиномиальный от длины записи) алгоритм для факторизации, то RSA сломается _внезапно_. Десятки лет попыток сломать не помогут. Не скажу, что такая ситуация часта, но в истории математики случалось, что та или иная проблема долгое время была открытой, а потом (относительно) внезапно решалась. Теоретически то же может произойти и с факторизацией.

                                              После появления алгоритма возникновение реальной угрозы — вопрос дней и недель, пока люди напишут реализацию.

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

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

                                          Самое читаемое