Основные теоретические сведения. Криптографический генератор - это аппаратно или программно реализованный имитатор источника равномерно распределенной случайной последовательности (РРСП)
Криптографический генератор - это аппаратно или программно реализованный имитатор источника равномерно распределенной случайной последовательности (РРСП) чисел, которая вычисляется по известному детерминированному рекуррентному соотношению. Основное требование к
выходной последовательности х криптографического генератора, г =0^о, состоит в минимальных отличиях по статистическим характеристикам последовательности х от РРСП.
Тесты, применяемые для оценки качества КГ, делятся на графические и оценочные [3].
К графическим тестам относится: гистограмма распределения элементов последовательности; распределение на плоскости; проверка серий; автокорреляционная функция; графический спектральный тест; проверка на монотонность; профиль линейной сложности.
Гистограмма распределения элементов - данный метод позволяет оценить равномерность распределения символов, а также определить частоту появления
каждого символа. Для исследуемой последовательности ^ ^} = \,п
подсчитывается сколько раз встречается каждый элемент, после чего строиться график зависимости числа появления элементов от их численного представления.
Распределение на плоскости - метод предназначен для определения зависимостей между элементами последовательностей. Построение
распределение на плоскости осуществляется по правилу ^, yi+i у = 1, (п -1). Если между элементами последовательности связь отсутствует, то точки на плоскости расположены хаотично, в случае когда на плоскости наблюдаются «узоры» - между элементами последовательности существует взаимосвязь, т.е. последовательность не является случайной.
Проверка серий - данный метод позволяет оценить равномерность распределения символов в исследуемой последовательности на основе анализа частоты появления нулей и единиц и серий состоящих из k бит. Построение осуществляется следующим образом: подсчитывается сколько раз проявляются нули, единицы, серии-двойки (00, 01, 10, 11), серии-тройки (000, 001, 010, 011, 100, 111) и т.д. в битовом представлении исследуемой последовательности
fi~£=\n. Результат представляется в графическом виде. У последовательности, чьи свойства близки к свойствами РРСП разбросы между числом появлений нулей и единиц, между числом появлений серий каждого вида должны стремиться к нулю.
Проверка на монотонность - данный метод позволяет оценить
равномерность распределения символов. В исследуемой последовательности на
основе анализа длин участков невозрастания и неубывания элементов
последовательности. Исследуемая последовательность % ^ = \,п
представляется в виде непересекающихся участков невозрастания и неубывания следующих друг за другом. У последовательности, чьи свойства близки к свойствам РРСП вероятность появления участка невозрастания (неубывания) обратно пропорциональна его длине.
Автокорреляционная функция (АКФ) - данный метод предназначен для оценки корреляции между сдвинутыми копиями исследуемой
последовательности
?{• 3=1,л. Метод позволяет обнаруживать зависимость
между подпоследовательностями исследуемой последовательности. Битовая
АКФ. Исследуемая последовательность ?J 3 = Мпредставляется в битовом
виде и затем нормируется по правилу уг-=(-1) ~^1' ,i = \,n. После этого
вычисляются всплески корреляции:
Символьная АКФ. Исследуемая последовательность нормируется по
R-1 ._____
правилу yi= Y^ 4-^' 2J J = \,n, R - разрядность числа, а,-- двоичная запись
7=0 i -го элемента исследуемой последовательности. Далее вычисляются всплески корреляции.
Для последовательности, чьи свойства близки к свойствам РРСП, значения всплесков корреляции должно стремиться к нулю, во всех точках, кроме тех,чье значение кратно длине последовательности в символах (в битах) для символьной (битовой) АКФ.
Профиль линейной сложности - данный метод позволяет исследовать последовательность на случайность анализируя зависимость линейной сложности последовательности от ее длины. Для исследуемой двоичной
последовательности $ ~£=1,прассматриваются подпоследовательности у
содержащие первые к элементов и строится графическая зависимость линейной сложности L от длины подпоследовательности к. У последовательности, чьи свойства близки к свойствам РРСП линия графика
к должна стремиться к линии L = —.
2 Графический спектральный метод - данный метод позволяет определить равномерность распределения 0 и 1 в исследуемой последовательности на основе анализа высоты выбросов преобразования Фурье. Исследуемая двоичная
последовательность
?}• 3 =1," преобразуется по правилу Yf = 2у; -1 в
последовательность % ~£ = 1,п к которой применяется дискретное
преобразование Фурье. У последовательности, чьи свойства близки к свойствам РРСП число гармоник, чьи длительности значительно превышают среднюю длину гармоники должно стремиться к нулю.
Оценочные тесты, в отличии от графических тестов, позволяют по результатам тестирования сделать практически однозначный вывод о возможности использования криптографического генератора. Существует множество различных оценочных тестов, сгруппированных в наборы: тесты Д.Кнута, тест DieHard, тест NIST и др. [3]. В настоящей практической работе рассматриваются некоторые тесты, входящие в набор NIST.
Частотный тест (frequency test) служит для проверки равномерности появления 0 и 1 в исследуемой последовательности. В исследуемой последовательности длинной п подсчитывается количество нулей w0 и единиц
щ, а затем вычисляется их разница Sn =1-п0.
 |  |
