Асиметричне криптографічне RSA перетворення направленого шифрування класу RSA, страница 2

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

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

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

Е_k, D_k – мають вибиратися з повної множини випадково, порівняно ймовір-
но і незалежно, мають забезпечувати однозначну оборотність прямого та зворотного перетворення. Відповідним чином засвідчений відкритий ключ є сертифікатом (див. п. 1.1.1).

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

,

де

.

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

ax+by=1.                                                       (1.56)

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

,                                          (1.57)

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

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

,                                               (1.58)

отримаємо а=j(N), x=(-k), b=E_k, y=D_k .

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

Найбільш швидке розв’язання (1.58) дає застосування ланцюгових дробів, які дозволяють визначити х та у як

,                                          (1.59)

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

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

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

,                                  (1.60)

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

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

                                                                  ,

                                            .

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

.                                          (1.61)

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

.

11.3 Методи оцінки стійкості RSA криптоперетворень

В системі RSA криптоаналіз метою якого є визначення особистого (таємного) ключа, наприклад Е_к ключа ключової пари (), де D_к є відкритий ключ, може бути здійснений таким чином:

1.  Зловмисник отримує системні параметри (однакові для обох користувачів)  та відкритий ключ Ек.

2.  Використовуючи спеціальну криптоаналітичну систему здійснюється факторизація модуля , в результаті чого він визначає прості числа та .

3.  Розраховується значення функції Ойлера

 .

4.  Використовуючи методику, наведену в (1.49), здійснюється розв’язок порівняння .

Взагалі, найбільш простим методом криптоаналізу є підбір ключової пари (), тобто при відомих  визначається Dк.

Нехай  має довжину  тоді, якщо , то

.

Область існування для ключа  можна визначити, як всі цілі числа, що не перевищують  та є взаємопростими, тобто . Підбір  із повної множини є задачею, що набагато складніша, ніж алгоритм, заданий вище пп. 1-4.

Проведені дослідження підтвердили, що необхідний рівень стійкості в RSA забезпечується в тому випадку, якщо прості числа є сильними.

Покладемо, що як  використовуються прості числа, тоді справедливе таке: , , .

Використовуючи теорему Чебишева [17], визначимо кількість особистих ключів, як

.                         (1.62)

Приклад 1. Визначимо число простих 1024 бітних чисел

.

Щоб розв’язати цю задачу методом тотального перебору не вистачить енергії сонця.

Згідно з сучасними поглядами найбільш перспективними методами криптоаналізу є методи, що базуються на пп. 1-4, що розглянуті вище. При цьому найбільш складна задача факторизації модуля N вимагає найбільших ресурсів і суттєво залежить від використовуваного методу. На сьогодні відомо та апробовано такі методи факторизації:

-  спробного поділу;

-  -Поларда і -1 Поларда;

-  Ленстра, з використанням еліптичних кривих ;

-  квадратичне решето;

-  загальне та спеціальні решета числового поля.

Одним із перспективних методів факторизації є метод, що реалізований у вигляді квадратичного решета. В таблиці 1.1 показано результати, які отримано в світі при розв’язку задач факторизації.