Лекція 22 тестування випадкових і псевдовипадкових послідовностей

22.1 Визначення та властивості випадкових і псевдовипадкових послідовностей

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

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

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

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

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

Визначення. Послідовність є РРВП, якщо виконуються наступні умови.

1. Кожний елемент випадкової послідовностіє дискретною випадковою величиною, що приймає значення з множини (алфавиту) потужності:.

2. Для довільного номера величинарозподілена рівноймовірно, тобто

3. Для довільної скінченної підсистеми індексів ,, випадкові величининезалежні у сукупності.

Нагадаємо, що випадкові величини незалежні у сукупності, якщо

, ,

,

.

У криптографії рівномірно розподілені випадкові послідовності часто називають «чисто випадковими» послідовностями. Ці послідовності мають важливі властивості, що є інтуїтивно очикуваними, наприклад:

а) для довільного (але постійного до кінця експерименту) набору індексів -мірний розподіл векторівє рівномірним, тобто,

б) кожна підпослідовність виду є чисто випадковою,

в) якщо послідовність - чисто випадкова, а,, довільна послідовність, що не залежить від, то послідовністьє чисто випадковою,

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

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

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

Дійсно, чисто випадкові послідовності є нескінченними і апериодичними.

Вони можуть, у принципі, містити скінченні відрізки з довільними властивостями: з довгими серіями нулів, періодичними підпослідовностями, тощо.

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

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

Принципова різниця між в РРВП і ПВП полягає в тому, що при повторенні експерименту повторення РРВП практично неможливо, а для генератора ПВП параметри, що призводять до генерації конкретної послідовності можна задавати у довільній кількості сеансів.

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

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