Выходные данные:

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

Интерфейс программы:

На рис 4.1 приведено главное окно для работы с программой.

Рис. 4.1. Главное окно программы «Cryptographically Strong Key Algorithm and Analysis (CryptoSKA)»

2. ИНСТРУКЦИЯ ПО РАБОТЕ С ПРОГРАММОЙ

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

В начале работы для генерации ключевой последовательности необходимо задать константу смещения (по стандарту 3073). После этого необходимо нажать кнопку с надписью «Сгенерировать». На форме в поле «Сгенерированная ключевая ПСП»

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

При необходимости открыть сформированную ранее тестируемую последовательность, необходимо нажать «Файл» → «Открыть», для сохранения текущей - «Файл» → «Открыть», либо «Файл» → «Открыть как…» в зависимости от необходимости задания имени файла. Для итогового сохранения 77-разрядного ключа в текстовый файл необходимо нажать «Сохранить ключ».

Далее рассмотрим варианты тестирования ключевых последовательностей, обязательно чтобы в поле «Сгенерированная ключевая ПСП» находилась созданная ранее или открытая из файла одна или несколько ключевых последовательностей.

Графические тесты.

1. Тест «Гистограмма распределения элементов».

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

---

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

Рис. 4.2. Окно результата работы теста «Гистограмма распределения элементов»

2. Тест «Распределение на плоскости».

Данный тест предназначен для определения зависимостей между элементами исследуемой последовательности. Построение распределения на плоскости осуществляется следующим образом. На поле размером (R – разрядность чисел исследуемой последовательности) наносятся точки с координатами (x_i; x_i+1), где x_i – элементы исследуемой последовательности x, n – длина последовательности. Далее анализируется полученная картина. Если между элементами последовательности отсутствуют зависимости, то точки на поле расположены хаотично. Если на поле присутствуют зависимости, наблюдаются «узоры» - последовательность не является случайной. Для последовательностей большой длины хорошим результатом является абсолютно черное поле.

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

Рис. 4.3. Окно результата работы теста «Распределение на плоскости»

3. Тест «Проверка на монотонность».

Данный тест позволяет оценить равномерность распределения символов в исследуемой последовательности на основе анализа длин участков невозрастания и неубывания элементов последовательности. Построение производится следующим образом. Исследуемая последовательность графически представляется в виде следующих друг за другом непересекающихся участков невозрастания и неубывания элементов последовательности. У последовательности, чьи статистические свойства близки к свойствам истинно случайной последовательности, вероятность появления участка невозрастания (неубывания) определенного размера зависит от его длины: чем больше длина, тем меньше вероятность. В противном случае последовательность не является случайной.

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

Рис. 4.4. Окно результата работы теста «Проверка на монотонность»

4. Тест «Проверка серий».

Данный тест позволяет оценить равномерность распределения символов в исследуемой последовательности на основе анализа частоты появления нулей и единиц и серий, состоящих из k-бит. Построение осуществляется следующим образом. Подсчитывается, сколько раз встречаются нули, единицы, серии-двойки (00, 01, 10, 11), серии-тройки (000, 001, 010, 011, 100, 101, 110, 111) в битовом представлении исследуемой последовательности. Полученные результаты представляются в графическом виде. У последовательности, чьи статистические свойства близки к свойствам истинно случайно последовательности, разбросы между числом появлений нулей и единиц, между числом появлений серий пар каждого вида и между числом появления серий-троек каждого вида должны стремиться к нулю. В противном случае последовательность не является случайной.

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

---

Рис. 4.5. Окно результата работы теста «Проверка серий»

Оценочные тесты.

1. Тест Д. Кнута «Проверка несцепленных серий».

Цель теста – исследовать последовательность на случайность, анализируя длины несцепленных серий различной длины. Пусть ε = ε₁ε₂…ε_n – двоичная последовательность длины n и m – длина серии. Подсчитывается число появлений всевозможных непересекающихся серий длиной m (лишние биты отбрасываются) и вычисляется статистика:

Полученный результат анализируется при помощи критерия χ² с числом степеней свободы 2^m – 1.

2. Тест Д. Кнута «Проверка комбинаций».

Данный тест определяет равномерность распределения символов в исследуемой последовательности, анализируя различные комбинации чисел в подпоследовательностях. Пусть ε = ε₁ε₂…ε_n – последовательность m-разрядных чисел длины n. Разобьем её на последовательности длинной t каждая (лишние биты отбрасываются). Подсчитывается число подпоследовательностей ν_i, i = , содержащих i различных чисел, и вычисляется статистика:

- числа Стирлинга.

Числом Стирлинга из k по r, обозначаемым или , называется количество неупорядоченных разбиений k-элементного множества на r непустых подмножеств. Явная формула для подсчета чисел Стирлинга следующая:

Полученный результат анализируется при помощи критерия χ² с числом степеней свободы r – 1.

Окно с результатами работы оценочных тестов приведены на рис. 4.6.

Рис. 4.6. Окно результата работы оценочных тестов

α k	0,01	0,025	0,05	0,95	0,975	0,99
1	6,63490	5,02389	3,84146	0,00393	0,00098	0,00016
2	9,21034	7,37776	5,99146	0,10259	0,05064	0,02010
3	11,34487	9,34840	7,81473	0,35185	0,21580	0,11483
4	13,2767	11,14329	9,48773	0,71072	0,48442	0,29711
5	15,08627	12,8325	11,0705	1,14548	0,83121	0,55430
6	16,81189	14,44938	12,59159	1,63538	1,23734	0,87209
7	18,47531	16,01276	14,06714	2,16735	1,68987	1,23904
8	20,09024	17,53455	15,50731	2,73264	2,17973	1,64650
9	21,66599	19,02277	16,91898	3,32511	2,70039	2,08790
10	23,20925	20,48318	18,30704	3,94030	3,24697	2,55821
11	24,72497	21,92005	19,67514	4,57481	3,81575	3,05348
12	26,21697	23,33666	21,02607	5,22603	4,40379	3,57057
13	27,68825	24,7356	22,36203	5,89186	5,00875	4,10692
14	29,14124	26,11895	23,68479	6,57063	5,62873	4,66043
15	30,57791	27,48839	24,99579	7,26094	6,26214	5,22935

Критические значения распределения Пирсона [8]

Сравним полученные нами значения и критические значения распределения с заданным числом степеней свободы и уровнями значимости 0,01 и 0,05 из таблицы критических значений распределения Пирсона, где k – степень свободы, α – уровень значимости:

---

1. по тесту «Проверка несцепленных серий» для серий из 1 цифры получим 0,96 < 24,99579 < 30,58;

2. по тесту «Проверка несцепленных серий» для серий из 2 цифр получим 4,03 < 24,99579 < 30,58;

3. по тесту «Проверка несцепленных серий» для серий из 3 цифр получим 8,38 < 24,99579 < 30,58;

4. по тесту «Проверка комбинаций» для серий из 1 цифры получим 4,32 < 7,81473 < 11,34487.

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

Текст программы находится в Приложении.

---

ЗАКЛЮЧЕНИЕ

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

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

---

Смотрите также файлы

• Раздатка.docx

• Доклад.docx

• Лекция 4.docx

• Лекция 5.docx

• Лекция 1.doc