Введение 4
Глава 1. Генераторы псевдослучайных последовательностей 11
1.1. Поточные шифры 11
1.2. Принципы проектирования генераторов ПСП 12
1.3. Создание генератора ПСП на основе поточного шифра RC4 14
1.4. Описание приложения "Генератор RC4" 15
Глава 2. Математические предпосылки 18
2.1. Числа Стирлинга 18
2.1.1. Числа Стирлинга первого рода 18
2.1.2. Числа Стирлинга второго рода 19
2.2. Целочисленные функции 19
2.3. Дискретное преобразование Фурье 19
2.4. Функция ошибок 20
2.5. Функция нормального распределения 20
2.6. Неполная гамма-функция 21
2.7. P-value 21
2.8. Критерий 25
Глава 3. Тестирование генераторов ПСП 27
Глава 4. Графические тесты 28
4.1. Гистограмма распределения элементов 28
4.2. Распределение на плоскости 30
4.3. Проверка серий 33
4.4. Проверка на монотонность 35
4.5. Битовая автокорреляционная функция (АКФ) 37
4.6. Графический спектральный тест 39
4.7. Профиль линейной сложности 41
Глава 5. Подборка тестов Д. Кнута 43
5.1. Проверка равномерности 43
5.2. Проверка несцепленных серий 44
5.3. Проверка интервалов 45
5.4. Проверка комбинаций 46
5.5. Тест собирателя купонов 47
5.6. Проверка перестановок 49
5.7. Проверка на монотонность 50
5.8. Проверка корреляции 50
5.9. Выводы 51
Глава 6. Руководство НИСТ 53
6.1. Частотный тест 55
6.2. Частотный тест в подпоследовательностях 57
6.3. Проверка на равномерность 58
6.4. Проверка на равномерность в подпоследовательностях 59
6.5. Проверка рангов матриц 61
6.6. Спектральный тест 62
6.7. Проверка непересекающихся шаблонов 63
6.8. Проверка линейной сложности 65
6.9. Проверка серий 66
6.10. Стратегия тестирования и интерпретация результатов 67
6.10.1 Выбор тестируемого генератора 68
6.10.2 Генерация последовательностей для тестирования 68
6.10.3 Исполнение тестов и анализ результатов 70
Глава 7. Система оценки статистических свойств «DIEHARD» 73
7.1. Проверка дней рождения 74
7.2. Проверка пересекающихся перестановок 76
7.3. Выводы 78
Глава 8. Создание системы оценки качества генераторов псевдослучайных
последовательностей 79
8.1. Инструменты разработки 79
8.2. Функционал системы 80
8.3. Описание основных классов приложения 81
8.4. Запуск приложения 84
8.5. Выбор и настройка тестов 86
8.6. Окно тестирования 88
8.7. Окно результатов 89
8.8. Сравнение с аналогами 90
Заключение 92
Список литературы 94
Приложение
Купить

