В январе 1955...⁠⁠

В январе 1955 года Джон Нэш, тогда ассистент-профессор MIT, отправил в Агентство национальной безопасности США серию рукописных писем с предложением новой машины шифрования. За устройством стоял математический вопрос, который оказался важнее судьбы самого проекта. Может ли сообщение быть лёгким для шифрования и чрезвычайно трудным для расшифровки без секретного ключа?

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

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

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

Эта оценка относится к конкретному предложенному шифру. Более широкая гипотеза о росте затрат на взлом тоже требует осторожности. Нэш выдвинул предположение об экспоненциальной трудности обнаружения ключа, а не доказал её. Его рассуждения не решили проблему P против NP, и предложенная машина не установила современную криптографическую безопасность.

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

#Криптография #ИсторияМатематики #ВычислительнаяСложность #ДжонНэш