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

На правах рукописи

Шерешик Антон Юрьевич

РАЗРАБОТКА АЛГОРИТМОВ ТЕСТИРОВАНИЯ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ХЕШИРОВАНИЯ ДАННЫХ НА ОСНОВЕ МОДЕЛИ

ИЗИНГА

05.13.19 - Методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

14 ЯНВ 2013

Омск-2013

005048686

Работа выполнена в ФГБОУ ВПО «Омский государственный университет им. ОмГУ им. Ф.М. Достоевского» (ОмГУ), г. Омск.

Научный руководитель:

доктор физико-математических наук, профессор

Белим Сергей Викторович

Официальные оппоненты: доктор технических наук, профессор Коробейников Анатолий Григорьевич

«Институт земного магнетизма, ионосферы и распространения радиоволн РАН им. Н.В.Пушкова» (ИЗМИРАН), зам. директора по научной работе СПбФУ

кандидат физико-математических наук, доцент Комаров Игорь Иванович

«Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» (НИУ ИТМО), доцент кафедры Безопасных информационных технологий

Ведущая организация:

ФГБОУ ВПО «Омский государственный университет путей сообщения» (ОмГУПС)

Защита диссертации состоится «13» февраля 2013 г. в 15:50 часов на заседании диссертационного совета Д 212.227.05 при ФГБОУ ВПО «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» (НИУ ИТМО) по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д.49. (

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского национального исследовательского университета информационныхдехнологий, механики и оптики.

Автореферат разослан «11» января 2013 г. Ученый секретарь

диссертационного совета, к.т.н., доцент

Поляков Владимир Иванович

Общая характеристика работы

Актуальность работы. В последнее время применение различных физических моделей в области информационных технологий приобретает все большее распространение. Особенно можно выделить модели статистической физики, такие как модель Изинга. Большинство современных алгоритмов шифрования и хеширования основываются на ограниченном количестве хорошо известных операций, таких как подстановки, перестановки и сложение по модулю 2. Практически все блочные шифры имеют в своей основе ячейку Фейстеля. Развитие криптографических методов защиты информации идет по экстенсивному пути увеличения длины ключа и величины блока данных, что приводит к экспоненциальному росту нагрузки на аппаратную часть вычислительных систем. В связи с этим актуальной является задача поиска новых подходов к построению алгоритмов шифрования и хеширования, использующих принципиально иные подходы. Это подтверждается, например, недавно завершившимся конкурсом на создание нового стандарта хеширования 8НА-3 (N181", 2007).

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

Модель Изинга является одной из самых широко используемых моделей статистической физики. С её помощью исследуют ферромагнитные материалы.

Однако в последнее время появился ряд подходов, позволяющих использовать модель Изинга и в вопросах защиты информации.

Первый подход связан с использованием модели Изинга для тестирования генераторов псевдослучайных последовательностей (P. D. Coddington, 1996). Вопрос получения качественной случайной последовательности весьма актуален для выработки стойких ключей шифрования, а также проверки стойкости хеш-функций и алгоритмов шифрования. Традиционный подход к тестированию генераторов псевдослучайных последовательностей связан с рассмотрением выходного набора чисел как значений случайной величины. Использование же модели Изинга в качестве теста генератора псевдослучайной последовательности основано на чувствительности алгоритма Метрополиса к входной последовательности псевдослучайных чисел. Если псевдослучайная последовательность далека по своим свойствам от истинно случайной, то критические индексы системы будут отличны от предсказываемых теорией и наблюдаемых в реальном эксперименте.

Кроме тестирования случайной последовательности модель Изинга может быть использована для генерации псевдослучайной последовательности и последующего поточного шифрования на ее основе (A. Perez и др., 2012). Ключом шифрования, при этом, служат данные для инициализации последовательности. Также для шифрования может быть использована модель решеточного газа, близкая к модели Изинга (В. Chopard и др., 2005). В работе D. Saad и др. модель Изинга используется для построения кода Галагера. Данный код с исправлением ошибок использует случайные матрицы, которые авторы и предлагают формировать с помощью алгоритма Метрополиса для модели Изинга. Также в работе приводится методика использования данного кода в криптосистемах с открытым ключом.

Таким образом, модель Изинга нашла применение при решении некоторых задач защиты информации. Однако остается не исследованной возможность использования модели Изинга для хеширования данных, а также не дос-

таточно развита методика тестирования псевдослучайной последовательности на ее основе.

Предмет исследования. В данной диссертационной работе предметом исследования является методика тестирования псевдослучайных последовательностей и разработка хеш-функций на базе статистической модели Изинга.

Объект исследования. Объектом исследования являются статистические свойства псевдослучайных последовательностей и хеш-функций на основе модели Изинга.

Цели и задачи диссертационной работы. Целью диссертационной работы является разработка новых методов тестирования псевдослучайных последовательностей и хеширования данных. Для достижения цели поставленной в данной работе необходимо решить следующие задачи:

1. Разработать методику тестирования псевдослучайных последовательностей, использующую чувствительность алгоритма Метрополиса для двумерной и трехмерной моделей Изинга к входным данным.

2. С помощью разработанной методики провести тестирование широко распространенных генераторов псевдослучайных последовательностей для определения предпочтительных параметров используемых рекуррентных соотношений.

3. Разработать хеш-функцию, использующую для перемешивания данных двумерную и трехмерную модели Изинга.

4. Провести сравнение разработанных хеш-функций и выявить наиболее предпочтительные параметры модели.

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

Научная новизна работы заключается в следующем:

1. Разработана новая методика тестирования псевдослучайных последовательностей, позволяющая, в отличие от статистических тестов, не просто давать качественную оценку последовательности, но и указывать какой именно параметр последовательности не удовлетворяет условиям задачи.

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

3. Впервые для построения алгоритма хеширования данных применена двумерная и трехмерная модели Изинга.

4. Разработан алгоритм хеширования, не уступающий по криптографическим свойствам широко распространенным современным хеш-функциям, однако обладающий вариативностью размеров входных и выходных данных без дополнительного «ручного» изменения констант алгоритма.

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

Основные научные положения, выносимые на защиту:

1. Методика тестирования псевдослучайных последовательностей на основе модели Изинга позволяет выявлять последовательности применимые в алгоритмах с заданной трудоемкостью. В случае невозможности применения псевдослучайной последовательности предложенная методика позволяет выявить, какой именно параметр последовательности не соответствует требованиям задачи.

2. Генератор псевдослучайных последовательностей Фибоначчи и вихрь Мерсена обладают достаточно хорошими свойствами, тогда линейный конгру-

энтный генератор не всегда проходит тест на длину периода последовательности. Существуют параметры линейного конгруэнтного генератора, не обладающие достаточными статистическими свойствами, однако обеспечивающие производство качественной выходной последовательности.

3. Алгоритм Метрополиса для модели Изинга обладает хорошими перемешивающими свойствами и может быть использован для построения функции хеширования данных.

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

Апробация работы. Основные положения диссертационной работы представлялись и обсуждались на следующих конференциях и семинарах: II Межвузовская научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2010; XIII Международная заочная научно-практическая конференция «Наука и современность — 2011», г. Новосибирск, 2011; Четвертая региональная научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2012; IV Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоровские чтения)», г. Санкт-Петербург, 2012.

Публикации. Результаты диссертационной работы были представлены в 8 научных работах, в том числе 3 статьи в журналах из списка периодических изданий, рекомендованных ВАК.

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

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения, библиографического списка и изложена на 97

страницах машинописного текста. Содержит 25 рисунков и 8 таблиц. Библиографический список литературы состоит из 105 наименований.

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

Первая глава носит обзорный характер и посвящена обсуждению модели Изинга, алгоритму Метрополиса, а также статистическим методам тестирования псевдослучайных последовательностей.

Вторая глава посвящена развитию методики тестирования псевдослучайных последовательностей с помощью алгоритма Метрополиса для модели Изинга. Разработанная методика применяется для тестирования таких генераторов как линейный конгруэнтный генератор, генератор Фибоначчи с запаздыванием, вихрь Мерсена.

Задача тестирования — оценить зависимость моделирования фазового перехода на трехмерной модели Изинга от выбора генераторов псевдослучайных последовательностей. Найти, какие из рассмотренных генераторов позволяют достоверно моделировать фазовый переход. Использовались следующие способы:

1. Сравнение критических индексов, полученных при температуре фазового перехода, со значениями, полученными ранее в теоретических и практических исследованиях.

2. Определение температуры фазового перехода с помощью кумулянтов Биндера.

Значение критических индексов удобно найти через уравнение аппроксимирующей прямой, которая строится для теплоемкости, намагниченности и восприимчивости по методу наименьших квадратов:

С ~ М ~ Гр1\ %~П'\ (1)

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

сс = 2-(1у, р = 0.5у(с1 -2 + т]), у = у(2-т]) (2)

