Другие предметы \ Алгоритмические основы криптографии

Методика статистичного тестування: Технічний звіт ІІТ – 001-2004, страница 2

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

2. Методика тестування

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

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

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

         S1 ={s1, s2, …, sn};

S2 ={s1, s2, …, sn};                                   (1)

………………….

         Sm ={s1, s2, …, sn}.

Таким чином, для тестування необхідно сформувати вибірку об’ємом 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. За отриманим статистичним портретом визначають долю послідовностей, що пройшли кожний статистичний тест. Для цього задають рівень значимості a Î [0,001, 0,01] та здійснюють підрахунок значень ймовірностей , що перевищують встановлений рівень a для кожного з q тестів, тобто визначають коефіцієнт [1]

.                                             (2)

У результаті формується вектор коефіцієнтів R = {r1, r2, …, rq}, елементи якого характеризують, у відсотках, проходження послідовності Si всіх статистичних тестів.

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

                                                (3)

де .

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

                                             (4)

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

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

6. Прикінцеве рішення приймають у відповідності з правилом: вважається, що генератор G пройшов статистичне тестування пакетом NIST STS, якщо значення коефіцієнтів rj для всіх  знаходяться в межах  довірчого інтервалу [rmax, rmin] та виконується умова  для всіх .

3. Опис статистичних тестів

3.1. Частотний (монобітний) тест (Frequency (Monobit)Test)

Мета тесту – перевірити рівномірність появи 0 та 1 у послідовності, що досліджується.

Нехай  - двійкова послідовність довжини n. Розрахуємо різницю між кількістю появ одиниць та нулів .  Розрахуємо статистику  та значення  у відповідності з виразом [1]:   

                                         (5)

Значення має бути більшим ніж 0,01. Рекомендована довжина послідовності – не менш ніж 100 біт.

3.2. Частотний тест у підпослідовностях (Frequency Test Within a Block)

Скачать файл