6. Генерування випадкових чисел. Використання та джерела випадкових чисел. Генератори псевдовипадкових чисел.

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

Випадкові числа відіграють важливу роль при шифруванні в різних додатках мережевого захисту. У цьому розділі ми спочатку проведемо короткий огляд можливостей застосування випадкових чисел в різних схемах захисту мережі, а потім розглянемо деякі підходи до генерування випадкових чисел.

Використання випадкових чисел

Ряд алгоритмів захисту мережі, заснованих на засобах криптографії, припускає використання випадкових чисел. До таких алгоритмам відносяться, зокрема, наступні.

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

• Генерування сеансових ключів, що виконується або центром розподілу ключів, або одним з учасників з'єднання.

• Генерування ключів для алгоритму RSA шифрування з відкритим ключем.

З цих додатків випливає дві чітких і необов'язково поєднуваних вимоги до використовуваної послідовності випадкових чисел: випадковість і непередбачуваність:

Випадковість

Традиційно при генеруванні послідовності нібито випадкових чисел потрібно, щоб послідовність одержуваних чисел була випадковою в деякому цілком певному статистичному сенсі. Для перевірки будь-якої послідовності на випадковість зазвичай служить два наступних критерії:

• однорідність розподілу: розподіл чисел в послідовності має бути однорідним, тобто частота появи в послідовності конкретного значення повинна бути приблизно однаковою для всіх значень;

• незалежність: жодне зі значень послідовності не повинно логічно виводитися з інших значень.

Є цілком чіткі алгоритми для перевірки того, що деяка після-довність чисел відповідає заданому розподілу (наприклад, однорідному), але от алгоритму, що дозволяє "довести" незалежність, немає. Тут зазвичай застосовується ряд тестів, що дозволяють продемонструвати, що послідовність не є незалежною. Загальна стратегія полягає в застосуванні таких тестів до тих пір, поки переконання в незалежності послідовності не стане досить правдоподібним.

У контексті нашої теми використання послідовності чисел, що здаються статистично випадковими, часто випливає з криптографічного структури самого алгоритму шифрування. Наприклад, однією з головних вимог схеми RSA шифрування з відкритим ключем, є можливість генерування простих чисел. Взагалі-зовсім не просто визначити, чи є дане досить велике число N простим чи ні. Безпосередня перевірка припускає розподіл числа N на кожне ціле число, менше . Якщо N виявляється порядку, скажімо, 10¹⁵⁰, що не є нереальним для сучасних методів криптографії з відкритим ключем, то така перевірка виявляється сьогодні далеко за рамками аналітичних знань людини і обчислювальних можливостей комп'ютера. Однак існує ряд ефективних алгоритмів перевірки простоти числа за допомогою використання послідовності випадково вибраних цілих чисел у відносно простих обчисленнях. Якщо така послідовність досить довга (але істотно менше ніж ), простота тестованого числа може бути визначена майже напевно. Такий підхід, відомий як рандомізація, служить для створення багатьох алгоритмів. По суті, якщо проблема занадто складна або вимагає занадто багато часу для точного рішення, то для знаходження рішення з будь-якої необхідної часткою впевненості застосовується більш простий і більш швидкий спосіб, заснований на рандомізації.

Непередбачуваність

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

Джерела випадкових чисел

Не можна сказати, що джерела істинно випадкових чисел є дуже поширеними пристроями. Потенційно такими джерелами можуть бути фізичні генератори шумів, такі як імпульсні детектори іонізуючого випромінювання, газорозрядні лампи і конденсатори з витоком струму. Однак такі пристрої можуть знайти досить обмежене застосування в додатках захисту мережі. Тут є проблеми як з випадковістю, так і з точністю одержуваних при цьому чисел [BRIG79], не кажучи вже про проблеми підключення такого роду пристроїв до кожної системі в мережі. Альтернативою може бути використання якого-небудь з перевірених і опублікованих наборів випадкових чисел (див., наприклад, [RAND55], [TIPP27]). Однак такі набори пропонують досить обмежений джерело чисел у порівнянні з потенційними вимогами додатка захисту великої мережі. До того ж, хоча числа із зазначених книг дійсно демонструють статистичну випадок-ність, вони цілком передбачувані, так як опонент, який знає, яка книга взята за основу, просто може взяти її копію.

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

