Введение к работе
Актуальность работы. В последнее время применение различных физических моделей в области информационных технологий приобретает все большее распространение. Особенно можно выделить модели статистической физики, такие как модель Изинга. Большинство современных алгоритмов шифрования и хеширования основываются на ограниченном количестве хорошо известных операций, таких как подстановки, перестановки и сложение по модулю 2. Практически все блочные шифры имеют в своей основе ячейку Фейстеля. Развитие криптографических методов защиты информации идет по экстенсивному пути увеличения длины ключа и величины блока данных, что приводит к экспоненциальному росту нагрузки на аппаратную часть вычислительных систем. В связи с этим актуальной является задача поиска новых подходов к построению алгоритмов шифрования и хеширования, использующих принципиально иные подходы. Это подтверждается, например, недавно завершившимся конкурсом на создание нового стандарта хеширования SHA-3 (NIST, 2007).
Одним из активно развивающихся направлений является использование конечных автоматов в вопросах криптографической защиты данных. При этом главным требованием к используемым автоматам является равномерное распределение выходных данных. Таким образом, упорядоченное входное слово (открытый текст) должно преобразовываться в случайную последовательность на выходе (шифртекст). Отсюда следует, что система шифрования должна повышать энтропию преобразовываемого текста. Данным свойством обладают физические системы вследствие второго начала термодинамики. Таким образом, «хороших» свойств можно ожидать от криптографических алгоритмов, построенных на автоматах, моделирующих реальные физические системы.
Модель Изинга является одной из самых широко используемых моделей статистической физики. С её помощью исследуют ферромагнитные материалы.
Однако в последнее время появился ряд подходов, позволяющих использовать модель Изинга и в вопросах защиты информации.
Первый подход связан с использованием модели Изинга для тестирования генераторов псевдослучайных последовательностей (P. D. Coddington, 1996). Вопрос получения качественной случайной последовательности весьма актуален для выработки стойких ключей шифрования, а также проверки стойкости хеш-функций и алгоритмов шифрования. Традиционный подход к тестированию генераторов псевдослучайных последовательностей связан с рассмотрением выходного набора чисел как значений случайной величины. Использование же модели Изинга в качестве теста генератора псевдослучайной последовательности основано на чувствительности алгоритма Метрополиса к входной последовательности псевдослучайных чисел. Если псевдослучайная последовательность далека по своим свойствам от истинно случайной, то критические индексы системы будут отличны от предсказываемых теорией и наблюдаемых в реальном эксперименте.
Кроме тестирования случайной последовательности модель Изинга может быть использована для генерации псевдослучайной последовательности и последующего поточного шифрования на ее основе (A. Perez и др., 2012). Ключом шифрования, при этом, служат данные для инициализации последовательности. Также для шифрования может быть использована модель решеточного газа, близкая к модели Изинга (B. Chopard и др., 2005). В работе D. Saad и др. модель Изинга используется для построения кода Галагера. Данный код с исправлением ошибок использует случайные матрицы, которые авторы и предлагают формировать с помощью алгоритма Метрополиса для модели Изинга. Также в работе приводится методика использования данного кода в криптосистемах с открытым ключом.
Таким образом, модель Изинга нашла применение при решении некоторых задач защиты информации. Однако остается не исследованной возможность использования модели Изинга для хеширования данных, а также не достаточно развита методика тестирования псевдослучайной последовательности на ее основе.
Предмет исследования. В данной диссертационной работе предметом исследования является методика тестирования псевдослучайных последовательностей и разработка хеш-функций на базе статистической модели Изинга.
Объект исследования. Объектом исследования являются статистические свойства псевдослучайных последовательностей и хеш-функций на основе модели Изинга.
Цели и задачи диссертационной работы. Целью диссертационной работы является разработка новых методов тестирования псевдослучайных последовательностей и хеширования данных. Для достижения цели поставленной в данной работе необходимо решить следующие задачи:
-
Разработать методику тестирования псевдослучайных последовательностей, использующую чувствительность алгоритма Метрополиса для двумерной и трехмерной моделей Изинга к входным данным.
-
С помощью разработанной методики провести тестирование широко распространенных генераторов псевдослучайных последовательностей для определения предпочтительных параметров используемых рекуррентных соотношений.
-
Разработать хеш-функцию, использующую для перемешивания данных двумерную и трехмерную модели Изинга.
-
Провести сравнение разработанных хеш-функций и выявить наиболее предпочтительные параметры модели.
Методы исследования. В диссертационной работе использованы методы статистической физики для решеточных моделей, методы тестирования псевдослучайных последовательностей, а также методы тестирования хеш-функций, хорошо зарекомендовавшие себя при построении алгоритмов защиты информации.
Научная новизна работы заключается в следующем:
-
-
Разработана новая методика тестирования псевдослучайных последовательностей, позволяющая, в отличие от статистических тестов, не просто давать качественную оценку последовательности, но и указывать какой именно параметр последовательности не удовлетворяет условиям задачи.
-
Для линейного конгруэнтного генератора выявлены значения мультп- ликативной константы, не удовлетворяющие статистическим условиям, однако обеспечивающие хорошее качество выходной последовательности.
-
Впервые для построения алгоритма хеширования данных применена двумерная и трехмерная модели Изинга.
-
Разработан алгоритм хеширования, не уступающий по криптографическим свойствам широко распространенным современным хеш-функциям, однако обладающий вариативностью размеров входных и выходных данных без дополнительного «ручного» изменения констант алгоритма.
Практическая значимость работы заключается, во-первых, в разработке методики тестирования, с помощью которой возможно не просто дать качественную оценку используемой псевдослучайной последовательности, но и определить её применимость в произвольном алгоритме с заданной трудоемкостью. Во-вторых, предложенная хеш-функция обладает достаточно большой свободой выбора размеров входных блоков и выходного дайджеста, что делает ее практически универсальной и позволяет использовать в любых криптографических протоколах и алгоритмах электронной цифровой подписи.
Основные научные положения, выносимые на защиту:
-
-
-
Методика тестирования псевдослучайных последовательностей на основе модели Изинга позволяет выявлять последовательности применимые в алгоритмах с заданной трудоемкостью. В случае невозможности применения псевдослучайной последовательности предложенная методика позволяет выявить, какой именно параметр последовательности не соответствует требованиям задачи.
-
Генератор псевдослучайных последовательностей Фибоначчи и вихрь Мерсена обладают достаточно хорошими свойствами, тогда линейный конгруэнтный генератор не всегда проходит тест на длину периода последовательности. Существуют параметры линейного конгруэнтного генератора, не обладающие достаточными статистическими свойствами, однако обеспечивающие производство качественной выходной последовательности.
-
Алгоритм Метрополиса для модели Изинга обладает хорошими перемешивающими свойствами и может быть использован для построения функции хеширования данных.
-
Хеш-функция на основе модели Изинга дает хорошие результаты для таких криптографических тестов как наличие коллизий и лавинный эффект при этом обладает свойством произвольности выбора размеров входных и выходных данных, что обеспечивает ей широкую область применимости в алгоритмах защиты информации.
Апробация работы. Основные положения диссертационной работы представлялись и обсуждались на следующих конференциях и семинарах: II Межвузовская научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2010; XIII Международная заочная научно-практическая конференция «Наука и современность - 2011», г. Новосибирск, 2011; Четвертая региональная научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2012; IV Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоровские чтения)», г. Санкт-Петербург, 2012.
Публикации. Результаты диссертационной работы были представлены в 8 научных работах, в том числе 3 статьи в журналах из списка периодических изданий, рекомендованных ВАК.
Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Все представленные в диссертации результаты получены лично автором.
Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения, библиографического списка и изложена на 97 страницах машинописного текста. Содержит 25 рисунков и 8 таблиц. Библиографический список литературы состоит из 105 наименований.
Похожие диссертации на Разработка алгоритмов тестирования псевдослучайных последовательностей и хеширования данных на основе модели Изинга
-
-
-