Полученные таким образом индексы можно сравнить со значениями, рассчитанными теоретически (таблица 1).

Таблица 1. Сравнение генераторов случайных чисел с помощью критических индексов.

Линейный конгруэнтный генератор Генератор Фибоначчи с запаздыванием Вихрь Мерсенна Теоретическое значение

а 0,103 0,1059 0,1115 0,11

Р 0,3615 0,3155 0,3252 0,3265

V 1,174 1,2634 1,2383 1,2372

Среднее отклонение 7,4% 3,1% 0,6%

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

Также с помощью модели Изинга была проведена оценка влияния параметров генератора на его качество. Зависимость исследовалась на примере линейного конгруэнтного генератора, поскольку он показал результат хуже, чем остальные генераторы и, следовательно, нуждается в улучшении. Последовательность, задаваемая линейным конгруэнтным генератором, имеет вид:

Хп+1=(аХп+С)тоаМ, (3)

где М>0 - модуль последовательности, а — множитель (0<а<М) и с — аддитивная константа.

Значение аддитивной константы намеренно было выбрано равным нулю, с тем, чтобы зависимость от множителя была более наглядна. Модуль последовательности был принят равным 231-1, что соответствует рекомендациям для улучшения качества и быстродействия генератора.

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

Таблица 2. Сравнение параметров линейного конгруэнтного генератора случайных чисел с помощью критических индексов.

Значение множителя а а Р У Отклонение Период генератора

16807 0,103 0,3615 1,174 7,4% 2147483646

16808 0,0214 0,3448 1,289 30,1% 306783378

16809 0,0099 0,351 1,2881 34,2% 195225786

16810 -0,1848 0,4075 1,3698 101,2% 2147483646

16811 0,1546 0,3554 1,1346 19,2% 715827882

16812 0,0928 0,3364 1,2344 6,3% 2147483646

16813 0,1305 0,3255 1,2186 6,8% 1073741823

16814 -0,0392 0,3704 1,2983 51,3% 2147483646

16815 -0,0432 0,3512 1,3408 51,7% 153391689

16816 -0,2469 0,4038 1,4392 121,5% 119304647