Вам, можливо, нелегко буде усвідомити причини можливості використання в якості випадкових чисел, що генеруються детермінованим алгоритмом. Незважаючи на те що такий підхід може викликати загальфілософські заперечення, на практиці він, загалом, працює. Як зауважив один експерт в області теорії ймовірності [НАММ91], для практичних цілей нам доводиться прийняти незграбний принцип "відносної випадковості", що означає, що в рамках запропонованого підходу ми не бачимо причин, за якими розглядаються об'єкти не будуть поводитися так, як ніби вони випадкові (як зазвичай вимагає теорія). Цей принцип виявляється досить суб'єктивним і дуже нелегкотравним для пуристів, але саме його мають на увазі статистики, коли розглядають "випадкову вибірку", - вони сподіваються, що використовувані ними при цьому результати будуть проявлятися приблизно так само, як і при повному обліку всього вибіркового простору, який передбачається в теорії.

Генератори псевдовипадкових чисел

Безумовно, найпопулярнішим алгоритмом для генерування псевдовипадкових чисел є алгоритм, запропонований Лемером (Lehmer) [LEHM51] і званий методом лінійного порівняння. Цей алгоритм має чотири наступних параметра.

т	модуль порівняння	т > 0
а	множник	0 <а < т
с	прирощення	0 < с < т
Хо	початкове або породжуюче число	0 < Х0 < т

Послідовність випадкових чисел {Х₀} виходить за допомогою ітерацій наступного співвідношення:

При цьому якщо m, а, c і Х₀ є цілими, то буде отримана послідовність цілих чисел з діапазону O <Х_n< m.

Вибір значень для а, с і m виявляється дуже важливим з точки зору розробки хорошого генератора випадкових чисел. Розглянемо, наприклад, випадок а = с = 1. Породжувана при цьому послідовність явно не буде задовільною. Тепер розглянемо значення а - 7, с = 0, m = 32 і Х₀ = 1. У цьому випадку генерується послідовність {7, 17, 23, 1, 7, ...}, яка також явно не буде задовільною. З 32 можливих значень тут виявляється задіяними тільки 4 (в даному випадку говорять, що послідовність має період 4). Якщо ж, залишивши інші значення колишніми, змінити значення а і покласти а = 5, то результуючої послідовністю буде {1, 5, 25, 29, 17, 21, 9, 13, 1, ...} і її період буде вже дорівнювати 8.

Бажано, щоб m було дуже великим, щоб потенційно могли генерувати дуже довгі серії різних випадкових чисел. Загальним правилом тут є вибір значення m, близького до максимально допустимого для даного комп'ютера неотрицательную цілого числа. Тому досить часто значення m вибирається рівним або майже рівним значенню 2³¹.

В [PARK88] пропонується три наступних критерії, за якими можна оцінити якість будь-якого генератора випадкових чисел.

1. Генеруюча функція повинна бути функцією повного періоду, тобто функція повинна породити всі числа від 0 до m перш, ніж числа почнуть повторюватися.

2. Генерируемая послідовність повинна вести себе як випадкова. Насправді ця послідовність перестав буде випадковою, оскільки генерується детермінованим алгоритмом, але існує безліч статистичних тестів, які можна використовувати для того, щоб оцінити ступінь випадковості поведінки послідовності.

3. Генеруюча функція повинна ефективно реалізовуватися в рамках 32-бітової арифметики.

Всі ці три критерії можуть бути задоволені при відповідному виборі значень а, с та m. Щодо критерію Т, можна довести, що якщо m є простим і c = 0, то для певних значень а період генерується функцією послідовності виявляється рівним m - 1 і в цій послідовності буде відсутня тільки значення 0. У 32-бітової арифметики зручним простим значенням для m є значення 231 - 1. У цьому випадку генеруюча функція приймає вид

Із понад двох мільйонів можливих значень а тільки декільком множникам відповідають функції, що витримують всі три тести. Одним з таких значень є значення а = 7⁵ = 16807, яке було знайдено і використано для сімейства комп'ютерів IBM 360 [LEWI69]. Відповідний генератор знаходить дуже широке застосування, і тому він був підданий більш ретельному аналізу, ніж будь-який інший генератор псевдовипадкових чисел. Він нерідко рекомендується для статистичного та імітаційного моделювання різних процесів (див., наприклад, [JAIN91], [SAUE81]).

