Статистические тесты генераторов случайных и псевдослучайных чисел

Статистические тесты генераторов случайных и псевдослучайных чисел

Статистические тесты генераторов случайных и псевдослучайных чисел

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

Содержание

Применение

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

Программные пакеты статистических тестов

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

№ Название Автор Организация
1 NIST Statistical Test Suite[1] Andrew Rukhin, et. al. NIST ITL
2 TEST-U01[2] P.L'Ecuyer и др. Universit´e de Montr´eal
3 CRYPT-X[3] Helen Gustafson и др. Queensland University of Technology
4 The pLab Project[4] Peter Hellekalek University of Salzburg
5 DIEHARD[5] George Marsaglia Florida State University
6 ENT[6] John Walker Autodesk, Inc.
7 The Art Of Computer Programming Vol. 2 Seminumerical Algorithms[7] Дональд Кнут Stanford University
8 Handbook of Applied Cryptography[8] Alfred Menezes и др. CRC Press, Inc.

Способы оценки результатов тестов

Пусть дана двоичная последовательность s. Требуется установить проходит ли данная последовательность статистический тест или нет. Разработчиками таких тестов применяются несколько различных подходов в определении этого факта:

  • пороговое значение
  • фиксированный диапазон значений
  • значение вероятности

Пороговое значение

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

Фиксированный диапазон значений

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

Значение вероятности

