ВУЗ:
Составители:
8
Потребность в математических моделях открытого текста продиктована,
прежде всего, следующими соображениями. Во-первых, даже при отсутствии
ограничений на временные и материальные затраты по выявлению
закономерностей, имеющих место в открытых текстах, нельзя гарантировать того,
что такие свойства указаны с достаточной полнотой. Например, хорошо известно,
что частотные свойства текстов в значительной степени зависят от их характера.
Поэтому при математических исследованиях свойств шифров прибегают к
упрощающему моделированию, в частности, реальный открытый текст заменяется
его моделью, отражающей наиболее важные его свойства. Во-вторых, при
автоматизации методов криптоанализа, связанных с перебором ключей, требуется
"научить" ЭВМ отличать открытый текст от случайной последовательности знаков.
Ясно, что соответствующий критерий может выявить лишь адекватность
последовательности знаков некоторой модели открытого текста.
Один из естественных подходов к моделированию открытых текстов связан с
учетом их частотных характеристик, приближения для которых можно вычислить с
нужной точностью, исследуя тексты достаточной длины. Основанием для такого
подхода является устойчивость частот к -грамм или целых словоформ реальных
языков человеческого общения (то есть отдельных букв, слогов, слов и некоторых
словосочетаний). Основанием для построения модели может служить также и
теоретико-информационный подход, развитый в работах К. Шеннона.
Учет частот 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
,
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
