MODIFICATION OF ASMUT-BLUM DATA SHARING SCHEME USING THE FRACTAL GEOMETRY METHOD

Full Text

Введение Хранение личной информации является важной составляющей жизни современного человека. С развитием облачных технологий для удаленного хранения данных, а также сетей для их передачи возрастает необходимость применения криптографических и не криптографических алгоритмов. Для надежного хранения информации и обеспечения распределенного доступа к ресурсам применяются схемы с разделением информации на части. В таких схемах получить доступ к ней, можно только собрав все ее части. В случае, когда количество долей достаточных для восстановления информации отличается от общего количества частей, то применяются пороговые схемы разделения данных (СРД). Основоположниками порогового разделения данных являются А. Шамир [9] и Дж. Блэкли [10]. Позже были предложены схемы разделения данных основанные на Китайской теореме об остатках (КТО), такие как схема Асмута-Блума [8] и схема Миньотта [11]. Основные критерии СРД это - совершенность, идеальность и вычислительная сложность. СРД, основанные на КТО, имеют меньшую вычислительную сложность по сравнению с другими схемами. Среди схем, основанных на КТО, совершенной и идеальной является схема Асмута-Блума [8]. СРД имеют также свои недостатки: они подвергаются как внутренним, так и внешним атакам [1]. Среди СРД основанных на КТО выявляется один общий недостаток - если данные меньше основания СОК, то они остаются неизменными, а в противном случае они меняют свой порядок. На рис. 1 показано, как исходный синусоидальный сигнал (см. рис. 1а) подвергается модулярному делению по основанию 200 (см. рис. 1б) и по основанию 100 (см. рис. 1в). Из рис. 1 видно, что часть сигнала остается неизменной, а другая часть меняет свой порядок, но не изменяет форму. Например, применив СОК на изображении часть его будет неизменна, либо будут видны его «тени». Введение в СОК. Схема разделения данных Асмута-Блума и ее модификация Напомним, что СОК относится к непозиционным системам счисления, числа в которой представляются в базисе взаимно-простых чисел, называемых модулями , , для . Произведение всех модулей СОК называется динамическим диапазоном системы. В диапазоне любое целое число может быть представлено единственным образом в СОК в виде вектора , где . Из вышесказанного можно сделать вывод, что для порогового разделения данных предпочтительнее использовать СРД Асмута-Блума, но необходимо применять дополнительные кодирующие преобразования. В схеме разделения данных Асмута-Блума разделение данных происходит по формуле , где , - аддитивное смещение которое добавляет шум в сигнал. Так как пороговые схемы разделения данных подвергаются различным типам атак, например, злоумышленник, прослушав линии связи, может восстановить информацию, то при использовании схемы Асмута-Блума он получит только . Для полного восстановления информации необходимо произвести вычитание где - постоянная константа в диапазоне . Для увеличения криптографических свойств константа должна изменятся. Величина выбирается из условий , где - динамический диапазон СОК и поэтому величина постоянная. Значение выбирается как случайное число из диапазона . Рис. 1. Представление сигнала в СОК: а) исходный сигнал, б) сигнал по модулю 200, в) сигнал по модулю 100 В статье предлагается подход к использованию фрактальных итерационных функций в качестве кодирующей функции. Данный подход отличается от обычных методов кодирования тем, что фрактальная последовательность используется в качестве сложной кодирующей функции [3]. При этом описание этой функции, достаточное для построения, является набором вещественных чисел, которые задают начальные условия итерационного процесса построения фрактальной последовательности [4]. Этот подход является вариантом гаммирования - процесса «наложения» гамма - последовательности, на открытые данные, где в качестве гамма - последовательности используется фрактальная последовательность. Основной проблемой средств защиты информации является порождение случайных последовательностей бит. Генераторы случайных последовательностей, используемые для общих целей, являются псевдослучайными генераторами [2]. Идея применения фракталов как псевдослучайных последовательностей исходит из предположения возможности описания поведения физических и природных систем с помощью фракталов [5]. Фракталы относятся к множествам с крайне нерегулярной разветвленной или изрезанной структурой. Теория фракталов рассматривает дробные меры вместо целочисленных и базируется на количественных показателях в виде дробных размерностей и соответствующих сигнатур. Фракталы характеризуют как топологию объектов, так и эволюцию динамических систем и связаны с их свойствами. Теория фракталов и нелинейность составляют геометрию хаоса. По своему содержанию контуры всех природных объектов суть динамические процессы, внезапно застывшие в физических формах и объединяющие в себе устойчивость и хаос [6]. Таким образом, применение «генераторов шума» основанных на фракталах дает преимущество над традиционными системами псевдослучайных последовательностей. Другим достоинством генератора псевдослучайных чисел основанного она фракталах является то что он имеет бесконечное количество состояний ЭВМ в отличие от классических генераторов псевдослучайных чисел. В статье для построения фрактала применено множество Мандельброта. Множество Мандельброта является одним из самых известных фракталов, в том числе за пределами математики, благодаря своим цветным визуализациям. Его фрагменты не строго подобны исходному множеству, но при многократном увеличении определённые части всё больше похожи друг на друга. Множество Мандельброта - это множество таких точек на комплексной плоскости, для которых итерационная последовательность при является ограниченной. Последовательность может быть раскрыта для каждой точки на комплексной плоскости следующим образом [7]: На рис. 2 слева представлен классический фрактал множества Мандельброта. Визуально внутри множества Мандельброта можно выделить бесконечное число элементарных фигур, причем самая большая в центре представляет собой кардиоиду. Пример увеличения множества фрактала представлен на рис. 2 справа. Таким образом, применив фрактал в качестве случайной величины , получим зашумленные части изображения. Рассмотрим алгоритм разделения информации на части с применим фрактала ее восстановления. Рис. 2. Увеличение фрактала, соответствующего множеству Мандельброта Изображение на ЭВМ имеет вид матрицы пикселей размерностью . В каждом ее элементе хранятся значения глубины цветов в палитре RGB (Red, Green, Blue) в диапазоне . Операторами и - где и , обозначим матрицу исходного изображения и матрицу изображения фрактала соответственно. Таким образом алгоритм состоит из следующих действий. 1. Выбирается ряд чисел . 2. Вычисляется . 3. Вычисляются части данных . 4. Выполняется обратное преобразование из СОК в ПСС: . 5. Вычисляется . Схема разделения данных с применения фрактала представлена на рис. 3. Рис. 3. Схема разделения изображения Применив для взлома метод «грубой силы» необходимо для каждой точки изображения перебрать все возможные комбинации. При использовании фрактала разрядностью 8 бит количество комбинаций, где - разрешение изображения; - глубина цвета изображения. Также достоинством данного метода является отсутствие необходимости хранить изображение фрактала или сгенерированные случайные числа поскольку при восстановлении зная схему раскраски фрактала и порядок его уравнения, числа могут быть сгенерированы заново. Численный метод разделения информации с применением модифицированной схемы разделения данных Асмута-Блума Для порогового разделения данных модифицированным методом Асмута-Блума необходимы две матрицы: - матрица данных, - матрица псевдослучайных чисел фрактала. Для простоты вычислений представим обе матрицы размерностью 3×3. Рис. 4. Увеличение участка изображения Необходимо заполнить массив данных и массив фрактала числами. Так как изображение - это матрица размерами , каждый пиксель которой представлен тремя цветами (красный, синий, зеленый), то путем увеличения рисунка (как это показано на рис. 4) и с помощью инструмента Paint можно получить значения нескольких пикселей и вычислить среднее арифметическое цветов RGB: Для вычислений возьмем следующий ряд модулей: , , , , , . Проверим условие: Значения также упорядочены. Для вычисления частей данных необходимо массив умножить на : Далее необходимо поэлементно сложить значения в получившемся массиве и в массиве А: Следующий шаг это - разделение данных, которое выполняется путем преобразования элементов массива в СОК: Массивы - это части информации, и они распространяются среди пользователей. Для восстановления данных необходимо провести для массивов обратное преобразование из СОК в ПСС. Выполнив данное преобразование, получим массив Далее из массива данных необходимо поэлементно вычесть произведение Блок схема алгоритма разделения изображения на части приведена на рис. 5. Рис. 5. Алгоритм вычисления частей данных модифицированным методом Асмута-Блума В отличие от криптографических алгоритмов таких как RSA в котором вычислительная сложность равна использование численного метода, основанного на модификации схемы Асмута-Блума с применением фрактальной геометрии, позволяет закодировать информацию, не увеличивая вычислительную сложность СРД. Моделирование модифицированной схемы разделения данных Асмута-Блума с применением фрактальной геометрии Рассмотрим пример реализации предложенного метода. Так как множество Мандельброта является бесконечной последовательностью, то увеличим его участок и в экспериментах будем использовать часть фрактала (см. рис. 7) для моделирования разделения изображения «Лена», показанного на рис. 7. Применив схему, представленную на рис. 4 и алгоритм, представленный на рис. 6, а также используя набор модулей , , , , , получим результаты, показанные на рис. 8. Рис. 6. Часть фрактала, используемого при моделировании Рис. 7. Изображение «Лена», используемое при моделировании Другим способом искажения изображения является наложение белого шума. Применив вместо фрактала белый шум, получим результаты, показанные на рис. 9. Визуально сравнивая изображения, представленные на рис. 8 и рис. 9, можно сделать вывод, что применение фрактальной последовательности позволит более качественно исказить изображение, а, следовательно, более надежно его хранить и обрабатывать. а) б) в) г) д) Рис. 8. Результаты работы модифицированной схемы разделения данных Асмута-Блума с применением фрактальной последовательности для набора модулей а) 547; б) 557; в) 563; г) 569; д) 571 а) б) в) г) д) Рис. 9. Результаты работы модифицированной схемы разделения данных Амсута-Блума с применением белого шума для набора модулей а) 547; б) 557; в) 563; г) 569; д) 571

About the authors

Nikolai Ivanovich Chervyakov

North Caucasus Federal University

Email: k-fmf-primath@stavsu.ru

Yuri Nikolaevich Kocherov

Nevinnomyssk Technological Institute

Email: kocherov_yra@mail.ru

References

Supplementary files