Криптоаналитик, пытающийся взломать моноалфавитный шифр, прежде всего сосчитает относительные частоты всех символов алфавита в зашифрованном тексте. Затем он попробует заменить наиболее часто встречающийся символ буквой e, а следующий по частоте — буквой t. Затем он найдет триграммы самой распространенной формы tXe, где, скорее всего, X — это h. Аналогичным образом, если последовательность thYt встречается достаточно часто, то, вероятно, Y обозначает символ a. Обладая этой информацией, криптоаналитик может поискать часто встречающуюся триграмму вида aZW, что, скорее всего, означает and. Продолжая угадывать буквы, биграммы и триграммы и зная, какие последовательности символов являются наиболее вероятными, криптоаналитик побуквенно восстанавливает исходный текст.
Другой метод заключается в угадывании слова или фразы целиком. Например, рассмотрим следующий зашифрованный текст, полученный от бухгалтерской фирмы (разбитый на блоки по пять символов):
CTBMN BYCTC BTJDS QXBNS GSTJC BTSWX CTQTZ CQVUJ QJSGS TJQZZ MNQJS VLNSX VSZJU JDSTS JQUUS JUBXJ DSKSU JSNTK BGAQJ ZBGYQ TLCTZ BNYBN QJSW
В сообщении бухгалтерской фирмы, скорее всего, есть слово financial. Используя тот факт, что в этом слове буква i встречается дважды, разделенная четырьмя другими буквами, мы будем искать в зашифрованном тексте повторяющиеся символы, отстоящие друг от друга на это расстояние. В результате мы найдем 12 таких мест в тексте в позициях 6, 15, 27, 31, 42, 48, 56, 66, 70, 71, 76 и 82. Однако только в двух случаях, в позициях 31 и 42, следующий символ (соответствующий букве n в открытом тексте) повторяется в соответствующем месте. Из этих двух вариантов символ a имеет правильное расположение только для позиции 31. Теперь нам известно, что слово financial начинается в позиции 30. С этого момента выяснить ключ проще, применяя лингвистическую статистику английского языка и угадывая целые слова.
8.4.4. Перестановочные шифры
Подстановочные шифры «маскируют» символы открытого текста, но не меняют порядок их следования. Перестановочные шифры (transposition ciphers), наоборот, меняют порядок следования символов, но не «маскируют» их. На илл. 8.10 показан простой перестановочный шифр с колоночной перестановкой. Ключом к такому шифру служит слово или фраза, в которых нет повторяющихся букв. В данном примере в качестве ключа используется слово MEGABUCK. Цель ключа — пронумеровать колонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т.д. Открытый текст записывается горизонтально в строках. Зашифрованный текст читается по колонкам, начиная с колонки с младшей ключевой буквой.
Илл. 8.10. Перестановочный шифр
Чтобы взломать перестановочный шифр, прежде всего криптоаналитик должен понять, что он имеет дело именно с таким способом шифрования. Если посмотреть, насколько часто здесь употребляются символы E, T, A, O, I, N и т.д., можно легко заметить, что частота их употребления такая же, как в обычном открытом тексте. Становится ясно, что мы имеем дело с перестановочным шифром, поскольку при его использовании буквы представляют сами себя, и, соответственно, распределение частот остается неизменным.
Затем нужно угадать число колонок. Во многих случаях по контексту сообщения можно угадать слово или фразу. К примеру, криптоаналитик подозревает, что где-то в сообщении должно встретиться словосочетание milliondollars. Обратите внимание, что из-за присутствия этих слов в исходном тексте в зашифрованном тексте встречаются биграммы MO, IL, LL, LA, IR и OS. Символ O следует за символом M (то есть они стоят рядом по вертикали в колонке 4), поскольку они разделены в предполагаемой фразе дистанцией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вместо перечисленных выше биграмм встречались бы следующие: MD, IO, LL, LL, IA, OR и NS. Таким образом, для каждой длины ключа в зашифрованном тексте образуется новый набор биграмм. Перебрав различные варианты, криптоаналитик зачастую довольно легко может определить длину ключа.
Остается узнать только порядок колонок. Если их число k невелико, можно перебрать все k(k – 1) возможных комбинаций пар соседних колонок, сравнивая частоты образующихся биграмм со статистическими характеристиками английского языка. Пара с лучшим соответствием считается правильно позиционированной. Затем все оставшиеся колонки по очереди проверяются в сочетании с уже найденной парой. Предполагается, что колонка, в которой биграммы и триграммы дают максимальное совпадение со статистикой, является правильной. Весь процесс повторяется, пока не будет восстановлен порядок всех колонок. Есть шанс, что на данном этапе текст уже будет распознаваемым (например, если вместо слова million мы увидим milloin, то сразу станет ясно, где допущена ошибка).
Некоторые перестановочные шифры принимают блок фиксированной длины на входе и выдают блок фиксированной длины на выходе. Они полностью определяются списком, сообщающим порядок, в котором символы попадают в выходной блок. Например, шифр на илл. 8.10 можно рассматривать в виде шифра с 64-символьным блоком. Его выход описывается последовательностью чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13, …, 62. То есть четвертая входная буква a первой появится на выходе, за ней последует двенадцатая f и т.д.
8.4.5. Одноразовые блокноты
Разработать шифр, который невозможно взломать, на самом деле довольно легко. Метод его создания известен на протяжении уже нескольких десятилетий. В качестве ключа выбирается произвольная битовая строка, длина которой совпадает с длиной исходного текста. Открытый текст также преобразуется в последовательность двоичных разрядов, например, с помощью стандартной кодировки ASCII. Наконец, две эти строки поразрядно складываются по модулю 2 (операция XOR). Полученный в итоге зашифрованный текст невозможно взломать, поскольку в достаточно большом отрывке любая буква, биграмма или триграмма будет равновероятной. Этот метод называется одноразовым блокнотом (one-time pad) и теоретически является панацеей от любых атак (как существующих сегодня, так и будущих), независимо от вычислительных мощностей, которыми обладает взломщик. Объясняется это теорией информации: дело в том, что в зашифрованном сообщении не содержится никаких сведений для взломщика, поскольку любой открытый текст нужной длины является равновероятным кандидатом.
Пример практического использования одноразового блокнота показан на илл. 8.11. Для начала фраза «I love you» («Я люблю тебя») преобразуется в 7-битный ASCII-код. Затем составляется некий одноразовый блокнот 1, который складывается по модулю 2 с сообщением. В результате получается шифр. Чтобы его разгадать, криптоаналитику придется перебрать все возможные варианты одноразового блокнота, всякий раз проверяя, каким получается открытый текст. Например, если попробовать расшифровать послание с помощью блокнота 2 (см. илл. 8.11), получится текст «Elvis lives» («Элвис жив»). На самом деле для генерации любой последовательности из 11 символов в кодировке ASCII найдется одноразовый блокнот. Именно это мы имеем в виду, говоря, что в зашифрованном тексте не содержится никаких сведений: из него можно извлечь любое сообщение подходящей длины.
Одноразовые блокноты теоретически являются очень мощным инструментом, но на практике они имеют ряд недостатков. Во-первых, такой длинный ключ невозможно запомнить, поэтому и отправитель и получатель должны носить с собой письменную копию ключа. Если есть риск того, что одну из копий захватит взломщик, хранить письменные копии весьма нежелательно. Кроме того, полный объем данных, которые можно передать, ограничен размером доступного ключа. Может произойти ситуация, в которой шпион добудет много информации, но не сможет передать все эти сведения в центр, так как ему не хватит длины ключа. Еще одна проблема заключается в чувствительности метода к потерянным или вставленным символам. Если отправитель и получатель потеряют синхронизацию, все данные, начиная с этого места, будут искажены.