Криптография уже более 3000 лет играет заметную роль в истории человечества. Немало войн было выиграно или проиграно благодаря хитроумности или глупости криптосистем. Если вам кажется, что я преувеличиваю, почитайте «Взломщиков кодов» Дэвида Кана[41] — и не забывайте, что эта книга написана еще до того, как стала известна крупнейшая криптографическая история всех времен: взлом нацистского военно-морского шифра во Второй мировой войне командой с участием Алана Тьюринга.
И все же, хотя криптография тысячелетиями влияла на человеческие дела, события последних тридцати лет полностью — да, именно полностью! — изменили наши представления о ней. Если нанести на шкалу времени основные математические открытия в области криптографии, то вы увидите несколько отметок в античности, несколько, может быть, от Средневековья до XIX века, одно в 1920-е гг. (одноразовые ключи), еще несколько во время и около Второй мировой войны — а затем, после рождения теории вычислительной сложности в 1970-е гг., они пойдут сплошным потоком, одно за одним…
Наше путешествие по истории криптографии начнется со знаменитого и жалкого «шифра Цезаря», использовавшегося в Римской империи. В нем обычное послание превращается в шифрованный текст простым добавлением 3 к номеру каждой буквы (с замыканием алфавита в кольцо, так что после Z снова идет A). Таким образом, D превращается в G, Y становится B, а DEMOCRITUS выглядит как GHPRFULWXV. Были и более сложные варианты шифра Цезаря (он же шифр замены), но при наличии достаточного количества зашифрованного текста все их нетрудно взломать при помощи (например) частотного анализа присутствия букв в зашифрованном тексте. Правда, это не очень-то останавливает людей в использовании подобных вещей! Представьте себе, совсем недавно, в 2006 г., глава сицилийской мафии[42] был наконец-то пойман после 40 лет охоты потому, что использовал шифр Цезаря — его оригинальную версию — для отправки записок своим подчиненным!
Может ли существовать криптосистема, безопасная с точки зрения теории информации, то есть доказуемо надежная вне зависимости от того, сколько компьютерного времени есть у перехватившей сообщение стороны на его взлом? Поразительно (если вы никогда прежде об этом не слышали), но ответ на этот вопрос оказывается положительным, и еще более поразительно, что такая система была открыта только в 1920-е гг. По причинам, о которых мы поговорим чуть позже, прототип системы, безопасной согласно теории информации, называется одноразовым ключом. Идея проста: текстовое сообщение представляется в виде двоичной строки p, над которой производится операция исключающего «или» (xor) со случайной двоичной ключевой строкой k той же длины. То есть зашифрованный текст c равен p ⊕ k, где знаком ⊕ обозначается побитовое сложение по модулю 2.
Получатель (которому известна k) может расшифровать шифрованное послание при помощи еще одной операции исключающего «или»:
c⊕k=p⊕k⊕k=p.
Для стороны, перехватившей послание и не знающей k, зашифрованный текст — это просто строка случайных бит, поскольку результатом операции исключающего «или» между произвольной строкой (посланием) и случайной строкой является еще одна случайная строка. Проблема с одноразовыми ключами, конечно, в том, что и отправителю, и получателю должен быть известен ключ, не менее длинный, чем само послание. Более того, если один и тот же ключ будет использован для шифрования двух или более посланий, то криптосистема перестанет быть безопасной с точки зрения теории информации. (Отсюда и название — «одноразовый ключ».) Чтобы понять, почему, предположим, что два текста p1 и p2 шифруются при помощи одного и того же ключа k и дают в результате шифрованные тексты c1 и c2 соответственно. Тогда мы имеем
c 1 ⊕ c 2 = p 1 ⊕ k ⊕ p 2 ⊕ k = p 1 ⊕ p 2,
и, следовательно, перехвативший может получить строку p1 ⊕ p2. Само по себе это может оказаться, а может и не оказаться полезным, но это, по крайней мере, позволяет противнику получить какую-то информацию об исходном тексте. Но ведь это всего лишь математическая диковинка, не правда ли? Ну, в 1940-е годы Советы проявили небрежность и использовали повторно некоторые из своих одноразовых ключей. В результате Агентство национальной безопасности АНБ в рамках проекта VENONA сумело восстановить некоторые (хотя и не все) зашифрованные таким способом сообщения. Кажется, именно так были пойманы Юлиус и Этель Розенберги.
В 1940-е гг. Клод Шеннон доказал, что теоретически надежная криптография требует, чтобы у отправителя и получателя был общий ключ длиной не менее длины того сообщения, которое они хотят передать. Как почти все результаты Шеннона, задним числом этот вывод кажется тривиальным. (Хорошо начинать с самого начала!) Вот его доказательство: если имеются шифрованный текст и ключ, лучше, чтобы исходный текст восстанавливался по этим данным однозначно. Иными словами, при любом фиксированном ключе функции, преобразующей исходный текст в шифрованный, лучше быть инъективной. Но из этого сразу же следует, что для заданного шифрованного текста c число исходных текстов, из которых в принципе мог получиться c, не превышает числа ключей. Иными словами, если возможных ключей меньше, чем исходных текстов, то противник сможет исключить некоторые из исходных текстов — те, из которых c не получится ни при каком значении ключа. Поэтому наша криптосистема не будет совершенно надежной. Следовательно, если мы хотим совершенной надежности, нужно иметь по крайней мере столько же ключей, как и исходных текстов — или, что эквивалентно, ключ должен содержать по крайней мере столько же бит, сколько содержится в исходном тексте.
Я уже упоминал, что передавать друг другу и хранить ключи громадной длины, как правило, непрактично, — даже КГБ не удавалось проделывать это без сучка без задоринки! Потому нам нужна криптосистема, которая позволяет обходиться менее длинными ключами. Конечно, результат Шеннона подразумевает, что такая система не будет надежной с точки зрения теории информации. Но что, если мы немного снизим требования? В частности, что, если мы будем считать, что перехвативший ограничен полиномиальным временем? Этот вопрос естественным образом переводит нас к нашей следующей теме…