Еліптична криптографія

Еліптична криптографія — розділ криптографії, який вивчає асиметричні криптосистеми, засновані на еліптичних кривих над кінцевими полями. Головна перевага еліптичної криптографії полягає в тому, що на сьогодні є невідомим існування субекспоненціальних алгоритмів вирішення завдань дискретного логарифмування. Використання еліптичних кривих для створення криптосистем було незалежно запропоновано Нілом Коблицем^[en] та Віктором Міллером^[en] у 1985 році.^[1]

Вступ[ред. | ред. код]

Асиметрична криптографія заснована на складності рішення деяких математичних задач. Ранні криптосистеми з відкритим ключем, такі як алгоритм RSA, криптостійкі завдяки тому, що складно розкласти велике число на прості множники. При використанні алгоритмів на еліптичних кривих припускається, що не існує субекспоненційних алгоритмів для вирішення завдання дискретного логарифмування в групах їх точок. При цьому порядок групи точок еліптичної кривої визначає складність завдання. Вважається, що для досягнення такого ж рівня криптостійкості як і в RSA, потрібні групи менших порядків, що зменшує витрати на зберігання та передачу інформації. Наприклад, на конференції RSA 2005 Агентство національної безпеки оголосила про створення «Suite B», у якому використовуються виключно алгоритми еліптичної криптографії, причому для захисту інформації класифікованої до «Top Secret» використовуються всього лише 384-бітові ключі.

Еліптичні криві над скінченними полями[ред. | ред. код]

Еліптичною кривою називається множина точок ${\displaystyle (x,y)}$, що задовольняють рівняння:

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}}$

Це рівняння може розглядатися над довільними полями і, зокрема, над скінченними полями, що викликає особливу зацікавленість для криптографії.

У криптографії еліптичні криві розглядаються над двома типами скінченних полів: простими полями непарної характеристики (${\displaystyle \mathbb {Z} _{p}}$, де ${\displaystyle p>3}$ — просте число) і полями характеристики 2 (${\displaystyle GF(2^{m})}$).

Еліптичні криві над полями непарної характеристики[ред. | ред. код]

Над полем ${\displaystyle \mathbb {Z} _{p}}$ характеристики ${\displaystyle p>3}$ рівнянню еліптичної кривої E можна надати вигляд:

${\displaystyle E:\quad y^{2}=x^{3}+Ax+B{\pmod {p}},}$

де ${\displaystyle A,B\in \mathbb {Z} _{p}}$ — константи, що задовольняють ${\displaystyle 4A^{3}+27B^{2}\not \equiv 0{\pmod {p}}}$.

Групою точок еліптичної кривої E над полем ${\displaystyle \mathbb {Z} _{p}}$ називається множина пар ${\displaystyle (x,y)}$, що лежать на E, об'єднаних з нульовим елементом ${\displaystyle {\mathcal {O}}}$:

${\displaystyle E(\mathbb {Z} _{p})={\mathcal {O}}\cup \left\{(x,y)\in \mathbb {Z} _{p}\times \mathbb {Z} _{p}|y^{2}\equiv x^{3}+Ax+B{\pmod {p}}\right\}.}$

Слід зазначити, що в ${\displaystyle \mathbb {Z} _{p}}$ у кожного ненульового елемента є або два квадратні корені, або нема жодного, тому точки еліптичної кривої розбиваються на пари виду ${\displaystyle (x,y)}$ і ${\displaystyle (x,-y)}$.

Приклад[ред. | ред. код]

Розглянемо еліптичну криву ${\displaystyle y^{2}=x^{3}+3x+2}$ над полем ${\displaystyle \mathbb {Z} _{5}}$. На цій кривій, зокрема, лежить точка ${\displaystyle (1,1)}$, оскільки ${\displaystyle 1^{2}\equiv 1^{3}+3\cdot 1+2{\pmod {5}}}$.

Теорема Гассе[ред. | ред. код]

Теорема Гассе про еліптичні криві стверджує, що кількість точок на еліптичній кривій близька до розміру кінцевого поля:

${\displaystyle ({\sqrt {p}}-1)^{2}\leqslant |E(\mathbb {Z} _{p})|\leqslant ({\sqrt {p}}+1)^{2},}$

звідки:

${\displaystyle \left||E(\mathbb {Z} _{p})|-p\right|<2{\sqrt {p}}+1.}$

Еліптичні криві над полями характеристики 2[ред. | ред. код]

Над полем характеристики 2 розглядають два види еліптичних кривих:

