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

UptoLike

ВУЗ: 

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

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

Рубрика: 

9
где р(с
i-1
с
i
) ∈Р
(2)
(А), р(с
i-1
)
∈
Р
(1)
(A), i = 2,3,.... Другими словами, модель
открытого текста второго приближения представляет собой простую однородную
цепь Маркова. В такой модели открытый текст с
1
с
2
...с
l
имеет вероятность
∏
=
−
⋅=
l
i
iil
ccpcpcccp
2
1121
)/()()...( .
Модели открытого текста более высоких приближений учитывают
зависимость каждого знака от большего числа предыдущих знаков. Ясно, что чем
выше степень приближения, тем более "читаемыми" являются соответствующие мо-
дели. Проводились эксперименты по моделированию открытых текстов с помощью
ЭВМ.
Отметим, что с более общих позиций открытый текст может рассматриваться
как реализация стационарного эргодического случайного процесса с дискретным
временем и конечным числом состояний.
Критерии распознавания открытого текста
Заменив реальный открытый текст его моделью, мы можем теперь построить
критерий распознавания открытого текста. При этом можно воспользоваться либо
стандартными методами различения статистических гипотез, либо наличием в
открытых текстах некоторых запретов, таких, например, как биграмма ЪЪ в русском
тексте. Проиллюстрируем первый подход при распознавании позначной модели
открытого текста.
Итак, согласно нашей договоренности, открытый текст представляет собой
реализацию независимых испытаний случайной величины, значениями которой
являются буквы алфавита А = {а
1
,...,а
п
}, появляющиеся в соответствии с распре-
делением вероятностей Р
(1)
(А) = (р(а
1
),...,р(а
п
)). Требуется ' определить, является ли
случайная последовательность с
1
с
2
...с
l
букв алфавита А открытым текстом или нет.
Пусть Н
0
— гипотеза, состоящая в том, что данная последовательность —
открытый текст, Н
1
— альтернативная гипотеза. В простейшем случае
последовательность c
1
c
2
...c
l
можно рассматривать при гипотезе Н
1
как случайную и
равновероятную. Эта альтернатива отвечает субъективному представлению о том,
что при расшифровании криптограммы с помощью ложного ключа получается
"бессмысленная" последовательность знаков. В более общем случае можно считать,
что при гипотезе Н1 последовательность c
1
c
2
...c
l
представляет собой реализацию
независимых испытаний некоторой случайной величины, значениями которой
являются буквы алфавита А = {а
1
,...,а
п
}, появляющиеся в соответствии с
распределением вероятностей Q
(1)
(A)= (q(a
l
),...,q(a
n
)). При таких договоренностях
можно применить, например, наиболее мощный критерий различения двух простых
гипотез, который дает лемма Неймана—Пирсона.
В силу своего вероятностного характера такой критерий может совершать
ошибки двух родов. Критерий может принять открытый текст за случайный набор
знаков. Такая ошибка обычно называется ошибкой первого рода, ее вероятность
равна
α
= p{H
1
/H
0
}. Аналогично вводится ошибка второго рода и ее вероятность
β
= p{Н
0
/Н
1
} . Эти ошибки определяют качество работы критерия. В
криптографических исследованиях естественно минимизировать вероятность

Страницы