Перевагою алгоритму лінійного порівняння є те, що якщо вибрати відповідні множник і модуль порівняння, то генерується послідовність чисел виявляється статистично неотличимой від послідовності чисел, обираних випадково (але безповоротно) з множини чисел 1, 2, ..., m - 1. Але в самому алгоритмі немає нічого випадкового взагалі, окрім вибору початкового значення Х₀. Якщо це значення вибрано, інші числа послідовності визначаються ним однозначно. Це виявляється дуже важливим з точки зору криптоаналізу.

Якщо противник знає, що використовується алгоритм лінійного порівняння і якщо до того ж йому відомі параметри алгоритму (наприклад, а = 7⁵, с = 0, m = 2³¹ -1), то, відкривши всього одне число, супротивник зможе отримати і всі наступні. Але навіть якщо опонент знає тільки те, що обраний алгоритм лінійного порівняння, знання невеликої частини послідовності вже достатньо для того, щоб визначити всі параметри алгоритму. Припустимо, наприклад, що супротивник зможе визначити значення для Х₀, Х₁, X₂, і Х₃. Тоді

Ці рівняння можуть бути вирішені щодо a, c і m. Отже, хоча і зручно використовувати хороший генератор псевдовипадкових чисел, бажано подбати про те, щоб генерована послідовність була насправді невідтворюваною, щоб знання частині послідовності не давало опонентові можливості визначити наступні елементи послідовності. Ця мета може бути досягнута через безліч способів. Наприклад, в [BRIG79] пропонується змінювати потік випадкових чисел, використовуючи для цього системний годинник. Один із способів на основі системних годинників полягає в ініціалізації нової послідовності після отримання кожних N чисел, використовуючи для початкового числа поточне значення часу (mod m). А можна просто додавати до кожного випадковому числу поточне значення часу (mod m).

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

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

Циклічне шифрування

На рис. 6.1 показана схема підходу, запропонованого в [MEYE82]. У даному випадку за допомогою головного ключа генеруються сеансові ключі. Лічильник з періодом N забезпечує вводяться параметри логіки шифрування. Наприклад, якщо потрібно отримати 56-бітові ключі DES, можна використовувати лічильник з періодом, рівним 2⁵⁶. Після отримання кожного ключа лічильник збільшується на одиницю. Тому отримувані таким чином псевдовипадкові числа будуть повторюватися з відповідним періодом: кожне з вихідних чисел Х₀, Х₁, .... Х_N-1 визначатиметься різними значеннями лічильника, і тому Х₀ ≠ Х₁ ≠ ... ≠ X_N-1. З огляду на те що головний ключ захищений, виявляється неможливим за допомогою обчислень отримати будь секретний ключ, знаючи один або кілька отриманих раніше ключів.

Щоб зробити алгоритм ще більш захищеним, замість значень простого лічильника в якості значень, які вводять можна використовувати вихідні значення деякого полноперіодіческого генератора псевдовипадкових чисел.

Режим зворотного зв'язку по виходу DES

Режим зворотного зв'язку по виходу (OFB) алгоритму DES, представлений у вигляді схеми на рис. 3.14, може служити не тільки для потокового шифрування, але й для генерування ключів. Зауважимо, що вихідним значенням на кожній стадії є 64-бітове значення, j крайніх зліва розрядів якого знову подаються на вхід функції шифрування. Наступні 64-бітові вихідні значення утворюють послідовність псевдовипадкових чисел з хорошими статистичними властивостями. Як і у випадку підходу, запропонованого в попередньому розділі, захист сеансових ключів, які генеруються забезпечується застосуванням захищеного головного ключа.

Рис. 6.1 Генерація псевдовипадкових чисел з використанням лічильника

Генератор псевдовипадкових чисел ANSI X9.17

Один з кращих (з точки зору криптографії) генераторів псевдовипадкових чисел визначається стандартом ANSI X9.17. Запропонований алгоритм використовується цілим рядом додатків, серед яких програми, що забезпечують безпеку фінансових платежів, і PGP.

На рис. 6.2 показана схема алгоритму, в якому для шифрування використовується "потрійний" DES. Цей алгоритм має наступні складові:

• Введення. На вхід генератора подається два псевдовипадкових значення. Одне з них є 64-бітовим поданням поточних дати і часу і змінюється для кожного нового генерованого числа. Інша являє собою 64-бітове початкове значення, яке ініціалізується до деякого довільного значенням і оновлюється в процесі обчислень.