16817 0,1213 0,3534 1,1718 7,9% 715827882

16818 0,1596 0,3361 1,1683 17,9% 119304647

16819 -0,0643 0,3381 1,3882 58,1% 715827882

16820 0,0082 0,3513 1,2893 34,8% 2147483646

16831 1,5739 0,0549 0,3162 496,1% 349867

16840 -0,3351 0,3526 1,6299 148,1% 32537631

16872 1,8163 0,0696 0,0445 575,4% 7697074

Также с помощью кумулянтов Биндера была проведена оценка влияния параметров генератора на его качество. На рисунках 1 и 2 приведены два различных случая.

Рис. 1. Расчет кумулянтов Биндера для случая а = 16807.

Рис. 2. Расчет кумулянтов Биндера для множителя а = 16831.

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

(а=16807) и маленьким периодом (а=16831). Если период генератора используемой псевдослучайной последовательности слишком мал, то становится невозможным само вычисление критических индексов, так как не может быть определена критическая температура. Для «коротких» последовательностей ку-муляты Биндера перестают пересекаться в одной точке.

В третьей главе представлен алгоритм хеширования данных на базе двумерной и трехмерной модели Изинга. Для оценки алгоритма, по результатам компьютерного эксперимента были определены значения частоты возникновения коллизий и проверен лавинный эффект. Выбор тестовых данных для исследования алгоритмов хеширования имеет очень большое значение. Чаще всего для этой цели используются словари, поскольку в таком случае результаты будут отражать применимость в реальных задачах связанных с криптографией и базами данных. В качестве тестовых данных использовали американский словарь, составленный проектом Ispell, применяющийся для проверки орфографии на платформе Unix. Словарь содержит 83657 слов, средняя длина которых 8,4 символа.

Алгоритм реализован в виде компьютерной программы, обрабатывающей файлы. В качестве основы алгоритма использована модель Изинга. Входящее сообщение в виде последовательности битов принимается за начальное состояние решетки. Если бит равен 1, будем считать что частица ориентирована по полю, а 0 — против поля. В результате проведения определенного количества итераций ожидается, что изначальное состояние решетки перейдет в новое, где частицы ориентированы хаотично. Таким образом, полученное состояние будет считаться хеш-значением входящей информации.

В качестве основы алгоритма были рассмотрены двумерные решетки с различными линейными размерами 8, 12, 16, 20, 24. Для оценки результатов, были определены значения частоты возникновения коллизий. Для качествен-

ных хеш-функций их частота близка к теоретическому минимуму. Результаты экспериментов представлены на рисунке 3.

Рис. 3. Влияние температуры на процент коллизий хеш-функции для двумерной решетки

Таким же образом были рассмотрены трехмерные решетки с различными линейными размерами: 4, 6, 8. На рисунке 4 приведены результаты экспериментов по количеству коллизий.

Рис. 4. Влияние температуры на процент коллизий хеш-функции для трехмерной решетки

Температура модели была выбрана в области критической температуры и выше. Для двумерных и трехмерных решеток эти значения различны, они соответствуют температуре, при которой происходит переход к неупорядоченному

состоянию. Стоит отметить, что алгоритм на основе трехмерной решетки показал результаты лучше, это объясняется большим количеством связей между элементами. Для трехмерной решетки с линейным размером 8 при температуре 5.1 удалось добиться минимального числа коллизий: 3 из 83657 или 0,0024%. Качественный лавинный эффект достигается уже при температуре выше 4.7 для любых линейных размеров решетки (рисунок 5).

Рис. 5. Влияние температуры на лавинный эффект хеш-функции для трехмерной решетки

Показатели среднего арифметического значения битов хеш-значений, полученных в результате эксперимента также зависят от выбора температуры.

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

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

промежуточных состояний. Схема полученного алгоритма приведена на рисун-

ке 6.

Рис. 6. Схема алгоритма хеширования данных с помощью трехмерной модели Изинга

По итогам серии экспериментов для этого алгоритма были получены результаты практически равные результатам для известных хеш-функций 1УГО5 и 8НА-1. Также удалось добиться отсутствия коллизий. Некоторые результаты приведены в таблице 3.

Таблица 3. Сравнение статистических качеств хеш-функций.

Энтропия на 1 байт Арифметич ское среднее на 1 байт Критерий х1

Трехмерная модель Изинга 7,997 127,583 63,65

МЭ5 7,998 127,594 5,15

БНА-! 7,999 127,43 83,17

По результатам экспериментов, на основе хеш-значений всех слов из словаря, были сформированы двоичные последовательности, которые были исследованы на случайность с помощью набора тестов разработанных институтом Ы18Т (А. ЯикЫп и др., 2010). Каждая последовательность была разбита на 100 блоков общей длинной 223 бит. Полученные в результате работы различных хеш-функций последовательности успешно прошли все тесты, что позволяет утверждать, что построенный на основе модели Изинга алгоритм хеширования не уступает распространенным аналогам.

В заключении представлены основные результаты работы и сформулированы выводы.

Основные результаты:

1. Разработана методика тестирования псевдослучайных последовательностей на основе алгоритма Метрополиса для модели Изинга. Показано, что:

1.1 Недостаточный период псевдослучайной последовательности приводит к отсутствию точки пересечения куммулянтов Биндера и, как следствие, невозможности определения температуры фазового перехода.

1.2 Отклонение от равномерного распределения значения членов псевдослучайной последовательности приводит к неверным значениям критических индексов.

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

2. Проведено тестирование наиболее распространенных генераторов псевдослучайных последовательностей с помощью разработанной методики для двумерной и трехмерной модели Изинга. Показано, что:

