Фрактальное шифрование

Фрактальное шифрование — метод шифрования, который использует в качестве кодирующей функции фрактальную последовательность.

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

История возникновения

Бенуа Мандельброт в 1970-х годах ввёл термин «фрактал» и в 1975 году создал «Фрактальную геометрию», но он уточнил, что объекты, которые теперь считаются фрактальными, существовали задолго до его описания. Теория фракталов, является активной развивающейся, начиная с 1970-х годов, используется в криптографии и в поиске новых подходов к исследованию объектов самоподобия и нерегулярных явлений. Эта теория имеет множество применений во многих областях, особенно в обработке изображений, фрактал был признан в качестве надёжной технологии, применяемой в различных криптосистемах. Сегодня фрактальные последовательности используются для сжатия различный изображений, так как изображения иногда содержат самоподобные элементы, которые хорошо описываются фрактальными последовательностями. Так же они используются при шифровании изображений, а так же в различных методах идентификации и биометрического шифрования, таких как сканирование отпечатка пальца, сетчатки и радужки глаза, линии руки, лица и другие. Многие страны мира в настоящее время используют биометрическое шифрование в предотвращении преступлений и мошенничества, розыске и криминалистике, учете посещаемости, платежных системах, контроле доступа и контроле безопасности границ. Евклидова геометрия не может объяснить все геометрические структуры, в отличие от фрактальной геометрии. Теория фракталов и её методы предоставляют новый взгляд и новые возможности, которые потенциально могут быть использованы в криптосистемах.

Отличия от обычных методов шифрования

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

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

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

Пример шифрования

Приведём простой пример принципа работы фрактального метода шифрования на чёрно-белых растровых изображениях. Наше исходное изображение представимо в виде прямоугольной матрицы, состоящей из 1, где пиксель чёрного цвета и 0, где он белого цвета. По начальным параметрам и итерационной функции получим изображение фрактала в виде матрицы такого же размера. После этого применим к этим двум матрицам поэлементное сложение по модулю 2 (или любую другую обратимую функцию), в итоге мы получим новую матрицу, которая отправляется по каналу связи. Чтобы расшифровать сообщение, получателю нужно знать итерационную функцию и начальные параметры для построения того же фрактала и далее провести обратную операцию по отношению к операции передающей стороны, в нашем случае это поэлементная сумма по модулю 2. В итоге получится отправленное изображение. В методе фрактального шифрования ключ шифрования генерируется кодирующей функцией, основанной на фрактальной последовательности, и начальными параметрами. Зная фрактальную последовательность и начальные параметры, как отправитель, так и получатель смогут сгенерировать ключ, по которому будет производиться зашифровка и расшифровка сообщения.

Факторы, повышающие стойкость

Стойкость данного метода фрактального шифрования можно повысить с помощью перемешивания последовательности исходного сигнала использую для этого заполняющую пространство кривую (ЗПК). Получается, что начальные параметры для ЗПК увеличивают общее количество параметров требуемых для взлома. Начальные параметры для итерационной функции и для ЗПК, определяющие конкретную фрактальную последовательность из множества возможных для данного алгоритма, являются криптографическим ключом. Ещё одним способом усложнить перебор начальных параметров итерационной функции является выбор начальных значений вблизи точки аттрактора, так как это требует более точного представления чисел. В окрестности таких точек фрактал обладает качественной неоднозначностью, что усложняет задачу подбора значений. Так же есть возможность реализовать визуальную схему разделения секретной информации информации k из n (ВСРС(k, n)). В такой схеме любые k участников из n могут восстановить секретную информацию и в то же время любые k-1 участников не смогут получить доступ к этой информации. Каждый участник имеет свою часть, некоторое шумоподобное изображение, полученное с помощью фрактальных последовательностей.

Исследование

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

Способы применения фракталов в алгоритмах шифрования

Фракталы в алгоритмах шифрования применяются для:

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

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

Литература

• Кулешов С. В. Фрактальное шифрование // Труды СПИИРАН : журнал. — Санкт-Петербург: Федеральное государственное бюджетное учреждение науки Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 2004. — Т. 1, вып. 2. — С. 231—235. — ISSN 2078-9181.
• Пителинский К. В., Синьковский А. В. Роль коммуникаций в информационном обществе и фрактальные алгоритмы шифрования данных // Вопросы защиты информации : журнал. — Москва: Научно-технический центр оборонного комплекса "Компас", 2005. — Вып. 4(71). — С. 15—17. — ISSN 2073-2600.
• Борискевич А. А. Алгоритм маркирования изображений на основе визуальной криптографии для защиты от несанкционированного распространения информации // Доклады Белорусского государственного университета информатики и радиоэлектроники : журнал. — Минск: Белорусский государственный университет информатики и радиоэлектроники, 2012. — Вып. 5 (67). — С. 73—79. — ISSN 1729-7648.
• Abraham Jun Jiang Lock, Chong Hooi Loh, Siti Hasanah Juhari, Azman Samsudin. Compression-Encryption Based on Fractal Geometric (англ.) // 2nd International Conference on Computer Research and Development, ICCRD 2010 : сборник трудов конференции. — 2010. — P. 213—217. — ISBN 978-0-7695-4043-6. — doi:10.1109/ICCRD.2010.40.
• Şefika Şule, ErçetinSanto Banerjee. Chaos, Complexity and Leadership 2013 (англ.). — Springer, 2014. — 566 p. — ISBN 978-3-319-09710-7.