Оцінка стійкості і складності RSA криптоперетворень

Вважається, що RSA – доказово стійка криптосистема (криптоалгоритм). Основною задачею для RSA є побудування () і параметрів.

Кількість пар () для заданого N:

. (1.68)

Очевидно, якщо P -1 і Q -1 великі й у канонічному розкладанні мають мало співмножників, то число ключів буде максимізоване.

Тому числа P і Q мають бути не просто простими, а сильно простими числами, наприклад, мати вигляд:

P =2 R +1, (1.69)

де R – також просте.

Якщо зловмиснику доступний відкритий ключ і він знає N, тоді він може знайти , якщо він обчислить , тобто взнає P і Q. Основна його задача розкласти N на 2 співмножники P і Q. Ця задача називається факторизацією модуля і розглянута вище.

RSA – доказово стійка система, тому що доказ стійкості зводиться до доказу складності розкладання N на 2 співмножники.

Для оцінки стійкості використовується безпечний час , причому

,

де g – потужність криптоаналітичної системи, K =3,15×10⁷с/рік

За останні 20 років математики працювали над розв’язанням задачі факторизації дуже великих чисел.

Для двійкового та загального решіт числового поля складність криптоаналізу може бути оцінена як:

, (1.70)

– параметри методу. Наприклад, для квадратичного решета δ=1,96; ν=1/3.

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

Формування параметрів та ключів, а також оцінка стійкості для RSA направленого шифру можна здійснити наступним чином.

При спрямованому шифруванні параметри і ключі поділяють на 2 групи:

- особисті ;

- публічні (відкриті) (), .

Далі k – й користувач генерує параметри, особистий і відкритий ключі.

Кожен користувач шифрує , використовуючи:

, (1.71)

розшифрувати її може тільки k – й користувач, використовуючи особистий ключ

. (1.72)

Найбільш оптимальним методом криптоаналізу є:

- перехоплення значень та відкритого ключа ;

- факторизація модуля (знайти P, Q);

- визначення особистого ключа D_k із порівняння

,

де

.

Складність криптоаналізу визначається з використанням співвідношення (1.3.24), причому параметри вибираються в залежності від методу криптоаналізу.

Для забезпечення стійкості при побудові параметрів та ключів необхідно:

1. Відбраковувати ключі-близнята, тобто відмовлятися від ключової пари у якої E_k = D_k.

2. Відмовитися від простих чисел P та Q, які близькі за значенням, тобто P»Q.

3. При зашифруванні контролювати, що воно здійснюється, так як може бути випадок

. (1.73)

1.4 Криптоперетворення в групі точок еліптичних кривих

1.4.1 Поняття еліптичної кривої над полем Галуа та метрика арифметичних операцій

В асиметричних криптосистемах важливо забезпечити максимальну складність криптоаналізу. Найбільшу складність криптоаналізу можна забезпечити при використанні перетворень в групі точок еліптичних кривих
[19-21,26]. В цьому випадку складність

, (1.74)

де n – порядок базової точки ЕК (період).

Ця складність набагато більше, ніж субекспоненціальна складність

(1.75)

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

Кубічна ЕК в афінному базисі над простим полем має вигляд:

, (1.76)

– точки ЕК, а, b – параметри ЕК, р – просте число.

При цьому параметри кривої а та b мають задовольняти умову

. (1.77)

Точка – належить ЕК, якщо ця пара чисел відповідає порівнянню (1.76). Над розширеним полем рівняння ЕК має вигляд:

, (1.78)

де – точка ЕК; а, b – коефіцієнти (параметри) ЕК; f (x) – примітивний поліном над полем вигляду

. (1.79)

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

У рівнянні (1.78) і , а також а і b являють собою m -бітні вектори в поліноміальному чи нормальному базисах, зокрема, у поліноміальному базисі x, y, a, b є поліномами не вище m –ступеня. При цьому всі операції виконуються за модулем .

Існує тривимірне подання ЕК, що називається проективною геометрією (базисом). У проективній геометрії кожна точка задається трьома координатами – X,Y,Z.

Основною операцією у групі точок ЕК є скалярне множення

. (1.80)

У (1.80) d – число, G – базова точка ЕК , що породжує групу точок порядку n, причому

(1.81)

для розширеного поля GF(2^m).

У виразі (1.80) та (1.81) число d є особистим (секретним) ключем. Операції (1.80) та (1.81) можна подати у вигляді

. (1.82)

При виконанні (1.82) виділяють дві операції: операція подвоєння – складання двох однакових точок, і операція додавання – складання двох різних точок та . Сума цих точок визначається як:

. (1.83)