Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Пусть /л — длина ключевого слова. Обычно криптоанализ шифра Виженера проводится в два этапа. На первом этапе
143
і лава б
определяется число //, на втором этапе — само ключевое слово.
Для определения числа ju применяется так называемый тест Казиски, названный в честь Ф. Казиски, применившего его в 1863 г. Тест основан на простом наблюдении того, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном //, будут одинаково зашифрованы. В силу этого в шифртексте ищутся повторения длины, не меньшей трех, и расстояния между ними. Обратим внимание на то, что случайно такие одинаковые отрезки могут появиться в тексте с достаточно малой вероятностью.
Пусть dx,d2,... — найденные расстояния между повторениями и d — наибольший общий делитель этих чисел. Тогда JU должно делить d. Чем больше повторений имеет текст, тем более вероятно, что pi совпадает с d. Для уточнения значения [л можно использовать так называемый индекс совпадения, введенный в практику У. Фридманом в 1920 г.
Для строки х = (X19...,хт) длины т, составленной из букв алфавита А, индексом совпадения в х, обозначаемым Zc(JC), будем (следуя [Sti95]) называть вероятность того, что две случайно выбранные буквы из jc совпадают.
Пусть А = {ах,...,ап}. Будем отождествлять буквы алфавита с числами, так что ах = 0,..., ап_{ = п — 2,ап =п — 1.
Теорема Индекс совпадения в х вычисляется по формуле
Ц/д/, - о
Zc(X)="0- - , (14)
т(т -1)
где ft —число вхождений буквы U1 в Xf і є Zn.
144
Шифры гаммирования
Доказательство. Будем вычислять /с(х) как отношение числа благоприятных исходов к общему числу исходов. Благоприятным является исход, при котором на выбранных двух позициях в jc расположены одинаковые буквы. Общее
число исходов равно, очевидно, C2 . Число благоприятных исходов есть
ш-1
IlcI-
(15)
/=O
В самом деле, переупорядочим буквы в jc таким образом, чтобы сначала шли fa букв , затем— fa букв а2 и т.д.:
a,,...,A1 ... . (16)
J at J ап
Теперь заметим, что при случайном выборе мест (/ и J) в строке jc благоприятными являются следующие исходы:
[0... І ... У- т — 1
I - av. O1 ..
I0' .. і. j... ,т-1
• а2 а2 ...
jo.. . І . ¦j - S і
I.. .ап. ап ...
(«и)
В случае (а}) мы можем выбрать пару букв ах из набора
(16) Cf способами, в случае (а2) пару букв а2 из (16) —
/о,
2
Cf способами и т. д. Таким образом, общее число благо-
J Q2
145
fлава 6
приятных исходов выражается величиной (15), а индекс совпадения вх — формулой
и, следовательно, формулой (14).
Пусть х — строка осмысленного текста (например, английского). Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями независимо друг от друга, где P1 — вероятность
появления буквы і в осмысленном тексте, і є Zn. В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с і є Zw, равна р] , следовательно,
Взяв за основу значения вероятностей р}, приведенные в Приложении 1 для открытых текстов на английском языке,
25 2
получаем приближение YjPi ® 0,066. Тем самым для анг-
*=0
лийских текстов X можно пользоваться следующим приближением для индекса совпадения:
Аналогичные приближения можно получить и для других языков. Так, для русского языка на основании данных из Приложения 1 получаем приближение:
т-1
л-1
(17)
Ic(X)* 0,066.
146
Шифры гаммирования
1с(х)* 0,053.
Приведем значения индексов совпадения для ряда европейских языков, заимствованные из [Fri85]:
Таблица 6. Индексы совпадения европейских языков
Язык Русский Англ. Франц. Нем. Итал. Испан.
/С(Лг) * 0,0529 0,0662 0,0778 0,0762 0,0738 0,0775
Рассуждения, использованные при выводе формулы (17), остаются, очевидно, справедливыми и в случае, когда х — результат зашифрования некоторого открытого текста простой заменой. В этом случае вероятности P1 переставляются
Предположим, что х — реализация независимых испытаний случайной величины, имеющей равномерное распределение на Ъп . Тогда индекс совпадения вычисляется по формуле
Вернемся к вопросу об определении числа /л .
Пусть у = У\У2—Ут —данный шифртекст. Выпишем его с периодом //:
п-1
местами, но сумма ^/?(2 остается неизменной.
I=о
?4 1 11
У1 Ум I У2» I
У2 Ум'2 У2,и 2
Ум У2м Уїм
147
І лава 6'
и обозначим столбцы получившейся таблицы через Yx .
Если Ji — это истинная длина ключевого слова, то каждый
столбец Y1^, / єі,//, представляет собой участок открытого
текста, зашифрованный простой заменой, определяемой подстановкой
(0 1 2 ... п -S ... п ^
(18)
s + 1 s + 2 ... О ... S-IJ
для некоторого S є 0, п -1 (числа берутся по модулю п).
В силу сказанного выше (для английского языка)
Ic (Y^) «0,066 при любом і. С другой стороны, если JU отлично от длины ключевого слова, то столбцы Y1^ будут более
“случайными”, поскольку они являются результатом зашифрования фрагментов открытого текста некоторым многоалфавитным шифром. Тогда 7С(У/) будет ближе (для английского языка) к числу ^ ж 0,038 .
