![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Вважається, що 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×107с/рік
За останні 20 років математики працювали над розв’язанням задачі факторизації дуже великих чисел.
Для двійкового та загального решіт числового поля складність криптоаналізу може бути оцінена як:
, (1.70)
– параметри методу. Наприклад, для квадратичного решета δ=1,96; ν=1/3.
Складність І – вимірюється кількістю групових операцій, які треба виконати для факторизації модуля N.
Формування параметрів та ключів, а також оцінка стійкості для RSA направленого шифру можна здійснити наступним чином.
При спрямованому шифруванні параметри і ключі поділяють на 2 групи:
- особисті ;
- публічні (відкриті) (),
.
Далі k – й користувач генерує параметри, особистий і відкритий ключі.
Кожен користувач шифрує , використовуючи:
, (1.71)
розшифрувати її може тільки k – й користувач, використовуючи особистий ключ
. (1.72)
Найбільш оптимальним методом криптоаналізу є:
- перехоплення значень та відкритого ключа
;
- факторизація модуля (знайти P, Q);
- визначення особистого ключа Dk із порівняння
,
де
.
Складність криптоаналізу визначається з використанням співвідношення (1.3.24), причому параметри вибираються в залежності від методу криптоаналізу.
Для забезпечення стійкості при побудові параметрів та ключів необхідно:
1. Відбраковувати ключі-близнята, тобто відмовлятися від ключової пари у якої Ek = Dk.
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(2m).
У виразі (1.80) та (1.81) число d є особистим (секретним) ключем. Операції (1.80) та (1.81) можна подати у вигляді
. (1.82)
При виконанні (1.82) виділяють дві операції: операція подвоєння – складання двох однакових точок, і операція додавання – складання двох різних точок та
. Сума цих точок визначається як:
. (1.83)
Дата публикования: 2015-01-14; Прочитано: 396 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!