2.1 Линейный конгруэнтный генератор не всегда производит последовательность с достаточно длинным периодом. Существуют параметры линейного конгруэнтного генератора, не удовлетворяющие достаточным статистическим свойствам, однако обеспечивающие производство качественной выходной последовательности.

2.2 Генератор Фибоначчи с запаздыванием обладает как хорошим распределением, так и достаточно длинным периодом.

2.3 Вихрь Мерсена обладает как хорошим распределением, так и достаточно длинным периодом. Из рассмотренных генераторов вихрь Мерсенна является наиболее качественным.

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

3.1 Исследование лавинного эффекта показало, что изменение одного бита входного сообщения приводит к изменению в среднем 50% битов в выходном значении.

3.2 Тестирование на наличие коллизий показало, что оно не выше, чем у широко распространенных алгоритмов хеширования.

3.3 Тесты Ы18Т показали, что качество полученной хеш-функции сопоставимо с широко распространенными алгоритмами М05 и 8НА-1.

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

Основные публикации по теме диссертации

Журналы из списка, рекомендованного ВАК:

1. Шерешик, А. Ю. Тестирование генераторов псевдослучайных последовательностей с помощью трехмерной модели Изинга // Вестник Омского университета. 2011. № 4. С. 172-174

2. Шерешик, А. Ю. Использование модели Изинга на двухмерной решетке для построения хеш-функции. // Вестник Омского университета. 2012. № 4. С. 187-190

3. Белим С. В., Шерешик А. Ю. Тестирование генераторов псевдослучайных последовательностей с помощью трехмерной модели Изинга // Наука и образование. 2012. № 09. С. 1-5.

Остальные публикации:

4. Шерешик А. Ю. Тестирование генераторов псевдослучайных последовательностей с использованием трехмерной модели Изинга // Математические структуры и моделирование. 2010. №21. С.32-3 6

5. Шерешик А. Ю. Анализ конгруэнтных генераторов псевдослучайных последовательностей с использованием трехмерной модели Изинга // Информационные технологии автоматизации и управления: материалы II межвузовской научно-практической конференции 2010 г. Омск: Изд-во ОмГТУ, 2010., С.120-122

6. Шерешик А. Ю. Влияние генератора псевдослучайных последовательностей на моделирование фазового перехода // Наука и современность — 2011:

Сборник материалов XIII Международной научно-практической конференции. Часть 2. С.256-258

7. Шерешик А. Ю. Оценка параметров линейного конгруэнтного генератора псевдослучайных последовательностей с помощью модели Изинга// Информационные технологии автоматизации и управления: материалы четвертой региональной научно-практической конференции, 2012 г., Омск: Изд-во Ом-ГТУ, 2012., С.156-159

8. Белим С. В., Шерешик А. Ю. Применение двумерной модели Изинга для построения хеш-функции // ХЫ Неделя науки СПбГПУ: материалы научно-практической конференции с международным участием. Факультет технической кибернетики. СПб.: Изд-во Политехн. ун-та, 2012., С.169-171

Подписано в печать 09.01.2013 Формат 60x84/16. Бумага писчая. Оперативный способ печати. Усл. печ. л. 1,25 Тираж 100 экз. Заказ № 009

Отпечатано в «Полиграфическом центре КАН» тел. (3812) 24-70-79, 8-904-585-98-84.

E-mail: pc_kan@mail.ru 644050, г. Омск, ул. Красный Путь, 30 Лицензия ПЛД № 58-47 от 21.04.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 Выводы.

Актуальность работы. В последнее время применение различных физических моделей в области информационных технологий приобретает все большее распространение. Особенно можно выделить модели статистической физики, такие как модель Изинга. Большинство современных алгоритмов шифрования и хеширования основываются на ограниченном количестве хорошо известных операций, таких как подстановки, перестановки и сложение по модулю 2. Практически все блочные шифры имеют в своей основе ячейку Фейстеля [48]. Развитие криптографических методов защиты информации идет по экстенсивному пути увеличения длины ключа и величины блока данных, что приводит к экспоненциальному росту нагрузки на аппаратную часть вычислительных систем. В связи с этим актуальной является задача поиска новых подходов к построению алгоритмов шифрования и хеширования, использующих принципиально иные подходы. Это подтверждается, например, недавно завершившимся конкурсом на создание нового стандарта хеширования Secure Hash Standard (SHS или SHA-3), который был объявлен институтом NIST [74, 75].

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

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

Первый подход связан с использованием модели Изинга для тестирования генераторов псевдослучайных последовательностей [36]. Вопрос получения качественной случайной последовательности весьма актуален для выработки стойких ключей шифрования, а также проверки стойкости хеш-функций и алгоритмов шифрования. Традиционный подход к тестированию генераторов псевдослучайных последовательностей связан с рассмотрением выходного набора чисел как значений случайной величины. Использование же модели Изинга в качестве теста генератора псевдослучайной последовательности основано на чувствительности алгоритма Метрополиса к входной последовательности псевдослучайных чисел. Если псевдослучайная последовательность далека по своим свойствам от истинно случайной, то критические индексы системы будут отличны от предсказываемых теорией и наблюдаемых в реальном эксперименте.

Кроме тестирования случайной последовательности модель Изинга может быть использована для генерации псевдослучайной последовательности и последующего поточного шифрования на ее основе [84]. Ключом шифрования, при этом, служат данные для инициализации последовательности. Также для шифрования может быть использована модель решеточного газа, близкая к модели Изинга [35]. В работе [92] модель Изинга используется для построения кода Галагера. Данный код с исправлением ошибок использует случайные матрицы, которые авторы и предлагают формировать с помощью алгоритма Метрополиса для модели Изинга. Также в работе приводится методика использования данного кода в криптосистемах с открытым ключом.

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

