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

Одним із важливих та необхідних напрямків досліджень та практичних робіт при створенні ефективних генераторів випадкових бітів та генераторів псевдовипадкових бітів є розробка методів та засобів оцінки статистичних властивостей випадкових послідовностей. Справа в тому, що статистичні показники мають вагомий вплив на загальну оцінку ефективності ГВЧ. По суті, статистичні показники та побудовані на їх основі критеріїв оцінки є інструментом перевірки правильності технічних рішень щодо побудови ГВЧ.

Дослідження статистичних властивостей здійснюються у рамках методики статистичних випробувань на основі статистичних тестів. Центральним елементом методики є набір статистичних тестів. Аналіз джерел та результати обґрунтування напрямків досліджень дозволяють зробити висновок, що відбір статистичних тестів є важливою задачею, і їх відбір та застосування впливає на якість методик тестування.

Під системою статистичного тестування ми будемо розуміти сукупність: математично обґрунтованого набору статистичних тестів; загальної моделі тестування; критеріїв прийняття рішення щодо проходження тестування (методики тестування); обладнання (технічне, програмне тощо), які є взаємопов’язаними елементами та використовуються при статистичному випробовуванні генераторів випадкових (псевдовипадкових) бітів.

Як базові рекомендується використовувати п'ять тестів:

-  частотний (монобітний) тест;

-  тест двох бітових серій;

-  тест Поккера;

-  тест серій (загальний);

-  автокореляційний тест.

Монобітний тест

Метою монобітного тесту є перевірка того, чи є число двійкових символів “0” та “1” в послідовності  приблизно таким, як у випадкової послідовності. Якщо  є число символів “0” в послідовності, а  – символів “1”, то параметр ПВП

підпорядковується  розподілу з одним ступенем свободи (якщо ).

Тест двобітових серій

Метою тесту двобітових серій є перевірка того, чи є число з'явлень серій “00” – , “01” – , “10” – , “11” –  такою, як і у випадковій послідовності. Параметр ПВП

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

Тест Поккера

Нехай m є додатне ціле число, таке що

.

Розділимо послідовність Y на k не перекриваючих частин, кожна довжиною m, нехай i буде число з'явлення послідовності довжиною m. Тест Поккера дозволяє визначити, чи дійсно послідовності довжиною m кожна приблизно
з'являються стільки ж разів, скільки очікується у випадковій послідовності.
Параметр:

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

Зазначимо, що тест Поккера є узагальненням частотного тесту – при  тест Поккера співпадає з частотним.

Тест серій

Тест серій дозволяє визначити, чи дійсно число нулів або одиниць (серії) різної довжини в послідовності Y такі ж як і у випадковій послідовності. Бажане число інтервалів довжиною і у випадковій послідовності n є

.

Нехай k буде рівним найбільшому цілому числу і, для якого . Нехай також B та G буде числом блоків і інтервалів відповідно довжиною і в Y для кожного і, . Тоді параметр

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

Автокореляційний тест

Метою автокореляційного тесту є перевірка ступеню зв'язку між  і її зсувами. Нехай d фіксоване ціле число, . Число бітів у Y послідовності дорівнює

.

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

Методика статистичного тестування NIST STS

Набір тестів NIST STS був запропонований у ході проведення конкурсу на новий національний стандарт США блокового шифрування. Цей набір використався для досліджень статистичних властивостей кандидатів на новий блоковий шифр. На сьогодні методика тестування, що запропонована NIST є найбільш поширеною у розробників криптографічних засобів захисту інформації.