Быстрый поиск

Учебное пособие: Криптоанализ классических шифров

48 84 13 3394 13 48 42 33 46 82,84 13 82 4894 82 46 84 33 4213 88 82 84 16 46 1625 8250 17 481342 61 37 78 50 511682 42 13 82 84 16 46 1650 48 17 341376 82 25 82 1672 82 46 48 69 17 82 28 82,28 84 4851 75 4875 84 33 46 1646 33 84 33 17,75 33 37 82 13 17 341638 48 37 17 16 46 33.82 1713 58 94 25 33 69 58 13 33 4676 82 75 48 46 33 17 16 34,163476 82 25 33 69 58 13 33 4648 50 5113 94 48,38 42 8217 1648 94 42 781350 16 37 48.1376 37 16 28 82 37 64 17 4817 48 17 33 13 16 94 42 17 82 28 8272 58 46 8294 82 72 37 33 17 8213 94 48,38 42 8284 82 13 48 46 82 94 78 76 82 13 16 84 33 42 7851 75 4851 94 82 76 64 16 501638 42 8269 37 34 4217 58 17 4869 84 37 33 13 94 42 13 51 61 21 16 48:28 82 37 82 84 33,75 33 37 25 16 481688 82 46 82 84 17 58 4894 42 37 33 17 58,94 82 25 37 82 13 16 21 33,94 25 37 58 42 58 481369 48 50 17 58 8828 46 51 72 16 17 33 88,72 82 37 82 69 84 34 21 16 4850 82 37 3425 82 37 33 72 46 16,82 37 51 84 16 3413 82 91 17 58,16 17 94 42 37 51 50 48 17 42 5813 37 33 38 48 13 33 17 16 341650 51 69 58 25 16,76 46 48 17 16 42 48 46 78 17 58 8875 48 17 21 16 17,17 48 76 82 84 13 16 75 17 58 4869 13 48 69 84 581676 46 33 17 48 42 58,25 37 33 94 25 16,25 82 42 82 37 58 50 1676 82 46 78 69 51 61 42 94 3417 48 13 48 37 17 58 48,25 82 28 84 3376 16 64 51 4294 13 82 1650 48 37 69 25 16 48

25 33 37 42 16 17 58,37 33 94 42 48 17 16 341650 16 17 48 37 334 65 894 8213 94 48 50 1616 8894 82 25 37 82 13 48 17 17 58 50 1669 33 50 48 38 33 42 48 46 78 17 58 50 1694 13 82 91 94 42 13 33 50 16,94 48 37 48 72 37 34 17 58 8833 17 28 48 46 82 13,38 48 9188 46 48 72-88 13 33 46 331676 37 48 13 82 69 17 48 94 48 17 16 4828 82 94 76 82 84 33,37 33 69 84 33 38 5117 33 28 37 33 841364 25 82 46 33 88,19 16 28 51 37 5876 42 16 981698 33 37 48 91,88 37 33 17 34 21 16 48 94 341394 33 50 82 5094 48 37 84 98 4876 16 37 33 50 16 84,42 48 17 7872 58 25 33,17 3325 82 42 82 37 82 5076 82 25 82 16 42 94 3469 48 50 46 34,1637 58 72 58,17 3325 82 42 82 37 82 9194 42 82 16 42

72 58 25,76 51 94 42 58 17 1613 94 48 50 16 46 82 94 42 16 13 82 28 8272 82 28 33.82 1751 13 16 84 48 4613 48 21 1617 48 82 76 16 94 51 48 50 58 48,42 33 25 16 48,25 33 2551 46 16 98 58,82 94 13 48 21 48 17 17 58 4828 33 69 82 13 58 50 1637 82 75 25 33 50 16,1625 16 42 33,25 82 42 82 37 58 9151 50 16 37 33 48 4276 37 1669 13 51 25 33 8838 48 46 82 13 48 38 48 94 25 82 28 8228 82 46 82 94 33.

3.4 Шифр Виженера

Теория криптоанализа шифра Виженера

Рассмотрим шифр модульного гаммирования с уравнением bi = (ai+ yi) mod n, для которого гамма является периодической последовательностью знаков алфавита. Такая гамма обычно получается периодическим повторением некоторого ключевого слова. Например, ключевое слово KEY дает гамму KEYKEYKEY... . Рассмотрим задачу вскрытия такого шифра по тексту одной криптограммы достаточной длины.

Пусть µ - длина ключевого слова. Обычно криптоанализ шифра Виженера проводится в два этапа. На первом этапе определяется число µ, на втором этапе — само ключевое слово.

Для определения числа µ применяется так называемый тест Казиски, названный в честь Ф. Казиски, применившего его в 1863 г. Тест основан на простом наблюдении о том, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном µ, будут одинаково зашифрованы. В силу этого в шифр-тексте ищутся повторения длины, не меньшей трех, и расстояния между ними. Обратим внимание на то, что случайно такие одинаковые отрезки могут появиться в тексте с достаточно малой вероятностью.

Пусть d1,d2,... — найденные расстояния между повторениями и d — наибольший общий делитель этих чисел. Тогда µ должно делить d. Чем больше повторений имеет текст, тем более вероятно, что µ совпадает с d. Для уточнения значения µ, можно использовать так называемый индекс совпадения, введенный в практику У. Фридманом в 1920 г.

