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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Еліптична криптографія — розділ криптографії, який вивчає асиметричні криптосистеми, основані на еліптичних кривих над кінцевими полями. Головна перевага еліптичної криптографії полягає у тому, що на сьогодні невідомо існування субекспоненціальне алгоритмів вирішення завдання дискретного логарифмування. Використання еліптичних кривих для створення криптосистем було незалежно запропоновано Нілом Коблицем[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 .

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

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

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

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

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

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

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

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

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

Додатки[ред.ред. код]

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

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

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

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

  1. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman An introduction to mathematical cryptography. — Springer. — 523 с.
  2. Recommended Elliptic Curves for Government Use
  3. SEC 2: Recommended Elliptic Curve Domain Parameters
  4. Schoof's algorithm
  5. Schoof-Elkies-Atkin algorithm
  6. Neal Koblitz Random Curves: Journeys of a Mathematician. — С. 312-313. — ISBN 9783540740780.
  7. .pdf FIPS 186-3 // NIST, 2009; застарів в 2013 році з виходом FIPS 186-4
  8. Може здатися, що в цій послідовності допущена помилка. Однак, остання величина саме 521, а не 512 бітів.
  9. Daniel J. Bernstein, Tanja Lange, Security dangers of the NIST curves // 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)
  10. Daniel J. Bernstein and Tanja Lange (2013.11.18). [http: //safecurves.cr.yp.to/index .html SafeCurves: choosing safe curves for elliptic-curve cryptography.] (en). safecurves.cr.yp.to. Процитовано 2013 -12-20. 
  11. Євген Золотов (16 вересня 2013). [http: //www.computerra.ru/82902/elliptic-crypto/ Сноуден і еліптичне крипто: Bitcoin і TOR поза підозрою, але що з іншими проектами?]. Компьютерра. Процитовано 2013-12-20. 
  12. Dr Michael Scott, [http: //www.certivox .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.»
  13. Bos et al, Elliptic Curve Cryptography in Practice // MSR-TR-2013-119, November +2013

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

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