Математические модели открытых текстов

Потребность в математических моделях открытого текста продиктована, прежде всего, следующими соображениями. Во-первых, даже при отсутствии ограничений на временные и материальные затраты по выявлению закономерностей, имеющих место в открытых текстах, нельзя гарантировать того, что такие свойства указаны с достаточной полнотой. Например, хорошо известно, что частотные свойства текстов в значительной степени зависят от их характера. Поэтому при математических исследованиях свойств шифров прибегают к упрощающему моделированию, в частности, реальный открытый текст заменяется его моделью, отражающей наиболее важные его свойства. Во-вторых, при автоматизации методов криптоанализа, связанных с перебором ключей, требуется “научить” ЭВМ отличать открытый текст от случайной последовательности знаков. Ясно, что соответствующий критерий может выявить лишь адекватность последовательности знаков некоторой модели открытого текста.

Один из естественных подходов к моделированию открытых текстов связан с учетом их частотных характеристик, приближения для которых можно вычислить с нужной точностью, исследуя тексты достаточной длины (см. Приложение1). Основанием для такого подхода является устойчивость частот -грамм или целых словоформ реальных языков человеческого общения (то есть отдельных букв, слогов, слов и некоторых словосочетаний). Основанием для построения модели может служить также и теоретико-информационный подход, развитый в работах К.Шеннона [Шен63].

Учет частот -грамм приводит к следующей модели открытого текста. Пусть представляет собой массив, состоящий из приближений для вероятностей появления -грамм в открытом тексте, , — алфавит открытого текста, Тогда источник “открытого текста” генерирует последовательность знаков алфавита , в которой -грамма появляется с вероятностью , следующая -грамма появляется с вероятность и т. д. Назовем построенную модель открытого текста вероятностной моделью -го приближения.

Таким образом, простейшая модель открытого текста – вероятностная модель первого приближения – представляет собой последовательность знаков , в которой каждый знак появляется с вероятностью , независимо от других знаков. Будем называть также эту модель позначной моделью открытого текста. В такой модели открытый текст имеет вероятность

.

В вероятностной модели второго приближения первый знак имеет вероятность , а каждый следующий знак зависит от предыдущего и появляется с вероятностью

,

где , . Другими словами, модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст имеет вероятность

.

Модели открытого текста более высоких приближений учитывают зависимость каждого знака от большего числа предыдущих знаков. Ясно, что чем выше степень приближения, тем более “читаемыми” являются соответствующие модели. Проводились эксперименты по моделированию открытых текстов с помощью ЭВМ.

Шифр замены

Шифр замены, каждая очередная шифрвеличина при преобразовании заменяется некоторым своим образом - шифробозначением.

Пример: Шифр Цезаря в котором каждая буква заменялась третьей последующей буквой латинского алфавита (с учетом циклического сдвига). Слово COMPUTER имело бы вид FRPSXWHU. Шифр Цезаря можно описать математически:

у = (х + k) mod 26, k = const,

где х,у - номера букв в латинском алфавите из 26 букв; k – ключ. Усложнением шифра Цезаря является моноалфавитная подстановка (шифр простой замены). Здесь каждая буква текста заменяется другой буквой по фиксированному правилу. Ключом является матрица перестановки, содержащая единственную единицу в каждой строке и каждом столбце, остальные элементы - нулевые, и действующая на множестве букв входного алфавита. При этом шифр Цезаря является частным случаем моноалфавитной подстановки, ключевая матрица является матрицей сдвига.

Существенной характеристикой преобразования является вид отображения шифрвеличин на шифробозначение.

Возможно четыре случая:

1. Взаимоодназначные отображения, когда каждой шифрвеличине придается ровно одно шифробозначение и обратно, каждому шифробоз­начению соответствует только одна шифрвеличина. Шифры замены такого типа называются шифрами простой замены.

2. Шифры, неоднозначные по зашифрованию, если каждой шифрвели­чине соответствуют несколько шифробозначений, но любое шифробозна­чение скрывает за собой одну шифрвеличину.

3. отдельные шифро­бозначения скрывают за собой одну из нескольких величин, то есть шифры неоднозначные по расшифрованию. При расшифровании нужная шифрвеличина подбирается по смыслу или с использованием дополни­тельных шифробозначений.

4. Наиболее сложный вид отображения - взаимонеоднознач­ное. Каждой шифрвеличине соответствует несколько шифробозначений и обратно, под данным шифробозначением могут скрываться различные шифрвеличины (в зависимости от ключевых установок) Большинство современных шифров строится именно по этому принципу.

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