Криптографія і випадковість мають тісний зв'язок. В "F. Теорія інформації". Теорія інформації. ми згадували, що досконала таємність може бути досягнута, якщо ключ алгоритму шифрування - дійсно випадкове число. Є два підходи до отримання довгого потоку випадкових бітів.
- Використання природного випадкового процесу, такого як багаторазове кидання монети і інтерпретація результату "орел" чи "решка", як значення бітів 0 або 1.
- Використання детермінованого процесу з інформацією зворотного зв'язку.
Перший підхід названий справжнім генератором випадкових чисел (TRNG - True Random Number Generator).
Другий названий псевдовипадковим генератором числа (PRNG - Pseudorandom Number Generator). Малюнок K.1 показує ці два підходи.
збільшити зображення
Мал. K.1. Істинний генератор випадкових чисел і псевдовипадковий генератор чисел
K.1. Істинний генератор випадкових чисел (TRNG)
При киданні правильної монети безперервно виникає досконалий випадковий потік бітів, але це не застосовується на практиці. Є багато природних джерел, які можуть призвести справжні випадкові числа, такі як тепловий шум в електричному резистори або час відповіді механічного або електричного процесу після передачі команди. Ці природні ресурси використовувалися в минулому, і деякі з них були впроваджені в комерційну діяльність. Однак є кілька недоліків такого підходу. Процес зазвичай повільний, і якщо необхідно, один і той же випадковий потік не може бути повторений.
K.2. Генератор псевдовипадкових чисел (PRNG)
конгруентні генератори
Кілька методів використовують деякі неконгруентні відносини.
Лінійний конгруентний генератор
В інформатиці сама загальна методика для того, щоб виробляти псевдовипадкові числа, - лінійний конгруентний метод, введений Лемера (Lehmer). Малюнок K.2 показує цей метод, який рекурсивно створює послідовність псевдовипадкових чисел, використовуючи лінійне конгруентне рівняння xi + 1 = (axi + b) mod n. де x0 називається початковим числом (seed) - це число між 0 і n - 1.
Мал. K.2. Лінійний конгруентний генератор псевдовипадкових чисел
Послідовність є періодичною, де період залежить від того, як ретельно обрані коефіцієнти a і b. Ідеально період повинен бути такого розміру, як модуль n.
Припустимо a = 4. b = 5. n = 17 і xi0 = 7. Послідовність - 16, 1, 9, 7, 16, 1, 9, 7. яка є явно незадовільна псевдослучайная послідовність; її період - тільки 4.
Критерії. Для прийнятного генератора псевдовипадкових чисел (PRNG) протягом минулих кількох десятиліть були розроблені кілька критеріїв.
- Період має дорівнювати n (модулю). Це означає, що перш ніж цілі числа в послідовності починають повторюватися, повинні бути згенеровані всі цілі числа між 0 і n - 1.
- Послідовність в кожен період повинна бути випадкова.
- Процес генерації повинен бути зручний для реалізації на комп'ютері. Більшість комп'ютерів сьогодні ефективно, коли застосовується арифметика, яка використовує слова по 32 біта.
Рекомендації. засновані на попередніх умовах: рекомендується вибрати коефіцієнти конгруентного рівняння і значення модуля виходячи з таких міркувань.
- Оптимальний вибір модуля, n. - це найбільше просте число, близьке до розміру слова, використовуваного в комп'ютері. Рекомендується використовувати тридцять перше просте число Мерсенна як модуль: n = M 31 = 2 31 - 1.
- Щоб створювати період, що дорівнює значенню модуля, значення першого коефіцієнта, a. має бути первісним коренем головного модуля. Хоча ціле число 7 - первісний корінь M31. рекомендують використовувати 7 k. де k - ціле число, взаємно-просте с (M31 - 1). Деякі рекомендовані значення для k - це 5 і 13. Це означає, що (a = 7 5) або (a = 7 13).
- Друга рекомендація: для ефективного використання комп'ютера значення другого коефіцієнта b має бути нульовим.
Лінійний конгруентний генератор:
xi + 1 = axi mod n. де n = 2 31 - 1 і a = 7 5 або a = 7 13
Безпека. Послідовність, згенерувала лінійним конгруентним рівнянням, показує прийнятну випадковість (якщо слідувати попереднім рекомендаціям). Послідовність корисна в деяких додатках, де потрібно тільки випадковість (таких як моделювання); вона марна в криптографії, де бажані і випадковість, і безпеку. Оскільки число n загальнодоступним, послідовність може бути атакована Євою з використанням однієї з двох стратегій:
- Якщо Єва знає значення початкового числа (x 0) і коефіцієнт a. вона може легко відновити цілу послідовність;
- Якщо Єва не знає значення x 0 і a. вона може перехопити перші два цілих числа і використовувати такі два рівняння, щоб знайти x0 і a:
Генератор квадратичних лишків
Щоб отримати менш передбачувану псевдослучайную послідовність, був введений генератор квадратичних відрахувань (див. "A. ASCII"), xi + 1 = xi 2 mod n. де x0 називають початковим числом, - число між 0 і n -1.
Генератор Blum Blum Shub
Простий, але ефективний метод створення генератора псевдовипадкових чисел названий Blum Blum Shub (BBS) на ім'я його трьох винахідників.
BBS використовує рівняння квадратичного вирахування, але це - псевдовипадковий генератор біт замість генератора псевдовипадкових чисел; він генерує послідовність бітів (0 або 1).
Малюнок K.3 показує ідею цього генератора.
Нижче наведені кроки створення:
- Знайдіть два великих простих числа p і q в формі 4k + 3. де k - ціле число (p і q є конгруентними 3 mod 4).
- Виберіть модуль n = p x q.
- Виберіть випадкове ціле число r. яке є взаємно-простим з n.
- Обчисліть початкове число як x0 = r 2 mod n.
- Генерувати послідовність xi + 1 = xi 2 mod n.
- Взяти наймолодший біт згенерованого випадкового цілого числа (LSB - Least Significant Bit) як випадковий біт.
збільшити зображення
Мал. K.3. Blum Blum Shub (BBS) генератор псевдовипадкових чисел
Безпека. Може бути доведено, що якщо p і q відомі, i-тий біт в послідовності може бути знайдений як наймолодший біт:
Це означає, що якщо Єва знає значення p і q. вона може знайти значення i-того біта, пробуючи всі можливі значення n (значення n зазвичай загальнодоступним). Тим самим складність у цього генератора - та ж сама, як у розкладання на множники n. Якщо n є досить великим, послідовність безпечна (непередбачувана). Було доведено, що при дуже великому n Єва не може передбачити значення наступного біта в послідовності, навіть якщо вона знає значення всіх попередніх бітів. Імовірність кожного прийняття значень для кожного біта, 0 або 1, - дуже близька до 50 відсотків.
Безпека BBS залежить від складності розкладання на множники n
Генератори на основі криптографічного системи
Криптографічні системи, такі як шифр для процесу шифрування або хеш-функція, можуть також бути використані для генерації випадкового потоку бітів. Ми коротко покажемо дві системи, які застосовують алгоритми шифрування.
ANSI X9.17 генератор псевдовипадкових чисел (PRNG)
ANSI X9.17 визначає криптографически сильний генератор псевдовипадкових чисел. використовує потрійний 3DES з двома ключами (шифрация - дешифрування - шифрация), малюнок рис. K.4 ілюструє цей проект. Зверніть увагу, що перше псевдовипадкове число це 64-бітове початкове число, яке використовується як ініціює вектор (IV); інша частина псевдовипадкових чисел використовує початкове число, показане як такі IV. Той же самий ключ засекречування на 112 бітів (K1 і K2 в 3DES) застосовується для всіх трьох 3DES-шифрів.
На рис. K.4 конфігурація - режим зчеплення блоків шифрованого тексту (CBC), який ми описали згідно рис. 8.3 в "Безпека на мережевому рівні: IP SEC". Режим X9.17 застосовує два каскади формування ланцюжка блоку. Оригінальний текст для кожного каскаду надходить від виходу першого 3DES, який використовує дату і час як вихідний текст на 64 біта. Зашифрований текст, створений другим 3DES, - випадкове число; зашифрований текст, створений третім 3DES, - наступний ініціює вектор IV для наступного випадкового числа.
Строгість X9.17 визначається наступними фактами.
- Ключ - 112 (2 56) біт.
- Введення дати і часу на 64 біта забезпечує хорошу мітку часу, що запобігає атаку відтворення.
- Система забезпечує чудовий ефект розсіювання і перемішування за допомогою шести шифрування і трьох дешифрування.
PGP генератор псевдовипадкових чисел (PRNG)
PGP (дуже хороша конфіденційність) бере ту ж саму ідею, що і X9.17 з декількома змінами. Спочатку PGP PRNG використовує сім каскадів замість двох. Друге: шифр є або IDEA, або CAST 128 (не розглянуті в цій книзі). Третє: ключ - зазвичай 128 бітів. PGP PRNG створює три випадкових числа на 4 біта: перше використовується як ініціює вектор IV секретності (для зв'язку, що працює з PGP, але не для PRNG), другий і третій конкатенуються, щоб створити секретний ключ 128 бітів (для зв'язку, що працює PGP). Малюнок K.5 показує ескіз PGP PRNG. Строгість PGP PRNG задана в розмірі його ключа і в тому, що оригінал IV (початкова число) і ключ засекречування на 128 бітів можуть бути згенеровані від 24-байтовой істинно випадкової змінної.
Вітаю! Хотілося б прояснити наступне питання: у МТІ припинена державна акредитація та коли буде восстановлена- невідомо, а в диплом про профперепідготовка видається на базі МТІ (як я зрозумів). Як закінчиться справа з отриманням диплома?
Питання важливе й актуальне, тому що необхідно терміново пройти навчання і отримати диплом і не хотілося б витрачати час і платити гроші даремно (якщо диплом виявиться недійсним і т.п.). Роз'ясніть, будь ласка, докладніше ситуацію.
Добрий день, Хотілося б прояснити ви в майбутньому плануєте узгоджувати цю програму, з регуляторами і чи пройде сам диплом зараз, коли вводяться проф стандарти?