1 Сравнительный анализ криптографических алгоритмов
Изучению хаотических систем и их возможному применению в криптографии в последние годы уделялось значительное внимание [1-4]. Известно, что хаотические системы характеризуются существенной зависимостью системы от начальных условий, аналогично случайному процессу. Они могут использоваться в ряде функциональных блоков цифровой системы связи: сжатие, шифрование и модуляция.
В начале развития хаотических систем основной целью исследований была разработка схем, в которых единая хаотическая система использовалась как для модуляции, так и для шифрования. Этот подход, в конечном счете, стал разделяться на две различные области исследований: хаотическую модуляцию [5, 6] и хаотическую криптографию [7].
Хаотические отображения и криптографические алгоритмы обладают рядом сходных свойств: чувствительностью к изменению начальных условий и параметров, хаотичным поведением и неустойчивыми периодическими орбитами с длительными периодами. Повторы шифрования криптографического алгоритма могут приводить к путанице алгоритма. Итерация хаотического отображения распространяет начальную область на все фазовое пространство. Параметры хаотического отображения могут представлять ключ алгоритма шифрования. Важное различие между хаосом и криптографией состоит в том, что преобразование кодов шифрования осуществляется на конечных множествах, в то время как хаотические системы имеют числовые значения только в вещественной области. Более того, в настоящее время понятия криптографической безопасности и производительности криптографических алгоритмов не имеют никакого отношения к теории хаоса.
Криптография общепризнана как лучший метод защиты данных от пассивного и активного мошенничества [8].
Анализируя ряд источников [1-7] возможно детально установить взаимосвязь между хаосом и криптографией, которая представлена в таблице 1.
Таблица 1 Сравнение свойств хаоса и криптографии
Хаотическое свойство Криптографическое свойство Описание
Эргодичность Распространение с небольшим изменением открытого текста или секретного ключа Выход имеет такое же распределение для любого входного сигнала
Чувствительность к начальным условиям/ контрольный параметр свойства смешивания Распространение с небольшим изменением в одном простом блоке всего открытого текста Небольшое отклонение на входе может вызвать большие изменения на выходе
Детермированная динамика Детермированная случайность Небольшое отклонение в локальной области может вызвать большие изменения во всем пространстве
Сложность структуры Сложность алгоритма (атаки) Простой процесс имеет очень высокую сложность
Несмотря на представленные в таблице 1 данные, тесная связь между хаосом и криптографией в полной мере не установлена. Приведем основные сходства и различия между хаотическими системами и криптографическими алгоритмами, также обобщим сходства и различия между хаотическими отображениями и криптографическими алгоритмами, которые представлены в таблице 2.
Алгоритмы шифрования Хаотическая система
Фазовое пространство: конечный набор целых чисел Фазовое пространство: (суб) множества действительных чисел
Алгебраический метод Аналитический метод
Циклический Интеграционный
Ключ (логический)- дискретное пространство ключей Параметры (реальные) – непрерывное пространство ключей
Рассеянный Чувствительность к изменению в исходном состоянии / параметрах
Цифровые реализации с помощью целочисленной арифметики Цифровая реализация нецелочисленной арифметикой, приближающей непрерывные системы непрерывных значений
Безопасность и производительность ?
Приведем краткое описание трех типов криптографических объектов и их хаотической реализации. Три наиболее распространенных криптографических алгоритма: алгоритмы блочного шифрования (алгоритмы с закрытым ключом), генераторы псевдослучайных чисел (аддитивные потоковые шифры) и алгоритмы с открытым ключом.
Блочные шифры преобразуют строку (обычно 64, 128 или 256 бит) в строку той же длины под управлением, так называемого секретного ключа. В научной литературе [10, 13] предложено несколько блочных шифров, основанных на хаотических отображениях, в которых дискретизация (процесс, описывающий способ реализации хаотического отображения в компьютере) не реализуется путем округления хаотического отображения в соответствии с компьютерной арифметикой, а строится в явном виде. В работе [9] предложены криптографические системы, основанные на хаотических перестановках, построенных путем явной дискретизации двумерной карты Бейкера. В работе [10] представлены способы хаотической перестановки на любых размерах двумерных решеток. Эти перестановки удобны в связи с тем, что используют расширяющее свойства двумерной решетки вдоль одной оси, технически избегая сжимающегося свойства двумерной решетки вдоль другой оси. Авторы работы [11] использовали для построения класса алгоритмов блочного шифрования два известных хаотических отображения: экспоненциальное и логистическое. В [12] они аналитически вывели нижнюю границу ряда активных S-блоков в своих алгоритмах, вычислили верхние границы для дифференциальных и линейных вероятностей и, следовательно, доказали устойчивость предложенных алгоритмов к дифференциальным и линейным атакам. В работе [13] предложен программно-базовый подход криптографии на основе хаоса. Такой подход не имеет дрейфа параметров, устойчив и не склонен к изменению динамики, то есть фактически не уязвим для атак. Динамика систем скрыта при помощи складывания траекторий, результаты которого показывают, что процессы шифрования, и дешифрования имеют хорошее быстродействие.
Генератор псевдослучайных чисел - это детерминированный метод, в котором возможно получить из небольшого набора случайных чисел, большой набор случайных чисел, называемых псевдослучайными. Например, в работе [14] авторы предложили хаотический псевдослучайный генератор чисел. Они численно наблюдали, что средние длины циклов и переходных процессов растут экспоненциально с увеличением точности реализации, и из этого факта приняли, что с помощью высокоточной арифметики можно получить генераторы псевдослучайных чисел (ГПСЧ). Статистические свойства бинарных последовательностей, порожденных классом эргодических отображений с некоторыми симметричными свойствами, обсуждены в работе [15]. Авторы вывели достаточное условие, чтобы получить последовательность независимых и одинаково распределенных двоичных случайных величин. Однако авторы не обсуждали реализацию этих отображений на конечных автоматах и последствия, которые эта реализация может иметь для случайных генерируемых последовательностей. В работе [16] авторы предложили класс генераторов псевдослучайных битов на основе хаоса. Некоторые методы в криптографии требуют использования генератора случайных чисел (ГСЧ), представляющего собой устройство, которое выдает последовательность статистически независимых и несмещенных чисел. Работы [18, 19] посвящены анализу применения хаотичного кусочно-линейного одномерного отображения в качестве ГСЧ. Кусочно-линейное отображение позволяет математически находить значения параметров, для которых генерирующая последовательность является Марковским и ГСЧ ведет себя как Марковский источник информации, а затем математически анализируют процесс генерации информации.
Алгоритмы с открытым ключом [8], также называемые асимметричными алгоритмами, разработаны таким образом, что:
1. ключ шифрования отличается от ключа дешифрования;
2. ключ шифрования можно сделать открытым;
3. ключ расшифровки не может быть вычислен из ключа шифрования.
Существует множество алгоритмов с открытым ключом, из которых три наиболее широко применяются в современных криптосистемах: RSA, ElGamal и Rabin [8].
Представителями отечественных криптосистем является ПСКЗИ ШИПКА - представляет собой специализированное мобильное устройство, позволяющее надежно выполнять криптографические преобразования и хранить ключи (рис. 1). Во всех устройствах семейства ШИПКА реализованы все российские криптографические алгоритмы. В них также реализована возможность поддержки зарубежных криптографических алгоритмов. Набор зарубежных алгоритмов для всех устройств одинаков: электронная цифровая подпись - RSA.
Рис. 1 – ПСКЗИ «ШИПКА»
Изделие КРИПТОН-10/PCI-E (рис. 2) предназначено для обеспечения защиты информации, содержащей сведения, составляющие государственную тайну со степенью секретности до «совершенно секретно» включительно, путём криптографического преобразования данных, представленных в виде файлов или областей памяти.
Проведем исследование алгоритма шифрования с открытым ключом при использовании отображения Чебышева, определяемого на множестве [-1, 1], и реализуемого с использованием плавающей запятой.
Рис. 2 - КРИПТОН-10/PCI-E
Алгоритмы ElGamal-подобные и RSA-подобные с использованием отображения Чебышева, представлены в [20]. В этом случае анализ периодических орбит в последовательностях целых чисел, порожденных отображениями Чебышева, основан на арифметических свойствах торических автоморфизмов, другого известного класса хаотических отображений. Этот вид хаотической криптографии наиболее безопасен и практичен, и может использоваться как для шифрования, так и для электронной цифровой подписи.
Таким образом, несмотря на огромное количество работ, опубликованных в области криптографии на основе хаоса, существенного влияния на традиционную криптографию не оказало. Это может быть связано с двумя причинами:
- во-первых, почти все криптографические алгоритмы, основанные на хаосе, используют динамические системы, определенные на множестве вещественных чисел, и поэтому трудны для практической реализации и схемотехнической реализации.
- во-вторых, безопасность и производительность почти всех предлагаемых методов, основанных на хаосе, не анализируются с точки зрения методов, разработанных в криптографии. Более того, большинство изученных методов обеспечивают функционирование небезопасных и ресурсоемких алгоритмов.
2 Анализ методов шифрования с открытым ключом
Анализируя системы шифрования с открытым ключом [8] допустим, что объект А имеет открытый ключ e и соответствующий закрытый ключ d. В защищенных системах задача вычисления d, заданного e, вычислительно невыполнима. Открытый ключ определяется преобразованием шифра Ee, в то время как закрытый ключ определяет связанное преобразование дешифровки Dd. Объект Б, отправляет сообщение m объекту А, получает подлинную копию открытого ключа e объекта А, используя преобразования шифра для получения шифра текста c = Ee(m) и передает c объекту А. Для расшифровки c объект А применяет преобразование дешифровки, чтобы получить исходное сообщение M = Dd (c).
В настоящее время предложены многочисленные алгоритмы с открытым ключом; три наиболее широко используемые криптосистемы с открытым ключом: RSA, ElGamal и Rabin. Безопасность системы RSA основана на неразрешимости задачи целочисленной факторизации. В схеме шифрования с открытым ключом Rabin проблема, с которой сталкивается противник, вычислительно эквивалентна факторингу. Безопасность системы открытого ключа ElGamal основана на неразрешимости задачи дискретного логарифма. Схемы шифрования с открытым ключом обычно значительно медленнее алгоритмов шифрования с симметричным ключом. По этой причине шифрование с открытым ключом наиболее часто используется в устройствах для шифрования небольших объемов данных и для передачи ключей, которые впоследствии используются для шифрования данных с помощью алгоритмов симметричного ключа.
Алгоритм открытого ключа ElGamal можно рассматривать как класс функций, определяемых как ?(x)=xp (mod N), где N ? простое число, x - источник мультипликативной группы Z?N, и 1? p ?N - 2. Любые две функции ? и ?q коммутируют по составу:
?p (?q (x)) = ?pq (x) (1)
Протокол соглашения о ключах описывает, как объект А и объект Б договариваются о своем общем секретном ключе. Объект А генерирует число p, вычисляет y= ?(x) и посылает (x, y) объекту Б. Объект Б создает число q, вычисляет z = ?q(x) и посылает z объекту А. Секретный ключ, который может быть общим как для объекта А, так и для объекта Б, вычисляется следующим образом: объект А вычисляет секретный ключ k как k = ?(z); объект Б вычисляет секретный ключ k как k = ?q (y).
В алгоритме ElGamal с открытым ключом объект А генерирует большое простое число N и формирует x мультипликативных групп Z?N состоящих из целых чисел взятых по модулю N. Объект А также генерирует случайное целое число s ? N-2 и вычисляет A = xs (modN). Открытый ключ объекта А - (x, N, A); закрытый ключ объекта А - s. Чтобы зашифровать сообщение m, объект Б выбирает случайное число r?N?2, вычисляет B= Хr(modN) и X = mAr(modN), и отправляет шифрованный текст с =(B, X) для объекта А. Чтобы восстановить сообщение m из c, объект А использует закрытый ключ s для восстановления m, вычисляя m=B-sX (modN). Расшифровка позволяет восстановить исходное сообщение, поскольку B-smAr ?x-rsmxrs ?m (mod N).