• Суперсингулярна крива

  ${\displaystyle y^{2}+ay=x^{3}+bx+c}$

• Несуперсингулярна крива

  ${\displaystyle y^{2}+axy=x^{3}+bx^{2}+c}$

Особлива зручність суперсингулярних еліптичних кривих полягає в тому, що для них легко обчислити порядок, тоді як обчислення порядку несуперсингулярних кривих викликає труднощі. Суперсингулярні криві зручні для створення саморобної ЕСС-криптосистеми. Для їх використання можна обійтися без трудомісткої процедури обчислення порядку.

Проєктивні координати[ред. | ред. код]

Для обчислення суми пари точок на еліптичній кривій потрібно не тільки кілька операцій додавання і множення в ${\displaystyle \mathbb {F} _{q}}$, а й операція обернення, тобто для заданого ${\displaystyle x\in \mathbb {F} _{q}}$ знаходження такого ${\displaystyle y\in \mathbb {F} _{q}}$, що ${\displaystyle xy=1}$, яка на один-два порядки повільніша, ніж множення. На щастя, точки на еліптичній кривій можуть бути представлені в різних системах координат, які не вимагають використання обернення при додаванні точок:

• У проєктивній системі координат кожна точка ${\displaystyle (x,y)}$ задається трьома координатами ${\displaystyle (X,Y,Z)}$, які задовольняють співвідношенням:

  ${\displaystyle x={\frac {X}{Z}}}$, ${\displaystyle y={\frac {Y}{Z}}}$.