Предмет исследования. В данной диссертационной работе предметом исследования является методика тестирования псевдослучайных последовательностей и разработка хеш-функций на базе статистической модели Изинга.

Объект исследования. Объектом исследования являются статистические свойства псевдослучайных последовательностей и хеш-функций на основе модели Изинга.

Цели и задачи диссертационной работы. Целью диссертационной работы является разработка новых методов тестирования псевдослучайных последовательностей и хеширования данных. Для достижения цели поставленной в данной работе необходимо решить следующие задачи:

1. Разработать методику тестирования псевдослучайных последовательностей, использующую чувствительность алгоритма Метрополиса для двумерной и трехмерной моделей Изинга к входным данным.

2. С помощью разработанной методики провести тестирование широко распространенных генераторов псевдослучайных последовательностей для определения предпочтительных параметров используемых рекуррентных соотношений.

3. Разработать хеш-функцию, использующую для перемешивания данных двумерную и трехмерную модели Изинга.

4. Провести сравнение разработанных хеш-функций и выявить наиболее предпочтительные параметры модели.

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

Научная новизна работы заключается в следующем:

1. Разработана новая методика тестирования псевдослучайных последовательностей, позволяющая, в отличие от статистических тестов, не просто давать качественную оценку последовательности, но и указывать какой именно параметр последовательности не удовлетворяет условиям задачи.

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

3. Впервые для построения алгоритма хеширования данных применена двумерная и трехмерная модели Изинга.

4. Разработан алгоритм хеширования, не уступающий по криптографическим свойствам широко распространенным современным хеш-функциям, однако обладающий вариативностью размеров входных и выходных данных без дополнительного «ручного» изменения констант алгоритма.

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

Основные научные положения, выносимые на защиту:

1. Методика тестирования псевдослучайных последовательностей на основе модели Изинга позволяет выявлять последовательности применимые в алгоритмах с заданной трудоемкостью. В случае невозможности применения псевдослучайной последовательности предложенная методика позволяет выявить, какой именно параметр последовательности не соответствует требованиям задачи.

2. Генератор псевдослучайных последовательностей Фибоначчи и вихрь Мерсена обладают достаточно хорошими свойствами, тогда линейный конгруэнтный генератор не всегда проходит тест на длину периода последовательности. Существуют параметры линейного конгруэнтного генератора, не обладающие достаточными статистическими свойствами, однако обеспечивающие производство качественной выходной последовательности.

3. Алгоритм Метрополиса для модели Изинга обладает хорошими перемешивающими свойствами и может быть использован для построения функции хеширования данных.

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

Апробация работы. Основные положения диссертационной работы представлялись и обсуждались на следующих конференциях и семинарах: II Межвузовская научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2010; XIII Международная заочная научно-практическая конференция «Наука и современность - 2011», г. Новосибирск, 2011; Четвертая региональная научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2012; IV Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоровские чтения)», г. Санкт-Петербург, 2012.

Публикации. Результаты диссертационной работы были представлены в 8 научных работах, в том числе 3 статьи в журналах из списка периодических изданий, рекомендованных ВАК.

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

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения, библиографического списка и изложена на 97 страницах машинописного текста. Содержит 25 рисунков и 8 таблиц. Библиографический список литературы состоит из 105 наименований.

3.6 Выводы

1. Разработан алгоритм хеширования на базе модели Изинга. Применен новый подход к проектированию хеш-функции позволяющий достаточно гибко изменять размер внутреннего блока и размер хеш-значения. Даны рекомендации по выбору параметров алгоритма.

2. Трехмерная модель предпочтительнее двухмерной, поскольку для трехмерной модели очевидно быстрее происходит перемешивание из за большего количества связей между элементами. Также для успешной работы она требует меньших значений температуры.

3. Температуру системы стоит выбирать тем выше, чем меньше линейный размер решетки.

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

5. С увеличением размера решетки уменьшается скорость работы и увеличивается число шагов моделирования необходимое для достижения лавинного эффекта.

6. При правильном выборе параметров алгоритма, можно добиться для хеш-функции достаточно высокой эффективности, не уступающей эффективности широко известных алгоритмов МЛ5 и 8НА-1.

Заключение

1. Разработана методика тестирования псевдослучайных последовательностей на основе алгоритма Метрополиса для модели Изинга. Показано, что:

1.1 Недостаточный период псевдослучайной последовательности приводит к отсутствию точки пересечения куммулянтов Биндера и, как следствие, невозможности определения температуры фазового перехода.

1.2 Отклонение от равномерного распределения значения членов псевдослучайной последовательности приводит к неверным значениям критических индексов.

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

2. Проведено тестирование наиболее распространенных генераторов псевдослучайных последовательностей с помощью разработанной методики для двумерной и трехмерной модели Изинга. Показано, что:

2.1 Линейный конгруэнтный генератор производит последовательность с равномерным периодом, но не всегда достаточно длинным периодом. Существуют параметры линейного конгруэнтного генератора, не удовлетворяющие достаточным статистическим свойствам, однако обеспечивающие производство качественной выходной последовательности.

2.1 Генератор Фибоначчи с запаздыванием обладает как хорошим распределением, так и достаточно длинным периодом.

