Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 21)
Харди писал в то время, когда типичный кембриджский «дон» (преподаватель) тратил около четырех часов в день на научные изыскания и, может быть, часок на работу со студентами, а остальное время отдыхал, заряжая свои интеллектуальные батарейки. Он смотрел крикет и читал газеты. Ему, по всей видимости, просто не приходило в голову, что даже ведущий математик-исследователь мог бы использовать свободное время с пользой и рассказывать неспециалистам, чем в настоящее время занимаются математики. Это позволило бы творить новую математику и параллельно писать о ней. Именно этим многие из нас, профессиональных математиков, занимаются сегодня.
Общее утверждение Харди о том, что значительная доля чистой математики не имеет практического применения и, вероятно, никогда не найдет его, остается верным{40}. Но вот при выборе конкретных примеров бесполезных тем он сильно рисковал попасть впросак. Сказав, что теория чисел и теория относительности еще много лет не смогут послужить никакой военной цели, он, что называется, попал пальцем в небо, хотя нужно признать, что его предсказание не исключало подобное применение полностью. Очень трудно решить заранее, какие идеи найдут применение, а какие нет. Научитесь делать это, и вы сможете без труда разбогатеть. Интересно, что именно те области, которые не кажутся практически применимыми, могут внезапно выскочить на передний план в промышленности, коммерции и, к несчастью, в военном деле. Именно это произошло с теорией чисел и конкретно с Малой теоремой Ферма, которая теперь стала основой того, что мы считаем абсолютно стойкими шифрами.
Ирония ситуации в том, что за два года до того, как Харди написал свою «Апологию…», глава британской контрразведки MI6 купил поместье Блетчли-парк, в котором в будущем должна была разместиться Правительственная школа кодирования и шифрования, секретный дешифровальный центр cоюзников во время Второй мировой войны. Там, как известно, криптоаналитики взломали шифр машины Enigma, которую Германия использовала в военных целях, и ряд других шифровальных систем стран Оси. Самый известный сотрудник Блетчли-парка Алан Тьюринг начал обучение в 1938 году и прибыл в школу в день объявления войны. Криптоаналитики Блетчли-парка использовали для взлома германских шифров неординарные подходы и математику, в том числе и идеи из теории чисел. Всего лишь через неполные 40 лет после этого произошла настоящая революция в криптографии, фундаментом которой стала теория чисел. Естественно, для новой криптографии нашлось не только гражданское, но и военное применение. Вскоре она приобрела принципиально важное значение для работы интернета. Сегодня мы сильно зависим от нее, по большей части даже не сознавая, что она существует.
Теория относительности тоже нашла свое место не только в гражданской, но и в военной сфере. Можно сказать, что она сыграла определенную роль в реализации Манхэттенского проекта по созданию атомной бомбы. В соответствии с популярной легендой, знаменитая формула Эйнштейна
Счет 2:0 в пользу военных.
Я совершенно не виню Харди. Он понятия не имел, что происходит в Блетчли-парке, и едва ли мог предугадать стремительный взлет цифровых вычислений и средств связи. Слово «цифровой» означает в основном работу с целыми числами, а ведь именно этим занимается теория чисел. Внезапно оказалось, что результаты, полученные многими поколениями специалистов по чистой математике исключительно из интеллектуального любопытства, теперь можно использовать для инновационной технологии. Сегодня в электронных устройствах, которые четверть рода человеческого ежедневно носит с собой, воплощен огромный пласт математики – и это не только теория чисел, но и многое другое, от комбинаторики до абстрактной алгебры и функционального анализа. Секретность онлайн-операций, осуществляемых частными лицами, компаниями, а также военными, обеспечивается хитроумными математическими преобразованиями, основанными на столь любимой Харди теории чисел. Это совсем не удивило бы Тьюринга, который был настолько впереди всех, что уже в 1950 году всерьез задумывался об искусственном интеллекте. Но Тьюринг был мечтателем. В те времена это было даже не научной фантастикой, а просто фантазией.
Код, или шифр, – это метод преобразования сообщения на обычном языке, то есть открытого текста, в зашифрованный текст, который выглядит как тарабарщина. При этом преобразовании, как правило, используется ключ – принципиально важная часть информации, которую держат в секрете. Говорят, например, что Юлий Цезарь пользовался шифром, в котором каждая буква алфавита сдвигалась на три позиции. «Три» здесь и есть ключ. Такой тип шифра подстановки, в котором каждая буква алфавита заменяется на другую букву по постоянному правилу, несложно взломать, если в вашем распоряжении имеется достаточное количество шифровок. Для этого достаточно знать частоты, с которыми буквы алфавита встречаются в открытом тексте. Тогда можно сделать достаточно достоверное предположение о принципе шифрования и проверить его. Поначалу будут встречаться ошибки, но если часть текста вдруг расшифруется как JULFUS CAESAR, то легко догадаться, что на месте F должна быть I.
Каким бы простым и ненадежным ни казался шифр Цезаря, он служит хорошим примером для иллюстрации общего принципа, который до недавнего времени лежал в основе практически всех систем шифрования. Это симметричный шифр, то есть и отправитель, и получатель пользуются, по существу, одним и тем же ключом. Я говорю «по существу», потому что они пользуются им по-разному: Юлий сдвигает алфавит на три позиции вправо, а получатель сдвигает его на три позиции в обратном направлении. Однако если вы знаете, как ключ используется при шифровании, то легко можете обратить процесс вспять и использовать тот же ключ для расшифровки. Даже весьма хитроумные и надежные шифры симметричны. Поэтому безопасность требует, чтобы используемый ключ держался в секрете от всех, за исключением отправителя и получателя сообщений.
Как сказал Бенджамин Франклин, «трое могут сохранить секрет, если двое из них мертвы». В симметричном шифре ключ должны знать как минимум двое, что, по мнению Франклина, слишком много. В 1944 или 1945 году кто-то (возможно, Клод Шеннон, изобретатель теории информации) в исследовательском центре Bell Labs в США предложил защищать голосовую связь от подслушивания при помощи добавления к сигналу случайного шума, а затем, после получения сигнала, его вычитания. Это тоже симметричный метод, поскольку ключ здесь – случайный шум и вычитание компенсирует его добавление. В 1970 году Джеймс Эллис, инженер Центра правительственной связи Великобритании, бывшей Правительственной школы кодирования и шифрования, заинтересовался, нельзя ли генерировать шум математически. Если да, то в принципе можно создать систему, где это будет результатом не простого добавления сигналов, а математического процесса, который очень трудно обратить, даже если знать, что он собой представляет. Конечно, получатель должен иметь возможность обратить процесс, но этого можно добиться с помощью
Эллис назвал свою идею «несекретным шифрованием». Сегодня используют термин «криптосистема с открытым ключом». Обе эти фразы означают, что правило для шифрования сообщения можно свободно опубликовать в общедоступных источниках, но без знания второго ключа никто не сможет понять, как обратить эту процедуру и расшифровать сообщение. Оставалась единственная проблема: Эллис не смог разработать подходящий метод шифрования. Он хотел получить то, что сегодня называется функцией с потайным входом: легко вычислить, но трудно обратить (в потайной вход легко провалиться, но трудно выбраться). Как всегда, здесь должен иметься секретный второй ключ, позволяющий законному получателю обратить процесс так же легко, как спрятанная лестница позволяет провалившемуся выбраться.
И тут на сцену выходит Клиффорд Кокс, британский математик, также работавший в Центре правительственной связи. В сентябре 1973 года Кокса неожиданно осенила блестящая идея. Он понял, что мечту Эллиса можно реализовать, создав функцию с потайным входом при помощи простых чисел. С точки зрения математики перемножить два или более простых числа легко. Можно, например, вручную перемножить два 50-значных простых числа, получив при этом 99– или 100-значный результат. Обратная операция – взять 100-значное число и найти его простые делители – намного труднее. Стандартный школьный метод «пробовать все возможные делители по очереди» здесь бесполезен: возможностей слишком много. Кокс придумал функцию, основанную на произведении двух больших простых чисел, то есть на результате их перемножения. Получившийся шифр настолько надежен, что это произведение (но не его простые сомножители) можно не держать в секрете. Для расшифровки необходимо знать эти два простых числа по отдельности, в них и кроется секретный второй ключ. Без этих чисел вы ничего не сможете сделать, знания только их произведения недостаточно. Допустим, я говорю вам, что нашел два простых числа, произведение которых равно