Тестирование псевдослучайных последовательностей

Тестирование псевдослучайных последовательностей

Тестирование псевдослучайных последовательностей — совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п.

Содержание

Теоретическая основа

Принципы построения

Один из самых наглядных тестов — тест на равномерное распределение частот появления каждого символа. Пусть \xi_1,\xi_2...\xi_n — последовательность длиной n и размерности m. Тогда частоты νi должны принадлежать отрезку  \Bigl[ \tfrac{n-2,58\sqrt{n(2^m-1)}}{2^m}; \tfrac{n+2,58\sqrt{n(2^m-1)}}{2^m} \Bigr]. Однако, большинство тестов используют другой метод — принятие или отклонение гипотезы о случайности последовательности, используя статистические распределения.

Зная вероятностные свойства истинно случайной последовательности, можно на их основе проверять гипотезу о том, насколько сгенерированная последовательность похожа на случайную. Для этого для каждого теста подбирается подходящая статистика, вычисляется её значения для идеальной и сгенерированной последовательности. Если разность этих значений превышает некоторое критическое значение, установленное заранее, то последовательность считается неслучайной. Для «хороших» последовательностей вероятность такого события крайне мала(допустим ~0,001 и обозначим её α). Однако, существует вероятность того, что «плохая» последовательность удовлетворит критерию и будет сделан вывод о её случайности(обозначим вероятность такого события β). На практике значения длины последовательности n, α и β связаны, задаётся α и подбирается n такое, чтобы минимизировать β.

Определим величину P-value как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Тогда если P-value больше α, то исследуемая последовательность считается случайной и наоборот в противном случае.

Кратко шаги статистического тестирования можно изобразить в виде таблицы:

№ шага Процесс Комментарии
1 Постановка гипотезы Предполагаем, что последовательность является случайной
2 Вычисление статистики исследуемой последовательности Тестирование на битовом уровне
3 Вычисление P-value P-value\in[0; 1]
4 Сравнение P-value с α Задаем α в пределах [0,001; 0,01]; если P-value>α, то тест пройден

Интерпретация результатов

Пусть дана двоичная последовательность 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].

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

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

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

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

Статистические тесты

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

Название Автор Организация
1 Тесты NIST[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 Dieharder[6] Robert G. Brown Duke University
7 ENT[7] John Walker Autodesk, Inc.
8 The Art Of Computer Programming Vol. 2 Seminumerical Algorithms[8] Дональд Кнут Stanford University
9 Handbook of Applied Cryptography[9] Alfred Menezes и др. CRC Press, Inc.

Тесты DIEHARD

Тесты DIEHARD были разработаны Джорджем Марсальей (англ.) в течение нескольких лет и впервые опубликованы на CD-ROM, посвящённом случайным числам. Они рассматриваются как один из наиболее строгих известных наборов тестов.

Тесты Д. Кнута

Тесты Кнута основаны на статистическом критерии \chi^2. Вычисляемое значение статистики \chi^2 сравнивается с табличными результатами, и в зависимости от вероятности появления такой статистики делается вывод о ее качестве. Среди достоинств этих тестов — небольшое их количество и существование быстрых алгоритмов выполнения. Недостаток — неопределенность в трактовке результатов. Вот краткое описание этих тестов:

  • Проверка несцепленных серий. Последовательность разбивается на m непересекающихся серий и строится распределение \chi^2 для частот появления каждой возможной серии.
  • Проверка интервалов. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя длины подпоследовательностей, все элементы которых принадлежат определённому числовому интервалу.
  • Проверка комбинаций. Последовательность разбивается на подпоследовательности определённой длины, и исследуются серии, состоящие из различных комбинаций чисел.
  • Тест собирателя купонов. Пусть \xi_1, \xi_2, \dots, \xi_n — последовательность длины n и размерности m. Исследуются подпоследовательности определённой длины, содержащие каждое m-разрядное число.
  • Проверка перестановок. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя взаимное расположение чисел в подпоследовательностях.
  • Проверка на монотонность. Служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей.
  • Проверка корреляции. Данный тест проверяет взаимонезависимость элементов последовательности.

Тесты NIST

Отличие этих тестов от других современных — открытость алгоритмов. Также среди достоинств — однозначная интерпретация результатов тестирования. Таблица общих характеристик:

Название теста Определяемый дефект
1 Частотный тест Слишком много нулей или единиц
2 Проверка кумулятивных сумм Слишком много нулей или единиц в начале последовательности
3 Проверка «дырок» в подпоследовательностях Отклонение в распределении последовательностей единиц
4 Проверка «дырок» Большое(малое) число подпоследовательностей нулей и единиц свидетельствует, что колебание потока бит слишком быстрое(медленное)
5 Проверка рангов матриц Отклонение распределения рангов матриц от соответствующего распределения для истинно случайной последовательности, связанное с периодичностью последовательностей
6 Спектральный тест Периодические свойства последовательности
7 Проверка непересекающихся шаблонов Непериодические шаблоны встречаются слишком часто
8 Проверка пересекающихся шаблонов Слишком часто встречаются m-битные последовательности единиц
9 Универсальный статистический тест Маурера Сжимаемость(регулярность) последовательности
10 Проверка случайных отклонений Отклонение от распределения числа появлений подпоследовательностей определённого вида
11 Разновидность проверки случайных отклонений Отклонение от распределения числа появлений подпоследовательностей определённого вида
12 Проверка аппроксимированной энтропии Неравномерность распределения m-битных слов. Малые значения означают высокую повторяемость
13 Проверка серий Неравномерность распределения m-битных слов
14 Сжатие при помощи алгоритма Лемпела-Зива Большая сжимаемость, чем истинно случайная последовательность
15 Линейная сложность Отклонение от распределения линейной сложности для конечной длины подстроки

Практические приложения

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

Конкурс AES

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

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

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

См. также

Примечания

Литература

  • Дональд Э. Кнут Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд.. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 5-8459-0081-6
  • М. А. Иванов, И. В. Чугунков Глава 4. Методика оценки качества генераторов ПСП // Теория, применение и оценка качества генераторов псевдослучайных последовательностей. — М.: КУДИЦ-ОБРАЗ, 2003. — 240 с. — ISBN 5-93378-056-1

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Тестирование псевдослучайных последовательностей" в других словарях:

  • Генератор псевдослучайных чисел — (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному). Современная информатика… …   Википедия

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

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

  • Тест на следующий бит — (англ. next bit test) тест, служащий для проверки генераторов псевдо случайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет… …   Википедия

  • Псевдослучайная двоичная последовательность — частный случай ПСП, в которой элементы принимают два возможных значения 0 и 1 (или 1 и +1 ). Постулаты Голомба Одна из первых формулировок некоторых основополагающих правил для статистических свойств периодических псевдослучайных… …   Википедия

  • Псевдослучайная последовательность — (ПСП) последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи. Хотя псевдослучайная последовательность в этом смысле… …   Википедия

  • Wikiproyecto:Matemáticas — …   Wikipedia Español

  • Wikipedia:Artículos solicitados — Atajos WP:AS WP:SOL Artículos solicitados En esta página pue …   Wikipedia Español

  • AES (конкурс) — У этого термина существуют и другие значения, см. AES. Основная статья: Advanced Encryption Standard Advanced Encryption Standard, AES  конкурс, организованный NIST в 1997 году для выбора нового криптографического стандарта, который должен… …   Википедия


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

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