| \S„ |
| ( Л |
| VV2 J |
| I - \~- I 4п IV2 |
Вычисляется статистика s = l—j= и определяется значение Р = erfc
где erfc^y1-erf^y^= \e T dr- дополнительный интеграл вероятностей,
х
2 \ -г2
erfty -j= \e~T dr- функция ошибок.
л1Ж 0
Связь стандартного нормального распределения Ф 4t и функции ошибок имеет вид:
ф«
л[2тг
X
\ e2dr = 0,5 1 + erf
-en V
f X ^
vV2y
Значение P должно быть больше 0,01.
Частотный тест в последовательностях (frequency test within a block)
необходим для проверки равномерности появления 0 и 1 в
подпоследовательности. Исследуемая двоичная последовательность
разбивается на N =
п
М
M -битных последовательностей. Лишние биты
отбрасываются. Определяется доля 1 в каждой подпоследовательности
м
7=1__________________________________________ л^*- л2
| и значение |
| ^7 - |
| м |
Вычисляется статистика ^ = 4M^^-0,5
7=1
Р = /gawc
TV s_ 2 , 2
где: /game ф, х > 1 - /?(а, jc) , р(а, х) =
Гх4~
Г<7
- гамма-функция, Гх #> \ta1e~fdt - неполная гамма-функция.
Значение Р должно быть больше 0,01.
| п H£i 7=1 |
| тест |
| Если |л--0,5|>г |
Тест «дырок» (runs test) служит для проверки равномерности распределения 0 и 1 в исследуемой последовательности на основе анализа количества появлений «блоков» - подпоследовательностей, состоящих из одних 1 или одних 0 («дырок»). Определяется предтестовая статистика я - доля 1 в
исследуемой последовательности ж =
п 4п
считается не пройденным, в противном случае вычисляем статистику
| [ 0, Sj - ei1 |
| 1 , . Затем |
77-1
(количество блоков и «дырок») vn = J]r(k) + 1, где: r(k)
| k1 |
I1, Sj*£i1
| вычисляется Р = erf с |
vn-2nn1-n\
Значение Р должно быть больше 0,01.
2л/2/7л-1-л- \
Проверка рангов матриц (binary matrix rank test) служит для проверки равномерности распределения 0 и 1 в исследуемой последовательности на основе анализа количества появлений матриц различных рангов. Исследуемая
двоичная последовательность длины
п
разбивается на N =
п
MQ
непересекающихся подпоследовательностей. Лишние биты отбрасываются.
Каждая подпоследовательность представляется как бинарная матрица размером tytxQ^.
Определяется ранг каждой матрицы. Пусть FM - число матриц ранга М,
FM_i - число матриц ранга М-1, N -FM -FM_\ - число оставшихся матриц.
Вычисляется статистика
0,28887V 0,57767V 0,13367V
а затем значение Р = igamcf 1,- . Значение Р должно быть больше 0,01.
У 2)
Спектральный тест (spectral test) служит для проверки равномерности 0
и 1 в исследуемой последовательности на основе анализа высоты выбросов
преобразования Фурье. _
Исследуемая двоичная последовательность 4, i = 1,n
преобразовывается в последовательность 4по правилу хг=2^-1. К полученной последовательности применяется дискретное преобразование Фурье S = DFT4l, из которого формируется подпоследовательность S',
содержащая первые —членов S. Члены последовательности S являются
| 0,95п |
комплексными числами. Определяются модули rrij =\Sj\ каждого из элементов последовательности S'. Последовательность т#гдает последовательность выбросов высот преобразования Фурье.
| Вычисляются Т = 3п, N0 = |
и определяется статистика
s
где N1 - число элементов щ , меньших чем Т
V2
Вычисляется значение Р = erf с
ы
Значение P должно быть больше
0,01.
Порядок выполнения работы
2.1. При подготовке к практической работе
На этапе подготовки к практической работе студенты должны, используя литературу [1,2,3], материалы лекций углубить свои знания по следующим вопросам: классификация криптографических генераторов, методы усложнения алгоритмов генерации псевдослучайных последовательностей, графические и оценочные тесты качества криптографических генераторов.
2.2. Во время проведения занятия
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практической работе. Преподаватель разбивает группу студентов на подгруппы, для каждой подгруппы выдается индивидуальное задание на предстоящую лабораторную работу. Индивидуальное задание представляет собой тип криптографического генератора с исходными данными, который требуется исследовать.
В процессе выполнения работы студенты должны:
1. Сформировать, для заданного преподавателем типа
криптографического генератора, псевдослучайную последовательность.
2. Оценить качество криптографического генератора с помощью
рассмотренных в учебных материалах тестов и построить соответствующие
графические зависимости.
3. Сформулировать вывод о возможности использования
криптографического генератора в алгоритмах шифрования.
Содержание отчета
Отчет по практической работе должен включать в себя следующие пункты:
1. Задание на лабораторную работу.
2. Графические зависимости, иллюстрирующие результаты применения графических тестов и таблицу с результатами оценочного тестирования.
3. Выводы о возможности использования заданного криптографического генератора в алгоритмах шифрования.
Контрольные вопросы
1. Классификация криптографических генераторов.
2. Методы улучшения псевдослучайных последовательностей.
3. Графические тесты оценки качества криптографических генераторов.
4. Оценочные тесты качества криптографических генераторов.
Литература
1. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.
2. Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание, 2003.
3. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайной последовательности. – М.: КУДИЦ-ОБРАЗ, 2003.