Текст книги "Математики, шпионы и хакеры. Кодирование и криптография"

Автор книги: Жуан Гомес

сообщить о нарушении

Текущая страница: 1 (всего у книги 8 страниц)

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

Моему сыну Висенсу

Предисловие

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

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

Криптография, то есть искусство кодированного письма, появилась с возникновением самой письменности. Хотя еще египтяне и жители Месопотамии использовали методы шифрования, первыми, кто серьезно занялся криптографией, были древние греки и римляне – враждующие культуры, для которых тайное общение являлось ключевым элементом военных успехов. Такая секретность привела к появлению нового типа соперников – тех, кто называл себя хранителями тайны, – криптографов, и тех, кто надеялся раскрыть ее, – криптоаналитиков или специалистов по взламыванию шифров. Между ними шла всегда разыгрываемая за кулисами война, в которой временное преимущество могло быть то на одной, то на другой стороне, но никто никогда не достигал решающей победы. В VIII в., например, арабский мудрец Аль-Кинди придумал метод дешифровки, известный как частотный криптоанализ, который вскрывал любое закодированное сообщение. Ответом шифровальщиков (на такой ответ потребовались столетия) было изобретение полиалфавитного шифра.

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

Переломный момент в этой битве кодирования и расшифровки наступил с появлением первых машин шифрования и, вскоре после этого, первых машин расшифровки.

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

При взрывном росте вычислительной мощности именно шифры, а не традиционные соображения секретности играют ведущую роль в передаче информации. Универсальный язык современного общества использует не буквы или иероглифы, а только две цифры – 0 и 1. Это двоичный код.

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

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

Глава 1. Насколько защищена информация?

Криптография – искусство написания и вскрытия шифров.

Оксфордский словарь

Желание написать сообщение, которое может быть понято только отправителем и получателем, но остается бессмысленным для любого постороннего человека, так же старо, как и само искусство письма. И действительно, существует целый ряд «нестандартных» иероглифик, которым более 4500 лет, хотя невозможно с определенностью заключить, являются ли они попыткой зашифровать информацию или их лишь использовали в неких ритуалах. Больше известно о вавилонской табличке, датируемой 2500 г. до н. э. Она содержит слова с опущенной первой согласной и использует некоторые необычные символы. Исследования показали, что текст на табличке описывает метод изготовления глазурованной керамики. Это позволяет нам заключить, что табличка была сделана купцом или, возможно, гончаром, который пытался защитить секрет производства от конкурентов.

С развитием письма и торговли возникли огромные империи, которые в свою очередь были вовлечены в пограничные конфликты. Криптография и защищенная передача информации превратились в задачу первостепенной важности как для правительств, так и для торговцев. В наш информационный век защита средств коммуникации и поддержка необходимого уровня конфиденциальности важны как никогда. Вряд ли сейчас можно найти передаваемую информацию, не закодированную тем или иным способом. Цель кодирования – облегчить пересылку. Например, текст конвертируется в двоичные коды (система счисления, использующая только нули и единицы), понятные компьютеру. После кодирования информацию следует защитить от тех, кто может перехватить ее. Другими словами, код должен быть зашифрован. И, наконец, законный получатель должен быть в состоянии расшифровать сообщение. Кодирование, шифрование и расшифровка – это основные фигуры в «танце информации», который повторяется миллионы раз в секунду, каждую минуту, каждый час и каждый день. А музыкой, сопровождающей этот танец, является не что иное, как математика.

Коды, шифры и ключи

Криптографы используют термин «кодирование» в несколько другом смысле, чем мы. Для них кодирование – это процесс преобразования текста путем замены одних слов другими. С другой стороны, шифрование, или шифр, означает замену букв либо отдельных символов. С течением времени второй способ стал настолько распространенным, что превратился в синоним «кодированного письма». Однако если мы будем следовать более научной интерпретации, правильным термином для второго метода будет шифрование (или дешифрование в случае обратного процесса) сообщения.

Давайте представим, что мы посылаем защищенное сообщение «АТАКА». Мы могли бы сделать это двумя основными способами: заменить слово (кодирование) либо заменить некоторые или все буквы, составляющие это слово (шифрование).

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

* * *

ДВОИЧНЫЙ КОД

Чтобы компьютер мог понять и обработать информацию, она должна быть переведена с языка, на котором написана, на так называемый двоичный язык. Он состоит только из двух цифр: 0 и 1. Двоичные выражения для чисел в десятичной системе от 0 до 10 приведены в таблице справа.

Соответственно, десятичное число 9780 в двоичном коде будет выражено как 10011000110100.

ПЕРЕВОДИТЬ ИЛИ РАСШИФРОВЫВАТЬ?

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

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

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

* * *

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

* * *

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

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

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

(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 февраля беспощадную подводную войну. Несмотря на это, мы попытаемся удержать США в состоянии нейтралитета.

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

Вы немедленно и совершенно секретно предупредите президента [Мексики], как только объявление войны между нами и США станет свершившимся фактом.

Добавьте, что президент Мексики может по своей инициативе сообщить японскому послу, что Японии было бы очень выгодно немедленно присоединиться к нашему союзу.

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

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

Кроме того, активные угрозы Мексики вдоль южной границы Соединенных Штатов могли в равной степени предотвратить их вступление в конфликт по другую сторону океана. Мексике, однако, нужно было определенное количество времени для организации своих сил. Было крайне важно как можно дольше сохранять в тайне намерения Германии – до тех пор, пока баланс сил не изменится в ее пользу.

Комната 40 приступает к работе

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

Телеграмма Циммермана (вверху), которую посол Гэрмании в Вашингтоне Йоханн фон Бернсторф переслал своему коллеге в Мексике, и расшифрованная версия той же телеграммы (внизу).

Фрагмент британской расшифровки телеграммы Циммермана. В нижней части можно видеть, как немцы, не имея кода для слова «Аризона», зашифровали его символами: AR, IZ, ON, А.

Британское правительство направило перехваченное сообщение для дешифровки в криптоаналитический отдел, известный как Комната 40.

Немцы использовали для шифрования свой обычный алгоритм министерства иностранных дел и ключ под номером 0075, который эксперты Комнаты 40 уже частично взломали. Этот алгоритм включал в себя замену слов (кодирование), а также замену букв (шифрование). Это обычная практика, которую немцы в то время использовали и в другом методе шифрования, шифре ADFGVX, который мы более подробно рассмотрим позже.

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

Во-первых, секретная телеграмма была передана по дипломатическим каналам связи, предоставленным Германии Соединенными Штатами, – привилегия, которую англичане проигнорировали. Во-вторых, если бы телеграмма была предана огласке, немецкое правительство сразу бы выяснило, что его шифры взломаны, и изменило свою систему шифрования. Таким образом, англичане решили сказать американцам, что они перехватили и расшифровали сообщение, посланное фон Экхарду в Мексику, и тем самым убедить немцев, что телеграмма была перехвачена в Мексике уже в расшифрованном виде.

В конце февраля правительство Вильсона организовало «утечку информации» о содержании телеграммы в прессу. Некоторые представители прессы – в частности, прогерманские и настроенные против войны газеты американского медиамагната Херста – восприняли телеграмму скептически. Тем не менее, к середине марта Циммерман публично признал себя автором нашумевшего сообщения. Чуть более двух недель спустя, шестого апреля 1917 г., Конгресс США объявил войну Германии. Это решение имело далеко идущие последствия для Европы и всего мира.

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