Исследование эллиптических кривых пар

Автор: Vitalik Buterin

Исходное название: 《Изучение парных эллиптических кривых》

Дата публикации: 14 января 2017 года

Многочисленные основы криптографии, такие как «детерминированная пороговая подпись» (deterministic threshold signature, временный перевод), zk-SNARKs и другие более простые формы нулевых доказательств, имеют за собой одну из ключевых оригинальных моделей — парные эллиптические кривые. Эллиптические кривые широко используются в криптографии, цифровых подписях и других приложениях на протяжении более тридцати лет, «парные эллиптические кривые (EC pairings)» (или билинейные отображения) — это новое изобретение, основанное на них, которое ввело криптографическое умножение и значительно увеличило возможности соглашений на основе эллиптических кривых. Эта статья подробно расскажет о парных эллиптических кривых и кратко объяснит, как они работают.

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

Сама по себе эллиптическая кривая уже является темой, которую трудно понять, но эта статья в большинстве случаев будет предполагать, что у вас есть некоторое представление о том, как она работает. Если у вас нет базового понимания, я рекомендую эту статью как вводную. В общем, эллиптические кривые работают с математическими объектами, называемыми «точками (points)», проще говоря, это точки на двумерной плоскости (x, y), а также некоторыми специальными формулами для сложения и вычитания (например, вычисление R = P + Q). Вы также можете умножать точку на целое число (например, P * n = P + P + … + P, хотя для больших n существует гораздо более быстрый алгоритм).

Вот как выглядит сложение точек на графике

Кроме того, есть особая точка, называемая «точка на бесконечности» (O), которая в правилах операций с точками служит нулевым элементом, то есть для всех точек выполняется P + O = P. Кривая также имеет характеристику, называемую «порядком (order)», то есть существует положительное целое число n, для всех P, такое что P * n = O (конечно, P * (n + 1) = P, P * ((7*n) + 5) = P * 5 и так далее). Также есть заранее согласованная «генерирующая точка (generator point) G», которая выбирается в качестве единичного элемента сложения, представляющего число 1. Теоретически любая точка на кривой может быть использована как генератор, важно, что G выбрана единообразно.

Парные эллиптические кривые позволяют вам проверять более сложные уравнения: например, если P = G * p, Q = G * q, R = G * r, когда вы хотите проверить, выполняется ли p * q = r, вам нужны только координаты трех точек P, Q и R в качестве входных данных. Это может показаться нарушением самой основной безопасности эллиптических кривых, потому что на первый взгляд, если известны координаты точки P, это раскрывает значение p. Но на самом деле риск утечки очень ограничен — точнее, проблема с определением Диффи-Хеллмана легко решается, но вычислительная версия по-прежнему остается «вычислительно неосуществимой (computationally infeasible)». По крайней мере, сложность примерно такая же, как если бы вы не знали это значение.

Третий способ понять «парные эллиптические кривые», возможно, является наиболее вдохновляющим в большинстве контекстов, которые мы обсуждаем: если вы рассматриваете точки на эллиптической кривой как одностороннюю криптографическую функцию (то есть encrypt(p) = p * G = P), то в отличие от традиционных математических принципов эллиптических кривых, которые позволяют вам проверять линейные ограничения между переменными (например, P = G * p, Q = G * q, R = G * r, проверка 5 * P + 7 * Q = 11 * R на самом деле проверяет 5 * p + 7 * q = 11 * r), парные эллиптические кривые позволяют вам проверять квадратичные ограничения (проверка e(P, Q) * e(G, G * 5) = 1 на самом деле проверяет p * q + 5 = 0). Возможность проверки квадратичных ограничений достаточно для того, чтобы мы могли делать такие интересные приложения, как детерминированные пороговые подписи, QAP (квадратичные арифметические программы, форма нулевых доказательств) и так далее.

Теперь вопрос: что же такое оператор e(P, Q), который мы ввели выше? Это и есть набор «пар». Математики иногда называют его «билинейным отображением», «билинейность» здесь в основном означает, что оно удовлетворяет следующим условиям:

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + S, Q) = e(P, Q) * e(S, Q)

Обратите внимание, что здесь + и * могут быть любыми операторами; когда вы создаете новый класс математических объектов, абстрактная алгебра не заботится о том, как + и * «определены», пока они согласуются с привычными нам операциями, такими как a + b = b + a, (a * b) * c = a * (b * c), (a * c) + (b * c) = (a + b) * c.

Если сейчас P, Q, R, S просто числа, то функцию пар можно легко построить: мы можем определить e(x, y) = 2^(xy). Тогда мы увидим:

