Алгоритм формування ключових пар.
Ключові дані – сукупність випадкових або псевдовипадкових значень змінних параметрів криптографічного перетворення інформації, за рахунок яких досягається мета цього перетворення.
Система RSA відноситься до криптосистем з відкритими ключами. У цій системі ключі Еk¹Dk, причому один із них повинний бути особистим, а другий відкритим. Наприклад, Еk – особистий, а Dk – відкритий, якщо вони використовуються для ЦП і навпаки, якщо використовуються для направленого шифрування.
Усі параметри (N,P,Q) також поділяються на 2 класи: N – відкритий, P,Q - конфіденційний (секретний).
Сутність забезпечення моделі взаємної недовіри – кожен користувач генерує ключі сам собі. Особистий ключ залишає в себе і забезпечує його строгу конфіденційність. Відкритий ключ розсилає всім користувачам, з якими він зв'язаний. Користувач також забезпечує цілісність і дійсність відкритих ключів.
Еk, Dk - повинні вибиратися з повної множини випадково, порівняно ймовірно і незалежно, повинні забезпечувати однозначну оборотність прямого та зворотного перетворення.
Значення Еk, Dk для практичних використань повинні задовольняти умові
,
де
Порівняння (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=Ek, y=Dk .
Якщо Ek сформувати випадково, а та b – відомі числа, а х та y – невідомі, що підлягають визначенню.
Одним із найбільш швидких рішень (3.) є ланцюгові дроби.
,
де m – порядок ланцюгового дробу, a і b – параметри ланцюгового дробу.
Знаходимо параметри:
a/b подається у виді ланцюгового дробу.
,
μ - порядок ланцюгового дробу, перший коефіцієнт, у якого залишок дорівнює 0.
Значення (а0,b0) та (а1,b1) визначаються як
3.
Значення (а3,b3), (а4,b4) і т.д. визначаються рекурентно згідно з правилами
Середнє число ітерацій в (1.3.13) [8] можна визначити як
.