Криптографічні генератори випадкових чисел виробляють випадкові числа, які використовуються в криптографічних додатках, наприклад - для генерації ключів.
Звичайні генератори випадкових чисел, які є в багатьох мовах програмування і програмних середовищах, не підходять для потреб криптографії (вони створювалися з метою отримати статистично випадкове розподіл, криптоаналитики можуть передбачити поведінку таких випадкових генераторів).
Коректна реалізація асиметричних криптоалгоритмів, наприклад RSA, вимагає додавати до кожної порції відкритого тексту кілька випадкових байт.
Відмінність генератора псевдовипадкових чисел (ГПСЧ) від генератора випадкових чисел (ГВЧ)
Джерела ентропії використовуються для накопичення ентропії з подальшим отриманням з неї початкового значення (initial value, seed), необхідного для генераторів випадкових чисел (ГВЧ) для формування випадкових чисел. ГПСЧ використовує єдине початкове значення, звідки і слід його псевдовипадковий, а ГСЧ завжди формує випадкове число, маючи на початку високоякісну випадкову величину, надану різними джерелами ентропії. Ентропія - це міра безладу. Інформаційна ентропія - міра невизначеності або непередбачуваності інформації. Можна сказати, що ГВЧ = ГПСЧ + джерело ентропії.
Передбачувана залежність між числами.
Передбачуване початкове значення генератора.
Мала довжина періоду генерується послідовності випадкових чисел, після якої генератор зациклюється.
Лінійний конгруентний ГПСЧ (LCPRNG)
Поширений метод для генерації псевдовипадкових чисел, що не володіє криптографічного стійкістю. Лінійний конгруентний метод полягає в обчисленні членів лінійної рекурентної послідовності по модулю деякого натурального числа m де a (multiplier), c (addend), m (mask) - деякі цілочисельні коефіцієнти. Отримана послідовність залежить від вибору стартового числа (seed) X0 і при різних його значеннях виходять різні послідовності випадкових чисел. Нехай генератор видав кілька випадкових чисел X0, X1, X2, X3. Виходить система рівнянь
Нехай потрібно отримати датчик експоненціально розподілених випадкових величин. В цьому випадку F (x) = 1 - exp (-lambda * x). Тоді з рішення рівняння y = 1 - exp (-lambda * x) отримуємо x = -log (1-y) / lambda. Можна помітити, що вираз під знаком логарифма в останній формулі має рівномірний розподіл на відрізку [0,1), що дозволяє отримувати іншу, але так само розподілену послідовність за формулою: x = -log (y) / lambda, де y є випадкова величина (rand ()).
Генератор псевдовипадкових чисел (ГПСЧ. Англ. Pseudorandomnumbergenerator, PRNG) - алгоритм, який породжує послідовність чисел, елементи якої майже незалежні один від одного і підкоряються заданому розподілу (зазвичай рівномірному).
Сучасна інформатика широко використовує псевдовипадкові числа в самих різних додатках - від методу Монте-Карло і імітаційного моделювання до криптографії. При цьому від якості використовуваних ГПСЧ безпосередньо залежить якість одержуваних результатів. Ця обставина підкреслює відомий афоризм Роберта Р. Кавью з ORNL: «генерація випадкових чисел занадто важлива, щоб залишати її на волю випадку».
Ніякої детермінований алгоритм не може генерувати повністю випадкові числа, він може тільки апроксимувати деякі їх властивості. Як сказав Джон фон Нейман, «всякий, хто має схильність до арифметичним методам отримання випадкових чисел, грішний поза всяких сумнівів».
Будь ГПСЧ з обмеженими ресурсами рано чи пізно зациклюється - починає повторювати одну і ту ж послідовність чисел. Довжина циклів ГПСЧ залежить від самого генератора і становить близько 2 n / 2. де n - розмір внутрішнього стану в бітах, хоча лінійні конгруентні і LFSR-генератори мають максимальними циклами близько 2 n. Якщо породжувана послідовність ГПСЧ сходиться до занадто коротким циклам, то такий ГПСЧ стає передбачуваним і непридатним для практичного застосування.
Більшість простих арифметичних генераторів хоча і володіють великою швидкістю, але страждають від багатьох серйозних недоліків:
Занадто короткий період / періоди.
Послідовні значення не є незалежними.
Деякі біти «менш випадкові», ніж інші.
Нерівномірний одномірний розподіл.
Зокрема, алгоритм RANDU, десятиліттями використовувався на основному комплекті, виявився дуже поганим [2] [3]. що викликало сумніви в достовірності результатів багатьох досліджень, які використовували цей алгоритм.
Найбільш поширені лінійний конгруентний метод, метод Фібоначчі з запізнюваннями, регістр зсуву з лінійним зворотним зв'язком, регістр зсуву з узагальненою зворотним зв'язком.
Нарівні з існуючою необхідністю генерувати легко відтворювані послідовності випадкових чисел, також існує необхідність генерувати абсолютно непередбачувані або просто абсолютно випадкові числа. Такі генератори називаються генераторами випадкових чисел (ГВЧ - англ. Randomnumbergenerator, RNG). Так як такі генератори найчастіше застосовуються для генерації унікальних симетричних і асиметричних ключів для шифрування, вони найчастіше будуються з комбінації криптостійкого ГПСЧ і зовнішнього джерела ентропії (і саме таку комбінацію тепер і прийнято розуміти під ГСЧ).
Майже всі великі виробники мікрочіпів поставляють апаратні ГВЧ з різними джерелами ентропії, використовуючи різні методи для їх очищення від неминучої передбачуваності. Однак на даний момент швидкість збору випадкових чисел усіма існуючими мікрочіпами (кілька тисяч біт в секунду) не відповідає швидкодії сучасних процесорів.
У сучасних дослідженнях здійснюються спроби використання вимірювання фізичних властивостей об'єктів (наприклад, температури) або навіть квантових флуктуацій вакууму в якості джерела ентропії для ГСЧ. [4]
Приклад найпростішого ГВЧ з джерелом ентропії [ред | правити вихідний текст]
Якщо в якості джерела ентропії використовувати поточний час, то для отримання натурального числа від 0 до N досить обчислити залишок від ділення поточного часу вміллісекундах на число N +1. Недоліком цього ГСЧ є те, що протягом однієї мілісекунди він видає один і той же число.
Криптографічно стійкий генератор псевдовипадкових чисел
Криптографічно стійкий генератор псевдовипадкових чисел (англ. Cryptographically secure pseudorandom number generator. CSPRNG) - це генератор псевдовипадкових чіселс певними властивостями, що дозволяють використовувати його в криптографії. Багато прикладні завдання криптографії вимагають випадкових чисел, наприклад:
Одноразові випадкові числа (англ. Nonces)
Сіль в схемах цифрового підпису, наприклад ECDSA
Необхідну «якість» випадковості змінюється від завдання до завдання. Наприклад, генерація одного випадкового числа в деяких протоколах вимагає тільки унікальності, тоді як генерація майстер-ключа або одноразового шифроблокнота вимагає високої ентропії. В ідеалі, генерація випадкових чисел в КСГПСЧ використовує високонадійний джерело ентропії, яким може бути апаратний генератор випадкових чисел або хід непередбачуваних процесів в системі - хоча в обох випадках можливі несподівані уразливості [1] [2]. З точки зору теорії інформації кількість випадковості - ентропія, яка може бути отримана, дорівнює ентропії, що надається системою. Але найчастіше в реальних ситуація потрібно більше випадкових чисел, ніж можна отримати при існуючій ентропії. До того ж процедура отримання випадковості з самої системи вимагає досить багато ресурсів (пам'яті і часу). У таких випадках, виправдано використання КСГПСЧ - це дозволяє «розтягнути» наявну ентропію на більше число біт. Коли вся ентропія доступна до виконання криптографічного алгоритму, виходить потоковий шифр [3]. Однак деякі криптосистеми дозволяють додавати ентропію в міру роботи, в такому випадку алгоритм не є еквівалентом потокового шифру і не може використовуватися в цій якості. Таким чином, розробка потокових шифрів і КСГПСЧ тісно пов'язані.