2.2 Вихрь Мерсена обладает как хорошим распределением, так и достаточно длинным периодом. Из рассмотренных генераторов вихрь Мер-сенна является наиболее качественным.

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

3.1 Исследование лавинного эффекта показало, что изменение одного бита входного сообщения приводит к изменению в среднем 50% битов в выходном значении.

3.2 Тестирование на наличие коллизий показало, что оно не выше, чем у широко распространенных алгоритмов хеширования.

3.3 Тесты МБТ показали, что качество полученной хеш-функции сопоставимо с широко распространенными алгоритмами МО 5 и 8НА-1.

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

1. Шерешик, А. Ю. Тестирование генераторов псевдослучайных последовательностей с помощью трехмерной модели Изинга // Вестник Омского университета. 2011. № 4. С. 172-174

2. Шерешик, А. Ю. Использование модели Изинга на двухмерной решетке для построения хеш-функции. // Вестник Омского университета. 2012. № 4. С.187-190

3. Белим С. В., Шерешик А. Ю. Тестирование генераторов псевдослучайных последовательностей с помощью трехмерной модели Изинга // Наука и образование. 2012. № 09. С. 1-5.

4. Шерешик А. Ю. Тестирование генераторов псевдослучайных последовательностей с использованием трехмерной модели Изинга // Математические структуры и моделирование. 2010. №21. С.32-36

5. Шерешик А. Ю. Влияние генератора псевдослучайных последовательностей на моделирование фазового перехода // Наука и современность -2011: Сборник материалов XIII Международной научно-практической конференции. Часть 2. С.256-258

6. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии /учеб. пособие. 3-е изд. М. : Гелиос АРВ, 2005

7. Биндер К., Хеерман Д.В. Моделирование методом Монте-Карло в статистической физике. М., 1995.

8. Вервейко В.М., Пушкарев А., Цепурит Т. Функции хэширования: классификация, характеристика, сравнительный анализ. Радиотехника. Вып. 126. 2002. С. 172-180

9. Гинзбург С.Л. Определение фиксированной точки и критических индексов // ЖЭТФ (Журнал экспериментальной и теоретической физики).- 1975.-Т.68, N 1. С.273-286.

10. Гулд X., Тобочник Я. Компьютерное моделирование в физике: В 2-х частях. Ч. 2: Пер. с англ. М.: Мир, 1990. - 400 с.

11. Диффи У., Хеллман М. Э. Защищенность и имитостойкость. Введение в криптографию // ТИИЭР. 1979. - Т. 67. - №3.

12. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.: Наука, 2-е издание, 1982. - 290 с.

13. Жуков И.Ю., Иванов М.А., Осмоловский С.А. Принципы построения генераторов псевдослучайных кодов, используемых при построении стойких криптоалгоритмов // Проблемы информационной безопасности. Компьютерные системы. 2001. № 1. С. 55-65.

14. Иванов М.А., Чугунков И.В. Теория, применение и оценки качества генераторов псевдослучайных последовательностей. М.: Изд-во Кудиц-образ, 2003. 238 с.

15. Камилов И. К., Муртазаев А. К., Алиев X. К. Исследование фазовых переходов и критических явлений методами Монте-Карло. УФН, 169:7 (1999), 773-795

16. Клейнен Дж. Статистические методы в имитационном моделировании. В 2-х т. - М.: Статистика, 1978. - 221 е., 335 с.

17. Кнут Д. Э. Исскуство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ. -М.: Издательский дом "Вильяме", 2007. 832 с

18. Кнут, Д.Э. Искусство программирования. Том 3. Сортировка и поиск, 2-е изд. Пер. С англ.; Уч. пос. М.: "Вильяме", 2000.

19. Коробейников А. Г., Гатчин Ю. А. Математические основы криптоло-гии: Учеб. пособие. СПб.: СПбГУ ИТМО, 2004. 109 с.

20. Левин В. Ю. О повышении криптостойкости однонаправленных хеш-функций

21. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т.: Пер. с англ. М.: Мир, 1988. Т. 1.430 с.

22. Соболь И. М. Численные методы Монте-Карло. 1973.

23. Шнайер Б. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си. М.: ТРИУМФ, 2002.

24. Adler J. J. Phys. A 16, 3585 (1983)

25. Anderson R. The classification of hash functions. Proc. of the IMA Conference on Cryptography and Coding, Cirencester, December 1993, Oxford University Press, 1995, pp. 83-95.

26. Baillie, C. Lattice spin models and new algorithms : a review of Monte Carlo computer simulations. International Journal of Modern Physics C, Vol.1, Issue 01, (1990), pp.91-117

27. Baxter, R. Exactly Solved Models in Statistical Mechanics (1982), Academic Press Inc. LTD, London

28. Beker H., Piper F. Cipher Systems: The Protection of Communications. -London /Northwood Books, 1982.

29. Biham E. On the Applicability of Differential Cryptoanalysis to Hash Functions. In E.I.S.S Workshop on Cryptographic Hash Functions, pages 25-27, March 1992.

30. Binder K., Phys. Rev. Lett. 47, 693 (1981)

31. Blote H. W. J., Compagner A., Croockewit J. H., Fonk Y. T. J. C., Heringa J. R., Hoogland A., Smit T. S. and van Willigen A. L. Physica A 161, 1 (1989).

32. Blum M., Micalli S. How To Generate Cryptographically Strong Sequences Of Pseudo-Random Bits. SIAM Journal on Computing. 1984. V. 13. P. 850-864.

33. Brent R. P. Uniform Random Number Generators for Supercomputers// Proceedings Fifth Australian Supercomputer Conference, 95-104. Melbourne, 1992

