Глава 1. Введение

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

§ 1.1. Криптография

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

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

алфавиту, а букву Я буквой А. По сути этот шифр совпадает с тем, которым пользовался Цезарь, обмениваясь посланиями с римскими генералами по всей Европе.

У криптографии есть близнец — криптоанализ, искусство взламывания шифров. Разумеется, «взломать» шифр означает найти способ декодирования без знания ключа; этим и занимаются дешифровалыцики. Взломать шифр Цезаря очень легко. Той же слабостью страдают все процедуры кодирования, основанные на систематической замене одних букв другими, поскольку средняя частота, с которой встречаются буквы данного языка, более или менее постоянна. Например, в английском языке чаще всего используются буквы . Поэтому можно угадать буквы, соответствующие наиболее часто повторяющимся символам шифровки. Более того, в английском языке чаще всего встречаются слова «the» и «and». Поэтому возможно, что группы из трех символов, которых в шифровке больше всего, соответствуют одному из этих слов, и так далее. Подобная стратегия называется частотным анализом.

Заметим, что мы предполагаем сообщение достаточно длинным. Всегда можно составить короткое послание, в котором частоты букв и слов будут сколь угодно невероятны. Однако в длинных сообщениях такое почти невозможно, поскольку частотные характеристики присущи самому языку.

У криптоанализа много и других задач помимо взлома шифров, и при их решении частотный анализ играет чрезвычайно важную роль. Одним из вариантов применения является расшифровка древних надписей. Возможно, наиболее известным результатом в этой области служит расшифровка египетских иероглифов Дж.-Ф.Шампольоном (J.-F. Champollion) в 1822 году. Ключом к расшифровке послужил камень Розетты — массив черного базальта, найденный в 1799 году, который находится теперь в Британском музее в Лондоне. На камне один текст записан тремя способами: иероглифическим, демотическим и по-гречески.

Во времена Шампольона было широко распространено мнение, будто египетские иероглифы были логографической системой записи. В таких системах каждому иероглифу соответствует понятие. Среди используемых и по сю пору систем записи ближе всего к логографическим подходит китайская. У мудрых современников Шампольона было много оснований верить в логографическую теорию. Кроме всего прочего, к наиболее старым теориям иероглифов относится предположение о том, что они представляют собой вид иероглифического письма. Такие сведения были собраны неким Хораполлоном из Нилополиса (Horapollo of Nilopolis) в четвертом или пятом веке нашей эры, когда навыки записи и чтения древних надписей были уже практически утрачены.

Шампольон решил проверить предположение Хораполлона, подвергнув частотному анализу тексты на камне Розетты. Он начал с подсчета слов в греческом тексте и насчитал их 486. Если бы каждый иероглиф соответствовал одному понятию (или слову), то их число в иероглифическом тексте должно было быть приблизительно таким же. Однако Шампольон насчитал 1419 символов, что значительно превышало ожидаемую величину. Значит, иероглифы не образовывали логографическую систему.

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

Безусловно, при использовании компьютера частотный анализ значительно ускоряется. Поэтому большинство ранних

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

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

Многие из используемых в этих новых условиях шифров принадлежат к типу, известному под названием «система шифрования с открытым ключом». Такие системы были введены в 1976 году Диффи (Diffie) и Хеллманом (Hellman) из Стэн-форда и, независимо, Мерклем (Merkle) из Университета Калифорнии. В системе шифрования с открытым ключом умение шифровать сообщения не позволяет легко их расшифровать. Поэтому можно рассказывать всем и каждому, как зашифровать сообщения, отправляемые в банк, не подвергая систему опасности. Преимущества такого подхода при коммерческих операциях очевидны.

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

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