або не використовуватися взагалі.
1.2 Методи та алгоритми формування робочих ключів
Генератор псевдовипадкових чисел (ГПСЧ, Pseudorandom number generator, PRNG) - алгоритм, що генерує послідовність чисел, елементи якої майже незалежні один від одного і підкоряються заданому розподілу (зазвичай рівномірному).
І часто використовуються в криптографії. При цьому від якості використовуваних ГПСЧ безпосередньо залежить якість одержуваних результатів. Ця обставина підкреслює відомий афоризм Роберта Р. Кавью: В«генерація випадкових чисел занадто важлива, щоб залишати її на волю випадкуВ». p align="justify"> Зазвичай використовується створення деякого набору з великої кількості випадкових чисел і опублікування його в деякому В«словникуВ». Тим не менше, і такі набори забезпечують дуже обмежений джерело чисел в порівнянні з тією кількістю, яка вимагається додаткам мережевої безпеки. Хоча дані набори дійсно забезпечують статистичну випадковість, вони не досить випадкові, так як противник може отримати копію словника. p align="justify"> Генератор псевдовипадкових чисел включений до складу багатьох сучасних процесорів (напр., сімейства х86)
Криптографічні додатки використовують для генерації випадкових чисел особливі алгоритми. Ці алгоритми заздалегідь визначені і, отже, генерують послідовність чисел, яка теоретично не може бути статистично випадковою. У той же час, якщо вибрати хороший алгоритм, отримана чисельна послідовність проходитиме більшість тестів на випадковість. Такі числа називають псевдовипадковими числами. p align="justify"> Піднесення до степеня за модулем
зведення в ступінь по модулю цілого числа, тобто
М = C d (mod N).
Насамперед відзначимо, що не має сенсу спочатку знаходити R =, а потім визначати його залишок від ділення на N. Дійсно, роблячи таким чином при обчисленні
5 (mod 511) = 28153056843 (mod 511) = 359,
ми отримуємо великий проміжний результат - 28153056843. У реальній ситуації, коли зводяться до степеня числа з 1024 двійковими знаками, проміжний результат буде мати 21024 1024 знаків. Тільки для запису таких чисел буде потрібно близько 1031 гігабайт на вінчестері. p> Щоб проміжні результати не були настільки величезні, необхідно згадати, що ми працюємо за модулем N. Але навіть при цьому варто бути уважним. Наївний підхід до вирішення нашої задачі привів би до наступних обчислень:
х = 123,2 = х В· х (mod 511) = 310,3 = х В· x2 (mod 511) = 316,4 = х В· x3 (mod 511) = 32,5 = х В· x4 (mod 511) = 359.
На це йде 4 множення в кільці вирахувань, що здається прийнятним для нашого іграшкового прикладу. Але в загальному випадку, при зведенні в 1024-розрядну ступінь потрібно близько 21024 таких множень. Якщо кожен твір при цьому здійснюється за 1...
