1.2 Методи отримання псевдовипадкових послідовностей
1.2.1 Метод Фібоначчі
Клас генераторів псевдовипадкових послідовностей заснований на використанні послідовностей Фібоначчі[7]. Приклад такої послідовності - {1, 1, 2, 3, 5, 8, 13, 21, 34, 55б 89, ...}. Перші два члени дорівнюють 0 та 1 чи 1 та 1 відповідно. Кожен з наступних членів дорівнює сумі двох попередніх значень послідовності.
Широке застосування генератори послідовностей на основі чисел Фібоначчі отримали в зв'язку з високою швидкодією виконання арифметичних операцій з числами, що беруть участь для формування послідовності. Значення цього параметру порівняне з швидкістю цілочисельної арифметики, а генератори Фібоначчі природно реалізуються в речовій арифметиці.
1.2.2 Вихор Мерсенна
Вихор Мерсенна є витковим регістром зсуву з узагальненою віддачею
"Вихор" - це перетворення, яке забезпечує рівномірний розподіл генеруються псевдовипадкових чисел в 623 вимірах. Тому кореляція між послідовними значеннями у вихідний послідовності Вихора Мерсенна пренебрежимо мала.
Вихор Мерсенна має величезний період, що дорівнює числу Мерсенна 2 19937 - 1, що більш ніж достатньо для багатьох практичних застосувань.
Регістр зсуву складається з 624 елементів, і в загальній складності 19937 клітин. Кожен елемент має довжину 32 біта за винятком першого елемента, який має тільки 1 біт за рахунок відкидання біта. Процес генерації починається з застосування бітової маски, що відкидає 31 біта (крім найбільш значущих). З ледующім кроком буде ініціалізація (x0,x1,..., x623) будь-якими беззнаковими 32-розрядними цілими числами. Наступні кроки включають в себе об'єднання і перехідні стани.
1.2.3 Лінайний регістр зсуву зі зворотнім звязком
Переваги генератора ПСП, заснованого на зсувному регістрі:
– ефективна апаратна реалізація;
– швидкодія.
Недоліком генераторів на основі регістрів утворюють тільки циклічні послідовності чисел. Для отримання нециклічних послідовностей необхідно під’єднати на виході генератора комбінаційний перетворювач кодів. Але при цьому погіршуються основні параметри генератора:
– швидкодія;
– потужність;
– розмір площі кристалу.
1.3 Вимоги до ПВП
Для застосування в криптографічних системах ГПВЧ повинні відповідати наступним вимогам:
послідовність, що генерується повинна мати максимально великий період;
послідовність, що генерується не повинна мати схованих періодичностей;
послідовність, що генерується повинна мати рівномірний спектр.
Найважливішою характеристикою ГПВЧ є довжина періоду повторення, після якого випадкові числа, на виході ГПВЧ почнуть повторюватися.
Другою за важливістю характеристикою ГПВЧ є його продуктивність, тобто кількість чисел, які генеруються за одиницю часу.
Для окремих прикладних програм (статистичне зондування, моделювання в реальному часі і т.д.) може бути потрібною продуктивністю порядку 1010 – 1012 випадкових чисел за секунду. Швидкий і надійний ГПВЧ може легко слугувати поточним шифром.
Оскільки для шифрування інформації достатньо її побітово скласти по модулю два з випадковою послідовністю бітів. Питанню проектування надійних і якісних ГПВЧ часто не надають належної уваги.
Сама система шифрування може бути виконана на дуже високому рівні, але якщо криптографічний ГПВЧ видає ключі, які легко вгадати, то всі інші бар'єри захисту долаються без особливих зусиль.
В ряді продуктів використовуються ГПВЧ, що продукують ключі, в яких відслідковується певна закономірність. В таких випадках про безпеку говорити не варто. Цікавим є те, що використання одного і того ж генератора в деяких областях забезпечує необхідну степінь захисту, а в інших - ні.
Таким чином, необхідно підкреслити важливість криптографічного ГПВЧ – якщо він розроблений погано, то він легко може стати самим вразливим елементом системи.
Існують різні методи для створення послідовностей випадкових чисел: апаратні, табличні та програмні методи генерування послідовностей.
Найбільш використовуваними є програмні генератори, які реалізовують можливість отримувати послідовності випадкових чисел за рекурентними формулами. Але варто звернути увагу, що числа, генеровані даним методом, насправді є псевдовипадковими, тобто, при належній підготовці є вірогідність «зламати» послідовність.
Також їх називають псевдовипадковими через те, що алгоритми отримання даних послідовностей завжди є детермінованими.
До програмних генераторів необхідно висувати такі вимоги :
генерування статистично незалежних випадкових чисел, рівномірно розподілених в інтервалі [0, 1];
можливість відтворювати задані послідовності випадкових чисел;
ресурси процесора, що витрачені на роботу програмного генератора, повинні бути мінімальними;
створення незалежних послідовностей випадкових чисел (потоків).
Слід звернути увагу на те, що більшість програмних генераторів продукують випадкові числа, рівномірно розподілені в інтервалі [0, 1].
Необхідність одержання таких чисел обумовлена тим, що на їх основі можна отримати випадкові числа практично будь-яких розподілів.
Якість роботи генераторів визначається статистичними властивостями послідовностей випадкових чисел, які він генерує, – незалежністю і випадковістю.
Властивості послідовностей перевіряються за статистичними критеріями. При відтворюванні послідовностей випадкових чисел за однакових початкових умов та параметрів програмний генератор має відтворювати ідентичні послідовності псевдовипадкових чисел.
Одні й ті ж послідовності чисел застосовуються в тому випадку, коли необхідно порівняти декілька варіантів систем, які моделюються, і налагодити програми.
Класичним представником ГВП є фізичний генератор випадкових послідовностей. Ентропія випадкової послідовності, що видається джерелом шуму, підвищується з генерацією кожного символу випадкової послідовності. В цьому випадку ГВП представляється ідеальним ГВП .
Детермінований генератор випадкових послідовностей є одним з базових примітивів для більшості криптографічних додатків, він забезпечує генерацію послідовностей, які називають псевдовипадковими. Однією з основних властивостей та переваг ДГВП є забезпечення відновлюваності послідовності в просторі і часі. В той же час ПВП повинні мати гарантовані властивості відносно періоду повторення, відновлення відрізків ПВП в просторі та часі, можливість проведення попереднього дослідження їх властивостей тощо Складність реалізації безумовно стійкої системи пов’язана з тим, що ключ повинен мати довжину, не меншу довжини повідомлення, що зашифровується. При використанні для зашифрування ПВП, довжина ключа суттєво зменшується, по суті на нинішній час її довжина не більше 512 бітів, а властивості ПВП близькі до фізично випадкової послідовності, тобто ПВП є практично нерозрізнюваною від випадкової послідовності. В той же час ПВП породжується деяким ДГВП на основі використання короткого ключа .
В висунуті вимоги до ДГВП та послідовностей, що ними генеруються, сутність яких зводиться до захищенності від таких основних атак, як:
криптоаналітичні атаки знаходження початкового чи розгорнутих ключів;
атаки, що зводяться до вирішення математичних задач, складність яких менше або суттєво менше атаки груба сила;
атак, що засновані на вхідних даних генератора, які здійснюються засобом визначення або маніпулювання вхідними даними ГВП з метою впливу на вихідні дані (ключі, параметри тощо для інших криптографічних додатків);
атаки, що зводяться до розповсюдження компрометованого стану генератора на інші стани
попередні чи майбутні;
атаки, що засновуються на недопустимо обмеженому періоді повторення .
В той же час відомо, що будь-який ДГВП з обмеженими ресурсами може генерувати ПВП з наперед відомим періодом, можливо недопустимо коротким. Довжина циклів ДГВП залежить від самого генератора і в середньому складає приблизно 2n/2, де n – розмір внутрішнього стану в бітах, хоча лінійні конгруентні і LFSR-генератори забезпечують максимальні періоди порядку 2n. Якщо ДГВП може сходитися до дуже коротких циклів, навіть з деякою ймовірністю, то такий ДГВП стає передбаченим і є непридатним.
1 2 3 4 5 6