Scientific journal
International Journal of Experimental Education
ISSN 2618–7159
ИФ РИНЦ = 0,425

1 1 1
1
2420 KB

Существует несколько признаков, при которых наблюдается хаотическое поведение системы [1]. В частности, необходимыми условиями являются два классических свойства – топологическая транзитивность и чувствительность к начальным условиям.

Динамическая система ten1.wmf называется хаотической, если выполняются условия:

1. Функция f : X →X топологически транзи­тивна на некотором метрическом множестве ten2.wmf, если для любых открытых множеств ten3.wmf существует ten4.wmf, такое что

ten5.wmf.

2. Функция f чувствительна к начальным условиям, если существует ten6.wmf, такое что для любого ten7.wmf и его окрестности Hx есть ten8.wmf для которого

ten9.wmf.

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

Криптосистемы по своим требованиям похожи на хаотические системы: топологическая транзитивность необходима, с одной стороны, для сохранения состояния криптосистемы в тех пределах, которые допускает носитель информации, а, с другой стороны, для «покрытия» всего пространства состояний шифротекста. Чувствительность к начальным условиям соответствует чувствительности криптосистемы к открытому тексту или семени псевдослучайного генератора.

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

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

ten12.wmf

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

ten13.wmf (1)

или

ten14.wmf (2)

Для каждого k производная ten15.wmf показывает, как быстро изменяется функция f по отношению к возрастанию аргумента с xk до xk+1· Предел равен среднему значению логарифма производной после n итераций и показывает скорость расхождения траекторий в течение дискретного времени п. Положительное значение показателя (λ > 0) есть индикатор хаотического поведения системы.

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

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

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

Взаимосвязь между объектами изучения в теории хаоса и криптографии

Теория хаоса

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

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

Псевдохаотическая система

– нелинейное преобразование

– нелинейное преобразование

– бесконечное число состояний

– конечное число состояний

– бесконечное число итераций

– конечное число итераций

Начальное состояние

Открытый текст

Заключительное состояние

Шифротекст

Начальные условия и параметры

Ключ

Асимптотическая независимость начального и конечного состояний

Запутывание

Чувствительность к начальным условиям и параметрам, смешивание

распыление

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

С точки зрения акцентов и объектов изучения, между криптографией и теорией хаоса существуют фундаментальные различия:

Криптография изучает эффект конечного числа итерационных преобразований (п < ∞), в то время как теория хаоса (непрерывного и дискретного) изучает асимптотическое поведение системы (п → ∞).

Классические хаотические системы представлены некоторым объектом (множеством) фазового пространства, который часто имеет дробную раз мерность (то есть является фракталом). В криптографии используются все возможные комбинации независимых переменных (что делает систему максимально непредсказуемой) и работают с пространствами с целыми размерностями.

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

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