Висновки до розділу
Генерація випадкових чисел мають важливу роль в областях наукових досліджень, моделювання, криптографії, оптимізації , інформаційної безпеки та навіть у сфері розваг та розробки ігор. Для того щоб вибрати найкращий генератор, потрібно провести ряд тестів та оцінку якості для наших потреб та параметрів. Перед цим потрібно ознайомитись з самими методами їх побудови та вимогами до генераторів ПВП. Є безліч задач для яких потрібні генератори випадкових та псевдовипадкових чисел, для ефективного рішення задач та гарної їх роботи, виконують оцінку якості.
РОЗДІЛ 2. ТЕСТУВАННЯ ПСЕВДОВИПАДКОВИХ ПОСЛІДОВНОСТЕЙ НА ОСНОВІ ГРАФІЧНИХ ТЕСТІВ ТА NIST STS
Будь-пакет статистичних тестів може використовуватися для вирішення наступних завдань:
ідентифікація ГСЧ (ГПСЧ), які формують «погані» виконавчі послідовності;
розробка нових ГСЧ (ГПСЧ);
перевірка коректності реалізації ГВЧ (ГПСЧ);
вивчення генераторів, описаних в стандартах;
дослідження ступеня випадковості реально використовуваних ГСЧ (ГПСЧ).
Основним принципом тестування двійковій послідовності є перевірка нульової гіпотези Н0, що полягає в тому, що тестована послідовність є випадковою. Альтернативною гіпотезою Н0 є гіпотеза про те, що тестована послідовність виник не випадково. За результатами застосування кожного тесту нульова гіпотеза або приймається, або відкидається. Рішення про те, що буде задана послідовність нулів і одиниць випадкової чи ні приймається за сукупністю результатів усіх тестів.
2.1 Тестування випадкових послідовностей
Псевдовипадкові послідовності, породжувані будь-яким генератором для криптографічних цілей, підлягають обов'язковому тестуванню.
Тестування псевдовипадкових послідовностей - сукупність методів визначення міри близькості заданої псевдовидкової послідовності до випадковою. В якості такого заходу зазвичай виступає наявність рівномірного розподілу, великого періоду, що дорівнює частоти появи однакових підрядків і т.п.
Існує кілька методів тестування ПСП:
Графічний тест
Статистичний
Графічні тести
До цієї категорії належать тести, результати яких відображаються у вигляді графіків, що характеризують властивості досліджуваної послідовності. Серед них:
гістограма розподілу елементів послідовності (дозволяє оцінити рівномірність розподілу символів в послідовності і визначити частоту повторення кожного символу);
розподіл на площині (призначено для визначення залежності між елементами послідовності);
перевірка серій (дозволяє визначити рівномірність окремих символів в послідовності, а так же рівномірність розподілу серій з k-біт);
перевірка на монотонність (служить для визначення рівномірності виходячи з аналізу невозростаючих і неубуваючих підпослідовностей);
автокореляційна функція (призначена для оцінки кореляції між зсунутими копіями послідовностей та окремих підпослідовностей);
профільfлінійноїfскладностіf(тестfоцінюєfзалежністьfлінійноїfскладності послідовності від її довжини);
графічний спектральний тест (дозволяє оцінити рівномірність розподілу біт послідовності на підставі аналізу висоти викидів перетворення Фур'є).
При графічному тестуванні статистичні властивості послідовностей відображаються у виді графічних залежностей, за виглядом яких роблять висновки про властивості досліджуваної послідовності.
До даної категорії відносяться такі тести: гістограма розподілу елементів послідовності, розподіл Тестування генераторів ПВЧ
Результати графічних тестів інтерпретуються людиною, тому висновки можуть бути неоднозначними.
Статистичні тести
Статистичні тести використовуються для перевірки певної нульової гіпотези щодо випадковості сформованої послідовності. З цією нульовою гіпотезою пов'язана альтернативна гіпотеза про те, що послідовність не випадкова. Для кожного тесту, що застосовується, можна зробити висновок щодо прийняття чи відхилення нульової гіпотези, виходячи із сформованої генератором послідовності. При цьому для кожного тесту має бути вибрана адекватна статистика випадковості, на основі якої може бути прийнята або відхилена нульова гіпотеза.
Теоретично для нульової гіпотези розподілення статистики визначається математичними методами. Під час проведення тесту розраховується значення тестової статистики, яке порівнюється з критичним. Якщо значення тестової статистики перевищує критичне значення, нульова гіпотеза для випадковості відхиляється, інакше – приймається.
Статистичні тести, на відміну від графічних тестів (результати інтерпретуються користувачами, внаслідок чого можливі відмінності у трактуванні результатів), характеризуються тим, що вони видають чисельну характеристику, яка дозволяє однозначно сказати, пройдено тест чи ні. Нижче описано короткий огляд найбільш відомих на сьогоднішній день методик тестування.
У США був зроблений перший крок до стандартизації набору статистичних тестів шляхом прийняття в 1994 році національного стандарту «Вимоги безпеки до криптографічних модулів» [Security Requirements For]. Проте вимоги і методика стандарту більше носять технологічний характер. Вони направлені на вирішення завдання статистичного контролю ПВП, які використовуються в криптографічних модулях і в загальному випадку малопридатні до вирішення завдання дослідження статистичних властивостей ГПВЧ.
Найбільш відомі тести:
підбірка статистичних тестів Д. Кнута;
NIST STS;
DIEHARD;
FIPS;
AIS.
Розглянемо основні принципи статистичних тестів. Знаючи імовірнісні властивості істинно випадкової послідовності, можна на їх основі перевіряти гіпотезу про те, на скільки згенерований ряд схожий на випадковий. Для цього для кожного тесту підбирається статистика, яка підходить і обчислюються її значення для ідеальної і згенерованої послідовності. Якщо різниця цих значень перевищує деяке критичне значення, встановлене заздалегідь, то послідовність вважається невипадковою. Для «хороших» послідовностей ймовірність такої події вкрай мала (припустимо «0,001, позначимо її а). Однак, існує ймовірність того, що «погана» послідовність задовольнить критерій і буде зроблено висновок про її випадковість (позначимо ймовірність такої події р). На практиці значення довжини ПВП п, показники а і Р — пов'язані, а саме таким чином: задається а і підбирається п таке, щоб мінімізувати р.
Визначимо величину Р — value як ймовірність того, що ідеальний генератор згенерував послідовність менш випадкову, ніж досліджуваний. Тоді якщо Р — value більше а, то досліджувана послідовність вважається випадковою і навпаки в іншому випадку .
Коротко кроки статистичного тестування можна зобразити у вигляді таблиці:
Критерії прийняття рішення про проходження тесту.
Для прийняття рішення про проходження послідовністю випадкових (псевдовипадкових) чисел статистичного тесту використовуються наступні три основних обчислювальних підходу.
Нехай дана двоїчна послідовність S = {s1, s2, ..., sn}, si є {0,1}, довжиною n біт. Необхідно прийняти рішення, проходить дана послідовність статистичний тест чи ні.
Можливі такі підходи до вирішення цього завдання:
Критерій прийняття рішення на основі завдання порогового рівня. Даний підхід заснований на обчисленні по даній послідовності S статистики тесту c (S) з її подальшим порівнянням з деякими пороговим рівнем Суперечки (S). Критерій прийняття рішення формується наступним чином: вважається, що двійкова послідовність S НЕ проходить статистичний тест щоразу, коли статистика тесту c (S) приймає значення менше, ніж граничний рівень Суперечки (S).
Критерій прийняття рішення на основі завдання фіксованого довірчого інтервалу. При цьому підході критерій прийняття рішення формулюється так: вважається, що двійкова послідовність S не проходить статистичний тест, якщо значення статистики тесту c (S) знаходиться поза межами довірчого інтервалу значень статистики, обчисленого для заданого рівня значущості .Цей критерій є більш надійними, ніж його першим. Необхідно тільки враховувати, що різним рівням значимості будуть відповідати різні довірчі інтервали.
Третій підхід побудови критерію прийняття рішення спирається на обчислення для статистики тесту c (S) відповідного значення ймовірності Р. Тут статистика тесту розглядається як реалізація випадкової величини, яка підпорядковується відомому закону розподілу. Малі значення ймовірності Р (Р <0,05 або Р <0,01) інтерпретуються як доказ того, що послідовність не випадкова.
Вирішальне правило формулюється так: для фіксованого рівня значущості двоїчна послідовність S не проходить статистичний тест, якщо значення ймовірності Р <а. Значення а рекомендується вибирати з інтервалу [0,001; 0,01].
Використання даного підходу має додаткову перевагу в порівнянні з попереднім, яке полягає в тому, що одного разу розраховане значення ймовірності Р може порівнюватися з довільно обраним рівнем значущості а без проведення додаткових розрахунків.
В основу найбільш потужних бібліотек статистичного тестування ГПСЧ, до яких можна віднести пакет DIEHARD , Сrypt-SX і пакет NIST STS , закладений саме третій критерій прийняття рішення.
Порядок тестування окремої двійковій послідовності S виглядає наступним чином.
Було висунуто нульова гіпотеза Н0 - припущення про те, що дана двоїчна послідовність S випадкова.
По послідовності S обчислюється статистика тесту c (S).
З використанням спеціальної функції і статистики тесту обчислюється значення ймовірності Р = f (c (S)), Р є [0, 1].
Значення ймовірності Р порівнюється з рівнем значущості а, а є [0,001, 0,01]. Якщо Р більше рівне а, то гіпотеза Н0 приймається. В протилежному випадку приймається альтернативна гіпотеза.
Для прийняття рішення щодо генератора в цілому застосовують наступну методику тестування генератора:
З безлічі апаратних або програмних генераторів вибирають генератор G, який необхідно оцінити і прийняти рішення по тому, що він формує випадкові виконавчі послідовності. Генератор повинен породжувати двійкову послідовність S = {s1, s2, ..., sn}, si є {0,1} довільної довжини n.
Кожну послідовність піддають тестуванню з використанням пакета NIST STS. В результаті формується статистичний портрет генератора
Таблиця 3.1 - Статистичний портрет генератораСтатистичний портрет генератора задається матрицею розмірністю т х q, де т - кількість двійкових послідовностей, що перевіряються, a q - кількість статистичних тестів, що використовуються для тестування кожної послідовності. являють собою значення ймовірності, отриманої в результаті тестування i - й послідовності j - м тестом.
Для фіксованого значення n формують безліч з m двійкових послідовностей:
S1 ={s1, s2, …, sn};
S2 ={s1, s2, …, sn};
………………….
Sm ={s1, s2, …, sn}.
Таким чином, для тестування необхідно сформувати вибірку обсягом
N = m х n.
За отриманим статистичному портрету визначають частку послідовностей, які пройшли кожен статистичний тест. Для цього задають рівень значущості а є [0,001, 0,01] і здійснюють підрахунок значень ймовірності Р, що перевищують заданий рівень а для кожного з q тестів, тобто визначають коефіцієнт.
Здійснюється статистичний аналіз статистичного портрету. Отримані значення Pij повинні підкорятися рівно ймовірному закону розподілу на інтервалі [0,1]. Для кожного вектору-стовпцю статистичного портрету будується гістограма частот Fk попадання значень Pij кожний з к = 1,2,..., 10 під інтервалів, на які розбитий інтервал [0,1].
Рівноймовірність розподілу значень ймовірностей Рі;- перевіряється з використанням критерію х2 . Для цього розраховується статистика виду:
Пакет статистичних тестів NIST STS.
Даний програмний пакет розроблений Лабораторією інформаційних технологій (англ. Information Technology Laboratory), що є головною організацією Національного інституту стандартів і технологій (NIST). До його складу входять 15 статистичних тестів, метою яких є визначення випадкового характеру бінарних послідовностей, взагалі кажучи, довільної довжини, породжених або апаратними, або програмними генераторами випадкових або псевдовипадкових чисел. Ці тести засновані на різних особливостях властивих тільки мимовільним послідовностей.
1.Частотнийтпобітовийттест
Суть даного тесту полягає у визначенні співвідношення між нулями і одиницями у всій двійковій послідовності. Мета - з'ясувати чи дійсно число нулів і одиниць у послідовності приблизно однакові, як це можна було б припустити в разі істинно випадкової бінарної послідовності. Тест оцінює наскільки близька частка одиниць до 0,5. Таким чином число нулів і одиниць має бути приблизно однаковим. Якщо обчислена в ході тесту значення ймовірності p <0,01, то дана двійкова послідовність не є істинно випадковою. В іншому випадку, послідовність носить випадковий характер.
Варто відзначити, що всі наступні тести проводяться за умови, що пройдено даний тест.
2.Частотнийтблочнийттест
Суть тесту - визначення частки одиниць всередині блоку довжиною m біт. Мета - з'ясувати чи дійсно частота повторення одиниць в блоці довжиною m біт приблизно дорівнює m / 2, як можна було б припустити в разі абсолютно довільній послідовності. Обчислене в ході тесту значення ймовірності p повинно бути не менше 0,01. В іншому випадку (p <0,01), двійкова послідовність не носить істинно випадковий характер. Якщо прийняти m = 1, даний тест переходить в тест № 1 (частотнийfпобітовийfтест).
3.Тесттнатпослідовністьтоднаковихтбітів
Суть полягає в підрахунку повного числа рядів у вихідній послідовності, де під словом ряд мається на увазі безперервна підпослідовність однакових бітів. Ряд довжиною k біт складається з k абсолютно ідентичних бітів, починається і закінчується з біта, що містить протилежне значення. Мета даного тесту - зробити висновок про те чи дійсно число рядів, що складаються з одиниць і нулів, і різними довжинами відповідає їх числа в довільній послідовності. Зокрема, визначається швидко або повільно чергуються одиниці і нулі у вихідній послідовності. Якщо обчислена в ході тесту значення ймовірності p <0,01, то дана двійкова послідовність не є істинно випадковою. В іншому випадку, вона носить випадковий характер.
4.Тесттнатнайдовшутпослідовністьтодиницьтвтблоці
У даному тесті визначається найдовший ряд одиниць всередині блоку довжиною m біт. Мета - з'ясувати чи дійсно довжина такого ряду відповідає очікуванням довжини самого протяжного ряду одиниць в разі абсолютно довільній послідовності. Якщо вирахувана в ході тесту значення ймовірності p <0,01 годиться, що вихідна послідовність не є довільною. В іншому випадку, робиться висновок про її випадковості. Слід зауважити, що з припущення про приблизно однаковою частотою появи одиниць і нулів (тест № 1) випливає, що точно такі ж результати даного тесту будуть отримані при розгляді самого довгого ряду нулів. Тому вимірюванняfможнаfпроводитиfтількитзтодиницями.
5.Тесттрангівтбінарнихтматриць
Тут проводиться розрахунок рангів непересічних підматриць, побудованих з вихідної двійкової послідовності. Метою цього тесту є перевірка на лінійну залежність підрядків фіксованої довжини, що становлять первісну послідовність. У випадку, якщо обчислене в ході тесту значення ймовірності p <0,01, робиться висновок про невипадковий характер вхідної послідовності біт. В іншому випадку, вважаємоfїїfабсолютноfдовільною.Данийfтестfтак самотприсутнійтвтпакетітDIEHARD.
6.Спектральнийттест
Суть тесту полягає в оцінці висоти піків дискретного перетворення Фур'є вихідної послідовності. Мета - виявлення періодичних властивостей вхідної послідовності, наприклад, близько розташованих один до одного повторюваних ділянок. Тим самим це явно демонструє відхилення від випадкового характеру досліджуваної послідовності. Ідея полягає в тому, щоб число піків, що перевищують порогове значення в 95% по амплітуді, було значно більше 5%. Якщо обчислена в ході тесту значення ймовірності p <0,01, то дана двійкова послідовність не є абсолютно довільною.Вfіншомуfвипадку,вонатноситьтвипадковийтхарактер.
7.Тесттнатзбігтнеперекриваючихтшаблонів
У даному тесті підраховується кількість заздалегідь визначених шаблонів, знайдених у вихідній послідовності. Мета - виявити генератори випадкових або псевдовипадкових чисел, що формують дуже часто задані неперіодичні шаблони. Як і в тесті № 8 на збіг перекриваються шаблонів для пошуку конкретних шаблонів довжиною m біт використовується вікно також довжиною m біт. Якщо шаблон не виявлений, вікно зміщується на один біт. Якщо ж шаблон знайдено, вікно переміщається на біт, наступний за знайденим шаблоном, і пошук триває далі. Обчислене в ході тесту значення ймовірності p повинно бути не менше 0,01. В іншому випадку (p <0,01), двійковатпослідовністьтнетєтабсолютнотвипадковою.
8.Тесттнатзбігтперекриваютьсятшаблонів
Суть даного тесту полягає в підрахунку кількості заздалегідь визначених шаблонів, знайдених у вихідній послідовності. Як і в тесті № 7 на збіг неперекривающіхся шаблонів для пошуку конкретних шаблонів довжиною m біт використовується вікно так само довжиною m біт. Сам пошук здійснюється аналогічним чином. Якщо шаблон не виявлений, вікно зміщується на один біт. Різниця між цим тестом і тестом № 7 полягає лише в тому, що якщо шаблон знайдено, вікно переміщається тільки на біт вперед, після чого пошук триває далі. Обчислене в ході тесту значення ймовірності p повинно бути не менше 0,01. В іншому випадку (p <0,01), двійкова послідовністьтнетєтабсолютнотвипадковою.
9.УніверсальнийтстатистичнийттесттМаурера
Тут визначається число біт між однаковими шаблонами у вихідній послідовності (міра, що має безпосереднє відношення до довжини стислій послідовності). Мета тесту - з'ясувати чи може дана послідовність бути значно стиснута без втрат інформації. У випадку, якщо це можливо зробити, то вона не є істинно випадковою. У ході тесту обчислюється значення ймовірності p. Якщо p <0,01, то вважається, що вихідна послідовність не є довільною. В іншому випадку, робиться висновок про її випадковості. Якщо обчислена в ході тесту значення ймовірності p <0,01, то дана двійкова послідовність не є абсолютно довільною. В іншому випадку, вона є випадковою.
10.Тесттнатлінійнутскладність
В основі тесту лежить принцип роботи лінійного регістр зсуву зі зворотним зв'язком (англ. Linear Feedback Shift Register, LFSR). Мета - з'ясувати чи є вхідна послідовність досить складною для того, щоб вважатися абсолютно випадковою. Абсолютно довільні послідовності характеризуються довгими лінійними регістрами зсуву зі зворотним зв'язком. Якщо ж такий регістр занадто короткий, то передбачається, що послідовність не є повною мірою випадковою. У ході тесту обчислюється значення ймовірності p. Якщо p <0,01, то вважається, що вихідна послідовність не є довільною. В іншому випадку,робитьсятвисновоктпротїїтвипадковості.
11.Тесттнатперіодичність
Даний тест полягає в підрахунку частоти всіх можливих перекривання шаблонів довжини m біт протягом вихідної послідовності бітів. Метою є визначення дійсно кількість появ 2m перекриваються шаблонів довжиною m біт, приблизно таке ж як у випадку абсолютно випадковою вхідної послідовності біт. Остання, як відомо, має одноманітністю, тобто кожен шаблон довжиною m біт з'являється в послідовності з однаковою ймовірністю. Якщо обчислена в ході тесту значення ймовірності p <0,01, то дана двійкова послідовність не є абсолютно довільною. В іншому випадку, вона носить випадковий характер. Варто зазначити, що при m = 1 тест на періодичність переходить в частотний побітовий тест (№ 1).
12.Тесттприблизноютентропії
Як і в тесті на періодичність в даному тесті акцент робиться на підрахунку частоти всіх можливих перекривання шаблонів довжини m біт протягом вихідної послідовності бітів. Мета тесту - порівняти частоти перекривання двох послідовних блоків вихідної послідовності з довжинами m і m +1 з частотами перекривання аналогічних блоків в абсолютно довільній послідовності. Обчислюване в ході тесту значення ймовірності p повинно бути не менше 0,01. В іншому випадку (p <0,01), двійкова послідовність не є абсолютно довільною.
13.Тестткумулятивнихтсум
Тест полягає в максимальному відхиленні (від нуля) при довільному обході, що визначаються кумулятивної сумою заданих (-1, +1) цифр в послідовності. Мета даного тесту - визначити чи є кумулятивна сума часткових послідовностей, що виникають у вхідний последоваетльності, занадто великий або занадто маленькою у порівнянні з очікуваним поведінкою такої суми для абсолютно довільної вхідної послідовності. Таким чином, кумулятивна сума може розглядатися як довільний обхід. Для випадкової послідовності відхилення від довільного обходу повинно бути поблизу нуля. Для деяких типів послідовностей, які не є в повній мірі випадковими подібні відхилення від нуля при довільному обході будуть досить істотними. Якщо обчислена в ході тесту значення ймовірності p <0,01, то вхідні двійкова послідовність не є абсолютно випадковою. В іншому випадку, вона носить довільнийтхарактер.
14.Тесттнатдовільнітвідхилення
Суть даного тесту полягає в підрахунку числа циклів, мають строго k відвідувань при довільному обході кумулятивної суми. Довільний обхід кумулятивної суми починається з часткових сум після послідовності (0,1), перекладеної у відповідну послідовність (-1, +1). Цикл довільного обходу складається із серії кроків одиничної довжини, скоєних в довільному порядку. Крім того такий обхід починається і закінчується на одному і тому ж елементі. Мета даного тесту - визначити чи відрізняється число відвідувань певного стану всередині циклу від аналогічного числа в разі абсолютно випадковою вхідної послідовності. Фактично даний тест є набір, що складається з восьми тестів, проведених для кожного з восьми станів циклу: -4, -3, -2, -1 і +1, +2, +3, +4. У кожному такому тесті приймається рішення про ступінь випадковості вихідної послідовності у відповідності з наступним правилом: якщо обчислене в ході тесту значення ймовірності p <0,01, то вхідні двійкова послідовність не є абсолютно випадковою. В іншому випадку,вонатноситьтдовільнийтхарактер.
15.Іншийттесттнатдовільнітвідхилення
У цьому тесті підраховується загальна кількість відвідувань певного стану при довільному обході кумулятивної суми. Метою є визначення відхилень від очікуваного числа відвідувань різних станів при довільному обході. Насправді цей тест складається з 18 тестів, що проводяться для кожного стану: -9, -8, ..., -1 і +1, +2, ..., +9. На кожному етапі робиться висновок про випадковість вхідної послідовності. Якщо обчислена в ході тесту значення ймовірності p <0,01, то вхідні двійкова послідовність не є абсолютно випадковою. В іншому випадку, вона носить довільний характер.
Таблиця 3.2 - Статистичні тести NIST STS
| № | Статистичний тест | Статистика тесту c(S) | Дефект, що виявляється |
| 1 | Частотний (монобітний тест) | Нормалізована абсолютна сума значень елементів послідовності | Надто багато нулів або одиниць в послідовності |
| 2 | Частотний тест (в середині блоку) | Міра узгодження кількості одиниць, що спостерігаються, з тим, що очікується теоретично | Локалізовані відхилення частоти появи одиниць в блоці від ідеального значення 1/2 |
| 3 | Перевірка накопичених сум | Максимальне відхилення значень накопиченої суми елементів послідовності від початкової точки відрахунку (точка 0) | Велика кількість одиниць або нулів на початку або в кінці двійкової послідовності |
| 4 | Перевірка серій | Загальна кількість серій на усій довжині послідовності | Занадто швидка або занадто повільна зміна знаку під час генерації послідовності |
| 5 | Перевірка максимальної довжини серії в блоці | Міра узгодженості значень максимальної довжини, які спостерігаються, з тими значеннями, що очікуються теоретично | Відхилення від теоретичного закону розподілу максимальної довжини серій одиниць |
| 6 | Перевірка рангу двійкової матриці | Міра узгодженості значень рангів різного порядку, які спостерігаються, з значеннями, які очікуються теоретично | Відхилення емпіричного закону розподілу значень рангів матриць від теоретичного, що вказує на залежність елементів послідовності |
| 7 | Спектральний аналіз на основі дискретного перетворення Фур’є | Нормалізована різниця кількості частотних компонент, що спостерігаються з тієї, що очікується теоретично, якщо перевищує граничний рівень 95% | Виявлення періодичних доданків (трендів) в двійковій послідовності |
| 8 | Перевірка шаблонів, що перекриваються | Міра узгодженості кількості шаблонів, що перекриваються і за якими спостерігають, в послідовності з теоретичними значеннями | Велика кількість /77 - бітних серій одиниць в послідовності |
| 9 | Універсальний тест Маурера | Сума логарифма відстаней між 1-бітними шаблонами | Можливість стиснення послідовності |
| 10 | Ентропійний Тест | Міра узгодженості значення ентропії джерела, що спостерігається з тим, що теоретично очікується 3 випадкового джерела | Нерівномірність розподілу УП -бітних слів у послідовності (регулярність властивостей джерела) |
| 11 | Перевірка випадкових відхилень | Міра узгодженості кількості візитів, що спостерігаються при випадковому блуканні з заданим станом в середині циклу, у порівнянні з тим, що очікується теоретично | Відхилення від теоретичного закону розподілу візитів в конкретний стан при випадковому блуканні |
| 12 | Перевірка випадкових відхилень (варіант) | Загальна кількість візитів при випадковому блуканні | Відхилення від теоретично очікуваної кількості загальної кількості візитів при випадковому блуканні в заданий стан |
| 13 | Послідовний тест | Міра узгодженості кількості всіх варіантів 77 - бітних шаблонів, які спостерігаються з тією кількістю, яка очікується теоретично | Нерівномірність розподілу 77-бітних слів у послідовності |
| 14 | Перевірка стиснення згідно 3 алгоритмом Лемпеля-Зіва | Кількість різних слів у послідовності | Велика ступінь стиснення послідовності, що тестується і ступенем стиснення очікуваної випадкової послідовності |
| 15 | Перевірка шаблонів, що не перекриваються | Міра узгодженості очікуваної кількості неперіодичних шаблонів в послідовності з теоретичним значенням | Велика кількість заданих неперіодичних шаблонів в послідовності |
| 16 | Перевірка лінійної складності | Міра узгодженості очікуваної кількості подій, що лежать в основі появи фіксованої довжини еквівалентного ЛРР для заданого блоку з теоретичним | Відхилення емпіричного розподілу довжини еквівалентних ЛРР для послідовностей фіксованої довжини від теоретичного закону розподілу для випадкової послідовності, що вказує на недостатню складність тестованої послідовності |
Основним недоліком NIST STS є велика складність стандарту тестування, що не уможливлює його використання в реальному часі, тому він рекомендується для використання в наукових дослідженнях та випробуваннях. Але в різних практичних додатках необов’язково використовувати всі 188 тестів.
Висновки до розділу
З розвитком технологій, зростають і обчислювальні можливості, наприклад для криптографічного алгоритму, який міг бути взломаний за декілька років, зараз потрібно декілька хвилин. Генератор ПВП є обовязковим в будь-якій системі захисту, використовуються в операційних системах для створення векторів, ідентифікації обєктів та паролів. Але не всі генератори ПВП є ефективними до захисту, потрібно щоб генератор міг забезпечити надійність, безпеку процесів передачі, обробки, зберігання, в ідеалі бути майже невідмінним від істинно випадкової послідовності. Для того щоб генератор ПВП відповідав вимогам(наприклад криптографічна стійкість більш важлива швидкості та ефективності) проводиться його тестування під ту чи іншу задачу та вимогами до неї.