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

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

Вступ

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

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

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

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

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

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

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

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

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

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

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

$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\}.$

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

Приклад

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

Теорема Гассе

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

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

звідки:

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

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

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

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

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

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

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

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

Проєктивні координати

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

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

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

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

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

Реалізація шифрування

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

Набір параметрів

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

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

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

• NIST
• SECG

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

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

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

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

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

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

Швидка редукція (NIST-криві)

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

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

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

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

NIST рекомендує 15 еліптичних кривих, багато з яких були отримані Jerry Solinas (NSA) на базі напрацювань Ніла Коблица. Зокрема, FIPS 186-3 рекомендує 10 скінченних полів. Деякі з них:

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

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

Розмір ключа

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

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

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

Застосування

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

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

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

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

Посилання

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