/
Author: Гомес Ж.
Tags: математика кодирование криптография серия мир математики точные науки
ISBN: 978-5-9774-0639-0
Year: 2014
Text
Мир
МАТЕМАТИКИ
Математики,
шпионы и хакеры
Кодирование и криптография
D^AGOSTINI
Мир математики
Мир математики
Жуан Гомес
Математики, шпионы и хакеры
Кодирование и криптография
Москва - 2014
D^AGOSTINI
УДК 51(0.062)
ББК22.1
М63
М63 Мир математики: в 40 т. Т. 2: Жуан Гомес. Математики, шпионы и хакеры. Кодирова-
ние и криптография. / Пер. с англ. — М.: Де Агостини, 2014. — 144 с.
Если бы историю человечества можно было представить в виде шпионского романа,
то главными героями этого произведения, несомненно, стали бы криптографы и крипто-
аналитики. Первые — специалисты, виртуозно владеющие искусством кодирования со-
общений. Вторые — гении взлома и дешифровки, на компьютерном сленге именуемые
хакерами. История соперничества криптографов и криптоаналитиков стара как мир.
Эволюционируя вместе с развитием высоких технологий, ремесло шифрования достигло
в XXI веке самой дальней границы современной науки — квантовой механики. И хотя
объектом кодирования обычно является текст, инструментом работы кодировщиков была
и остается математика. Эта книга — попытка рассказать читателю историю шифрования
через призму развития математической мысли.
ISBN 978-5-9774-0682-6
ISBN 978-5-9774-0639-0 (т. 2)
УДК 51(0.062)
ББК22.1
© Joan Gomez, 2010 (текст)
© RBA Collecionables S.A., 2010
© ООО «Де Агостини», 2014
Иллюстрации предоставлены:
age fotostock, Aisa, Album, Corbis, Getty Images, iStockphoto.
Все права защищены.
Полное или частичное воспроизведение без разрешения издателя запрещено.
Оглавление
Предисловие ...................................................... 7
Глава 1. Насколько защищена информация?........................... 9
Коды, шифры и ключи............................................... 10
Закрытые и открытые ключи...................................... 13
Телеграмма Циммермана............................................. 14
Комната 40 приступает к работе................................. 16
Глава 2. Криптография от античности до XIX века................... 21
Стеганография..................................................... 21
Перестановочное шифрование........................................ 22
Кесарю кесарево................................................... 24
16 = 4. Модульная арифметика и математика шифра Цезаря ........... 27
Игра в шпионов.................................................... 33
За пределами аффинного шифра...................................... 35
Частотный криптоанализ............................................ 38
Подробный пример............................................... 39
Полиалфавитный шифр .............................................. 41
Идея Альберти................................................. 42
Квадрат Виженера .............................................. 43
Классификация алфавитов .......................................... 47
Анонимный криптоаналитик...................................... 49
Глава 3. Шифровальные машины ..................................... 53
Азбука Морзе ..................................................... 53
80 километров от Парижа........................................... 57
Шифровальная машина «Энигма» .................................... 60
Расшифровка кода «Энигмы» ..................................... 67
Британцы принимают эстафету................................... 69
Другие шифры Второй мировой войны................................ 71
Шифровальщики навахо.......................................... 73
Нововведения: шифр Хилла.......................................... 74
5
ОГЛАВЛЕНИЕ
Глава 4. Процесс общения посредством нулей и единиц............. 77
ASCII-код........................................................ 77
Шестнадцатеричная система счисления.............................. 79
Системы счисления и переход к другому основанию . 82
Коды для обнаружения ошибок передачи ............................ 83
Другие коды: коммерческие и индустриальные стандарты ............. 88
Кредитные карты ............................................... 88
Штрихкоды..................................................... 92
Стандарт штрихкода EAN-13...................................... 95
Глава 5. Общедоступная тайна: криптография с открытым ключом.... 99
Проблема распределения ключей.................................... 99
Алгоритм Диффи — Хеллмана ...................................... 100
Простые числа спешат на помощь: алгоритм шифрования RSA ..... 104
Подробнее об алгоритме RSA... 105
Почему мы можем доверять алгоритму RSA....................... 106
Приемлемая конфиденциальность ................................ 107
Проверка подлинности сообщений и ключей ........................ 108
Хеш-функции ................................................. 109
Сертификаты открытых ключей.................................... 110
Безопасно ли делать покупки через интернет? ...................... 112
Глава 6. Квантовое будущее ....................................... ИЗ
Квантовые вычисления.............................................. ИЗ
Кот, ни живой ни мертвый..................................... 114
От бита к кубиту .......................................... 116
Конец криптографии?.......................................... 118
Квантовая механика взяла, квантовая механика дала............... 118
Неуязвимый шифр ............................................. 120
32 сантиметра абсолютной секретности......................... 124
Приложение.................................................... 127
Список литературы ............................................ 139
Алфавитный указатель.............................................. 141
6
Моему сыну Висенсу
Предисловие
С давних пор любимой игрой всех мальчишек были попытки изобретения специ-
ального алфавита для обмена секретными сообщениями. Конечно, это было связано
больше с детским желанием поиграть в шпионов, чем с реальной угрозой перехвата
передаваемой информации посторонними лицами. Однако в мире взрослых такая
угроза, несомненно, существует, и конфиденциальность многих сообщений чрезвы-
чайно важна.
С наступлением информационного века кодирование и шифры, ранее представ-
лявшие интерес лишь для политической и социальной элиты, стали необходимыми
для нормального функционирования общества в целом. Эта книга является попыткой
рассказать историю секретных шифров с точки зрения наиболее квалифицированного
из гидов: математики.
Криптография, то есть искусство кодированного письма, появилась с возникнове-
нием самой письменности. Хотя еще египтяне и жители Месопотамии использовали
методы шифрования, первыми, кто серьезно занялся криптографией, были древние
греки и римляне — враждующие культуры, для которых тайное общение являлось
ключевым элементом военных успехов. Такая секретность привела к появлению ново-
го типа соперников — тех, кто называл себя хранителями тайны, — криптографов,
и тех, кто надеялся раскрыть ее, — криптоаналитиков или специалистов по взламы-
ванию шифров. Между ними шла всегда разыгрываемая за кулисами война, в которой
временное преимущество могло быть то на одной, то на другой стороне, но никто
никогда не достигал решающей победы. В VIII в., например, арабский мудрец
Аль-Кинди придумал метод дешифровки, известный как частотный криптоанализ,
который вскрывал любое закодированное сообщение. Ответом шифровальщиков
(на такой ответ потребовались столетия) было изобретение полиалфавитного шифра.
Это, казалось бы, стало решающей победой криптографов... но появился еще более
продвинутый метод расшифровки, разработанный в тишине кабинета английским
гением, что вновь склонило чашу весов в пользу криптоаналитиков. С тех пор главным
оружием, применяемым каждой из сторон, была математика, от статистики и теории
чисел до модульной арифметики.
Переломный момент в этой битве кодирования и расшифровки наступил с появле-
нием первых машин шифрования и, вскоре после этого, первых машин расшифровки.
7
ПРЕДИСЛОВИЕ
Первая программируемая вычислительная машина, названная Colossus, была изо-
бретена и построена британцами для взлома сообщений, закодированных немецкой
шифровальной машиной «Энигма».
При взрывном росте вычислительной мощности именно шифры, а не традицион-
ные соображения секретности играют ведущую роль в передаче информации. Универ-
сальный язык современного общества использует не буквы или иероглифы, а только
две цифры — 0 и 1. Это двоичный код.
Какая из сторон выиграла от прихода новых технологий: криптографы или крип-
тоаналитики? Возможна ли безопасность в наш век вирусов, информационных краж
и суперкомпьютеров? Ответ на второй вопрос в значительной степени положителен,
и снова мы должны сказать спасибо математике, а именно простым числам и их осо-
бенным свойствам. Как долго продержится временная победа криптографии? Ответ
на этот вопрос уведет нас к самой дальней границе современной науки — теории
квантовой механики, поразительные парадоксы которой подведут итог нашему за-
хватывающему путешествию по разделу математики, отвечающему за безопасность
и секретность.
Эта книга заканчивается списком литературы для тех, кто желает глубже про-
никнуть в мир кодирования и шифрования, а алфавитный указатель на последних
страницах поможет в поиске.
8
Глава 1
Насколько защищена
информация?
Криптография — искусство написания и вскрытия шифров.
Оксфордский словарь
Желание написать сообщение, которое может быть понято только отправителем
и получателем, но остается бессмысленным для любого постороннего человека,
так же старо, как и само искусство письма. И действительно, существует целый ряд
«нестандартных» иероглифик, которым более 4500 лет, хотя невозможно с опреде-
ленностью заключить, являются ли они попыткой зашифровать информацию или
их лишь использовали в неких ритуалах. Больше известно о вавилонской табличке,
датируемой 2500 г. до н. э. Она содержит слова с опущенной первой согласной и ис-
пользует некоторые необычные символы. Исследования показали, что текст на та-
бличке описывает метод изготовления глазурованной керамики. Это позволяет нам
заключить, что табличка была сделана купцом или, возможно, гончаром, который
пытался защитить секрет производства от конкурентов.
С развитием письма и торговли возникли огромные империи, которые в свою
очередь были вовлечены в пограничные конфликты. Криптография и защищенная
передача информации превратились в задачу первостепенной важности как для
правительств, так и для торговцев. В наш информационный век защита средств
коммуникации и поддержка необходимого уровня конфиденциальности важны как
никогда. Вряд ли сейчас можно найти передаваемую информацию, не закодирован-
ную тем или иным способом. Цель кодирования — облегчить пересылку. Например,
текст конвертируется в двоичные коды (система счисления, использующая только
нули и единицы), понятные компьютеру. После кодирования информацию следует
защитить от тех, кто может перехватить ее. Другими словами, код должен быть
зашифрован. И, наконец, законный получатель должен быть в состоянии расшиф-
ровать сообщение. Кодирование, шифрование и расшифровка — это основные фи-
гуры в «танце информации», который повторяется миллионы раз в секунду, каждую
минуту, каждый час и каждый день. А музыкой, сопровождающей этот танец, явля-
ется не что иное, как математика.
9
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
Коды, шифры и ключи
Криптографы используют термин «кодирование» в несколько другом смысле, чем
мы. Для них кодирование — это процесс преобразования текста путем замены од-
них слов другими. С другой стороны, шифрование, или шифр, означает замену букв
либо отдельных символов. С течением времени второй способ стал настолько рас-
пространенным, что превратился в синоним «кодированного письма». Однако если
мы будем следовать более научной интерпретации, правильным термином для вто-
рого метода будет шифрование (или дешифрование в случае обратного процесса)
сообщения.
Давайте представим, что мы посылаем защищенное сообщение «АТАКА». Мы
могли бы сделать это двумя основными способами: заменить слово (кодирование)
либо заменить некоторые или все буквы, составляющие это слово (шифрование).
Простым способом закодировать слово является его перевод на язык, который по-
тенциальный перехватчик не знает, тогда как для зашифровки было бы достаточно,
например, заменить каждую букву другой буквой алфавита. В каждом случае необ-
ходимо, чтобы получатель знал процедуру, которая была использована для кодиро-
вания или шифрования сообщения, иначе наше послание будет бесполезно. Если мы
уже договорились с получателем, какой метод будем использовать — перевод слова
на другой язык или замену каждой буквы другой — все, что нам надо сделать, —
это сообщить ему этот другой язык или число позиций, на которое мы сдвигаем
в алфавите каждую букву, чтобы сделать замену. В случае шифрования получатель,
имея сообщение «ВФВМВ» и зная, что каждая буква была сдвинута в алфавите
на две позиции, может легко обратить процесс и расшифровать сообщение.
ДВОИЧНЫЙ код
0 0
Чтобы компьютер мог понять и обработать информацию, она должна быть переведена с языка, на котором написана, на так называемый двоичный язык. Он состоит только из двух цифр: 0 и 1. Двоичные выражения для чисел в десятичной системе от 0 до 10 приведены в таблице справа. Соответственно, десятичное число 9780 в двоичном коде будет выражено как 10011000110100. 1 1
10 2
11 3
100 4
101 5
110 6
111 7
1000 8
1001 9
1010 10
10
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
ПЕРЕВОДИТЬ
ИЛИ РАСШИФРОВЫВАТЬ?
Перевод текста, написанного на языке, который
использует неизвестный набор символов, можно
рассматривать как общую проблему расшифровки.
Перевод - это неизвестный текст, уже переведенный
на наш язык, а алгоритм шифрования - это
грамматические правила и синтаксис оригинального
языка. Методы, используемые для обеих задач, -
перевода и расшифровки - имеют много общего.
В обоих случаях должно быть выполнено одно условие:
отправитель и получатель по крайней мере должны
владеть общим языком. Вот почему перевод текстов,
написанных на утерянных языках, таких как египетская иероглифика или линейное письмо Б,
был невозможен, пока не были найдены соответствия с известным языком. В обоих случаях
это оказался древнегреческий язык. На рисунке выше изображена найденная на Крите
табличка с надписью линейным письмом Б.
Различие, которое мы установили между правилом шифрования (применяемым ме-
тодом) и ключом шифрования (изменяемой инструкцией, специфичной для каждого
сообщения или группы сообщений), чрезвычайно полезно, потому что потенциаль-
ному шпиону необходимо знать и то, и другое, чтобы расшифровать сообщение. На-
пример, шпиону может быть известно правило шифрования, а именно, что каждая
буква заменяется другой, сдвинутой в алфавите на х позиций. Тем не менее, если он
не знает, чему равен х, ему придется перебрать все возможные комбинации: по од-
ной для каждой буквы алфавита. В данном примере шифр очень прост, и перебрать
все комбинации не составит большого труда. Такой способ расшифровки называется
методом перебора всех возможных вариантов. Однако в случае более сложных пра-
вил этот метод расшифровки, или криптоанализа, практически неприменим, во вся-
ком случае, вручную. Более того, перехват и расшифровка сообщения, как правило,
ограничены по времени. Информацию нужно получить и понять до того, как она
станет бесполезной или известной другим.
И
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
СКОЛЬКО ТРЕБУЕТСЯ КЛЮЧЕЙ?
Какое минимальное количество ключей необходимо в системе с двумя пользователями? Три?
Четыре? Для тайного общения двух пользователей друг с другом требуется только один код или
ключ. Для трех пользователей необходимы три ключа: один для связи между А и В, другой - для
пары А и С, а третий - для В и С. Далее, четырем пользователям потребуется уже шесть ключей.
Таким образом, в общем случае п пользователей должны иметь столько ключей, сколько всего
комбинаций пар из п пользователей, а именно:
/п\ п(п-1)
U 2
Так, относительно небольшая система из 10000 взаимосвязанных пользователей потребует
49995000 ключей. Для населения земного шара из шести миллиардов людей потребуется голо-
вокружительное количество: 17999999997000000000.
Общее правило шифрования называется алгоритмом шифрования, в то время как
определенный параметр, используемый для шифрования или кодирования сообще-
ний, называется ключом. (В примере шифрования со словом «АТАКА» на странице
10 ключ равен 2. Каждая буква оригинального сообщения заменяется другой, сдви-
нутой на две позиции вправо по алфавиту). Очевидно, что для каждого алгоритма
шифрования существует большое количество ключей, поэтому знание алгоритма
чаще всего бесполезно, если мы не знаем ключ, используемый для шифрования. Так
как ключи обычно легче менять и передавать, для обеспечения безопасности систе-
мы шифрования логичнее будет постараться сохранить их в тайне. Этот принцип был
сформулирован в конце XIX в. нидерландским лингвистом Огюстом Керкгоффсом
фон Ниувенгофом и обычно называется принципом Керкгоффса.
12
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
Подводя итог вышеизложенному, мы можем изобразить общую систему шифро-
вания в виде следующих элементов:
алгоритм + ключ алгоритм + ключ
Таким образом, мы имеем отправителя и получателя сообщения, алгоритм шиф-
рования и определенный ключ, который позволяет отправителю зашифровать со-
общение, а получателю — расшифровать его. Позже мы увидим, как эта схема была
модифицирована из-за изменившихся в последнее время функций ключа, но пока
мы будем придерживаться этой диаграммы.
Закрытые и открытые ключи
Принцип Керкгоффса определяет ключ как основополагающий элемент безопасно-
сти любой криптографической системы. До сравнительно недавнего времени ключи
у отправителя и получателя во всех известных криптографических системах обяза-
тельно были идентичными или по крайней мере симметричными, то есть они исполь-
зовались как для шифрования, так и для расшифровки сообщений. Ключ, таким об-
разом, был секретом, известным отправителю и получателю, а значит, используемая
криптографическая система всегда была уязвимой, так сказать, с обеих сторон. Этот
тип шифрования, который зависит от ключа, известного отправителю и получателю,
называется шифрованием с закрытым ключом.
Все криптографические системы, изобретенные человеком с начала времен, неза-
висимо от используемого алгоритма и его сложности, имеют эту характерную осо-
СКОЛЬКОТРЕБУЕТСЯ КЛЮЧЕЙ?.. ЧАСТЬ 2
Как мы видели на странице 12, классической криптографии требуется огромное количество клю -
чей. Однако в открытой криптографической системе любым двум пользователям, которые обме-
ниваются сообщениями, нужно только четыре ключа: по одному закрытому и открытому ключу для
каждого. В этом случае п пользователей должны иметь 2п ключей.
13
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
бенность. Ситуация, когда и получатель, и отправитель имеют одинаковый ключ,
вроде бы отвечает здравому смыслу. В конце концов, как может один человек шиф-
ровать сообщение одним ключом, а второй — расшифровать это же сообщение дру-
гим ключом, надеясь, что смысл текста не изменится? На протяжении тысячелетий
эта возможность считалась логическим абсурдом. Однако, как мы более подробно
увидим позже, всего пять десятилетий назад этот абсурд стал реальностью и теперь
повсеместно используется в шифровании.
В настоящее время алгоритмы шифрования, используемые в системах связи, со-
стоят как минимум из двух ключей: тайный закрытый, как это уже было принято,
и открытый, известный всем. Процесс передачи информации выглядит так: отпра-
витель использует для шифрования открытый ключ получателя, которому он хочет
отправить сообщение. Получатель использует свой закрытый ключ для расшифров-
ки полученного сообщения. Более того, эта система обладает чрезвычайно важным
дополнительным преимуществом: отправителю и получателю не нужно встречаться
заранее, чтобы договориться об используемых ключах, поэтому безопасность систе-
мы стала более надежной, чем это было возможно раньше. Эта совершенно револю-
ционная форма шифрования известна как шифрование с открытым ключом, и имен-
но она обеспечивает безопасность современных коммуникационных сетей.
В основе этой революционной технологии лежит математика. В действительно-
сти, как мы позже подробнее поясним, современная криптография зиждется на двух
столпах. Первый — модульная арифметика, а второй — теория чисел, в частности,
ее раздел, изучающий простые числа.
Телеграмма Циммермана
Криптография — это одна из областей прикладной математики, в которой контраст
между безупречной ясностью, лежащей в основе теории, и темными последствиями
ее применения является наиболее очевидным. В конце концов, судьбы целых на-
родов зависят от успеха или провала обеспечения безопасной связи. Одним из наи-
более впечатляющих примеров того, как криптография изменила ход истории, стала
телеграмма Циммермана, посланная почти сто лет назад.
7 мая 1915 г., когда половина Европы была втянута в кровавый конфликт, немец-
кая подлодка торпедировала трансатлантический пассажирский лайнер «Лузита-
ния», который шел под британским флагом у берегов Ирландии. Результатом была
одна из самых печально известных в истории катастроф: погибло 1198 пассажиров,
из которых 124 были американцами. Новость привела в ярость общественное мне-
14
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
1 She ;№еш JJcrk Suw. EZXR*
~ ' ’у у* * - ~'.i.7 Л^^.^ДДМЙЙи^И
LUSITANIA SUNK BY A SUBMARINE, PROBABLY 1,260 DEAD;
TWICE TORPEDOED OFF IRISH COAST; SINKS IN IS MINUSES;
CAPT. TURNER SAVED, FROHMAN AND VANDERBILT MISSING;
WASHINGTON BELIEVES THAT A GRAVE CRISIS IS AT HAND
Так газета Нью-Йорк Таймс известила о гибели судна:
«"Лузитания" потоплена подводной лодкой, возможно 1260 погибших;
две торпеды от берегов Ирландии; затонула за 15 минут;
капитан Тёрнер спасен, Фроман и Вандербилт пропали без вести;
Вашингтон считает, что грядет серьезный кризис».
ние в Соединенных Штатах, и правительство президента Вудро Вильсона пред-
упредило немецкую сторону о том, что любые подобные действия вынудят Соеди-
ненные Штаты немедленно вступить в войну на стороне союзников. Кроме того,
Вильсон потребовал, чтобы немецкие подводные лодки всплывали на поверхность
перед выполнением любой атаки, чтобы не допускать гибели гражданских судов.
Это серьезно подрывало тактическое преимущество подводных лодок.
В ноябре 1916 г. новым министром иностранных дел Германии был назначен Ар-
тур Циммерман, человек с репутацией дипломата. Новость была благоприятно при-
нята прессой Соединенных Штатов, которая расценивала этот факт как хорошее
предзнаменование для развития отношений между Германией и США.
В январе 1917 Г., менее чем через два года после трагедии «Лузитании», а также
в наивысшей стадии развития конфликта, посол Германии в Вашингтоне Йоханн
фон Бернсторф получил следующую шифрованную телеграмму от Циммермана
с инструкциями тайно доставить ее послу Германии в Мексике Генриху фон Экхарду.
«Мы намерены начать 1 февраля беспощадную подводную войну. Несмотря
на это, мы попытаемся удержать США в состоянии нейтралитета.
15
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
Однако в случае неуспеха мы предложим Мексике следующее: вместе вести вой-
ну и сообща заключить мир. С нашей стороны мы окажем Мексике щедрую фи-
нансовую поддержку и заверим, что по окончании войны она получит обратно
утраченные ею территории Техаса, Новой Мексики и Аризоны. Мы поручаем
вам [фон Экхарду] выработать детали этого соглашения.
Вы немедленно и совершенно секретно предупредите президента [Мексики], как
только объявление войны между нами и США станет свершившимся фактом.
Добавьте, что президент Мексики может по своей инициативе сообщить япон-
скому послу, что Японии было бы очень выгодно немедленно присоединиться
к нашему союзу.
Обратите внимание президента на тот факт, что безжалостное использование на-
ших подводных сил заставит Англию подписать мир в ближайшие месяцы».
Если бы телеграмма была предана гласности, неизбежным следствием этого было бы
начало войны между Германией и Соединенными Штатами. Хотя император Виль-
гельм II знал, что война неизбежна, если подводные лодки не будут выходить на по-
верхность перед атакой, он надеялся, что к тому времени Великобритания капитулирует
и, следовательно, не будет конфликта, к которому США могли бы присоединиться.
Кроме того, активные угрозы Мексики вдоль южной границы Соединенных Штатов
могли в равной степени предотвратить их вступление в конфликт по другую сторону
океана. Мексике, однако, нужно было определенное количество времени для органи-
зации своих сил. Было крайне важно как можно дольше сохранять в тайне намерения
Германии — до тех пор, пока баланс сил не изменится в ее пользу.
Комната 40 приступает к работе
Однако у британского правительства были другие планы. Вскоре после начала вой-
ны британцы перерезали подводные телеграфные кабели, которые соединяли Гер-
манию напрямую с западным полушарием, поэтому любые электронные сообщения
шли по кабелям, которые англичане могли прослушивать. Соединенные Штаты,
пытаясь путем переговоров положить конец конфликту, позволяли Германии про-
должать передавать дипломатические сообщения. В результате сообщение Цим-
мермана в нетронутом виде было получено немецким представительством в Ва-
шингтоне.
16
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
telbgbam bjgxjkivkd.
im i-e-M
Гяом 2nd from London f 5747.
'Me intend to begin on the first of February
unrestricted submarine warfare, ft shall endeavos
in spite of this to keep the United states of
anerlca neutral. In the event of this not succeed-
ing, we make Mexico a proposal of alliance on the
following basis: make war together, make peace
together, generous financial support and an under-
stand I np
the lost
*rlaona.
Tou will
secretly
United States of Anerlca is certain and add the
suggt tlon that he should, on hie own initiative,
wsMW Japan to imnedlate adherence and at the same
time mediate between Jape: and
call the President's attention
the ruthless employment of our
offers the prospect of compelling Xngland In a
few months to make peace.” feigned, ИГгГ-’ЪЖ'Лг-.Н.
on our part that Mexico is to reconquer
territory In Texas, New Mexico, and
The settlement In detail Is left to you.
Inform the President of the above most
as soon as the outbreak of war with the
ourselves. Please
to the fact that
submarines now
Телеграмма Циммермана (вверху), которую посол Гэрмании в Вашингтоне Йоханн фон Бернсторф
переслал своему коллеге в Мексике, и расшифрованная версия той же телеграммы (внизу).
17
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
Г
Ф
буе 6 е / A t А.
Го «'♦ -Z.
"С*к /*•»'-7л <
7 Я • А
/л «п
(>7^3
Ри.
3U77 7С*< а
Ф
кЛъл»
Алл, Со ,
G)
лК
IX
Ка»7 ' 0.V
А
Фрагмент британской расшифровки телеграммы Циммермана. В нижней части можно видеть,
как немцы, не имея кода для слова «Аризона», зашифровали его символами: AR, IZ, ON, А.
Британское правительство направило перехваченное сообщение для дешифровки
в криптоаналитический отдел, известный как Комната 40.
Немцы использовали для шифрования свой обычный алгоритм министерства
иностранных дел и ключ под номером 0075, который эксперты Комнаты 40 уже ча-
стично взломали. Этот алгоритм включал в себя замену слов (кодирование), а также
замену букв (шифрование). Это обычная практика, которую немцы в то время ис-
пользовали и в другом методе шифрования, шифре ADFGVX, который мы более
подробно рассмотрим позже.
Англичанам не потребовалось много времени, чтобы расшифровать телеграм-
му, хотя они и не поспешили показать ее американцам. На это было две причины.
Во-первых, секретная телеграмма была передана по дипломатическим каналам свя-
18
НАСКОЛЬКО ЗАЩИЩЕНА ИНФОРМАЦИЯ?
зи, предоставленным Германии Соединенными Штатами, — привилегия, которую
англичане проигнорировали. Во-вторых, если бы телеграмма была предана огласке,
немецкое правительство сразу бы выяснило, что его шифры взломаны, и изменило
свою систему шифрования. Таким образом, англичане решили сказать американцам,
что они перехватили и расшифровали сообщение, посланное фон Экхарду в Мекси-
ку, и тем самым убедить немцев, что телеграмма была перехвачена в Мексике уже
в расшифрованном виде.
В конце февраля правительство Вильсона организовало «утечку информации»
о содержании телеграммы в прессу. Некоторые представители прессы — в част-
ности, прогерманские и настроенные против войны газеты американского медиа-
магната Херста — восприняли телеграмму скептически. Тем не менее, к середине
марта Циммерман публично признал себя автором нашумевшего сообщения. Чуть
более двух недель спустя, шестого апреля 1917 г., Конгресс США объявил войну
Германии. Это решение имело далеко идущие последствия для Европы и всего мира.
Чрезвычайно скандальная в свое время телеграмма Циммермана является лишь
одним из ярких исторических событий, в которых криптография сыграла существен-
ную роль. В этой книге мы увидим много примеров из других веков и культур. Од-
нако можно быть почти уверенными в том, что о многих важнейших событиях мы
ничего не знаем. Ведь по своей природе история криптографии является историей
тайн.
19
Глава 2
Криптография от античности
до XIX века
Как мы уже говорили, криптография является древней дисциплиной, вероятно,
столь же древней, как и само письменное общение. Однако это не единственно воз-
можный способ тайной передачи информации. В конце концов, каждый текст как-
то изображается, и если мы сделаем это изображение невидимым для всех, кроме
получателя, наша цель будет достигнута. Техника сокрытия самого существования
сообщения называется стеганографией, и она, вероятно, появилась примерно в то же
время и по тем же причинам, что и криптография.
Стеганография
Греческий ученый Геродот, считающийся одним из величайших историков мира,
в своей знаменитой хронике войны между греками и персами в V в. до н. э. упо-
минает два любопытных примера стеганографии, потребовавших значительной изо-
бретательности. Первый пример описан в третьей книге «Истории» Геродота: Ги-
стией, тиран города Милета, приказал побрить гонцу голову. Затем на коже головы
написали сообщение, которое нужно было отправить, и подождали, когда волосы
отрастут. После этого человека послали к месту назначения, в лагерь Аристагора.
Благополучно добравшись туда, посланник объяснил уловку Аристагору и снова
сбрил волосы, показав долгожданное сообщение. Второй пример, если это, конечно,
правда, имел большее историческое значение, поскольку это позволило спартанско-
му царю Демарату, сосланному в Персию, предупредить своих соотечественников
о грозящем нашествии персидского царя Ксеркса. Геродот пишет об этом в седьмой
книге:
«Дело в том, что Демарат не мог так просто предупредить их, поэтому он
придумал вот какую хитрость: он взял пару восковых дощечек [для письма],
соскоблил воск и написал планы персидского царя на деревянной поверхно-
сти. Затем он залил дощечки растопленным воском, таким образом скрыв
сообщение.
21
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
В итоге дощечки, выглядевшие пустыми, не могли возбудить никаких подо-
зрений у дорожных стражей.
Когда дощечки доставили в Лакедемон (Спарта), лакедемоняне долго не мог-
ли разгадать секрет, пока, наконец, как я это понимаю, Горго [...] не пред-
ложила соскоблить воск с дощечек, потому что тогда, по ее словам, на дереве
обнаружится сообщение».
Стеганографический метод, выдержавший испытание временем, — это невидимые
чернила. Известные по многим рассказам и фильмам, такие чернила содержат мате-
риалы, как правило, органического происхождения с высоким содержанием углерода:
лимонный сок, растительные соки и даже человеческую мочу, поэтому они имеют
тенденцию темнеть при умеренном нагревании, например, над пламенем свечи.
Польза стеганографии бесспорна, хотя этот способ совершенно невыгоден при
большом количестве сообщений. Более того, сам по себе этот метод имеет суще-
ственный недостаток: если сообщение все-таки будет перехвачено, его содержание
сразу же станет известным. По этой причине стеганография в основном использует-
ся совместно с методами криптографии как средство усиления безопасности сообще-
ний наивысшей секретности.
Как показывают приведенные примеры, угроза вооруженного конфликта была
серьезным стимулом для защиты передаваемой информации. Поэтому не удиви-
тельно, что такие воинственные люди, как спартанцы, бывшие, если верить Геро-
доту, мастерами стеганографии, были также пионерами в развитии криптографии.
Перестановочное шифрование
Во время конфликта между Афинами и Спартой для контроля над Пелопоннесом
часто использовалась скитала — прибор, состоящий из цилиндра и обмотанной во-
круг него по спирали узкой полоски бумаги, на которой писалось сообщение. Хотя
используемый метод (то есть алгоритм шифрования) был известен противнику,
не зная точных размеров скиталы, было чрезвычайно трудно расшифровать пере-
хваченное сообщение. Толщина и длина скиталы были, в сущности, ключом к этой
системе шифрования. После разматывания бумажной ленты прочитать сообщение
было невозможно. На рисунке ниже передаваемое сообщение (М) выглядит так:
A message encoded with a scytale («Сообщение, закодированное с помощью скита-
22
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
КРОШЕЧНЫЕ БУКВЫ
В годы холодной войны герои шпионских триллеров часто использовали крошечные микрофиль-
мы для пересылки сообщений, чтобы их было невозможно прочитать невооруженным глазом.
Этот стеганографический метод, названный «микроточки», был разработан на несколько лет
раньше, в Германии во время Второй мировой войны. Фотография текста сообщения уменьша-
лась до размеров точки, а затем прикреплялась к безобидному письму в качестве одного из мно-
гих типографских символов.
лы»), но после разматывания бумажной ленты сообщение превратилось в тарабар-
щину (С): anh mca eos sdc sey adt gwa eil ete.
M = A MESSAGE ENCODED WITH A SCYTALE
C = ANH MCA EOS SDC SEY ADT GWA EIL ETE
Использование скиталы основано на криптографическом методе, известном как
перестановочное шифрование, когда буквы сообщения переставляются местами.
Чтобы получить представление о силе этого метода, рассмотрим простой пример
перестановки всего трех букв: А, О и R. Быстрая проверка без каких-либо расче-
тов показывает, что они могут быть переставлены шестью различными способами:
AOR, ARO, OAR, ORA, ROA и RAO.
В абстрактных терминах процесс выглядит следующим образом: как только одна
из трех возможных букв поставлена на первое место, что дает нам три различных
возможности, остаются еще две буквы, которые в свою очередь могут быть пере-
ставлены двумя различными способами. Таким образом, общее количество составит
3x2 = 6 способов. В случае более длинного сообщения, например, из 10 букв, чис-
23
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
РУКОВОДСТВО ДЛЯ МОЛОДЫХ ДАМ
Камасутра - это пространное руководство, которое посвящено, среди прочего, тому, что необ-
ходимо знать каждой женщине, чтобы быть хорошей женой. Созданное около IV в. до н. э. бра-
мином по имени Ватьсьяяна, оно рассказывает о 64 различных навыках в том числе о музыке,
кулинарии и шахматах. Особый интерес для нас имеет навык под номером 45, потому что он
представляет собой искусство тайнописи, или млеччхита-викальпа. Древний мудрец рекоменду-
ет несколько методов, в том числе такой: разделить алфавит на две части и распределить бук-
вы по парам случайным образом. В этой системе каждое соответствие пар представляет собой
ключ. Например, один из ключей может быть следующим:
А S С D N F G X 1 J к Z М
Е О р Q R В Т и V W н Y L
Чтобы написать тайное послание, нужно просто заменить каждую букву А в оригинальном тек-
сте буквой Е, букву Р, соответственно, буквой С, J - буквой W, и так далее.
ло возможных перестановок составит 10x9x8x7x6x5x4x3x2x1. Такое
произведение в математике записывается как 10! и дает число 3 628 800. В общем
случае для сообщения из п букв существует и! различных способов изменить их
порядок. Таким образом, скромное сообщение из 40 символов имеет так много спо-
собов изменения порядка букв, что это сообщение практически невозможно рас-
шифровать вручную. Может быть, мы нашли идеальный криптографической метод?
Не совсем так. По сути, алгоритм перестановочного шифрования обеспечивает
высокий уровень безопасности, но как насчет ключа, который позволяет расшифро-
вать сообщение? Случайность процесса составляет и его силу, и его слабость. По-
требовался другой метод шифрования, чтобы генерировать ключи, которые были бы
простыми и легкими для запоминания и передачи без потери уровня безопасности.
Так начались поиски идеального алгоритма, и первые успехи в этом деле были до-
стигнуты римскими императорами.
Кесарю кесарево
Veni, vidi, vici (пришел, увидел, победил).
Юлий Цезарь
Шифры подстановки разрабатывались параллельно с перестановочным шифрова-
нием. В отличие от перестановочного шифрования, строгий шифр подстановки заме-
24
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
няет каждую букву или символ на какой-то другой. В отличие от перестановочного
шифрования, шифр подстановки основывается не только на буквах, которые содер-
жатся в сообщении. В перестановочном шифровании буква меняет свое положение,
но сохраняет свою роль; одна и та же литера имеет одинаковое значение в исходном
сообщении и в зашифрованном. В шифре подстановки буквы сохраняют свои по-
зиции, но меняют роли (одна и та же буква или символ имеет в исходном сообщении
одно значение, а в зашифрованном — другое). Одним из первых известных алго-
ритмов шифра подстановки был шифр Полибия, названный в честь греческого исто-
рика Полибия (203—120 гг. до н. э.), который оставил нам его описание. Об этом
методе подробно рассказано в Приложении.
Спустя примерно 50 лет после появления шифра Полибия, в I в. до н. э., возник
другой шифр подстановки, известный под общим названием шифра Цезаря, пото-
му что именно Юлий Цезарь использовал его для секретной переписки со своими
генералами. Шифр Цезаря является одним из наиболее изученных в криптографии,
и он очень полезен тем, что иллюстрирует принципы модульной арифметики, одной
из математических основ кодированного письма.
Шифр Цезаря заменяет каждую букву другой, находящейся в алфавите на неко-
торое фиксированное число позиций правее. Как писал великий историк Светоний
в книге «Жизнь двенадцати цезарей», Юлий Цезарь использовал для своей личной
ГАЙ ЮЛИЙ ЦЕЗАРЬ (100-44 гг. до н.э.)
Цезарь (на изображении справа) был военным и государ-
ственным деятелем, диктатура которого положила конец
Римской республике. После службы в качестве магистра-
та в Дальней Испании он присоединился к двум другим
влиятельным людям того времени, Помпею и Крассу, об-
разовав Первый Триумвират, скрепленный браком Пом-
пея с дочерью Цезаря, Юлией. Три союзника разделили
между собой Римскую империю: Красс получил восточные
провинции, Помпей остался в Риме, а Цезарь взял на себя
военное командование Цизальпийской Галлией и управле-
ние Трансальпийской Галлией. В это время началась Галльская война. Она длилась восемь лет
и завершилась завоеванием римлянами галльских территорий. После этого Цезарь со своей по-
бедоносной армией вернулся в столицу империи и назначил себя единственным диктатором.
25
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
переписки следующий алгоритм подстановки: каждая буква исходного сообщения
сдвигалась по алфавиту на три позиции, а именно, буква А заменялась на D, В —
на Е, и так далее. Буква W превращалась в Z, а X, Y и Z возвращались к А,
В и С.
Кодирование и декодирование зашифрованных таким образом сообщений может
быть осуществлено с помощью простого устройства, показанного ниже:
ABC DEFGHIJ KLMNOPQRST UV WX YZ
defgHijklmno
QR S TUVWXYZA ВС DEFGHIJKLMNOP
Рассмотрим теперь этот процесс подробнее. В таблице ниже мы видим изначальный
алфавит из 26 букв и алфавит, преобразованный шифром Цезаря, где каждая буква
сдвинута на три позиции вправо (верхний ряд — алфавит открытого сообщения,
а нижний — шифроалфавит).
А В С D Е F G Н 1 J К L М N о Р Q R S т и V W X Y Z
D Е F G Н 1 J К L М N О Р Q R S т и V W X Y Z А В С
ШИФРЫ В ФИЛЬМАХ
В классическом научно-фантастическом фильме режиссера Стэнли Кубрика по мотивам пове-
сти Артура Кларка «Космическая одиссея 2001 года» (1968) наделенный сознанием суперком-
пьютер космического корабля HAL 9000 сходит с ума и пытается убить человеческий экипаж.
Теперь предположим, что слово HAL закодировано шиф-
ром Цезаря со сдвигом на одну позицию. Тогда буква Н
соответствует букве I, А соответствует В, a L - букве М;
другими словами, получается IBM, в то время крупней-
ший в мире производитель компьютеров. 0 чем пытался
рассказать этот фильм: об опасностях искусственного
интеллекта или об угрозах бесконтрольной коммерче-
ской монополии? Или это просто совпадение?
Всевидящий глаз компьютера HAL 9000
из фильма «Космическая одиссея 2001 года»
26
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Когда два алфавита, оригинальный (или алфавит открытого сообщения) и шиф-
роалфавит, расположены таким образом, шифрование любого сообщения сводится
к замене букв из первого алфавита буквами из второго. Ключ к такому шифру по-
лучает название по букве, соответствующей зашифрованному значению буквы А
(первой буквы оригинального алфавита). В нашем случае это буква D. Известное
выражение AVE CAESAR («Радуйся, Цезарь») будет зашифровано как DYH
FDHVDU. Обратно, если зашифрованное сообщение выглядит как WUHH,
то расшифрованный текст будет TREE («Дерево»). В случае с только что описан-
ным шифром Цезаря криптоаналитик, который перехватил сообщение и знает ис-
пользуемый алгоритм, но не знает ключ к шифру, должен будет перебрать все воз-
можные сдвиги алфавита, пока не найдет сообщение, имеющее смысл. Для этого он
должен будет, в худшем случае, попробовать все возможные ключи или сдвиги. В ал-
фавите, состоящем из п букв, существует п возможных сдвигов, то есть п ключей.
16 = 4. Модульная арифметика и математика шифра Цезаря
16 = 4? 2 = 14? Это не ошибка и не какая-то странная система счисления. Работа
шифра Цезаря может быть проиллюстрирована теорией, которая привычна для ма-
тематики и в еще большей степени для криптографии — модульной арифметикой,
иногда называемой часовой арифметикой. Эта теория появилась еще в работах гре-
ческого математика Евклида (325—265 гг. до н. э.) и является одной из основ совре-
менной информационной безопасности. В этом параграфе мы расскажем о базовых
математических понятиях, связанных с этим особым типом арифметики.
ОТЕЦ АНАЛИТИЧЕСКОЙ КРИПТОГРАФИИ
Основная работа Евклида Александрийского, «Начала», состоит из 13 томов, в которых из-
лагаются основные факты планиметрии, теории пропорций, свойства чисел, сведения об ир-
рациональных числах и стереометрии. Чаще всего ассоциируемые с этой последней теорией,
работы греческого математика, связанные с арифметическими операциями на конечных
числовых множествах, или операциями по модулю, являются одним из столпов современной
теории криптографии. Известные и почитаемые еще арабскими учеными, работы Евклида
впервые были изданы в Венеции в 1482 г. Вовсе не случайно, что и арабы, и венецианцы
были великими мастерами криптографии.
27
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Возьмите в качестве примера обычные часы со стрелками и сравните их с цифро-
выми часами. На часах со стрелками циферблат разделен на 12 частей, которые мы
обозначим числами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. В следующей таблице можно
видеть, как время на аналоговом циферблате соответствует времени после полудня
экране цифровых часов.
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22 23
Когда мы говорим, например, что сейчас 14:00, мы
можем также сказать, что сейчас два часа дня. Тот же
принцип применяется и в случае измерения углов. Угол
в 370 градусов равен углу в 10 градусов, потому что от пер-
вого значения мы должны вычесть полный оборот в 360 граду-
сов. Заметим, что 370 = (1 х 360) + 10, то есть 10 является остатком от деления
370 на 360. Какой угол эквивалентен углу в 750 градусов? Вычитая соответству-
ющее количество полных оборотов, мы получим, что угол в 750 градусов равен углу
в 30 градусов. Мы видим, что 750 = (2 х 360) + 30, то есть 30 является остатком
от деления 750 на 360. В математике это обозначается так:
750 = 30 (mod 360).
Мы говорим: «750 сравнимо с 30 по модулю 360». В случае с часами мы бы написали
14 = 2 (mod 12).
Мы также можем представить себе часы с отрицательными числами. В этом слу-
чае который будет час, когда стрелка показывает на —7? Или, другими словами,
с каким числом сравнимо число —7 по модулю 12? Давайте посчитаем, учитывая,
что на наших часах с циферблатом, разделенным на 12 частей, значение 0 соответ-
ствует 12.
-7=-7 + 0 =-7+12 =5.
ОПЕРАЦИИ ПО МОДУЛЮ
Как посчитать 231 по модулю 17 на калькуляторе?
Сначала мы разделим 231 на 17 и получим 13,58823529.
Затем найдем произведение 13 * 17 = 221. Таким образом мы избавимся от дробной части.
Наконец, найдем разность 231-221 = 10, получив остаток отделения.
Итак, 231 по модулю 17 равно 10. Этот результат записывается как 231 = 10 (mod 17)
28
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Математика для расчетов на наших часах со стрелками, циферблат которых раз-
делен на 12 частей, называется арифметикой по модулю 12. В общем случае мы го-
ворим, что a = b (mod m), если остаток от деления а на т равен Ь, при условии что а,
bum — целые числа. Число b сравнимо с остатком от деления а на т. Следующие
утверждения эквивалентны:
a = b (mod т)
b = a (mod m)
а — b = 0 (mod т)
а — b кратно т
Вопрос «Которому часу на часах со стрелками соответствует время 19 часов?»
эквивалентен в математических терминах следующему .вопросу: «С каким числом
сравнимо число 19 по модулю 12?» Чтобы ответить на этот вопрос, мы должны
решить уравнение
19 = х (mod 12).
Разделив 19 на 12, мы получим частное 1 и остаток 7, поэтому
19 = 7 (mod 12).
А в случае 127 часов? Разделив 127 на 12, мы получим частное 10 и остаток 7,
поэтому
127 = 7 (mod 12).
Чтобы повторить изученное до сих пор, давайте рассмотрим следующие опера-
ции по модулю 7:
(1)3+3 =6
(2)3 + 14=3
(3)3х3=9 = 2
(4)5x4=20 = 6
(5)7 = 0
(6)35 = 0
(7)-44 =-44 +0= —44+7x7=5
(8)- 3 3=-33 +0= -33+ 5x7=2
29
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
(1) 6 меньше, чем модуль, поэтому не меняется
(2) 3 + 14 = 17;
(3) 3 X з = 9;
(4) 5 х 4 = 20;
(5) 7 = 7;
(6) 35 = 35;
(7) _ 44 = - 44 + 0;
(8) - 33 = - 33 + 0;
17 : 7 = 2 и в остатке 3.
9 : 7 = 1 и в остатке 2.
20 : 7 = 2 и в остатке 6.
7 : 7 — 1 и в остатке 0.
35 : 7 = 5 и в остатке 0.
_ 44 + 7 X 7 = 5.
- 33 + 5 х 7 = 2.
ТАБЛИЦА УМНОЖЕНИЯ ПО МОДУЛЮ 5 В EXCEL
0 12 3 4
0 0 0 0 0 0
10 12 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Построить такую и подобные таблицы очень легко даже с базовыми знаниями офисной програм-
мы Excel. В нашем случае синтаксис функций для ячеек Excel (для столбцов и строк на нашем ком-
пьютере) показан ниже. Действие «остаток отделения числа на 5» переводится на язык Excel как
«=ОСТАТ(число;5)». Конкретная операция по нахождению произведения 4 на 3 по модулю 5 запи-
сывается как «=ОСТАТ (4*3;5)» и дает результат 2. Подобные таблицы очень помогают в расчетах
по модульной арифметике.
0 1 2 3 4
0 =0СТАТ(В$5*$А6;5) =0СТАТ(С$5*$А6:5) =0CTAT(D$5*$A6:5) =OCTAT(E$5*$A6;5) =0CTAT(F$5*$A6:5)
1 =0СТАТ(В$5*$А7;5) =0СТАТ(С$5*$А7;5) =0CTAT(D$5*$A7;5) =0CTAT(E$5*$A7;5) =OCTAT(F$5*$A7;5)
2 =0СТАТ(В$5*$А8;5) =0СТАТ(С$5*$А8;5) =0CTAT(D$5*$A8;5) =0CTAT(E$5*$A8;5) =0CTAT(F$5*$A8;5)
3 =0СТАТ(В$5*$А9;5) =0СТАТ(С$5*$А9;5) =0CTAT(D$5*$A9;5) =0CTAT(E$5*$A9;5) =0CTAT(F$5*$A9;5)
4 =0СТАТ(В$5*$А10;5) =0СТАТ(С$5*$А10;5) =OCTAT(D$5*$A10;5) =0CTAT(E$5*$A10;5) =OCTAT(F$5*$A10;5)
30
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Какая связь между модульной арифметикой и шифром Цезаря? Чтобы ответить
на этот вопрос, мы запишем в таблице стандартный алфавит и алфавит со сдвигом
на три буквы, добавив титульный ряд из 26 чисел.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
А В С D Е F G Н 1 J к L М N 0 Р Q R S Т и V W X Y Z
D Е F G Н 1 J К L М N 0 Р Q R S т и V W X Y Z А В С
Мы видим, что зашифрованное значение буквы под номером х (в стандартном
алфавите) является буквой, стоящей на позиции х + 3 (также в стандартном алфа-
вите). Поэтому необходимо найти преобразование, которое каждому числу ставит
в соответствие число, сдвинутое на три единицы, и взять результат по модулю 26.
Заметим, что 3 является ключом нашего шифра. Таким образом, наша функция за-
писывается как
С(х) = (х + 3) (mod 26),
где х — изначальное значение, а С(х) — зашифрованное значение. Теперь доста-
точно подставить вместо буквы ее числовое значение и применить трансформацию.
Возьмем в качестве примера слово PLAY и зашифруем его.
Буква Р стоит на позиции 15, С (15) = 15 + 3 = 18 (mod 26), а число 18 соот-
ветствует букве S.
Буква L стоит на позиции 11, С (И) = И + 3 = 14 (mod 26), а число 14 соот-
ветствует букве О.
Буква А стоит на позиции О, С (0) =0+3=3 (mod 26), а число 3 соответству-
ет букве D.
Буква Y стоит на позиции 24, С (24) = 24 + 3 = 27 = 1 (mod 26), а число 1 со-
ответствует букве В.
Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово
SODB.
В общем случае, если х означает позицию буквы, которую мы хотим зашифро-
вать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С(х)]
выражается формулой
С(х) = (х + k) (mod n),
где п — длина алфавита (26 в английском алфавите), a k — ключ, используемый
в данном шифре.
31
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Расшифровка такого сообщения включает в себя расчеты, обратные тем, что ис-
пользовались для шифрования. В нашем примере расшифровка означает примене-
ние формулы, обратной той, что использовалась выше:
О1 (х) = (х — k) (mod и).
В случае сообщения SODB, зашифрованного шифром Цезаря с ключом 3 с при-
менением английского алфавита, то есть k = 3 и п = 26, мы получим:
С-1 (х) = (х — 3) (mod 26).
Применим эту формулу следующим образом:
Для S: х = 18, С-1 (18) = 18—3 = 15 (mod 26), что соответствует букве Р.
Для О: х = 14, С-1 (14) = 14—3 = И (mod 26), что соответствует букве L.
Для D: х = 3, С-1 (3) = 3—3 = 0 (mod 26), что соответствует букве А.
Для В: х = 1, С-1 (1) — 1—3 = —2+26 = 24 (mod 26), что соответствует букве Y.
Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует,
как мы уже знаем, оригинальному тексту PLAY.
В заключении нашего первого знакомства с математикой криптографии мы рас-
смотрим новое преобразование, известное как аффинный шифр, частным случаем
которого является шифр Цезаря. Оно определяется следующим образом:
(*) = (а х * + b) (mod п),
где а и b — два целых числа, меньших, чем число (п) букв в алфавите. Наиболь-
ший общий делитель (НОД) чисел а и п должен быть равен 1 [НОД (а, n) = 1],
потому что иначе, как мы увидим позже, получится несколько возможностей для
шифрования одной и той же буквы. Ключ шифра определяется парой (а, Ь). Шифр
Цезаря с ключом 3 является, следовательно, аффинным шифром со значениями
а 1 и b = 3.
Обобщенный аффинный шифр имеет более высокий уровень безопасности,
чем обычный шифр Цезаря. Почему? Как мы видели, ключом аффинного шифра
является пара чисел (а, Ь). Если сообщение написано с использованием алфавита
из 26 букв и зашифровано с помощью аффинного шифра, то и а, и b могут прини-
32
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД)
Наибольший общий делитель двух чисел может быть найден с помощью алгоритма Евклида. Этот
алгоритм заключается в делении одного числа на другое, а затем проведении последовательных
делений предыдущего делителя на новый остаток. Процесс заканчивается, когда остаток равен
0. Делитель последней операции деления и будет наибольшим общим делителем данных чисел.
Например, найдем
НОД (48,30).
Разделим 48 на 30, получим остаток 18 и частное 1.
Разделим 30 на 18, получим остаток 12 и частное 1.
Разделим 18 на 12, получим остаток 6 и частное 1.
Разделим 12 на 6, получим остаток 0 и частное 2.
Мы закончили алгоритм.
НОД (48,30) = 6.
Если НОД (а, п) - 1, мы говорим, что а и л взаимно просты.
Соотношение Безу, имеющее большое значение в криптографии, устанавливает следующий факт:
для двух целых чисел аил, больших нуля, существуют целые числа к и q, такие что НОД (а, п) = ка + nq.
мать любые значения от 0 до 25. Таким образом, в этой системе шифрования с алфа-
витом из 26 букв возможное количество ключей составит 25 х 25 = 625. Заметим,
что количество ключей для алфавита из п букв в п раз больше, чем в шифре Цезаря.
Это значительное улучшение, но аффинный шифр все еще возможно расшифровать
методом перебора всех возможных вариантов.
Игра в шпионов
При каких условиях сообщение, зашифрованное аффинным шифром, может рас-
шифровать предполагаемый получатель или шпион? Мы ответим на этот вопрос,
используя простой пример шифра для алфавита из шести букв:
0 1 2 3 4 5
А В С D Е F
Текст будет зашифрован с помощью аффинного шифра С (х) = 2х + 1 (mod 6).
33
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Буква А зашифрована по формуле С (0) =2х0+1=1 (mod 6), что соответствует букве В.
Буква В зашифрована по формуле C(l) = 2xl + 1 = 3 (mod 6), что соответствует букве D.
Буква С зашифрована по формуле С (2) = 2 х 2 + 1 = 5 (mod 6), что соответствует букве F.
Буква D зашифрована по формуле С (3) = 2хЗ + 1 = 7 = 1 (mod 6), что соответствует букве В.
Буква Е зашифрована по формуле С (4) = 2х4 + 1 = 9 = 3 (mod 6), что соответствует букве D.
Буква F зашифрована по формуле С(5) = 2х5 + 1 = 11 = 5 (mod 6), что соответствует букве F.
Предлагаемый аффинный шифр преобразует сообщения АВС и DEF в одно
и то же BDF, поэтому исходное сообщение теряется. Что же случилось?
Если мы работаем с шифром, выраженным формулой С(о (х) = (ах + b) (mod и),
мы можем расшифровать сообщение однозначно, только когда НОД (а, n) = 1. В на-
шем примере НОД (2, 6) = 2 и, следовательно, не удовлетворяет этому условию.
Математическая операция расшифровки эквивалентна нахождению неизвестно-
го х при данном значении у по модулю п.
C(a,bSx^ = (ах + Ъ) = у (mod п)
(ах + Ь) = у (mod п)
ах = у — b (mod п)
Другими словами, нам нужно найти значение а-1 (обратное значению а), удов-
летворяющее равенству а~ха — 1, так что
а-1ах = я1 (у — b) (mod п)
х — а~1 (у — b) (mod и).
Следовательно, для успешной расшифровки мы должны найти число, обратное
числу а по модулю и, и, чтобы не тратить зря время, мы должны заранее знать, су-
ществует ли это обратное число.
В случае аффинного шифра С(о fc)(x) = (ах + b) (mod п) обратное значение числа
а будет существовать тогда и только тогда, когда НОД (а, n) = 1.
В случае аффинного шифра в нашем примере, С(х) = 2х + 1 (mod 6), мы хотим
узнать, существует ли обратное значение для числа а, в нашем случае для числа 2.
То есть существует ли целое число п, которое меньше 6 и удовлетворяет выражению
2 • n = 1 (mod 6). Для ответа на этот вопрос мы подставим в данное выражение всё
возможные значения (0,1,2,3,4,5):
2-0 = 0, 2-1 = 2, 2-2 = 4, 2-3 = б = 0, 2-4 = 8 = 2, 2-5=10 = 4.
Нет такого значения, следовательно, можно заключить, что 2 не имеет обратного
числа. На самом деле мы это уже знали, так как НОД (2,6) * 1.
34
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Предположим теперь, что мы перехватили зашифрованное сообщение:
YSFMG. Мы знаем, что оно было зашифровано аффинным шифром вида С(х) =
= 2х + 3 и изначально было написано на испанском языке с алфавитом из 27 букв
(включая букву N, идущую после обычной N). Как получить исходное сообщение?
Сначала мы посчитаем НОД (2,27), который равен 1. Значит, сообщение можно
расшифровать! Для этого для функции С(х) = 2х 4- 3 мы должны найти обратную
функцию по модулю 27:
у = 2х 4-3
2х = у - 3.
Чтобы найти х, мы должны умножить обе части уравнения на число, обратное 2.
Число, обратное числу 2 по модулю 27, — это целое число п такое, что 2п = 1 (mod 27),
а именно 14. И действительно:
14 • 2 = 28 = 1.
Итак, мы имеем
х = 14 • (у — 3).
Теперь мы можем расшифровать сообщение YSFMG.
Буква Y стоит на позиции 25, ей соответствует расшифрованная буква, стоящая на позиции
14 • (25-3) = 308 = И (mod 27).
Буква, стоящая в алфавите на позиции И, — это L.
Для буквы S имеем 14 • (19—3) = 224 = 8 (mod 27), эта позиция соответствует букве I.
Для буквы F имеем 14 • (5—3) = 28 = 1 (mod 27), что соответствует букве В.
Для буквы М имеем 14 • (12—3) = 126 = 18 (mod 27), что соответствует букве R.
Для буквы G имеем 14 • (6—3) = 42 = 15 (mod 27), что соответствует букве О.
Расшифрованное сообщение является испанским словом LIBRO, что означает
«книга».
За пределами аффинного шифра
Различные системы безопасности на протяжении многих веков использовали идею
Цезаря и ее обобщение в виде аффинного шифра. В настоящее время любой шифр,
в котором каждая буква исходного сообщения заменяется на другую букву, сдвинутую
на фиксированное число позиций (не обязательно три), называется шифром Цезаря.
Одним из существенных достоинств хорошего алгоритма шифрования является
способность генерировать большое количество ключей. И шифр Цезаря, и аффин-
ный шифр уязвимы для криптоанализа, поскольку максимальное количество ключей
ограничено.
35
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Если мы снимем какие-либо ограничения относительно порядка букв шифро-
алфавита, то потенциальное количество ключей резко возрастет. Количество ключей
для стандартного алфавита из 26 символов (расположенных в произвольном поряд-
ке) составляет 26! = 403291461126605635584000000, то есть более 403 сеп-
тиллионов ключей. Криптоаналитику, который тратит на проверку одного ключа
всего лишь одну секунду, потребуется в миллиард раз больше времени, чем ожидае-
мое время существования Вселенной, чтобы исчерпать все возможности!
Вот один из примеров такого обобщенного шифра подстановки:
(1) А в С D Е F G Н 1 J к L м N 0 Р Q R S Т и V W X Y Z
(2) Q W Е R Т Y и 1 0 р А S D F G Н J К L Z X с V в N м
Строка (1) — алфавит открытого сообщения. Строка (2) — шифроалфавит.
Первые шесть букв шифроалфавита дают подсказку к выбранному порядку букв:
он соответствует порядку букв на клавиатуре в стандарте QWERTY. Чтобы за-
шифровать известное высказывание Цезаря VENI VIDI VICI («Пришел, увидел,
победил») шифром QWERTY, для каждой буквы алфавита открытого сообщения
мы найдем соответствующую в шифроалфавите.
(1) А в с D Е F G Н 1 J к L м N 0 Р Q R S Т и V W X Y Z
(2) Q W Е R Т Y и 1 0 р А S D F G Н J К L Z X с V в N м
Мы получим следующее зашифрованное послание:
CTFO CORO СОЕО
Существует очень простой способ для генерации почти неисчерпаемого количе-
ства легко запоминающихся шифров для шифрования этим методом. Достаточно
выбрать любое ключевое слово (это может быть даже фраза), поместить его в на-
чале шифроалфавита и, начиная с последней буквы ключевого слова, завершить ряд
буквами стандартного алфавита, следующими в обычном порядке, исключив лишь
повторяющиеся буквы. Возьмем в качестве примера ключевую фразу JANUARY
CIPHER («январский шифр»). Сначала мы избавимся от пробела и одинаковых
букв, получив ключевое слово JNUYCIPHE. В результате наш шифроалфавит бу-
дет выглядеть так:
36
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
А В С D Е F G Н 1 J К L М N О р Q R S т и V W X Y Z
J N и Y С 1 Р Н Е F G К L М О Q R S Т V W X Z А В D
Сообщение VENI VIDI VICI теперь будет зашифровано как ХСМЕ XEYE
XEUE. Такая система генерации шифров легко обновляется и почти исключает ошиб-
ки со стороны отправителя и получателя. В нашем примере было бы достаточно
менять ключевое слово каждый месяц — JANUARY CIPHER (январский шифр),
FEBRUARY CIPHER (февральский шифр), MARCH CIPHER (мартовский
шифр) и т. д. — то есть после изначального выбора шифра стороны могут обойтись
без дополнительных соглашений.
Надежность и простота алгоритма шифра подстановки с использованием ключе-
вых слов сделали его самой распространенной системой шифрования на протяжении
многих веков. В прежние времена считалось, что криптографы все-таки взяли верх
над криптоаналитиками.
ШИФРОВАНИЕ СЛОВА БОЖЬЕГО
Средневековые криптоаналитики считали, что в Ветхом Завете тоже использовались шифры,
и они не ошиблись. Существует несколько фрагментов из священных текстов, которые зашифро-
ваны с помощью шифра подстановки, называемого атбаш. Этот шифр состоит в замене каждой
буквы (л) другой буквой, которая находится в алфавите на таком же расстоянии от конца ал-
фавита, как оригинальная буква -
от начала. Например, в латинском
алфавите буква А заменяется на Z,
буква В - на Y и т.д. В оригиналь-
ном Ветхом Завете использовались
буквы еврейского алфавита. Так,
в книге пророка Иеремии (25:26)
слово «Бабель» (Вавилон) зашиф-
ровано как «Шешах».
Еврейская Библия
начала XVIII в.
37
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Частотный криптоанализ
Коран состоит из 114 глав, каждая из которых соответствует одному из открове-
ний, полученных пророком Мухаммедом. Эти откровения были записаны во время
жизни пророка различными его спутниками и позднее собраны воедино по решению
первого халифа Абу Бакра. Умар и Усман, второй и третий халифы соответственно,
завершили проект. Фрагментарный характер оригинальных писаний привел к рож-
дению области богословия, посвященной точной датировке различных откровений.
В частности, ученые-корановеды определили частоту появления некоторых слов,
считавшихся новыми в периоды записи откровений. Если в каком-то откровении со-
держалось достаточное количество таких новых слов, было логично заключить, что
это сравнительно позднее откровение.
Рукопись Корана. XIV в.
Этот подход стал первым конкретным инструментом криптоанализа, получив-
шим название частотного анализа. Первым человеком, оставившим письменное
упоминание об этом революционном методе, был философ по имени Аль-Кинди,
который родился в Багдаде в 801 г. Хотя он был астрономом, врачом, математи-
ком и лингвистом, прославился он как создатель манускрипта по криптоанализу.
Даже если Аль-Кинди не был первым, его имя, безусловно, занимает важное ме-
сто в истории криптоанализа.
38
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
До недавнего времени очень мало было известно о новаторской роли Аль-Кинди.
В 1987 г. в одном из архивов Стамбула была обнаружена копия его трактата «Ма-
нускрипт о дешифровке криптографических сообщений». Он содержит краткое из-
ложение революционного метода:
«Чтобы расшифровать зашифрованное сообщение, если мы знаем, на каком
языке оно было написано, надо взять достаточно длинный текст, написанный
на том же языке, а затем подсчитать, сколько раз каждая буква встречает-
ся в этом отрывке. Назовем наиболее часто встречающуюся букву «первой»,
вторую по частоте — «второй», и так далее, пока не переберем все буквы это-
го отрывка. Затем вернемся к криптограмме, которую мы хотим расшифро-
вать, и классифицируем ее символы тем же образом: найдем в криптограмме
символ, встречающийся чаще всех, и заменим его на «первую» букву из про-
анализированного текста, затем перейдем ко второму по частоте символу и за-
меним его на «вторую» букву, и так далее, пока не переберем все символы,
используемые в криптограмме».
На предыдущих страницах манускрипта Аль-Кинди упоминает, что в шифре
подстановки каждая буква исходного сообщения «сохраняет свою позицию, но ме-
няет свою роль», и именно это «сохранение позиции» делает метод уязвимым для
частотного криптоанализа. Гениальный Аль-Кинди изменил соотношение сил меж-
ду криптографами и криптоаналитиками, по крайней мере на какое-то время, в поль-
зу последних.
Подробный пример
Вот как встречаются буквы латинского алфавита — от наибольшей до наименьшей
частоты — в текстах на английском языке: ETAOINSHRDLCUMWF
GYPBVKJXQZ. Частота появления (в процентах) каждой буквы показана
в следующей таблице.
А 8,17% Н 6,09% 0 7,51% V 0,98%
В 1,49% 1 6,97% Р 1,93% W 2,36%
С 2,78% J 0,15% Q 0,10% X 0,15%
D 4,25% К 0,77% R 5,99% Y 1,97%
Е 12,70% L 4,03% S 6,33% Z 0,07%
F 2,29% М 2,41% Т 9,06%
G 2,02% N 6,75% и 2,76%
39
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Если сообщение было зашифровано с использованием шифра подстановки, как
те, что описаны выше, его можно расшифровать в соответствии с относительной ча-
стотой, с которой встречаются буквы исходного сообщения. Достаточно посчитать
частоту появления каждой зашифрованной буквы и сравнить ее с таблицей частот
в языке, на котором сообщение было написано. Так, если буква J чаще всего встре-
чается в зашифрованном тексте, она, скорее всего, соответствует букве Е в ориги-
нальном сообщении (в случае английского языка). Если вторая по частоте появления
в зашифрованном тексте будет буква Z, те же рассуждения приводят нас к выводу,
что ей, скорее всего, соответствует буква Т. Криптоанализ завершается повторени-
ем процесса для всех букв зашифрованного текста.
Очевидно, что частотный метод не всегда может быть так легко применим. Ча-
стоты, указанные в таблице, справедливы лишь в среднем. В коротких текстах, та-
ких как Visit the zoo kiosk for quiz tickets («Билеты викторины продаются в кассе
зоопарка»), относительная частота появления букв сильно отличается от частоты,
ШЕРЛОК ХОЛМС, КРИПТОАНАЛИТИК
Расшифровка с использованием частотного анализа - очень драматичный метод, который
привлекал внимание большого количества авторов. Возможно, самая известная история, ос-
нованная на криптоанализе тайного послания, описана Эдгаром Алланом По в 1843 г. в рас-
сказе «Золотой жук». В Приложении содержится подробный разбор вымышленного послания,
зашифрованного Эдгаром По, и его блестящая расшифровка с использованием частотного
анализа. Другие писатели, такие как Жюль Верн и Артур Конан Дойл, использовали подобные
идеи, чтобы добавить драматизма в сюжеты своих произведений. Герой рассказа Дойла «Пля-
шущие человечки», Шерлок Холмс, также сталкивается с шифром подстановки, что заставляет
детектива обратиться к частотному анализу. Более 1000 лет спустя гениальная идея Аль-Кинди
все еще привлекает людей своей красотой.
Первое из закодированных сообщений, которые Шерлок Холмс должен был
расшифровать в рассказе «Пляшущие человечки». Мы не будем его здесь расшифровывать,
чтобы не открывать всех секретов будущим читателям книги. Добавим только, что флажки
у танцующих человечков представляют собой важный элемент шифра.
40
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
характерной для языка в целом. По сути, для текстов, содержащих менее 100 сим-
волов, такой простой анализ редко бывает полезен. Частотный анализ, однако,
не ограничивается только изучением букв. Как мы видели, маловероятно, что в ко-
роткой криптограмме наиболее часто встречающейся буквой будет Е, но с большей
уверенностью можно сказать, что пять наиболее часто встречающихся букв, скорее
всего, будут А, Е, I, О и Т, хотя мы и не знаем, каким именно символам они соот-
ветствуют. В английском языке А и I никогда не появляются в паре, в то время как
другие буквы могут. Более того, независимо от длины текста, гласные, как правило,
чаще появляются в начале и в конце группы других букв, а согласные чаще встре-
чаются с гласными или в коротких словах. Таким образом, нам, возможно, удастся
отличить Т от А, Е, I и О. После успешной расшифровки некоторых букв в крипто-
грамме появятся слова, в которых осталось расшифровать только один или два сим-
вола, что позволит нам строить гипотезы, каким буквам эти символы могут соответ-
ствовать. Скорость расшифровки увеличивается с количеством разгаданных букв.
Полиалфавитный шифр
8 февраля 1587 г. Мария Стюарт, королева Шотландии, была обезглавлена в зам-
ке Фотерингей после признания ее виновной в государственной измене. Судебное
разбирательство, приведшее к такому суровому приговору, установило, что Мария,
вне всяких сомнений, была в сговоре с группой католических аристократов, воз-
главляемой молодым Энтони Бабингтоном. В их планы входило убийство англий-
ской королевы Елизаветы I и возведение Марии на трон католического царства,
охватывающего Англию и Шотландию. Решающие доказательства были добыты
контрразведкой Елизаветы во главе с лордом Уолсингемом. Из переписки между
Марией и Бабингтоном стало ясно, что молодая шотландская королева знала о же-
стоком плане и одобрила его. Эти письма были зашифрованы с помощью алгоритма,
который использовал и шифры, и коды: не только одни буквы заменялись други-
ми, но и вместо некоторых общеупотребительных слов использовались специальные
символы. Шифроалфавит Марии представлен ниже:
abcdefghiklmnopqrstuxyz
of ft -ж- С 6 ОО I § X II $ V J ГЛ -f А Ь С 7 g 9
41
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
За исключением того, что буквы заменялись символами, шифр Марии ничем
не отличался от любых других, которые криптографы во всем мире использовали
в течение многих столетий. Молодая королева и ее сообщники были убеждены, что
шифр надежен, но, к сожалению для них, лучший криптоаналитик Елизаветы, Томас
Фелиппес, был экспертом в частотном анализе и смог расшифровать письма Марии
без особых трудностей. Провал того, что стало известно как Заговор Бабингто-
на, показал правительствам и тайным агентам всей Европы, что обычный алгоритм
шифра подстановки уже не безопасен. Криптографы оказались бессильными перед
новыми методами расшифровки.
* * 'fa** o o
р'<*-
Фрагмент одного из писем шотландской королевы Марии Стюарт к ее сообщнику Энтони
Бабингтону. За это письмо ее в конечном счете осудили на смерть.
Идея Альберти
Тем не менее, средство против частотного анализа было найдено за сто лет до того,
как Мария взошла на эшафот. Отцом нового шифра стал выдающийся ученый эпохи
Возрождения Леон Баттиста Альберти. Более известный как архитектор и матема-
тик, внесший большой вклад в изучение перспективы, в 1460 г. Альберти разрабо-
тал систему шифрования, которая состояла в использовании двух шифроалфавитов,
как показано в следующей таблице:
42
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
(1) А В С D Е F G н 1 J К L М N 0 Р Q R S т и V W X У Z
(2) D Е F G Н 1 J к L М N 0 Р Q R S Т и V W X У Z А В с
(3) М N В V С X Z L К J Н G F D S А Р 0 1 и У т R Е W Q
Строка (1) — стандартный алфавит. Строка (2) — первый шифроалфавит.
Строка (3) — второй шифроалфавит.
Для зашифровки какого-либо сообщения Альберти предложил чередовать два
шифроалфавита. Например, в случае слова SHEEP («овца») шифр для первой
буквы берется из первого алфавита (V), а шифр для второй буквы — из второго
алфавита (L), и так далее. В нашем примере слово SHEEP будет зашифровано как
VLHCS. Преимущество такого алгоритма полиалфавитного шифрования по срав-
нению с предыдущими видно сразу: буква Е исходного слова шифруется двумя раз-
личными способами — как Н и С. Чтобы еще больше запутать криптоаналитика,
пытающегося расшифровать этот текст, одна и та же буква криптограммы соответ-
ствует двум разным буквам оригинального текста. Частотный анализ, таким обра-
зом, теряет значительную часть своей силы. Альберти так нигде и не записал свои
идеи, поэтому шифр был позже разработан примерно в одно и то же время, но неза-
висимо друг от друга двумя учеными: немцем Иоганном Тритемием и французом
Блезом де Виженером.
Квадрат Виженера
В шифре Цезаря используется одноалфавитный шифр подстановки; один шифро-
алфавит соответствует алфавиту открытого текста, так что одна зашифрованная
буква соответствует одной и той же букве исходного текста. (В классическом шифре
Цезаря буква D всегда соответствует букве А, Е — В, и так далее).
В полиалфавитном же шифре определенной букве открытого сообще-
ния может быть сопоставлено столько букв, сколько используется шифро-
алфавитов. Для зашифровки текста при переходе от одной буквы сообщения к дру-
гой используются различные шифроалфавиты. Первой и самой известной поли-
алфавитной системой шифрования был так называемый квадрат Виженера. Его
таблица алфавитов состояла из стандартного алфавита из п букв, под которым
стояли п шифроалфавитов, сдвинутых циклически на одну букву влево по сравне-
нию с вышестоящим алфавитом. Другими словами, это была квадратная матрица
из 26 строк и 26 столбцов, изображенная на следующей странице.
43
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Обратите внимание на симметрию в расположении букв. Пара (A, R) = (R, А)
и это же соотношение справедливо для всех букв.
ABCDEFGHI J К
1 A abcdefghijk
2 В bcdefghijkl
3 С cdefghijklm
4 D defghijklmn
5 Е efghijklmno
6 F fghtjklmnop
7 G ghijklmnopq
8 H hijklmnopqr
9 I ijklmnopqrs
10 J jklmnopqrst
И К klmnopqrstu
12 L Imnopqrstuv
13 M mnopqrstuvw
14 N nopqrstuvwx
15 0 opqrstuvwxy
16 P pqrstuvwxyz
17 Q qrstuvwxyza
18 R rstuvwxyzab
19 S stuvwxyzabc
20 T tuvwxyzabcd
21 U uvwxyzabcde
22 V vwxyzabcdef
23 W wxyzabcdefg
24 X xyzabcdefgh
25 Y yzabcdefghi
26 Z zabcdefghij
L M N OPQRSTUVWXYZ
Imn opqrstuvwxyz
mno pq rstuvwxyza
nop q rstuvwxyzab
opq rstuvwxyzabc
pqrstuvwxyzabcd
qrs tuvwxyzabcde
rst uvwxyzabcdef
stu vwxyzabcdefg
tuvwxyzabcdefgh
uvwxyzabcdefghi
vwx yzabcdefghij
wxy zabcdefgh i j k
xyz abcdefghi j k I
yza bcdefgh ij k I m
zab cdefghi j k Imn
abcdefghijklmno
bcdefghijklmnop
cde fghijklmnopq
def gh ijklmnopqr
efgh i jklmnopqrs
f g ti i j klmnopqrst
gh i j k Imnopqrstu
hij k Imnopqrstuv
i j k Imnopqrstuvw
j k I mnopqrstuvwx
k Imnopqrstuvwxy
Мы видим, что квадрат Виженера содержит стандартный алфавит из п букв,
повторяющийся п раз с различными увеличивающимися параметрами. Так, первый
шифроалфавит получается применением шифра Цезаря с параметрами а = 1 и b =
2; второй — эквивалентен шифру Цезаря с b = 3 и так далее. Ключом к квадрату
Виженера является правило для каждой буквы, которое указывает, на сколько строк
вниз надо спуститься, чтобы найти зашифрованное значение, соответствующее этой
букве. Простейший ключ состоит из движения вниз на одну строку при переходе
от одной буквы исходного сообщения к другой.
44
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
ИГРА С ДИСКАМИ
На практике для полиалфавитного шифрования используется устройство, известное как шиф-
ровальный диск Альберти. Этот портативный прибор состоит из двух концентрических дисков:
один - фиксированный, с выгравированным на нем стандартным алфавитом, второй - подвиж-
ный, с другим алфавитом. Отправитель, поворачивая подвижный диск, может сопоставить стан-
дартный алфавит с разными шифроалфавитами в зависимости от числа поворотов диска, макси-
мальное количество которых равно числу букв используемого алфавита. Шифр, полученный с по-
мощью диска Альберти, очень устойчив к частотному анализу. Чтобы расшифровать сообщение,
получатель должен сделать то же число оборотов, что и отправитель. Безопасность этого шифра,
как всегда, зависит от сохранения в тайне кода, а именно - от распо-
ложения алфавита на подвижном диске плюс число необходимых
поворотов. Диск Альберти с одним подвижным кольцом, на ко-
тором выгравирован стандартный алфавит, дает шифр Цезаря
при каждом повороте. Аналогичные устройства использова-
лись во время Гражданской войны в США, и сегодня их можно
встретить в детских шпионских играх.
Диск Альберти, используемый Конфедерацией во время
американской гражданской войны.
Таким образом, наша классическая фраза VENI VIDI VICI будет зашифрована
следующим образом:
Для шифрования первой V мы найдем соответствующую букву в строке 2: W.
Для шифрования Е мы найдем соответствующую букву в строке 3: G.
Для шифрования N мы найдем соответствующую букву в строке 4: Q.
I (строка 5): М.
V (строка 6): А.
I (строка 7): О.
D (строка 8): К.
I (строка 9): Q.
V (строка 10): Е.
I (строка И): S.
С (строка 12): N.
I (строка 13): U.
45
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
ДИПЛОМАТ И КРИПТОГРАФ
Блез де Виженер родился во Франции в 1523 г. В 1549 г.
он был послан французским правительством с дипломати-
ческой миссией в Рим, где заинтересовался криптографи-
ей и шифрованием сообщений. В 1585 г. он написал ос-
новополагающий трактат о шифрах, Traicte des Chiffres, где
описывалась система шифрования, которой он дал свое
имя. Эта система шифрования оставалась неподдающейся
взлому на протяжении почти трех столетий, пока британцу
Чарльзу Бэббиджу не удалось взломать ее в 1854 г. Лю-
бопытно, что этот факт стал известен лишь в XX в., когда
группа ученых разбирала вычисления и личные заметки
Бэббиджа.
В результате наша фраза превратится в WGQM AOKQ ESNU. При этом по-
вторяющиеся буквы исходного сообщения исчезнут. Однако каждый криптограф
стремится к тому, чтобы генерировать шифры, которые легко запомнить, распро-
странять и обновлять. Тогда стали брать ключевые слова с таким же или меньшим
количеством букв, что и в исходном сообщении, чтобы строить более короткие
и легкие в использовании квадраты Виженера. Ключевое слово дает первые буквы
каждой строки (см. стр. 47), и строки продолжаются остатком алфавита (как они
представлены в полном квадрате). Затем ключевое слово, повторенное нужное ко-
личество раз, пишется под буквами сообщения, которое необходимо было зашифро-
вать. Буква ключевого слова под каждым символом сообщения подсказывала крип-
тографу строку в матрице, из которой нужно было взять зашифрованное значение
этой буквы.
Например, если мы хотим зашифровать сообщение BUY MILK TODAY
(«Купи сегодня молоко») с помощью ключевого слова JACKSON:
Исходное сообщение В и Y М 1 L к т О D А Y
Ключевое слово J А С К S О N J А С К S
Зашифрованное сообщение К и А W А Z X с О F К Q
Зашифрованное сообщение будет KUAWAZXCOFKQ.
46
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
А В С D E F G H 1 J К L M N 0 P QRSTUVWX Y Z
J j k 1 m n о P q r s t u V W X У z a b c d e f g h i
А abed e f g h i j к 1 m n 0 P q r s t u v w x У z
С с d е f g h i j к 1 m n о P q r s tuvwx yz a b
К к 1 m n 0 P q r s t u v w x у z a bedef gh i j
S s t u V w x у z a b c d e f g h i j к 1 m n о p q r
0 о p q r s t U V w X у z a b c d e f g h i j к 1 m n
N n о p q r Stu v w x у z a b c d e f g h i j к 1 m
Квадрат Виженера со строками, определенными ключевым словом JACKSON.
Как и в случае всех классических систем шифрования, расшифрованный текст
сообщения, зашифрованного с помощью квадрата Виженера, является симметрич-
ным исходному тексту. Например, пусть у нас есть зашифрованное сообщение
WZPKGIMQHQ, и мы знаем, что использовалось ключевое слово WINDY:
Исходное сообщение ? ? ? ? ? ? ? ? ? ?
Ключевое слово W 1 N D Y W 1 N D У
Зашифрованное сообщение W Z Р К G 1 м Q Н Q
Давайте посмотрим на первый столбик. Мы хотим найти неизвестную букву «?»,
зная, что (?, W) = W. Для этого мы посмотрим на строку W квадрата Виженера
на стр. 44, найдем в этой строке букву W и определим, какому столбцу она со-
ответствует; получим букву А. Аналогично мы ищем вторую букву «?», зная, что
(?, I) = Z, и получаем букву R и так далее. Таким образом мы получим исходное
сообщение ARCHIMEDES («Архимед»).
Историческое значение квадрата Виженера, которое он разделяет и с другими поли-
алфавитными шифрами, например, с шифром Гронсфельда (разработанным примерно
в то же время; мы приводим его подробное описание в Приложении), состоит в устой-
чивости к частотному анализу. Если одна и та же буква может быть зашифрована
несколькими способами с возможностью тем не менее ее впоследствии расшифровать,
как же можно такой шифр взломать? Этот вопрос оставался без ответа более 300 лет.
Классификация алфавитов
Хотя на это потребовалось почти восемь веков, полиалфавитные шифры, такие как
квадрат Виженера, наконец-то переиграли частотный анализ. Однако моноалфавит-
47
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
ные шифры, несмотря на свои слабые стороны, имели особое преимущество: про-
стоту реализации. Криптографы посвятили себя совершенствованию алгоритмов,
наполняя их трюками, но принципиально они продолжали использовать ту же идею,
что и для простейших шифров.
Одним из наиболее успешных вариантов моноалфавитного шифра был так назы-
ваемый однозвучный шифр подстановки, который пытался защититься от методов
статистического криптоанализа, заменяя буквы с наибольшей частотой появления
несколькими разными символами. Например, частота появления буквы Е в среднем
составляет 10 % в любом языке. Однозвучный шифр подстановки пытался изменить
эту частоту, заменяя букву Е десятью альтернативными символами. Такие методы
были популярны вплоть до XVIII в.
КРИПТОГРАФЫ КОРОЛЯ-СОЛНЦА
Хотя мало кто за пределами королевского двора Людовика XIV знал об их существовании,
Антуан и Бонавентура Россиньоль принадлежали к числу самых грозных людей Европы во вре-
мена социальных потрясений XVII в. Они обладали незаурядным криптографическим талан-
том, что позволяло им расшифровывать письма врагов Франции (и личных врагов монар-
ха). Они разработали Grande Chiffre
(Великий шифр), сложный алгоритм
замены слогие используемый для
шифрования самых важных писем ко-
роля. После смерти Россиньоль шифр
вышел из употребления и считался
невзламываемым. Лишь в 1890 г.
специалист по криптографии, от-
ставной солдат Этьен Базарье взял
на себя трудоемкую задачу расшиф-
ровки документов и после многих лет
напряженной работы смог прочитать
секретные послания Короля-Солнца.
Людовик XIV, портрет работы
Миньяра
48
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
Время все же не стояло на месте. Образование больших национальных госу-
дарств и развитие дипломатии вызвали заметное возрастание требований к безопас-
ности коммуникации. Эта тенденция еще больше усилилась с появлением новых
коммуникационных технологий, таких как телеграф, в результате чего значитель-
но увеличилось количество передаваемых сообщений. В европейских странах были
созданы так называемые «черные кабинеты», где кодировалась самая конфиден-
циальная корреспонденция и расшифровывались перехваченные сообщения врагов.
Экспертные возможности «черных кабинетов» вскоре сделали небезопасными лю-
бые формы одноалфавитного шифра подстановки, как бы он ни модифицировался.
Мало-помалу ведущие игроки на поле обмена информацией избирали полиалфа-
витные алгоритмы. Утратив свое самое мощное оружие, частотный анализ, крипто-
аналитики в очередной раз оказались беззащитными перед натиском криптографов.
Анонимный криптоаналитик
Английский математик Чарльз Бэббидж (1791—1871) был одним из самых выдаю-
щихся научных деятелей XIX в. Он изобрел механический компьютер, названный
разностной машиной, далеко опередив свое время, и в сферу его интересов входили
все отрасли математики и технологии того века. Бэббидж решил применить свои
знания к расшифровке полиалфавитных алгоритмов, в первую очередь квадрата Ви-
женера (см. стр. 44 и 47). Он сосредоточил внимание на одной особенности это-
го шифра. Напомним, что в случае шифра Виженера длина выбранного ключевого
слова определяла количество используемых шифроалфавитов. Таким образом, если
ключевое слово было WALK, каждая буква исходного сообщения могла быть за-
шифрована четырьмя разными способами. То же самое справедливо и для слов. Эта
особенность и была ключевой зацепкой для Бэббиджа, позволившей ему взломать
полиалфавитный шифр. Рассмотрим следующий пример, где сообщение зашифрова-
но с помощью квадрата Виженера.
Исходное сообщение В Y L А N D О R В Y S Е А
Ключевое слово W А L К W А L К W А L К W
Зашифрованное сообщение X Y W К J D Z В X Y D 0 W
Наше внимание сразу привлекает то, что слово BY исходного сообщения шифруется
в обоих случаях одинаково — XY. Это связано с тем, что второй раз BY встреча-
49
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
ется после восьми символов, а восемь кратно количеству букв (четыре) в ключевом
слове (WALK). Обладая этой информацией и имея достаточно длинный исходный
текст, можно догадаться, какова длина ключевого слова. Процедура заключает-
ся в следующем: вы отмечаете все повторяющиеся символы и записываете, через
сколько позиций они повторяются. Затем вы находите все делители этих чисел. Об-
щие делители и являются кандидатами на длину ключевого слова.
Предположим, что наиболее вероятный кандидат — число 5, потому что это об-
щий делитель, который встречается чаще всего. Теперь мы попытаемся догадаться,
каким буквам соответствует каждая из пяти букв ключевого слова. Как мы помним,
каждая буква ключевого слова в квадрате Виженера определяет моноалфавтный
шифр для соответствующей буквы в исходном сообщении. В случае нашего гипоте-
тического ключевого слова из пяти букв (Cl, С2, СЗ, С4, С5) шестая буква (С6)
шифруется тем же алфавитом, что и первая буква (С1), седьмая (С7) — тем же,
что и вторая (С2), и так далее. Поэтому на самом деле криптоаналитик имеет дело
Рабочая часть разностной
машины Бэббиджа, построен-
ной в 1991 г. в соответствии
с чертежами, оставленными
ее изобретателем. Устройство
позволяет находить прибли-
женные значения логарифми-
ческих и тригонометрических
функций и, следовательно,
делать расчеты астрономи-
ческих таблиц. Бэббидж не
успел при жизни увидеть свою
машину.
50
КРИПТОГРАФИЯ ОТ АНТИЧНОСТИ ДО XIX ВЕКА
с пятью отдельными моноалфавитными шифрами, каждый из которых уязвим для
традиционного криптоанализа.
Процесс завершается составлением таблицы частот для всех букв в зашифро-
ванном тексте, соответствующих буквам ключевого слова (Cl, С6, СИ ... и С2,
С7, С12 ...). Таким образом, получается пять групп букв, вместе составляющих
все сообщение. Затем, чтобы расшифровать ключевое слово, эти таблицы частот
сравниваются с таблицами частот языка, на котором написано исходное сообщение.
Если таблицы не совпадают, процесс повторяется с другой вероятной длиной ключе-
вого слова. Как только мы определим ключевое слово, останется только расшифро-
вать исходное сообщение. С помощью этого метода и был взломан полиалфавитный
шифр.
Поразительные работы Бэббиджа, завершенные около 1854 г., так бы и оста-
лись в безвестности. Эксцентричный британский интеллектуал не опубликовал свое
открытие, и только недавние исследования его записок показали, что именно он был
пионером в расшифровке полиалфавитных ключевых слов. К счастью для крипто-
аналитиков всего мира, несколько лет спустя, в 1863 г., прусский офицер Фридрих
Касиски опубликовал аналогичный метод.
Независимо от того, кто первый взломал его, полиалфавитный шифр перестал быть
неприступным. С этого момента сила шифра стала зависеть не столько от алгорит-
мических нововведений шифрования, сколько от количества используемых шифро-
алфавитов, которое должно быть достаточно большим, чтобы сделать частотный
анализ и его варианты совершенно бесполезными. Параллельной целью был поиск
способов ускорения криптоанализа. Обе цели пересеклись в одной точке и породили
один и тот же процесс: компьютеризацию.
51
Глава 3
Шифровальные машины
В XIX в. шифрование оказалось полезным не только для пересылки секретных со-
общений. Появление телеграфа в первой трети века и затем, спустя 30 лет, развитие
двусторонней телеграфной связи Томасом Альвой Эдисоном произвело революцию
в коммуникации и, следовательно, изменило мир. Так как телеграф использовал
электрические импульсы, нужен был метод для перевода текста сообщения на язык,
который машина может воспроизвести и передать. Другими словами, необходимо
было кодирование. Среди различных предложенных методов верх взяла система
передачи букв точками и тире, придуманная американским художником и изобрета-
телем Сэмюэлом Морзе. Азбуку Морзе можно считать предшественником кодов,
которые многие десятилетия спустя неявно используются всеми нами для ввода дан-
ных в компьютеры и получения информации от них.
Азбука Морзе
Азбука Морзе использует комбинацию точек, тире и пробелов для представления
букв алфавита, цифр и других символов. Таким образом, она переводит алфавит
в набор знаков, которые могут быть выражены с помощью простых сигналов света,
звука или электричества. Каждая точка соответствует единице времени продолжи-
тельностью около 1/25 доли секунды; каждое тире — три единицы времени (эк-
вивалентно трем точкам). Длина пробелов между буквами — также три единицы
времени, а пять единиц соответствуют пробелам между словами.
Сначала Морзе было отказано в патенте на этот код и в Соединенных Штатах,
и в Европе. Лишь в 1843 г. он получил государственную субсидию для строительства
телеграфной линии между Вашингтоном и Балтимором. В 1844 г. была произведена
первая передача закодированного сообщения, и почти сразу была создана компания
с целью охвата всей Северной Америки телеграфными линиями. К 1860 г., когда
Наполеон III наградил Морзе орденом Почетного легиона, Соединенные Штаты
и Европа уже были опутаны телеграфными проводами. К моменту смерти Морзе
в 1872 г. в Америке было проложено более 300000 километров кабеля.
Сначала простое устройство, изобретенное в 1844 г. самим Морзе, использова-
лось для передачи и приема телеграфных сообщений. Оно состояло из телеграфного
53
ШИФРОВАЛЬНЫЕ МАШИНЫ
НЕВЕРБАЛЬНАЯ КОММУНИКАЦИЯ
Так какТомас Альва Эдисон (1847-1931) плохо слышал, он общался со своей женой, Мэри Стиу-
элл, с помощью азбуки Морзе. Во время ухаживания Эдисон сделал предложение, отстучав слова
рукой, и она ответила тем же способом. Телеграфный код стал обычным средством общения для
супругов. Даже когда они ходили в театр, Эдисон клал руку Мэри себе на колено, чтобы она могла
«телеграфировать» ему диалоги актеров.
ключа, который служил для включения и отключения электрического тока, а также
электромагнита, который получал поступающие сигналы. Каждый раз, когда на-
жимался ключ, — как правило, указательным или средним пальцем — возникал
электрический контакт. Периодические импульсы, производимые нажатием теле-
графного ключа, передавались по кабелю, состоящему из двух медных проводов.
Эти провода, поддерживаемые высокими деревянными «телеграфными» столбами,
связывали различные телеграфные станции страны и часто тянулись на сотни кило-
метров.
Первый телеграфный аппарат, изобретенный Сзмюзлом Морзе в 1844 г.
54
ШИФРОВАЛЬНЫЕ МАШИНЫ
СИМФОНИЯ V-МАЖОР
Бетховен - еще один плохослышащий знаменитый человек, имя которого связано с телеграфом,
хотя в данном случае лишь косвенно: первые четыре ноты Пятой Симфонии гениального компо-
зитора по ритму напоминают сообщение в азбуке Морзе: «точка точка точка тире».
В азбуке Морзе «точка точка точка тире» соответствуют букве V, первой букве английского
слова «victory» («победа»). Поэтому на «Би-би-си» Пятая симфония Бетховена использовалась как
позывные радиостанции перед началом всех трансляций для оккупированной Европы во время
Второй мировой войны.
В приемном устройстве имелся электромагнит, представлявший собой катушку
из медной проволоки, обмотанной вокруг железного сердечника. Когда катушка по-
лучала импульсы электрического тока, соответствующие точкам и тире, железный
сердечник намагничивался и притягивал подвижную часть, также сделанную из же-
леза. Она издавала характерный звук при ударе о магнит. Этот звук слышен как
короткий «щелчок», если получена точка, и как более длительная нота — при полу-
чении тире. Первое время для отправки телеграммы с помощью такого устройства
требовался человек-оператор, который настукивал кодированную версию сообщения
на одном конце, и еще один человек получал и расшифровывал текст на другом конце.
Кодирование символов по азбуке Морзе производилось в соответствии со сле-
дующей таблицей:
Символ Код Символ Код Символ Код Символ Код Символ Код Символ Код
А G N и 0 — 7 —
В — Н 0 — V 1 — 8 —
С — 1 Р — W 2 — 9 —
СН — J — Q — X — 3 — —
D К — R Y — 4 — —
Е L .... S Z — 5 —
F — М -- Т - 6 — —
55
ШИФРОВАЛЬНЫЕ МАШИНЫ
Так, сообщение: «I love you» («Я тебя люблю») будет закодировано следующим
образом:
1 L О V Е Y О и
— — — — — —
Как уже говорилось ранее, азбука Морзе была в некотором смысле первым ва-
риантом будущих цифровых систем связи. Чтобы продемонстрировать эту идею, мы
легко можем преобразовать код Морзе в числа, заменяя каждую точку единицей,
а каждое тире — нулем. Строки из нулей и единиц часто будут встречаться нам
в следующих главах.
В XX в. благодаря изобретению радио традиционный телеграф заменила беспро-
водная связь. Телеграфисты недавнего прошлого стали радистами. Новая технология
позволила обмениваться информацией с еще большей скоростью и в большем объеме.
Однако сообщения, посылаемые в виде электромагнитных волн, можно относительно
легко перехватить. Это обеспечило криптоаналитиков большим количеством зашиф-
рованного материала и помогло укрепить их позиции в борьбе с криптографами, по-
тому что большинство шифров, используемых правительствами и тайными агентами,
даже самые секретные, были основаны на известных алгоритмах. Так было и в случае
с шифром Плейфера, изобретенным сэром Чарльзом Уитстоном и внедренным в прак-
тику госслужб Великобритании лордом Лайоном Плейфером. Шифр Плейфера был
хитроумным вариантом шифра Полибия, но все-таки лишь вариантом. Подробнее
о нем рассказано в Приложении.
Несмотря на изобретательность их создателей, расшифровка этих модифициро-
ванных шифров в конечном счете была вопросом времени и вычислительных мощно-
СПАСИТЕ НАШИ ДУШИ, КОРАБЛЬ ИЛИ ЧТО-НИБУДЬ ЕЩЕ,
НАЧИНАЮЩЕЕСЯ С БУКВЫ «S»
Самым известным сигналом в азбуке Морзе является SOS. Он был выоран группой европейских
стран в качестве сигнала бедствия из-за простоты передачи (три точки, три тире, три точки) - эти
буквы не являлись аббревиатурой. Тем не менее, вскоре появились альтернативные «расшиф-
ровки». Самым известным из этих «бэкронимов» является значение «Save Our Souls» («Спасите
наши души»). Позже, так как сигнал часто использовали на море, популярным стало другое зна-
чение: «Save Our Ship» («Спасите наш корабль»).
56
ШИФРОВАЛЬНЫЕ МАШИНЫ
стей. Криптографическая история Первой мировой войны прекрасно это иллюстри-
рует. Мы уже рассказали о слабости немецких дипломатических шифров во вре-
мя инцидента с телеграммой Циммермана. Но оказалось, о чем сами немцы даже
не подозревали, что другой их шифр, известный как ADFGVX и используемый для
шифрования наиболее секретных сообщений, предназначенных для фронта, также
был взломан вражескими криптоаналитиками, несмотря на то, что считался неуяз-
вимым. Этот двойной провал немецких шифровальщиков Первой мировой войны
привел к тому, что все стороны осознали необходимость разработки более надежных
шифров. Этой цели можно было достигнуть, лишь сильно затруднив криптоанализ.
80 километров от Парижа
В июне 1918 г. германские войска готовились напасть на столицу Франции. Для со-
юзников было крайне важно перехватить вражеские сообщения, чтобы выяснить, где
именно произойдет вторжение. Немецкие сообщения, предназначенные для фрон-
та, были зашифрованы шифром ADFGVX, который немецкие военные считали
неуязвимым.
Наш интерес к этому шифру связан с тем, что он сочетает в себе алгоритмы под-
становки и перестановочного шифрования. Это один из самых изощренных методов
классической криптографии. Немцы начали использовать его в марте 1918 г., и как
только французы узнали о его существовании, они отчаянно принялись за его взлом.
К счастью для них, в центральном шифровальном бюро работал талантливый крип-
тоаналитик Жорж Панвэн. Он посвятил себя этой задаче, работая круглые сутки.
Ночью 2 июня 1918 г. Панвэну удалось расшифровать первое сообщение, зловещим
содержанием которого был приказ фронту: «Ускорьте продвижение боевой техники.
Даже в дневное время, лишь бы незаметно». В начале шифровки было указано,
что она отправлена из местечка, расположенного между Мондидье и Компьень,
в 80 километрах к северу от Парижа. Результат Панвэна позволил французам со-
рвать атаку и остановить продвижение немцев.
Как уже упоминалось, шифр ADFGVX состоит из двух частей: шифра подста-
новки и шифра перестановки. Первый шаг — подстановка — состоит в следующем:
у нас имеется таблица размером 7 х 7, в которой первая строка и первый столбец
содержат буквы ADFGVX (см. стр. 58). Остальные поля таблицы случайным об-
разом заполняются 36 символами: 26 букв алфавита и цифры от 0 до 9. Расположе-
ние символов представляет собой ключ к шифру, и получателю, очевидно, нужна эта
информация, чтобы понять содержание сообщения.
57
ШИФРОВАЛЬНЫЕ МАШИНЫ
Мы будем использовать следующую таблицу:
А D F G V X
А 0 Р F 0 Z С
D G 3 В Н 4 к
F А 1 7 J R 2
G 5 6 L D Е т
V V м S N Q 1
X и W 9 X Y 8
Шифр сообщения состоит в замене каждого символа его координатами, вы-
раженными группой букв ADFGVX. Первой координатой будет буква, соответ-
ствующая строке, а второй — соответствующая столбцу. Например, если мы хо-
тим зашифровать цифру 4, мы должны написать DV. Сообщение Target is Paris
(«Цель — Париж») будет зашифровано следующим образом:
Т а г g е t i s P a r i s
GX FA FV DA GV GX VX VF AD FA FV VX VF
До сих пор мы использовали лишь простую подстановку, и частотного анализа
было бы достаточно, чтобы расшифровать сообщение.
Однако этот шифр содержит второй шаг — перестановку. Она зависит от ключе-
вого слова, о котором договорились отправитель и получатель. Этот шаг осуществля-
ется следующим образом. Сначала мы построим таблицу с таким числом столбцов,
сколько букв в ключевом слове, и заполним поля таблицы зашифрованным текстом.
Буквы ключевого слова пишут в верхнем ряду новой таблицы. В этом примере клю-
чевое слово будет ВЕТА. Построим таблицу, в которой первая строка состоит из букв
ключевого слова и следующие строки содержат буквы, полученные после кодирования
сообщения на этапе подстановки. Любые пустые ячейки заполняются цифрой ноль,
которая, как видно из первой таблицы, имеет код AG.
58
ШИФРОВАЛЬНЫЕ МАШИНЫ
Чтобы применить второй шаг к нашему сообщению «Цель — Париж», напом-
ним сначала, что после подстановки оно выглядело так:
GX FA FV DA GV GX VX VF AD FA FV VX VF
Используя ключевое слово ВЕТА, мы получим следующую таблицу.
В Е Т А
G X F А
F V D А
G V G X
V X V F
А D F А
F V V X
V F А G
Применяя перестановочный шифр, изменим порядок столбцов, чтобы буквы
ключевого слова были расположены в алфавитном порядке. Это даст нам следую-
щую таблицу.
А В Е Т
А G X F
А F V D
X G V G
F V X V
А А D F
X F V V
G V F А
59
ШИФРОВАЛЬНЫЕ МАШИНЫ
Зашифрованное послание получается, если брать буквы этой таблицы по столб-
цам. В нашем примере это будет:
AAXFAXGGFGVAFVXWXDVFFDGVFVA
Как мы видим, теперь сообщение состоит из вроде бы случайного набора букв
A, D, F, G, V и X. Немцы выбрали эти шесть букв, потому что по звучанию
в азбуке Морзе они сильно отличаются друг от друга, и получатель легко может
отсеять возможные при передаче ошибки. Более того, поскольку сообщения со-
стоят из шести букв, посылать такие телеграфные передачи могли даже неопытные
операторы.
Если мы обратимся к таблице кодов Морзе в начале главы, то увидим следующие
коды для каждой из букв шифра ADFGVX:
А = •-
D =
F =
G =
V =
X =
Чтобы расшифровать сообщение, получателю необходимо знать распределение
букв и цифр в базисной таблице и ключевое слово.
Шифровальная машина «Энигма»
В 1919 г. немецкий инженер Артур Шербиус запатентовал машину для защищен-
ной связи. Ее название, «Энигма», с тех пор стало синонимом военной тайны.
Несмотря на свою сложность, «Энигма», по сути, является улучшенной версией
диска Альберти.
60
ШИФРОВАЛЬНЫЕ МАШИНЫ
Благодаря относительной простоте использования и сложности выдаваемых
шифров, система «Энигма» была выбрана германским правительством для шифро-
вания большей части военных донесений в годы Второй мировой войны.
Именно поэтому расшифровка кодов «Энигмы» стала абсолютным приорите-
том для правительств стран, воюющих с нацистской Германией. Когда это нако-
нец удалось, сообщения, перехваченные и расшифрованные разведками союзников,
оказались решающими для завершения военного конфликта. История расшифровки
кода «Энигмы» — это захватывающая эпопея с участием отделов разведки Поль-
ши и Великобритании, а также гениального математика Алана Тьюринга, человека,
считающегося отцом современной вычислительной техники. В результате работы
по взлому кода «Энигмы» появился первый в мире компьютер, что можно считать
самым значительным событием в долгой и яркой истории военного криптоанализа.
Слева: немецкие солдаты во время Второй мировой войны записывают сообщение, зашифрованное
с помощью «Энигмы». Справа: реплика четырехроторной «Энигмы».
61
ШИФРОВАЛЬНЫЕ МАШИНЫ
«Энигма» представляла собой электромагнитное устройство, внешне похожее
на пишущую машинку. Уникальной ее делало то, что ее механические части меняли
положение после каждого нажатия клавиш, так что даже при нажатии подряд одной
и той же буквы символ каждый раз кодировался по-новому.
На практике процесс шифрования был относительно прост. Сначала оператор
устанавливал различные разъемы и роторы машины в соответствии с исходным по-
ложением, заданным справочником кодов, используемых на данный момент (эти
справочники регулярно менялись). Затем он печатал первую букву открытого текста,
и машина автоматически генерировала код, который появлялся на светящейся пане-
ли — это была первая буква зашифрованного сообщения.
ТРАНШЕЙНЫЕ КОДЫ
В бою использовать сложные шифры, такие как ADFGVX, было очень трудно. Во время гражданской
войны в Испании (1936-1939), например, применялся более простой шифр подстановки:
А В С D Е F G Н Y J
53,91 12,70 40,86 31 27,43 24 16 11 40,59 22
L М N 0 Р Q S R Т и
13 15 96,66 84,39 75 71 28,54 28,54 19 74,44
Как мы видим, несколько букв имеют более одного зашифрованного символа. Например,
буква R может быть заменена на 28 или 54. Слово GUERRA («Война») будет зашифровано как
167427285453. Эти коды, которые фактически были шифром подстановки, получили название
траншейных кодов и предназначались для особых целей.
Clave Violeta («фиолетовый ключ-,
слева) использовался 415-м бата-
льоном 104-й бригады республи-
канцев и был перехвачен национа-
листами. Примечание переводится
как: «Шифры обязательно должны
быть представлены в виде букв.
Столбцы [строки] с пометкой (1) со-
ответствуют алфавиту. Столбцы
с пометкой (2) соответствуют их
зашифрованным эквивалентам».
62
ШИФРОВАЛЬНЫЕ МАШИНЫ
Первое переключение ротора поворачивало его в одну из 26 возможных пози-
ций. Каждое положение переключателя соответствовало новому шифру. После этого
оператор вводил вторую букву и так далее. Чтобы расшифровать сообщение, доста-
точно было ввести зашифрованные символы в другую машину «Энигма» с теми же
исходными параметрами, что и у машины, использованной для шифрования.
На рисунке на следующей странице представлена упрощенная схема механизма
«Энигмы», где для шифрования используются роторы с алфавитом из трех букв.
В результате каждый ротор имеет только три возможных позиции, а не 26, как
в реальной машине.
Для обеспечения более высокого уровня секретности националисты во главе с генералом
Франко применили особое оружие - 30 машин «Энигма», присланных нацистскими союзниками.
Это было первое интенсивное использование в военных целях шифровальных устройств, которые
Германия начала широко применять во время Второй мировой войны. Британцы пытались взло-
мать код во время испанского конфликта, но безуспешно.
гжГе ..лсх.2 тспаса.- ----— - —
с if л*™ дцсег zUicraa .clave Шоп i
t вж UL1A еп шв) HMiiltJi carDletCJWflte inceucirra-
Ke ilt Drcftr f. c jJ’lf t О CiTFtt C • "i 'Ito ~ Ф»-
co я !.хи Jo cy U " rctF .юн У
..t* с reamilcn с BataGlSn.: tencldn
Телеграмма (слева) от 27 октября 1936 г.
начальнику сектора Гэанада (республиканцу):
«Ваша телеграмма, зашифрованная вчера... не
подлежит расшифровке».
. имж , 3;
I ' W ж hdu МЛ.^.
RADIO TILBGCAHCA £Ж F i7 Й J-O.N.X.
__i Mt ж ватл «ИШ.__________
ЖЮГПСТС 1ЖТ«01??аИ> П t* «ОДНО* »Ш0СТЬ2С«1>ТСА вАХ £В ЖхКжШи.
1*0 Ъ«ГМ1««« 10 JK 14. to
•Mlal рх«Ъ«
AAWCTF3B JPOLMrr 800» 1Ч«ЖЫ WJUIAC2 ЙОЫЖ OKQWTJUW
w за г» ifi.yo -<•
вокала
•во niTl ожжио става жтстт жтто ооит «ом nvx arm юиш
I*on font* ПГО1» XKTOJ № XIA Wflt WTW» Ш1Л 010*1 ШИ HHl
ШЛА BTBZf СТ1ВЖ ААХТГ ШИ V&n OT*ft mi* ТГСТ1 8ИЦ ОРТЫ
оажи nm otno о?з«
Зашифрованное сообщение респу-
бликанцев (справа), перехваченное
испанскими фашистами-фалангистами
на Канарских островах.
IW «мкоа M 24 19. atM
tlMNMOtfT MUw»
тлей ШП I00M W>₽9 WF1P USU. 2^0» WBU MIT PWT*
»IM* WVAF9 АГРГТ votr МОП OTW Х1ОГС M«O»C TtTK? ITtt» SOW
xitnm оогао
63
ШИФРОВАЛЬНЫЕ МАШИНЫ
Как мы видим, когда ротор машины «Энигма» находится в исходном положении,
каждая буква открытого сообщения заменяется на другую, за исключением буквы
А. После шифрования первой буквы ротор поворачивается на одну треть оборота.
В новой позиции буквам теперь соответствуют другие — не те, что в первом шифре.
Процесс завершается третьей буквой, после чего ротор возвращается в исходное по-
ложение и последовательность шифров повторяется.
Роторы стандартной машины «Энигма» имеют 26 позиций, по одной на каж-
дую букву алфавита. Следовательно, с одним ротором можно применять 26 раз-
личных шифров. Таким образом, начальное положение ротора является ключевым.
Для увеличения количества возможных ключей дизайн «Энигмы» предусматривал
до трех роторов, механически соединенных друг с другом. Когда первый ротор де-
64
ШИФРОВАЛЬНЫЕ МАШИНЫ
лал полный оборот, следующий
переключался на одно положение,
и так далее до полного оборота
третьего ротора, что давало в об-
щей сложности 26 х 26 х 26 =
= 17 576 возможных шифров.
Кроме того, дизайн Шербиуса
позволял изменять порядок пере-
ключателей, еще больше увеличи-
вая количество шифров, как мы
увидим ниже.
Кроме трех роторов «Эниг-
ма» также имела коммутаци-
онную панель, расположенную
между первым ротором и клавиа-
турой. Коммутационная панель
позволяла перекоммутировать со-
единения между буквами клави-
Трехроторная машина «Энигма» с частично открытым
корпусом, позволяющим видеть коммутационную
панель (спереди).
атуры до соединения с ротором
и таким образом добавляла значительное количество кодов к шифру. Стандартный
дизайн «Энигмы» предусматривал шесть кабелей, которые могли соединять шесть
пар букв. На следующем рисунке показана работа коммутационной панели, снова
в упрощенной форме для трех букв и трех кабелей.
65
ШИФРОВАЛЬНЫЕ МАШИНЫ
Таким образом, буква А меняется местами с буквой С, буква В — с буквой А,
а С — с буквой В. С добавлением коммутационной панели упрощенная трехбуквен-
ная «Энигма» будет работать следующим образом:
На сколько больше шифров мы получим при, казалось бы, простом добавлении
коммутационной панели? Сначала посчитаем количество способов соединения ше-
сти пар букв, выбранных из 26 возможных. Число способов выбрать п пар букв
из алфавита, содержащего N символов, определяется по формуле:
_____N!______
(N-2/z)!-/z!-2"
В нашем примере N = 26 и п = 6, что дает нам 100391791500 комбинаций.
Следовательно, общее количество шифров, возможных на машине «Энигма»
с тремя роторами из 26 букв и коммутационной панелью с шестью кабелями, счита-
ется следующим образом.
1. Количество поворотов трех роторов дает 26 ’ = 26 26 • 26 = 17 576 комбинаций.
2. Кроме того, три ротора (1, 2, 3) могут меняться друг с другом местами, на-
пример, 1—2—3, 1—3—2, 2—1—3, 2—3—1, 3—1—2, 3—2—1. Это дает нам до-
полнительные шесть комбинаций.
3. Наконец, мы подсчитали число способов соединять пары букв шестью кабеля-
ми на коммутационной панели, что дало нам 100391791500 дополнительных
шифров.
66
ШИФРОВАЛЬНЫЕ МАШИНЫ
Общее количество шифров получается умножением перечисленных результатов
и составляет 6-17 576 • КХ) 391 791 5(X) = 10 586 916 764 424 (XX). Таким образом, машина
«Энигма» могла шифровать текст, используя более чем десять тысяч триллионов
различных шифров. Германское правительство было в полной уверенности, что се-
кретные коммуникации высшего уровня совершенно неуязвимы. И это было большой
ошибкой.
Расшифровка кода «Энигмы»
Любой ключ кода «Энигмы» сначала указывал конфигурацию коммутационной па-
нели, а именно возможные соединения шести пар букв, например, B/Z, F/Y, R/C,
Т/Н, Е/О И L/J, что означало, что первый кабель менял местами буквы В и Z,
и так далее. Во-вторых, ключ определял порядок роторов (например, 2—3—1). На-
конец, ключ описывал исходную ориентацию роторов (например, буквы R, V, В по-
казывали, какая буква находится в начальном положении, или начальные позиции).
Эти параметры были собраны в шифровальных книгах, которые тоже передавались
в зашифрованном виде и могли меняться в установленные дни или при особых обсто-
ятельствах. Например, некоторые ключи были зарезервированы для определенных
типов сообщений.
Чтобы не повторять один и тот же шифр в течение одного дня, во время кото-
рого могли быть посланы тысячи сообщений, операторы «Энигмы» использовали
гениальные трюки для выбора новых шифров в особых случаях, но без замены всей
шифровальной книги. Так, оператор отправлял сообщение из шести букв, зашиф-
рованное в соответствии с действующим в этот день кодом, представляющее со-
бой новый набор начальных позиций для роторов, например, T-Y-J. (Для большей
безопасности оператор шифровал эти три буквы два раза, поэтому и получалось
шесть букв). Затем он шифровал настоящее сообщение в соответствии с этим но-
вым ключом. Другой оператор получал сообщение, которое он не мог расшифровать
с ключом этого дня, но он знал, что первые шесть букв на самом деле являлись ин-
струкцией переставить роторы в другую позицию. Получатель делал это, оставляя
коммутационную панель и порядок роторов без изменения, и затем мог правильно
расшифровать сообщение.
Союзники получили первые ценные сведения относительно «Энигмы» в 1931 г.
от немецкого шпиона Ганса-Тило Шмидта. Это были различные инструкции для
работы с машиной. Контакт со Шмидтом установили французские спецслужбы,
которые впоследствии поделились информацией с польскими коллегами. Польский
67
ШИФРОВАЛЬНЫЕ МАШИНЫ
криптоаналитический отдел, Biuro Szyfrow (шифровальное бюро), начал работу
с документами Шмидта, а также добыл несколько машин «Энигма», украденных
у немцев.
Не совсем обычный штрих для того времени: в польском отделе работало боль-
шое количество математиков. Среди них был талантливый 23-летний застенчивый
молодой человек по имени Мариан Реевский. Он сразу же сосредоточил усилия
на шести буквенных кодах в начале многих ежедневных сообщений, которыми обме-
нивались немцы. Реевский предположил, что последние три буквы кода были новым
шифром для первых трех, и поэтому понял, что четвертая, пятая и шестая буквы
могли дать ключ для начальных позиций роторов.
На этой, казалось бы, незначительной гипотезе Реевский построил незауряд-
ную систему умозаключений, которая привела к расшифровке кода «Энигмы».
Подробности этого процесса достаточно сложны, и мы не будем здесь их изла-
гать, но после нескольких месяцев Реевский смог сократить количество возмож-
ных шифров с десяти тысяч триллионов до всего лишь 105 456, что соответствова-
ло различным комбинациям расположения роторов и их начальных позиций. Для
этого Реевский создал устройство, известное как Bombe («Бомба»), которое ра-
ботало так же, как «Энигма», и могло имитировать любую из возможных позиций
трех роторов для поиска ежедневного кода. Уже в 1934 г. сотрудники польского
шифровального бюро взломали код «Энигмы» и могли расшифровать любое со-
общение в течение 24 часов.
Хотя немцы не знали, что польские криптоаналитики расшифровали код «Эниг-
мы», они продолжали совершенствовать систему, которая уже успешно работала
на протяжении более чем десятилетия. В 1938 г. операторы «Энигмы» получили до-
полнительные два ротора к трем стандартным, и вскоре после этого были выпущены
новые модели машин с десятью коммутационными кабелями.
Тогда число возможных шифров возросло до почти 159 квинтиллионов. Лишь
добавление еще двух роторов увеличивало возможные комбинации их расположе-
ния с шести до 60: пять возможностей поместить любой из пяти роторов на первом
месте, умноженные на четыре возможности поставить любой из четырех оставшихся
роторов на второе место, умноженные на три возможности поставить любой из трех
оставшихся роторов на третье место. Итого 5x4x3 = 60. Даже сумев расшифро-
вать код, сотрудники польского бюро не имели средств, необходимых для анализа
такого количества расположений роторов.
68
ШИФРОВАЛЬНЫЕ МАШИНЫ
Некоторые версии машины «Энигма»
Британцы принимают эстафету
Обновление машин «Энигма» не было случайным: Германия уже начала агрессив-
ную экспансию в Европу с аннексии Чехословакии и Австрии и планировала втор-
жение в Польшу. В 1939 г. в связи со вспыхнувшим в сердце Европы конфликтом
и завоеванием их страны поляки передали все машины «Энигма» и сведения о них
британским союзникам, которые в августе того же года решили объединить свои
ранее рассредоточенные криптоаналитические отделы. Новым центром был выбран
особняк, расположенный на окраине Лондона, в поместье Блетчли-Парк. В коман-
ду Блетчли-Парка был включен блестящий криптоаналитик, молодой кембридж-
ский математик Алан Тьюринг. Он был мировым авторитетом в тогда еще только
зарождавшейся теории вычислений и был открыт для работы на новых, революци-
онных проектах. Расшифровка усовершенствованных машин «Энигма» оказалась
серьезным импульсом для ускоренного развития теории вычислений.
69
ШИФРОВАЛЬНЫЕ МАШИНЫ
Эксперты за работой в Блетчли-Парке, где был расшифрован код «Энигмы».
Эксперты Блетчли-Парка сосредоточились на расшифровке коротких фраг-
ментов зашифрованного текста, содержание которых они примерно знали. Напри-
мер, благодаря «полевым» шпионам было известно, что немцы около шести вечера
каждый день передавали кодированные сообщения о метеорологических условиях
в различных точках вдоль линии фронта. Таким образом, можно было с достаточной
степенью уверенности ожидать, что сообщение, перехваченное вскоре после этого
часа, содержало зашифрованные версии таких слов, как «погода» и «дождь». Тью-
ринг изобрел электрическую систему, которая менее чем за пять часов позволяла
воспроизвести все возможные 1054650 комбинаций расположения трех роторов.
В эту систему вводили зашифрованные символы, которые по их длине или другим
признакам, возможно, соответствовали словам «погода» и «дождь».
Предположим, мы подозреваем, что зашифрованные символы FGRTY соответ-
ствуют слову BREAD («хлеб»). После введения шифровки в машину, если при
каком-то положении роторов получалось слово BREAD, криптоаналитики знали,
что найден ключ, соответствующий конфигурации начальных позиций роторов. За-
тем оператор вводил зашифрованный текст в настоящую машину «Энигма» с ро-
торами, расположенными в соответствии с найденным ключом. Если машина по-
казывала, например, расшифрованный текст DREAB, было ясно, что часть шифра
связана с конфигурацией коммутационной панели и включает перестановку букв D
70
ШИФРОВАЛЬНЫЕ МАШИНЫ
и В. Таким образом криптоаналитики получали весь шифр. Секреты «Энигмы» по-
степенно раскрывались. В процессе разработки и совершенствования вышеупомя-
нутых аналитических методов команда Блетчли-Парка построила первую в истории
программируемую вычислительную машину, названную Colossus.
Colossus, предшественник современного компьютера, в Блетчли-Парке. Фотография,
сделанная в 1943 г., показывает панель управления сложного устройства.
Другие шифры Второй мировой войны
Япония разработала две собственные системы шифрования: Purple («Пурпурный
код») и JN-25. Первая из них предназначалась для дипломатической связи, а вто-
рая — для военных сообщений. Оба шифра использовали механические устройства.
JN-25, например, работал на алгоритме подстановки, который переводил симво-
лы японского языка (порядка 30000 знаков) в ряд чисел, определенных слу-
чайными таблицами из пяти групп чисел. Несмотря на меры предосторожности,
предпринятые в Японии, англичане и американцы взломали «Пурпурный код»
и шифр JN-25. Сведения из расшифрованной переписки получили кодовое название
«Мэджик» и оказали значительное влияние на военные конфликты в Тихом океане,
71
ШИФРОВАЛЬНЫЕ МАШИНЫ
в частности, на сражение в Коралловом море и у атолла Мидуэй в 1942 г. Сведения
«Мэджик» были также использованы для планирования стратегических задач, та-
ких как перехват и уничтожение самолета японского адмирала Ямамото год спустя.
БЛЕСТЯЩИЙ УМ
Алан Тьюринг (слева) родился в Англии
в 1912 г. Даже в молодости он демонстриро-
вал большие способности к математике и фи-
зике. В 1931 г. он поступил в Кембриджский
университет, где увлекся работами логика
Курта Геделя по общей проблеме неполно-
ты любой логической системы. За три года
до того он опубликовал работу о теоретиче-
ской возможности создания машины, спо-
собной выполнять вычислительные алгорит-
мы, такие как сложение, умножение и т.д.
Вдохновленный работами Гёделя, Тьюринг
в 1937 г. развил свои идеи о доказатель-
ствах и вычислениях и сформулировал прин-
цип «универсальной машины», способной вы-
полнять любые мыслимые алгоритмические
действия. 1ак появилась одна из основ современной информатики. За два года до того Тьюринг
познакомился с крупным венгерским математиком Яношем фон Нейманом, который к тому
времени жил в Соединенных Штатах и носил имя Джон. Фон Нейман, считающийся «вторым
отцом» информатики, предложил Тьюрингу хорошо оплачиваемую и престижную работу в Прин-
стоне. Однако Тьюринг предпочел богемную атмосферу Кембриджа и отклонил предложение.
В 1939 г., когда началась война, он присоединился к британской команде криптоаналитиков
в Блетчли-Парке. За свою работу во время войны он был награжден Орденом Британской импе-
рии. Но Тьюринг был гомосексуалистом, что было запрещено законом в то время, и в результате
приговора в 1952 г. потерял право работать на секретных проектах правительства. Глубоко
подавленный, Алан Тьюринг покончил жизнь самоубийством 8 июня 1954 г., приняв цианистый
калий.
72
ШИФРОВАЛЬНЫЕ МАШИНЫ
Шифровальщики навахо
Хотя Соединенные Штаты умело использовали информацию, перехваченную
у противника во время военных действий на Тихом океане, американские военные
для собственной связи применяли несколько шифров, по сути похожих на те, о кото-
рых говорилось в начале книги. Алгоритмы шифрования были основаны непосред-
ственно на природе слов. Эти шифры — чокто, команче, месквоки и прежде всего
навахо — не были четко описаны в сложных руководствах и не были результатом
работы отделов криптографии: это были просто подлинные языки индейцев.
Армия Соединенных Штатов включала радистов из этих племен в отделы шиф-
ровальщиков на фронте, чтобы они передавали сообщения на своих языках, на ко-
торых не говорили не только японцы, но и другие американские военные. Эти со-
общения дополнительно шифровались простыми кодами, чтобы захваченные в плен
солдаты не смогли их перевести. Такие радисты служили в американских отделах
вплоть до Корейской войны.
Два шифровальщика навахо во время битвы за Бугенвиль в 1943 г.
73
ШИФРОВАЛЬНЫЕ МАШИНЫ
Нововведения: шифр Хилла
Шифры, обсуждавшиеся прежде, в которых один символ заменялся другим по неко-
торому заранее установленному правилу, как мы уже видели, всегда уязвимы для
криптоанализа.
В 1929 г. американский математик Лестер Хилл придумал, запатентовал и вы-
ставил на продажу — правда, без особого успеха — новую систему шифрования,
в которой использовались и модульная арифметика, и линейная алгебра.
Как мы увидим ниже, матрицы являются очень полезным инструментом для
шифрования сообщений, когда текст разбивается на пары букв и каждой букве ста-
вится в соответствие числовое значение.
Чтобы зашифровать сообщение, мы будем использовать следующие матрицы:
с определителем, равным единице, то есть
ad — be = 1. Для расшифровки мы бу-
дем использовать обратную матрицу:
Л-1 =
-Ь
а
НЕМНОГО ЛИНЕЙНОЙ АЛГЕБРЫ
Матрица может быть определена как таблица, представляющая собой совокупность строк и столб-
цов. Например, матрица 2x2 имеет вид:
fa b
\ с d /
а матрица 2x1 записывается как: | * |
\ У /
Произведение этих двух матриц дает нам новую матрицу 2x1, называемую векгор-столбцом:
fa b W х \ = /ах + Ьу\
I с d J I у I I cx+dy I
В случае матрицы 2x2 число (ad - be) называется определителем матрицы.
74
ШИФРОВАЛЬНЫЕ МАШИНЫ
Ограничение на значение определителя установлено для того, чтобы обратная
матрица работала как инструмент расшифровки. Как правило, для алфавита из п
символов необходимо, чтобы НОД определителя матрицы и числа п равнялся еди-
нице. Иначе нельзя гарантировать существование обратного элемента в модульной
арифметике.
Продолжая пример, возьмем алфавит из 26 букв с символом пробела, который
мы обозначим как @. Каждой букве мы поставим в соответствие число, как пока-
зано в следующей таблице:
А В С D Е F G Н 1 J К L М N 0 Р Q R S Т и V W X Y Z @
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Для получения значений от 0 до 26 мы будем работать по модулю 27.
Процесс шифрования и расшифровки текста происходит следующим образом:
сначала мы определяем шифровальную матрицу с определителем 1.
Например, д _ | j
1 2 7 /
Матрицей для расшифровки будет обратная матрица /j-i — | — *
1-2 1
Таким образом, А будет ключом шифра, А 1 — ключом для расшифровки.
Например, зашифруем сообщение BOY («мальчик»). Буквы сообщения груп-
пируются в пары: ВО Y@. Их численными эквивалентами, согласно таблице, яв-
ляются пары чисел (1, 14) и (24, 26). Умножим матрицу А на каждую пару чисел.
Зашифрованное ВО =
3 \ / 1 \ / 43 \ / 16 \ , , __
I 1= I ) = I I (mod 27),
2 7/ \14/ \1(Х1/ \ 19/
что, согласно таблице, соответствует буквам (Q, Т).
что соответствует буквам (V, О).
Сообщение BOY будет зашифровано как QTVO.
75
ШИФРОВАЛЬНЫЕ МАШИНЫ
Обратная операция расшифровки выполняется при помощи матрицы:
( 7 -3 \
Л-' = 1 .
1-2 1 )
Возьмем пару букв (Q, Т) и найдем их числовые эквиваленты из таблицы: (16,
19). Затем умножим их на А и получим:
7
-2
-3
1
, что дает нам
(В, О).
Делаем то же со второй парой (V, О) и ее численными значениями (21, 14)
и получаем:
/7 -3 \ / 21 \ = / 105 \ = / 24
\-2 1 / \14/ \-28/ " \2б
(mod 27). что дает нам (Y, @).
Таким образом, мы доказали, что расшифровка работает.
В этом примере мы рассматривали пары символов. Для большей безопасности
можно группировать буквы по три или даже по четыре. Тогда расчеты будут прово-
диться с матрицами порядка 3 х 3 и 4 х 4 соответственно, что было бы чрезвычайно
трудоемким процессом для вычислений вручную. Современные компьютеры позво-
ляют работать с огромными матрицами и с обратными к ним.
У шифра Хилла есть существенный недостаток: имея даже небольшой фрагмент
исходного текста, можно расшифровать все сообщение. Поиск идеального шифра
был еще далек от завершения.
76
Глава 4
Процесс общения
посредством нулей и единиц
Изобретение компьютера Colossus и расшифровка кода «Энигмы» открыли путь
к величайшей революции в сфере коммуникаций. Этот гигантский шаг вперед прои-
зошел в значительной степени благодаря развитию систем шифрования, что обе-
спечило безопасную, эффективную и быструю связь по разветвленным сетям, пред-
ставляющим собой компьютеры и их пользователей — то есть нас с вами. Когда
сегодня мы употребляем слово «безопасность», мы имеем в виду не только крип-
тографию и секретность. Это слово имеет более широкий смысл, который включает
в себя понятия надежности и эффективности.
Двоичная система является основой технологической революции. Этот супер-
простой код, содержащий лишь два символа, 0 и 1, используется в цифровых устрой-
ствах из-за его способности представлять состояние электронных схем: единица оз-
начает, что в контуре есть ток, ноль — тока нет. Одна двоичная цифра — 0 или
1 — называется битом.
ASCII-код
Одним из многих приложений двоичной системы является особый набор символов,
состоящий из восьми битов и называемый байтом. Каждый байт обозначает букву,
цифру или другой символ. Именно байты лежат в основе обычных коммуникаций.
Они называются ASCII-кодами (аббревиатура ASCII переводится как «американ-
ская стандартная кодировочная таблица»). Количество размещений (с повторения-
ми) из двух цифр (0 и 1) по 8 (длина символа) составляет 28 = 256.
ASCII-коды позволяют пользователям вводить текст в компьютер. Когда мы
печатаем букву или цифру, компьютер превращает этот символ в байт — строку
БАЙТЫ ПАМЯТИ
Емкость памяти компьютера измеряется в единицах, кратных байтам.
Килобайт (КБ): 1024 байтов Гигабайт (ГБ): 1 073 741 824 байтов
Мегабайт (МБ): 1 048 576 байтов Терабайт (ТБ): 1099 511627776 байтов
77
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
из восьми битов. Так, например, если мы печатаем букву А, компьютер превращает
ее в 0100 0001.
Двоичные ASCII-коды приведены для всех используемых в обычном обиходе
символов: 26 заглавных букв, 26 строчных букв, 10 цифр, 7 символов пунктуа-
ции и некоторых специальных символов. Все они показаны в следующей таблице.
Для двоичного кода каждого символа указано соответствующее десятичное число
(в столбце «Дес»):
Таблица ASCII
Символ Двоичный код Дес Символ Двоичный код Дес Символ Двоичный код Дес
пробел 0010 0000 32 @ 0100 0000 64 ОНО 0000 96
! 0010 0001 33 А 0100 0001 65 а ОНО 0001 97
0010 0010 34 В 0100 0010 66 b ОНО 0010 98
# 0010 ООН 35 С 0100 ООН 67 с ОНО ООН 99
$ 0010 0100 36 D 0100 0100 68 d ОНО 0100 100
% 0010 0101 37 Е 0100 0101 69 е ОНО 0101 101
& 0010 оно 38 F 0100 оно 70 f ОНО ОНО 102
* 0010 0111 39 G 0100 0111 71 g ОНО 0111 103
( 0010 1000 40 Н 0100 1000 72 h ОНО 1000 104
) 0010 1001 41 1 0100 1001 73 i ОНО 1001 105
* 0010 1010 42 J 0100 1010 74 j ОНО 1010 106
+ 0010 1011 43 К 0100 1011 75 k ОНО 1011 107
0010 1100 44 L 0100 1100 76 1 ОНО 1100 108
- 0010 1101 45 М 0100 1101 77 m ОНО 1101 109
0010 1110 46 N 0100 1110 78 n ОНО 1110 но
/ 0010 1111 47 0 0100 1111 79 0 ОНО 1111 111
0 ООН 0000 48 Р 0101 0000 80 P 0111 0000 112
1 ООН 0001 49 Q 0101 0001 81 Q 0111 0001 113
2 ООН 0010 50 R 0101 0010 82 r 0111 0010 114
3 ООН ООН 51 S 0101 ООН 83 s 0111 ООН 115
4 ООН 0100 52 Т 01010100 84 t 0111 0100 116
5 ООН 0101 53 и 01010101 85 u 0111 0101 117
6 ООН оно 54 V 01010110 86 V 0111 оно 118
7 0011 0111 55 W 0101 0111 87 w 01110111 119
8 ООН 1000 56 X 01011000 88 X 01111000 120
9 ООН 1001 57 Y 01011001 89 У 01111001 121
ООН 1010 58 Z 01011010 90 z 01111010 122
ООН 1011 59 [ 01011011 91 { 01111011 123
< ООН 1100 60 \ 01011100 92 1 01111100 124
ООН 1101 61 ] 01011101 93 } 01111101 125
> ООН 1110 62 А 01011110 94 01111110 126
? ООН 1111 63 - 01011111 95
78
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Фразу «GOTO 2» (команду на языке программирования «Бейсик») компьютер
переведет в следующую последовательность двоичных кодов:
Напечатанное СЛОВО G 0 т 0 пробел 2
Перевод на компьютерный язык 01000111 01001111 01010100 01001111 0010 0000 00110010
Компьютер, таким образом, будет выполнять следующую команду:
010001110100111101010100010011110010000000110010
Шестнадцатеричная система счисления
Шестнадцатеричная система — еще один известный код, используемый в вычис-
лениях. Это система счисления, которая использует 16 уникальных «цифр» (отсюда
и название — шестнадцатеричная), в отличие от обычной системы с десятью циф-
рами (десятичной). Можно сказать, что шестнадцатеричная система является вто-
рым языком компьютеров после двоичной системы. Почему 16 цифр? Напомним,
что байт, основная единица хранения информации на компьютере, состоит из восьми
битов, которые дают 28 = 256 различных комбинаций из 0 и 1. А 28 = 24 х 24 = 16 х
х 16. Иными словами, один байт — это комбинация двух шестнадцатеричных чисел.
Шестнадцать «цифр» шестнадцатеричной системы — это традиционные цифры
0,1, 2,3, 4, 5, 6, 7, 8, 9 и еще шесть символов, выбранных по соглашению: А, В, С,
D, Е, F. Числа в шестнадцатеричной системе записываются следующим образом:
От 0 ДО 15: 0,1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F.
От 16 до 31:10, И, 12,13,14,15,16,17,18,19,1А, IB, 1С, ID, IE, 1F.
От 32 и дальше: 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 2А, 2В, 2С...
79
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Эти файлы были созданы компьютером автоматически. Их странные имена — на самом деле
шестнадцатеричные числа.
Шестнадцатеричные цифры не различают регистр букв (1Е означает то же са-
мое, что и 1е). В следующей таблице приведены первые 16 двоичных чисел и их
шестнадцатеричные эквиваленты:
Двоичное Шестнадцатеричное
0000 0
0001 1
0010 2
ООН 3
0100 4
0101 5
ОНО 6
0111 7
1000 8
1001 9
1010 А
1011 В
1100 С
1101 D
1110 Е
ни F
80
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Чтобы перейти от двоичной записи к шестнадцатеричной, мы сгруппируем биты
в четыре группы по четыре цифры, начиная с правого конца, а потом преобразуем
каждую четверку цифр в соответствии с предыдущей таблицей. Если количество
двоичных цифр не кратно четырем, мы дописываем слева нули. Чтобы перейти
от шестнадцатеричной записи к двоичной, мы преобразуем каждую шестнадцате-
ричную цифру в ее двоичный эквивалент, как показано в следующем примере.
Шестнадцатеричное число принято обозначать так: 9F216 (с нижним индексом
16). Напомним соответствующие двоичные коды:
9 F 2
1001 1111 0010
9F2]6 = 1001111100102 (здесь нижний индекс 2 указывает, что число выражено
в двоичной системе).
Давайте теперь осуществим обратный процесс: число 11101001102 состоит из де-
сяти цифр. Мы дополняем его двумя нулями слева, чтобы получить 12 цифр, кото-
рые можно сгруппировать по четыре.
Преобразуем:
1110100110 = (ХИ 1 Ю10 0110 =ЗЛ6и.
2 2 16
Какая связь между шестнадцатеричными символами и ASCII-кодами? Каждый
ASCII-код содержит восемь битов (один байт) информации, поэтому пять ASCII-
символов содержат 40 битов (пять байтов), и так как шестнадцатеричный символ
содержит четыре бита, мы заключаем, что пять ASCII-символов — это десять
шестнадцатеричных символов.
Рассмотрим пример кодирования фразы в шестнадцатеричном коде. Например,
возьмем название NotRealCo Ltd. Выполним следующие действия.
1. Переведем NotRealCo Ltd в двоичные коды в соответствии с таблицей ASCII.
2. Сгруппируем цифры по четыре. (Если длина двоичной строки не кратна четырем,
мы добавим нули слева.)
3. Выполним замену по таблице соответствий двоичных и шестнадцатеричных
символов.
81
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Фраза N о t R е а 1
Двоичный код по ASCII 01001110 01101111 01110100 01110010 01100101 01100001 01101100
Шестнадцатеричный код 4Е 6F 74 72 65 61 6С
Фраза (продолжение) С о L t d
Двоичный код по ASCII 01100011 01101111 00100000 01001011 01110100 01100100
Шестнадцатеричный код 63 6F 20 4В 74 64
Фраза NotRealCo Ltd в шестнадцатеричных символах выглядит так:
4Е 6F 74 72 65 61 6С 63 6F 20 48 74 64.
Системы счисления и переход к другому основанию
Если система счисления имеет п цифр, то число п называется основанием системы.
На руках человека десять пальцев, поэтому, вероятно, и была придумана десятичная
система счисления — счет проводился на пальцах. Десятичное число, например,
7392, представляет собой количество, равное семи тысячам трем сотням девяти де-
сяткам и двум единицам. Тысячи, сотни, десятки и единицы являются степенями ос-
нования системы счисления, в данном случае 10. Число 7392, таким образом, может
быть выражено следующим образом:
7392 = 7 • 103 + 3 • 102 + 9 • 101 + 2 • 10°.
Однако по соглашению принято писать только коэффициенты (в нашем при-
мере это 7, 3, 9 и 2). Кроме десятичной системы существует много других систем
счисления (на самом деле их общее число бесконечно). В этой главе мы уделили осо-
бое внимание двум из них: двоичной системе с основанием 2 и шестнадцатеричной
с основанием 16. В двоичной системе счисления коэффициенты имеют только два
возможных значения: 0 и 1. Разряды двоичных чисел представляют собой степени
двойки. Таким образом, число 110112 может быть записано как
110112 = 1 • 24 + 1 • 23 + 0 • 22 + 1 • 2' + 1 • 2°.
Если мы вычислим выражение, стоящее справа от знака равенства, мы получим
27, что является десятичной формой двоичного числа 11011. Для обратного перехода
82
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
мы последовательно делим десятичное число на 2 (основание двоичной системы)
и записываем остатки, пока не получим частное 0. Двоичное число будет иметь в ка-
честве первой цифры последнее ненулевое частное, а следующими цифрами будут
полученные остатки, начиная с последнего. Например, переведем десятичное число
76 в двоичный вид.
Разделим 76 на 2, получим частное 38 и остаток 0.
Разделим 38 на 2, получим частное 19 и остаток 0.
Разделим 19 на 2, получим частное 9 и остаток 1.
Разделим 9 на 2, получим частное 4 и остаток 1.
Разделим 4 на 2, получим частное 2 и остаток 0.
Разделим 2 на 2, получим частное 1 и остаток 0.
Разделим 1 на 2, получим частное 0 и остаток 1.
Остаток от деления записываем в обратном порядке. Таким образом, число
76 выглядит в двоичной системе как 10011002 Этот результат можно проверить
по таблице ASCII (в таблице слева приписан дополнительный 0, чтобы получить
строки из четырех цифр). Выражение числа, записанного в одной системе счисле-
ния, в другой системе называется переходом к другому основанию.
Коды для обнаружения ошибок передачи
Описанные выше коды обеспечивают безопасную и эффективную связь между
компьютерами, программами и пользователями. Но этот онлайновый язык осно-
ван на общей теории информации, которая лежит в основе процесса коммуникации.
Первый шаг в этой теории является настолько очевидным, что его легко упустить
из вида: как измерить информацию.
Такая простая фраза, как «Приложение размером 2 КБ», основана на блестящих
идеях, которые впервые появились в статье «Математическая теория связи», опу-
бликованной в двух частях в 1948 г. американским инженером Клодом Шенноном.
В этой основополагающей статье Шеннон предложил использовать слово «бит» для
обозначения наименьшей единицы информации. Общая проблема, которую Шен-
нон рассматривал в своей работе, знакома и современным читателям. Как лучше
всего зашифровать сообщение, чтобы оно не повредилось во время передачи? Шен-
нон пришел к выводу, что невозможно найти шифр, который предотвратит поте-
рю информации. Иными словами, при передаче информации неизбежно возникают
83
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
ошибки. Однако этот вывод не помешал поиску стандартов кодификации, которые,
не имея возможности исключить ошибки, могли бы по крайней мере обеспечить вы-
сокий уровень надежности.
При цифровой передаче информации сообщение, сгенерированное отправителем
(это может быть как человек, так и компьютер или другое устройство), кодируется
в двоичной системе и поступает в канал связи, состоящий из компьютеров отправи-
теля и получателя, плюс самой линии связи, которая может быть или физическим
кабелем, или беспроводной (радиоволны, инфракрасное излучение и т. д.). Движе-
ние по каналу связи является особенно уязвимым процессом, потому что сообщение
подвергается всевозможным воздействиям, в том числе взаимодействиям с другими
сигналами, неблагоприятным температурам физической среды и затуханиям (осла-
блению) сигнала при прохождении через среду. Эти источники помех называются
шумами.
Одним из таких методов является избыточность информации. Он состоит в по-
вторении при определенных критериях некоторых характеристик сообщения. Рас-
смотрим пример, который поможет пояснить процесс. Возьмем текст, в котором
каждое слово состоит из четырех битов, общее количество различных слов — 16
(т. к. 24 = 16), каждое слово имеет вид а}а2а^а4 Перед отправкой сообщения мы
добавим к слову еще три бита c]c2c3, так что закодированное сообщение при дви-
жении по каналу связи будет выглядеть как а1а2а3о4с)с2с3 Дополнительные символы
с1с2с3 обеспечивают надежность сообщения. Они называются контрольными бита-
ми, или битами четности, и строятся следующим образом.
_ 0, если сумма а( + а2 + а3 — четная
1 1, если сумма а1 + а2 + а3 — нечетная
, 0, если сумма а + а, + а — четная
с2 = \ 1 11
z 1, если сумма Э] + а2 + а4 — нечетная
_ { 0, если сумма а2 + а3 + а4 — четная
3 1, если сумма а2 + а3 + а4 — нечетная
84
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Добавим следующие биты четности к сообщению 0111.
Так как сумма 0 + 1 + 1 — 2 четная, — 0.
Так как сумма 0 + 1 + 1 = 2 четная, с2 = 0.
Так как сумма 1 + 1 + 1 = 3 нечетная, с3 = 1.
Следовательно, сообщение 0111 будет передано в виде 0111001. Для всех 16
«слов» мы, таким образом, получим следующую таблицу:
Оригинальное сообщение Посланное сообщение
0000 0000000
0001 0001011
0010 0010111
0100 0100101
1000 1000110
1100 1100011
1010 1010001
1001 1001101
оно 0110010
0101 0101110
ООН 0011100
1110 1110100
1101 1101000
1011 юною
0111 0111001
1111 1111111
ГЕНИЙ БЕЗ НАГРАДЫ
Клод Элвуд Шеннон (1916-2001) был одним из величайших научных деяте-
лей XX в. Получив образование по специальности «электротехника» в Мичиган-
ском университете и Массачусетском технологическом институте, он работал
математиком в лаборатории компании «Белл», где занимался исследования-
ми по криптографии и теории коммуникации. Его научный вклад настолько ве-
лик, что он считается одним из основоположников теории информации, но по-
скольку его работы были на стыке математики и информационных технологий,
он так и не получил самой престиж! юй среди ученых Нобелевской премии.
85
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Допустим, что на другом конце сообщение будет получено в виде 1010110. За-
метим, что такая комбинация нулей и единиц не входит в число возможных кодов
и, следовательно, является ошибкой при передаче. В попытке исправить ошибку си-
стема сравнивает каждую цифру с набором цифр всех возможных кодов, чтобы най-
ти наиболее вероятную альтернативу. Для этого система проверяет, какие из цифр
представляют собой ошибку, следующим образом.
Возможное сообщение 0000000 0001011 0010111 0100101 1000110
Полученное сообщение 1010110 1010110 1010110 1010110 1010110
Количество отличающихся цифр 4 5 2 5 1
Возможное сообщение 1100011 1010001 1001101 0110010 0101110
Полученное сообщение 1010110 1010110 1010110 1010110 1010110
Количество отличающихся цифр 4 3 4 3 4
Возможное сообщение 0011100 1110100 1101000 1011010 0111001 1111111
Полученное сообщение 1010110 1010110 1010110 1010110 1010110 1010110
Количество отличающихся цифр 3 2 5 2 6 3
Ошибочное слово (1010110) отличается от другого слова (1000110) одной циф-
рой. Так как эта разница наименьшая, система предложит получателю этот второй,
исправленный вариант. Аналогичный принцип использует программа контроля
правописания текстового редактора. При обнаружении слова, которое не содер-
жится в ее внутреннем словаре, программа предлагает ряд близких альтернатив.
Количество позиций, в которых соответствующие символы двух слов (понимаемых
как последовательность символов) различны, называется расстоянием между дву-
мя последовательностями. Этот метод обнаружения и исправления ошибок был
предложен американцем Ричардом Хэммингом (1915—1998), современником Кло-
да Шеннона.
В теории информации, как и в любой другой области, одно дело — обнаружить
возможные ошибки, и совсем другое — исправить их. В шифровании, как в по-
следнем примере, если имеется только один кандидат с наименьшим расстоянием,
проблема достаточно проста. Пусть t — минимальное количество раз, когда единица
появляется в последовательности цифр (исключая последовательность, где все нули),
тогда:
86
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Если t — нечетное, мы можем исправить----ошибок.
2
Если t — четное, мы можем исправить —— ошибок.
2
Если наша цель заключается только в обнаружении ошибок, максимальным коли-
чеством ошибок, которые мы можем обнаружить, будет t — 1. В языке из 16 симво-
лов, описанном выше, t — 3, значит, наш метод способен обнаружить 3 — 1 = 2 ошиб-
ки и исправить — (3 — 1) : 2 = 1 — одну ошибку.
КРИПТОГРАФИЯ ТРЕТЬЕГО ПОКОЛЕНИЯ
В 1997 г. был введен протокол для надежной передачи информации с помощью беспроводных
сетей под названием WEP (сокращение от Wired Equivalent Privacy). Этот протокол включает алго-
ритм шифрования RC4 с двумя типами кодирования 5 и 13 ASCII-символов соответственно. Мы
имеем дело, таким образом, с кодированием 40 или 104 битов или, другими словами, 10 или
26 шестнадцатеричных символов:
5 ASCII-символ' в - 40 битов - 10 шестнадцатеричных символов;
13 ASCII-символов - 104 битов - 26 шестнадцатеричных символов.
Провайдер подключения предоставляет коды, хотя пользователь может, в принципе, их изме-
нить. До установления связи компьютер запрашивает ключ. В следующем диалоговом окне мы
видим сообщение об ошибке при запросе WEP-ключа с указанием его длины в битах, ASCII-
и шестнадцатеричных символах:
Wireless configuration
©The network password has to be 40 bits or 104 bits depending on its network conf igurmon
It can be written as 5 or 13 ASCI characters, or 10 or 26 hexadecimal characters
| Enter |
На самом деле реальные ключи длиннее. Используя ключ, выбранный пользователем, алгоритм
RC4 генерирует новый с большим количеством битов, который и используется для шифрования
передаваемых данных. Это - криптография с открытым ключом, и о ней будет более подробно
рассказано в пятой главе. Пользователь, который желает поменять ключ, должен помнить, что
ключ из десяти шестнадцатеричных символов более надежен, чем ключ из пяти букв и цифр, хотя
битовый размер у них одинаковый. Однако очевидно, что слово james легче запомнить, чем его
шестнадцатеричный эквивалент «6A616D6573».
87
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Другие коды: коммерческие и индустриальные стандарты
Хотя и не такие впечатляющие, как криптография или двоичная математика, и ча-
сто незаметные для нас, несмотря на их вездесущность, стандартизированные коды
банков, супермаркетов и других крупных подсистем экономики являются одной
из основ современного общества. Только в этом случае задача состоит в обеспечении
уникальной и точной идентификации продукта, будь то банковские счета, книги или
яблоки. Рассмотрим эти коды более подробно.
Кредитные карты
Дебетовые и кредитные карты, предлагаемые крупными банками и универмагами,
фактически определяются набором групп чисел, рассчитанных и проверяемых одним
и тем же алгоритмом, основанным на уже известной нам модульной арифметике.
Большинство карт имеет 16 цифр от 0 до 9. Числа сгруппированы по четыре цифры,
чтобы их легче было прочитать. Для наших целей мы будем обозначать их следую-
щим образом:
ABCD EFGH IJKL MNOP
Каждая группа цифр кодирует определенную информацию: первая группа
(ABCD) идентифицирует банк (или любой другой субъект, оказывающий услуги).
Каждый банк имеет свой номер, который может меняться в зависимости от кон-
тинента, а также от бренда карты и условий. Пятая цифра (Е) соответствует типу
карты и указывает, какое финансовое учреждение управляет счетом.
Тип Провайдер
3 American Express
4,0,2 Visa
5,0 MasterCard
6 Discover
Как мы видим, это не жесткое правило.
Следующие десять цифр (FGH IJKL MNO) являются уникальным идентифи-
катором для каждой карты. Эти числа связаны с номером счета клиента, с уровнем
карты — Classic, Gold, Platinum и т. д., а также с кредитным лимитом, сроком дей-
ствия и процентными ставками по типу баланса.
88
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Наконец, контрольная цифра (Р) связана с предыдущими цифрами в соответ-
ствии с алгоритмом Луна.
В России первые шесть цифр номера карты (ABCDEF) являются банковским
идентификационным номером (БИН). Первая из этих шести цифр указывает на
платежную систему. Например, у карт Visa первая цифра — 4, у MasterCard — 5.
Седьмая и восьмая цифры номера карты (GH) уточняют, в рамках какой про-
граммы банка была выпущена карта. Следующие семь цифр (IJKL MNO) иденти-
фицируют непосредственно карту. Последняя цифра (Р) — контрольная.
Алгоритм Луна назван так в честь Ганса Питера Луна, немецкого инженера,
разработавшего его. Для 16-значной карты этот алгоритм работает следующим об-
разом.
1. Каждую цифру в нечетной позиции, начиная с первого числа слева, мы ум-
ножаем на два. Если результат больше 9, мы складываем обе цифры этого дву-
значного числа (или, что то же самое, вычитаем из него 9). Например, если мы
получили 18, сложение цифр дает 1 + 8 = 9, а вычитание — 18 — 9 — 9.
2. Затем мы складываем все полученные таким образом результаты, а также
цифры, расположенные на четных позициях (в том числе последнюю контроль-
ную цифру).
3. Если окончательная сумма кратна 10 (то есть ее значение равно нулю по моду-
лю 10), номер карты является действительным. Заметим, что именно последняя
контрольная цифра делает общую сумму кратной 10.
DINER’S CLUB
Одной из первых кредитных карт, получивших широкое признание, была карта Diner's Club. Ав-
тором идеи был американец Фрэнк Макнамара. В 1950 г. ему удалось убедить различные ре-
стораны принимать оплату безналично с помощью персональных гарантированных кредитных
карт, которые Макнамара распространил среди своих лучших клиентов. Наиболее часто в пер-
вые десятилетия кредитными картами расплачивались за обеды американские коммивояжеры,
будучи в дороге.
89
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Например, пусть карта имеет следующий номер:
1234 5678 9012 3452
По алгоритму Луна имеем:
1-2 = 2
3-2 = 6
5-2 = 10 =s> 1+0 = 1
7-2=14 =>1+4 = 5 (или 14-9 = 5)
9-2 = 18 =>1+8 = 9
1-2 = 2
3-2 = 6
5-2 = 10 => 1+0 = 1
Далее найдем сумму результатов и цифр на четных позициях:
2 + 6 + 1 + 5 + 9 + 2 + 6 + 1 = 32
2 + 4 + 6 + 8 + 0 + 2 + 4 + 2 = 28
32 + 28 = 60
Результат равен 60, это число кратно 10. Поэтому номер карты является дей-
ствительным.
Алгоритм Луна можно применить другим способом: номер карты ABCD
EFGH IJKL MNOP является правильным, если удвоенная сумма цифр на нечет-
ных позициях и сумма цифр на четных позициях плюс количество цифр на нечет-
ных позициях, которые больше, чем 4, кратно 10. Это правило записывается так:
2 (A+C+E+G+I+K+M+O) + (B+D+F+H+J+L+N+P) + (количество цифр
на нечетных позициях, которые больше, чем 4) = 0 (mod 10).
Применим это правило к предыдущему примеру:
1234 5678 9012 3452
2 (1+3+5+7+9+1+3+5) + (2+4+6+8+0+2+4+2) + (4) = 100 = 0 (mod 10).
Снова мы убедились, что номер кредитной карты является действительным,
и показали, что на первый взгляд случайные номера карт соответствуют строгому
математическому стандарту.
90
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
ПРИМЕР РАСЧЕТА КОНТРОЛЬНОЙ ЦИФРЫ КРЕДИТНОЙ КАРТЫ
В EXCEL
Номер кредитной карты состоит из 15 цифр плюс контрольная цифра. Цифры сгруппированы в че-
тыре группы по четыре цифры. Контрольная цифра (КЦ) рассчитывается следующим образом.
В CDEFGHIJKLMNOPQRSTUV
2 ____
3 Номер кредитной карты: | 5 5 2 ~1~| | 4 5 7 ~2~] | 6 1 6 ~2~| | 3 6 2 ~4~]
4
5 Используемые цифры: 5 2 1 4 5 7 2 6 16 2 3 6 2
6 Цифры на четных позициях: 2 4 7 6 6 3 2
7 Сумма цифр на четных позициях: 30
8 Число цифр, больших 4, на четных позициях: 3
9 Сумма предыдущих сумм: 33
10 Цифры на нечетных позициях: 5 1 5 2 1 2 6
11 Сумма цифр на нечетных позициях: 22
12 Сумма двух предыдущих результатов плюс 1: 56
13 Остаток от деления предыдущего результата на 10: 6
14 Контрольная цифра - это 0, если предыдущий результат равен нулю, иначе это 10 минус предыдущий результат: 4
Можно ли восстановить цифру, отсутствующую в номере карты? Да, если мы
имеем дело с действительной кредитной картой. Найдем, например, цифру X в но-
мере 4539451203X87356.
Начнем с умножения на 2 цифр на нечетных позициях (4—3—4—1—0—X—7—5),
сразу преобразуя результат к одной цифре.
4*2 = 8
3-2 = 6
4-2 = 8
1-2 = 2
0-2 = 0
X • 2 = 2Х
7 • 2 = 14,14 - 9 = 5
5 • 2 = 10,10 - 9 = 1.
Складывая цифры, стоящие на четных позициях, и новые цифры на нечетных,
получим:
91
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
30 + 41+ 2Х = 71+ 2Х.
Мы знаем, что число (71 + 2Х) должно быть кратно 10.
Если значение X меньше или равно 4, то для таких X (71 + 2Х) никогда не бу-
дет кратно 10.
Если же значение X больше 4, то кратно 10 должно быть выражение (71 + 2Х +
+ 1), так как X стоит на нечетной позиции. Видим, что выражение (72 + 2Х) крат-
но 10 только при X = 9.
Следовательно, мы нашли потерянную цифру 9, и полный номер кредитной кар-
ты: 4539451203987356.
Штрихкоды
Первая система штрихкодов была запатентована 7 октября 1952 г. американцами
Норманом Вудландом и Бернардом Сильвером. Первые версии штрихкодов отли-
чались от сегодняшних. Вместо привычных нам линий Вудланд и Сильвер придума-
ли концентрические круги. Впервые штрихкоды начали официально использоваться
в 1974 г. в магазине города Трой, штат Огайо.
Современные штрихкоды представляют собой последовательность черных полос
(которые кодируются как 1 в двоичной системе) и пробелов между ними (которые
кодируются как 0). Штрихкоды используются для идентификации физических объек-
тов. Штрихкоды, как правило, печатаются на этикетках и считываются оптическими
устройствами. Это устройства, похожие на сканер, которые измеряют отраженный
свет и преобразуют темные и светлые области в буквенно-цифровой код, который
затем посылается на компьютер. Существует множество стандартов для штрихкодов:
110 1 0 0 1
Толщина штрихов и пробелов в штрихкоде соответствует двоичным цифрам.
92
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Code 128, Code 39, Codabar, EAN (этот стандарт появился в 1976 г. в двух версиях, со-
стоящих из 8 и 13 цифр соответственно) и UPC (Universal Product Code — универсаль-
ный код товара, используемый в основном в США и доступный также в двух версиях
из 12 и 8 цифр соответственно). Наиболее распространенной является 13-значная версия
EAN. Несмотря на разнообразие стандартов, штрихкоды позволяют идентифицировать
любой продукт в любой части мира быстро и без существенных ошибок.
Oct 7,3952
rued Jet. 20, ХОД
F J. WOODLAND ET AL
CLAJJiniHC hl.JUU.TU3 W ЕЛЮ0
2,612,994
S Sheets-Sheet X
1 2 J 4
FIG 6
FIG 5
Патент системы Вудланда и Сильвера с концентрическими кругами, предшественниками
современных штрихкодов.
93
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
ПРОГРАММА В EXCEL ДЛЯ РАСЧЕТА
КОНТРОЛЬНОЙ ЦИФРЫ КОДА EAN-13
Штрихкод стандарта EAN-13 - это номер из 12 цифр плюс тринадцатая цифра, называемая кон-
трольной цифрой (КЦ). 13 цифр составляют четыре группы:
С D Е х! G Н - 1 К L М N ° р Q R
3 Страна Компания Продукт КЦ
4 3 4 1 0 3 5 9 1 2 5 9 2 2
5
6 Сумма цифр на нечетных позициях 27
7 Сумма цифр на четных позициях и результат, умноженный на 3 51
8 Сумма двух предыдущих результатов 78
9 Остаток от деления предыдущего результата на 10 8
10 Контрольная цифра — зто 0 или 10 минус предыдущий результат 2
Используя команды программы Excel, этот алгоритм будет работать следующим образом:
С D Е F G Н 1 J К Г [м N 0 Р Q R
3 Страна Компания Продукт КЦ
4 3 4 1 0 3 5 9 1 2 5 9 2 =R10
5
6 Сумма цифр на нечетных позициях =C4+F4+H4+J4+M4+04
7 Сумма цифр на четных позициях, умноженная на 3 =(D4+G4+I4+L4+N4+P4)*3
8 Сумма двух предыдущих результатов =R6+R7
9 Остаток отделения предыдущего результата на 10 =OCTAT(R8;10)
10 Контрольная цифра: 0 или 10 минус предыдущий результат =ECnM(R9=0;0;10-R9)
94
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Стандарт штрихкода EAN-13
Стандарт EAN в момент создания в 1976 г. являлся аббревиатурой (European
Article Number — европейский номер товара), а сейчас известен как Международ-
ный номер товара. Это наиболее устоявшийся стандарт штрихкодов, используемый
во всем мире. Штрихкоды EAN обычно состоят из 13 цифр, представленных чер-
ными полосами и пробелами, вместе образующими двоичный код, который легко чи-
тать. EAN-13 изображает эти 13 цифр с помощью 30 черных и белых полос. Цифры
делятся на три группы: первая, состоящая из двух или трех цифр, обозначает код
страны; вторая, состоящая из 9 или 10 цифр (в зависимости от длины кода страны),
указывает компанию и продукт, и третья, состоящая из единственной цифры, вы-
ступает в качестве контрольного кода. Для штрихкода ABCDEFGHIJKLM эти
группы выглядят так:
Первые три цифры (АВС) обозначают код страны, производящей товар. Для
России этот код может быть от 460 до 469. Для некоторых стран этот код мо-
жет быть двузначным; тогда третья цифра входит в следующую группу.
Следующие шесть цифр (DEFGHI) обозначают компанию, производящую
продукт. В этой группе может быть 4—6 цифр.
Остальные три цифры (JKL) означают код продукта, который был выбран ком-
панией. В этой группе может быть 3—5 цифр.
Последняя цифра (М) — контрольный код. Чтобы вычислить его, мы должны
сложить цифры на нечетных позициях, начиная с левой и без учета контрольной.
К полученному значению мы прибавим утроенную сумму цифр на четных пози-
циях. Тогда контрольная цифра дополняет общую сумму до значения, кратного
10. Как видно, контрольный алгоритм системы штрихкодов очень напоминает
правило контроля кредитных карт.
8 413871 003049
Проверим, действителен ли следующий штрихкод:
8413871003049
95
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
8 + 1 + 8 + 1 + 0 + 0 + 3-(4 + 3 + 7 + 0 + 3 + 4) = 18 + 3-21 = 18 + 63 = 81.
Правильная контрольная цифра должна быть 90 — 81 = 9.
Математическая модель алгоритма основана на модульной арифметике (по моду-
лю 10) и работает следующим образом.
Для штрихкода ABCDEFGHIJKLM обозначим за N следующее значение:
A + C + E + G + I + K + 3-(B + D + F + H+ J + L) = N,
и пусть п будет значение N по модулю 10. Контрольная цифра М определяется как
М = 10 — и. В нашем примере 81 = 1 (mod. 10), поэтому контрольная цифра дей-
ствительно 10 — 1 = 9.
Предыдущий алгоритм можно сформулировать по-другому, используя в рас-
четах контрольную цифру. Следующий метод позволяет проверить правильность
контрольной цифры, даже не вычисляя ее.
A + C + E + G + I + K+ 3-(B + D + F + H + J + L) = 0 (mod 10).
Например, для штрихкода
5701263900544
5 + 0 + 2 + 3 + 0 + 5 + 3-(7 + 1 + 6 + 9 + 0 + 4) + 4 = 100.
100 = 0 (mod 10).
Значит, штрихкод действителен.
Теперь попробуем определить значение утерянной цифры в штрихкоде, а имен-
но, цифры X в следующем коде:
401332003X497
96
ПРОЦЕСС ОБЩЕНИЯ ПОСРЕДСТВОМ НУЛЕЙ И ЕДИНИЦ
Подставим цифры в формулу в соответствии с алгоритмом
4 + 1 + 3 + 0 + 3 + 4 + 3 • (0 + 3 + 2 + 0 + X + 9) + 7 = 64 + ЗХ = 0 (mod 10).
По модулю 10 получим следующее уравнение:
4 + 3X = 0(mod 10).
ЗХ = —4 + 0 = —4 + 10 = 6 (mod 10).
Заметим, что число 3 имеет обратный элемент, т. к. НОД (3,10) = 1.
Отсюда видим, что X должно быть 2. Поэтому правильный штрихкод
4013320032497.
QR-КОД
В 1994 г. японская компания Denso-Wave разрабо-
тала графическую систему шифрования для иден-
тификации автомобильных деталей на сборочной
линии. Система была названа QR (Quick Response -
«быстрый отклик») из-за скорости, с которой ин-
формация может быть прочитана машинами, пред-
назначенными для этой цели, и стала использо-
ваться не только на автомобильных заводах. Всего
несколько лет спустя большинство японских мобиль-
ных телефонов могли считывать информацию, со-
держащуюся в коде. QR-код является матричным ко-
дом, представляющим собой некоторое количество
черных и белых квадратов, расположенных в виде
QR-код, составленный из 37 рядов,
для университета Осаки, Япония
большого квадрата. Квадраты соответствуют двоичным значениям, 0 или 1, и, следовательно,
работают аналогично штрихкодам, хотя двумерность кода позволяет хранить намного больше
информации.
97
Глава 5
Общедоступная тайна:
криптография с открытым ключом
При быстром развитии вычислительной техники криптография вовсе не игнориро-
валась. Процесс шифрования сообщения с помощью компьютера почти не отли-
чается от шифрования без компьютера, но есть три основных отличия. Во-первых,
компьютер можно запрограммировать для имитации работы обычной шифровальной
машины, например, с 1000 роторами, что избавляет от необходимости физически
создавать такие устройства. Во-вторых, компьютер работает только с двоичными
числами и, следовательно, все шифрование будет происходить на этом уровне (даже
если числовая информация потом снова будет расшифрована в текст). И в-третьих,
компьютеры очень быстро работают с вычислениями и расшифровывают сообщения.
Первый шифр, предназначенный для того, чтобы воспользоваться потенциалом
компьютеров, был разработан в 1970-х гг. Например, «Люцифер», шифр, который
разделял текст на блоки по 64 бита и зашифровывал некоторые из них с помощью
сложной подстановки, а затем группировал их снова в новый блок зашифрованных
битов и повторял процесс. Для работы такой системы было необходимо, чтобы от-
правитель и получатель имели компьютеры с одной и той же программой шифрова-
ния, а также общий цифровой ключ. 56-битная версия шифра «Люцифер», названная
DES, была разработана в 1976 г. DES (Data Encryption Standard — «стандарт шиф-
рования данных») по-прежнему используется в наши дни, хотя этот шифр был взло-
ман в 1999 г. и заменен 128-битным AES (Advanced Encryption Standard) в 2002 г.
Без сомнения, такие алгоритмы шифрования сполна использовали вычислитель-
ную мощность компьютеров, но, как и их предшественники тысячелетней давности,
компьютерные шифры по-прежнему были уязвимы, поскольку несанкционирован-
ный получатель мог перехватить ключ и, зная алгоритм шифрования, расшифровать
сообщение. Этот основной недостаток каждой «классической» криптографической
системы известен как проблема распределения ключей.
Проблема распределения ключей
Всем известно, что для обеспечения безопасности кода ключи шифрования должны
быть защищены надежнее, чем алгоритм. Тогда возникает проблема: как безопасно
99
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
распределять ключи. Даже в простых случаях это является серьезной проблемой
логистики, например, как распределить тысячи шифровальных книг среди радистов
большой армии, или как доставить книги в мобильные центры связи, работающие
в экстремальных условиях, такие как станции на подводных лодках или штабы
на линии фронта. Какой бы сложной ни была классическая система шифрования,
она остается уязвимой, так как соответствующие ключи могут быть перехвачены.
Алгоритм Диффи - Хеллмана
Сама концепция безопасного обмена ключами может показаться противоречивой:
как вы можете послать ключ в виде сообщения, которое уже как-то зашифровано?
Ключом, переданным заранее обычным способом? Однако, если ключами действи-
тельно несколько раз обменивались, то решение проблемы можно себе предста-
вить — по крайней мере, на теоретическом уровне.
Предположим, что отправитель по имени Джеймс шифрует сообщение с по-
мощью своего ключа и посылает результат получателю по имени Питер, который
повторно шифрует зашифрованное послание своим ключом и возвращает его от-
правителю. Джеймс расшифровывает сообщение своим ключом и посылает назад
результат, т. е. текст, в данный момент зашифрованный только ключом Питера,
который его расшифровывает. Казалось бы, вековая проблема безопасного обме-
на ключами решена! Неужели это правда? К сожалению, нет. В любом сложном
алгоритме шифрования порядок применения ключей имеет решающее значение,
а в нашем примере мы видим, что Джеймс расшифровывает сообщение, которое
АВТОРЫ АЛГОРИТМА
Уитфилд Диффи (слева) родился в 1944 г. в Соединен-
ных Штатах. Получив степень бакалавра математики
в Массачусетском технологическом институте (MIT), он
с 2002 по 2009 гг. работал главой службы безопас-
ности и вице-президентом компании Sun Microsystems
(в Калифорнии).
Инженер Мартин Хеллман родился в 1945 г. и работал
в IBM и Массачусетском технологическом институте, где
сотрудничал с Диффи.
100
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
уже зашифровано другим ключом. Когда порядок ключей меняется, результат бу-
дет абракадаброй. Вышеизложенный пример не объясняет теории подробно, но он
дает подсказку к решению проблемы. В 1976 г. два молодых американских ученых,
Уитфилд Диффи и Мартин Хеллман, нашли способ, при котором два человека мо-
гут обмениваться зашифрованными сообщениями без всякого обмена секретными
ключами. Этот метод использует модульную арифметику, а также свойства простых
чисел. Идея заключается в следующем.
1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это
число N .
2. Питер выбирает другое случайное число, которое он тоже держит в секрете.
Мы обозначим это число Npf
3. Затем и Джеймс, и Питер применяют к своим числам функцию вида /(х) =
= a* (mod р), где р — простое число, известное им обоим.
• После этой операции Джеймс получает новое число, N 7, которое он посы-
лает Питеру.
• А Питер посылает Джеймсу свое новое число Np2.
4. Джеймс вычисляет (mod р) и получает новое число С^.
5. Питер вычисляет (mod р) и получает новое число Ср.
Хотя это кажется невозможным, но числа и Ср являются одинаковыми. И те-
перь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией
только тогда, когда они выбрали функцию /(х) — a* (mod р) и послали друг другу
числа N/2 и Np2. Ни то, ни другое не является ключом, поэтому перехват этой ин-
формации не будет угрожать безопасности системы шифрования. Ключ этой систе-
мы имеет следующий вид:
(mod р).
Важно также учесть, что данная функция имеет одну особенность: она необра-
тима, то есть зная саму функцию и результат ее применения к переменной х, невоз-
можно (или, по крайней мере, очень сложно) найти исходное значение х.
101
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
Далее, чтобы пояснить идею, мы повторим процесс с конкретными значениями.
Возьмем следующую функцию:
/(*) = 7л (mod И).
1. Джеймс выбирает число, например, 3, и подставляет в функцию / (3) =
= 73 = 2(mod И).
2. Питер выбирает число, N , например, 6, и подставляет в функцию / (6) = 76=
= 4 (mod И).
3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу — свой, 4.
4. Джеймс считает 43 = 9 (mod И).
5. Питер считает 26 = 9 (mod 11).
Это число, 9, и будет ключом системы.
Джеймс и Питер обменялись функцией /(х) и числами 2 и 4. Будет ли эта ин-
формация полезна злоумышленнику? Допустим, злоумышленник знает и функцию,
и числа. Тогда он должен найти и Npi по модулю И, где и Npi — такие числа,
которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удаст-
ся узнать эти числа, он получит ключ, лишь вычислив л'Ч/| Np' по модулю р. Решение
уравнения вида у — а*, кстати, в математике называется дискретным логарифмом.
Например, в случае:
/(х) = 3х (mod 17),
зная, что 3х — 15 (mod 17), и пробуя различные значения х, мы получим, что
х = 6.
Алгоритмы этого типа и задачи с дискретным логарифмом не получали должного
внимания вплоть до начала 1990 гг., и лишь в последнее время эти методы начали
разрабатываться. В приведенном выше примере число 6 является дискретным лога-
рифмом числа 15 с основанием 3 по модулю 17.
Особенностью этого типа уравнений, как мы уже говорили, является сложность
обратного процесса — они асимметричны. Если р больше 300, а число а больше
100, решение — и, следовательно, взлом ключа — становится крайне сложной за-
дачей.
102
ОБЩЕДОСТУПНАЯ ТАИНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
ВИРУСЫ И БЭКДОРЫ
Даже самый безопасный шифр с открытым ключом зависит от закрытого ключа, который держит-
ся в секрете. Следовательно, если компьютерный вирус заражает компьютер, находит и переда-
ет этот закрытый ключ, вся система шифрования сводится на нет. В 1998 г. стало известно, что
одна швейцарская компания, лидер в области производства и распространения криптографиче-
ских продуктов, включала в свои продукты бэкдоры («черные ходы»), которые обнаруживали за-
крытые ключи пользователей и пересылали их компании. Часть этой информации передавалась
правительству Соединенных Штатов, которое, таким образом, могло читать сообщения, посылае-
мые инфицированными компьютерами.
Этот алгоритм является основой современной криптографии. Диффи и Хеллман
представили свою идею на Национальной компьютерной конференции, на семина-
ре, который можно назвать поворотным. В полном объеме их работу можно почи-
тать на www.cs.berkeley.edu/~christos/classics/diffiehellman.pdf, статья с названием
«Новые направления в криптографии».
Алгоритм Диффи—Хеллмана продемонстрировал возможность создания крип-
тографического метода, который не требует обмена ключами, хотя, как ни парадок-
сально, использует открытую связь — передачу пары первых чисел, которые слу-
жат для определения ключа.
Иными словами, это дало возможность иметь надежную систему шифрования
между отправителем и получателем, которым нет необходимости встречаться и до-
говариваться о секретном ключе. Однако некоторые проблемы все же существуют:
если Джеймс хочет послать сообщение Питеру в то время, когда Питер, например,
спит, ему придется подождать, когда его коллега проснется, чтобы завершить про-
цесс генерации ключа.
Пытаясь найти новые, более эффективные алгоритмы, Диффи придумал систе-
му, в которой ключ для шифрования отличается от ключа, используемого для рас-
шифровки, и, следовательно, они никак не могут быть получены один из другого.
В этой теоретической системе отправитель имеет два ключа: для шифрования и для
расшифровки. Из этих двух отправитель делает открытым только первый, чтобы
любой человек, желающий отправить ему сообщение, мог зашифровать его. Полу-
чив это сообщение, отправитель расшифрует его, используя второй ключ, который,
конечно, останется в тайне. Возможно ли использовать такие системы на практике?
103
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
Простые числа спешат на помощь: алгоритм шифрования RSA
В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин
Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific
American так: «Новый вид шифра, на расшифровку которого потребуются миллио-
ны лет». После объяснения принципа системы шифрования с открытым ключом он
показал само зашифрованное сообщение и открытый ключ N, используемый в этом
шифре:
N = 114 381 625 757 888 867 669 235 779 976 146
612 010 218 296 721 242 362 562 561 842 935 706 935 245 733
897 830 597 123 563 958 705 058 989 075 147 599 290 026 879
543 541.
Гарднер призвал читателей попробовать расшифровать сообщение, используя
предоставленную информацию, и даже дал подсказку: для решения необходимо
разложить число N на простые множители р и q. Более того, Гарднер назначил
приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит
правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер,
может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Лену Ад-
леману из Лаборатории информации Массачусетского технологического института.
Правильный ответ был получен лишь через 17 лет. Он стал результатом сотруд-
ничества более чем 600 человек. Ключами оказались р = 3276913299326670954
9 961988190 834 461413177642967992942539798288533 и q = 349052951
0 847 650 949147 849 619 903 898133 417 764 638 493 387 843 990 820 577, а за-
шифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».
Алгоритм, представленный Гарднером, известен как RSA — буквенная аббре-
виатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это
первое практическое применение придуманной Диффи системы шифрования с от-
крытым ключом, которая повсеместно используется и по сей день. Надежность ее
практически гарантирована, потому что процесс расшифровки является невероятно
сложным, почти невозможным делом. Далее мы рассмотрим основы этой системы
в упрощенной форме.
104
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
&
Подробнее об алгоритме RSA
Алгоритм RSA основан на некоторых свойствах простых чисел, о которых заинте-
ресованный читатель может подробнее прочитать в Приложении. Мы ограничимся
здесь изложением простых фактов, лежащих в основе алгоритма.
• Количество натуральных чисел, меньших п и взаимно простых с и, называется
функцией Эйлера и обозначается как 0(п).
• Если п = pq, где pnq — простые числа, то ф(п) = (р—1) (<7—1).
• Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля,
и р — простое число, то а pI = 1 (mod р).
• Согласно теореме Эйлера, если НОД (и, а) — 1, то = 1 (mod и).
Как уже упоминалось, система шифрования называется «с открытым ключом»,
потому что ключ шифрования доступен любому отправителю, желающему переда-
вать сообщения. Каждый получатель имеет свой открытый ключ. Сообщения всегда
передаются в виде цифр, будь то ASCII-коды или какая-либо другая система.
Сначала Джеймс вычисляет значение п путем умножения двух простых чисел
р и q (n = pq) и выбирает значение е так, чтобы НОД (ф(п), е) = 1. Напом-
ним, что ф(п) = (р—1) (<?—1). Данные, которые являются открытыми, — это зна-
чение п и значение е (ни при каких обстоятельствах нельзя выдавать значения р
и q). Пара (п, е) является открытым ключом системы, а значения р и q называются
RSA -числами. Затем Джеймс вычисляет единственное значение d по модулю ф(п),
которое удовлетворяет условию d • е = 1, то есть d является обратным элементом
к числу е по модулю ф(п). Мы знаем, что обратный элемент существует, потому что
НОД(ф( п), е) = 1. Это число d является закрытым ключом системы. Со своей сто-
роны, Питер использует открытый ключ (п, е) для шифрования сообщения М с по-
мощью функции М = mL (mod и). Получив сообщение, Джеймс вычисляет Md =
= (me)d (mod и), а это выражение эквивалентно Md — (me)d = m (mod n), что сви-
детельствует о возможности расшифровать сообщение.
Теперь мы применим эту процедуру к конкретным числовым значениям.
Если р = 3 и q = И, получим п = 33. Тогда 0(33) = (3—1) • (11—1) = 20.
Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый
ключ Джеймса (33,7).
105
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
• Джеймс также вычислил закрытый ключ d, который является обратным эле-
ментом к числу 7 по модулю 20, а именно число d = 3, так как 7 • 3 = 1 (mod 20).
• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы за-
шифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:
97 = 4782969 = 15 (mod 33).
Зашифрованное сообщение имеет вид «15». Питер посылает его нам.
Джеймс получает сообщение «15» и расшифровывает его следующим образом:
153 = 3375 = 9 (mod 33).
Сообщение расшифровано правильно.
Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA
становятся такими сложными, что нам придется использовать компьютер. Напри-
мер, если р = 23 и q — 17, то п = 391. Открытым ключом при выбранном е = 3 будет
пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки
будет выглядеть так:
204235 = 34 (mod 391).
Обратите внимание на степень числа и представьте себе гигантское количество
расчетов, необходимых для нахождения этого решения.
Почему мы можем доверять алгоритму RSA
Потенциальный шпион располагает значениями пив, потому что они являются откры-
тыми. Чтобы расшифровать сообщение, ему нужно также значение d, т. е. закрытый
ключ. Как мы показали в предыдущем примере, значение d получается из п и е. Чем же
обусловлена безопасность? Напомним, что для построения d необходимо знать ф (и ) =
= (p-D U-1). в частности, р и q. Для этого «достаточно» разложить п на простые
множители pnq. Проблема для шпиона заключается в том, что разложение большо-
го числа на простые множители является медленным и трудоемким процессом. Если
п достаточно большое (состоящее более чем из 100 цифр), не существует известных
способов нахождения р и q за разумное количество времени. В настоящее время
простые числа, используемые для шифрования чрезвычайно конфиденциальных со-
общений, состоят более чем из 200 цифр.
106
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
Приемлемая конфиденциальность
Алгоритм RSA требует много машинного времени и очень мощных процессоров.
До 1980-х гг. только правительства, армия и крупные предприятия имели достаточ-
но мощные компьютеры для работы с RSA. В результате у них была фактически мо-
нополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, амери-
канский физик и борец за сохранение конфиденциальности, предложил бесплатную
систему шифрования PGP (Pretty Good Privacy — «достаточно хорошая степень
конфиденциальности»), алгоритм которой мог работать на домашних компьютерах.
PGP использует классическое симметричное шифрование, что и обеспечивает ей
большую скорость на домашних компьютерах, но она шифрует ключи по асимме-
тричному алгоритму RSA.
Циммерман объяснил причины этой меры в открытом письме, которое заслужи-
вает быть процитированным здесь, по крайней мере, частично из-за пророческого
описания того, как мы живем, работаем и общаемся два десятилетия спустя.
«Это личное. Это конфиденциальное. И это только ваше дело и ничье другое.
Вы можете планировать политическую кампанию, обсуждать ваши налоги или
иметь тайную любовную связь. Или вы можете заниматься тем, что вам не ка-
жется незаконным, хотя таковым является. Что бы то ни было, вы не хотите, что-
бы ваши личные электронные письма или конфиденциальные документы были
прочитаны кем-то еще. Нет ничего плохого в том, чтобы охранять вашу частную
жизнь. Частная жизнь неприкосновенна, как Конституция...
Мы движемся к будущему, где мир будет опутан волоконно-оптическими сетями
высокой емкости, связывающими наши повсеместно распространенные персо-
нальные компьютеры. Электронная почта станет нормой для всех, а не новинкой,
как сегодня. Правительство будет защищать наши электронные сообщения го-
сударственными протоколами шифрования. Наверное, большинство людей при-
мет это. Но, возможно, некоторые захотят иметь свои собственные защитные
меры... Если конфиденциальность признать вне закона, только люди вне закона
будут ею обладать.
Спецслужбы обладают лучшими криптографическими технологиями. Как и тор-
говцы оружием и наркотиками. Как и военные подрядчики, нефтяные компании
и другие корпорации-гиганты. Но обычные люди и общественные организации
107
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
БЕЗОПАСНОСТЬ ДЛЯ ВСЕХ
Филипп Циммерман, родившийся в 1954 г., американский
физик и инженер-программист, стоявший у истоков движения,
которое стремится сделать современную криптографию до-
ступной для всех. Кроме разработки системы PGP он в 2006 г.
создал Zfone - программу для безопасной голосовой связи
через Интернет. Он является президентом альянса OpenPGP,
выступающего за открытое программное обеспечение.
практически не имеют недорогих защитных криптографических технологий с от-
крытым ключом. До сих пор не имели.
PGP дает людям возможность самим защищать свою конфиденциальность. Се-
годня существует растущая социальная потребность в этом. Вот почему я на-
писал PGP».
Из слов Циммермана мы видим, что жизнь в век информации сопряжена с угро-
зой нашим традиционным представлениям о частной жизни. Следовательно, глубо-
кое понимание кодирования и механизмов шифрования, используемых вокруг нас,
не только делает нас мудрее, но также может оказаться чрезвычайно полезным, ког-
да речь идет о защите того, что для нас особенно ценно.
PGP с момента его создания становится все более популярным и представляет
собой наиболее важный инструмент шифрования, доступный сегодня частным лицам.
Проверка подлинности сообщений и ключей
Различные системы шифрования с открытым ключом — или сочетающие открытые
и закрытые ключи, как, например, PGP — обеспечивают высокий уровень кон-
фиденциальности при передаче информации. Тем не менее, безопасность сложных
систем связи, таких как интернет, заключается не только в конфиденциальности.
До появления современных коммуникационных технологий подавляющее боль-
шинство сообщений приходило от известных адресатов: от членов семьи, от друзей
или от партнеров по бизнесу. Сегодня, однако, на каждого человека обрушивается
лавина сообщений из множества источников. Подлинность этих сообщений часто
невозможно определить исходя лишь из их содержания, со всеми вытекающими
108
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
проблемами. Например, как мы можем предотвратить фальсификацию адреса элек-
тронной почты отправителя?
Диффи и Хеллман сами предложили гениальный способ использования шифрова-
ния с открытым ключом для проверки подлинности сообщения. В криптографических
системах такого типа отправитель шифрует сообщение с помощью открытого ключа
получателя, который в свою очередь использует свой закрытый ключ для расшифров-
ки сообщения. Диффи и Хеллман заметили, что RSA и другие подобные алгоритмы
обладают интересной симметрией. Закрытый ключ также можно использовать для
шифрования сообщения, а открытый — для расшифровки. Этот подход не усиливает
безопасность — ведь открытый ключ доступен для всех — зато получатель может
убедиться, что сообщение пришло от определенного отправителя, владельца закры-
того ключа. Чтобы проверить подлинность отправителя сообщения, теоретически
достаточно добавить к нормальному шифрованию дополнительные шаги.
1. Отправитель шифрует сообщение с помощью открытого ключа получателя.
Этот первый шаг гарантирует конфиденциальность.
2. Отправитель снова шифрует сообщение, на этот раз с помощью своего за-
крытого ключа. Таким образом удостоверяется подлинность сообщения, оно
«подписано».
3. Получатель использует открытый ключ отправителя, чтобы расшифровать
шифр шага 2. Таким образом проверяется подлинность сообщения.
4. Получатель теперь использует свой закрытый ключ, чтобы расшифровать
шифр шага 1.
Хеш-функции
Одна из проблем теоретического процесса, о котором говорилось выше, заключает-
ся в том, что шифрование открытым ключом требует значительной вычислительной
мощности и времени, и повторять этот процесс для подписания и проверки каждого
сообщения было бы чрезвычайно невыгодно. Именно поэтому на практике подпи-
сание сообщения осуществляется с помощью математических ресурсов, называемых
хеш-функциями. Для каждого оригинального сообщения эти функции генерируют
простую цепочку битов (обычно 160), называемых хешем или хеш-кодом. Алгоритм
работает таким образом, что вероятность того, что различные сообщения получат
один и тот же хеш-код, почти равна нулю. Кроме того, практически невозможно
обратить процесс и получить исходное сообщение, имея только хеш-код. Хеш каж-
109
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
дого сообщения отправитель шифрует своим закрытым ключом и отправляет вместе
с зашифрованным обычным образом исходным сообщением. Получатель расшиф-
ровывает с помощью открытого ключа отправителя ту часть сообщения, которая
содержит хеш. Далее, определив таким образом хеш-код отправителя, получатель
применяет хеш-функцию к полученному основному сообщению и сравнивает два
хеша. Если они совпадают, личность отправителя подтверждается, и, кроме того,
получатель теперь уверен, что никто не изменил исходное сообщение.
Хеш-
Сообщение Функция
RED
DKJD 1242 AACB 78813 761A
696C 2409 7009 CA99 2D17
THE COLOUR RED
CORRESPONDS
TO THE LOWEST FREQUENCY
THE COLOUR RED
CORRESPONDS
TO THE LOWEST FREQUENCY
THE COLOUR RED
CORRESPONDS
TO THE LOWEST FREQUENCY
0896 56BB ZC7I) CBE2 823C
ADD7 8CD1 9AB2 JJ6J 8ABC
FCD3 7FDB D588 4C75 4BF4
1799 7D88 ACDE 92B9 6A6C
1)401 C0A9 7D9A 46AF FB45
76B1 79A9 0DA4 AEH 4819
Небольшие различия в содержании сообщения приводят к совершенно разным хеш-кодам. Таким
образом, получатель может быть уверен, что текст не был изменен.
Сертификаты открытых ключей
Однако наиболее важной проблемой систем криптографии с открытым ключом яв-
ляется проверка не подлинности сообщения, а подлинности самих открытых клю-
чей. Как отправитель и получатель могут быть уверены, что открытые ключи их
партнеров подлинны? Допустим, шпион обманул отправителя, дав ему свой откры-
тый ключ и заставив его поверить, что это ключ получателя. Тогда, если шпиону
удастся перехватить сообщение, он может использовать свой закрытый ключ для
расшифровки. И чтобы избежать разоблачения, шпион затем использует открытый
ключ получателя для повторного шифрования сообщения и отправляет это сообще-
ние первоначальному адресату.
110
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
Вот почему существуют государственные и частные организации, занимающиеся
независимой сертификацией открытых ключей. Сертификат такого типа содержит,
помимо соответствующего ключа, информацию о владельце и сроке действия серти-
фиката. Владельцы этого типа ключей делают свои сертификаты открытыми, чтобы
ими можно было обмениваться с определенной степенью безопасности.
ЦИФРОВАЯ СТЕГАНОГРАФИЯ
Хотя это может показаться парадоксальным, развитие новых технологий привело к возрожде-
нию стеганографии. Обычный аудио-файл состоит из 16-битовых значений, воспроизводимых
с частотой в 44,1 кГц. Очень просто использовать некоторые из этих битов для передачи се-
кретных данных, так что слушатель вообще не заметит никакой акустической разницы. Файлы
изображений также можно использовать для передачи скрытой информации.
Пример цифровой стеганографии: число л с четырьмя знаками после запятой скрыто
в крошечном фра/ менте изображения. Слева — казалось бы, нормальная фотография,
а справа — увеличенные пиксели одной маленькой части, содержащие в себе
число 3,1415.
111
ОБЩЕДОСТУПНАЯ ТАЙНА: КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ
Безопасно ли делать покупки через интернет?
Большинство интернет-шпионов и хакеров мало интересуются сообщениями, кото-
рыми обмениваются обычные люди, за одним исключением: если сообщения содер-
жат номера кредитных карт. Но существует криптографическая система, которая
защищает передачу такой важной информации, известная как TLS (Transport Layer
Security — безопасность транспортного уровня). Она была разработана в 1994 г.
корпорацией Netscape, занимающейся программным обеспечением для интернета,
и была принята в качестве глобального стандарта два года спустя.
Протокол TLS использует как открытые, так и симметричные ключи и представ-
ляет собой довольно сложный процесс, который в кратком изложении выглядит так.
Во-первых, веб-браузер интернет-покупателя проверяет, имеет ли интернет-прода-
вец действительный сертификат открытого ключа. Если это так, браузер использует
этот открытый ключ для шифрования второго ключа, на этот раз симметричного,
который он посылает продавцу. Продавец использует свой закрытый ключ для рас-
шифровки сообщения и получает симметричный ключ, которым будет шифроваться
вся обрабатываемая информация. Таким образом, чтобы получить номер кредит-
ной карты при любом интернет-платеже, злоумышленник должен будет взломать
не одну, а две системы шифрования.
112
Глава 6
Квантовое будущее
По словам Филиппа Циммермана (см. «Безопасность для всех» на стр. 108),
в «Книге кодов» Саймона Сингха говорится: «Современная криптография дает воз-
можность создать такой шифр, который неуязвим ни для каких существующих форм
криптоанализа». Как мы уже отмечали, даже самым быстрым компьютерам не под
силу взломать методом перебора всех возможных вариантов такие алгоритмы шиф-
рования, как RSA или DES, и даже такие системы, как, например, PGP. Может,
какие-то математические лазейки позволят злоумышленникам упростить криптоана-
лиз? Хотя исключить это предположение нельзя, считается, что такое маловероятно.
Прав ли Циммерман? Разрешился ли длившийся тысячелетиями конфликт меж-
ду криптографами и криптоаналитиками?
Квантовые вычисления
Ответ на этот вопрос неясен. В последние десятилетия XX в. возникли кванто-
вые вычисления — новый и революционный способ проектирования и управления
компьютерами. Пока на теоретическом уровне квантовый компьютер может обла-
дать достаточной вычислительной мощностью для взлома сегодняшних алгоритмов
шифрования методом проб и ошибок. Так что криптоанализ еще может нанести от-
ветный удар.
Эта новая техническая революция основана на квантовой механике — теорети-
ческой науке, построенной в начале прошлого века такими учеными, как датчанин
Нильс Бор (1885-1962), англичанин Поль Дирак (1902—1984), немцы Макс
Планк (1858—1947), Вернер Гейзенберг (1901—1976), Эрвин Шрёдингер (1887—
1961), и многими другими. Устройство Вселенной, постулируемое квантовой меха-
никой, настолько парадоксально, что Альберт Эйнштейн, критикуя эту теорию, как-
то воскликнул: «Бог не играет в кости». Несмотря на сомнения Эйнштейна, теория
квантовой механики была много раз успешно протестирована, и ее правильность в на-
стоящее время не вызывает сомнений. Большинство ученых считает, что на макро-
скопическом уровне — то есть на уровне звезд, домов и молекул — Вселенная
подчиняется законам классической физики. Однако в квантовом мире — на уровне
113
КВАНТОВОЕ БУДУЩЕЕ
элементарных частиц, таких как кварки, фотоны, электроны и т. д. — действуют
совсем другие законы, приводящие к поразительным парадоксам. Без этой теории
не существовало бы ни ядерных реакторов, ни лазерных считывающих устройств.
Не было бы никакого способа объяснить свечение солнца или работу ДНК.
Нильс Бор (слева) и Макс Планк, основатели квантовой физики, на фотографии, сделанной в 1930 г.
Кот, ни живой ни мертвый
На семинаре по квантовой физике, состоявшемся в 1958 г., Бор так ответил одному
из выступающих: «Мы все согласны с тем, что эта теория является бредовой. Во-
прос, который нас разделяет, состоит в том, является ли она бредовой настолько,
чтобы иметь шанс оказаться правильной». Насколько, на самом деле, бредова кван-
товая механика? Возьмем, например, принцип суперпозиции состояний. Частица
находится в суперпозиции состояний, если в один и тот же момент она находится
в двух различных положениях или когда она одновременно имеет различное коли-
чество энергии. Однако когда наблюдатель производит измерения, частица всегда
114
КВАНТОВОЕ БУДУЩЕЕ
выбирает одно состояние или обладает определенным количеством энергии. Шрё-
дингер предложил мысленный эксперимент, известный как «кот Шрёдингера», что-
бы проиллюстрировать этот очевидно парадоксальный принцип. Пусть в закрытом
непроницаемом ящике находится кот. Внутри ящика имеется колба с ядовитым га-
зом, связанная специальным устройством с радиоактивной частицей, так что если
частица распадается, газ выходит из колбы и кот умирает. Вероятность того, что
эта частица распадется в течение определенного периода времени, составляет 50%.
Эксперимент с такими параметрами зависит от поведения частицы и подчиняется
законам квантовой физики.
«Кот Шрёдингера» — мысленный эксперимент, иллюстрирующий один из принципов квантовой
теории, а именно принцип суперпозиции состояний.
Допустим, что определенный период времени прошел. Вопрос: жив кот или
мертв? Или, на языке квантовой механики, в каком состоянии находится система
«ящик-кот»? Ответ на этот вопрос состоит в том, что пока наблюдатель не откроет
ящик и не «измерит» состояние системы, частица может находиться в суперпозиции
состояний: быть распавшейся и нераспавшейся. Значит, и система находится в су-
перпозиции состояний: кот, строго говоря, может быть и жив, и мертв одновременно.
Для тех, кто считает суперпозицию состояний надуманной гипотезой, важно
отметить, что многими уважаемыми физиками были предложены альтернативные
теории. Например, теория, известная как гипотеза возможных миров, утвержда-
ет, что понятие суперпозиции состояний — неприемлемый тезис, а на самом деле
115
КВАНТОВОЕ БУДУЩЕЕ
происходит вот что: для каждого из возможных состояний частицы — будь то по-
ложение, количество энергии и т. д. — существует альтернативная вселенная, где
частица находится в одном конкретном состоянии. Другими словами, в одной все-
ленной кот в ящике жив, а в другой — мертв. Когда наблюдатель открывает ящик
и убеждается, что его маленький дружок на самом деле жив, он делает это, находясь
в одной из возможных вселенных. В другой параллельной вселенной — вместе с ее
звездами, планетами, вокзалами и муравьями — этот же наблюдатель заглядывает
в ящик и обнаруживает, к своему горю, что кот отравился смертельным ядом. Одна-
ко сторонники гипотезы возможных миров до сих пор не объяснили, как эти миры
взаимодействуют друг с другом. Несмотря на это, теория показывает, что вопрос
заключается лишь в интерпретации того, почему квантовая реальность ведет себя
подобным образом, а не в самом поведении, которое подтверждено многочисленны-
ми убедительными экспериментами.
От бита к кубиту
Какая, однако, связь между суперпозицией состояний частиц и вычислениями,
не говоря уже о криптографии? До 1984 г. никто даже не думал о связи между
этими двумя областями. Примерно в то же время британский физик Дэвид Дойч
выступил с революционной идеей: а что было бы, если бы компьютеры подчинялись
законам квантовой механики, а не классической физики? Как повлиял бы принцип
суперпозиции состояний частиц на вычисления?
Напомним, что обычные компьютеры обрабатывают минимальные единицы ин-
формации, называемые битами, допускающими два взаимоисключающих значения:
О и 1. Квантовый компьютер, с другой стороны, в качестве минимальной единицы
информации мог бы работать с частицей, находящейся в двух возможных состоя-
ниях. Например, спин электрона может быть направлен либо вверх, либо вниз. Та-
кая частица будет иметь фантастическое свойство: представлять значение 0 (спин
вниз) или значение 1 (спин вверх). По принципу суперпозиции состояний она может
представлять оба значения одновременно. Эта новая единица информации получила
название кубит (сокращение от «квантовый бит»), и работа с такими единицами
открывает двери в мир супермощных компьютеров.
Обычный компьютер выполняет вычисления последовательно. Возьмем в каче-
стве примера цифровую информацию, содержащуюся в 32 битах. С таким количест-
вом битов мы можем закодировать числа от 0 до 4 292967 295. Обычный компью-
тер, чтобы найти определенное число из этой группы, должен будет перебирать бит
116
КВАНТОВОЕ БУДУЩЕЕ
за битом. Однако квантовый компьютер может выполнить задачу гораздо быстрее.
Чтобы проиллюстрировать это, представим, что в специальном контейнере нахо-
дятся 32 электрона в суперпозиции состояний. Применяя достаточно сильные элек-
трические импульсы, мы можем изменить спин электрона сверху вниз. Тогда эти
32 электрона — кубиты нашего квантового компьютера — будут представлять все
возможные комбинации спина вверх (1) и спина вниз (0) одновременно. В резуль-
тате поиск нужного числа выполняется за один раз, так как находит все возможные
варианты. Если мы увеличим количество кубитов до, например, 250, количество од-
новременных операций, которые могут быть выполнены, составит примерно 1075 —
чуть больше, чем предполагаемое число атомов в нашей Вселенной.
Работы Дойча доказали, что квантовые компьютеры теоретически возможны.
Над тем, чтобы они в один прекрасный день стали реальностью, работают десятки
институтов и исследовательских групп по всему миру. До сих пор, однако, не удалось
преодолеть технические трудности и построить устойчивый квантовый компьютер.
Некоторые эксперты полагают, что потребуется еще 15 или 25 лет, чтобы достичь
этой цели, другие сомневаются, что это вообще возможно.
«БОЛЬШОЙ БРАТ» XXI ВЕКА
Результатом создания жизнеспособного квантового компьк)1ера станет не просто крах современ-
ной криптографии. Такая вычислительная мощность на службе государственных или частных ин-
тересов может сместить баланс сил в мире. Битва за то, чтобы стать первой страной, развившей
такие технологии, может легко превратиться в еще i дну технологическую гонку, похожую на гонки
второй половины XX в.: за выход в космос и гонку вооружений. Логично предположить, что любой
прогресс в этой области будет держаться в тайне из соображений национальной безопасности.
Может, в каком-то уголке мира, в холодных подземных туннелях, уже готов к запуску квантовый
компьютер, который навсегда изменит нашу жизнь?
117
КВАНТОВОЕ БУДУЩЕЕ
ПРОЩАЙ, DES, ПРОЩАЙ
Через два года после того, как Шор продемонстрировал, что квантовый компьютер может взло-
мать шифр RSA, другой американец, Лов Гровер, сделал то же самое с еще одним столпом со
временной криптографии, алгоритмом DES. Гровер разработал программу, которая позволила
квантовому компьютеру найти правильное числовое значение из списка возможных значений
за время, равное квадратному корню из времени, которое нужно для этого обычному компьюте-
ру. Другой широко используемый алгоритм, который станет жертвой квантового компьютера,-
это RC5, стандарт, используемый в браузерах компании Microsoft.
Конец криптографии?
Квантовые вычисления приведут к смерти современной криптографии. Возьмем
в качестве примера звезду современных алгоритмов шифрования — RSA. Напом-
ним, чтобы взломать шифр RSA методом перебора всех возможных вариантов,
нужно разложить на множители произведение двух очень больших простых чисел.
Эта операция чрезвычайно трудоемкая, и пока не существует математической лазей-
ки для ее решения. Может ли квантовой компьютер взять на себя задачу разложе-
ния числа на простые числа, которые использует шифр RSA? Американский ученый
Питер Шор в 1994 г. дал на этот вопрос утвердительный ответ. Шор разработал
алгоритм для квантового компьютера, способный разложить большие числа на мно-
жители за намного меньшее время, чем самый мощный обычный компьютер.
Если это поразительное устройство когда-либо будет построено, алгоритм Шора
кирпичик за кирпичиком разрушит мощное криптографическое здание, построенное
на RSA, и наступит день, когда вся самая тайная информация на планете станет
явной. Все современные системы шифрования постигнет та же участь. Но, перефра-
зируя Марка Твена, мы можем сказать, что слухи о смерти криптоанализа «сильно
преувеличены».
Квантовая механика взяла, квантовая механика дала
Одной из основ квантовой механики является принцип неопределенности, откры-
тый Вернером Гейзенбергом в 1927 г. Хотя его точная формулировка очень сложна,
сам Гейзенберг обобщил его следующим образом: «Мы в принципе не можем знать
настоящее во всех подробностях». Более точно: невозможно определить с любой
118
КВАНТОВОЕ БУДУЩЕЕ
степенью точности те или иные свойства частицы в любой момент времени. Возь-
мем, например, частицы света (фотоны). Одной из их основных характеристик яв-
ляется поляризация — технический термин, связанный с колебаниями электромаг-
нитных волн. [Хотя фотоны поляризованы во всех направлениях, в нашем примере
мы будем считать, что они имеют поляризацию четырех типов: вертикальную (t),
горизонтальную (**), по диагонали слева направо вниз (\), по диагонали слева
направо вверх (к”).] Принцип Гейзенберга утверждает, что для определения поля-
ризации фотона нужно пропустить его через фильтр, или «щель», которая, в свою
очередь, может быть горизонтальной, вертикальной и диагональной: слева направо
вниз или слева направо вверх. Фотоны, поляризованные горизонтально, пройдут
горизонтальный фильтр без изменений, а поляризованные вертикально этот фильтр
не пройдут. Что касается фотонов, которые поляризованы по диагонали, то полови-
на из них пройдет через этот фильтр, поменяв поляризацию с диагональной на го-
ризонтальную, а другая половина этот фильтр не пройдет. Это будет происходить
случайным образом. Более того, после того как фотон пройдет фильтр, невозможно
будет с уверенностью сказать, какова была его первоначальная поляризация.
Если мы пропустим ряд фотонов с различной поляризацией через горизонтальный фильтр,
то увидим, что половина фотонов, поляризованных по диагонали, пройдет через фильтр, поменяв
поляризацию на горизонтальную.
Какова связь между поляризацией фотонов и криптографией? Очень сущест-
венная, как мы увидим ниже. Для начала представим себе исследователя, который
хочет определить поляризацию ряда фотонов. Для этого он выбирает фильтр с фик-
сированной ориентацией, например, горизонтальный. Предположим, что фотон
прошел через фильтр. Какой вывод может сделать наш исследователь? Конечно, он
может сказать, что исходная поляризация фотона не была вертикальной. А может
он сделать другие предположения? Нет. Казалось бы, можно подумать, что более
вероятно, что этот фотон был поляризован по горизонтали, а не по диагонали, пото-
му что половина фотонов, поляризованных по диагонали, не проходит через фильтр.
119
КВАНТОВОЕ БУДУЩЕЕ
Но зато число фотонов, поляризованных по диагонали, в два раза больше, чем с го-
ризонтальной поляризацией. Важно подчеркнуть, что трудность определения поля-
ризации фотона заключается не в каких-то технологических или теоретических про-
блемах, которые могут быть устранены в будущем; трудность является следствием
самой природы мира частиц. Если использовать этот эффект надлежащим образом,
то можно создать совершенно неуязвимый шифр, «святой грааль» криптографии.
Неуязвимый шифр
В 1984 г. американец Чарльз Беннет и канадец Жиль Брассар выдвинули идею
системы шифрования на основе передачи поляризованных фотонов. Сначала отпра-
витель и получатель договариваются, как разным поляризациям поставить в соот-
ветствие 0 или 1. В нашем примере это будет функцией двух видов поляризации:
первый вид, называемый прямолинейной поляризацией и обозначаемый символом
+, где 1 соответствует вертикальной поляризации (|), а 0 — горизонтальной (<“*•);
второй вид, называемый диагональной поляризацией и обозначаемый символом
х, ставит в соответствие 1 диагональную поляризацию слева направо вверх ( Z ),
а 0 — диагональную поляризацию слева направо вниз (\ ). Например, сообщение
0100101011 будет передано следующим образом:
Сообщение 0 1 0 0 1 0 1 0 1 1
Вид X + + X + X X + X +
Передача t i <-> i
Если шпион перехватит передачу, ему придется использовать фильтр с фиксиро-
ванной ориентацией X;
Передача i < -> i % < ► 1
Фильтр X
Определенная поляризация ИЛИ S ИЛИ или г Гх или Fx или *
Возможное сообщение или п ИЛИ или t или * * < •> или I * К к» или , :: или * 1
120
КВАНТОВОЕ БУДУЩЕЕ
Как мы видим, не зная изначального вида поляризации, шпион не может извлечь
полезную информацию из поляризации, определенной фильтром. Даже зная правило
соответствия 0и1, используемое отправителем и получателем, шпион будет ошибаться
в трети из случаев, в которых вид поляризации выбирается случайным образом (в та-
блице показаны все возможные комбинации при описанных условиях). Однако пробле-
ма заключается в том, что получатель находится не в лучшем положении, чем шпион.
Хотя отправитель и получатель могут обойти эту проблему, послав друг другу
последовательность видов поляризаций с помощью какого-то защищенного метода,
например, RSA шифрования, но тогда шифр будет уязвим для гипотетических кван-
товых компьютеров.
Чтобы преодолеть это последнее препятствие, Брассару и Беннету пришлось
усовершенствовать свой метод. Если читатель помнит, ахиллесовой пятой полиал-
фавитных шифров, таких как квадрат Виженера, являлось использование коротких
повторяющихся ключей, из-за которых в шифре возникали закономерности, что со-
здавало небольшую, но достаточную возможность для криптоаналитика взломать
шифр. Но что было бы, если бы ключ представлял собой случайный набор символов
и был длиннее, чем само послание, а каждое сообщение, даже самое незначительное,
для большей безопасности было бы зашифровано другим ключом? Тогда бы у нас
получился неуязвимый шифр.
Первым человеком, предложившим использовать полиалфавитный шифр с уни-
кальным ключом, был Джозеф Моборн. Вскоре после Первой мировой войны, буду-
чи начальником службы связи американского криптографического отдела, Моборн
придумал блокнот с ключами, каждый из которых содержал более 100 случайных
символов. Такие блокноты выдавались отправителю и получателю с инструкцией
уничтожать использованный ключ и переходить к следующему. Эта система, из-
вестная как шифрблокнот одноразового назначения, является, как мы уже говорили,
неуязвимой, и это можно доказать математически. И действительно, самые секрет-
ные послания между главами государств шифруются с помощью этого метода.
Если одноразовые шифры блокнота так безопасны, почему же они не использу-
ются повсеместно? Почему же мы так беспокоимся из-за квантовых компьютеров
и даже занимаемся манипуляциями с фотонами?
Оставив в стороне технические трудности генерации тысяч случайных одно-
разовых ключей для шифрования такого же количества сообщений, шифрблокнот
одноразового назначения имеет такой же недостаток, как и другие классические ал-
горитмы шифрования: проблему распределения ключей, которую пытается решить
современная криптография.
121
КВАНТОВОЕ БУДУЩЕЕ
Вид У поляризации отправителя Бит отправителя Отправитель послал Поляризация, определенная получателем Поляризация определена верно? Получатель определил Бит получателя Бит получателя верен?
1 А Я 1 Нет 1 Да
< > 0 Нет
, Г 0 Н А Л Ь Да 1 Да
0 Нет t 1 Нет
< * 0 Да
s: =5 № Да 0 Да
Й Н А Я 1 * Да 1 1 Да
И Нет 0 Нет
ш
S' 1 Да
L _1 о 0 <-> Да < * 0 Да
Нет 1 Нет
Q- F^ 0 Да
Однако передача информации с помощью поляризованных фотонов является
идеальным способом безопасного обмена уникальными ключами. Но прежде чем
передавать сообщение, необходимо сделать следующее.
1. Сначала получателю посылают случайную последовательность нулей и единиц
через различные, случайным образом выбранные фильтры: вертикальные (j),
горизонтальные (*“*) и диагональные ( \ , С )•
2. Затем получатель измеряет поляризацию полученных фотонов, случайным
образом чередуя прямолинейный (+) и диагональный (х) виды поляризации.
Так как он не знает последовательности фильтров, используемых отправителем,
большая часть нулей и единиц будет определена неправильно.
3. Наконец, отправитель и получатель связываются друг с другом в любой удоб-
ной им форме, не беспокоясь о безопасности канала, и обмениваются следующей
информацией: во-первых, отправитель объясняет, какой вид поляризации —
прямолинейный или диагональный — нужно использовать для каждого фотона,
не раскрывая самой поляризации фотона (то есть не говоря, какой именно ис-
пользовался фильтр). Со своей стороны получатель сообщает, в каких случаях
122
КВАНТОВОЕ БУДУЩЕЕ
ВАВИЛОНСКОЕ ПОСЛАНИЕ
Аргентинский писатель Хорхе Луис Борхес в коротком рассказе «Вавилонская библиотека» опи-
сал библиотеку, настолько большую, что на ее полках были все возможные книги: все романы,
стихотворения и диссертации, опровержения этих диссертаций, а также опровержения опро-
вержений, и так далее до бесконечности. Криптоаналитик, пытающийся расшифровать методом
проб и ошибок послание, зашифрованное с помощью шифрблокнота одноразового назначения,
окажется в подобном положении. 1ак как шифр выбран совершенно случайно, возможные рас-
шифровки будут представлять из себя всевозможные тексты одинаковой длины: реальное сооб-
щение, опровержение этого сообщения, то же сообщение со всеми существительными, заменен-
ными на другие той же длины, и так далее до бесконечности.
он правильно определил вид. Как видно из предыдущей таблицы, если у отпра-
вителя и получателя виды поляризации совпали, можно быть уверенным, что
нули и единицы переданы правильно. Наконец, уже в частном порядке каждый
из них отбрасывает биты, соответствующие фотонам, для которых получатель
неправильно определил вид поляризации.
В результате этого процесса и отправитель, и получатель будут иметь одну
и ту же совершенно случайно сгенерированную последовательность нулей и единиц,
так как отправитель случайным образом выбирал поляризационные фильтры, а по-
лучатель тоже случайным образом выбирал виды поляризации. На следующем ри-
сунке изображен простой 12-битовый пример описанного процесса.
Бит отправителя 0 1 1 0 1 1 1 0 0 0 0 1
Поляризация, определенная получателем + X X + X + X + + X + X
Получатель определил 1 1 1 0 1 0 1 0 0 0 0 1
Неотброшенные биты - 1 - 0 1 - - 0 0 0 0 1
123
КВАНТОВОЕ БУДУЩЕЕ
Обратите внимание, что некоторые окончательные биты отброшены, хотя они
были правильно определены. Это потому, что получатель не был твердо уверен в их
правильности, так как в тех случаях использовал неправильный вид поляризации.
Если передача содержит необходимое число фотонов, последовательность нулей
и единиц будет достаточно длинной, чтобы служить одноразовым ключом шифр-
блокнота для шифрования сообщений нормальной длины.
Теперь представим себе шпиона, который перехватил и отправленные фотоны,
и открытый разговор отправителя и получателя. Мы уже видели, что, не зная точно,
какой поляризационный фильтр был использован отправителем сообщения, невоз-
можно определить, когда поляризация была определена правильно. Открытый раз-
говор отправителя и получателя также бесполезен, потому что в нем никогда не го-
ворится о конкретных фильтрах.
Но самое главное, если шпион ошибется в выборе фильтра и тем самым изменит
поляризацию фотонов, его вмешательство сразу будет раскрыто, и он уже ничего
не сможет сделать, чтобы остаться незамеченным. Отправителю и получателю стоит
только проверить достаточно длинную часть ключа, чтобы обнаружить любые мани-
пуляции с поляризацией фотонов со стороны злоумышленников.
В конце процесса отправитель и получатель договариваются о простой проверке.
Выполнив три предварительных шага, описанных выше, и имея достаточное количе-
ство сохраненных битов, отправитель и получатель связываются друг с другом лю-
бым удобным способом и вместе проверяют группу битов (скажем, 100), выбран-
ных из общего числа случайным образом. Если все 100 битов совпали, отправитель
и получатель могут быть полностью уверены, что ни один шпион не перехватил их
передачу, и выбирают некоторую последовательность в качестве одноразового шиф-
ра. В противном случае им придется повторить процесс.
32 сантиметра абсолютной секретности
Метод Брассара и Беннета безупречен с точки зрения теории, но когда эту тео-
рию попытались применить на практике, она была встречена очень скептически.
В 1989 Г., после более чем года напряженной работы, Беннет построил систему,
состоящую из двух компьютеров, расположенных на расстоянии 32 сантиметра друг
от друга, один из которых выступал в роли отправителя, а другой — получателя.
После нескольких часов проб и поправок эксперимент был признан успешным. От-
правитель и получатель выполнили все этапы процесса, включая проверку шифра.
Возможность квантовой криптографии была доказана.
124
КВАНТОВОЕ БУДУЩЕЕ
Исторический эксперимент Беннета имел один очевидный недостаток: секрет по-
сылался на расстояние менее шага. Передача шепотом была бы, наверное, столь же
эффективна. Однако в последующие годы другие исследовательские группы уве-
личили это расстояние. В 1995 г. ученые из Университета Женевы использовали
оптоволокно для передачи сообщений на 23 километра. В 2006 г. команда из Лос-
Аламосской национальной лаборатории в США повторила этот процесс на рассто-
янии 107 километров. Хотя такие расстояния недостаточны для обычной связи, этот
метод уже может быть использован в местах, где строжайшая тайна имеет перво-
степенное значение, например, в правительственных зданиях и офисах компаний.
Если не брать во внимание соображения, связанные с техническими ограниче-
ниями для отправки сообщений, возможность того, что передача будет подслуша-
на, совершенно исключена даже на квантовом уровне. Этот квантовый шифр пред-
ставляет собой окончательную победу тайны над ее разглашением, криптографов
над криптоаналитиками. Все, о чем нам осталось теперь позаботиться — вопрос,
во всяком случае, немаловажный — как применять этот мощный инструмент и кто
в результате получит наибольшую выгоду.
125
Приложение
Различные классические шифры и спрятанные сокровища
В этом приложении мы расскажем о различных классических криптографических
шифрах, упоминаемых в предыдущих главах, но не описанных там достаточно под-
робно. Все они представляют различные криптографические методы и интересны
даже в качестве развлечения. В завершении мы приведем процесс расшифровки
из рассказа американского писателя Эдгара Аллана По, в котором блестяще про-
иллюстрировано применение частотного криптоанализа.
Шифр Полибия
Этот шифр, один из древнейших, о котором у нас имеется подробная информация,
основан на выборе пяти букв алфавита, служащих заголовками строк и столбцов
таблицы размером 5*5, которая затем заполняется буквами алфавита. Шифр за-
меняет каждую букву алфавита парой букв, являющихся заголовками соответствую-
щих столбца и строки. Первоначально использовался греческий алфавит из 24 букв,
поэтому английские буквы I и J, как правило, комбинируются (см. таблицу, приве-
денную ниже, где для простоты в качестве заголовков используются буквы А—Е).
Таблица заполняется по правилу, о котором договорились отправитель и получатель.
Рассмотрим, например, следующую таблицу:
А в С D Е
А А в с D Е
В F G н I-J К
С L м N 0 Р
D Q R S т и
Е V W X У Z
Заметим, что шифроалфавит состоит из 25 букв (5 х 5). В качестве заголовков
можно использовать и цифры (например, 1, 2, 3, 4 и 5). В этом случае таблица
имеет вид:
127
ПРИЛОЖЕНИЕ
1 2 3 4 5
1 A В c D E
2 F G H l-J К
3 L M N 0 P
4 Q R S T u
5 V W X Y z
Рассмотрим шифр Полибия на примере этих двух таблиц. Мы будем шифровать
сообщение BLANKS («пробелы»). По первой таблице мы получим:
В заменяется парой АВ.
L заменяется парой СА.
А заменяется парой АА.
N заменяется парой СС.
К заменяется парой BE.
S заменяется парой DC.
Зашифрованное сообщение имеет вид ABCAAACCBEDC. Если мы использу-
ем таблицу с цифрами, то получим: «123111332543».
Шифр Гронсфельда
Этот шифр, изобретенный голландцем Постом Максимилианом Бронкхорстом,
графом Гронсфельд, использовался в Европе в XVII в. Это полиалфавитный шифр,
аналогичный квадрату Виженера, но менее сложный (и менее надежный). Чтобы
зашифровать сообщение, рассмотрим следующую таблицу.
ABCDEFGH I J KLMNOPQRSTUVWXYZ
О: С D Е F G Н I J KLMNOPQRSTUVWXYZAB
1: D Е F G Н I J KLMNOPQRSTUVWXYZABC
2: F G Н I J KLMNOPQRSTUVWXYZABCDE
3: Н I JKLMNOPQRSTUVWXYZABCDEFG
4:LMN0PQRSTUVWXYZABCDEFGH I J К
5:N0PQRSTUVWXYZABCDEFGH I JKLM
6:RSTUVWXYZABCDEFGHI JKLMNOPQ
7:TUVWXYZABCDEFGH I JKLMNOPQRS
8:XYZABCDEFGH I JKLMNOPQRSTUVW
9: C D E F G H I J KLMNOPQRSTUVWXYZAB
128
ПРИЛОЖЕНИЕ
Далее, для каждой буквы в нашем сообщении мы выбираем случайным образом
число от 0 до 9. Для сообщения MATHEMATICAL («математический») мы вы-
бираем случайным образом 12 чисел, например: 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2. Этот
набор чисел и будет ключом шифра. Теперь вместо каждой буквы сообщения мы
поставим букву из строки с соответствующим номером (см. таблицу на предыдущей
странице).
Сообщение М А Т Н Е М А Т 1 С А L
Ключ 1 2 3 4 5 6 7 8 9 0 1 2
Зашифрованное сообщение Р F А S R D Т Q К Е D Q
Буква М будет заменена буквой Р (взятой из строки номер 1 в столбце М), и так
далее. Мы получим сообщение PFASRDTQKEDQ. Буква А исходного сообще-
ния будет зашифрована как F, Т, и D. Как и для всех полиалфавитных шифров, эта
система шифрования устойчива к методу перебора всех возможных вариантов и к ча-
стотному анализу. Количество ключей в шифре Гронсфельда для алфавита из 26 букв
составляет 26! X 10 = 4,03 X ю26.
Шифр Плейфера
Создатели этого шифра лорд Лайон Плейфер и сэр Чарльз Уитстон (также изо-
бретатель электромагнитного телеграфа) были друзьями и соседями и разделяли
любовь к криптографии. Их метод напоминает знаменитый шифр Полибия и тоже
использует таблицу из пяти строк и пяти столбцов. В качестве первого шага каж-
дая буква сообщения заменяется на пару букв в соответствии с ключом из пяти раз-
личных букв. В нашем примере эти пять букв будут JAMES. В случае алфавита
с 26 символами мы получаем следующую таблицу:
J А М Е S
В С D F G
н 1-К L N 0
р Q R Т и
V W X Y Z
Далее текст сообщения разбивается на пары букв или биграммы. Две буквы каж-
дой биграммы должны быть разными. Чтобы избежать возможных совпадений, мы
используем букву X. Мы также используем эту букву, чтобы завершить биграмму
в случае, если последняя буква не имеет пары.
129
ПРИЛОЖЕНИЕ
Например, сообщение TRILL будет разбито на биграммы следующим обра-
зом:
TR IL LX.
А слово TOY — так:
ТО YX.
Разбив текст на биграммы, мы можем начать шифрование, обращая внимание
на следующие условия:
а) две буквы биграммы расположены в одной и той же строке;
б) две буквы биграммы расположены в одном и том же столбце;
в) ни одно из вышеперечисленных.
В случае (а) буквы биграммы заменяются буквами, расположенными справа
от каждой из них («следующими» в таблице в естественном порядке). Таким об-
разом, пара JE будет зашифрована как AS:
J А М Е S
В случае (б) буквы биграммы заменяются буквами, которые находятся следом ниже
по таблице. Например, биграмма ЕТ будет зашифрована, как FY, a TY — как YE:
Е
F
N
Т
У
В случае (с), чтобы зашифровать первую букву биграммы, мы смотрим на ее
строку, пока не дойдем до столбца, содержащего вторую букву. Результат располо-
жен на пересечении этой строки и этого столбца. Чтобы зашифровать вторую букву,
мы смотрим на ее строку, пока не дойдем до столбца, содержащего первую букву.
Результат опять расположен на пересечении этой строки и этого столбца.
130
ПРИЛОЖЕНИЕ
Например, в биграмме СО буква С будет заменена буквой G, а буква О — бук-
вой I или К.
J А м Е S
в С D F G
н 1-К L N 0
р Q R Т и
V W X Y Z
Чтобы зашифровать сообщение TEA («чай») с помощью ключевого слова
JAMES, мы сделаем следующее.
• Разобьем слово на биграммы: ТЕ АХ.
• Букву Т заменим буквой Y.
• Букву Е — F.
• Букву А — М.
• Букву X — W.
Мы получим зашифрованное сообщение YFMW.
Криптограмма «Золотого жука»
Уильям Легран, главный герой рассказа Эдгара Аллана По «Золотой жук» (1843),
определяет, где зарыт клад с сокровищами, расшифровав криптограмму, написан-
ную на куске пергамента. Легран использовал статистический метод, основанный
на частоте, с которой буквы алфавита встречаются в английских текстах. Зашифро-
ванное послание выглядело следующим образом:
53iJt305))6*;4826)4J.)4J);806*;48t8^60))85
;li(;:i*8t83(88)5*f;46(;88*96*?;8)*i(;485);
5*|2:*П;4956*2(5*4)8^8*;4069285);)6|8)4+
t; 1($9;48081 ;8:8J 1 ;48f85; 4)4851528806*81 (
J9;48;(88;4(X?34;48)4t;l 61 ;:188;$?;
Легран начал с предположения, что оригинальный текст был написан на англий-
ском языке. В английских текстах наиболее часто встречается буква «е». Далее,
131
ПРИЛОЖЕНИЕ
в порядке уменьшения частоты, идут остальные буквы: а, о, i, d, h, n, r, s, t, u, y, c,
f, g, 1, m, w, b, k, p, q, x, z.
Герой рассказа строит по криптограмме таблицу, в первой строке которой распо-
ложены символы зашифрованного сообщения, а во второй — частота их появления.
8 4 f ) * 5 6 ( + 1 0 9 2 3 ? 11 —
33 26 19 16 16 13 12 11 10 8 8 6 5 5 4 4 3 2 1
Таким образом, символ «8» скорее всего соответствует букве «е». Затем он ищет
повторяющиеся тройки символов, заменившие также довольно распространенное
слово «the», что позволяет ему расшифровать символы «;», «,», «4» и «8».
Группа символов «; (88», теперь, когда он знает, что она соответствует «t (ее»,
позволяет ему определить отсутствующую букву. Это может быть только «г», учи-
тывая, что tree — «дерево» — наиболее вероятное слово в словаре. Наконец, бла-
годаря подобным хитроумным криптографическим допущениям и большому терпе-
нию, он получает следующую таблицу с частично расшифрованным алфавитом:
5 + 8 3 4 6 * f ( z ?
А d е g h i n 0 r t u
Этого достаточно, чтобы расшифровать сообщение:
«Хорошее стекло в трактире епископа на чёртовом стуле двадцать один
градус и тринадцать минут север-северо-восток главный сук седьмая ветвь
восточная сторона стреляй из левого глаза мертвой головы прямая от дере-
ва через выстрел на пятнадцать футов».
132
ПРИЛОЖЕНИЕ
Простые числа и их значение в криптографии
Настоящая математика не оказывает влияния на войну.
Никому еще не удалось обнаружить ни одну военную задачу,
которой бы служила теория чисел.
Годфри Харолд Харди, «Апология математика» (1940)
Для расшифровки сообщения важно, чтобы шифр был обратим. Как мы уже ви-
дели в случае аффинного шифра, это можно гарантировать, лишь используя простое
число в качестве модуля. Более того, произведение простых чисел является практиче-
ски необратимой функцией, то есть после выполнения умножения разложить произ-
ведение на исходные множители является очень трудоемкой задачей.
Такое свойство превращает эту операцию в очень полезный инструмент для си-
стем шифрования, основанных на асимметричных ключах, как, например, RSA-
алгоритм, который, в свою очередь, является основой криптографии с открытым
ключом. Далее мы более подробно расскажем о связи простых чисел с криптогра-
фией и о формальной математической основе алгоритма RSA.
Простые числа и «другая» теорема Ферма
Простые числа — это подмножество натуральных чисел, больших единицы, ко-
торые делятся только на единицу и на само себя. Основная теорема арифметики
утверждает, что любое натуральное число, большее единицы, всегда можно пред-
ставить в виде произведения степеней простых чисел, и это представление (факто-
ризация) является единственным. Например:
20 = 22-5
63 = 32-7
1 050 = 2-3-52-7.
Все простые числа, кроме числа 2, нечетные. Единственные два последователь-
ных простых числа — это 2 и 3. Нечетные последовательные простые числа — т. е.
пары простых чисел, отличающихся на 2 (например, 17 и 19), — называются про-
стыми числами-близнецами. Простые числа Мерсенна и числа Ферма также пред-
ставляют особый интерес.
Простое число называется числом Мерсенна, если при добавлении единицы по-
лучается степень двойки. Например, 7 — число Мерсенна, так как 7 + 1 = 8 = 23.
133
ПРИЛОЖЕНИЕ
Первые восемь простых чисел Мерсенна выглядят так:
3, 7, 31,127, 8191,131071, 524287, 2147483647.
В настоящее время известно чуть более 40 простых чисел Мерсенна. Самым
большим из них является гигантское число: 243112609—1, найденное в 2008 г. Для
сравнения, примерное число элементарных частиц во Вселенной меньше, чем 2300.
Простые числа Ферма — это простые числа вида F = 2-" +1, где п — нату-
ральное число.
В настоящее время известно пять простых чисел Ферма: 3 (п = 0), 5 (n = 1),
17 (п = 2), 257 (п = 3) и 65 537 (п = 4).
Простые числа Ферма носят имя прославленного французского юриста и мате-
матика Пьера де Ферма (1601—1665), который их открыл. Он сделал также другие
важные открытия в теории простых чисел. Классической является малая теорема
Ферма, которая утверждает: «Если р — простое число, и целое а не делится на р,
то ар = a (mod р).»
Этот результат имеет большое значение для современной криптографии, как мы
сейчас увидим.
От Эйлера к RSA
Еще один важный результат в модульной арифметике известен как соотношение
Безу. Это утверждение гласит, что если а и b — целые положительные числа, тогда
уравнение НОД (a, b) = k эквивалентно существованию двух целых чисел р, q,
таких что:
pa + qb = k.
В частности, если НОД (о, Ь) — 1, это соотношение гарантирует существование
целых чисел р и q, таких что
pa + qb = 1.
134
ПРИЛОЖЕНИЕ
Работая по модулю п, возьмем НОД (а, п) — 1, тогда обязательно существуют
целые числа р и q, такие что pa + qn = 1. Так как п — модуль, то qn = 0, следова-
тельно, существует такое р, что pa = 1, то есть существует число, обратное числу а
по модулю п, а именно р.
Элементы, имеющие обратный элемент по модулю п, являются натуральными
числами, которые меньше, чем п, и удовлетворяют условию НОД (а. n) = 1. Коли-
чество таких чисел называется функцией Эйлера и обозначается как ф(п).
Если число п представлено в виде произведения степеней простых чисел следую-
щим образом и = р1*' р“2 ...р^, то
9?(н) = п
Например, если п = 1600 = 26 52, то
/ 1 \
<р(1 6W) = 1 600 I 1 — —
1 \
1 - - = 640.
Более того, в случае, если п — простое число, то для любого значения а вы-
полняется НОД (а, п) = 1, и, следовательно, любое число а будет иметь обратное
по модулю п, значит ф(п) = п — 1.
Итак, подведем итог самым важным фактам.
1. ф(п) называется функцией Эйлера и обозначает количество натуральных чи-
сел, меньших п и взаимно простых с ним.
2. Если п = pq, где р и q простые числа, то
0(n) = (p-l)U-l).
3. Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля,
и р — простое число, то а р = a (mod р), что эквивалентно а р = 1 (mod р).
В заключении мы используем функцию Эйлера, подставив ее в предыдущее со-
отношение.
4. Если НОД (g, n) = 1, тогда имеем а = 1 (mod п).
135
ПРИЛОЖЕНИЕ
Почему работает RSA-алгоритм?
Математические факты, изложенные выше, лежат в основе алгоритма шифрования
RSA.
RSA -алгоритм зашифровывает численное представление т некоторого сообще-
ния с помощью двух простых чисел р и q. Возьмем п = pq. Обозначим за е любое
значение, такое что НОД (е, 0(n)) = 1, и пусть d будет обратный элемент числа е
по модулю ф(п). [Мы знаем, что он существует, так как НОД (е,0(п)) = 1]. Тогда:
d • е = 1 по модулю 0(п).
Зашифрованное послание М шифруется следующим образом: М = те (mod п).
Алгоритм подразумевает, что исходное сообщение т может быть получено как
т = Md = (mc)d (mod п). Проверка этого уравнения как раз и демонстрирует рабо-
ту алгоритма RSA. Мы воспользуемся теоремой Ферма и функцией Эйлера.
Рассмотрим два случая.
1. Если (т, n) = 1, то с функцией Эйлера имеем: m^(n) = 1 (mod п).
Начнем с того, что d • е — 1 по модулю ф(п) эквивалентно соотношению е • d —1 =
= 0 (mod 0(п)), то есть существует целое значение k, такое, что е • d — 1 = k • ф(п)
или е • d — k ф(п) + А. Используя это и формулу Эйлера, получим:
(mc)d = med = mk +1= mk • т = • т = lfe т (mod n) = т (mod п).
Это и есть нужный нам результат.
2. Если НОД (т,п) * 1 и п = р ' q, тот содержит или только множитель р, или
только q, или оба одновременно.
136
ПРИЛОЖЕНИЕ
Пусть т содержит только множитель р. Тогда, во-первых, т кратно р, то есть суще-
ствует целое число г, такое, что т = гр. Поэтому mde = 0 (mod р) или mdc = т (mod р),
другими словами, существует значение А, такое, что:
mdc — т = Ар. (1)
Во-вторых, мы имеем:
(mc)d = mcd = mk + 1= mk • т = (m^(n))fe • т = (п? • т.
Так как НОД (т, п) = р, НОД (т, q) = 1, то по теореме Ферма т =
= 1 (mod q).
Подставим это в предыдущее выражение.
(me)d = mcd = mk ^(п) + 1 = mk • m = (m^(n))fe • m = (n? (p-1) • m - lfe • m =
= m (mod q).
Откуда мы заключаем, что существует значение В, такое что:
mdc — т = Bq. (2)
Из (1) и (2) следует, что разность (mde — т) делится на п = pq, поэтому
mde — т = 0 (mod п).
Аналогично это доказывается для случая, когда т содержит только множитель q.
В случае, когда т кратно и р, и q одновременно, результат тривиален. Сле-
довательно,
(me)d = т (mod п).
Таким образом, мы продемонстрировали математическую основу алгоритма RSA.
137
Список литературы
Fernandez, S., Classical Cryptography. Sigma Review No. 24, April 2004.
Garfunkel, S., Mathematics in Daily Life, Madrid, COMAP, Addison-Wesley, UAM,
1998.
Gomez, J., From the leaching to the Practice of Mathematics Barcelona, Paidos, 2002.
Kahn, D., The Codebreakers: The Story of Secret Writing, New York, Scribner, 1996.
Издание на русском языке: Кан Д. Взломщики кодов. — М.: Центрполиграф,
2000.
Singh, S., The Secret Codes, Madrid, Editorial Debate, 2000.
Tocci, R., Digital Systems: Principles and Applications, Prentice Hall, 2003.
Издание на русском языке: Точчи Р. Цифровые системы. Теория и практика. —
М.: Вильямс, 2004.
139
Алфавитный указатель
Адлеман, Лен 104
Алгоритм
— Аль-Кинди 7, 38—39, 40
— Диффи — Хеллмана 100—103
— Луна 89—90
— перестановочного шифрования
22-25, 57-59
— подстановки 24—25, 48, 49, 57—
59, 62, 99
— шифрования 11—14,18,19, 22, 35,
43, 87, 99,107
— DES ( «стандарт шифрования дан-
ных») 99, ИЗ, 118
— RSA104-107,109, ИЗ, 118,121,
133,134,136,137
— TLS («безопасность транспортного
уровня») 112
Алфавит
— открытого сообщения 31, 36, 43,
44, 45
— шифроалфавит 26, 27, 36—37,
42-45,49-51,127
Альберти
— диск 45, 60
— Леон Баттиста Альберти 42—43
Байт 77-81
Безу, соотношение 134
Бит 77, 83,116,117,122
— квантовый 116—118
— контрольный (бит четности)
84-85
Блетчли-Парк 69—72
Бэббидж, Чарльз 46, 49—51
«Бэкдоры» («черные ходы») 103
Виженер
— Блез де Виженер 43
— квадрат Виженера 43—47, 49, 50,
128
Гейзенберг, Вернер ИЗ, 118—119
Двоичная система счисления 8, 9, 10,
77-79, 80, 81-83, 84, 88, 92, 95,
99
Десятичная система счисления 10, 79,
82-83
Диффи, Уитфилд 100—104,109
Евклид 27, 33
Избыточность информации 84
Касиски, Фридрих 51
Ключ 10—14
— асимметричный 102, 133
— закрытый 13—14, 103, 105—106,
109,110,112
— открытый 13—14,103,105—106,
108,109-112,133
— распределение 99, 121
— шифрблокнот одноразового назна-
чения 121—124
Ключевое слово 36—37, 46—47, 49—
51, 58-60,129
Коды
— Морзе 53—56, 60
— траншейные 62
— штрихкод 92—97
— ASCII 77-78, 81-83, 87,105
141
АЛФАВИТНЫЙ УКАЗАТЕЛЬ
— QR (Quick Response — «быстрый
отклик» ) 97
Кубит 116—117
Матрица 74—76
Модульная арифметика 7, 14, 25, 27,
30, 31, 74, 75, 88, 96,101,134
«Мэджик» 72
Панвэн, Жорж 57
По, Эдгар Аллан 40, 127, 131
Принцип
— Керкгоффса 12, 13
— неопределенности 118
Простые числа 8, 14, 33, 101, 104, 105,
106,107,118,133-136
— Мерсенна 134
— Ферма 134
Реевский, Мариан 68
Ривест, Рон 104
Система счисления 27, 79, 82—83
— основание системы счисления
82-83
Скитала 22—23
Стеганография 21—22, 111
Тьюринг, Алан 61, 69, 70, 72
Ферма
— малая теорема Ферма 105, 134—135
— Ферма, Пьер де 105, 133—137
Хеллман, Мартин 100—103, 109
Хеш-функция 109—110
Хилл, Лестер 74—76
Циммерман
— Артур 15,19
— Филипп 107, ИЗ, 125
— телеграмма 14—19, 56
Частотный криптоанализ 7, 37-41, 42,
43, 45, 47, 49, 58
Шамир, Ади 104
Шеннон, Клод 83—86
Шестнадцатеричная система счисления
79-82, 87
Шифровальщики навахо 73
Шифр
— атбаш 37
— аффинный 32—35
— Гронсфельда 47, 128—129
— одноалфавитный 43, 48, 50
— Плейфера 56, 129—131
— полиалфавитный 41, 43, 45, 48, 49,
51,121,128
— Полибия 25, 56,127—129
— Цезаря 25—27
— ADFGVX 18, 57-62
— JN-25 71-72
Шрёдингер, Эрвин ИЗ, 115
Шум 84
Эйлер
— теорема 105,136
— функция 105, 135
«Энигма» 7, 60—77
Biuro Szyfrow (шифровальное бюро)
67-68
142
АЛФАВИТНЫЙ УКАЗАТЕЛЬ
Colossus 7, 71, 77
EAN-13 94-95
PGP (Pretty Good Privacy — «доста-
точно хорошая степень конфиденци-
альности») 107—108, ИЗ
143
Научно-популярное издание
Выходит в свет отдельными томами с 2014 года
Мир математики
Том 2
Жуан Гомес
Математики, шпионы и хакеры.
Кодирование и криптография.
РОССИЯ
Издатель, учредитель, редакция:
ООО «Де Агостини», Россия
Юридический адрес: Россия, 105066,
г. Москва, ул. Александра Лукьянова, д. 3, стр. 1
Письма читателей по данному адресу не при-
нимаются.
Генеральный директор: Николаос Скилакис
Главный редактор: Анастасия Жаркова
Старший редактор: Дарья Клинг
Финансовый директор: Наталия Василенко
Коммерческий директор: Александр Якутов
Менеджер по маркетингу: Михаил Ткачук
Менеджер по продукту: Яна Чухиль
Для заказа пропущенных книг и по всем вопро-
сам, касающимся информации о коллекции, за-
ходите на сайт www.deagostini.ru, по остальным
вопросам обращайтесь по телефону бесплатной
горячей линии в России:
@ 8-800-200-02-01
Телефон горячей линии
для читателей Москвы:
@ 8-495-660-02-02
Адрес для писем читателей:
Россия, 170100, г. Тверь, Почтамт, а/я 245,
«Де Агостини», «Мир математики»
Пожалуйста, указывайте в письмах свои кон-
тактные данные для обратной связи (телефон
или e-mail).
Распространение:
ООО «Бурда Дистрибьюшен Сервисиз»
УКРАИНА
Издатель и учредитель:
ООО «Де Агостини Паблишинг» Украина
Юридический адрес: 01032, Украина,
г. Киев, ул. Саксаганского, 119
Генеральный директор: Екатерина Клименко
Для заказа пропущенных книг и по всем вопро-
сам, касающимся информации о коллекции, за-
ходите на сайт www.deagostini.ua, по остальным
вопросам обращайтесь по телефону бесплатной
горячей линии в Украине:
® 0-800-500-8-40
Адрес для писем читателей:
Украина, 01033, г. Киев, a/я «Де Агостини»,
«Мир математики»
УкраГна, 01033, м. Кшв, а/с «Де АгоспнЬ>
БЕЛАРУСЬ
Импортер и дистрибьютор в РБ:
ООО «Росчерк», 220037, г. Минск,
ул. Авангардная, 48а, литер 8/к,
тел./факс: +375 17 331 94 27
Телефон «горячей линии» в РБ:
& + 375 17 279-87-87 (пн-пт, 9.00-21.00)
Адрес для писем читателей:
Республика Беларусь, 220040, г. Минск,
а/я 224, ООО «Росчерк», «Де Агостини»,
«Мир математики»
КАЗАХСТАН
Распространение:
ТОО «КГП «Бурда-Алатау Пресс»
Издатель оставляет за собой право увеличить реко-
мендуемую розничную цену книг. Издатель остав-
ляет за собой право изменять последовательность
заявленных тем томов издания и их содержание.
Отпечатано в соответствии с предоставленными
материалами в типографии:
Grafica Veneta S.p.A Via Malcanton 2
35010 Trebaseleghe (PD) Italy
Подписано в печать: 31.07.2013
Дата поступления в продажу на территории
России: 28.01.2014
Формат 70 х 100 / 16. Гарнитура «Academy».
Печать офсетная. Бумага офсетная. Печ. л. 4,5.
Усл. печ. л. 5,832.
Тираж: 200 000 экз.
© Joan Gomez, 2010 (текст)
© RBA Collecionables S.A., 2010
© ООО «Де Агостини», 2014
ISBN 978-5-9774-0682-6
ISBN 978-5-9774-0639-0 (т. 2)
@
Данный знак информационной про-
дукции размещен в соответствии с требования-
ми Федерального закона от 29 декабря 2010 г.
№ 436-ФЗ «О защите детей от информации, при-
чиняющей вред их здоровью и развитию».
Издание для взрослых, не подлежит обязатель-
ному подтверждении! соответствия единым требо-
ваниям, установленным Техническим регламентом
Таможенного союза «О безопасности продукции,
предназначенной для детей и подростков» ТР ТС
007/2011 от 23 сентября 2011 г. № 797.
Математики,
шпионы и хакеры
Кодирование и криптография
Если бы историю человечества можно было представить в виде
шпионского романа, то главными героями этого произведения,
несомненно, стали бы криптографы и криптоаналитики.
Первые - специалисты, виртуозно владеющие искусством
кодирования сообщений. Вторые - гении взлома и дешифровки,
на компьютерном сленге именуемые хакерами. История сопер-
ничества криптографов и криптоаналитиков стара как мир.
Эволюционируя вместе с развитием высоких технологий,
ремесло шифрования достигло в XXI веке самой дальней границы
современной науки - квантовой механики. И хотя объектом
кодирования обычно является текст, инструментом работы
кодировщиков была и остается математика. Эта книга - попытка
рассказать читателю историю шифрования через призму
развития математической мысли.
ISBN 978-597740639-0
9 785977 406390