Криптоанализ классических шифров. Жданов О.Н - 46 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

46
наблюдении о том, что два одинаковых отрезка открытого текста, отстоящих друг от
друга на расстоянии, кратном µ, будут одинаково зашифрованы. В силу этого в
шифр-тексте ищутся повторения длины, не меньшей трех, и расстояния между
ними. Обратим внимание на то, что случайно такие одинаковые отрезки могут
появиться в тексте с достаточно малой вероятностью.
Пусть d
1
,d
2
,... — найденные расстояния между повторениями и d —
наибольший общий делитель этих чисел. Тогда µ должно делить d. Чем больше
повторений имеет текст, тем более вероятно, что µ совпадает с d. Для уточнения
значения µ, можно использовать так называемый индекс совпадения, введенный в
практику У. Фридманом в 1920 г.
Для строки х = (x
1
,...,
,
x
m
) длины т, составленной из букв алфавита А, индексом
совпадения в х, обозначаемым I
c
(х) будем называть вероятность того, что две
случайно выбранные буквы из х совпадают.
Пусть A = { a
i
,..., a
n
}. Будем отождествлять буквы алфавита с числами, гак что
a
1
≡ 0,..., a
n-1
≡ n - 2, а
n
= n -1.
Теорема. Индекс совпадения в х вычисляется по формуле
,
)1(
)1(
)(
1
0
1
−
−
=
∑
−
=
mm
ff
xI
n
i
i
C
(1)
где f
i
— число вхождений буквы a
i
в х, i Z
n
.
Доказательство. Будем вычислять I
с
(х) как отношение числа благоприятных
исходов к общему числу исходов. Благоприятным является исход, при котором на
выбранных двух позициях в х расположены одинаковые буквы. Общее число
исходов равно, очевидно, С
2
m
. Число благоприятных исходов есть
∑
−
=
1
0
2
m
i
f
i
C , (2)
В самом деле, переупорядочим буквы в х таким образом, чтобы сначала шли
f
a1
букв а
1
затем — f
a2
букв а
2
и т.д.(4):
, (3)
Теперь заметим, что при случайном выборе мест (i и j) в строке х
благоприятными являются следующие исходы:
⎩
⎨
⎧
−
⎩
⎨
⎧
−
⎩
⎨
⎧
−
.........
1.........0
)(
.........
1.........0
)(
.........
1.........0
)(
22
2
11
1
nn
n
aa
mji
a
aa
mji
a
aa
mji
a
В случае (а
1
) мы можем выбрать пару букв а, из набора (3)
2
1a
f
С способами, в случае (а
2
) пару букв а
2
из (3) —
2
2a
f
C способами и т. д.

Страницы