34. Brush S. G. History of the Lenz-Ising Model, Rev. Mod. Phys 39 (1962) 883-893

35. ButeraP., Comi M. Phys. Rev. B 65 (2002) 144431.

36. Campostrini M., Pelissetto A., Rossi P., Vicari E. Phys. Rev. E (2002).

37. Citavicius A., Jonavicius A., Japertas S. Unpredictable Cryptographic Pseudo-Random Number Generator based on Non-linear Dynamic chaotic system// Electronics and electrical engineering. 2007. № 7. P. 29-32.

38. Challa M.S.S., Landau D.P., Binder K., Phys. Rev. B 34, 1841 (1986)

39. Chopard B., Marconi S. "Discrete Physics: a new way to look at cryptography" // CoRR abs/nlin/0504059. 2005.

40. Coddington P.D. Tests of random number generators using Ising model simulations // Int. J. Modern Physics C.- 1996. -V. 7. N 3.- P. 295-303.

41. Cormen T. H.; Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (3rd ed.). 2009. MIT Press and McGraw-Hill.

42. Cover T.M., Thomas J.A. Elements of Information Theory. Wiley. - New York, 1991.

43. Creutz, M. Deterministic Ising Dynamics. Annals of Physics, Vol.167, (1986), pp. 62-72

44. Devroye L., Gyorfi L., Lugosi G. A probabilistic theory of pattern recognition. New York : Springer, 1996.

45. Goldreich O., Goldwasser S., Micali S., How To Construct Random Functions // Journal of the Association for Computing Machinery. 1986. V. 33. №4. P. 792-807.

46. Golomb S W. Shift Register Sequences. Aegean Park Press, 1981. 257 p.

47. Good I. J. The serial test for sampling numbers and other tests for randomness. In Proceedings of the Cambridge Philosophical Society 1953. V. 49, 276-284.

48. Gonnet G. H. Handbook of Algorithms and Data Strustures. Addison-Wesley, 1984.

49. Guida R., Zinn-Justin J. J. Phys. A 31 (1998) 8103.

50. Gustafson H., Dawson E., Nielsen L., Caelli W. A Computer Package For Measuring Strength Of Encryption Algorithms // Journal of Computers & Securi-ty.1994. V. 12 №.8. P. 687-697.

51. Guttmann A. J., Enting I. G. J. Phys. A 26 (1993) 806.

52. Feistel H. Cryptography and Computer Privacy// Scientific American. 1973. V. 228. № 5.P. 15-23.

53. Ferrenberg A M, Landau D P Phys. Rev. B 44 5081 (1991)

54. Fisher M.E., Barber M.N. Scaling Theory for Finite-Size Effects in the Critical Region//Phys. Rev. Lett.- 1972.-V. 28. P. 1516-1519.

55. Fishman G. A., Moore L. R. III. An exhaustive analysis of multiplicative congruential random number generators with modulus 231-1, SIAM Journal on Scientific and Statistical Computing, v.7 n.l, p.24-45, Jan. 1986

56. Hastad J., Impagliazzo R., Levin L., Luby M. A Pseudorandom Generator From Any One-Way Function // SIAM Journal on Computing. 1999. №. 28. P. 13641396.

57. Hellekalek P. Inversive pseudorandom number generators: concepts, results, and links // Winter Simulation Conference (WSC'95). 1995. P. 255262.

58. Heuer H.-O. "Critical crossover phenomena in disordered Ising systems", J. Phys. A, 26, L333-L339. (1993).

59. Holian, B. L., Percus, O. E., Warnock, T. T., and Whitlock, P. A. 1994. Pseudorandom number generator for massively parallel molecular-dynamics simulations. Phys. Rev. E 50, 2, 1607-1615.

60. Ising E. "Beitrag zur Theorie des Ferromagnetismus". Zeitschrift fur Physik, Vol.31, 1925, pp. 253-258

61. Jasch F., Kleinert H. J. Math. Phys. 42 (2001).

62. Kalos M. A., Whitlock P. A. Monte Carlo Methods, Volume I: Basics, Wiley Interscience, New York, 1986.

63. Kelsey J., Schneier B., Wagner D., Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption, Fifth International Workshop Proceedings. 1998.P. 168-188.

64. L'Ecuyer P. Tables of linear congruential generators of different sizes and good lattice structure // Mathematics of computation volume 68, number 225, january 1999, pages 249-260

65. L'Ecuyer P., Blouin F., Couture R. A search for good multiple recursive random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.2, p.87-98, April 1993

66. L'Ecuyer P. and Hellekalek P. Random number generators: Selection criteria and testing. In Random and Quasi-Random Point Sets, P. Hellekalek and G. Larcher, Eds. Lecture Notes in Statistics, 1998. vol. 138. Springer-Verlag, Berlin, Germany. 223-265.

67. Landau D.P., Binder K. A guide to Monte Carlosimulation in statistical physics. Cambridge University Press, 2005.- 427 p.

68. Ledue D, Landau D P, Teillet J Phys. Rev. B 51 12523 (1995)

69. Lehmann E.L. Testing Statistical Hypotheses. Wiley. - New York, 1959.

70. Lehmer D. H. Mathematical methods in large-scale computing units. // Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951). 141-146

71. Loison D., Phys. Lett. A, 257, 83 (1999)

72. Marsaglia G., Bray C., On-Line Random Number Generators and their Use in Combinations. Communications of the ACM, v. 11, m 11, 1968 - pp. 757-759.

