Что любой разработчик должен знать об эллиптических кривых

Ссылка на оригинал статьи: https://www.entropy1729.com/what-every-dev-needs-to-know-about-elliptic-curves/ Мой Discord: useless_dorozhkina#1394

Эллиптические кривые (EC) стали одним из самых полезных инструментов для современной криптографии. Они были предложены в 1980-х годах и стали широко использоваться после 2004 года. Их главное преимущество заключается в том, что они предлагают меньшие размеры ключей для достижения того же уровня безопасности, что и другие методы, что приводит к меньшим требованиям к хранению и передаче. Например, для криптографии EC (ECC) требуются 256-битные ключи для достижения того же уровня безопасности, что и 3000-битный ключ при использовании RSA (еще одна криптографическая система с открытым ключом, появившаяся в конце 70-х годов). ECC и RSA работают, скрывая вещи внутри определенной математической структуры, известной как конечная циклическая группа (мы скоро объясним это). Сокрытие делается скорее на виду: вы могли бы взломать систему, если бы смогли отменить математический трюк (предупреждение о спойлере: если все сделано правильно, это заняло бы у вас несколько жизней). Это как если бы вы положили 1 000 000 долларов в небьющуюся стеклянную коробку, и любой мог бы взять деньги, если бы смог её разбить.

Чтобы понять эти объекты и почему они работают, нам нужно зайти за кулисы и взглянуть на математические принципы (мы не будем вдаваться в сложные детали или доказательства, а скорее сосредоточимся на концепциях или идеях). Мы начнем с объяснения конечных полей и групп, а затем перейдем к эллиптическим кривым (над конечными полями) и посмотрим, все ли кривые были созданы равными для криптографических целей.

Конечные поля

Мы знаем примеры полей из элементарной математики. Рациональные, вещественные и комплексные числа с обычными понятиями сложения и умножения являются примерами полей (хотя они не конечны).

Конечное поле — множество, снабженное двумя операциями, которые мы будем называть + и ×. Чтобы это действительно являлось полем, эти операции должны обладать определенными свойствами:

Если a и b принадлежат одному множеству, то c = a + b и d = a × b должны также принадлежать одному множеству. В математике это называется множеством, замкнутым относительно операций +, ×.
Имеется нулевой элемент, 0, такой, что a + 0 = a для любого a в множестве. Данный элемент называется аддитивной идентичностью.
Имеется элемент, 1, такой, что 1 × a = a для любого a в множестве. Данный элемент называется мультипликативной идентичностью.
Если a принадлежит множеству, то имеется такой элемент b, что a + b = 0. Мы называем такой элемент противоположным и обычно записываем как −a.
Если a принадлежит множеству, то имеется такой элемент c, что a × c = 1. Такой элемент называется мультипликативной обратной величиной и записывается как

Прежде чем мы сможем поговорить о примерах конечных полей, нам нужно ввести арифметику по модулю.

Мы узнали, что, учитывая натуральное число или ноль a и ненулевое число b, мы могли бы записать a следующим образом: a = q × b + r, где q — частное, а r — остаток от деления a/b. Это r может принимать значения 0, 1, 2, ..., b−1. Мы знаем, что если r равно нулю, то a кратно b. Это может показаться не новым, но это дает нам очень полезный инструмент для работы с числами. Например, если b = 2, тогда r = 0, 1. Когда оно равно 0, a — чётное (делится на 2), а когда 1, a — нечётное. Простой способ перефразировать это (благодаря Гауссу):

если a — нечётное, и

если a — чётное. Можно увидеть, что если мы сложим два нечётных числа a1 и a2

Это показывает нам, что, если мы хотим знать, чётна сумма чисел или нет, мы можем просто суммировать остатки от деления этих чисел на 2 (применение этого заключается в том, что для проверки делимости на два мы должны смотреть только на последний бит двоичного представления).

Другая ситуация, с которой мы встречаемся каждый день, связана со временем. Если в понедельник в 10 утра у нас есть 36 часов до крайнего срока проекта, мы должны сдать его к 10 часам вечера вторника. Это потому, что 12 помещается в 36 ровно 3 раза, откуда получается пн-10 вечера, вт-10 утра, вт-10 вечера. Если бы у нас было 39 часов, мы бы перешли к часу ночи среды.

Простой способ взглянуть на это соотношение (формально известное как сравнение по модулю p) заключается в том, что если a ≡ b(mod p), то p делит a − b или a = k × p + b для целого числа k.

Если подходить более неформально, мы видим, что действующая операция (mod p) оборачивается вокруг результатов определенных вычислений, всегда выдавая числа в ограниченном по p − 1 диапазоне.

