Содержание к диссертации
Введение 1 6
1. Теория и применение генераторов псевдослучайных последовательностей 1 14
1.1. Функции генераторов псевдослучайных последовательностей в компьютерных системах ответственного назначения 1 14
1.2. Классификация генераторов псевдослучайных последовательностей 1 21
1.3. Конгруэнтные генераторы 1 22
1.4. Генераторы на основе регистров сдвига с обратными связями . 1 28
1.5. Генераторы, функционирующие в недвоичных конечных полях 1 32
1.5.1. Основы теории конечных полей 1 32
1.5.2. Сложение и умножение в поле GF{1) 1 34
1.5.3. Устройства, функционирующие в полях Галуа 1 36
1.5.4. Свойства генераторов М-последовательностей 1 38
1.6. Генераторы на основе криптографических преобразований 1 39
1.6.1. Блочные генераторы 1 40
1.6.2. Поточные генераторы 1 43
1.6.3. Генераторы на основе односторонних функций 1 46
1.6.4. Стохастические генераторы псевдослучайных последовательностей 1 49
1.7. Требования к генераторам псевдослучайных последовательностей 1 50
1.7.1. Непредсказуемость генераторов 1 50
1.7.2. Статистическая безопасность генераторов 1 51
1.8. Выводы 1 53
2. Методы проведения исследований статистических свойств генераторов псевдослучайных последовательностей 1 55
2.1. Графические тесты 1 56
2.2. Оценочные тесты 1 63
2.2.1. Математические предпосылки 1 63
2.2.2. Подборка тестов Д. Кнута 1 66
2.2.3. Система оценки статистических свойств «DIEHARD» 1 70
2.2.4. Руководство НИСТ 1 77
2.2.5. Тесты для байтовых последовательностей 1 100
2.3. Оценка результатов тестирования 1 102
2.4. Выводы 1 106
3. Программный комплекс для исследования статистических свойств псевдослучайных последовательностей 1 108
3.1. Структура комплекса 1 109
3.2. Система оценки качества псевдослучайных последовательностей 1 110
3.3. Система оценки периода последовательности 1 116
3.4. Система оценки корреляции между последовательностями 1 118
3.5. Выводы 1 123
4. Исследование статистических свойств генераторов псевдослучайных последовательностей 1 124
4.1. Методика и параметры тестирования 1 124
4.1.1. Генерация последовательностей для тестирования 1 124
4.1.2. Исполнение набора статистических тестов 1 126
4.1.3. Анализ прохождения статистических тестов 1 132
4.2. Использование теста «Автокорреляционная функция» для выявления периодичности 1 133
4.3. Исследование блочных генераторов 1 134
4.4. Выводы 1 140
5. Разработка и исследование стохастических генераторов псевдослучайных последовательностей 1 141
5.1. Стохастическое преобразование информации. /?-блок 1 141
5.2. Стохастические генераторы многоразрядных псевдослучайных последовательностей RFSR 1 147
5.3. Анализ непредсказуемости стохастических генераторов RFSR 1 147
5.4. Двухступенчатые стохастические генераторы многоразрядных случайных последовательностей 1 152
5.5. Стохастические генераторы псевдослучайных последовательностей с многораундовой функцией обратной связи 1 154
5.6. Алгоритмы стохастического преобразования с динамически изменяемой в процессе работы таблицей преобразования 1 162
5.7. Универсальный блок стохастического преобразования RExt-16 1 164
5.8. Исследование статистических свойств стохастических генераторов 1 166
5.9. Выводы 1 173
Заключение 1 174
Список литературы 1 177
Приложения 2 1
Приложение 1. Акты о внедрении 2 2
Приложение 2. Примеры, иллюстрирующие работу тестов 2 6
Приложение 3. Система оценки качества генераторов псевдослучайных последовательностей. Руководство пользователя 2 35
Приложение 4. Система оценки корреляции между файлами. Руководство пользователя 2 41
Приложение 5. Система оценки периода последовательности. Руководство пользователя 2 48
Приложение 6. Система генерации паролей. Руководство пользователя 2 50
Приложение 7. Система генерации псевдослучайных последовательностей «Л-генератор». Руководство пользователя 2 54
Приложение 8. Система для анализа стохастических генераторов. Руководство пользователя 2 63
Приложение 9. Список сокращений 2 66
Приложение 10. Список терминов 2 67
Введение к работе
Неотъемлемым элементом любой компьютерной системы (КС), независимо от ее сложности и назначения, являются программные и программно- аппаратные средства генерации псевдослучайных последовательностей (ПСП). Можно выделить следующие задачи, для решения которых используются гене- раторы ПСП:
техническое диагностирование компонентов КС (в том числе встроенное диагностирование) [31; 54];
контроль хода выполнения программ с использованием сторожевых процессоров [29; 37; 54];
помехоустойчивое кодирование [42; 43; 46];
защита информации [4; 8; 15; 30; 35].
Во всех вышеперечисленных случаях генераторы ПСП используются ли- т бо непосредственно, либо в составе генераторов случайных последовательно стей, либо на их основе строятся алгоритмы хеширования информации. В последних двух случаях качество операций генерации случайных последовательностей и хеширования определяется в первую очередь качеством используемых генераторов ПСП. Таким образом, именно от свойств генераторов ПСП, особенно в тех случаях, когда необходимо обеспечить устойчивую работу КС при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации. К ним предъявляются жесткие требования, в первую очередь , по таким параметрам, как непредсказуемость, статистические и периодические свойства.
Основа любого генератора ПСП - нелинейное преобразование, используемое либо в качестве функции обратной связи генератора (режим Output Feedback (OFB)), либо в качестве функции выхода (режим Counter (CNT)). В настоящее время существуют несколько подходов к построению этих преобразований. Перечислим основные из них.
Использование многократного повторения одной и той же раундовой операции, в состав которой входят преобразования замены и перестановки. Смысл конструкции - обеспечить свойства рассеивания и перемешивания информации, которые, согласно К.Шеннону, необходимы любому непредсказуемому генератору ПСП. Подход применяется при построении блочных генераторов. Все существующие государственные стандарты: российский (ГОСТ 28147-89 [9; 10; 18]) и американский (AES [63]) используют этот принцип. Недостатком генераторов данного класса является низкое быстродействие. Это цена, которую приходится платить, чтобы обеспечить непредсказуемость формируемых последовательностей. Однако утверждение о наличии у генератора этого свойства основывается на недоказуемом предположении о том, что у противника не хватит ресурсов (вычислительных, временных или материальных) чтобы инвертировать используемую нелинейную функцию обратной связи или выхода.
Использование односторонних функций. Понятие односторонней функции [79; 84] введено Диффи и Хеллманом в 1978 году, однако до сих пор ни одной односторонней функции не найдено. Существуют и реально используются лишь функции-кандидаты на звание односторонних, иначе говоря, функции которые вероятно являются односторонними. Задача инвертирования этих функций эквивалентна решению трудной математической задачи, например, задачи факторизации больших чисел, на основе которой построен генератор RSA, долгое время являвшийся де-факто неофициальным мировым стандартом для генераторов ПСП этого класса. Недостатки генераторов этого класса те же, что и в предыдущем случае, причем их быстродействие во много раз ниже, чем у блочных генераторов, которые сами считаются медленными.
Все остальные подходы к построению генераторов ПСП позволяют в той или иной степени решить проблему быстродействия, но обязательно в ущерб свойству непредсказуемости. Подавляющее большинство фактов компрометации генераторов ПСП ответственного назначения относятся именно к алгоритмам, отличным от двух, описанных выше.
Итак, существует трудно разрешимое противоречие между непредсказуемостью генераторов ПСП, с одной стороны, и их производительностью и эффективностью реализации. Поэтому актуальной научной задачей является создание новых алгоритмов генерации ПСП, сочетающих в себе непредсказуемость, высокое быстродействие и эффективную реализацию на различных платформах. Одним из направлений решения данной задачи является исследование стохастических алгоритмов формирования цифровых последовательностей [42-46] и разработка на их основе непредсказуемых генераторов ПСП. Указанные алгоритмы генерации ПСП основаны на использовании стохастических сумматоров, т. е. сумматоров с непредсказуемым результатом работы (R-блоков), впервые предложенных С.А.Осмоловским для решения задач помехоустойчивого кодирования. Стохастические генераторы ПСП сочетают в себе высокое качество формируемых последовательностей и эффективную программную и аппаратную реализацию.
Вторая проблема, с которой приходится сталкиваться при разработке программных средств генерации ПСП, - отсутствие инструментальных средств для статистического исследования формируемых последовательностей. Более того, этим исследованиям уделялось мало внимания. За последние несколько лет ситуация кардинально изменилась, специалисты признали значимость статистического тестирования. Об этом свидетельствуют многочисленные факты.
Национальный Институт Стандартов и Технологий США (НИСТ) выпустил многосотстраничное руководство [60; 82; 83; 85] по статистическому тестированию генераторов ПСП ответственного назначения.
При проведении многолетнего открытого международного конкурса (завершившегося в 2001 году) на принятие вышеупомянутого стандарта AES для оценки алгоритмов-кандидатов активно использовались статистические исследования ПСП.
Наконец, появились программные комплексы для проведения статистических испытаний генераторов ПСП (наиболее известные из них - DIEHARD [75; 77], CRYPT-X [67]).
Однако существующие программные комплексы либо являются узкоспециализированными (например, DIEHARD предназначен для исследования лишь конгруэнтных генераторов), либо малофункциональными (например, CRYPT-X содержит всего лишь пять тестов, в то время как в руководстве НИСТ описано шестнадцать). Отсутствуют программные комплексы, реализующие графические тесты оценки статистических свойств ПСП. Поэтому актуальной научной задачей является создание программного комплекса, позволяющего проводить полнофункциональное статистическое исследование ПСП, в том числе проводить испытания на всех существующих графических и оценочных тестах, оценивать корреляцию между различными выборками последовательности и др.
Целями работы являются:
разработка и исследование стохастических алгоритмов генерации псевдослучайных последовательностей;
разработка программного комплекса для оценки качества псевдослучайных последовательностей.
Для достижения поставленных целей необходимо решение следующих задач:
формулировка требований, предъявляемых к генераторам ПСП ответственного назначения;
классификация существующих алгоритмов генерации ПСП;
оценка существующих методов анализа непредсказуемости ПСП;
формулировка требований, предъявляемых к системе оценки качества ПСП, и оценка существующих систем аналогичного назначения;
разработка структуры программного комплекса для исследования свойств генераторов ПСП;
исследование качества лучших из существующих алгоритмов генерации ПСП;
разработка и исследование стохастических алгоритмов генерации ПСП;
разработка алгоритма анализа непредсказуемости стохастических генераторов ПСП;
разработка рекомендаций по использованию статистических тестов для исследования генераторов ПСП.
Методами исследований являются: теория конечных полей [2; 3; 6; 33; 40; 54], теория линейных последовательностных машин [16; 53; 55], теория вероятностей [17], математическая статистика [19; 36; 38].
Научная новизна работы состоит в том, что:
сформулированы требования, предъявляемые к генераторам ПСП ответственного назначения;
разработана классификация существующих алгоритмов генерации ПСП;
проведен анализ существующих методов анализа непредсказуемости ПСП;
сформулированы требования, предъявляемые к системе оценки качества ПСП, и проведен анализ существующих систем аналогичного назначения;
разработана структура программного комплекса для исследования свойств генераторов ПСП;
сформулированы принципы проектирования стохастических генераторов ПСП;
предложен алгоритм стохастического преобразования с динамически изменяющейся в процессе работы таблицей преобразования;
предложены алгоритмы генерации ПСП, основанные на использовании блоков стохастического преобразования информации в цепи обратной связи;
предложены стохастические алгоритмы генерации ПСП, реализующие многораундовые функции обратной связи;
на основе предложенных стохастических методов генерации ПСП разработан алгоритм хеширования информации;
разработан алгоритм анализа непредсказуемости стохастических генераторов ПСП.
Практическая ценность работы заключается в следующем:
разработан программный комплекс, предназначенный для исследования статистической безопасности алгоритмов генерации ПСП;
исследована возможность использования существующих статистических тестов для анализа статистической безопасности и непредсказуемости алгоритмов генерации ПСП;
разработаны программные модели существующих генераторов ПСП;
проведено исследование качества лучших из существующих алгоритмов генерации ПСП;
разработаны программные модели стохастических генераторов ПСП, проведено исследование их статистических свойств;
разработаны программные средства анализа непредсказуемости стохастических генераторов ПСП;
разработаны рекомендации по использованию статистических тестов для исследования генераторов ПСП.
Основные положения, выносимые на защиту:
структура программного комплекса для исследования статистических свойств генераторов ПСП, включающего в себя систему проведения графических и оценочных статистических тестов; систему оценки периода последовательностей; систему оценки корреляции между последовательностями;
стохастические алгоритмы генерации ПСП;
алгоритм анализа непредсказуемости стохастических генераторов ПСП;
алгоритм стохастического преобразования с динамически изменяющейся в процессе работы таблицей преобразования;
результаты исследования блочных, поточных и стохастических генераторов ПСП;
рекомендации по использованию статистических тестов для анализа периодичности ПСП и раундовых преобразований блочных генераторов ПСП.
Работа состоит из введения, пяти глав, заключения и приложений.
В первой главе рассматриваются общие принципы построения генераторов ПСП. Предложена их классификация, описаны основные строительные блоки, используемые для создания генераторов каждого типа. Особое внимание уделяется требованиям, предъявляемым к генераторам ПСП.
Вторая глава посвящена методам исследования статистических свойств генераторов ПСП. Рассмотрены существующие системы оценки, указаны их достоинства и недостатки. Показана необходимость создания единого программного комплекса для исследования статистических свойств генераторов ПСП.
Третья глава содержит описание разработанного программного комплекса для исследования статистических свойств генераторов ПСП. Обосновывается структура комплекса, рассматриваются алгоритмы работы его основных частей.
Четвертая глава посвящена исследованию статистических свойств генераторов ПСП. Приведены результаты тестирования существующих генераторов, сделаны выводы об их свойствах. Показана возможность использования графических тестов для оценки периодических свойств последовательностей и для исследования раундовых преобразований блочных генераторов.
Пятая глава посвящена алгоритмам генерации ПСП, использующим блоки стохастического преобразования. Рассмотрена структура блоков, сформулированы принципы построения стохастических генераторов ПСП. Описываются разработанные алгоритмы стохастического преобразования с динамически изменяющейся в процессе таблицей преобразования; стохастические алгоритмы генерации ПСП. Предлагается метод анализа непредсказуемости стохастических генераторов ПСП. Проведены результаты исследования стохастических генераторов ПСП.
Результаты работы докладывались и обсуждались:
на международном форуме по проблемам науки, техники и образования в г. Москве в декабре 1997 г.;
на V конференции «Проблемы защиты информации в системе высшей школы» в г. Москве в январе 1998 г.;
на VI конференции «Проблемы защиты информации в системе высшей школы» в г. Москве в январе 1999 г.;
на VII конференции «Проблемы защиты информации в системе высшей школы» в г. Москве в январе 2000 г.;
на научной сессии МИФИ — 2000 в г. Москве в январе 2000 г.;
на научной сессии МИФИ - 2001 в г. Москве в январе 2001 г.;
на научной сессии МИФИ - 2003 в г. Москве в январе 2003 г.
Результаты диссертационной работы внедрены в учебные процессы МИФИ и Военной академии ракетных войск стратегического назначения имени Петра Великого, а также в следующие разработки:
ОКР Всероссийского НИИ Автоматизации Управления в Непромышленной Сфере;
ОКР Московского НИИ Приборной автоматики.
Практическое использование результатов диссертации подтверждено 4 актами о внедрении (см. приложение 1).
По теме диссертационной работы опубликовано 10 печатных работ, в том числе монография, изданная во внешнем издательстве, две статьи в журнале «Безопасность информационных технологий», получен один патент на изобретение.
