Криптографічно стійкий генератор псевдовипадкових чисел

Безпека деяких алгоритмів шифрування залежить від стійкості генератора випадкових чисел завдяки якому формується ключ або послідовність біт. Шифри з досконалою стійкістю потребують повністю випадкового ключа такої ж довжини, як і вихідний ключ. Проте у більшості випадків, насправді випадкові послідовності біт необхідної довжини не доступні. Тому були розроблені методи отримання псевдовипадкових послідовностей. Такі послідовності можуть справляти враження випадкових, але отримані вони в результаті роботи детермінованого алгоритму. Такі алгоритми називають генераторами псевдовипадкових чисел. Отримавши порівняно невеликий випадковий вхідний рядок (так зване випадкове початкове значення — англ. seed), такі алгоритми здатні обчислити доволі довгі псевдовипадкові послідовності[1].

Звичайні генератори псевдовипадкових послідовностей можуть обчислювати послідовності з якісними статистичними показниками. Отримані послідовності можуть бути придатними для використання в методах Монте-Карло, але непридатними для використання в криптографічних алгоритмах. Наприклад, таємні параметри генераторів псевдовипадкових послідовностей на основі лінійного конгруентного методу або на основі регістру зсуву з лінійним зворотнім зв'язком можут бути відтворені з доволі невеликої кількості згенерованих ними елементів послідовності. Таким чином, стає можливим відтоврити всю згенеровану ними послідовність[1].

Серед відомих методів побудови криптографічно стійких генераторів псевдовипадкових послідовностей важливу роль відіграють генератори на основі односторонніх підстановок[1].

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

Оскільки генератори псевдовипадкових чисел є детермінованими алгоритмами, тому буть-хто здатен обчислити елементи генерованої послідовності для заданого початкового значення (англ. seed). А оскільки, зазвичай, алгоритми таких генераторів загально відомі, особливі зусилля мають бути скеровані на те, що б втаємничити їхні початкові значення та унеможливити їхнє обчислення на основі згенерованої послідовності. Крім того, саме початкове значення бажано зробити випадковим та непередбачуваним[3].

Властивості генераторів псевдовипадкових чисел оцінюють з використанням низки кількісних показників, основними з яких є:[4]

• період ${\displaystyle l}$ (довжина) послідовності псевдовипадкових чисел;
• основа алфавіту ${\displaystyle m}$;
• ймовірність перекриття в просторі або в часі двох сегментів ${\displaystyle Y_{r}}$ та ${\displaystyle Y_{\mu }}$, тобто в різних абонентів або в одного абонента протягом часу, так, що ${\displaystyle Y_{r}=Y_{\mu }}$;
• структурна скритність (еквівалентна складність) ${\displaystyle S_{e}}$ послідовності ${\displaystyle Y}$;
• кількість (ентропія ${\displaystyle N_{k}(H_{k})}$ джерела) ключів для випадку, коли генератор випадкових чисел використовують як джерело ключів;
• відстань рівнозначності ${\displaystyle l_{0}}$ конкретної послідовності ${\displaystyle Y_{\nu }}$;
• безпечний час генератора випадкових чисел ${\displaystyle t_{b}}$;
• складність ${\displaystyle I_{y}}$ формування послідовності ${\displaystyle Y}$;
• довжина параметрів зворотного зв'язку;
• властивості випадковості, рівноймовірності, незалежності та однорідності.

За всіма названими показниками до генератора послідовностей псевдовипадкових чисел висувають низку вимог. Так, період повторення ${\displaystyle l_{n}\geq l_{z}}$, тобто повинен бути не менше заданого, можливість змінної основи алфавіту ${\displaystyle m}$, ймовірність перекриття ${\displaystyle P_{n}<P_{z}}$ менше допустимої, структурна скритність ${\displaystyle S\geq S_{g}}$, ентропія джерела ключів ${\displaystyle H\geq H_{g}}$, відстань рівнозначності ${\displaystyle l_{0}>l_{g}}$, безпечний час ${\displaystyle t_{b}<t_{g}}$, тобто не менш допустимих. Крім того, реалізації ${\displaystyle Y}$ i повинна задовольняти вимогам випадковості, рівноймовірності, незалежності та однозначності[4].

Крім того, до генераторів псевдовипадкових послідовностей можуть бути висунуті вимоги прямої стійкості (англ. forward unpredictability): попри знання всіх попередніх чисел послідовності наступні числа мають бути непередбачуваними якщо не відоме початкове значення генератора. Зворотна стійкість вимагає унеможливити обчислення початкового значення на основі будь-якої кількості згенерованих чисел послідовності. Кореляція між початковим значенням та згенерованою послідовністю має бути неочевидною, а кожен наступний елемент має справляти враження реалізації випадкової події з імовірністю ½[3].

Загальним підходом до генерування ключів, ключової інформації та параметрів є стандартизація методів, механізмів і практичних (конкретних) алгоритмів їх генерування[4].

Нині розроблені та прийняті регіональні і міжнародні стандарти, у яких визначені вимоги, методи, механізми та алгоритми реалізації генераторів. Оскільки при застосуванні засобів криптографічного захисту інформації необхідністю є відновлення ключів та ключової інформації у просторі й часі, у зазначених стандартах розглянуті лише детерміновані генератори випадкових бітів[4].

Базовими міжнародними стандартами, що стандартизують алгоритми генерації послідовностей випадкових чисел є:[4]

• міжнародний стандарт ISO/IEC 18031 «Information technology — Random number generation», який визначає алгоритми генерації псевдовипадкових і випадкових чисел, а також визначає статистичні тести перевірки генераторів;
• міжнародний стандарт ISO/IEC 18032 «Information technology — Prime number generation», який визначає методи генерації простих чисел і методи тестування чисел на простоту;
• національний стандарт ДСТУ ISO/IEC19790 «Інформаційна технологія — Методи захисту — Вимоги щодо захисту для криптографічних модулів».

Додаткові вимоги до алгоритмів та реалізацій методів і засобів генерації та тестування послідовностей випадкових чисел визначені національними та промисловими стандартами США: FIPS 140-3, ANSI X9.17, ANSI X9.31, ANSI X9.44 та ін., а також рекомендаціями NIST — NIST SP 800-22 і рекомендаціями органу зі стандартизації Німеччини — AIS-20, AIS-31 та інші[4].

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

Найбільш прийнятними (з точки зору практичного використання) методиками тестування є методики NIST STS, FIPS PUB 140-1, AIS 20 та AIS 31[4].

ANSI X9.17

Генератор псевдовипадкових послідовностей визначений у стандарті ANSI X9.17 (Financial Institution Key Management (wholesale)) пройшов сертифікацію та прийнятий як стандарт FIPS. На вході він отримує TDEA (варіант ключів 2) набір ключів k та випадкове початкове число розміром 64 біт s.[5] Для обчислення наступного псевдовипадкового числа послідовності він:

• Бере поточний час D з найбільшою доступною точністю (мілісекунди, тощо).
• Обчислює проміжне значення t = TDEA_k(D)
• Обчислює псевдовипадкове число x = TDEA_k(s ⊕ t), де ⊕ позначає побітову операцію виключної диз'юнкції.
• Оновлює значення початкового числа s = TDEA_k(x ⊕ t)

• Jan Krhovják, Abstract Analysis, demands, and properties of pseudorandom number generators

• Генерація випадкових чисел

• A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications. Special Publication (вид. Revision 1a). NIST. квітень 2010. NIST 800-22.
• RFC 4086 Randomness Requirements for Security (2005)
• Random Bit Generation на сайті NIST