Мы видим, что, если a1 ≡ b1 (mod p) и a2 ≡ b2 (mod p), тогда a1 + a2 ≡ b1 + b2 (mod p) (если b1 + b2 > p мы можем обернуться вокруг результата). Аналогичные результаты применимы при использовании вычитания и умножения. Деление предоставляет определенные трудности, но мы можем немного изменить ситуацию и заставить ее работать следующим образом: вместо того, чтобы представлять деление как a ÷ b, мы можем вычислить

где b^(−1) — мультипликативная обратная величина от b, вспомните

Представим, что p = 5,следовательно элементами группы являются 0, 1, 2, 3, 4.

Мы можем видеть, что 1 является своей собственной мультипликативной обратной величиной, поскольку 1 × 1 = 1 ≡ 1 (mod 5). Если мы возьмем 2 и 3, тогда 2 × 3 = 6 ≡ 1 (mod 5) (поэтому 3 — обратное число 2) и 4 × 4 = 16 ≡ 1 (mod 5). Определенные множество и операции удовлетворяют условиям поля.

Мы также можем простым способом определить целочисленные степени элементов поля. Если мы хотим возвести число a в квадрат, мы можем просто выполнить a × a и взять mod p. Если мы хотим возвести в куб, мы выполняем a × a × a и берем mod p. RSA использует возведение в степень для выполнения шифрования. Легко увидеть, что если показатель степени довольно велик (или основание очень велико, или и то, и другое), числа становятся действительно большими. Например, мы захотим вычислить

то когда мы дойдем до 1000, мы будем получать более, чем 300-значные числа, и это будет даже не конец вычисления. Мы можем провести это вычисление гораздо проще, поняв, что 65536=2^(16), каждый раз возводя число в квадрат и беря его остаток. В итоге мы выполняем только 16 подобных операций вместо первоначальных 65536! таким образом, избегая огромных чисел. Аналогичная стратегия будет использоваться при работе с EC!

Группы

Мы видели, что всякий раз, когда мы складываем два чётных целых числа, мы получаем еще одно. Кроме того, поскольку 0 является чётным, если мы сложим a и −a, мы получим 0, элемент идентичности суммы. Многие различные объекты имеют схожее поведение при выполнении определенной операции. Например, умножение двух обратимых матриц приводит к обратимой матрице. Если мы рассмотрим множество обратимых матриц из N × N, оснащенных умножением, мы увидим, что, если A принадлежит множеству, то A^(−1) — тоже; матрица идентичности принадлежит множеству (и играет роль элемента идентичности по отношению к умножению). Другими словами, некоторые множества, оснащенные определенной операцией, обладают некоторыми общими свойствами, и мы можем воспользоваться знаниями об этой структуре. Множество вместе с операцией образует группу. Формально группа — это множество G, оснащенное бинарной операцией × так, что:

Операция является ассоциативной, то есть (a × b) × c = a × (b × c).
Имеется элемент идентичности, e: e × a = a и a × e = a.
Для каждого элемента a в множестве имеется элемент b такой, что a × b = e и b × a = e. Мы обозначаем его b = a^(−1) для простоты.

Мы можем легко увидеть, что любое поле является, в частности, группой по отношению к каждой из двух его операций (условия 1, 2 и 4 для поля указывают, что оно также является группой по отношению к сумме, а 1, 3 и 5 — к умножению). Если операция коммутативна (то есть a × b = b × a), то группа известна как абелева (или коммутативная). Например, обратимые матрицы из N × N образуют группу, но она не является абелевой, поскольку A × B ≠ B × A для некоторых матриц A и B.

Мы будем рассматривать конечные группы (те, в которых множество содержит конечное число элементов) и, в частности, циклические группы. Такие группы могут быть сгенерированы путем многократного применения операции к элементу g, генератору группы. n-й корень из единицы в комплексных числах образует пример циклической группы при умножении; это множество решений

которые формируют exp(2πik/n), где k = 0, 1, 2..., n−1. Эта группа может быть сгенерирована путем взятия целых степеней exp(2πi/n). Корни единицы играют важную роль в вычислении быстрого преобразования Фурье (БПФ), которое имеет множество применений.

Эллиптические кривые в двух словах

Эллиптические кривые — очень полезные объекты, потому что они позволяют нам получить групповую структуру с интересными свойствами. С данным полем F, эллиптическая кривая является множеством точек (x, y), которые удовлетворяют следующему уравнению:

Оно известно как общее уравнение Вейерштрасса. Во многих случаях это уравнение может быть записано в более простой форме

которая является краткой формой (Вейерштрасса). В зависимости от выбора параметров a и b и области кривая может обладать некоторыми желаемыми свойствами или не обладать. Если

то такая кривая не является сингулярной.

