Генератори випадкових бітів. Методика статистичного тестування NIST STS, страница 5

Порядок тестування окремої двійкової послідовності S згідно NIST STS має такий вигляд:

          1. Висувається нульова гіпотеза  – припущення про те, що дана двійкова послідовність S випадкова.

2.  По послідовності S розраховується статистика тесту с(S).

3. Із використанням спеціальної функції і статистики тесту розраховується значення імовірності

          4. Значення імовірності Р порівнюється із рівнем значущості ,[0.001,0.01]. Якщо , то гіпотеза  приймається. У противному випадку приймається альтернативна гіпотеза.

Пакет містить у собі 16 статистичних тестів. Але фактично, в залежності від вхідних параметрів обчислюється 189 значень імовірності Р, які можна розглядати як результат роботи окремих тестів.

Таким чином у результаті тестування двійкової послідовності формується вектор значень імовірності . Аналіз складових  даного вектору дозволяє вказати на конкретні дефекти випадковості послідовності, що тестується.

Методика тестування NIST STS має такий вигляд.

1. Для кожного апаратного модуля (АМ) необхідно оцінити та прийняти рішення про те, що він формує випадкові двійкові послідовності. Генератор повинен формувати двійкову послідовність S={s₁, s₂, …, s_n}, s_iÎ {0,1} довільної довжини n.

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

S₁ ={s₁, s₂, …, s_n};

S₂ ={s₁, s₂, …, s_n};

………………….

S_m ={s₁, s₂, …, s_n}.

Таким чином, для тестування необхідно сформувати вибірку об’ємом N = m ´ n.

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

№ теста j № пос-ті i	1	2	…	q
S1	P1,1	P1,2	…	P1,q
S2	P2,1	P2,2	…	P2,q
...	…	…	…	…
Sm	Pm,1	Pm,2	…	Pm,q

.

Статистичний портрет генератора є матриця розмірністю m´q, де m – кількість двійкових послідовностей, що перевіряються, а q – кількість статистичних тестів, що використовуються для тестування кожної послідовності. Елементи матриці , де , представляють собою значення ймовірності, яка отримана у результаті тестування i-ої послідовності j-им тестом.

4. За отриманим статистичним портретом визначають долю послідовностей, що пройшли кожний статистичний тест. Для цього задають рівень значимості [0.001,0.01] та здійснюють підрахунок значень ймовірностей , що перевищують встановлений рівень  для кожного з q тестів, тобто визначають коефіцієнт

.                                                (1.7)

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

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

,                                            (1.8)

де .

5. Здійснюється статистичний аналіз статистичного портрету. Отримані значення івно ймовір P_ij повинні підкорятися івно ймовірному закону розподілу на інтервалі [0,1]. Для кожного вектору-стовпцю статистичного портрету будується гістограма частостей F_k влучень значень P_ij у кожний з k = 1, 2, …, 10 підінтервалів, на які розбитий інтервал [0,1]. Рівноймовірність розподілу значень ймовірностей P_ij перевіряється з використанням критерію . Для цього розраховується статистика виду

,                                             (1.9)

яка підкоряється розподілу  с дев’ятьма ступенями волі.

Правило 2. Вважається, що генератор G пройшов тестування за j-им тестом, якщо виконується умова .