• У системі координат Якобі точка також задається трьома координатами ${\displaystyle (X,Y,Z)}$ зі співвідношеннями: ${\displaystyle x={\frac {X}{Z^{2}}}}$, ${\displaystyle y={\frac {Y}{Z^{3}}}}$.
• У системі координат Лопес-Дахаб (кит. 洛佩斯 · 達哈卜, лат. Lopez-Dahab) Виконується співвідношення: ${\displaystyle x={\frac {X}{Z}}}$, ${\displaystyle y={\frac {Y}{Z^{2}}}}$.
• У модифікованій системі координат Якобі використовуються 4 координати ${\displaystyle (X,Y,Z,aZ^{4})}$ з тими ж співвідношеннями.
• У системі координат Чуднівського-Якобі використовується 5 координат ${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$.

Важливо зазначити, що можуть існувати різні найменування — наприклад, IEEE P1363-2000 називає проєктивними координатами те, що зазвичай називають координатами Якобі.

Реалізація шифрування[ред. | ред. код]

Конкретні реалізації алгоритмів шифрування на еліптичній кривій описані нижче. Тут ми розглянемо загальні принципи еліптичної криптографії.

Набір параметрів[ред. | ред. код]

Для використання еліптичної криптографії всі учасники повинні узгодити всі параметри, що визначають еліптичну криву, тобто набір параметрів криптографічного протоколу. Еліптична крива визначається константами ${\displaystyle a}$ і ${\displaystyle b}$ з рівняння (2). Абелева підгрупа точок є циклічною і задається однією породжує точкою G . При цьому кофактор ${\displaystyle h={\frac {|E|}{n}}}$, де n  — порядок точки G , повинен бути невеликим (${\displaystyle h\leq 4}$, бажано навіть ${\displaystyle h=1}$).

Отже, для поля характеристики 2 характерний набір параметрів: ${\displaystyle (m,f,a,b,G,n,h)}$, а для кінцевого поля ${\displaystyle \mathbb {Z} _{p}}$, де ${\displaystyle p>3}$, набір параметрів: ${\displaystyle (p,a,b,G,n,h)}$.

Існує кілька рекомендованих наборів параметрів:

• NIST^[2]
• SECG^[3]

Для створення власного набору параметрів необхідно:

1. Вибрати набір параметрів.
2. Знайти еліптичну криву, що задовольняє цьому набору параметрів.

Для знаходження кривої для заданого набору параметрів використовуються два методи:

• Вибрати випадкову криву, потім скористатися алгоритмом підрахунку точок.^[4][5]
• Вибрати точки, після чого побудувати криву за цими точкам, використовуючи техніку множення.

Існує декілька класів криптографічно «слабких» кривих, яких слід уникати:

• Криві над ${\displaystyle \mathbb {F} _{2^{m}}}$, де ${\displaystyle m}$ — не просте число. Шифрування на цих кривих піддається атакам Вейля.
• Криві з ${\displaystyle |E(\mathbb {F} _{q})|=Q}$ вразливі до атаки відображенням точки даної кривої на аддитивну групу поля ${\displaystyle \mathbb {F} _{q}}$.

Швидка редукція (NIST-криві)[ред. | ред. код]

Розподіл по модулю p (необхідний для операцій додавання і множення) може виконуватися швидше, якщо як p вибрати просте число близьке до ступеня числа 2. Зокрема, в ролі p може виступати просте число Мерсенна. Наприклад, хорошим вибором є ${\displaystyle p=2^{251}-1}$ або ${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1}$. Національний інститут стандартів і технології (NIST) рекомендує використовувати такі прості числа подібні до p.

Порівняно з алгоритмом Барретта, може бути на порядок швидшим.^[6] Вища швидкість цього методу є більш практичною ніж теоретичною, і полягає в тому, що операції з числами близькими до ступенів двійки ефективніше виконуються комп'ютерами бітовими операціями.

Ще одною перевагою кривих, рекомендованих NIST, є вибір значення ${\displaystyle a=-3}$, — це прискорює операцію додавання в координатах Якобі.

Еліптичні криві, рекомендовані NIST[ред. | ред. код]

NIST рекомендує 15 еліптичних кривих, багато з яких були отримані Jerry Solinas (NSA) на базі напрацювань Neal Koblitz^[en][7]. Зокрема, FIPS 186-3^[8] рекомендує 10 кінцевих полів. Деякі з них:

• Поля ${\displaystyle \mathbb {F} _{p}}$, де просте p має довжину 192, 224, 256, 384 або 521^[9] біт.
• Поля ${\displaystyle \mathbb {F} _{2^{m}}}$, де m = 163, 233, 283, 409 або 571.

Причому для кожного кінцевого поля рекомендують одну еліптичну криву. Ці кінцеві поля та еліптичні криві вибрані, як часто помилково вважають, завдяки високому рівню безпеки. За заявами NIST їх вибір був обґрунтований ефективністю програмної реалізації.^[10] Є сумніви в безпеці принаймні декількох з них.^[11][12][13]

Розмір ключа[ред. | ред. код]

Найшвидшим алгоритмам, що виконують завдання дискретного логарифмування на еліптичних кривих, як от алгоритм Шенкса і ρ-метод Полларда, необхідно ${\displaystyle O({\sqrt {n}})}$ операцій. Тому розмір поля повинен як мінімум в два рази перевищувати розмір ключа. Наприклад, для 128-бітного ключа рекомендується використовувати еліптичну криву над полем ${\displaystyle \mathbb {F} _{p}}$, де p має довжину 256 бітів.

Найскладніші публічно зламані схеми на еліптичних кривих містили 112-бітний ключ для кінцевого простого поля і 109-бітний ключ для кінцевого поля характеристики 2.

У липні 2009 року, кластер з більше двохсот Sony Playstation 3 за 3,5 місяці знайшов 109-бітний ключ. Ключ над полем характеристики 2 був знайдений у квітні 2004, а з використанням 2 600 комп'ютерів, протягом 17 місяців.

Застосування[ред. | ред. код]

Більшість криптосистем сучасної криптографії природним чином можна «перекласти» на еліптичні криві. Головна ідея полягає в тому, що відомий алгоритм, який використовується для конкретних кінцевих груп переписується для використання груп раціональних точок еліптичних кривих:

• ECDSA алгоритм, що ґрунтується на ЕЦП.
• ECDH алгоритм заснований на алгоритмі Діффі — Геллмана.
• ECIES (англ. Elliptic Curve Integrated Encryption Scheme) — також ґрунтується на еліптичних кривих.
• ECMQV алгоритм, що ґрунтується на MQV, протоколі розподілу ключів Менезеса-Кью-Венстоуна.
• Факторизація Ленстри за допомогою еліптичних кривих
• Dual EC DRBG

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

З огляду 2013 найчастіше використовуються криві: nistp256, nistp384, nistp521, secp256k1, secp384r1, secp521r1^[14]

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]

• Болотов А.А., Гашков С.Б., Фролов А.Б., Часовських А.А. Алгоритмічні основи еліптичної криптографії. — Москва : МЕІ, 2000. — 100 с. Архівовано з джерела 4 березня 2016
• Болотов А.А., Гашков С.Б., Фролов А.Б., Часовських А.А. Елементарне введення в еліптичну криптографію. — Москва : КомКнига, 2 006. — 280 с.

Це незавершена стаття з криптографії. Ви можете допомогти проєкту, виправивши або дописавши її.