Третий подход в определении того факта, что двоичная последовательность s проходит статистический тест, включает подсчет не только статистической величины с(s), но и соответствующее ей значение вероятности p. Обычно подсчет конкретной статистической величины производится таким образом, чтобы ее большие значения предполагали неслучайный характер последовательности s. Тогда p есть вероятность получения значения с(s) большего либо равного значению с(s'), высчитанного для истинно случайной последовательности s'. Следовательно, малые значения вероятности p (обычно p < 0,05 или p < 0,01) могут быть интерпретированы как доказательство того, что s не является случайной. Таким образом, если для некоторого фиксированного значения a значение вероятности p < a, то двоичная последовательность s не проходит данный тест. Как правило, a принимает значения из интервала [0,001;0,01].

Пакет статистических тестов NIST

Данный программный пакет разработан Лабораторией информационных технологий (англ. Information Technology Laboratory), являющейся главной исследовательской организацией Национального института стандартов и технологий (NIST). В его состав входят 15 статистических тестов, целью которых является определение случайного характера бинарных последовательностей, вообще говоря, произвольной длины, порожденных либо аппаратными, либо программными генераторами случайных или псевдослучайных чисел. Эти тесты основаны на различных особенностях присущих только непроизвольным последовательностям.

  1. Частотный побитовый тест (англ. The Frequency Monobit Test)
  2. Частотный блочный тест (англ. Frequency Test within a Block)
  3. Тест на последовательность одинаковых битов (англ. The Runs Test)
  4. Тест на самую длинную последовательность единиц в блоке (англ. Tests for the Longest-Run-of-Ones in a Block)
  5. Тест рангов бинарных матриц (англ. The Binary Matrix Rank Test)
  6. Спектральный тест (англ. Spectral Test)
  7. Тест на совпадение неперекрывающихся шаблонов (англ. The Non-overlapping Template Matching Test)
  8. Тест на совпадение перекрывающихся шаблонов (англ. The Non-overlapping Template Matching Test)
  9. Универсальный статистический тест Маурера (англ. Maurer’s «Universal Statistical» Test)
  10. Тест на линейную сложность (англ. The Linear Complexity Test)
  11. Тест на периодичность (англ. The Serial Test)
  12. Тест приблизительной энтропии (англ. The Approximate Entropy Test)
  13. Тест кумулятивных сумм (англ. The Cumulative Sums Test)
  14. Тест на произвольные отклонения (англ. The Random Excursions Test)
  15. Другой тест на произвольные отклонения (англ. The Random Excursions Variant Test)

Частотный побитовый тест

Суть данного теста заключается в определении соотношения между нулями и единицами во всей двоичной последовательности. Цель — выяснить действительно ли число нулей и единиц в последовательности приблизительно одинаковы, как это можно было бы предположить в случае истинно случайной бинарной последовательности. Тест оценивает насколько близка доля единиц к 0,5. Таким образом число нулей и единиц должно быть примерно одинаковым. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является истинно случайной. В противном случае, последовательность носит случайный характер. Стоит отметить, что все последующие тесты проводятся при условии, что пройден данный тест.

Частотный блочный тест

Суть теста — определение доли единиц внутри блока длиной m бит. Цель — выяснить действительно ли частота повторения единиц в блоке длиной m бит приблизительно равна m/2, как можно было бы предположить в случае абсолютно случайной последовательности. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не носит истинно случайный характер. Если принять m = 1, данный тест переходит в тест № 1 (частотный побитовый тест).

Тест на последовательность одинаковых битов

Суть состоит в подсчете полного числа рядов в исходной последовательности, где под словом ряд подразумевается непрерывная подпоследовательность одинаковых битов. Ряд длиной k бит состоит из k абсолютно идентичных битов, начинается и заканчивается с бита, содержащего противоположное значение. Цель данного теста — сделать вывод о том действительно ли число рядов, состоящих из единиц и нулей, и различными длинами соответствует их числу в произвольной последовательности. В частности, определяется быстро либо медленно чередуются единицы и нули в исходной последовательности. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является истинно случайной. В противном случае, она носит случайный характер.

Тест на самую длинную последовательность единиц в блоке

В данном тесте определяется самый длинный ряд единиц внутри блока длиной m бит. Цель — выяснить действительно ли длина такого ряда соответствует ожиданиям длины самого протяженного ряда единиц в случае абсолютно произвольной последовательности. Если высчитанное в ходе теста значение вероятности p < 0,01 полагается, что исходная последовательность не является произвольной. В противном случае, делается вывод о ее случайности. Следует заметить, что из предположения о примерно одинаковой частоте появления единиц и нулей (тест № 1) следует, что точно такие же результаты данного теста будут получены при рассмотрении самого длинного ряда нулей. Поэтому измерения можно проводить только с единицами.

Тест рангов бинарных матриц

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

Спектральный тест

Спектральный тест

Суть теста заключается в оценке высоты пиков дискретного преобразования Фурье исходной последовательности. Цель — выявление периодических свойств входной последовательности, например, близко расположенных друг к другу повторяющихся участков. Тем самым это явно демонстрирует отклонения от случайного характера исследуемой последовательности. Идея состоит в том, чтобы число пиков, превышающих пороговое значение в 95 % по амплитуде, было значительно больше 5 %. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является абсолютно произвольной. В противном случае, она носит случайный характер.

Тест на совпадение неперекрывающихся шаблонов

В данном тесте подсчитывается количество заранее определенных шаблонов, найденных в исходной последовательности. Цель — выявить генераторы случайных или псевдослучайных чисел, формирующие слишком часто заданные непериодические шаблоны. Как и в тесте № 8 на совпадение перекрывающихся шаблонов для поиска конкретных шаблонов длиной m бит используется окно также длиной m бит. Если шаблон не обнаружен, окно смещается на один бит. Если же шаблон найден, окно перемещается на бит, следующий за найденным шаблоном, и поиск продолжается дальше. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не является абсолютно случайной.

Тест на совпадение перекрывающихся шаблонов

Суть данного теста заключается в подсчете количества заранее определенных шаблонов, найденных в исходной последовательности. Как и в тесте № 7 на совпадение неперекрывающихся шаблонов для поиска конкретных шаблонов длиной m бит используется окно так же длиной m бит. Сам поиск производится аналогичным образом. Если шаблон не обнаружен, окно смещается на один бит. Разница между этим тестом и тестом № 7 заключается лишь в том, что если шаблон найден, окно перемещается только на бит вперед, после чего поиск продолжается дальше. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не является абсолютно случайной.

Универсальный статистический тест Маурера

Здесь определяется число бит между одинаковыми шаблонами в исходной последовательности (мера, имеющая непосредственное отношение к длине сжатой последовательности). Цель теста — выяснить может ли данная последовательность быть значительно сжата без потерь информации. В случае, если это возможно сделать, то она не является истинно случайной. В ходе теста вычисляется значение вероятности p. Если p < 0,01, то полагается, что исходная последовательность не является произвольной. В противном случае, делается вывод о ее случайности. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является абсолютно произвольной. В противном случае, она является случайной.

Тест на линейную сложность

В основе теста лежит принцип работы линейного регистр сдвига с обратной связью (англ. Linear Feedback Shift Register, LFSR). Цель — выяснить является ли входная последовательность достаточно сложной для того, чтобы считаться абсолютно случайной. Абсолютно произвольные последовательности характеризуются длинными линейными регистрами сдвига с обратной связью. Если же такой регистр слишком короткий, то предполагается, что последовательность не является в полной мере случайной. В ходе теста вычисляется значение вероятности p. Если p < 0,01, то полагается, что исходная последовательность не является произвольной. В противном случае, делается вывод о ее случайности.

Тест на периодичность

Данный тест заключается в подсчете частоты всех возможных перекрываний шаблонов длины m бит на протяжении исходной последовательности битов. Целью является определение действительно ли количество появлений 2m перекрывающихся шаблонов длиной m бит, приблизительно такое же как в случае абсолютно случайной входной последовательности бит. Последняя, как известно, обладает однообразностью, то есть каждый шаблон длиной m бит появляется в последовательности с одинаковой вероятностью. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является абсолютно произвольной. В противном случае, она носит случайный характер. Стоит отметить, что при m=1 тест на периодичность переходит в частотный побитовый тест (№ 1).

Тест приблизительной энтропии

Как и в тесте на периодичность в данном тесте акцент делается на подсчете частоты всех возможных перекрываний шаблонов длины m бит на протяжении исходной последовательности битов. Цель теста — сравнить частоты перекрывания двух последовательных блоков исходной последовательности с длинами m и m+1 с частотами перекрывания аналогичных блоков в абсолютно случайной последовательности. Вычисляемое в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не является абсолютно произвольной.

Тест кумулятивных сумм

Тест заключается в максимальном отклонении (от нуля) при произвольном обходе, определяемым кумулятивной суммой заданных (-1, +1) цифр в последовательности. Цель данного теста — определить является ли кумулятивная сумма частичных последовательностей, возникающих во входной последоваетльности, слишком большой или слишком маленькой по сравнению с ожидаемым поведением такой суммы для абсолютно произвольной входной последовательности. Таким образом, кумулятивная сумма может рассматриваться как произвольный обход. Для случайной последовательности отклонения от произвольного обхода должно быть вблизи нуля. Для некоторых типов последовательностей, не являющихся в полной мере случайными подобные отклонения от нуля при произвольном обходе будут достаточно существенными. Если вычисленное в ходе теста значение вероятности p < 0,01, то входная двоичная последовательность не является абсолютно случайной. В противном случае, она носит произвольный характер.

Тест на произвольные отклонения

Суть данного теста заключается в подсчете числа циклов, имеющих строго k посещений при произвольном обходе кумулятивной суммы. Произвольный обход кумулятивной суммы начинается с частичных сумм после последовательности (0,1), переведенной в соответствующую последовательность (-1, +1). Цикл произвольного обхода состоит из серии шагов единичной длины, совершаемых в произвольном порядке. Кроме того такой обход начинается и заканчивается на одном и том же элементе. Цель данного теста — определить отличается ли число посещений определенного состояния внутри цикла от аналогичного числа в случае абсолютно случайной входной последовательности. Фактически данный тест есть набор, состоящий из восьми тестов, проводимых для каждого из восьми состояний цикла: −4, −3, −2, −1 и +1, +2, +3, +4. В каждом таком тесте принимается решение о степени случайности исходной последовательности в соответствии со следующим правилом: если вычисленное в ходе теста значение вероятности p < 0,01, то входная двоичная последовательность не является абсолютно случайной. В противном случае, она носит произвольный характер.

Другой тест на произвольные отклонения

В этом тесте подсчитывается общее число посещений определенного состояния при произвольном обходе кумулятивной суммы. Целью является определение отклонений от ожидаемого числа посещений различных состояний при произвольном обходе. В действительности этот тест состоит из 18 тестов, проводимых для каждого состояния: −9, −8, …, −1 и +1, +2, …, +9. На каждом этапе делается вывод о случайности входной последовательности. Если вычисленное в ходе теста значение вероятности p < 0,01, то входная двоичная последовательность не является абсолютно случайной. В противном случае, она носит произвольный характер.

Результаты тестирования алгоритмов, участвовавших в конкурсе AES

С целью утверждения нового стандарта шифрования Национальный институт стандартов и технологий при поддержке правительства США провел конкурс «Продвинутый стандарт шифрования» (англ. Advanced Encryption Standard, AES), в ходе которого были протестированы 15 претендовавших алгоритмов. Один из критериев, используемых при оценке алгоритмов, заключался в их пригодности в качестве генераторов случайных чисел. Проверка таких генераторов на предмет формирования абсолютно случайных двоичных последовательностей осуществлялась с помощью набора статистических тестов NIST.

Первый раунд AES

В течение первого раунда AES тестирование проводилось с 128-битными ключами. В результате было обнаружено что из 15 алгоритмов лишь 9 смогли пройти статистические тесты, а именно:

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

Второй раунд AES

9 августа 1999 года 5 алгоритмов шифрования были выбраны в качестве финалистов AES:

Во втором раунде AES оценка пригодности этих 5 алгоритмов в качестве генераторов случайных чисел проводилось на основе 192-битных и 256-битных ключей. Продолжительность статистических тестов NIST составило несколько месяцев, причем вычисления производились на многочисленных рабочих станциях Sun Ultra. Все данные формировались и обрабатывались в режиме онлайн. В результате второго раунда было показано, что каждый из пяти вышеуказанных алгоритмов формирует абсолютно случайную бинарную последовательность и поэтому может быть использован в качестве генератора псевдослучайных чисел. Причем имеется возможность использования ключей размерами: 128, 192 и 256 бит.

Примечания

  1. ↑ http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
  2. ↑ [http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
  3. ↑ The Information Security Research Centre (Crypt-X)
  4. ↑ The pLab Project
  5. ↑ The DIEHARD Test Suite
  6. ↑ ENT
  7. ↑ Donald E. Knuth. The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms / 3rd ed. Addison-Wesley, 1998
  8. ↑ Alfred Menezes и др. Handbook of Applied Cryptography

Литература

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное



Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»