Алгоритм формування ключових пар

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

Система RSA відноситься до криптосистем з відкритими ключами. У цій системі ключі Е_k ¹ D_k, причому один із них повинний бути особистим, а другий відкритим. Наприклад, Е_k – особистий, а D_k – відкритий, якщо вони використовуються для ЦП і навпаки, якщо використовуються для направленого шифрування.

Усі параметри (N, P, Q) також поділяються на 2 класи: N – відкритий, P, Q - конфіденційний (секретний).

Сутність забезпечення моделі взаємної недовіри – кожен користувач генерує ключі сам собі. Особистий ключ залишає в себе і забезпечує його строгу конфіденційність. Відкритий ключ розсилає всім користувачам, з якими він зв'язаний. Користувач також забезпечує цілісність і дійсність відкритих ключів.

Е_k, D_k - повинні вибиратися з повної множини випадково, порівняно ймовірно і незалежно, повинні забезпечувати однозначну оборотність прямого та зворотного перетворення.

Значення Е_k, D_k для практичних використань повинні задовольняти умові

,

де

Порівняння (1.3.7) можна звести до Діфантового рівняння:

ax+by=1 (1)

Діафантове рівняння – нормоване, тому що праворуч коефіцієнт = 1, a, b – цілочисельні коефіцієнти, х, у – невідомі. Порівняння (1) можна представити у виді:

(2)

k – деяке невідоме число

Діафант рівняння (1.3.10) має цілочисельне рішення, якщо a і b цілочисленні, і a ≥ b, a і b взаємно прості. Представивши (2) у виді

, (3.)

одержимо а = j (N), x =(- k), b = E_k, y = D_k.

Якщо E_k сформувати випадково, а та b – відомі числа, а х та y – невідомі, що підлягають визначенню.

Одним із найбільш швидких рішень (3.) є ланцюгові дроби.

,

де m – порядок ланцюгового дробу, a і b – параметри ланцюгового дробу.

Знаходимо параметри:

a / b подається у виді ланцюгового дробу.

,

μ - порядок ланцюгового дробу, перший коефіцієнт, у якого залишок дорівнює 0.

Значення (а ₀, b ₀) та (а ₁, b ₁) визначаються як

3.

Значення (а ₃, b ₃), (а ₄, b ₄) і т.д. визначаються рекурентно згідно з правилами

Середнє число ітерацій в (1.3.13) [8] можна визначити як

.

Дата добавления: 2013-12-14