e(3, 4 + 5) = 2^(3 * 9) = 2²⁷
e(3, 4) * e(3, 5) = 2^(3 * 4) * 2^(3 * 5) = 2¹² * 2¹⁵ = 2²⁷

Это действительно билинейно!

Однако такие простые пары не подходят для использования в криптографии, потому что анализ чисто работающих с целыми числами математических объектов чрезвычайно прост; свойства целых чисел делают деление, логарифмы и многие другие операции легкими. У целых чисел также нет концепции «открытого ключа» или «односторонней функции». Более того, описанные выше пары обратимы: зная x и e(x, y), можно сделать деление и логарифм, чтобы вычислить y. Мы хотим, чтобы математическая структура была как можно ближе к «черному ящику»: вы можете выполнять сложение, вычитание, умножение и деление, но только это. В этот момент на помощь приходят эллиптические кривые и парные эллиптические кривые.

Люди обнаружили, что действительно можно спроектировать билинейное отображение на точках эллиптической кривой — то есть, когда входными данными являются две точки P и Q на эллиптической кривой, создается функция e(P, Q), которая отображает в элемент F_p¹² (по крайней мере, в этом конкретном случае это достаточно, и этот стандарт будет различаться в зависимости от деталей кривой, о чем будет упомянуто позже), но математика, лежащая в основе этого, действительно очень сложна.

Во-первых, давайте введем понятия простого поля (prime fields) и расширенного поля (extension fields). Кривая на рисунке выше хотя и красива, но она выглядит так только при условии, что уравнение кривой определено на обычных действительных числах. Если бы мы действительно использовали действительные числа в криптографии, то вы могли бы «вернуться назад» с помощью логарифмов, и все это стало бы бесполезным, не говоря уже о том, что пространство, необходимое для хранения действительных чисел, может быть бесконечно большим. Поэтому мы используем числа в простом поле.

Простое поле состоит из множества чисел 0, 1, 2, …, (p−1), где p — это простое число, а операции определяются следующим образом:

a + b: (a + b) % p
a * b: (a * b) % p
a - b: (a - b) % p
a / b: (a * b^(p-2)) % p

В основном все операции выполняются по модулю p (здесь есть введение в модульную арифметику). Деление является исключением. Обычно 3/2 не является целым числом, но мы хотим обрабатывать только целые числа, поэтому мы ищем целое число x, такое что x * 2 = 3, и здесь * конечно же относится к определенному выше модульному умножению. К счастью, малый теорема Ферма позволяет определить этот показатель, но есть и более быстрый способ, который заключается в использовании расширенного алгоритма Евклида. Предположим, p = 7, вот несколько примеров:

2 + 3 = 5 % 7 = 5
4 + 6 = 10 % 7 = 3
2 - 5 = -3 % 7 = 4
6 * 3 = 18 % 7 = 4
3 / 2 = (3 * 2^5) % 7 = 5
5 * 2 = 10 % 7 = 3

Если вы попробуете выполнять такие операции, вы обнаружите, что они последовательны и удовлетворяют всем обычным правилам. Последние два примера показывают, что (a / b) * b = a, и вы также можете заметить, что (a + b) + c = a + (b + c), (a + b) * c = a * c + b * c, и другие алгебраические равенства, которые вы знали и любили в школе, также будут работать. На практике используемые эллиптические кривые, точки и уравнения обычно вычисляются в простом поле.

Теперь давайте поговорим о расширенных полях. Вы, возможно, уже видели расширенные поля, наиболее распространенный пример в учебниках по математике — это комплексные числа, которые образуются путем добавления нового элемента sqrt(-1) = i к действительным числам. Проще говоря, расширенное поле — это «изобретение» нового элемента на основе уже существующего поля и определение отношений между этим новым элементом и существующими элементами (в приведенном примере это i² + 1 = 0); это соотношение не может быть выполнено существующими числами, и добавление этого нового элемента к «всем линейным комбинациям старых элементов» создает новое множество.

Мы также можем расширить простое поле; например, добавив i в простое поле по модулю 7, мы получаем

(2 + 3i) + (4 + 2i) = 6 + 5i
(5 + 2i) + 3 = 1 + 2i
(6 + 2i) * 2 = 5 + 4i
4i * (2 + i) = 3 + i

Последнее равенство может быть трудным для понимания; на самом деле, первый шаг этого равенства — это сначала распределить умножение слева, получая 4i * 2 + 4i * i, что дает 8i - 4. Поскольку мы выполняем операции в модуле 7, это число становится i + 3. Что касается деления, то:

a / b : (a * b^(p²-2)) % p

Здесь показатель в теореме Ферма изменился с p на p², и, конечно, можно использовать расширенный алгоритм Евклида для более эффективных вычислений. Поскольку для любого элемента x в поле выполняется x^(p² − 1) = 1, мы называем (p² − 1) «порядком мультипликативной группы в поле».

