С точки зрения криптоаналитика задача криптоанализа имеет три принципиальных варианта. Во-первых, у криптоаналитика может быть некоторое количество зашифрованного текста без соответствующего открытого текста. Задачки, в которых в качестве исходных данных имеется в наличии только зашифрованный текст (ciphertext-only), часто печатаются в различных газетах в разделе ребусов. Во-вторых, у криптоаналитика может оказаться некоторое количество зашифрованного текста и соответствующего ему открытого текста. В этом случае мы имеем дело с проблемой известного открытого текста (known plaintext). Наконец, когда у криптоаналитика есть возможность зашифровать любой кусок открытого текста по своему выбору, мы получаем третий вариант проблемы дешифрации, то есть проблему произвольного открытого текста (chosen plaintext). Если бы криптоаналитикам было позволено

задавать вопросы типа: «Как будет выглядеть зашифрованное ABCDEFGHJKL?», задачки из газет решались бы очень легко.

Новички в деле криптографии часто полагают, что шифр является достаточно надежным, если он может выдержать атаку первого типа (только зашифрованный текст). Такое предположение весьма наивно. Во многих случаях криптоаналитик может угадать часть зашифрованного текста. Например, первое, что говорят многие компьютеры при входе в систему, это login:. После того как криптоаналитик получит несколько соответствующих друг другу пар кусков зашифрованного и открытого текста, его работа становится значительно легче. Для обеспечения секретности нужна предусмотрительность криптографа, который должен гарантировать, что система не будет взломана, даже если его оппонент сможет закодировать несколько фрагментов открытого текста по своему выбору.

Исторически методы шифрования разделились на две категории: метод подстановки и метод перестановки. Мы кратко рассмотрим их в качестве введения в современную криптографию.

8.1.2. Метод подстановки

В шифрах, основанных на методе подстановки (substitution cipher), каждый символ или группа символов заменяется другим символом или группой символов. Одним из древнейших шифров является приписываемый Юлию Цезарю ( Julius Caesar) шифр Цезаря (Caesar cipher). Этот шифр заменяет все буквы алфавита на другие с помощью циклического сдвига на три позиции. Так буква а становится буквой D, b становится E, c превращается в

Например, слово attack превращается в DWWDFN.

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

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

Следующее усовершенствование состоит в установлении соответствия каждому встречающемуся в открытом тексте символу другого символа. Например,

Такая система называется моноалфавитным подстановочным шифром (monoalphabetic substitution cipher), ключом к которому является 26-символьная строка, соответствующая полному алфавиту. В нашем примере слово attack будет выглядеть, как QZZQEA.

На первый взгляд такая система может показаться надежной, так как, даже если криптоаналитику известна общая система, он не знает, какой из 26! = 4 х 1026 возможных вариантов ключа применить. В отличие от шифра Цезаря применение метода простого перебора в данном случае весьма сомнительно. Даже при затратах 1 нс на проверку одного варианта ключа, чтобы перепробовать все ключи, миллиону компьютерных чипов, работающих одновременно, понадобится около 10 000 лет.

Тем не менее подобный шифр легко взламывается даже при наличии довольно небольших фрагментов зашифрованного текста. Для атаки шифра может быть использовано преимущество статистических характеристик естественных языков. Например, в английском языке буква e встречается в тексте чаще всего. Следом за ней по частоте использования идут буквы t, о, a, n, i и т. д. Наиболее часто встречающимися комбинациями из двух символов (биграммами — digrams) являются th, in, er, re и an. Наиболее часто встречающимися комбинациями из трех символов, или триграммами (trigrams), являются the, ing, and и ion.

Криптоаналитик, пытающийся взломать моноалфавитный шифр, начнет с того, что сосчитает относительные частоты всех символов алфавита в зашифрованном тексте. Затем он может попытаться заменить наиболее часто встречающийся символ буквой e, а следующий по частоте — буквой t. Затем он посмотрит на триграммы и попытается найти что-либо похожее на tXe, после чего он сможет предположить, что X — это h. Аналогично, если последовательность thYt встречается достаточно часто, то, вероятно, Yобозначает символ а. Обладая этой информацией, криптоаналитик может поискать часто встречающуюся триграмму вида 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.1.3. Метод перестановки

Шифры, основанные на методе подстановки, сохраняют порядок символов, но подменяют их. Шифры, использующие метод перестановки (transposition ciphers), меняют порядок следования символов, но не изменяют сами символы. На рис. 8.2 показан простой перестановочный шифр с колоночной перестановкой. Ключом к шифру служит слово или фраза, не содержащая повторяющихся букв. В данном примере в качестве ключа используется слово MEGABUCK. Цель ключа — пронумеровать колонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита и т. д. Открытый текст записывается горизонтально в строках. Шифрованный текст читается по колонкам, начиная с колонки с младшей ключевой буквой.

Рис. 8.2. Перестановочный шифр

Чтобы взломать перестановочный шифр, криптоаналитик должен вначале понять, что он имеет дело именно с перестановочным шифром. Если взглянуть на частоту символов E, T, A, O, I, N и т. д., легко заметить, что их частоты соответствуют нормальным частотам открытого текста. В таком случае, очевидно, что этот шифр является перестановочным, так как каждая буква в таком шифре представляет сама себя.