Магистрант Пустовар Н. В.

Магистрант Мусин Р. А.

Евразийский национальный университет им. Л.Н. Гумилева, г. Астана

Хаос и Криптография

Прошедшее десятилетие ознаменовалось чрезвычайным интересом к возможности использования динамического хаоса для шифрования данных. Это обуславливается тем, что уже на концептуальном уровне между хаотическими и криптографическими системами имеется взаимосвязь. И в криптографии, и в нелинейной динамике осуществляется нелинейное преобразование информации. С одной стороны, это преобразование детерминировано (например, выполняется компьютером), с другой стороны, оно должно быть практически непредсказуемым для внешнего наблюдателя. Таким образом, словосочетание "детерминированный хаос" вполне "подходит" для криптографии.

Помимо концептуальной взаимосвязи, можно отметить, что и на практическом уровне криптографические и хаотические системы тоже похожи. Так, уже в классических работах К. Шеннона, написанных почти за 15 лет до обнаружения хаоса, можно найти упоминание об этом. Например, хотя он и не произносит слово "хаос" в работе, он предлагает перемешивающие, сохраняющие меру преобразования, зависящие от аргумента очень "чувствительным" образом и явно упоминает базовый механизм образования хаоса через растяжение и складывание:

"Хорошие перемешивающие преобразования часто достигаются путем повторения двух простых некоммутируемых операций. Хопф показал, например, что тесто может быть перемешано следующей последовательностью операций. Вначале оно раскатывается в тонкий слой, затем скатывается, затем снова раскатывается и скатывается и т.д.

При хорошем перемешивающем преобразовании функции усложняются за счет повышения чувствительности всех переменных. Небольшое возмущение в любой из них приводит к значительному изменению конечного результата".

Рассмотрим более подробно свойства хаотических систем, определяющие взаимосвязь хаоса и криптографии.

Хаотическая система

Исследователями отмечено несколько признаков, при которых наблюдается хаотическое поведение системы. В частности, необходимым условием являются два классических свойства - топологическая транзитивность и чувствительность к начальным условиям.

Определение 1. Динамическая система называется хаотической, если выполняются следующие условия:

1) Функция топологически транзитивна на некотором метрическом множестве . Т.е. для любых открытых множеств существует такое, что

.

2) Функция чувствительна к начальным условиям. Т.е. существует такие, что для любого и его окрестности найдется , для которого

.

Другими словами, динамическая система называется хаотической, если все ее траектории ограничены, но быстро расходятся в каждой точке фазового пространства.

Требования, предъявляемые шифрсистемам, похожи на условия, необходимые для хаотичности динамических систем. Топологическая транзитивность, с одной стороны, нужна для сохранения состояния шифрсистемы в тех пределах, которые допускает носитель информации, а, с другой стороны, для покрытия всего пространства состояний шифртекста. Чувствительность к начальным условиям соответствует чувствительности к открытому тексту или/и ключу.

Таким образом, и в теории хаоса, и в криптографии мы имеем дело с системами, в которых небольшое изменение начальных условий приводит к существенным изменениям во всей траектории.

Показатель Ляпунова

В определении хаотической системы было введено понятие чувствительности к начальным условиям. Показатель Ляпунова , определяемый для каждой точки , является мерой чувствительности, т. е. характеризует скорость экспоненциального разбегания траекторий траекторий, находящихся в окрестности . Для одномерной системы

где - небольшое отклонение от начального состояния , и - число итераций (дискретное время). В общем случае, зависит от начальных условий , поэтому определяют усредненное значение. Для систем, сохраняющих меру, остается постоянным для всех траекторий. Практически, показатель Ляпунова можно вычислить как предел

(1)

или

(2)

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

Для - мерного системы мы имеем набор и более сложное поведение, которое качественно не отличается от одномерного случая.

С позиции криптографии, показатель Ляпунова является мерой криптографической эффективности системы. Чем больше , тем меньше итераций требуется для достижения заданной степени распыления и перемешивания информации.

СПИСОК ЛИТЕРАТУРЫ

1. Дмитриев А.С. Прикладной динамический хаос: Курс лекций. Ч. И. Ярославль. ЯрГУ. 2000.

2. Дмитриев А.С. Динамический хаос как носитель информации. Новое в синергетике: Взгляд в третье тысячелетие // М.: Наука (Информатика: неограниченные возможности и возможные ограничения). 2002. с. 82.

3. Золотарев В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и
алгоритмы: Справочник. / Под ред. чл.-кор. РАИ Ю.Б.Зубарева. - М.: Горячая линия - Телеком, 2004. -126с.

4. Чмора А.Л. Современная прикладная криптография // М.: Гелиос АРВ, 2001.256 с.