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

UptoLike

ВУЗ: 

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

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

Рубрика: 

48
............
...
...
...
...
32212
221
21
21
µµµ
µµµ
µ
µ
yyy
yyy
yyy
YYY
++
++
↓↓↓
и обозначим столбцы получившейся таблицы через Y
↓
1
,..., Y
↓
µ
. Если µ это
истинная длина ключевого слова, то каждый столбец Y
↓
i
, i 1, µ, представляет собой
участок открытого текста, зашифрованный простой заменой, определяемой
подстановкой
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−++
−
1...0...21
......210
ssss
nsn
(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) позволяет в большинстве случаев установить точное
значение µ.
Предположим, что на первом этапе мы нашли длину ключевого слова µ.
Рассмотрим теперь вопрос о нахождении самого ключевого слова. Для его
нахождения можно использовать так называемый взаимный индекс совпадения.
Пусть х = (х
]
,...,х
п
),у = (у
1
,...,у
т
)— две строки букв алфавита А. Взаимным
индексом совпадения х и у, обозначаемым МI
с
(х, у), называется вероятность того,
что случайно выбранная буква из х совпадает со случайно выбранной буквой из у.
Пусть f
0
f
1
…f
n
и f
1
0
f
1
1
…f
1
n-1
— числа вхождений букв алфавита в х и у
соответственно.
Теорема. Взаимный индекс совпадения в х и у вычисляется по формуле (эта
теорема доказывается точно так же, как и предыдущая теорема.)
mm
ff
yxMI
n
i
ii
c
′
⋅
⋅
=
∑
−
=
1
0
1
),(
, (6)
Пусть k = (k
1
,..., k
µ
,) — истинное ключевое слово. Попытаемся оценить
индексы MI
c
(Y
↓
i
, Y
↓
j
)
Для этого напомним, что Y
↓
3
является результатом зашифрования фрагмента
открытого текста простой заменой, определяемой подстановкой (5) при некотором s.
Вероятность того, что Y
↓
i
и Y
↓
j
произвольная пара букв равна 0, имеет вид p
n-si
*p
n-sj
(где р
а
— вероятность появления буквы а в открытом тексте); вероятность того, что
обе буквы есть 1, равна p
n-si+1
*p
n-sj+1
и так далее. На основании этого получаем:

Страницы