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

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

Вступ

Асиметрична криптографія заснована на складності рішення деяких математичних задач. Ранні криптосистеми з відкритим ключем, такі як алгоритм 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
• SECG

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

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

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

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

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

• Криві над ${\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.

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

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

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

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

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

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

Розмір ключа

Найшвидшим алгоритмам, що виконують завдання дискретного логарифмування на еліптичних кривих, як от і , необхідно ${\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) — також ґрунтується на еліптичних кривих.
• алгоритм, що ґрунтується на , протоколі розподілу ключів Менезеса-Кью-Венстоуна.
• Dual EC DRBG

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

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

Примітки

1. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography. — Springer. — 523 с.
2. (PDF). Архів оригіналу (PDF) за 5 червня 2011. Процитовано 18 грудня 2015.
3. SEC 2: Recommended Elliptic Curve Domain Parameters (PDF). (PDF) оригіналу за 31 травня 2005. Процитовано 31 травня 2005.
4. Schoof's algorithm^{[недоступне посилання з квітня 2019]}
5. (PDF). Архів оригіналу (PDF) за 26 липня 2011. Процитовано 26 липня 2011.
6. Brown, M.; Hankerson, D.; Lopez, J.; Menezes, A. (2001). Software Implementation of the NIST Elliptic Curves Over Prime Fields. Topics in Cryptology – CT-RSA 2001. Lecture Notes in Computer Science. 2020: 250—265. doi:10.1007/3-540-45353-9_19. ISBN .
7. Neal Koblitz. Random Curves: Journeys of a Mathematician. — Springer, 2009. — С. 312-313. — .
8. .pdf FIPS 186-3^{[недоступне посилання з липня 2019]} // NIST, 2009; застарів в 2013 році з виходом FIPS 186-4
9. Може здатися, що в цій послідовності допущено помилку. Однак, остання величина саме 521, а не 512 бітів.
10. Daniel J. Bernstein, Tanja Lange, Security dangers of the NIST curves [ 20 грудня 2015 у Wayback Machine.] // 2013.09.16: «Why did NIST choose these curves? * Most people we have asked: security * Actual NIST design document: eficiency» (-dan + tanja-20130531-4x3.pdf^{[недоступне посилання з липня 2019]})
11. Daniel J. Bernstein and Tanja Lange (2013.11.18). [http: //safecurves.cr.yp.to/index .html SafeCurves: choosing safe curves for elliptic-curve cryptography] (англ.). safecurves.cr.yp.to. Процитовано 2013 -12-20.^{[недоступне посилання з липня 2019]}
12. Євген Золотов (16 вересня 2013). . Компьютерра. Архів [http: //www.computerra.ru/82902/elliptic-crypto/ оригіналу] за 21 січня 2018. Процитовано 20 грудня 2013.
13. Dr Michael Scott, .com/blog/bid/344797/Backdoors-in-NIST-elliptic-curves Backdoors in NIST elliptic curves^{[недоступне посилання]}, Oct 24, 2013: «The curves themselves were suggested by Jerry Solinas who worked at the NSA.»
14. Bos et al, Elliptic Curve Cryptography in Practice [ 7 лютого 2016 у Wayback Machine.] // MSR-TR-2013-119, November +2013

Посилання

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