Методичні вказівки до практичних занять з дисципліни “Оcнови теорїї захисту інформації”, страница 10

В якості засобів формування випадкових та псевдовипадкових послідовностей використовують пристрої або алгоритми, які називають генераторами випадкових та псевдовипадкових послідовностей. Генератором випадкових послідовностей (ГВП) називають пристрій або алгоритм, який формує на своєму виході  послідовність статистично незалежних символів з основою алфавіту m.

Генератором псевдовипадкових послідовностей (ГПВП) називають детермінований алгоритм, сукупність алгоритмів чи сукупність алгоритмів та засобів, які для заданої послідовності довжиною k формують при своїй роботі  послідовність символів довжиноюl >> k, яка володіє більшістю властивостей випадкової послідовності. На рис. 1. наведено спрощену схему генератора псевдовипадкових послідовностей, де:

1 – генератор випадкової послідовності довжиною k;

2 – схема формування початкових значень k та П параметрів ГПС;

3 – генератор псевдовипадкових символів;

4 – логіка зворотного зв'язку.


Рис.1. Генератор псевдовипадкових послідовностей

В загальному вигляді ПВП Y можна задати як залежність:

                                                                                             (1)

від початкових значень ключа К та параметрів П, а також випадкових послідовностей . При цьому зворотній зв'язок Y призводить до впливу його на параметри, початкові значення та роботу генератора 3.

Основним призначенням ГПВП та ГВП в криптографії є формування ключів, початкових значень ключів та параметрів, параметрів та синхромаркерів.

Властивості ПВП оцінюють з використанням ряду кількісних показників. Основними показниками є:

-  період l (довжина) ПВП;

-  основа алфавіту m;

-  ймовірність перекриття в просторі або в часі двох сегментів  та , тобто в різних абонентів або в одного абонента з плином часу, так, що  = ;

-  структурна скритність (еквівалентна складність)  послідовності ;

-  кількість (ентропія) джерела ключів  для випадку, коли ГПВП використовується в якості джерела ключів;

-  відстань рівнозначності  конкретної послідовності ;

-  безпечний час ГПП ;

-  складність  формування послідовності ;

-  довжина параметрів зворотного зв'язку B2 та B3;

-  властивості випадковості, рівноймовірності, незалежності та однорідності.

За всіма названими показниками до генератора ПВП повинен бути пред'явлений ряд вимог. Так період повторення , тобто повинен бути не менше заданого, основа алфавіту m, ймовірність перекриття  менше допустимої, структурна скритність , ентропія джерела ключів , відстань рівнозначності , безпечний час , тобто не менш допустимих. Крім того, реалізації  повинні задовольняти вимогам випадковості, рівноймовірності, незалежності та однозначності.

4.2.2. Класифікація генераторів псевдовипадкових послідовностей

Основними генератора псевдовипадкових послідовностей є такі:

-  Лінійний регістр зсуву  (ЛРЗ);

-  Лінійний конгруентний генератор;

-  Комбіновані генератори;

-  Багатомодульне перетворення;

-  Несиметричний генератор

-  X9.17

-  Генератор на еліптичних кривих

-  Блокові симетричні криптоалгоритми

-  Потокові криптоалгоритми

4.2.3. Базові статистичні ймовірностні тести [4].

В якості базових рекомендується використовувати п'ять тестів:

-  частотний (монобітний) тест;

-  тест двох бітових серій;

-  тест Поккера;

-  тест серій (загальний);

-  автокореляційний тест;

Монобітний тест

Метою монобітного тесту є перевірка того, чи є число двійкових символів “0” та “1” в послідовності  приблизно таким, як у випадкової послідовності. Якщо  є число символів “0” в послідовності, а  - символів “1”, то параметр ПВП

підчиняється  розподілу з одним ступенем свободи (якщо ).

Тест двобітових серій

Метою тесту двобітових серій є перевірка того, чи є число з'явлень серій “00” - , “01” - , “10” - , “11” -  такою, як і у випадковій послідовності. Параметр ПВП

підчиняється  розподілу з двома ступенями свободи (якщо ).