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

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

2 Вступ Інформатизація Захист інформації, моделювання Послідовності Вимоги до послідовностей (закон розподілу) Якісні послідовності Генератори якісних послідовностей Дослідження та розробка генераторів Експериментальне підтвердження якості вихідної послідовності

3 Випадкове число Алфавіт – множина допустимих значень Неможливо спрогнозувати, яке саме значення із допустимих прийме число (змінна)

4 Випадкова послідовність Вектор (масив) випадкових чисел Елементи послідовності не залежать один від одного Непередбачуваність

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

6 Генератор псевдовипадкових чисел Математичний алгоритм Якісна послідовність (задовольняє вимоги до її характеристик) Рівномірний розподіл: складна передбачуваність досягається за мінімальної імовірності появи певного символу алфавіту послідовності в якості її наступного члена, що, в свою чергу, забезпечується рівномірним законом розподілу

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

8 Комбінаційний генератор Первинний генератор 1 Первинний генератор 2 Первинний генератор N... Комбінаційна функція Вихідна послідовність

9 Комбінаційний генератор T = НСК( T 1, T 2, …, T N ) T = T i – якщо T i – взаємно прості Регістр зсуву розміром T 1 Регістр зсуву розміром T 2 Регістр зсуву розміром T N... Сума по модулю M Вихідна послідовність

10 Методи аналізу генераторів псевдовипадкових послідовностей Тести Д. Кнута невелика кількість тестів швидкі алгоритми неоднозначна інтерпретація результатів Пакети статистичних тестів (diehard, NIST тощо) готове програмне забезпечення для аналізу послідовностей

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

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

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

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

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

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

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

18 Аналіз k-грам - розпаралелювання Одночасно можна аналізувати k-грами різних розмірностей навіть на одному й тому ж вузлі, це може відслідковувати координуючий вузол або дочірній вузол може вказувати розміри обрахованих k- грам разом із обрахованим значенням Видача навантаження може виконуватися і по запиту дочірнього вузла (із передачею зміщення відносно початку послідовності і розмір бажаного навантаження) Коорд. вузол Дочірній вузол 2 Дочірній вузол N Дочірній вузол 1 Обраховані значення χ² Частина послідовності Координуючий вузол: - видає навантаження (частини послідовності) - складає обраховані дочірніми вузлами значення χ² За нестачі дочірніх вузлів, координуючий вузол може виконувати декілька проходів послідовністю для аналізу усіх груп k-грам

19 Результати аналізу 4 первинних генератори із періодами T 1 =256, T 2 =251, T 3 =241, T 4 =239; перші 5 частин послідовності розміром 32 МБ кожна; розмір грам k від 1 до 25

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

21 Ергономіка робочого місця наукового співробітника BodyBilt K3507 Samsung B2430L Adesso Intellimedia Pro Ergo Keyboard Logitech Performance Mouse MX

22 Поведінка при бомбардуванні або артилерійському обстрілі Укриття: спеціалізовані сховища метро заглиблення (ями, канави) підвищення (фундамент забору, тротуар, лежачий бетонний блок, насип піску) відкриті смотрові ями каналізаційні люки Необхідно уникати: будівлі підвали житлових будинків техніка (в т.ч. автомобілі) будматеріали (щебінка тощо) водойми

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