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

Висновки

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