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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

* * *

ДВОИЧНЫЙ КОД

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

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

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

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

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

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

* * *

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