Алгоритм 1

1. Подсчет частот встречаемости шифробозначений, а также некоторых их сочетаний, например биграмм и триграмм подряд идущих знаков.

2. Выявление шифробозначений, заменяющих гласные и согласные буквы.

3. Выдвижение гипотез о значениях шифробозначений и их проверка. Восстановление истинного значения шифробо­значений.

Если длина текста достаточно велика, то найденные на этапе 1 частоты окажутся близкими к табулированным значе­ниям частот знаков (соответственно — биграмм или три­грамм). Проведенная на этом этапе работа служит основанием для выдвижения гипотез о значениях шифрвеличин, соответ­ствующих данным шифробозначениям. При этом учитывает­ся, что каждая буква имеет группу предпочтительных связей (наиболее вероятных сочетаний её с другими буквами), которые составляют ее наиболее харак­терную особенность. Как правило, такие гипотезы подтвер­ждаются не полностью. Хорошим критерием при этом являет­ся «читаемость» восстанавливаемого открытого текста. Важно также учитывать процентное соотношение количества гласных и согласных в открытом тексте и прочие их характеристики, например:

- если шифробозначение часто встречается, равномерно располага­ется по шифртексту, в отдельных местах чередуется через 1, 2 или 3 знака, сочетается с средними и редкими (по частоте) шифробозначениями, то это дает основания полагать, что такое шифробозначение скрывает гласную букву;

- удвоение гласных в открытом тексте происходит реже, чем согласных;

- если некоторое шифробозначение признано гласной, то бук­ва, часто сочетающаяся с ней, скорее всего согласная;

- в от­крытом тексте чрезвычайно редко встречаются три, и более, подряд идущие гласные;

- четыре, и более, подряд идущие согласные также редки и т. д. (см. Алферов и др. «Криптографические методы защиты информации», Приложение 1).

Если с помощью приведенных соображений произведено несколько идентификаций шифробозначений, то дальнейшая работа по вскрытию текста криптограммы не представляет особого труда. Пример вскрытия шифра простой однобуквенной замены по алгоритму 1 приведен в (Алферов и др. «Криптографические методы защиты информации», Приложение 2).

Наи­более трудно формализуемым фрагментом алгоритма 1 явля­ется проверка выдвигаемых гипотез о значениях шифробозначений. Трудность состоит в формулировке критерия, под­тверждающего или отвергающего ту или иную гипотезу. В (см. Алферов и др. «Криптографические методы защиты информации», п. 5.2) со ссылкой на автора изложен один из способов четкой формализации критерия, основанный на “близос­ти” матрицы биграмм (где n — число букв алфавита) данного текста t эталонной матрице биграмм открытого текста. Приведем эту идею и осно­ванный на ней эвристический алгоритм дешифрования.

Мерой близости служит следующая «целевая функция» f(t), связывающая матрицы (t) и b:

.

Будем исходить из того естественного предположения, что если у — данная криптограмма и D_k — правило расшиф­рования на ключе k данного шифра простой замены, то для истинного ключа k_u, значение

должно быть минимальным.

Идея основного шага алгоритма состоит в том, чтобы ис­ходя из некоторого первичного “приближения” k для ключа k_u, основанного, например, на диаграмме частот букв, не­много его изменять неким «разумным» способом, уменьшая значение целевой функции f(t).

Приведем теперь формальное описание алгоритма.