Оцінка закону розподілу випадкових чисел комбінаційного генератора у k-вимірному просторі презентация

Максим
МКМ-1305

розробка генераторів
Експериментальне підтвердження якості вихідної послідовності

допустимих прийме число (змінна)

майже незалежні один від одного
Складна передбачуваність
Елементи відповідають заданому закону розподілу (зазвичай – рівномірному)

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

поточні значення кожного первинного генератора в єдине число із алфавіту комбінаційного генератора

Ti – якщо Ti – взаємно прості

Регістр зсуву
розміром T1

Регістр зсуву
розміром T2

Регістр зсуву
розміром TN

...

Сума
по модулю M

Вихідна послідовність

результатів
Пакети статистичних тестів (diehard, NIST тощо)
готове програмне забезпечення для аналізу послідовностей

тестів
Полягає в аналізі k-грам
Послідовності, рівномірно розподілені при максимальному k, будуть рівномірно розподілені і при менших k

кожного варіанту k-грам у послідовність
Для рівномірного розподілу – просте порівняння кількостей входжень

(time-memory tradeoff) – підвищити швидкодію програми можна за рахунок збільшення використання пам'яті і навпаки – зменшити використання пам'яті можна за рахунок сповільнення роботи програми (алгоритму)

момент часу в пам'яті можна тримати всього лише один лічильник
Повільна робота – для підрахунку кількості входжень кожного варіанту k-грами у послідовність виконується повний прохід послідовністю (добуток кількості варіантів k-грам на кількість k-грам у послідовності)
Переваги – можливість анализу k-грам великої розмірності
Недоліки – на практиці даний алгоритм потребує занадто багато часу на виконання, особливо для великих послідовностей

лічильники для усіх можливих варіантів k-грам
Швидкий аналіз – прохід послідовністю для усіх варіантів k-грам виконується лише один раз
Переваги – швидкий аналіз
Недоліки – обмеження максимального розміру k-грам (в залежності від об'єму пам'яті)

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

із видачею дочірнім вузлам однієї і більше k-грами послідовності (map)
Кожен дочірній вузол відповідає за підрахунок певної групи комбінацій k-грам (map)
Після проходу усієї послідовності (або бажаної для аналізу її частини) із кожного вузла збирається проміжне значення лічильників (або значення χ²) і складається на координуючому вузлі (reduce)
Координуючий вузол також може виступати в якості дочірнього (але в усій мережі для аналізу може бути лише 1 координуючий вузол – не p2p мережа)

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

Коорд.
вузол

Дочірній
вузол 2

Дочірній
вузол N

Дочірній
вузол 1

Обраховані значення χ²

Обраховані значення χ²

Обраховані значення χ²

Частина послідовності

Частина послідовності

Частина послідовності

Координуючий вузол:
- видає навантаження (частини послідовності)
- складає обраховані дочірніми вузлами значення χ²

За нестачі дочірніх вузлів, координуючий вузол може виконувати декілька проходів послідовністю для аналізу усіх груп k-грам

5 частин послідовності розміром 32 МБ кожна; розмір грам k від 1 до 25

наукового співробітника – оператора персонального комп'ютера
Безпека у надзвичайних ситуаціях – бомбардування / артилерійський обстріл житлових масивів

Performance Mouse MX

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

Необхідно уникати:
будівлі
підвали житлових будинків
техніка (в т.ч. автомобілі)
будматеріали (щебінка тощо)
водойми

значення χ² менші за χ²кр.)
Рівномірний розподіл:
→ мінімальна імовірність того, що певний символ алфавіту виявиться наступним членом послідовності
→ максимально складна передбачуваність
→ задоволена основна вимога до псевдовипадкових чисел
→ теоретично (при більшій кількості експериментів із різними початковими станами або іншими типами початкових генераторів) може бути застосований у криптографічних цілях