Эллиптическая криптография

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день неизвестно существование субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования. Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем (англ.) и Виктором Миллером (англ.) в 1985 году.[1]

Введение[править | править вики-текст]

Асимметричная криптография основана на сложности решения некоторых математических задач. Ранние криптосистемы с открытым ключом, такие как алгоритм RSA, безопасны благодаря тому, что сложно разложить составное число на простые множители. При использовании алгоритмов на эллиптических кривых полагается, что не существует субэкспоненциальных алгоритмов для решения задачи дискретного логарифмирования в группах их точек. При этом порядок группы точек эллиптической кривой определяет сложность задачи. Считается, что для достижения такого же уровня безопасности как и в RSA требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 Агентство национальной безопасности объявила о создании “Suite B”, в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации классифицируемой до “Top Secret” используются всего лишь 384-битные ключи.

Эллиптические кривые над конечными полями[править | править вики-текст]

Эллиптической кривой называется множество точек (x,y), удовлетворяющих уравнению:

y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+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}.
  • в системе координат López-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\le4, желательно даже h=1).

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

Существует несколько рекомендованных наборов параметров:

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

  1. Выбрать набор параметров.
  2. Найти эллиптическую кривую, удовлетворяющую этому набору параметров.

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

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

Существует несколько классов криптографически «слабых» кривых, которых следует избегать:

  • Кривые над \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) на базе наработок Neal Koblitz (англ.)русск.[6]. В частности, FIPS 186-3[7] рекомендует 10 конечных полей. Некоторые из них:

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

Причем для каждого конечного поля рекомендуется одна эллиптическая кривая. Эти конечные поля и эллиптические кривые выбраны как часто ошибочно считается, из-за высокого уровня безопасности. По заявлениям NIST их выбор был обоснован эффективностью программной реализации.[8] Имеются сомнения в безопасности по крайней мере нескольких из них.[9][10][11]

Размер ключа[править | править вики-текст]

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

Самые сложные схемы на эллиптических кривых, публично взломанные к настоящему времени, содержали 112-битный ключ для конечного простого поля и 109-битный ключ для конечного поля характеристики 2. [источник не указан 249 дней] В июле 2009 года, кластер из более чем 200 Sony Playstation 3 за 3.5 месяца нашел 109-битный ключ. Ключ над полем характеристики 2 был найден в апреле 2004 года, с использованием 2600 компьютеров, в течение 17 месяцев.[источник не указан 249 дней]

Приложения[править | править вики-текст]

Большинство криптосистем современной криптографии естественным образом можно "переложить" на эллиптические кривые. Основная идея заключается в том, что известный алгоритм, используемый для конкретных конечных групп переписывается для использования групп рациональных точек эллиптических кривых:

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

По обзору 2013 года чаще всего используются кривые: nistp256, nistp384, nistp521, secp256k1, secp384r1, secp521r1[12]

Примечания[править | править вики-текст]

  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. — Springer, 2009. — С. 312-313. — 402 с. — ISBN 9783540740780
  7. FIPS 186-3 // NIST, 2009; устарел в 2013 году с выходом FIPS 186-4
  8. 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" ([1])
  9. Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe curves for elliptic-curve cryptography. (англ.). safecurves.cr.yp.to (2013.11.18). Проверено 20 декабря 2013.
  10. Евгений Золотов. Сноуден и эллиптическое крипто: Bitcoin и TOR вне подозрений, но что с другими проектами?, Компьютерра (16 сентября 2013). Проверено 20 декабря 2013.
  11. Dr Michael Scott, Backdoors in NIST elliptic curves, Oct 24, 2013: "The curves themselves were suggested by Jerry Solinas who worked at the NSA."
  12. Bos et al, Elliptic Curve Cryptography in Practice // MSR-TR-2013-119, November 2013

Ссылки[править | править вики-текст]

  • Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Алгоритмические основы эллиптической криптографии. — Москва: МЭИ, 2000. — 100 с.
  • Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию. — Москва: КомКнига, 2006. — 280 с.