Для действительного поля основная теорема алгебры гарантирует его квадратичное расширение (quadratic extension): комплексные числа, являются полными (примечание переводчика: должно быть алгебраически замкнутыми, действительное поле также имеет полноту, но может быть расширено) — это поле не может быть расширено, потому что все возможные новые элементы j и математические отношения, которые должны быть выполнены между существующими комплексными числами (строго говоря, определяемыми полиномами), уже удовлетворяются элементами в поле. Но в простом поле такой проблемы нет, мы можем провести кубическое расширение (cubic extension) (новый элемент w и соотношение с существующими элементами задается кубическим полиномом, поэтому 1, w, w² являются линейно независимыми), более высокие расширения и даже расширения расширений и так далее. Эллиптические кривые основаны на этих модульных вычислениях.

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

Вернемся к парным эллиптическим кривым. Парные эллиптические кривые (то, что мы обсуждаем, — это только один из видов пар, но логика пар схожа) — это отображение G2 × G1 → Gt, где:

• G1 — это эллиптическая кривая, точки на которой удовлетворяют уравнению вида y² = x³ + b, и координаты точек x, y являются элементами F_p (то есть они просто обычные числа, но арифметические операции будут выполняться по модулю некоторого простого числа).
• G2 также является эллиптической кривой, которая также удовлетворяет уравнению G1, но элементы G2 имеют координаты x, y, которые являются элементами F_p¹² (это те комплексные числа, о которых мы говорили; мы определяем волшебное число w, которое удовлетворяет 12-му полиному w¹² − 18 w⁶ + 82 = 0).
• Gt — это множество, образованное результатами операций эллиптической кривой. В обсуждаемой нами кривой Gt является F_p¹² (так же, как и G2, использует те же комплексные числа).

Основное требование, которое должно быть выполнено, — это билинейность, в этом контексте это означает:

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + Q, R) = e(P, R) * e(Q, R)

(примечание переводчика: здесь билинейность на самом деле является «билинейностью над целыми числами (bilinearity over ℤ)», просто потому, что точки на эллиптической кривой, о которых идет речь, являются целыми точками, и определения умножения и сложения — это целочисленные операции, выполненные с последующим взятием по модулю, что уже удовлетворяет некоторым линейным свойствам).

Выбор функции пар также подчиняется двум важным критериям:

• Операции должны быть достаточно эффективными (например, мы можем просто взять дискретные логарифмы всех точек и перемножить их, как простой метод пар, но стоимость вычислений, необходимых для этого, так же сложна, как и для взлома эллиптической криптографии, поэтому это не считается).
• Неперерабатываемость (вы, конечно, можете просто определить e(P, Q) = 1, но это не очень полезная пара).

Так как же нам это сделать?

Математика, стоящая за работой функции пар, очень сложна и требует некоторых продвинутых алгебраических знаний, превышающих то, что мы видели до сих пор, но я постараюсь объяснить в общих чертах. Во-первых, нам нужно определить концепцию «делителя (divisor)», которая по сути является другим способом представления функций, действующих на эллиптической кривой. Делитель функции в основном вычисляет, сколько у функции нулевых точек и точек, принимающих бесконечные значения. Чтобы проиллюстрировать это, давайте рассмотрим несколько примеров. Выберем точку P = (Px, Py) и рассмотрим следующую функцию:

f(x, y) = x − P_x

Ее делитель будет [P] + [−P] − 2 * [O] (здесь квадратные скобки используются для обозначения множества точек, которые появляются в нулевых точках функции и точках, принимающих бесконечные значения, а не самой точки; [P] + [Q] и [P + Q] не одно и то же). Причины следующие:

• Эта функция равна нулю в точке P, потому что x принимает значение Px, поэтому x − Px = 0.
• Эта функция равна нулю в точке −P, потому что x-координаты −P и P совпадают.
• Эта функция стремится к бесконечности, когда x стремится к бесконечности, поэтому мы говорим, что эта функция принимает бесконечное значение в точке O. Чтобы вычислить эту точку на бесконечности, нужно считать дважды, поэтому O умножается на множитель -2 (отрицательный знак, потому что это точка на бесконечности, а не нулевая точка, 2 — потому что она считается дважды).

Приблизительная причина вычисления такова: поскольку уравнение этой кривой x³ = y² + b, когда x увеличивается, чтобы y² достигло соответствующего масштаба, y должно расти примерно в 1,5 раза быстрее, чем x. Поэтому, если линейная функция содержит только x, то множитель для бесконечности будет 2, но если она включает y, то множитель должен быть 3.

Теперь рассмотрим функцию линии:

