Анотація. Метою дослідження є перевірка можливості використання розробленого генератора випадкових чисел [1], який використовує як джерело ентропії шуми звукової карти, в алгоритмах симетричної криптографії. Ключові слова: генератор випадкових чисел, джерело ентропії, статистичний критерій, закон розподілу, симетрична криптографія.
використовує випадкові числа. Вектори ініціалізації, модифікатори геш-функцій,
унікальні параметри при роботі з цифровими підписами повинні прийматися
випадковими [
Методологія
У 1999 році фахівцями NIST в рамках проекту AES (Advanced Encryption
Standard) був розроблений набір статистичних тестів NIST Statistical Test Suite),
а також запропонована методика проведення статистичного тестування
генераторів випадкових чисел [
У даній роботі розглядаються критерії прийняття рішення про проходження
послідовністю статистичного тесту, набір статистичних тестів NIST і наводяться
результати експериментальних досліджень властивостей ГВЧ, описаного в
роботі [
Порядок тестування окремої двійкової послідовності S виглядає наступним чином. 1. Висувається нульова гіпотезу Н0 – припускаємо, що дана двійкова послідовність S випадкова. 2. За послідовністю S розраховується статистику тесту c(S). 3. З використанням спеціальної функції та статистики тесту розраховується значення ймовірності P=f(c(S)), P[0; 1]. 4. Значення ймовірності P порівнюється з рівнем значущості α, α[0,001; 0,01]. Якщо P≥α, то гіпотеза Н0 приймається. В іншому випадку приймається альтернативна гіпотеза. Обраний пакет статистичних тестів може використовуватися для вирішення наступних завдань: ─ виявлення ГВЧ (ГПВЧ), які формують «погані» двійкові послідовності; Для перевірки було генеровано три випадкові послідовності в діапазоні [0; 255] розміром 10 000 елементів.
Пакет NIST STS було завантажено з офіційного сайту Національного інституту
стандартів і технологій (National Institute of Standards and Technology) [
Перед тим, як було протестовано кожну з трьох послідовностей, був побудований загальний графік розподілу для послідовностей, показаний на рис. 1. По осі x відкладено значення байту, а по осі y кількість байтів з таким значенням у послідовності.
Рис. 1. Графік розподілів трьох генерованих послідовностей З рис. 1 видно, що кожна із послідовностей має свої піки та особливості, тому вони підходять для перевірки пакетом NIST STS. Першим тестом, проведеним над генерованими послідовностями, був Binary Matrix Rank Test. Основну увагу в даному тесті приділяють рангу непересічної підматриці всієї послідовності. Метою цього тесту є перевірити лінійну залежність між підрядками фіксованої довжини оригінальної послідовності. Варто зауважити, що цей тест також використовуються в серії тестів DIEHARD.
Інтерпретація цього тесту: великі значення χ2 (obs) вказують на те, що відхилення рангового розподілу від того, що відповідає випадковій послідовності, є значним. В результаті проходження даного тесту результатом, за яким можна зазначати, що послідовність випадкова, є значення p. Якщо обчислене p<0,01, то вважається, що послідовність не випадкова. Інакше послідовність є випадковою.
Результати проходження тесту Binary Matrix Rank Test для першої послідовності показані на рис. 2.
Для даної послідовності значення p=0,203766, що свідчить про випадковість генерованої послідовності. Також значення χ2=3,181562 є малим, тобто відхилення рангового розподілу від того, що відповідає випадковій послідовності, є незначним.
Рис. 2. Binary Matrix Rank Test для першої послідовності Для послідовностей 2 і 3 значення p=0,374306 та p=0,648387, що також вказує на їх випадковість. Відповідні значення χ2: 1,965364 та 0,866535 є досить малими, що знову свідчить про те, що відхилення рангового розподілу від того, що відповідає випадковій послідовності, є незначним.
При цьому варто відмітити, що третя генерована послідовність з отриманих результатів є більш «випадковою» через більше значення p та менше значення χ2 у порівнянні із послідовностями 1 та 2.
Наступний тест, що використовувався для перевірки випадковості генерованих послідовностей, це Non-overlapping Template Matching Test. Основною для цього тесту є кількість випадків попередньо заданих цільових рядків. Мета цього тесту – виявлення генераторів, що виробляють забагато випадків даної аперіодичної моделі. Для цього тесту використовується m-бітне вікно, що шукає конкретний m-бітний шаблон. Якщо шаблон не знайдено, вікно пропускає одну бітну позицію. Якщо шаблон знайдено, вікно пропускає біт після знайденого шаблону, і пошук відновлюється.
Цей тест відкидає послідовності, що демонструють занадто багато або занадто мало випадків даної аперіодичної картини.
Тест можна інтерпретувати як відхилення послідовностей, що виявляють нерегулярні входження даної неперіодичної картини.
Перша генерована послідовність за тестом Non-overlapping Template Matching Test дала результуючий файл, показаний на рис. 3. Рис. 3. Non-overlapping Template Matching Test для першої послідовності Для кожного із 148-ми індексів значення p=0,010549, що дає підставу програмі видавати результат Assignment = SUCCESS (успіх), що означає успішне проходження тесту та підтверджує «випадковість» генерованої послідовності.
Для послідовності 2 і 3 значення p є аналогічним, як і помітки про успішне проходження даними послідовностями тесту Binary Matrix Rank.
Наступний тест, що використовувався для перевірки випадковості генерованих послідовностей, це Overlapping Template Matching Test. Основна увага тесту приділяється кількості випадків попередньо заданих цільових рядків. Даний тест використовує вікно m-біт для пошуку конкретного m-бітового шаблону. Якщо шаблон не знайдено, вікно пропускає бітну позицію. Коли шаблон знайдено, вікно пропускає лише один біт, перш ніж відновити пошук.
Цей тест відкидає послідовності, які показують занадто багато або дуже мало випадків m-пробілів, але може бути легко модифікований для виявлення нерегулярних випадків будь-якого періодичного малюнка.
Для першої генерованої послідовності відповідний результат продемонстровано на рис. 4:
Рис. 4. Overlapping Template Matching Test першої послідовності З отриманих результатів ми бачимо значення p=0,049053 та значення χ2=11,119950, що відповідають за успішне проходження генерованої послідовності даного тесту. Для другої та третьої послідовності значення p та χ2 є аналогічними, що підтверджує їх випадковість.
Наступний тест, яким було перевірено генеровані послідовності, був Serial Test. Основна увага цього тесту сконцентрована на частотах всіх можливих перекриваючих m-бітних шаблонів по всій послідовності. Мета цього тесту полягає в тому, щоб визначити, чи є число входжень 2m m-біт приблизно таким же, як було б очікувано для випадкової послідовності. Випадкові послідовності однорідні, тобто кожен m-бітний шаблон має такий же шанс з’являтись, як і будьякий інший m-розрядний шаблон. Варто звернути увагу, що для m=1 послідовний тест еквівалентний частотному тесту.
Серійний тест (генералізований) – це перелік процедур, що базується на тестуванні однорідності розподілу моделей заданих довжин.
У результаті проходження тесту першою послідовністю було отримано два значення р, та відповідні значення ψ (рис. 5).
Рис. 5. Serial Test першої послідовності З отриманих результатів можна зробити висновок, що послідовність є випадковою за Serial Test. Щодо послідовностей 2 і 3, то вони мають аналогічні показники значень, що також підтверджує випадковість розробленого генератора випадкових чисел.
Останнім тестом, що проходять генеровані послідовності, є Linear Complexity Test. Основна увага цього тесту приділена довжині регістру зсуву з лінійним зворотним зв’язком (LFSR). Метою цього тесту є визначення, чи є послідовність досить складною, щоб вважатись випадковою. Випадкові послідовності характеризуються більш тривалими LFSR. Якщо LFSR занадто короткий, то послідовність вважається невипадковою.
Для першої генерованої послідовності в результаті виконання даного тесту було отримано результати, показані на рис. 6.
Рис. 6. Linear Complexity Test першої послідовності За отриманими результатами p=0,167974 та χ2=9,101060 можна зробити висновок, що генерована послідовність є випадковою. Щодо інших послідовностей: для другої послідовності p=0,783217 та χ2=3,201098; для третьої p=0,167974 та χ2=9,101060. Тобто, значення першого і третього розподілу збігається, в той же час, значення другого розподілу відрізняється, проте, всі три послідовності є випадковими. 4
Висновки 1. Найкращі результати було продемонстровано в тестах Binary Matrix Rank та Linear Complexity, де кожна із послідовностей мала власні значення p та χ2, що давало можливість порівняти роботу генератора випадкових чисел в однакових умовах, проте, при різних генерованих послідовностях. Не зважаючи на відмінні результати, всі три послідовності успішно пройшли тест. Загалом створений апаратний генератор випадкових чисел, згідно результатів тестування пакетом NIST STS, можна вважити таким, що задовольняє вимоги пройдених тестів. 2. Створена бібліотека генерації випадкових чисел може бути використана в проектах, які мають потребу в високоякісних послідовностях випадкових чисел. В майбутньому генератор випадкових чисел може бути вдосконалений за рахунок використання більш чистого звуку та реалізації можливості вибору користувачем розподілу, за яким генеруватимуться випадкові числа. Список використаних джерел References (translated and transliterated)