73. Matsumoto M., Nishimura T. "Mersenne twister: A 623-dimensionally equi-distributed uniform pseudorandom number generator". ACM Trans, on Modeling and Computer Simulations (1998) 8 (1): 3-30.

74. Maurer U. A universal statistical test for random bit generators // Journal of Cryptology. v.5, n.2, 1992.-pp. 89-105.

75. Menezes A., Oorschot O., Vanstone S. Handbook of Applied Cryptography.—CRC Press, 1996.

76. Metropolis, N & Ulam, S. The Monte Carlo method. Journal of American Statistical Association, Vol.44 (1949), pp. 335-341

77. NIST. 2002. Secure hash standard (SHS). FIPS-186-2, with change notice added in february 2004, U.S. DoC/National Institute of Standards and Technology.

78. NIST. "Federal Register / Vol. 72, No. 212". Government Printing Office,2007

79. Ohta K. and Koyama K. Meet-in-the-Middle Attack on Digital Signature Schemes. In Abstract of AUSCRYPT'90, pages 110-121, 1990.

80. Onsager L. Crystal Statistics. I. A Two-Dimensional Model with a OrderDisorder Transition. //Physical Review, Vol.65 (1944), pp. 117-149

81. Ottavi, H. & Parodi, O. Simulation of the Ising Model by Cellular Automata. Europhysics Letters, Vol.8 (1989), pp. 741

82. Park S. K., Miller K. W. Random Number Generators: Good Ones Are Hard to Find. // Communications of the ACM. v. 31, n. 10, Oct 1988. - pp. 1192-1201.

83. Peczac P., Ferrenberg A.M., Landau D.P. Phys. Rev. B 43, 6087 (1991).

84. Peierls R. On Ising's model of ferromagnetism.// Proc. Cambridge Phil. Soc. 32(1936), 477-481.

85. Pelissetto Andrea, Vicari Ettore "Critical phenomena and renormalization-group theory".// Physics Reports (2002) 368 (6): 549-727.

86. Perez A., Huynh Van Thieng C., Charbouillot S. and Aziza H. "An En/Decryption Machine Based on Statistical Physics" // Applied Cryptography and Network Security. 2012. P. 321-336.

87. Perez, A.; Ottavi, H. & Cotton, M. The Ising model as a test for a personal parallel computer. Computational Materials Science, Vol.4 (1995), pp. 133-142

88. Peterson I. Monte Carlo Physics: A Cautionary Lesson. // Science News. v. 142, n. 25. - 19 Dec 1992. - p. 422.

89. Plackett, R.L. "Karl Pearson and the Chi-Squared Test". International Statistical Review (International Statistical Institute (ISI)) 51 (1): 59-72.

90. Preneel B. Analysis and Design of Cryptographic Hash Functions. PhD thesis, Katholieke University Leuven, January 1993.

91. Quisquater J.-J. and Delescaille J.-P. How Easy is Collision Search. New results and applications to DES. In Advances in Cryptology, Proceedings of CRYP-TO'89, pages 408-415, 1990.

92. Rukhin A. and other. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST special publication 800-22, National Institute of Standards and Technology (NIST), Gaithersburg, MD.

93. Ryabko, B. Y., Stognienko, V. S., and Shokin, Y. I. 2004. A new test for randomness and its application to some cryptographic problems. J. Statist. Plan. Infer. 123, 365—376.

94. Saad D., Kabashima Y., Murayama T. Public key cryptography and error correcting codes as Ising models//arXiv:cond-mat/0008363vl

95. Salman Z., Adler J. "High and Low Temperature Series Estimates for the Critical Temperature of the 3d Ising Model" (1991).

96. Salman Z., Adler J. Int. J. Mod. Phys. C 9 (1998) 195.

97. Shannon C. E. Predication and Entropy in Printed English // Bell Sys-tem Technical Journal. v. 30. - n. 1, 1951.-pp. 50-64.

98. Stallings William, "Cryptography and network security: principles and practice". -Prentice Hall, 1999.

99. Stanley H. E., Introduction to Phase Transitions and Critical Phenomena (Clarendon, Oxford, 1971

100. Uhlenbeck and Goudsmit: Ersetzung der Hypothese vom unmechanischen Zwang durch eine Forderung bezüglich des inneren Verhaltens jedes einzelnen Elektrons. // Die Naturwissenschaften 13, pp 953-4, 1926.

101. Vattulainen, I., Ala-Nissila, T., and Kankaala, K. 1995. Physical models as tests of randomness. Physic. Rev. E 52, 3, 3205-3213.

102. Wang M. Z. Linear complexity profiles and jump complexity, Information Processing Letters, v.61 n.3, p.165-168, Feb. 1997

103. Wang X., Feng D., Lai X., Yu H. Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD // CRYPTO 2004.

104. Wegenkittl S., Matsumoto M. Getting rid of correlations among pseudorandom numbers: Discarding versus tempering. ACM Trails. Mod-el. Comput. Si-muL // 9 (3), 1999. pp. 282-294.

105. Wu Pei-Chi, Multiplicative, congruential random-number generators with multiplier ± 2k 1 ± 2k2 and modulus 2p 1, ACM Transactions on Mathematical Software (TOMS), v.23 n.2, p.255-265, June 1997

106. Zeeb, C. N., and Burns, P. J. "Random Number Generator Recommendation," Report prepared for Sandia National Laboratories, Albuquerque, 1997,

107. Zinn-Justin J. Summation of divergent series: Order-dependent mapping Journal Applied Numerical Mathematics archive Volume 60 Issue 12, December, 2010 Pages 1454-1464