Введение в современную криптографию


Усовершенствованная атака на сдвиговый шифр



Pdf көрінісі
бет11/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   7   8   9   10   11   12   13   14   ...   249
Криптография Катц

Усовершенствованная атака на сдвиговый шифр. Можно использовать 
таблицы частотности букв, чтобы провести более изощренную атаку на сдвиго-
вый шифр. В предыдущих атаках на сдвиговый шифр требовалось дешифровать 
засекреченный текст с помощью каждого возможного ключа и затем проверять 
какой ключ дает образец «со смыслом». Недостаток данного подхода в том, что 
его до некоторой степени проблематично автоматизировать, поскольку машине 
трудно определить, имеет ли данный образец открытого текста «смысл» или 
нет. (Мы не утверждаем, что это невозможно, так как криптоанализ можно ав-
томатизировать с помощью современного английского толкового словаря. Мы 
лишь утверждаем, что данная задача автоматизации отнюдь не тривиальна.) 
Кроме того, могут быть случаи - мы рассмотрим один такой позднее - когда 
буквы открытого текста распределены в соответствии с характеристиками ча-
стотности английского текста, хотя сам текст составлен не на общепринятом 
английском языке, в результате проверка образца «на смысл» не сработает.
Опишем теперь вариант атаки, который не имеет данных недостатков. Как и 
до этого, интерпретируем буквы английского алфавита с цифрами: 0, . . . , 25. 
Пусть pi, при условии 0 ≤ pi ≤ 1, обозначает частоту встречаемости i-той буквы 
в обычном тексте на английском (без учета пробелов, знаков пунктуации и т.д.).
Вычисление по схему на рисунке 1.3. даст
Теперь, допустим, мы получили некоторый шифртекст, и пусть qi обозначает 
частоту i-той буквы алфавита в данном шифртексте, т.е. qi - просто число появ-
лений i-той буквы алфавита в шифртексте, поделенное на длину зашифрован-


19
ного текста. Если ключ - k, следовательно, pi должно быть примерно равно qi+k 
для всех i, так как i-тая буква отображается в (i + k)-тую букву. (Мы используем 
i+k вместо более громоздкой структуры [i+k mod 26].) Таким образом, если вы-
числить
для каждого значения j ∈ {0, . . . , 25}, то следует ожидать, что Ik ≈ 0,065 (где k 
- настоящий ключ), тогда как Ij для j ƒ= k будет отлично от 0,065. Это приводит 
к атаке на восстановление ключа, которую легко автоматизировать: вычислить 
Ij для всех j, а затем вывести значение k для которого Ik ближе всего к 0,065.


Достарыңызбен бөлісу:
1   ...   7   8   9   10   11   12   13   14   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет