Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

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.

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

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

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

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

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

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

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

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

a₁ ≡ 0,..., a_n-1 ≡ n - 2, а_n = n -1.

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

(1)

где f_i — число вхождений буквы a_i в х, i Z_n.

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

, (2)

В самом деле, переупорядочим буквы в х таким образом, чтобы сначала шли f_a1 букв а₁ затем — f_a2 букв а₂ и т.д.(4):

, (3)

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

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

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

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

Пусть х — строка осмысленного текста (например, английского). Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями р₀,...,р_n-1 независимо друг от друга, где р_i — вероятность появления буквы i в осмысленном тексте, i Z_n В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с i Z_n равна p²_i следовательно,

, (4)

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

I_с(x) ≈ 0,066.

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

I_с(x) ≈ 0,053.

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

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

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

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

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

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

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

(5)

для некоторого s 0,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) позволяет в большинстве случаев установить точное значение µ.

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

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

Пусть f₀ f₁ …f_n и f¹₀ f¹₁ …f¹_n-1 — числа вхождений букв алфавита в х и у

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

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

, (6)

Пусть k = (k₁,..., k_µ,) — истинное ключевое слово. Попытаемся оценить индексы MI_c(Y^↓_i, Y^↓_j)

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

Заметим, что сумма в правой части последнего равенства зависит только от разности (s_i – s_j)mod n , которую назовем относительным сдвигом Y^↓_i и Y^↓_j. Заметим также, что

, (7)

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

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

Сдвиг s	0	1	2	3	4	5	6
	0,066	0,039	0,032	0,034	0,044	0,033	0,036
Сдвиг s	7	8	9	10	11	12	13
	0,039	0,034	0,034	0,038	0,045	0,039	0,043

Обратим внимание на то, что ненулевые "сдвиги" дают взаимные индексы совпадения, изменяющиеся в пределах от 0,032 до 0,045, в то время как при нулевом сдвиге индекс MI_c(x,y) близок к 0,066. Это наблюдение позволяет определить величины относительных сдвигов s_i – s_j столбцов Y^↓_i и Y^↓_j. Для этого заметим, что при некотором значении s(i,j) 0, n-1столбец Y^s(i,j)↓_j, полученный из Y^↓_j прибавлением к каждому его элементу числа S(i,j) (по модулю n), имеет нулевой относительный сдвиг с Y^↓_j.

Пусть Y^0↓_j , Y^1↓_j,…, Y^n-1↓_j – результаты зашифрования Y^↓_j каждой из простых замен (5). Несложно вычислить взаимные индексы

(всего, таким образом, имеется С²_µn значений). Для этого воспользуемся формулой, полученной из (6):

Если s равно s_i – s_j - (относительному сдвигу Y^↓_i и Y^↓_j), то взаимный индекс впадения должен быть (для английского языка) близок к 0,066, так как относительный сдвиг Y^↓_i и Y^↓_j равен нулю. Если же s не равно s_i – s_j то взаимный индекс совпадения должен колебаться в пределах 0,032 - 0,045.

Используя изложенный метод, мы сможем связать системой уравнений относительные сдвиги различных пар столбцов Y^↓_i и Y^↓_j. В результате останется 26 (для английского языка) вариантов для ключевого слова, из которых можно выбрать наиболее предпочтительный вариант (если ключевое слово является осмысленным).

Характеристики

Список файлов книги