Розробка та аналіз властивостей алгоритмів формування псевдовипадкових та випадкових послідовностей. Приклади розв’язку задач та задачі для самостійного розв’язання

1.10.1 Основні теоретичні відомості

1.10.1.1 Основні вимоги до засобів формування випадкових та
псевдовипадкових послідовностей.

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

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

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

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

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

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

Рисунок 1.8 – Генератор псевдовипадкових послідовностей

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

(1.172)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- асиметричні генератори, що реалізуються в кільці, полі або групі точок еліптичної кривої;

- генератор ПВП відповідно до стандарту ANSI X9.17;

- блокові симетричні криптоалгоритми, що функціонують в режимі генератора ПВП;

- потокові криптоалгоритми в режимі виробки гами.

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

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

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

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

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

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

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