Автокореляційний тест

Метою автокореляційного тесту є перевірка ступеню зв'язку між і її зсувами. Нехай d фіксоване ціле число, . Число бітів у Y послідовності дорівнює

.

Статистика параметра приблизно підпорядковується нормальному розподілу, якщо . Автокореляційний метод має бути двостороннім, щоб розглядати його як для малих значень , так і для великих.

1.10.2 Приклади розв'язку задач

Задача 1.

Розглянемо послідовність Y довжиною n =160, яку сформуємо із чотирьох 40 бітових послідовностей Y ₀.

Y ₀=11100 01100 01000 10100 11101 11100 10010 01001

1. Частотний (монобітний тест)

2. Двобітовий тест

3. Тест Поккера

Нехай m =3 і k =53. Блоки 000, 001, 010, 011, 100, 101, 110, 111 з'являються відповідно 5, 10, 6, 4, 12, 3 та 7 разів. Значення параметра

.

4. Тест серій

Є 25, 4 та 5 блоків довжиною 1, 2, 3 відповідно, 8, 20 та 12 інтервалів довжиною 1, 2 та 3 відповідно. Параметр приймає значення .

5. Автокореляційний тест.

Якщо d =8, то R (8)=100.

Значення статистичного параметра

.

Для рівня значущості порогові значення c1, c2, c3, c4 та c5 дорівнюють 3.8415, 5.9915, 14.0671, 9.4877, 1.96 відповідно.

Бачимо, що послідовність проходить частотний (монобітний) тест, двобітовий тест та тест Поккера, але не проходить тест серій та автокореляційний тест.

1.10.3 Задачі для самостійного розв'язання

1. Федеральним стандартом США FIPS – 140 – 1, 140 – 2 використовуються 4 статистичні тести на випадковість. Замість вибору користувачами потрібних рівнів значущості задаються реальні границі. Довжина бітової послідовності 20000 бітів. Проведіть аналіз цього стандарту.

Монобітний тест. Кількість n ₀ та n ₁, .

Тест Поккера. Статистичний параметр обчислюється для m =4; тест виконується, якщо .

Тест серій. Тести проходять, якщо кожний із 12 номерів та , , знаходиться в інтервалі згідно з табл. 1.7.

Таблиця 1.7 – Значення інтервалів

Довжина серії	Відповідний інтервал
	2267 – 2733
	1079 – 1421
	502 – 748
	223 – 402
	90 – 223
	90 – 223

Тест довжин серій. Цей тест проходить, якщо не існує ніяких серій довжиною 34 або більше. Для високозахищених застосувань FIPS – 140 – 1 зобов'язує, щоб 4 тести виконувалися при кожній ініціалізації генератора випадкових бітів. В FIPS-140-2 максимальна довжина серії збільшена до 36 бітів.

2. Необхідно розробити такі процедури на мові С++ або іншій мові:

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

Таблиця 1.8 – Примітивні поліноми

№ п/п
№ п/п

б) реалізація монобітного тесту згідно з вищесказаною теорією для довільної довжини послідовності;

в) реалізація тесту Покера згідно з вищесказаною теорією для довільної довжини послідовності;

г) реалізація тесту серій згідно з вищесказаною теорією для довільної довжини послідовності;

д) реалізація тесту довгих серій згідно з вищесказаною теорією для довільної довжини послідовності.

3. Розв'язати задачі 2 (а-д) з використанням ЕОМ при довжині послідовності бітів.

4. Розв'яжіть задачу 1 пункту 1.10.2, якщо псевдовипадкова послідовність довжиною n =128 бітів побудована шляхом чотириразового повторення такої 32-х бітової послідовності:

S ={0110 0100 0111 1010 1100 1000 1111 0101}.

Відповідь: (c₁=0,5; c₂=2,295; c₃=1,048; c₄=5,99; c₅=0,18).

1.10.4 Контрольні запитання та завдання

1. Поясніть алгоритм функціонування генератора псевдовипадкових послідовностей (рис.1.10.1).

2. Назвіть основні показники оцінки властивостей генератора псевдовипадкових послідовностей.

3. Визначте період повторення лінійної рекурентної послідовності, якщо m ={7, 10, 12, 19, 31, 63, 89, 127, 257, 52}.

4. Визначте структурну скритність лінійної рекурентної послідовності періоду .

5. Визначте значення безпечного часу, якщо в генератор псевдовипадкової послідовності може бути введено N_k (10²⁰, 10²⁵, 10³⁰, 10³⁵, 10⁴⁰, 10⁵⁰, 10⁷⁰, 10⁸⁰, 10⁹⁰, 10¹⁰⁰, 10¹²⁷) ключів.

6. Визначте структурну скритність лінійної рекурентної послідовності періоду , m =20, 25, 30, 35, 40, 61, 63, 85, 89, 127, 257, 507.

7. Поясніть сутність:

- монобітного тесту;

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

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

- тесту серій;

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

8. Поясніть вихідний код процедури реалізації:

- монобітного тесту;

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

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

- тесту серій;

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

9. Дайте визначення лінійного конгруентного генератора.

10. Які вимоги висуваються до коефіцієнтів а та b рекурентного співвідношення, що визначає алгоритм функціонування лінійного конгруентного генератора.

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

12. Зробіть пропозиції щодо реалізації та виберіть параметри конгруентного генератора, що забезпечує максимальний період послідовності.