3.5. Лабораторна робота №17. Аналіз шифрів гамування шляхом виділення тренду псевдовипадкової послідовності.
Тема роботи: Аналіз шифрів гамування шляхом виділення тренду псевдовипадкової послідовності.
Ціль роботи: На практиці відпрацювати вміння аналізу псевдовипадкових послідовностей. Провести апроксимацію псевдовипадкової послідовності до поліному третього порядку.
Загальні відомості
На сьогоднішній день відомо багато методів шифрування, в яких використовуються випадкові числа. В різних алгоритмах вони можуть мати різне призначення (на їх основі генеруються ключі, або на основі короткого ключа, що задає користувач, генерується інший “складний” ключ, потрібний для даного алгоритму), але в цілому, знаючи ці числа, можна повністю чи частково розкрити шифроване повідомлення, що не є добре. Тому в криптографії велику увагу приділяють якості використовуємого ГВЧ генератора випадкових чисел (ГВЧ) [1].
Теоретичні відомості
Під якістю будь-якого ГВЧ розуміють ступінь залежності генерованого випадкового числа від попереднього, виданого цим же ГВЧ. В ідеальному випадку числа, що видаються ГВЧ не повинні бути зв‘язані між собою. Якби так було, то злочинець, навіть знаючи частину випадкових чисел не зміг би далі дешифрувати жодного наступного випадкового числа, тобто шифрування було б абсолютно надійним [9]. Реально ж отримати ідеальний ГВЧ важко, хоча і можливо. Це можна зробити, наприклад, на основі приладу, що переводить у потрібну форму абсолютно випадкову швидкість вітру у даному місці, або, на основі переводу у числа інтервалів між натисками користувача на кнопки клавіатури ПК (теж абсолютно випадкові послідовності, якщо задати одиничний інтервал достатньо малим). Але основна проблема не в процесі отримання незалежних випадкових чисел. Багато шифровок просто не зможуть бути розшифровані законними користувачами, якщо зашифровані справжнім ГВЧ [9]. Пояснимо на прикладі шифру простого накладання (гамування) вихідного тексту на випадкову послідовність (гаму). Нехай текст вихідної послідовності після переводу в числа матиме вигляд: 3, 23, 10, 15, 3, 13. Користувач 1 генерує абсолютно випадкову гаму: 10, 15, 11, 8, 29, 11. Після переводу в бінарний вигляд і накладання за допомогою операції XOR, шифровка матиме вигляд: 9, 24, 1, 7, 30, 6. Користувач 2 отримує шифровку і розшифровує її тим же методом (адже операція XOR оборотна), тобто накладає шифровку на генеруєму ним абсолютно випадкову послідовність, але, оскільки використовуються справжні ГВЧ, то генерована послідовність зовсім інша ніж у користувача 1 (природно, що швидкість вітру не буде однаковою у різні моменти часу). Послідовність 2: 8, 18, 28, 13, 26, 12. Результат, звичайно, відрізняється від вихідного тексту: 8 XOR 9 = 1, 18 XOR 24 = 10, 28 XOR 1 = 29, 13 XOR 7 = 10, 26 XOR 30 = 4, 12 XOR 6 = 10. Отже, ніхто ніколи вже не дізнається, що ж було у тій шифровці (такі саме швидкості вітру відтворити не вдасться).
Саме тому у таких алгоритмах (в яких на основі випадкових чисел генеруються таємні ключі) використовуються псевдовипадкові генератори (ПВЧ). ГВЧ ж використовуються в тих алгоритмах, які потребують випадкових чисел для генерації відкритих ключів (в системах з відкритим ключем). Але залишимо ГВЧ і перейдемо до розгляду ПВЧ, як таких, що широко використовуються у алгоритмах класичної криптографії. ПВЧ являють собою генератори чисел, що залежать одне від одного. Спочатку користувач ініціалізує ПВЧ початковим значенням (що є справжнім ключем), а далі він (ПВЧ) починає самостійно виробляти числа, причому кожне наступне генерується на основі попередніх (або одного попереднього в найпростішому і найбільш розповсюдженому варіанті).
При використанні ПВЧ виникає багато проблем нового характеру, що пов‘язані саме з залежністю чисел одне від одного. Крім того, доводиться вводити таке поняття, як довжина ПВЧ – кількість псевдовипадкових чисел, що не є повторювані, адже починаючи з деякого номера генератор зациклюється і послідовність повторюється [6]. Наприклад, ПВЧ видає послідовність: 3, 15, 17, 2, 22, 3, 15, 17, 2, 22, 15, 3, 15, і т.д. Чим більша довжина (період) ПВЧ, тим він більше підходить для використання в криптографії.
Іншою і найбільш серйозною проблемою є можливість “злому” ПВЧ, тобто прогнозування зловмисником наступних чисел по вже отриманим. Це досягається завдяки різним математичним методам аналізу псевдовипадкових послідовностей: виділення тренду псевдовипадкової послідовності, фільтрація псевдовипадкових послідовностей методом зваженого ковзного середнього та ковзної медіани, спектральний аналіз за допомогою перетворення Фур‘є [4]. В даній роботі розглянемо виділення тренду псевдовипадкової послідовності, за допомогою метода найменших квадратів.
Розглянемо сутність задачі. Наш супротивник передає по доступній нам лінії зв‘язку зашифроване повідомлення, що містить секретний код доступу до його комп‘ютерної системи. По агентурним даним ми дізналися, що використовується шифр гамування вихідного тексту з псевдовипадковою послідовністю за допомогою операції побітового XOR. Нагадуємо, що принцип такого гамування полягає у наступному: представлення тексту у вигляді чисел, записаних в бінарному вигляді. Потім кожний біт вихідної послідовності додається до відповідного біту псевдовипадкової послідовності по модулю 2 (що і відповідає операції XOR). Наприклад, передаємо текст “АБ”. Як відомо всі символи зберігаються в ПК у вигляді кодів ASCII, отже всі літери українського (і російського) алфавіту будуть числами з вісьмома бінарними розрядами: “А” – 19210 – 110000002, “Б” – 19310 – 110000012. ПВЧ генерує числа в діапазоні 0..255 (тобто всі числа з вісьмома бінарними розрядами): 128, 63, і т.д. 12810 – 100000002, 6310 – 001111112. Накладання додаванням по модулю 2 (XOR):
|
10000000 00111111
01000000 11111110
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.