Компьютерные сети. 6-е изд. - Эндрю Таненбаум

и обманул жителей Помпеи, но с тех пор ему уже никого не удалось ввести в заблуждение.

Следующее усовершенствование заключается в установлении соответствия между каждым символом в открытом тексте (для простоты, скажем, это 26 букв) и каким-либо другим. Например,

открытый текст:

a b c d e f g h i j k l m n o p q r s t u v w x y z

зашифрованный текст:

Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

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

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

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

Криптоаналитик, пытающийся взломать моноалфавитный шифр, прежде всего сосчитает относительные частоты всех символов алфавита в зашифрованном тексте. Затем он попробует заменить наиболее часто встречающийся символ буквой 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,