ax + by + c = 0

где a, b, c выбраны так, чтобы линия проходила через точки P и Q. В соответствии с тем, как работает сложение эллиптических кривых, она также должна проходить через точку −P−Q. Поскольку она стремится к бесконечности, это будет зависеть как от x, так и от y, поэтому делитель будет [P] + [Q] + [−P−Q] − 3 * [O].

Мы знаем, что все «рациональные функции» (то есть функции, определяемые конечным числом операций сложения, вычитания, умножения и деления над координатами точек) уникально соответствуют какому-то делителю, максимум с умножением на некоторую константу (то есть, если две функции F и G имеют одинаковый делитель, то обязательно существует константа k, такая что F = G * k).

Для любых двух функций F и G, делитель (F * G) равен сумме делителей F и G (в учебниках по математике вы увидите, что (F * G) = (F) + (G)), поэтому, например, f(x, y) = P_x − x, тогда (f³) = 3 * [P] + 3 * [−P] − 6 * [O]; P и −P считаются трижды, потому что в определенном математическом смысле f³ будет «трижды быстро» стремиться к 0.

Обратите внимание на теорему, которая говорит, что если вы уберете квадратные скобки у какого-либо делителя, результат обязательно будет O (операция [P] + [Q] + [−P−Q] − 3 * [O] приведет к P + Q − P − Q − 3 * O = O), и любой делитель с этим свойством будет делителем этой функции.

Теперь мы можем начать рассматривать парные Тейта. Рассмотрим следующие функции, определенные через делители:

• (F_P) = n * [P] − n * [O], где n — это порядок G1, то есть для всех P, n * P = O
• (F_Q) = n * [Q] − n * [O]
• (g) = [P + Q] − [P] − [Q] + [O]

Теперь давайте посмотрим на произведение FP * FQ * g^n. Его делитель будет:

n * [P] − n * [O] + n * [Q] − n * [O] + n * [P + Q] − n * [P] − n * [Q] + n * [O]

Упрощая, мы получаем чистый:

n * [P + Q] − n * [O]

Обратите внимание, что формат этого делителя совпадает с делителями FP и FQ. Таким образом, FP * FQ * g^n = F_(P + Q).

Теперь проведем операцию, называемую «финальным возведением в степень (final exponentiation)», возведя результат предыдущих вычислений (FP, FQ и так далее) в степень z = (p¹² − 1) / n, где p¹² − 1 — это порядок мультипликативной группы в Fp¹² (другими словами, для всех x ϵ Fp¹², x^(p¹² − 1) = 1). Обратите внимание, что если вы примените этот показатель к любому результату, который уже является n-й степенью, вы получите (p¹² − 1)-ю степень некоторого элемента, и результат станет равным 1. Таким образом, после последнего шага возведения в степень g^n исчезнет, и мы получим FP^z * FQ^z = F_(P + Q)^z. Таким образом, мы получили часть свойства билинейности.

Теперь, если вы хотите построить функцию, которая будет билинейной по обоим параметрам, вам понадобятся более сложные математические конструкции, и вам нужно будет не только вычислить FP, но и вычислить делитель FP, и продолжать, чтобы получить полное парное Тейта. Чтобы доказать больше выводов, вам нужно понять некоторые концепции, такие как «линейная эквивалентность (linear equivalence)» и взаимность Вейля (Weil reciprocity). Подробности этих концепций можно найти здесь и здесь.

А здесь реализована модификация парного Тейта — Оптимальное парное Ate. В этом коде также реализован расчет F_p с использованием алгоритма Миллера.

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

Каждая эллиптическая кривая имеет значение, называемое embedding degree — минимальное целое число k, такое что p^k − 1 является кратным n (p — это простое число, используемое в поле, а n — это порядок кривой). В упомянутом выше поле k = 12, в традиционной эллиптической криптографии (не учитывая пары) используемые поля обычно имеют очень большое значение embedding degree, настолько большое, что вычисление пар становится вычислительно неосуществимым. Однако, когда мы не обращаем на это внимания, мы можем построить поле с k = 4 или даже k = 1.

Когда k = 1, «проблема дискретного логарифма» на эллиптической кривой (в случае, когда известна только точка P = G * p, вычислить значение p; то есть то, что нужно решить при «взломе» приватного ключа эллиптической кривой) может свестись к относительно простой задаче в F_p (этот метод называется атакой MOV); использование эллиптической кривой с embedding degree, равным или превышающим 12, гарантирует, что такая редукция невозможна, или что редуцированная задача будет сложной как минимум так же, как и задача нахождения приватного ключа из открытого ключа «нормальным» способом. В настоящее время все стандартные параметры кривых тщательно проверены и не подвержены этому проблеме.