Статистически оптимальный генератор псевдослучайных последовательностей
1.3.2 Статистический набор тестов НИСТ
В 1999 году разработчиками НИСТ(Национальный институт стандартизации и технологий США) в рамках проекта AES(Advanced Encryption Standard) был представлен статистический набор тестов НИСТ (NIST Statistical Test Suite) и предложена методика проведения статистического тестирования шифров и генераторов случайных чисел.
Для принятия решения, достаточно ли случайна последовательность значений, вырабатываемая шифром или генератором псевдослучайных чисел, используется несколько подходов:
? первый и самый простой из них - это принятие положительного решения о случайности выхода шифра в зависимости от заданного порогового уровня случайности. Для этого вычисляют специальную статистическую характеристику от последовательности выхода шифра и сравнивают ее с заранее заготовленными эталонными значениями. При этом считается, что двоичная последовательность A не проходит статистический тест всякий раз, когда статистика теста S принимает значение меньшее, чем пороговый уровень Srange.;
? следующий критерий - принятие решения на основе задания доверительного интервала. В этом случае двоичная последовательность A не проходит статистический тест, если значение статистики теста S находится вне пределов доверительного интервала значений статистики, вычисленного для заданного уровня значимости . Критерий на основе доверительного интервала намного более надежен по сравнению с предыдущим;
? еще один способ определения решения заключается в вычислении для некоторой статистической функции S значения соответствующей ей и последовательности A вероятности Р. В этом случае статистика теста рассматривается как реализация случайной величины, которая подчиняется определенному закону распределения. Обычно статистическую функцию строят таким образом, чтобы всплески ее значений указывали на наличие неслучайных дефектов в представляемой на рассмотрение случайной последовательности чисел. Вероятность P означает вероятность того, что статистика примет значения большие, чем это возможно для случайной последовательности. Обратно, малые значения этой вероятности говорят о прохождении последовательностью A тестов на случайность.
Пакет НИСТ включает в себя 16 статистических тестов, которые разработаны для проверки гипотезы о случайности представляемой двоичной последовательности любой длины. В таблице 1 даны общие характеристики каждого статистического теста НИСТ.
|
Табл.1 Статистические тесты НИСТ |
||
|
Статистический тест |
Определяемый дефект |
|
|
1. Частотный тест |
Слишком много нулей или единиц |
|
|
2. Проверка кумулятивных сумм |
Слишком много нулей или единиц в начале последовательности |
|
|
3. Проверка "дырок" в подпоследовательностях |
Отклонения в распределении подпоследовательностей единиц |
|
|
4. Проверка "дырок" |
Большое (малое) число подпоследовательностей нулей и единиц свидетельствует, что колебание потока бит слишком быстрое (медленное) |
|
|
5. Проверка рангов матриц |
Отклонение распределения рангов матриц от соответствующего распределения для истинно случайной последовательности, связанное с периодичностью подпоследовательностей |
|
|
6. Спектральный тест |
Периодические свойства последовательности |
|
|
7. Проверка непересекающихся шаблонов |
Непериодические шаблоны встречаются слишком часто |
|
|
8. Проверка пересекающихся шаблонов |
Слишком часто встречаются m-битные последовательности единиц |
|
Делись добром ;)Похожие главы из других работ:Планы второго порядка, реализация В3-плана
1.2 Статистический анализ полученных данных... Системы линейных неравенств
ГЛАВА III. ОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ. ФУНДАМЕНТАЛЬНЫЙ НАБОР РЕШЕНИЙв первой главе был рассмотрен метод решения системы линейных неравенств путем последовательного уменьшения числа неизвестных. При очевидных достоинствах этого метода... Статистически оптимальный генератор псевдослучайных последовательностей
9. Универсальный статистический тест МаурераСжимаемость (регулярность) последовательности 10. Проверка случайных отклонений Отклонение от распределения числа появлений случайных отклонений определенного значения 11... Статистически оптимальный генератор псевдослучайных последовательностей
- универсальный статистический тест Маурера;- критерий серий; 1.3.3 Тест n-серий Тест n-серий является классическим тестом n-мерной равномерности. Он является частным случаем универсального алгоритма тестирования (10)-(12), описанного в 1.3.1: , ; m=n;... Статистически оптимальный генератор псевдослучайных последовательностей
1.3.4 Универсальный статистический тест МаурераУниверсальный статистический тест Маурера основан на следующей идее: последовательность случайна, когда ее невозможно значительно упаковать или сжать. Для этого вводится мера, которая оценивает степень сжимаемости... Статистический анализ выборочных совокупностей
4. Статистический анализ выборочной совокупностиВыборочной совокупностью, или просто выборкой, называют совокупность случайно отобранных объектов. Объемом n выборочной совокупности называют число объектов этой совокупности... Теория информации. Статистический подход
Статистический подход к измерению правовой информацииСтатистический подход изучается в разделе кибернетики, называемом теорией информации. Его основоположником считается К. Шеннон, опубликовавший в 1948 году свою математическую теорию связи... |