ВУЗ:
Составители:
39
достаточной полнотой. Например, хорошо известно, что частотные свойства
текстов в значительной степени зависят от их характера. Поэтому при
математических исследованиях свойств шифров прибегают к упрощающему
моделированию, в частности, реальный открытый текст заменяется его
моделью, отражающей наиболее важные его свойства. Во-вторых, при
автоматизации методов криптоанализа, связанных с перебором ключей,
требуется "научить" ЭВМ отличать открытый текст от случайной по-
следовательности знаков. Ясно, что соответствующий критерий может
выявить лишь адекватность последовательности знаков некоторой модели
открытого текста.
Один из естественных подходов к моделированию открытых текстов
связан с учетом их частотных характеристик, приближения для которых
можно вычислить с нужной точностью, исследуя тексты достаточной длины.
Основанием для такого подхода является устойчивость частот к -грамм или
целых словоформ реальных языков человеческого общения (то есть
отдельных букв, слогов, слов и некоторых словосочетаний). Основанием для
построения модели может служить также и теоретико-информационный
подход, развитый в работах К. Шеннона.
Учет частот k-грамм приводит к следующей модели открытого текста.
Пусть Р
(k)
(А) представляет собой массив, состоящий из приближений для
вероятностей р(b
1
,b
2
,...,b
k
) появления k-грамм b
1
b
г
...b
k
в открытом тексте,
k∈N,
А = (а
1
,...,а
п
) — алфавит открытого текста, b
i
∈
A, i = 1,k.
Тогда источник "открытого текста" генерирует последовательность
с
1
,с
2
,...,с
k
,с
k+1
,... знаков алфавита А, в которой k-грамма с
1
с
2
...с
k
появляется с
вероятностью р(с
1
с
2
...с
k
) е Р
(k)
(А), следующая k-грамма с
1
с
2
...с
k+1
появляется с
вероятность р(с
2
с
3
...с
k+1
)∈Р
(k)
(А) и т. д. Назовем построенную модель
открытого текста вероятностной моделью k-го приближения.
Таким образом, простейшая модель открытого текста -вероятностная
модель первого приближения – представляет собой последовательность
знаков с
1
,с
2
,..., в которой каждый знак ci, i = 1,2,..., появляется с
вероятностью р(с
i
)
∈
P
(1)
(A), независимо от других знаков. Будем называть
также эту модель позначной моделью открытого текста. В такой модели
открытый текст с
1
с
2
...с
1
имеет вероятность
∏
=
=
l
i
il
cpcccp
1
21
)()...( .
В вероятностной модели второго приближения первый знак с
1
имеет
вероятность р(с
1)
∈
P
(1)
(A), а каждый следующий знак с
i
зависит от
предыдущего и появляется с вероятностью
)(
)(
)/(
1
1
1
−
−
−
=
i
i
ii
cp
ccp
ccp
,
где р(с
i-1
с
i
)
∈
Р
(2)
(А), р(с
i-1
)
∈
Р
(1)
(A), i = 2,3,.... Другими словами, модель
открытого текста второго приближения представляет собой простую
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