• Ключі. Генератор використовує три модулі шифрування "потрійного" DES. Кожен з цих трьох модулів використовує одну і ту ж пару 56-бітових ключів, які повинні зберігатися в секреті і використовуватися тільки для генерування псевдовипадкових чисел.

• Виведення. Виведеними значеннями є 64-бітове псевдовипадкове число і 64-бітове початкове значення.

Рис. 6.2 Генератор псевдовипадкових чисел ANSI X9.17

Визначимо натсупні величини

DT_i: значення дати/часу на початку кожної i-ї стадії генерування;

V_i: початкове значення для i-ї стадії генерування;

R_i: псевдовипадкове число, отримане в результаті i-ї стадії генерування;

K₁, К₂: ключі DES, які використовують на кожній стадії.

Тоді

де EDE означає послідовність шифрування-дешифрування-шифрування з використанням алгоритму "потрійного" DES із двома ключами.

Криптографічний надійність цього методу визначається декількома факторами. Тут використовуються 112-бітовий ключ і три блоки шифрування EDE, в сумі дають дев'ятикратному шифрування DES. Схема управляється двома псевдовипадковими значеннями, які вводяться: значенням дати та часу і початковим значенням, виробленим генератором, але відмінним від виробленого генератором псевдовипадкового значення. Таким чином, обсяг даних, які повинен аналізувати противник, виявляється величезним. Навіть якщо йому стане відомим псевдовипадкове значення Ri, з R, неможливо буде вивести V_i+1. оскільки для генерування V_i+1 використовується додаткова операція EDE.

Генератор BBS

Один з популярних підходів до генерування надійних послідовностей псевдовипадкових чисел полягає у використанні генератора Блюма-Блюма-Шуба (Blum, Blum, Shub - BBS), названий так на честь розробників [BLUM86]. Доказ його криптографічного надійності є, мабуть, найбільш суворим з опублікованих. Закладена в його алгоритмі процедура виглядає наступним чином. Спочатку вибирається два великих простих числа, що дають при діленні на 4 в залишку 3, тобто

р = q = 3 (mod 4).

Це означає, що (р mod 4) = (q mod 4) = 3 (детальніше використовувані тут позначення будуть пояснюватися в главі 7). Наприклад, для простих чисел 7 і 11 ми якраз маємо 7 = 11 = 3 (mod 4). Нехай тепер n = p*q. Виберемо випадкове число s, взаємно просте з 1 - в даному випадку це означає, що ні р, ні q не є дільниками s. Тоді генератор BBS породжує послідовність бітів В_i у відповідності з наступним алгоритмом.

X₀ = s² mod n

for i=1 to ∞

X_i = (X_i-1)² mod n

B_i = X_i mod 2

Таким; чином, на кожній ітерації вибирається молодший біт. У табл. 6.1, взятої з [STIN95], показаний приклад послідовності, отриманої в результаті використання алгоритму BBS. Тут, n = 192649 = 383 х 503 і початкове значення s = 101355.

Таблиця 6.1. Приклад виведення генератора BBS

S	Xi	Вi		S	Xi	Вi
0	20749			11	137922	0
1	143135	1		12	123175	1
2	177671	1		13	8630	0
3	97048	0		14	114386	0
4	89992	0		15	14863	1
5	174051	1		16	133015	1
6	80649	1		17	106065	1
7	45663	1		18	45870	0
8	69442	0		19	137171	1
9 10	186894 177046	0 0		20	48060	0
S

Генератор BBS зазвичай називають криптографічно захищеним генератором псевдовипадкових бітів. Цей генератор є одним з генераторів, що задовольняють так званому критерієм наступного біта (next-bit test), який визначається так [MENE97]:

■ Кажуть, що генератор псевдовипадкових бітів задовольняє критерію наступного біта, якщо не існує алгоритму з поліноміальною оцінкою часу його виконання, який за перші k біт вихідної послідовності може передбачити її (k + 1)-й біт з імовірністю, істотно більшою, ніж 1/2.

Іншими словами, не повинно існувати практично ефективного алгоритму, який дозволив би вам по перших k бітах послідовності з'ясувати з імовірністю більшої, ніж 1/2, що наступний біт буде дорівнює 1 (або 0). З точки зору будь-якого практичного підходу, послідовність буде непередбачуваною. Захищеність генератора BBS заснована на труднощі розкладання значення n на множники, тобто на труднощі задачі знаходження простих множників р і q по даному n. Докладніше обговорення даного питання ви знайдете в [STIN95].