Разработка алгоритмов тестирования псевдослучайных последовательностей и хеширования данных на основе модели Изинга

• Автор: Шерешик, Антон Юрьевич
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 97 с. : ил.

Содержание
Введение
Глава 1. Статистические физические модели и генераторы псевдослучайных последовательностей

1.1 Модель Изинга.

1.2 Алгоритм Метрополиса

1.3 Генераторы псевдослучайных последовательностей

1.3.1 Линейный конгруэнтный генератор.

1.3.2 Генератор Фибоначчи с запаздыванием.

1.3.3 Вихрь Мерсенна

1.4 Тестирование псевдослучайных последовательностей

1.5 Хешфункции.

Глава 2. Тестирование генераторов псевдослучайных последовательностей с помощью модели Изинга
2.1 Метод тестирования
2.1.1 Алгоритм
2.1.2 Способы оценки точности моделирования фазового перехода
2.1.3 Описание эксперимента.
2.1.4 Выбор параметров моделирования
2.2 Тестирование линейного конгруэнтного генератора псевдослучайных последовательностей на двумерной модели Изинга.
2.3 Тестирование линейного конгруэнтного генератора псевдослучайных последовательностей на трехмерной модели Изинга
2.4 Тестирование генератора Фибоначчи на двумерной модели Изинга
2.5 Тестирование генератора Фибоначчи на трехмерной модели Изинга
2.6 Тестирование генератора Вихрь Мерсенна на двумерной модели
2.7 Тестирование генератора Вихрь Мерсенна на трехмерной модели
2.8 Сравнение результатов тестирования
2.9 Выводы
Глава 3. Хеширование данных с помощью модели Изинга.
3.1 Описание алгоритма хеширования
3.2 Тестирование хешфункций на основе двумерной модели Изинга
3.3 Тестирование хешфункций на основе трехмерной модели Изинга.
3.4 Описание улучшенного алгоритма хеширования
3.5 Сравнение хешфункций.
3.6 Выводы
Заключение
Литература


Традиционный подход к тестированию генераторов псевдослучайных последовательностей связан с рассмотрением выходного набора чисел как значений случайной величины. Использование же модели Изинга в качестве теста генератора псевдослучайной последовательности основано на чувствительности алгоритма Метрополиса к входной последовательности псевдослучайных чисел. Если псевдослучайная последовательность далека по своим свойствам от истинно случайной, то критические индексы системы будут отличны от предсказываемых теорией и наблюдаемых в реальном эксперименте. Кроме тестирования случайной последовательности модель Изинга может быть использована для генерации псевдослучайной последовательности и последующего поточного шифрования на ее основе []. Ключом шифрования, при этом, служат данные для инициализации последовательности. Также для шифрования может быть использована модель решеточного газа, близкая к модели Изинга []. В работе [] модель Изинга используется для построения кода Галагера. Данный код с исправлением ошибок использует случайные матрицы, которые авторы и предлагают формировать с помощью алгоритма Метрополиса для модели Изинга. Также в работе приводится методика использования данного кода в криптосистемах с открытым ключом. Таким образом, модель Изинга нашла применение при решении некоторых задач защиты информации. Однако остается не исследованной возможность использования модели Изинга для хеширования данных, а также не достаточно развита методика тестирования псевдослучайной последовательности на ее основе. Предмет исследования. В данной диссертационной работе предметом исследования является методика тестирования псевдослучайных последовательностей и разработка хеш-функций на базе статистической модели Изинга. Объект исследования. Объектом исследования являются статистические свойства псевдослучайных последовательностей и хеш-функций на основе модели Изинга. Цели и задачи диссертационной работы. Целью диссертационной работы является разработка новых методов тестирования псевдослучайных последовательностей и хеширования данных. Разработать методику тестирования псевдослучайных последовательностей, использующую чувствительность алгоритма Метрополиса для двумерной и трехмерной моделей Изинга к входным данным. С помощью разработанной методики провести тестирование широко распространенных генераторов псевдослучайных последовательностей для определения предпочтительных параметров используемых рекуррентных соотношений. Разработать хеш-функцию, использующую для перемешивания данных двумерную и трехмерную модели Изинга. Провести сравнение разработанных хеш-функций и выявить наиболее предпочтительные параметры модели. Методы исследования. В диссертационной работе использованы методы статистической физики для решеточных моделей, методы тестирования псевдослучайных последовательностей, а также методы тестирования хеш-функций, хорошо зарекомендовавшие себя при построении алгоритмов защиты информации. Разработана новая методика тестирования псевдослучайных последовательностей, позволяющая, в отличие от статистических тестов, не просто давать качественную оценку последовательности, но и указывать какой именно параметр последовательности не удовлетворяет условиям задачи. Для линейного конгруэнтного генератора выявлены значения мультпли-кативной константы, не удовлетворяющие статистическим условиям, однако обеспечивающие хорошее качество выходной последовательности. Впервые для построения алгоритма хеширования данных применена двумерная и трехмерная модели Изинга. Разработан алгоритм хеширования, не уступающий по криптографическим свойствам широко распространенным современным хеш-функциям, однако обладающий вариативностью размеров входных и выходных данных без дополнительного «ручного» изменения констант алгоритма. Практическая значимость работы заключается, во-первых, в разработке методики тестирования, с помощью которой возможно не просто дать качественную оценку используемой псевдослучайной последовательности, но и определить её применимость в произвольном алгоритме с заданной трудоемкостью.