Криптоанализ шифра простой замены методом поиска наиболее вероятных слов

Пример 2.1

Шифр простої заміни

Метод простой замены состоит в том, что фиксируется некоторая перестановка алфавита , после чего она применяется к каждой букве открытого текста.

В следующем примере описана лишь часть перестановки , достаточная для данного открытого текста. Используется функция StringReplace пакета "Mathematica".

StringReplace["plaintext",

{ "a" -> "k", "e" -> "z", "i" -> "b", "l" -> "r",

"n" -> "a", "p" -> "v", "t" -> "q", "x" -> "d" }]

|| vrkbaqzdq

Более формальное описание системы простой замены состоит в следующем: пространством ключей является множество всех перестановок на множестве , а криптосистема определяется как

где

Функция дешифрования задается равенством , поскольку

В отличие от шифра Цезаря эта система свободна от такого недостатка, как слишком малое пространство ключей. Действительно, . Эта система дает великолепный пример того, как нельзя верить в надежность криптосистемы, основываясь лишь на том, что она имеет большое пространство ключей! Простой подсчет частот появления букв в шифровке и их сравнение с частотами букв из табл. 1.1 позволяет быстро найти образы относительно для большинства наиболее употребительных букв открытого текста. В самом деле, наиболее частая буква в криптограмме скорее всего окажется образом буквы при перестановке . Следующая по частоте будет образом буквы и т.д. После того как найдены прообразы наиболее частых букв криптограммы, нетрудно найти и остальные. Разумеется, чем длиннее криптограмма, тем легче ее расшифровать.

В следующем примере известен очень длинный шифртекст. Вообще говоря, для криптоанализа этого не требуется, но это необходимо, если мы хотим узнать весь ключ полностью. В самом деле, если длина шифртекста мала, то в нем может не встретиться какая-либо пара букв, и тем самым по нему невозможно полностью восстановить ключ, но, разумеется, для его расшифровки весь ключ и не нужен. Помимо известного шифртекста, приведенного в табл. 2.2, будем считать известным то, что в открытом тексте шла речь о "теории двусторонней связи" (по-английски "bidirectional communication theory"). Тогда расшифровка еще больше упрощается.

Таблица 2.2. Криптограмма, полученная простой заменой.

Предположив, что в открытом тексте встречается слово , ищем в шифртексте последовательность из 13 букв, в которой первая буква совпадает с восьмой, вторая — с двенадцатой, третья - с четвертой, шестая — с тринадцатой, а седьмая — с одиннадцатой.

И на самом деле, видим, что подходящая строка трижды встречается в криптограмме. Отсюда извлекаем следующую информацию о перестановке

Предположив, что в открытом тексте встречается также слово , и используя уже полученную о информацию, ищем в шифртексте последовательность вида . Оказывается, что в шифровке четырежды встречается последовательность , из чего следует, что в перестановке

Если теперь применить полученную информацию ко всему шифртексту, то легко найти перестановку целиком. Например, начало текста имеет вид

что, очевидно, читается как

Это дает -образы букв и . Продолжая подобным образом, легко получить всю перестановку: