УДК 004.056.55 Ó ,,,, 2011
ДЕТЕРМИНИРОВАННЫЙ ХАОС И КРИПТОГРАФИЯ
, ст. преподаватель,
, к. т.н., профессор,
, доцент,
, ст. преподаватель.
Карагандинский государственный технический университет
Рассмотрена взаимосвязь криптографических систем и хаотической динамики. Показаны, какие фундаментальные различия существуют между криптографией и теорией хаоса. Представлены алгоритмы шифрования с точки зрения нелинейной динамики. Известные свойства хаотических систем можно использовать в криптографии при разработке новых схем шифрования.
Ключевые слова: детерминированный, хаос, хаотическая система, криптосистема, криптография, шифрование, запутывание, распыление,
Криптографическую систему можно отнести к нелинейным системам с обратной связью, когда информация с выхода системы подается на вход и становится следующим набором входных данных.
Рисунок 1 - Схема криптографической системы
Т. к. на сегодняшний день алгоритмы шифрования известны, то криптостойкость шифра определяется длиной ключа, т. к. единственный путь вскрытия зашифрованной информации - перебор комбинаций ключа и выполнение алгоритма расшифрования. Таким образом, время и средства, затрачиваемые на криптоанализ, зависят от длины ключа и сложности алгоритма шифрования.
Как известно, различают два класса криптосистем. В симметричной криптосистеме используется один и тот же ключ для шифрования и расшифровки сообщения. Смысл симметричного шифрования состоит в многократном рассеивании и перемешивании исходных данных. После определенного числа раундов (в алгоритме DES - 16, в алгоритме ГОСТ 28147-89 – 32) проводится конечная перестановка, полученный после этого результат становится блоком шифртекста.
Принципиальное отличие асимметричной криптосистемы от криптосистемы симметричного шифрования состоит в том, что для шифрования информации и ее последующего расшифрования используются различные ключи.
Отметим характерные особенности асимметричных криптосистем:
1. Открытый ключ и криптосистему С можно отправлять по незащищенным каналам, т. е. злоумышленнику они могут быть известны.
2. Алгоритмы шифрования и расшифрования
EB : M → C;
DB : C → M являются открытыми.
У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы [1]:
1. Вычисление пары ключей (KB, kB) получателем на основе начального условия должно быть простым.
2. Отправитель A, зная открытый ключ KB и сообщение M, может легко вычислить криптограмму: 
.
3. Получатель B, используя секретный ключ kB и криптограмму С, может легко восстановить исходное сообщение: 
.
4. Злоумышленник, зная открытый ключ KB, при попытке вычислить секретный ключ kB наталкивается на непреодолимую вычислительную проблему.
5. Злоумышленник, зная пару (KB, С) при попытке вычислить исходное сообщение M наталкивается на непреодолимую вычислительную проблему.
Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Криптосистемы с открытыми ключами различаются видом односторонних функций. Среди них самыми известными являются системы RSA, Эль-Гамаля и Мак-Элиса.
Алгоритмы шифрования можно рассматривать с точки зрения нелинейной динамики:
1. Шифрование блочного алгоритма осуществляется путем n-кратного применения некоторой итерационной функции f . Число n фиксировано и невелико. Каждая итерация переводит криптосистему в следующее состояние, т. е. xi+1 = f (xi). Начальному состоянию присваивается открытый текст (xо = p), а заключительное состояние принимается за шифротекст (c = xn).
2. Потоковые схемы более разновидны с точки зрения использования траектории. Их отличительной чертой является то, что весь шифротекст «связан» одной траекторией, т. е. шифрование порции открытого текста зависит от текущего состояния криптосистемы. Число итераций не фиксировано, а зависит от объема исходного текста.
Запутывание и распыление
Динамическая система непрерывного состояния (дискретного времени) может быть задана итерационной функцией [2].
xn+1 = f (xn, k), 
, n = 0,1,2,... (1)
где xi - дискретные состояния системы. Траектория j(i, x0) представляет собой последовательность x0,x1,x2, ... Легко заметить, что выражение (1) описывает криптографическую итерационную функцию, используемую в псевдослучайных генераторах, блочных шифрах и др. В динамической и в криптографической системах используют итерационное преобразование информации, зависящее от параметра.
Согласно Шеннону, необходимо использовать две базовые техники для скрытия избыточности исходного текста:
- запутывание предполагает, что статистические свойства открытого текста не заметны в шифротексте. Для всякого наблюдателя шифротекст должен казаться случайным, т. е. быть псевдослучайным.
- распыление:
1) для текста распыление предполагает, что статистически похожие последовательности текста преобразуются в совершенно различные последовательности шифротекста (при шифровании одним и тем же ключом). Другими словами, любой элемент открытого текста должен влиять на все элементы шифротекста сложным непредсказуемом образом. Так, изменение одного бита сообщения должно приводить к изменению половины битов шифротекста.
2) для ключа распыление предполагает, что похожие ключи преобразуют текст в совершенно разные шифротексты. Аналогично, каждый бит ключа должен влиять на каждый бит шифротекста сложным непредсказуемым образом.
Этот подход используется в симметричных блочных шифрах. Итерационная функция обычного блочного алгоритма включает фазы подстановки (запутывание) и перемешивания (распыление). В конечном счете, оба свойства обеспечивают псевдослучайность шифротекста для любого текста и любого ключа. Перемешивания является эффективным средством усиления нелинейности итерационной функции криптосистемы.
Хаотическая система
Выделено несколько признаков, при которых наблюдается хаотическое поведение системы. В частности, необходимым условием являются два классических свойства - топологическая транзитивность и чувствительность к начальным условиям.
Динамическая система áX,fñ называется хаотической, если выполняются условия:
1) Функция f : X → X топологически транзитивна на некотором метрическом множестве XÎRd, если для любых открытых множеств U, V Ì X существует n ³ 0, такое что fn(U) ÇV ¹ 0.
2) Функция f чувствительна к начальным условиям, если существует δ > 0, n ³ 0, такое что для любого x Î X и его окрестности Hx есть y Î Hx для которого êfn(x) - fn(y) ê > δ.
Другими словами, динамическая системы называется хаотической, если все ее траектории ограничены, но быстро расходятся в каждой точке фазового пространства (рисунок 4).
Рисунок 4 - Двумерная хаотическая система:
(а) временное пространство; (b) фазовое пространство.
Криптосистемы по своим требованиям похожи на хаотические системы: топологическая транзитивность необходима, с одной стороны, для сохранения состояния криптосистемы в тех пределах, которые допускает носитель информации, с другой стороны, для «покрытия» всего пространства состояний шифротекста. Чувствительность к начальным условиям соответствует чувствительности криптосистемы к открытом тексту или семени псевдослучайного генератора. Таким образом, и в теории хаоса, и в криптографии мы имеем дело с системами, в которых небольшое изменение начальных условий приводит к существенным изменениям во всей траектории.
Взаимосвязь криптографии и хаотической динамики
Традиционные криптосистемы (схемы шифрования, псевдослучайные генераторы) можно рассматривать как динамические системы, осуществляющие преобразования информации (таблица 1).
Таблица 1 - Взаимосвязь между объектами изучения в теории хаоса и криптографии
Теория хаоса | Криптография |
Хаотическая система | Псевдохаотическая система |
- нелинейное преобразование | - нелинейное преобразование |
- бесконечное число состояний | - конечное число состояний |
- бесконечное число итераций | - конечное число итераций |
Начальное состояние | Открытый текст |
Заключительное состояние | Шифротекст |
Начальные условия и параметры | Ключ |
Асимптотическая независимость начального и конечного состояний | Запутывание |
Чувствительность к начальным условиям и параметрам, смешивание | распыление |
Известные свойства хаотических систем (экспоненциальное расхождение траекторий, эргодичность, смешивание) могут оказаться полезными в криптографии при разработке новых схем шифрования.
Однако между криптографией и теорией хаоса существуют фундаментальные различия [2]:
1. Криптография изучает эффект конечного числа итерационных преобразований (n < ∞), в то время как теория хаоса (непрерывного и дискретного) изучает асимптотическое поведение системы (n →∞).
2. Классические хаотические системы представлены некоторым множеством фазового пространства, которое часто имеет дробную размерность (т. е. является фракталом). В криптографии, используют все возможные комбинации независимых переменных и работают с пространствами с целыми размерностями.
3. В компьютерной криптографии рассматриваются системы с конечным числом состояний, а пространство состояний хаотической системы определено на бесконечном множестве непрерывных или дискретных значений. Таким образом, все модели хаоса, реализованные на компьютере являются приближенными.
Криптосистема является идеально безопасной только в том случае, если все ее возможные состояния равновероятны и не зависят от предыдущих состояний, т. е., последовательность состояний характеризуется равномерным законом распределения вероятности и не имеет корреляций.
Многомерные хаотические системы не могут использоваться в шифровании, так как они не репродуцируемы. С другой стороны, генерация ключей (без возможности повтора) при помощи «естественного» хаоса (например, термальный шум в системно блоке компьютера) широко используется уже сегодня.
Детерминированный хаос, который можно применить в шифровании, имеет малую размерность и бесчисленное множество состояний. Детерминированный хаос может порождать алгоритмически случайные последовательности. Более того, в смешивающей системе, выборка xn, xn+k, xn+2k, xn+3k …· является асимптотически (k→∞) случайной, то есть с увеличением k члены выборки будут все менее зависимы [3].
ЛИТЕРАТУРА
1 Хеллмэн и имитостойкость: Введение в криптографию //ТИИЭР. 1979. Т. 67. № 3. - С. 71-109.
2 Приложение теории детерминированного хаоса в криптографии – М.: МГТУ им. , 2002.
3 , Тайлак порождения детерминированного хаоса и криптографическая система защиты информации в компьютерных сетях //Труды университета. КарГТУ, 2009 г. - С. 72-75.
қ, , . Детерминироваланғаң хаос және криптография.
Криптографиялық жүйелер және хаотикалык динамиканың өзара байланыстары қарастырылады, сонымен қатар хаос теориясының және криптография арасында қандай фундаментальды айырмашылықтар бар екендігі көрсетілген. Шифрлау алгоритмдері сызықтық емес динамика жағының қарастырылған. Хаотикалық жүйелердің түрлі-түсті қасиеттерін жаңа шифрлеу схемаларын өңдеу кезінде криптографияда қолдануға болады.
B.E.Tailak, G. D. Kogai, N. I.Tomilova, B. M.Sadanova. Deterministic chaos and cryptography.
The interrelation of cryptographic systems and chaotic dynamics are considered. What fundamental distinctions exist between cryptography and the theory of chaos also are shown. Encryption algorithms are presented in terms of nonlinear dynamics. Known properties of chaotic systems can be used in cryptography by development of new schemes of enciphering.
СВЕДЕНИЯ ОБ АВТОРАХ:
Тайлақ Бибігүл Елжасқызы – старший преподаватель кафедры «Вычислительная техника и программное обеспечение» КарГТУ. Выпускница Карагандинского государственного политехнического института - в 1994 г. закончила по специальности «Автоматизированные системы обработки информации и управления». Опубликовала более 10 научных статей в области информационных и компьютерных технологий, защиты информации.
– зав. кафедрой «Вычислительная техника и программное обеспечение» КарГТУ, кандидат технических наук, профессор, член-корреспондент Международной Академии информатизации Казахстана. Имеет более 160 печатных трудов, в том числе монографии, учебные пособия, электронные учебники, слайд-лекции, видео-лекции, мультимедийные презентации. Научные направления: компьютерные технологии, область информатизации и автоматизации информационных систем, инновационные, информационные и IT технологии.
– кандидат технических наук, доцент кафедры «Вычислительная техника и программное обеспечение» КарГТУ. Область научных интересов: информационные технологии в области энергетики. В соавторстве были разработаны и изданы более 30 научных и учебно-методических работ.
Саданова Бакытгуль Маратовна – старший преподаватель кафедры «Вычислительная техника и программное обеспечение» КарГТУ. В 1992 году с отличием закончила КПТИ по специальности «Автоматизированные системы обработки информации и управления». Автор 3 монографий, а также более 20 научных и учебно-методических работ. Область научных интересов – разработка интеллектуальных систем на основе семантических Web-технологий.