Для строки х = (x1,...,,xm) длины т, составленной из букв алфавита А, индексом совпадения в х, обозначаемым Ic(х) будем называть вероятность того, что две случайно выбранные буквы из х совпадают.

Пусть A = { ai,..., an }. Будем отождествлять буквы алфавита с числами, гак что

a1 ≡ 0,..., an-1 ≡ n - 2, аn = n -1.

Теорема. Индекс совпадения в х вычисляется по формуле

(1)

где fi — число вхождений буквы ai в х, i Zn.

Доказательство. Будем вычислять Iс(х) как отношение числа благоприятных исходов к общему числу исходов. Благоприятным является исход, при котором на выбранных двух позициях в х расположены одинаковые буквы. Общее число исходов равно, очевидно, С2m . Число благоприятных исходов есть

, (2)

В самом деле, переупорядочим буквы в х таким образом, чтобы сначала шли fa1 букв а1 затем — fa2 букв а2 и т.д.(4):

, (3)

Теперь заметим, что при случайном выборе мест (i и j) в строке х благоприятными являются следующие исходы:

В случае (а1) мы можем выбрать пару букв а, из набора (3) способами, в случае (а2) пару букв а2 из (3) — способами и т. д.

Таким образом, общее число благоприятных исходов выражается величиной (2), а индекс совпадения в х — формулой

и, следовательно, формулой (1).

Пусть х — строка осмысленного текста (например, английского). Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями р0,...,рn-1 независимо друг от друга, где рi — вероятность появления буквы i в осмысленном тексте, i Zn В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с i Zn равна p2i следовательно,

, (4)

Взяв за основу значения вероятностей рi для открытых текстов на английском языке, получаем приближение. Тем самым для английских текстов х можно пользоваться следующим приближением для индекса совпадения:

Iс(x) ≈ 0,066.

Аналогичные приближения можно получить и для других языков. Так, для русского языка получаем приближение:

Iс(x) ≈ 0,053.

Приведем значения индексов совпадения для ряда европейских языков:

Таблица 7. Индексы совпадения европейских языков

Язык	Русский	Алгл.	Франц.	Нем.	Итал.	Испан.
	0,0529	0,0662	0,0778	0,0762	0,0738	0,0775

Рассуждения, использованные при выводе формулы (4), остаются, очевидно, справедливыми и в случае, когда х результат зашифрования некоторого открытого текста простой заменой. В этом случае вероятности рi переставляются местами, но сумма остается неизменной.

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

Вернемся к вопросу об определении числа µ.

Пусть y = y1 y2 …yn данный шифр-текст. Выпишем его с периодом µ:

и обозначим столбцы получившейся таблицы через Y↓1,..., Y↓µ . Если µ это истинная длина ключевого слова, то каждый столбец Y↓i, i1, µ, представляет собой участок открытого текста, зашифрованный простой заменой, определяемой подстановкой

(5)

для некоторого s0,n-l (числа берутся по модулю n).

В силу сказанного выше, (для английского языка) Iс(Y↓i) ≈ 0,066 при любом i. С другой стороны, если µ отлично от длины ключевого слова, то столбцы Y↓i будут более "случайными", поскольку они являются результатом зашифрования фрагментов открытого текста некоторым многоалфавитным шифром. Тогда Iс(Y↓i) будет ближе (для английского языка) к числу1/28 ≈ 0,038

Заметная разница значений Iс(x) для осмысленных открытых текстов и случайных последовательностей букв (для английского языка 0,066 и 0,038, для русского языка — 0,053 и 0,030) позволяет в большинстве случаев установить точное значение µ.

Предположим, что на первом этапе мы нашли длину ключевого слова µ. Рассмотрим теперь вопрос о нахождении самого ключевого слова. Для его нахождения можно использовать так называемый взаимный индекс совпадения.

Пусть х = (х],...,хп),у = (у1,...,ут) две строки букв алфавита А. Взаимным индексом совпадения х и у, обозначаемым МIс(х, у), называется вероятность того, что случайно выбранная буква из х совпадает со случайно выбранной буквой из у.

Пусть f0 f1 …fn и f10 f11 …f1n-1 — числа вхождений букв алфавита в х и у

соответственно.

Теорема. Взаимный индекс совпадения в х и у вычисляется по формуле (эта теорема доказывается точно так же, как и предыдущая теорема.)

, (6)

Пусть k = (k1,..., kµ,) истинное ключевое слово. Попытаемся оценить индексы MIc(Y↓i, Y↓j)

Для этого напомним, что Y↓3 является результатом зашифрования фрагмента открытого текста простой заменой, определяемой подстановкой (5) при некотором s. Вероятность того, что Y↓i и Y↓j произвольная пара букв равна 0, имеет вид pn-si*pn-sj (где ра вероятность появления буквы а в открытом тексте); вероятность того, что обе буквы есть 1, равна pn-si+1*pn-sj+1 и так далее. На основании этого получаем:

Заметим, что сумма в правой части последнего равенства зависит только от разности (si – sj)mod n , которую назовем относительным сдвигом Y↓i и Y↓j. Заметим также, что

, (7)

поэтому Y↓i и Y↓j с относительными сдвигами s и п-s имеют одинаковые взаимные индексы совпадения. Приведем таблицу значений сумм (7) для английского языка:

Таблица 8. Взаимный индекс совпадения при сдвиге s