Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Из наших рассмотрений становится понятным, что наиболее трудно формализуемым фрагментом алгоритма 1 является проверка выдвигаемых гипотез о значениях шифробозначений. Трудность состоит в формулировке критерия, подтверждающего или отвергающего ту или иную гипотезу. В статье [Jak95], посвященной этому вопросу, был предложен четко сформулированный критерий, основанный на “близости” матрицы биграмм A(Z) = (Af7(Z))rtxw (где п — число букв алфавита) данного текста t эталонной матрице биграмм
108
Шифры замены
В = (Jblj )пхп открытого текста. Приведем эту идею и основанный на ней эвристический алгоритм дешифрования.
Мерой близости служит следующая “целевая функция” /(/), связывающая матрицы Д(/) и В:
Будем исходить из того естественного предположения, что если у — данная криптограмма и Dk — правило расшифрования на ключе к данного шифра простой замены, то для истинного ключа ки значение
должно быть минимальным.
Идея основного шага алгоритма состоит в том, чтобы исходя из некоторого первичного “приближения” к для ключа ки, основанного, например, на диаграмме частот букв, немного его изменять неким “разумным” способом, уменьшая значение целевой функции /(J).
Приведем теперь формальное описание алгоритма
Алгоритм 2
1. Построить начальный вариант ключа к на основе сравнения частот знаков криптограммы и открытого текста.
2. Положить V = f(Dk(y)).
3. Положить к' = к .
4. Поменять местами в нижней строке подстановки А:1 некоторую пару букв, скажем а и P.
5. Положить Vt= f(Dk,(y)).
6. Если v’< V, то положить к = к\ Vf= v и перейти к 4.
(1)
[Jak95].
109
/ лава 5
7. Перейти к шагу 3.
Алгоритм заканчивается, когда условие v'< v не выполняется в течение некоторого числа итераций, например 100.
Переход на шаге 4 от к к к', связанный с транспозицией пары символов, имеет под собой следующее основание. На шаге 5 вычисляется величина
V'= )) = 2 -*j,| =
и и
где A1 (/) — матрица, полученная из матрицы A(V) путем перестановки в ней столбцов с номерами а и P, а также строк с теми же номерами.
В силу отмеченного свойства на шаге 5 алгоритма не нужно проводить трудоемкую операцию вычисления матрицы биграмм А (Dk, (у)) непосредственно по “расшифрованному” тексту DkXy) • Достаточно вычислить лишь матрицу
A(Dk(y)), а на следующих шагах алгоритма производить в ней одноименные перестановки строк и столбцов.
Выбор транспозиции (а, /5) на шаге 4 можно производить, например, следующим естественным образом. Пусть s = (sx,s2,...,s„) — вектор, образованный буквами криптограммы, упорядоченными по убыванию частот. Тогда последовательность транспозиций можно выбрать такой:
HO
Шифры замены
C^l 9 )’ 2 ’ *3 )»•••» 2 » ^n-I )> 9 $п )’
(S\? S3 )ї С52 > )?*••? (5л-2 > 5W )>
Ol ,s„).
В [Jak95] показано, что алгоритм 2 является достаточно эффективным.
Отметим некоторые особенности вскрытия равнозначных и разнозначных шифров простой замены.
Если шифр простой замены не является однобуквенным, то при вскрытии криптограммы необходимо попытаться восстановить множество шифрвеличин. Если эта задача решена, то дальнейшая работа ничем не отличается от той, которую мы проделали для шифра однобуквенной простой замены.
Заметим, что в литературных открытых текстах часто встречаются повторения фрагментов, состоящих из трех и большего числа букв. При применении к тексту шифра простой замены соответствующие повторения остаются и в шифрованном тексте. Если в криптограмме встретилось несколько повторений, то их успешно можно использовать для определения значности шифробозначений.
Очевидно, что для равнозначного шифра простой замены длины повторений и расстояния между ними должны быть кратны значности шифра. Находя наибольший общий делитель этих чисел, мы с большой вероятностью получаем искомую значность. Некоторые сомнения в правильности определения значности помогает устранить подсчет общего числа шифробозначений. Если это число близко к ожидаемому числу шифробозначений (скажем, к числу букв алфавита), и диаграмма их повторяемости близка к табличной, то, скорее всего, значность определена верно.
Для разнозначного шифра дело обстоит несколько сложнее. В этом случае числа, равные длинам повторений и расстояниям между ними, скорее всего, взаимно просты в сово-
111
І лава Ь
купности. Однако и для таких шифров задача определения множества шифробозначений не безнадежна. В этом помогает естественное ограничение, которым обычно пользуются при составлении таблицы шифробозначений. Оно связано с требованием однозначности расшифрования и заключается в том, чтобы ни одно из шифробозначений не являлось началом никакого другого шифробозначения (в теории кодирования в подобной ситуации говорят о префиксном коде). Если значность шифробозначений колеблется в незначительных пределах, то перебор сравнительно небольшого числа вариантов приводит (с учетом ограничения) к правильному определению большинства шифробозначений. Некоторые затруднения могут возникать лишь при определении значности шифробозначений, редко встречающихся в тексте. Как правило, эти проблемы решаются вместе с попытками прочтения тех участков криптограммы, для которых восстановленная значность шифробозначений не вызывает сомнений.