Мы можем задать операцию, которая позволит нам суммировать элементы, принадлежащие эллиптической кривой, и получить группу. Это делается с помощью геометрической конструкции, правила хорды и касательной. Имея две точки на кривой, P1 = (x1, y1) и P2 = (x2, y2), мы можем нарисовать линию, соединяющую их. Эта линия пересечёт кривую в третьей точке, P3 = (x3, y3). Мы устанавливаем сумму P1 и P2 как (x3, −y3), то есть точка P3 перевёрнута вокруг оси x. Формулы следующие:

Мы легко можем заметить, что встречаемся с проблемой, когда пытаемся суммировать P1 = (x1, y1) и P2 = (x1, −y1). Нам нужно добавить в систему дополнительную точку, которую мы называем точкой на бесконечности, O. Это включение необходимо для определения структуры группы и работает как элемент идентификации для групповой операции.

Другая проблема появляется, когда мы хотим сложить P1 и P1, чтобы получить P3 = 2P1. Но, если мы проведем касательную линию к кривой в P1, мы увидим, что она пересекает кривую в другой точке. Если мы хотим выполнить эту операцию, нам нужно найти наклон касательной линии и найти пересечение:

Это требует небольшой работы, но мы можем доказать, что эллиптическая кривая с помощью этой операции обладает свойствами группы. Мы будем использовать конечные поля для работы с этими кривыми, и группы, которые мы получим, будут являться конечными циклическими группами, то есть группами, которые могут быть сгенерированы путем повторного использования операции над генератором g: g, 2g, 3g, 4g, 5g...

Если мы нанесем совокупность точек на график, то увидим, что точки распределены довольно "случайным" образом. Например, 2g может находиться очень далеко от 3g, которая в свою очередь находится очень далеко от 4g. Если бы мы хотели знать, сколько раз k мы должны добавить генератор, чтобы достичь определенной точки P (то есть решить уравнение kg = P), мы бы увидели, что у нас нет простой стратегии, и мы вынуждены выполнять грубый поиск по всем возможным k. Эта проблема известна как проблема дискретного логарифмирования (эллиптической кривой) (log для друзей) (другие друзья предпочитают ECDLP).

С другой стороны, если мы знаем k, мы можем очень быстрым способом вычислять P = kg. Это дает нам способ скрыть (на виду) вещи внутри группы. Конечно, если бы вы могли сломать DLP, вы могли бы получить k, но это довольно неосуществимо. Если мы хотим вычислить 65536g, мы можем сделать это , поняв , что g + g = 2g, 2g + 2g = 4g, 4g + 4g = 8g...до 32768g + 32768g = 65535g, так мы сузили бы количество операций от 65536 до 16. Существует множество полезных алгоритмов, которые позволяют нам ускорить операции над эллиптическими кривыми, избегая дорогостоящих вычислений, таких как инверсии, которые пригождаются, когда мы хотим вычислить наклон.

Все ли эллиптические кривые полезны для криптографии?

Сила криптографии эллиптических кривых заключается в сложности решения задачи дискретного логарифмирования. Это связано с количеством элементов (порядком множества), составляющих циклическую группу. Если число является очень большим простым числом или оно содержит очень большое простое число в своей факторизации (то есть число кратно большому простому числу), то задача становится неосуществимой. Однако, если порядок состоит из малых простых чисел, можно выполнить поиск по подгруппам и восстановить ответ с помощью китайской теоремы об остатках. Это связано с тем, что сложность зависит от размера самого большого задействованного простого числа.

Некоторые кривые обладают желаемыми свойствами, и им были даны имена. Например, Bitcoin использует secp256k1, которая имеет следующие параметры:

Чтобы получить представление о количестве элементов группы можно представить, что они составляют около r ≈ 10^(77). Даже если бы у нас были 10^(12) суперкомпьютеров, выполняющих более 10^(17) поисков точек в секунду в течение ста миллионов лет мы даже близко не подошли бы к проверке всех возможностей.

Чтобы гарантировать 128-битную безопасность, ECs нужны порядки групп, близкие к 256-битным (то есть порядки с простыми множителями около 10^(17)). Это связано с тем, что существуют алгоритмы, которые могут решить задачу, выполняя операции вокруг √r. Если длина самого большого простого числа меньше 94 бит, его можно разбить с помощью настольного компьютера. Конечно, даже если ваша группа достаточно велика, ничто не может спасти вас от плохой реализации.

Возникает вопрос: как мы можем узнать количество элементов нашей EC? К счастью, математика снова приходит нам на помощь, например, граница Хассе, алгоритм Шуфа и способ проверки, является ли число простым или нет. В следующий раз мы продолжим раскрывать математические принципы, лежащие в основе полезных инструментов в криптографии.