Need for speed: Глава об эллиптических кривых
Ссылка на оригинал статьи: https://www.entropy1729.com/need-for-speed-elliptic-curves-chapter/ Мой Discord: useless_dorozhkina#1394
Введение
Эллиптические кривые (EC) получили широкое признание в качестве инструментов для криптографии. Они предлагают ряд преимуществ по сравнению с другими методами, такими как RSA, обеспечивая равные уровни безопасности с более короткими ключами (например, 228-битные ключи в криптографии EC так же хороши, как 2300-битные ключи RSA). Это является преимуществом, поскольку все больше и больше криптографии выполняется на смартфонах, которые менее мощны, чем компьютеры. Это кривые, определяемые уравнением
над каким-либо полем (например, полем действительных чисел). Их форма зависит от a и b, но более или менее они выглядят как на следующем рисунке:
В криптографии нас не интересуют кривые, определенные над действительными числами. Мы работаем с кривыми над некоторым конечным полем Fp (то есть множеством с конечным числом элементов, таких как 53, 101 или 2^(255)−19), потому что это дает нам математическую структуру (конечную группу), которая очень удобна. Кривая выглядит как разбросанные без четкого рисунка точки на конечном поле:
Эллиптические кривые играют роль в обмене ключами при подключении через SSH к серверу или для подтверждения владения bitcoin. Они также поригождаются при выполнении цифровых подписей, генерации случайных чисел (хотя с этим и были некоторые проблемы), и они полезны даже для факторных чисел (метод Ленстры). Например, в алгоритме цифровой подписи с эллиптической кривой (ECDSA) у вас есть следующие шаги (не волнуйтесь, если вы не понимаете всех терминов сейчас, мы рассмотрим их один за другим позже):
1. Вычислить E=hash(message), где hash — надежная хеш-функция.
2. Принять Z равным n крайним левым битам E, где n — порядок группы (то есть количество элементов, составляющих группу).
3. Выбрать криптографически защищенное случайное число k (никогда не используйте одно и то же k дважды, иначе вы раскроете свой ключ).
4. Вычислить (x1, y1) = kg, где g — генератор группы.
В этом примере на шаге 4 мы должны выполнить сложение на кривой, чтобы прийти к точке (x1, y1), которая даст нам r. В общем случае, k — это огромное число (например, имеющее 256 бит), так что эта операция может быть довольно дорогостоящей. Кроме того, если реализация не выполнена должным образом, криптография эллиптической кривой может стать мишенью для атак по сторонним каналам, таких как атак по времени и атаки на кэш. Некоторые эллиптические кривые обладают свойствами, которые допускают реализацию в постоянном времени, что делает их устойчивыми к этим стратегиям.
Эллиптические кривые также появляются в zk-SNARKs (кратких не интерактивных аргументах знания с нулевым разглашением; мы отправимся на охоту за SNARK в другом посте), чтобы обеспечить гомоморфное скрытие. Слово звучит важно, но идея, лежащая в его основе, проста. Предположим, что есть две переменные, x и y, и вы хотите (или вам нужно) узнать x + y. Проблема в том, что вы не знаете их напрямую, но знаете их зашифрованную форму E(x) и E(y). Если у вас есть гомоморфное скрытие, вы можете вычислить E(x + y) = E(x) × E(y), где × — операция над зашифрованными переменными. Таким образом, даже если вы не знаете самих переменных, вы можете выполнять с ними математические операции (и, к счастью, это именно то, что вам нужно). На практике это достигается с помощью двух эллиптических кривых (это называется сопряжением; не все эллиптические кривые настолько общительны или достаточно хорошо ладят с другими). Чтобы быть хорошей парой, нам нужно, чтобы операции выполнялись как можно быстрее (среди прочего). Простым примером является экспоненциальная функция, f:
Если x = 2,303, exp(2,303) ≈ 10, y = 3, exp(3) ≈ 20,09, тогда exp(x + y) = exp(x)exp(y) = 10 × 20,09 = 200,9, что равно exp(5,303) и x + y = 5,303. Конечно, в данном случае очень легко вернуться назад и узнать точные числа x, y и x + y; в случае эллиптических кривых это очень сложно из-за особой структуры группы.
Чтобы иметь возможность работать с эллиптическими кривыми, нам нужно определить операцию, включающую точки на кривой. Мы можем сделать это, используя конструкцию хорды и касательной: имея две точки на кривой, мы можем провести соединяющую их линию; линия пересекает кривую в третьей точке, и мы отражаем её вокруг оси x, чтобы получить сумму (вспомните изображение кривой, определенной над действительными числами). Формулы следующие:
Есть некоторые особые случаи, например, когда мы хотим добавить точку к самой себе (мы называем это "удвоением"). Чтобы все заработало, нам нужно добавить особую точку O, точку на бесконечности. Кривая вместе с операцией образуют конечную циклическую группу. Простыми словами, каждый раз, когда мы добавляем две точки, мы получаем третью, которая принадлежит кривой (она закрывается при выполнении операции). У нас также есть точка идентичности (нулевая точка, P + O), а также каждая точка P имеет обратную P′ такую, что P + P′ = O. Более того, элементы группы могут быть сгенерированы путем многократного добавления точки g (генератора) самой к себе. Другими словами, для P в группе имеется некое k такое, что kg = P. Если нам дано k, мы можем быстро вычислить P, но выполнение операции в обратную сторону (то есть, имея P, найти k) может быть очень сложно (это известно как задача дискретного логарифмирования), и мы использовали эту идею в предыдущем параграфе.
Все эти вычисления выполняются с помощью операций конечного поля Fp. Мы видим, что на каждом шаге сложения мы должны вычислить наклон линии, что включает в себя деление на элементы конечного поля. Это можно переписать как
— мультипликативная инверсия x2 − x1. В более простой форме, b(x2 − x1) ≡ 1 (mod p) (Когда мы пишем a ≡ b (mod p), мы имеем в виду, что существует такое целое число q, что a = pq + b. Это выражение читается, как a соответствует b по модулю p). Вычисление обратных чисел возможно, но стоит гораздо дороже, чем умножение. Существует результат теории чисел, называемый малой теоремой Ферма, который сообщает нам, что
если a и p не имеют общих делителей, отличных от 1 (мы говорим, что a и p взаимно просты). Мы можем записать это по-другому
(мы можем упростить себе задачу и свести b к
). Итак, чтобы получить мультипликативную обратную величину, мы должны выполнить много умножений. (Иногда сделать это гораздо проще. Возьмем p = 5 и попытаемся найти 4^(−1). Мы можем заметить, что 4 × 4 = 16 ≡ 1 (mod 5), поэтому 4^(−1) = 4. Это довольно странно, но мы должны помнить, что операции над конечным полем ведут себя по-другому.) На самом деле, p − 1 определяет верхнюю границу степени n, которую мы должны применить к элементу поля a, чтобы получить его обратную величину, то есть a^n ≡ 1 (mod p). Мы называем наименьший (положительный) показатель n такой, что a^n ≡ 1 (mod p), порядком элемента. Теорема Лагранжа свидетельствует, что n является делителем p − 1. Например, возьмем p = 7, следовательно, p − 1 = 6. Мы видим, что 4^3 = 64 ≡ 1 (mod 7), поэтому 4^2 ≡ 2 (mod 7) — инверсия от 4 (2 × 4 = 8 ≡ 1 (mod 7)). Таким же образом, 2^3 ≡ 1 (mod 7). В случае с 3, 3^6 ≡ 1 (mod 7) и 3^5 ≡ 5 (mod 7), а также 5^6 ≡ 1 (mod 7). Из этого мы видим, что порядки n входят в число делителей p − 1 = 6.
Таким образом, даже если уравнения для сложения точек по эллиптическим кривым выглядят действительно простыми, они требуют большого количества вычислений, и они могут быть дорогостоящими. Если каждый раз, когда мы хотим добавить две точки, нам приходится находить мультипликативную обратную величину по модулю большого простого числа, мы заметим, что операция дорого нам обходится. Есть пара трюков, которые мы можем выполнить, например, преобразовать кривую, чтобы увеличить скорость или избежать некоторых других проблем, таких как атаки по сторонним каналам.
Если вы один из тех, кто не готов платить за поиск обратных величин и хочет сэкономить время, или просто любите скорость в подобных вычислениях, тогда следующий раздел для вас.
Проективные координаты
Мы можем избавить себя от дорогостоящих инверсий, если перейдем из нашего приятного 2-мерного пространства в 3-мерное пространство. Это было введено Мёбиусом и помогает нам также представить свойство точки на бесконечности. Мы можем перенести четыре точки с нашей эллиптической кривой (x, y) в точки на проекции (X, Y, Z) следующим образом (x, y) → (X = x, Y = y, Z = 1) и O → (0, 1, 0). Мы можем вернуться назад, используя преобразование (X, Y, Z) → (x = X/Z, y = Y/Z), за исключением точки на бесконечности там, где она плохо определена. Мы можем визуализировать этот процесс с помощью следующего рисунка, где мы берем три точки из эллиптической кривой и преобразуем их в трехмерные.
Мы можем думать об этом как о преобразовании наших двумерных точек в линии, проходящие через начало координат в трехмерном пространстве. Например, двумерная точка (x1, y1) преобразуется в линию (μx1, μy1, μ), где μ — элемент поля. Таким образом, две точки P1 = (X1, Y1, Z1) и P2 = (X2, Y2, Z2) одинаковы в двумерном пространстве (точнее, конгруэнтны), если мы можем найти такой η, что (ηX1, ηY1, ηZ1) = (X2, Y2, Z2). Эти линии не проходят через начальную точку (0, 0, 0). Обычно точки в проективном пространстве записываются как (X : Y : Z) вместо (X, Y, Z). На нашем рисунке точка A (желтая) сопоставляется с точкой D (красная над ней). Все точки, которые лежат на одной прямой, проходящей через начало координат и D (розовая пунктирная линия), считаются эквивалентными D. Аналогично, точка B (синяя) сопоставляется с точкой F (светло-синяя), а все точки над светло-зеленой пунктирной линией (кроме начала координат) эквивалентны F. Когда мы добавляем точки в это пространство, компоненты (X, Y, Z) будут меняться, но мы можем вернуться к точке, принадлежащей кривой, просто проследив наши шаги до Z = 1 вдоль линии, проходящей через начало координат. Зачем идти так далеко? Вскоре мы увидим, что мы избегаем инверсий на каждом шаге сложения и делаем только одну инверсию во время нахождения точки в двумерном пространстве (например, когда нам нужно найти r = x1 в ECDSA). Конечно, нам это ничего не даст, если мы должны вычислить P = 2g; но если нам нужно вычислить P = kg, где k порядка 256 бит, мы сэкономили бы на множестве дорогих инверсий.
Внесем подстановки в уравнение эллиптической кривой
Умножим на Z^3 и получим следующее уравнение
Если мы хотим сложить P и Q, чтобы получить R = P + Q на проекции, мы можем использовать следующие формулы:
Это выглядит более сложным, чем простые формулы для 2-мерного (2-d) пространства. Однако нам не нужно вычислять никаких обратных чисел! Чтобы получить сумму, мы должны выполнить 12 умножений и 2 возведения в квадрат. В 2-d у нас есть 2 умножения, одно возведение в квадрат и одна инверсия. Инверсии могут быть в 20 или более раз дороже, чем умножения, поэтому мы сэкономили по крайней мере 10 умножений (некоторые авторы говорят, что инверсии обходятся примерно в 80 раз дороже, чем умножения).
Некоторые кривые могут вычисляться даже быстрее. Если x^3 + ax + b имеет решение в Fp, мы можем работать с эквивалентной кривой Якоби v^2 = a′u^4 + du^2 + 1, где a′ и d зависят от решения. Мы можем отобразить кривую (u, v) в 3-d пространстве (U, V, W), используя u = U/W и v=V/(W^2) и получить следующее уравнение
Если мы захотим сложить P3 = P1 + P2 в данных координатах, мы получим:
Это позволяет нам еще больше снизить затраты на сложение до 6 умножений и 4 возведений в квадрат. Другими моделями с быстрой реализацией являются кривые Эдвардса и кривые Монтгомери, которые имеют одни из самых быстрых реализаций.
Кривые Монтгомери удовлетворяют следующему уравнению
где B(A^2 − 4) ≠ 0. Это выражение может быть приведено к форме Вейерштрасса путем некоторого преобразования. Если мы возьмем (x, y) и перенесём в (x′, y′), зная, что (x, y) → (x/B + A/3B, y/B), мы получим
Однако преобразование кривой Вейерштрасса в кривую Монтгомери не всегда возможно. Порядок группы должен быть кратен 4 и уравнение x^3 + ax + b = 0 должно иметь решение.
Кривые Монтгомери также могут быть связаны со скрученными кривыми Эдвардса, которые подчиняются следующему уравнению
Параметры соотносятся через A = 2(a + d)/(a − d) и B = 4/(a − d). Мы говорим, что эти две кривые бирационально эквивалентны. Например, хорошо известная кривая Эдвардса 25519 , в которой p = 2^255 − 19 — (бирационально) эквивалентна кривой Монтгомери
Кривые Монтгомери обладают некоторыми интересными свойствами, которые поддаются реализации с постоянным временем. Мы можем работать в проективных координатах, просто используя компонент x с переносом x = X/Z. Удвоение точки принимает простую форму:
Скрученные кривые Эдвардса также имеют свои преимущества. Выражения для сложения и удвоения точек одинаковы. Имея P1 = (x1, y1), P2 = (x2, y2), мы получаем
Если мы примем x1 = x2 и y1 = y2, мы получим выражение для удвоения точки. Существует несколько альтернатив для ускорения вычислений, таких как проективные, инвертированные или расширенные координаты.
Существуют и некоторые другие приемы для добавления и умножения точек над эллиптическими кривыми, такие как техника Галланта, Ламберта и Ванстоуна (GLV) и обобщенная Гэлбрейтом, Лином и Скоттом (GLS).
Заключение
Эллиптические кривые получили признание в криптографии, потому что они обеспечивают хороший уровень безопасности при короткой длине ключа и позволяют выполнять более быструю реализацию, чем другие методы, такие как RSA. Это позволяет смартфонам и другим менее мощным устройствам выполнять криптографические операции быстро и надежно.
Используя метод хорды и касательной, мы можем генерировать конечные циклические группы; на практике нас обычно интересует вычисление kg, где k — целое число, а g — точка эллиптической кривой. Главный недостаток заключается в том, что нам нужно найти мультипликативные инверсии элементов поля, что включают в себя множество умножений.
Мы можем повысить скорость этих вычислений, выполнив преобразования между кривыми (например, приведя кривую Вейерштрасса к форме Монтгомери) и используя проективные координаты. Таким образом, мы избегаем вычисления мультипликативных инверсий на каждом шаге за счет нескольких дополнительных умножений (эти дополнительные затраты обычно незначительны по сравнению с общей стоимостью инверсии). Существуют также более продвинутые методы, позволяющие нам прыгать из одной точки в другую, очень удаленную, например, GLS.