Вибір та використання криптографічно стійких еліптичних кривих
,
Львівський державний університет безпеки життєдіяльності, м. Львів
В тезах розглянуто криптографічні методи захисту інформації. Проаналізовано принципи побудови криптографічних алгоритмів. Визначено сферу застосування еліптичних кривих в асиметричній криптографії. Сформульовано проблематику вибору параметрів криптографічно стійкої еліптичної кривої.
Ключові слова: захист інформації, криптографія, еліптична крива.
In theses were considered cryptographic methods of information security. Also were analyzed the construct principles of cryptographic algorithms and defined the application scope of elliptic curves in asymmetric cryptography. In particular were formulated the problems of selecting options cryptographically strength elliptic curve.
Keywords: information security, cryptography, elliptic curve.
Сучасний світ характеризується тенденцією постійного підвищення ролі інформації, яка має усе більш вагоме значення у функціонуванні державних і суспільних інститутів в житті кожної людини. Інформатизація веде до створення єдиного світового інформаційного простору. Сьогодні багато конфіденційної інформації передається між комп’ютерами відкритими мережами, що потребують її захисту та автентифікації. Серед всього спектру методів захисту інформації особливе місце займають саме криптографічні методи.
З кінця 1990 років починається процес відкритого формування світових стандартів на криптографічні методи захисту інформації. Мабуть, найвідомішим є розпочатий в 1997 році конкурс AES, в результаті якого в 2000 році державним стандартом США для шифрування інформації був прийнятий шифр Rijndael. Аналогічні проекти називаються NESSIE в Європі і CRYPTREC в Японії. У самих алгоритмах операціями, які ускладнюють лінійний і диференціальний криптоаналіз, крім випадкових функцій (наприклад, S-блоків, використовуваних в шифрах DES і ГОСТ), почали використовувати більш складні математичні конструкції, а саме обчислення в полі Галуа.
На сьогодення існує дві великі групи криптоалгоритмів: симетричні і асиметричні. До симетричних криптографічних алгоритмів належать такі алгоритми, для яких шифрування і розшифрування виконується однаковим ключем, тобто і відправник, і отримувач повідомлення використовують такий самий ключ. Такі алгоритми мають досить велику швидкість обробки як для апаратної, так і для програмної реалізації. Основним їх недоліком є труднощі, пов'язані з дотриманням безпечного розподілу ключів між абонентами системи [1]. На відміну від симетричних, асиметричні алгоритми шифрування використовують пару споріднених ключів – відкритий та секретний. При цьому, незважаючи на пов'язаність відкритого та секретного ключа в парі, обчислення секретного ключа на основі відкритого вважається технічно неможливим. В асиметричних криптосистемах, відкритий ключ може вільно розповсюджуватись, в той час як секретний ключ має зберігатись в таємниці. Зазвичай, відкритий ключ використовується для шифрування, в той час як секретний ключ використовується для розшифрування.
В останні роки інтенсивно в криптографії почали використовувати еліптичні криві (ЕК). Еліптична криптографія – це розділ криптографії, який вивчає асиметричні криптосистеми, що використовують еліптичні криві в кінцевих полях [2]. Асиметрична криптографія заснована на складності рішення деяких математичних задач. Ранні криптосистеми з відкритим ключем, такі як алгоритм RSA, безпечні завдяки тому, що складно розкласти складене число на прості множники. При використанні алгоритмів на еліптичних кривих вважається, що не існує субекспоненціальних алгоритмів для розв'язання задачі дискретного логарифмування в групах їх точок. При цьому порядок групи точок еліптичної кривої визначає складність завдання. Вважається, що для досягнення такого ж рівня безпеки як і в RSA потрібні групи менших порядків, що зменшує витрати на зберігання та передачу інформації. У сучасних криптосистемах на основі еліптичних кривих бінарної розмірності в діапазоні від 150 до 350 забезпечується рівень криптографічної стійкості, який потрібно використовувати у відомих криптографічних системах бінарної розмірності від 600 до 1400 і більше.
Розглянемо принципи побудови і використання еліптичних кривих в криптографії.
Кубічна крива на площині XY, задана рівнянням y2 = x3 + ax + b, що не має особливих точок, називається еліптичною кривою [3]. В реальних криптосистемах використовується рівняння
y2 = x3 + ax + b (mod p), (1)
де a, b належать полю GF(p), 4a3 + 27b2 (mod p) ≠ 0, p – просте число. Множина Ep(a, b) містить всі точки (х, у), х ≥ 0, р > у, що задовольняють рівняння (1), і точку в нескінченності О, яка є нулем для площини еліптичних кривих. Кількість точок еліптичної кривої позначається #Ep(a, b).
Множина точок Ep(a, b) має такі властивості:
– якщо P = (x, y) є точкою ЕК, то (x, y) + (x, -y) = О; точка (x, -y) позначається як –P;
– якщо P=(x1, y1) і Q = (x2, y2), де P≠Q, то P + Q = (x3, y3) обчислюється так:
x3 = (y2–y1)/(x2–x1)–x1–x2; y3 = –y1–(y2–y1)(x2–x1)/(x2–x1) (2)
– якщо P = Q, то подвоєння точки [2]P = (х3, у3) обчислюється за формулою:
x3 = ((3x12+a)/2/y1)2–2x1; y3 = –y1–(3x12+a)/2/y1 (3)
Одним із криптографічних застосувань еліптичних кривих є розподіл ключів. Криптографічний протокол обміну ключами з використанням еліптичної кривої виглядає таким чином:
– користувачі повинні обирати і повідомити всім форму еліптичної кривої та цілу точку G на цій кривій, яка є генеруючою точкою;
– користувач I повинен обрати ціле число k і знайти точку PA= k*G (додати точку G до самої себе k разів);
– користувач II повинен обрати число m і обчислити точку PB=m*G. Після цього вони обмінюються своїми результатами і їх спільним секретним ключем стає точка k*m*G.
Для розкриття такого протоколу потрібно за відомими k*G і G обчислити k<p, що є аналогом важкої задачі дискретного логарифмування у випадку алгоритму RSA: легко обчислити P за відомими k і G, проте важко обчислити k за відомими P і G.
Однією з проблем криптографічного застосування еліптичних кривих є вибір надійної випадкової кривої. Вирішення цієї проблеми визначає стійкість результуючої криптосистеми.
Процес формування надійної випадкової кривої містить етапи.
1. Вибирається випадково просте число р. Бітова довжина числа р: t = ëlog pû +1 повинна бути такою, щоб зробити неможливим застосування загальних методів знаходження логарифмів на кривій.
2. Вибираються випадкові числа а і b, такі, що а, b ≠ 0 і (4а3 + 27b2) (mod p) ≠ 0. Для підвищення ефективності розрахунків можна випадково вибирати тільки b, а а приймати рівним невеликому цілому числу.
3. Визначається кількість точок на кривій п = #Ер(а, b). Важливо, щоб п мало великий простий дільник q (розмір підмножини точок кривої), а найкраще саме було простим числом.
4. Перевіряється виконання умови (рk – 1) mod q ≠ 0 для всіх k, 0 < k < 32. Якщо умова не виконується, то повертаються до кроку 2.
5. Перевіряється, чи виконується умова q ≠ р. Якщо ні, то повертаються до кроку 2.
6. Знаходиться точка G – генератор підмножини точок q. Якщо q = n, то будь-яка точка (крім О) є генератором. Якщо q < n, то вибираються випадкові точки G', доки не виконається умова G = [n/q]G' ≠ 0.
В подальших дослідженнях планується розробити алгоритми генерування криптографічно стійких еліптичних кривих і перевірити застосування цих кривих в різних криптографічних додатках.
Література
[1] Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке Си / Б. Шнайер. – М.: Триумф, 2002. – 816 с.
[2] Криптография / Н. Смарт. – К.: Техносфера, 2005. – 528 с.
[3] Горбенко І. Д. Генерація параметрів та ключів для цифрового підпису на еліптичних кривих для скінченого простого поля / І. Д. Горбенко, , іков // Радіотехніка: Всеукр. міжвід. наук.-техн. зб. 2002., вип. 126. с. 193–198.
