Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Атака на шифр Виженера. Первое, на что надо обратить внимание при по-
пытке раскрыть шифр Виженера, - это известна ли длина ключа, остальной анализ шифра относительно прост. В частности, пусть длина ключа, также на- зываемая периодом повторения, равна t. Запишем ключ k как k = k1 • • • kt, где каждый ключ ki - буква алфавита. Наблюдаемый шифркод c = c1c2 • • • можно поделить на t частей, где каждая часть может рассматриваться как шифрграмма с помощью сдвигового шифра. В частности, для всех j ∈{1, . . . , t} символы шифртекста cj, cj+t, cj+2t, . . . получились путем сдвига соответствующих букв открытого текста на kj пози- ций. Последовательность символов, которая указана выше, называется j-тым потоком. Все, что осается сделать - определить какой из 26 возможных сдвигов использовался для каждого из потоков t . Данная задача не так проста, как в случае со сдвиговым шифром, так как больше уже невозможно простым пере- бором определить, когда дешифрование потока будет «иметь смысл». (Стоит напомнить, что поток не соответствует последовательности букв открытого текста.) Далее, в попытке разгадать весь ключ k сразу потребуется перебрать 26t различных вариантов, что нереализуемо при больших t. Несмотря на это, можно применять частотный анализ для вскрытия каждого потока отдельно. То есть для каждого потока мы составляем таблицу частотности каждого символа шифртекста и проверяем, какой из 26 возможных сдвигов приводит к «правиль- ному» распределению вероятностей в данном потоке. Поскольку такая проце- дура может проводиться для каждого потока в отдельности (т.е. для каждого символа ключа), времени на такую атаку потребуется 26 • t, а не 26t. Более принципиальный и легкий для автоматизации подход заключается в ис- 21 пользовании улучшенного метода раскрытия сдвигового шифра, описанного ранее. Такая атака не опиралась на проверку образца «на смысл», а только учи- тывала базовое частотное распределение символов открытого текста. Любой из представленных выше подходов подойдет для атаки, когда извест- на длина ключа. А если она неизвестна? Поскольку максимальная длина ключа T не слишком велика, мы можем запро- сто повторить описанную выше атаку T раз (для каждого возможного значения t ∈ {1, ..., T}). В результате мы получим максимум T разных потенциально подходя- щих текстов, среди которых выявить настоящий текст, скорее всего, будет просто. Таким образом, неизвестная длина ключа не является серьезным препятствием. Кроме того, существуют более эффективные способы определения длины ключа по наблюдаемому шифртексту. Один из них - метод Касиски, опубли- кованный в середине XIX века. Первый шаг - выявление повторяющихся со- четаний двух или трех символов шифртекста. Они, скорее всего, будут соответ- ствовать часто встречающимся биграммам или триграммам открытого текста. Например, рассмотрим часто встречающееся в английском языке слово «the». Это слово будет отображаться с помощью разных символов шифртекста, в за- висимости от его положения в открытом тексте. Однако если слово дважды встретится в относительно похожей позиции, то оно отобразится с помощью аналогичных символов шифртекста. Таким образом, в достаточно длинном от- крытом тексте, велика вероятность, что «the» неоднократно отобразится с по- мощью одинаковых символов шифртекста. Рассмотрим конкретный пример, ключом в котором будет beads (пробелы до- бавлены для внесения ясности): __________________________________________________________ Открытый текст: the man and the woman retrieved the letter from the post office (муж- чина и женщина получили письмо на почте) Ключ: bea dsb ead sbe adsbe adsbeadsb ead sbeads bead sbe adsb eadsbe Шифртекст: ULE PSO ENG LII WREBR RHLSMEYWE XHH DFXTHJ GVOP LII PRKU SFIADI __________________________________________________________ Слово «the» иногда отображается как ULE, иногда как LII, и иногда как XHH. С другой стороны, оно дважды встречается в виде LII, а в достаточно длинном тексте оно, скорее всего, несколько раз встретилось бы в каждом из возмож- ных сочетаний. Наблюдение Касиски заключалось в том, что расстояние между подобными повторениями (при условии, что они неслучайны) должно быть кратно периоду повторения. (В приведенном выше примере период повторения 22 равен 5, а расстояние между двумя сочетаниями LII равно 30, что соответствует 6 повторениям периода.) Таким образом, наибольший общий делитель рассто- яния между повторяющимися последовательностями (при условии, что они не- случайны) позволяет определить длину ключа t или его кратное. Альтернативный подход, метод индекса повторений, методичнее, а значит, его легче автоматизировать. Напомним, что если длина ключа равна t, то все символы шифртекста c1, c1+t, c1+2t, ... в первом потоке были получены из шифрования с использованием одинаково- го сдвига. Таким образом, предполагается, что частота появлений символов в данной последовательности будет совпадать с частотой появлений символов стандартного английского текста в некоторой сдвинутой последовательности. Например, пусть qi обозначает замеченную частоту повторений i-той буквы английского алфавита в данном потоке, соответствующее отношению числа вхождений i-той буквы алфавита к общему числу букв в потоке. Если использованный здесь сдвиг равен j (т.е ., если первый символ ключа k1 равен j), то для всех i мы полагаем, что qi+j ≈ pi, где рi - частота появления i-той буквы алфавита стандартного английского текста. (Опять-таки , мы используем qi+j вместо q[i+j mod 26].) Но из этого следует, что последовательность q0, ..., q25 всего лишь является последовательностью p0, ..., p25, сдвинутой на j мест. Следовательно, (см. Уравнение (1.1)): Таким образом, мы можем точно определить длину ключа t. Для τ = 1, 2, . .., рассмотрите последовательность символов шифртекста c1, c1+τ , c1+2τ , ... и составьте таблицу q0, ..., q25 для данной последовательности. Затем вычислите Когда τ = t, мы предполагаем, что Sτ ≈ 0.065, как указано выше. С другой сто- роны, если τ не кратно t, мы предполагаем, что все символы будут встречаться с приблизительно равной вероятностью в последовательности c1, c1+τ, c1+2τ, . . ., а значит, мы полагаем, что qi ≈ 1/26 для всех i. В этом случае мы получим Таким образом, наименьшее значение τ, для которого Sτ ≈ 0.065, скорее всего, будет равно длине ключа. Затем можно проверить предположение τ, проведя 23 аналогичные расчеты, используя второй поток c2, c2+τ , c2+2τ , . .., и т.д . жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|