Методика тестирования NISTSTS

Методика тестирования включает следующие этапы:

Цель методики - для каждого ГСП оценить и принять решение о том, что он формирует случайные двоичные последовательности.

1. Генератор формирует двоичную последовательность S ={s₁ , s₂ ,…, s_n}, s_iÎ{0,1} произвольной длины n .

2. Для фиксированного значения n формируется множество из m двоичных последовательностей:

S₁ = S₁₁, S₁₂, …, S_1n

S₂ = S₂₁, S₂₂, …, S_2n

…

S_m = S_m1, S_m2, …, S_mn, S_ij={0,1}, 1≤ i≤ m, 1≤ j≤n.

3. Каждую последовательность проверяют с использованием пакета NIST STS. В результате формируется статистический портрет генератора, таблица 3.

Таблица 3. Статистический портрет генератора

№ теста j	1	2	…	q
№ последовательности i
S₁	P₁₁	P₁₂		P_1q
S₂	P₂₁	P₂₂		P_2q
…	…	…	…	…
S_m	P_m1	P_m2	…	P_mq

Либо в матричном виде:

Статистическим портретом генератора является матрица размерностью m´q , де m – количество проверяемых двоичных последовательностей, а q – количество статистических тестов, используемых для тестирования каждой последовательности. Элементы матрицы P_ijÎ[0,1], где i= и j= представляют собой значения вероятности, которая получена в результате тестирования i-ой последовательности j-ым тестом.

4. Согласно полученному статистическому портрету определяют долю последовательностей, которые прошли каждый статистический тест. Для этого задают уровень значимости aÎ[0.001, 0.01] и выполняют подсчет значений вероятности, что превышают установленный уровень значимости a для каждого из q тестов, то есть определяют коэффициент:

(3.3)

В результате формируется вектор коэффициентов R ={r₁, r₂,…, r_q}, элементы которого характеризуют, в процентах, прохождения последовательности S_i всех статистических тестов.

Правило 1. Предполагается, что генератор G прошел тестирование по j-ому тесту, если значение коэффициента r_j находится в пределах доверительного интервала [r_max, r_min]. Границы доверительного интервала определяются в соответствии с выражением:

, где (3.4)

5. Производится статистический анализ статистического портрета. Полученные значения вероятностей P_ij подчиняются равновероятному закону распределения на интервале [0, 1] . Для вектора-столбца статистического портрета строится гистограмма частот F_k попадания значений P_ij в каждый из k= подинтервалов, на которые разбит интервал [0, 1]. Равновероятность распределения значений вероятностей P_ij, проверяется с использованием критерия x².Для этого рассчитывается статистика вида:

, (3.5)

котораяподчиняетсяраспределениюx²с девятью степенями свободы.

Правило 2. Предполагается, что генератор G прошел тестирование по j-му тесту, если выполняется условие .

6. Предпоследнее решение принимают в соответствии с правилом: предполагается, что генератор G прошел статистическое тестирование пакетом NIST STS, если значение коэффициентов r_jдля всех j= находятся в пределах доверительного интервала [r_max, r_min] и выполняется условие для всех j= .

Описание тестов NIST

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

1.FrequencyTest(Частотный побитовый тест)

Этот тест определяет соотношения между нулями и единицами во всей двоичной последовательности. Цель – выяснить, действительно ли число нулей и единиц в последовательности приблизительно одинаковы, как это можно было бы предположить в случае истинно случайной бинарной последовательности. Тест оценивает, насколько близка доля единиц к 0.5. Таким образом, число нулей и единиц должно быть примерно одинаковым. Все последующие тесты проводятся при условии, что пройден данный тест.

2. Frequency Test within a Block (Частотныйблочныйтест)

Этот тест определяет количество единиц внутри блока длиной M бит. Цель – выяснить, действительно ли частота повторения единиц в блоке длиной M бит приблизительно равна M /2 , как можно было бы предположить в случае абсолютно случайной последовательности. Если принять M=1 , данный тест переходит в тест Frequency (частотный побитовый тест).

3. Cumulative Sums (Cusum) Test (Тесткумулятивныхсумм)

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

4.Runs Test (Тест на последовательность одинаковых битов)

Этот тест подсчитывает полное число серий в исходной последовательности, где под серией подразумевается непрерывная подпоследовательность одинаковых битов. Серия длинойk бит состоит из k идентичных битов. Цель данного теста – сделать вывод о том, действительно ли число серий, состоящих из единиц и нулей, с различными длинами соответствует их числу в случайной последовательности. В частности, определяется, быстро либо медленно чередуются единицы и нули в исходной последовательности.

5.TestfortheLongestRunofOnesinaBlock (Тест на самую длинную последовательность единиц в блоке)

В данном тесте определяется самая длинная серия единиц внутри блока длиной m бит. Цель – выяснить, действительно ли длина такой серии соответствует ожиданиям длины самой протяжённой серии единиц в случае абсолютно случайной последовательности. Следует заметить, что из предположения о примерно одинаковой частоте появления единиц и нулей (тест Frequency) следует, что точно такие же результаты данного теста будут получены при рассмотрении самой длинной серии нулей. Поэтому измерения можно проводить только с единицами.

6. Binary Matrix Rank Test (Тест рангов бинарных матриц)

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

7. Discrete Fourier Transform (Spectral) Test (Спектральныйтест)

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

8. Non-overlapping Template Matching Test (Тест на совпадение неперекрывающихся шаблонов)

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

9. Overlapping Template Matching Test (Тест на совпадение перекрывающихся шаблонов)

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

10. Maurer’s “Universal Statistical” Test (Универсальный статистический тест Маурера)

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

11. ApproximateEntropyTest (Тест приблизительной энтропии)

Как и в тесте на периодичность, в данном тесте акцент делается на подсчёте частоты всех возможных перекрываний шаблонов длины m бит на протяжении исходной последовательности битов. Цель теста – сравнить частоты перекрывания двух последовательных блоков исходной последовательности с длинами m и m+1 с частотами перекрывания аналогичных блоков в абсолютно случайной последовательности.

12. RandomExcursions Test (Тест на произвольные отклонения)

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

13. Random Excursions Variant Test (Другой тест на произвольные отклонения)

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

14. Serial Test (Тест на переодичность)

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

15. Linear Complexity Test (Тест на линейную сложность)

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

Дата добавления: 2018-06-01; просмотров: 862; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒

Мы поможем в написании ваших работ!