Контрольні питання

Висновки

Пример 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. Як можна описати джерело відкритих текстів у статистичному сенсі?

Дата добавления: 2013-12-12