Контрольні питання
Висновки
Пример 1.3
Пример 1.2
Пример 1.1
Источник открытых текстов (Алиса на рис. 1.1) генерирует отдельные буквы (1-граммы) из с независимыми, но идентичными (по отношению к моментам появления) вероятностями . Таким образом,
.
Вероятности появления букв алфавита в обычных английских текстах приведено в табл. 1.1.
Таблица 1.1. Распределение вероятностей 1-грамм в английском языке.
В этой модели
.
Заметим, что в этой модели также и т.д, т.е. все перестановки трех букв , и равновероятны, что неправдоподобно для обычных английских текстов.
порождает 2-граммы над алфавитом с независимыми, но идентичными распределениями , где . Таким образом, для
Конечно, можно продолжать подобным же образом с таблицами распределения 3-грамм и т.д. Иной, более привлекательный подход дается в следующем примере.
В этой модели источник открытых текстов генерирует 1-граммы посредством Марковской цепи с конечным числом состояний. Этот процесс можно описать матрицей переходов , где — вероятность того, что вслед за буквой в тексте следует буква . Из теории марковских процессов вытекает, что имеет собственное значение 1. Пусть ‑ соответствующий собственный вектор, называемый равновесным (стационарным) распределением процесса. Предполагая, что процесс с самого начала находится в равновесном (стационарном) состоянии, получаем
Пусть и заданы таблицами 1.2 и 1.3 (из [3]; здесь они обозначены посредством "ed" и "ТrРr"). Тогда получаются следующие более правдоподобные вероятности:
Таблица 1.2. Равновероятное распределение букв в английском языке.
Таблица 1.3. Вероятности переходов в английском языке , – столбец, – строка.
С помощью функций StringTake, ToCharacterCode и StringLength пакета "Mathematica" эти вероятности могут быть вычислены следующим способом (сначала вводятся таблицы 1.2 и 1.3):
sourcetext = "run";
ed[StringTake[sourcetext, {1}]] *
StringLength[sourcetext] - 1
ToCharacterCode[StringTake[sourcetext, {i}]] - 96,
ToCharacterCode[StringTake[sourcetext, {i +1}]] - 96]]
|| {{0.000218448}}
Можно получить лучшие аппроксимации языка, если считать вероятности переходов зависящими от более чем одной предшествующей буквы.
Отметим, что во всех трех рассмотренных примерах модели стационарны, т.е.
не зависит от значения . Можно считать, что в середине обычного текста это свойство выполняется, но в иных ситуациях это не так. Подумайте, например, о дате в начале письма.
1. Як можна класифікувати алгоритми шифрування?
2. Як Шеннон представляв загальну схему симетричної криптосистеми?
3. Як визначається симетрична криптосистема через поняття мови і тексту?
4. Що таке криптоаналіз і які існують типи криптоаналітичного розкриття?
5. У чому суть криптоаналізу з використанням тільки шифротексту і тільки відкритого тексту?
6. У чому суть криптоаналізу з використанням обраного відкритого тексту і з використанням адаптивного розкриття з наявним відкритим текстом?
7. У чому суть криптоаналізу з використанням обраного шифротексту і з використанням вибраного ключа?
8. У чому сенс безпеки алгоритмів шифрування?
9. Як можна описати джерело відкритих текстів у статистичному сенсі?