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

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

Вступ

ред.

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

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

ред.
Докладніше: Еліптична крива

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

 

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

У криптографії еліптичні криві розглядаються над двома типами скінченних полів: простими полями непарної характеристики ( , де   — просте число) і полями характеристики 2 ( ).

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

ред.

Над полем   характеристики   рівнянню еліптичної кривої E можна надати вигляд:

 

де   — константи, що задовольняють  .

Групою точок еліптичної кривої E над полем   називається множина пар  , що лежать на E, об'єднаних з нульовим елементом  :

 

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

Приклад

ред.

Розглянемо еліптичну криву   над полем  . На цій кривій, зокрема, лежить точка  , оскільки  .

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

ред.

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

 

звідки:

 

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

ред.

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

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

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

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

ред.

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

  • У проєктивній системі координат кожна точка   задається трьома координатами  , які задовольняють співвідношенням:
     ,  .
  • У системі координат Якобі точка також задається трьома координатами   зі співвідношеннями:  ,  .
  • У системі координат Лопес-Дахаб (кит. 洛佩斯 · 達哈卜, лат. Lopez-Dahab) Виконується співвідношення:  ,  .
  • У модифікованій системі координат Якобі використовуються 4 координати   з тими ж співвідношеннями.
  • У системі координат Чуднівського-Якобі використовується 5 координат  .

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

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

ред.

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

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

ред.

Для використання еліптичної криптографії всі учасники повинні узгодити всі параметри, що визначають еліптичну криву, тобто набір параметрів криптографічного протоколу. Еліптична крива визначається константами   і   з рівняння (2). Абелева підгрупа точок є циклічною і задається однією породжує точкою G . При цьому кофактор  , де n  — порядок точки G , повинен бути невеликим ( , бажано навіть  ).

Отже, для поля характеристики 2 характерний набір параметрів:  , а для скінченного поля  , де  , набір параметрів:  .

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

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

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

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

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

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

  • Криві над  , де   — не просте число. Шифрування на цих кривих піддається атакам Вейля.
  • Криві з   вразливі до атаки відображенням точки даної кривої на аддитивну групу поля  .

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

ред.

Розподіл по модулю p (необхідний для операцій додавання і множення) може виконуватися швидше, якщо як p вибрати просте число близьке до ступеня числа 2. Зокрема, в ролі p може виступати просте число Мерсенна. Наприклад, хорошим вибором є   або  . Національний інститут стандартів і технології (NIST) рекомендує використовувати такі прості числа подібні до p.

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

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

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

ред.

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

  • Поля  , де просте p має довжину 192, 224, 256, 384 або 521[9] біт.
  • Поля  , де m = 163, 233, 283, 409 або 571.

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

Розмір ключа

ред.

Найшвидшим алгоритмам, що виконують завдання дискретного логарифмування на еліптичних кривих, як от алгоритм Шенкса і ρ-метод Полларда, необхідно   операцій. Тому розмір поля повинен як мінімум в два рази перевищувати розмір ключа. Наприклад, для 128-бітного ключа рекомендується використовувати еліптичну криву над полем  , де p має довжину 256 бітів.

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

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

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

ред.

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

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

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

Примітки

ред.
  1. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography. — Springer. — 523 с.
  2. Recommended Elliptic Curves for Government Use (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. Schoof-Elkies-Atkin algorithm (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 978-3-540-41898-6.
  7. Neal Koblitz. Random Curves: Journeys of a Mathematician. — Springer, 2009. — С. 312-313. — ISBN 9783540740780.
  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). Сноуден і еліптичне крипто: Bitcoin і TOR поза підозрою, але що з іншими проєктами?. Компьютерра. Архів [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
  • Болотов А.А., Гашков С.Б., Фролов А.Б., Часовських А.А. Елементарне введення в еліптичну криптографію. — Москва : КомКнига, 2006. — 280 с.