38. Тестування джерел сп та пвп на основі методики fips-140-1. Тести серій та довжин серій.

Американский федеральный стандарт FIPS 140-1 определяет четыре статистических теста на случайность: монобитный тест, блочный тест, тест серий, тест длин серий. Для этих тестов, задаются границы для удовлетворительных значений статистических параметров. Отдельная битовая строка длиной 20000 битов, получаемая из генератора подвергается каждому из четырех приведенных тестов. Если какой-нибудь из тестов не пройден, то считается, что генератор не прошел весь комплекс проверок.

1. Монобитный тест

Суть теста заключается в подсчете количества нулей и единиц на отрезке последовательности определённой длины. Пусть n₁ и n₂ обозначает число нулей и единиц в последовательности x, соответственно. Если последовательность случайная, то значения n₁ и n₂ должны удовлетворять условию 9654 < n₁ (n₂) < 10346.

2. Блочный тест

Пусть m положительное целое число, такое, что и пусть. Разобьем последовательностьx на k непересекающихся подпоследовательностей, каждая длиной m, и пусть n_i будет числом появлений i-го типа последовательности длиной m,. Блочный тест определяет, действительно ли последовательности длиной m, появляются приблизительно столько же раз в последовательности x, колько ожидается для случайной последовательности. Для применения критерия используется расчет параметра

который согласуется с распределением χ² с 2^m – 1 степенями свободы. Статистический параметр, задаваемый уравнением, вычисляется для m = 4. Статистика должна удовлетворять условию 1,03 < X₃ < 57,4.

3. Тест серий

Под серией понимается последовательность одинаковых символов, т.е. из последовательных единиц или нулей. Суть теста заключается в том, что на заданной длине тестируемой последовательности осуществляется подсчет серий длиной 1, 2, 3, 4, 5, 6 элементов (серии длиной более чем 6 элементов рассматриваются как серии длиной 6). Если последовательность случайная, то количество серий каждой длины должно находится в определённых интервалах.

4. Тест длин серий.

Суть теста заключается в проверке максимальной длины серии из одинаковых элементов. Если последовательность случайная, то максимальная длина серии не должна превышать значения 34. (Вероятность события, заключающегося в появлении серии такой длины очень мала).

39. Тестування джерел вп та пвп за допомогою теста Маурера.

Универсальный тест Маурера использует идею, заключающуюся в том, что случайную двоичную последовательность не возможно достаточно сильно сжать. Таким образом, если некоторая последовательность xс выхода генератора сжимается, то данный генератор можно считать неудовлетворительным. Для определения сжимаемости или несжимаемости последовательностей можно использовать архиваторы, напримерZIP,ARJ,RARи др.

Универсальность теста заключается в том, что он способен обнаруживать широкий класс дефектов, которые обнаруживаются по отдельности другими тестами. Для эффективного применения теста Маурера необходимо иметь выборки больших объёмов.

Суть универсального теста Маурера.

При тестировании некоторой двоичной последовательности x = x₀, x₁,…,x_n-1вычисляется статистикаX_U. Сначала необходимо выбрать параметрL[6,16]. Тестируемая последовательность разбивается на непересекающиеся блоки поLбит. В случае, если длина последовательностиnне кратно числуL, лишние старшие биты последовательности отбрасываются. Общее количество блоков, необходимых для тестирования определяется как:

N_бл = Q + K,

где Q  10·2^L;

K1000·2^L.

Значение Qвыбирается таким для того, чтобы обеспечить достаточную вероятность того, что любой блок как минимум один раз встретится среди всех возможныхL-битных блоков.

Таким образом, параметры Q,K иLзадают необходимую длину последовательности, которая составитn  1010·2^L·L, бит.

Для проверки последовательности используется двусторонний критерий с уровнем значимости 0,001 < < 0,01. На основе полученного значенияХ_uвычисляется параметрZ_u=(X_u-)/.

Распределение случайной величины Z_uподчиняется стандартному нормальному закону распределения с математическим ожиданием равным 0 и дисперсией равной 1.