Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

* * *

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

* * *

СКОЛЬКО ТРЕБУЕТСЯ КЛЮЧЕЙ?

Какое минимальное количество ключей необходимо в системе с двумя пользователями? Три? Четыре? Для тайного общения двух пользователей друг с другом требуется только один код или ключ. Для трех пользователей необходимы три ключа: один для связи между А и В, другой — для пары А и С, а третий — для В и С. Далее, четырем пользователям потребуется уже шесть ключей.

Таким образом, в общем случае п пользователей должны иметь столько ключей, сколько всего комбинаций пар из п пользователей, а именно:

(n/2) = n∙(n-1)/2

Так, относительно небольшая система из 10000 взаимосвязанных пользователей потребует 49995000 ключей. Для населения земного шара из шести миллиардов людей потребуется головокружительное количество: 17999999997000000000.

* * *

Общее правило шифрования называется алгоритмом шифрования, в то время как определенный параметр, используемый для шифрования или кодирования сообщений, называется ключом. (В примере шифрования со словом «АТАКА» на странице 10 ключ равен 2. Каждая буква оригинального сообщения заменяется другой, сдвинутой на две позиции вправо по алфавиту). Очевидно, что для каждого алгоритма шифрования существует большое количество ключей, поэтому знание алгоритма чаще всего бесполезно, если мы не знаем ключ, используемый для шифрования. Так как ключи обычно легче менять и передавать, для обеспечения безопасности системы шифрования логичнее будет постараться сохранить их в тайне. Этот принцип был сформулирован в конце XIX в. нидерландским лингвистом Огюстом Керкгоффсом фон Ниувенгофом и обычно называется принципом Керкгоффса.

Подводя итог вышеизложенному, мы можем изобразить общую систему шифрования в виде следующих элементов:

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

Закрытые и открытые ключи

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

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

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

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

* * *

СКОЛЬКО ТРЕБУЕТСЯ КЛЮЧЕЙ?.. ЧАСТЬ 2

Как мы видели на странице 12, классической криптографии требуется огромное количество ключей. Однако в открытой криптографической системе любым двум пользователям, которые обмениваются сообщениями, нужно только четыре ключа: по одному закрытому и открытому ключу для каждого. В этом случае n пользователей должны иметь 2n ключей.

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

7 мая 1915 г., когда половина Европы была втянута в кровавый конфликт, немецкая подлодка торпедировала трансатлантический пассажирский лайнер «Лузитания», который шел под британским флагом у берегов Ирландии. Результатом была одна из самых печально известных в истории катастроф: погибло 1198 пассажиров, из которых 124 были американцами. Новость привела в ярость общественное мнение в Соединенных Штатах, и правительство президента Вудро Вильсона предупредило немецкую сторону о том, что любые подобные действия вынудят Соединенные Штаты немедленно вступить в войну на стороне союзников. Кроме того, Вильсон потребовал, чтобы немецкие подводные лодки всплывали на поверхность перед выполнением любой атаки, чтобы не допускать гибели гражданских судов.

Это серьезно подрывало тактическое преимущество подводных лодок.

В ноябре 1916 г. новым министром иностранных дел Германии был назначен Артур Циммерман, человек с репутацией дипломата. Новость была благоприятно принята прессой Соединенных Штатов, которая расценивала этот факт как хорошее предзнаменование для развития отношений между Германией и США.

Так газета Нью-Йорк Таймс известила о гибели судна: «"Лузитания" потоплена подводной лодкой, возможно 1260 погибших; две торпеды от берегов Ирландии: затонула за 15 минут: капитан Тёрнер спасен, Фроман и Вандербилт пропали без вести; Вашингтон считает, что грядет серьезный кризис».

В январе 1917 г., менее чем через два года после трагедии «Лузитании», а также в наивысшей стадии развития конфликта, посол Германии в Вашингтоне Йоханн фон Бернсторф получил следующую шифрованную телеграмму от Циммермана с инструкциями тайно доставить ее послу Германии в Мексике Генриху фон Экхарду.

«Мы намерены начать 1 февраля беспощадную подводную войну. Несмотря на это, мы попытаемся удержать США в состоянии нейтралитета.

Однако в случае неуспеха мы предложим Мексике следующее: вместе вести войну и сообща заключить мир. С нашей стороны мы окажем Мексике щедрую финансовую поддержку и заверим, что по окончании войны она получит обратно утраченные ею территории Техаса, Новой Мексики и Аризоны. Мы поручаем вам [фон Экхарду] выработать детали этого соглашения.