В настоящее время множество полезных применений находят числа, которые выбираются случайным образом, так называемые последовательности случайных чисел (ПСЧ). Они могут применяться при моделировании различных явлений для повышения адекватности моделей. Для решения сложных задач численного анализа была разработана специальная методика, также использующая случайные числа. Последовательности случайных чисел используются в компьютерной графике, а также являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов.
Особую роль ПСЧ играют в криптографии. Например, они могут применяться в качестве ключевых последовательностей. Корректная реализация асимметричных криптоалгоритмов требует добавления к каждой порции открытого текста нескольких случайных байт. Случайные числа используются также при блочном шифровании и хэшировании.
Следует отметить, что получение подобных чисел сложно, т. к. любые алгоритмы и технологии строятся таким образом, чтобы результат их работы был предсказуем. Тем не менее в настоящее время уже разработано достаточно большое количество различных генераторов ПСЧ. В общем случае все они должны удовлетворять следующим основным требованиям:
• эффективность;
• невозможность повторной генерации выработанной ПСЧ;
• мультиплатформенность;
• простота программной реализации.
Однако практика показывает, что реализовать генератор ПСЧ, удовлетворяющий всем вышеперечисленным критериям, достаточно сложно.
В настоящее время широкое распространение получили программные генераторы, вырабатывающие псевдослучайные последовательности чисел
(ПСП), т. е. такие последовательности, которые генерируются с помощью детерминированных рекуррентных формул. Псевдослучайными эти последовательности называют потому, что фактически они, даже пройдя все тесты на независимость и равномерность распределения, остаются полностью детерминированными.
Можно выделить следующие задачи, для решения которых используются генераторы ПСП:
• техническое диагностирование компонентов компьютерных систем(КС).
• контроль хода выполнения программ с использованием сторожевых процессоров.
• помехоустойчивое кодирование.
• защита информации.
Во всех вышеперечисленных случаях генераторы ПСП используются либо непосредственно, либо в составе генераторов случайных последовательностей, либо на их основе строятся алгоритмы хеширования информации. Именно от свойств генераторов ПСП, особенно в тех случаях, когда необходимо обеспечить устойчивую работу КС при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации.
Подобные генераторы ПСП должны удовлетворять нескольким дополнительным требованиям:
• числа в генерируемой последовательности должны быть равномерно
распределены и независимы, т. е. должны быть некоррелированы;
• период последовательности должен иметь, возможно, большую длину.
Непредсказуемость генераторов ПСП основывается на недоказуемом предположении, что аналитику не хватит ресурсов (вычислительных, временных или стоимостных), для того чтобы инвертировать функцию обратной связи или функцию выхода. Теория сложности вычислений, к сожалению, не в состоянии дать нижнюю границу сложности анализируемого алгоритма инвертирования. Иначе говоря, никогда нет гарантии, что алгоритм, сложность которого анализируется, самый эффективный из всех возможных.
В связи с этим задачу построения непредсказуемого генератора ПСП сводят к задаче построения статистически безопасного генератора.
Статистически безопасный генератор должен удовлетворять следующим требованиям:
• ни один статистический тест не обнаруживает в ПСП каких-либо закономерностей, иными словами не отличает эту последовательность от истинно случайной;
• нелинейное преобразование, используемое для построения генератора ПСП, должно обладать свойством «размножения» искажений - все выходные (преобразованные) векторы возможны и равновероятны независимо от исходного вектора;
• при инициализации случайными значениями генератор порождает статистически независимые ПСП.
О целесообразности данного подхода косвенно свидетельствуют следующие факты:
• при проведении международного конкурса AES (Advanced Encryption Standard - американский, а де-факто - международный стандарт шифрования) для оценки качества алгоритмов-участников активно использовались результаты их статистических исследований;
• Национальный институт стандартов и технологий (НИСТ) США выпустил многостраничное руководство «А statistical test suite for random and pseudorandom number generators for cryptographic applications»по проведению статистических исследований криптографических генераторов ПСП (т. е. генераторов, к которым предъявляются наиболее жесткие требования), методам оценки их результатов.
Таким образом, можно сделать вывод, что исследование статистических свойств формируемых генератором последовательностей является основным моментом при оценке качества последнего. В настоящее время при разработке программных средств генерации ПСП сталкиваются с проблемой отсутствия инструментальных средств, полноценной системы для статистического исследования формируемых последовательностей.
Для оценки статистических свойств псевдослучайных последовательностей используются следующие наборы тестов (табл.1).
Анализ указанных наборов показывает, что всем им присущи следующие недостатки:
• отсутствие графических тестов;
• отсутствие средств настройки параметров тестирования;
• жесткие рамки для тестируемой последовательности;
• отсутствие средств оценки корреляции между последовательностями;
• сложные для понимания неподготовленному пользователю результаты тестирования.
В связи с этим возникает необходимость создания системы, свободной от указанных недостатков.
Можно сформулировать следующие свойства, которые должна иметь полнофункциональная система для оценки качества генераторов ПСП {1}:
• Полнота тестов. Каждый отдельно взятый (даже очень сильный) тест можно «обмануть», т.е. сформировать заведомо плохую последовательность, не удовлетворяющую совокупности требований, предъявляемых к качественной ПСП, но успешно проходящую рассматриваемый тест. Учитывая, что задача определения минимально допустимой совокупности тестов вряд ли имеет решение, должны быть реализованы все тесты, рекомендуемые для исследования генераторов, к качеству выходных последовательностей которых предъявляются наиболее жесткие требования. При этом система должна содержать как оценочные, так и графические тесты. Ни одна из существующих систем не удовлетворяет этому требованию.
• Возможность тестирования несколько последовательностей.
Для принятия решения о свойствах генератора недостаточно протестировать одну последовательность - требуется испытание множества последовательностей, как правило, равного — ,где уровень значимости
теста. В связи с этим система оценки качества должна иметь возможность тестировать группу последовательностей.
• Оценка корреляции. В качественных ПСП должна отсутствовать корреляция между отдельными выборками. Кроме этого, в ряде случаев нелинейные преобразования, осуществляемые функцией обратной связи или функцией выхода генератора, состоят из нескольких шагов (раундов, уровней и пр.). Система должна содержать средства для анализа изменений, вносимых каждым шагом преобразования.
• Настройка параметров тестирования. Пользователь должен иметь возможность настраивать параметры тестирования, например, задавать границы для количественных характеристик тестов, длины подпоследовательностей и т.д. В существующих системах большинство параметров, как правило, фиксировано.
• Интерпретация результатов. Результатом выполнения оценочного теста является численная характеристика. Зачастую для того, чтобы трактовать полученное значение, необходимо знать структуру теста. Поэтому система должна представлять результат в виде, понятном даже неподготовленному пользователю. В существующих системах такая возможность отсутствует.
Таким образом, целью моей работы было разработать единую систему оценки качества генераторов ПСП, наиболее полно удовлетворяющую свойствам, которые должна иметь полнофункциональная система для исследования статистических свойств ПСП [стр.8, {1}] .
Для реализации поставленной задачи я выбрал наиболее прозрачный подход, собрав в одной программе все наиболее известные тесты:
1. Графические тесты.
2. Подборку тестов Д. Кнута.
3. Тесты системы "DIEHARD".
4. Тесты НИСТ.
На мой взгляд, возможность проверить ПСП на таком наборе тестов даст наиболее точный ответ о её качестве, так как недостатки одних тестов компенсируются достоинствами других. Так, к примеру, Проверку серий, Проверку линейной сложности и Спектральный тест можно анализировать не только на графическом, визуальном уровне, но так же оценив статистические данные, так как интерпретация результатов графических тестов зависит от конечного пользователя. Проще говоря, посмотрев на диаграмму один пользователь скажет, что последовательность случайна, а другой будет считать, что она всё же неслучайна. Получив данные статистического теста, с численной характеристикой, пользователь уже наглядно получит однозначный ответ о прохождение теста.
Основными задачами дипломной работы являются:
1. Изучить и проанализировать существующие методы тестирования псевдослучайных последовательностей.
2. Разработать приложение для тестирования современных генераторов ПСП, используя существующие статистические методики оценки качества ПСП.
3. Осуществить сравнение с существующими аналогами.

Купить