Затем нужно угадать число колонок. Во многих случаях по контексту сообщения можно угадать слово или фразу. Например, предположим, что криптоаналитик подозревает, что где-то в сообщении должно встретиться словосочетание milliondollars. Обратите внимание, что в результате того, что эти слова присутствуют в исходном тексте, в шифрованном тексте встречаются биграммы MO, IL, LL, LA, IR и OS. Символ O следует за символом M (то есть они стоят рядом по вертикали в колонке 4), так как они разделены в предполагаемой фразе дистанцией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вместо перечисленных выше биграмм встречались бы следующие: MD, IO, LL, LL, IA, OR и NS. Таким образом, для каждой длины ключа в шифрованном тексте образуется различный набор биграмм. Перебрав различные варианты, криптоаналитик часто довольно легко может определить длину ключа.
Остается узнать только порядок колонок. Если число колонок k невелико, можно перебрать все k(k - 1) возможных комбинаций пар соседних колонок, сравнивая частоты образующихся биграмм со статистическими характеристиками английского языка. Пара с лучшим соответствием считается правильно позиционированной. Затем все оставшиеся колонки по очереди проверяются в сочетании с уже найденной парой. Колонка, в которой биграммы и триграммы дают максимальное совпадение со статистикой, предполагается правильной. Весь процесс повторяется, пока не будет восстановлен порядок всех колонок. Есть шанс, что на данном этапе текст уже будет распознаваемым (например, если вместо слова million мы увидим milloin, то сразу станет ясно, где сделана ошибка).
Некоторые перестановочные шифры принимают блок фиксированной длины на входе и выдают блок фиксированной длины на выходе. Такие шифры полностью определяются списком, сообщающим порядок, в котором символы попадают в выходной блок. Например, шифр на рис. 8.2 можно рассматривать в виде шифра с 64-символьным блоком. Его выход описывается последовательностью чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13, ..., 62. Другими словами, четвертая входная буква, а, первой появится на выходе, за ней последует двенадцатая, f, и т. д.
8.1.4. Одноразовые блокноты
Разработать шифр, который невозможно взломать, на самом деле весьма просто. Методика для этого известна уже несколько десятилетий. В качестве ключа выбирается произвольная битовая строка, длина которой совпадает с длиной исходного текста. Открытый текст также преобразуется в последовательность двоичных разрядов, например, с помощью стандартной кодировки ASCII. Наконец, эти две строки поразрядно складываются по модулю 2 (операция «исключающее ИЛИ», XOR). Полученный в результате зашифрованный текст взломать невозможно, поскольку в достаточно большом отрывке любая буква, биграмма или триграмма будет равновероятной. Этот метод, известный как одноразовый блокнот (one-time pad), теоретически является панацеей от любых атак, независимо от вычислительных мощностей, которыми обладает или будет когда-либо в будущем обладать взломщик. Объясняется этот невероятный факт с помощью теории информации: дело в том, что в зашифрованном сообщении не содержится никакой информации для взломщика, поскольку любой открытый текст является равновероятным кандидатом.
Пример практического использования одноразового блокнота показан на рис. 8.3. Для начала фраза «I love you» («Я люблю тебя») преобразуется в 7-битный ASCII-код. Затем выбирается одноразовая последовательность, Последовательность 1, которая складывается по модулю 2 с сообщением. В результате получается некий шифр. Для того чтобы его разгадать, криптоаналитику придется перебрать все возможные одноразовые последовательности, всякий раз проверяя, каким получается открытый текст. Например, если попробовать расшифровать послание с помощью Последовательности 2 (см. рис. 8.3), получится текст «Elvis lives» («Элвис жив»). Обсуждение правдоподобности этого утверждения выходит за рамки данной книги, однако, как мы видим, исходное сообщение разгадать не удалось, но при этом получилась вполне нормальная с точки зрения английской грамматики фраза. На самом деле, для любой последовательности из 11 символов в кодировке ASCII найдется одноразовый блокнот для ее генерации. Именно это мы имеем в виду, говоря, что в зашифрованном тексте не содержится никакой информации: из него можно извлечь любое сообщение подходящей длины.
Одноразовые ключи теоретически являются очень мощным инструментом, однако у них есть ряд практических недостатков. Во-первых, такой длинный ключ невозможно запомнить, поэтому и отправитель, и получатель должны носить с собой письменную копию ключа. Если есть опасность того, что одна из этих копий может быть захвачена неприятелем, хранение письменных копий оказывается весьма нежелательным. Кроме того, полный объем данных, которые могут быть переданы, ограничен размером доступного ключа. Если шпиону повезет и он добудет большое количество информации, может выясниться, что он не сможет передать все эти сведения в центр, так как ему не хватит длины ключа. Еще одна проблема заключается в чувствитель
ности данного метода к потерянным или вставленным символам. Если отправитель или получатель потеряют синхронизацию, все данные, начиная с этого места, будут испорчены.
Рис. 8.3. Использование одноразового блокнота для шифрования сообщений и возможность получения произвольного открытого сообщения из зашифрованного путем подстановки другой ключевой последовательности
С появлением компьютеров метод одноразового блокнота может получить практическое применение. Ключ можно хранить на специальном диске DVD, содержащем несколько гигабит информации. Он даже не вызовет особых подозрений, если его перевозить в коробке от видеокомпакт-диска и в начале даже записать несколько минут фильма. Конечно, в сетях со скоростями передачи данных, исчисляющимися гигабитами, необходимость менять компакт-диск через каждые 30 секунд быстро утомит. Получается, что DVD с одноразовым ключом нужно вручить лично в руки будущему получателю секретного сообщения, а такой подход резко снижает вероятность практического использования метода одноразового блокнота.
Квантовая криптография
Интересно, что решение проблемы передачи по сети одноразовой последовательности пришло из довольно далекой науки — квантовой механики. Эта область остается экспериментальной, однако многообещающей. Если удастся усовершенствовать этот метод, все задачи криптографии можно будет решать с помощью одноразовых последовательностей, ведь это самый надежный способ защиты информации. Ниже мы вкратце опишем суть технологии, называемой квантовой криптографией. В частности, мы рассмотрим протокол BB84, названный так в честь его создателей и года, в котором его описание было впервые опубликовано (Bennet и Brassard, 1984).
Допустим, пользователь по имени Алиса хочет передать одноразовую последовательность другому пользователю, Бобу. Алиса и Боб называются принципалами (principals), это главные герои в нашей истории. Например, Боб может быть банкиром, а Алиса — лицом, желающим вступить в деловые отношения с ним. Имена «Алиса» и «Боб» традиционно используются для обозначения принципалов практически во всех материалах, касающихся криптографии, с тех пор как Рон Ривест использовал их в первый раз много лет назад (Rivest и др., 1978). Криптографы вообще обожают разного рода традиции. Если бы мы стали описывать тут взаимоотношения Андрея и Беллы вместо Алисы и Боба, ни одному слову в этой главе никто бы не поверил (стало бы понятно, что автор, на самом деле, далек от криптографии). А так, может быть, поверят. Поэтому пусть Алиса и Боб будут героями нашей книги.
Итак, если Алисе и Бобу удастся установить единую одноразовую последовательность, их переговоры будут полностью конфиденциальными. Задача стоит следующим образом: как им обменяться секретным ключом, не передавая друг другу DVD? Мы можем предположить, что оба пользователя находятся на разных концах одного оптоволоконного кабеля, по которому они могут передавать и принимать световые импульсы. Тем не менее нашлась бесстрашная шпионка Труди, которой удалось установить на пути этого кабеля активное подслушивающее устройство. Она может считывать сигналы, идущие в обоих направлениях. Кроме того, она может посылать как в одну, так и в другую сторону фальшивые сообщения. Ситуация для Алисы и Боба, казалось бы, безнадежная. Но тут на помощь приходит квантовая криптография, и мы сейчас увидим, что у наших героев появляется лучик надежды.
