Что такое эллиптическая кривая

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

где $a,b \in <<\mathbb>>$ – вещественные числа. Эта форма представления эллиптической кривой называется формой Вейерштрасса.

На кривой определён инвариант:

Пусть $x_<1>$ , $x_<2>$ и $x_<3>$ – корни уравнения $x^3 + a x + b = 0$ . Определим дискриминант $D$ в виде:

Рассмотрим различные значения дискриминанта $D$ и соответствующие им кривые, которые представлены на рисунках 16.1a, 16.1b, 16.1c.

При $D>0$ график эллиптической кривой состоит из двух частей (см. рис. 16.1a). Прямая, проходящая через точки $P(x_1; y_1)$ и $Q(x_2; y_2)$ , обязательно пересечёт вторую часть кривой в точке с координатами $(x_3; \widetilde_3)$ , отображением которой является точка $R(x_3; y_3)$ , где $y_3 = — \widetilde_3$ . Любые точки на кривой при $D>0$ являются элементами группы по сложению.
Если $D=0$ , то левая и правая части касаются в одной точке (см. рис. 16.1b). Эти кривые называются сингулярными и не рассматриваются.
Если $D<0$ , то записанное выше уравнение [Wer] описывает одну кривую, представленную на рис. 16.1c.

Рассмотрим операцию сложения точек на эллиптической кривой при $D \ne 0$ (другие кривые не рассматриваются).

Пусть точки $P(x_1; y_1)$ и $Q(x_2; y_2)$ принадлежат эллиптической кривой (рис. 16.1a). Определим операцию сложения точек

Eсли $P \neq Q$ , то точка $R$ определяется как отображение (инвертированная $y$ -координата) точки, полученной пересечением эллиптической кривой и прямой $PQ$ . Совместно решая уравнения кривой и прямой, можно найти координаты их точки пересечения. Зная координаты точки пересечения, можно вычислить и координаты искомой точки $R = (x_3; y_3)$ , которые будут равны:

Все точки эллиптической кривой, а также точка $O$ образуют коммутативную группу $<<\mathbb>>(<<\mathbb>>)$ относительно введённой операции сложения, то есть выполняются законы коммутативной группы:

сумма точек $P + Q$ лежит на эллиптической кривой;
существует нулевой элемент – это точка $O$ на бесконечности:

Сложение точки с самой собой $d$ раз обозначим как умножение точки на число $d$ :

16.7.2. Эллиптические кривые над конечным полем

Эллиптические кривые можно строить не только над полем рациональных чисел, но и над другими полями. То есть координатами точек могут выступать не только числа, принадлежащие полю рациональных чисел $<<\mathbb>>$ , но и элементы поля комплексных чисел $\mathbb$ или конечного поля $<<\mathbb>>$ . В криптографии нашли своё применение эллиптические кривые именно над конечными полями.

Далее будем рассматривать эллиптические кривые над конечным полем, являющимся кольцом вычетов по модулю нечётного простого числа $p$ (дискриминант не равен 0):

Возможна также более компактная запись:

y^2 = x^3 + a x + b \mod p.$$

Точкой эллиптической кривой является пара чисел

удовлетворяющая уравнению эллиптической кривой, определённой над конечным полем $<<\mathbb>>_p$ .

Операцию сложения двух точек $P = (x_1; y_1)$ и $Q = (x_2; y_2)$ определим точно так же, как и в случае кривой над полем вещественных чисел, описанном выше.

>>_p$ , складываются по правилу:

Мы рассматриваем эллиптические кривые над конечным полем $<<\mathbb>>_p$ , где $p > 3$ – простое число, элементы $<<\mathbb>>_p$ – целые числа $\<0, 1, 2, \ldots, p-1\>$ , то есть исследуем следующее уравнение двух переменных $x, y \in <<\mathbb>>_p$ :

где $a, b \in <<\mathbb>>_p$ – некоторые константы.

Как и в случае выше, множество точек над конечным полем $<<\mathbb>>_p$ , удовлетворяющих уравнению эллиптической кривой, вместе с точкой в бесконечности $O$ образуют конечную группу $<<\mathbb>>(<<\mathbb>>_p)$ относительно описанного закона сложения:

y^2 = x^3 + a x + b \mod p \right\>. $$

По теореме Хассе порядок группы точек $|<<\mathbb>>(<<\mathbb>>_p)|$ оценивается как

или, в другой записи,

16.7.3. Примеры группы точек

Пример 1

Пусть эллиптическая кривая задана уравнением

y^2 = x^3 + 1 \mod 7. $$

Найдём все решения этого уравнения, а также количество точек $|<<\mathbb>>(<<\mathbb>>_p)|$ на этой эллиптической кривой. Для нахождения решений уравнения составим следующую таблицу:

$x$	0	1	2	3	4	5	6
$y^2$	1	2	2	0	2	0	0
$y_1$	1	3	3	0	3	0	0
$y_2 = — y_1 \mod p$	6	4	4	4

Выпишем все точки, принадлежащие данной эллиптической кривой $<<\mathbb>>(<<\mathbb>>_p)$ :

Проверим выполнение неравенства Хассе:

Следовательно, неравенство Хассе выполняется.

Минимальное натуральное число $s$ такое, что

$$ \underbrace

_ ~~\equiv s P = O, $$~~

будем называть порядком точки $P$ .

Пример 2

Группа точек эллиптической кривой

состоит из точек:

Порядок группы точек по теореме Хассе:

Порядки возможных подгрупп: 2, 3, 4, 6 (все возможные делители порядка группы 12).

Найдём порядок точки $A = (-8; 7)$ . Так как возможные порядки подгрупп (и всех точек группы) известны, нужно проверить только их.

Найденный порядок точки $A = (-8; 7)$ равен 12, следовательно, она является генератором всей группы.

В таблице [tab:elliptic-group-sample] найдены порядки точек и циклические подгруппы группы точек $<<\mathbb>>(<<\mathbb>>_p)$ такой же эллиптической кривой

Группа циклическая, число генераторов:

верхний индекс обозначает порядок подгруппы.

16.7.4. Эллиптические кривые в скрученной форме Эдвардса

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

Примеры кривых, заданных этим уравнениям при различных значениях $d$ , приведены на рис. 16.2. Данное кривые в указанном представлении называются эллиптическими кривыми в скрученной форме Эдвардса (англ. Twisted Edwards Curves , [102]).

Рис. 16.2 — Эллиптические кривые в скрученной форме Эдвардса при значениях (от внешней фигуры ко внутренней) $d = +0<,>9, -\sqrt<8>, -300$

Для данной формы формулы сложения точек задаются одним и тем же способом для любых случаев. В этом важное отличие от формы Вейерштрасса, для которой есть частный случай сложения точки самой с собой (с отдельной формулой вычисления угла наклона касательной). Формулы сложения выглядят так:

При переходе к построению кривых над конечным полем, оказывается, что не все кривые, представимые в форме Вейерштрасса, могут быть представлены в скрученной форме Эдвардса. Для этого необходимо, чтобы порядок кривой $\|E\|$ делился на $4$ . Однако если такие кривые использовать для криптографических целей, это даёт значимые преимущества:

меньшая трудоёмкость операций сложения точек;

отсутствие частных случаев для формул сложения (усложнение атак по сторонним каналам с различением времени);

16.7.5. Конвертация из скрученной формы Эдвардса в форму Вейерштрасса

Кривая в скрученной форме Эдвардса:

Кривая в форме Вейерштрасса:

Зная коэффициенты $d$ и $e$ кривой в скрученной форме Эдвардса можно найти коэффициенты $a$ и $b$ эквивалентной кривой в форме Вейерштрасса:

И определить правила преобразования координат $(u, v)$ и $(x, y)$ между двумя кривыми:

Нахождение коэффициентов для кривой в скрученной форме Эдвардса по эквивалентной в форме Вейерштрасса является более сложной и нетривиальной задачей, включающей нахождение корней кубического уравнения $x^ <3>+ ax + b = 0 \mod p$ . Кроме того, как было сказано ранее, не все кривые в форме Вейерштрасса имеют эквивалентную кривую в скрученной форме Эдвардса.

16.7.6. Пример группы точек кривой в скрученной форме Эдвардса

Кривая $x^2+y^2=1+6x^2y^2 \mod 11$ .

Все точки кривой:

Нейтральным элементом является точка $(0; 1)$ .

Данная группа точек является циклической группой, её генератором выступает точка $(2; 5)$ (рис. 16.3):

Рис. 16.3 — Группа точек эллиптической кривой в скрученной форме Эдвардса $x^2+y^2=1+6x^2y^2 \mod 11$

Данная группа изоморфна группе вычетов по сложению $<<\mathbb>>_<12>$ . Можно удостовериться, что сложение двух точек $P (6; 9)$ и $Q(10; 0)$ будет соответствовать результату сложения элементов «2» и «3» в группе $<<\mathbb>>_<12>$ :

Группа не имеет эквивалентной группы точек эллиптической кривой в форме Вейерштрасса над конечным полем $<<\mathbb>>_<11>$ . Группа точек соответствующей кривой $y^2 = x^3 + 6 \bmod 11$ имеет только 11 элементов в группе.

Вступление

Эллиптические кривые (EC) получили широкое признание в качестве инструментов для криптографии. Они предлагают ряд преимуществ по сравнению с другими методами, такими как RSA, обеспечивая одинаковые уровни безопасности с более короткими ключами (например, 228-битные ключи в криптографии EC так же хороши, как 2300-битовые ключи RSA). Это преимущество, поскольку все больше и больше криптографии выполняется на смартфонах, которые менее мощны, чем компьютеры. Это кривые, определяемые уравнением

над любым полем (например, полем действительных чисел). Их форма зависит от a и b, но более или менее они выглядят как на следующем рисунке:

В криптографии нас не интересуют кривые, определенные над действительными числами. Мы работаем с кривыми над некоторым конечным полем Fp (т.е. множеством с конечным количеством элементов, таких как 53, 101 или 2^(255)-19), потому что это дает нам математическую структуру ( конечную группу ), которая очень удобна. Кривая выглядит как разбросанные без четкого рисунка точки на конечном поле:

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

Вычислить E=hash(message), где hash — надежная хэш-функция .

Принять Z равным n крайним левым битам E, где n — порядок группы (т.е. количество элементов, составляющих группу).

Выбрать криптографически защищенное случайное число k (никогда не используйте одно и то же k дважды, иначе вы раскроете свой ключ).

Вычислить (x1, y1) = kg, где g — генератор группы.

Пусть r=x1.

Вычислить

где sk — секретный ключ.

7. Подпись — это пара (r, s).

В этом примере на шаге 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, но делать операцию наоборот (то есть, учитывая 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. Мы видим, что ⁴³ = 64 ≡ 1 (mod 7), поэтому ⁴² ≡ 2 (mod 7) — инверсия от 4 (2×4 = 8≡1 (mod 7)). Таким же образом, ²³ ≡ 1 (mod 7). В случае с 3, ³⁶≡1 (mod 7) и ³⁵≡5 (mod 7), а также ⁵⁶≡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, 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) будут изменяться, но мы можем вернуться к точке, принадлежащей кривой, просто проследив наши шаги к Z = 1 вдоль линии, проходящей через начало координат. Зачем идти так далеко? В скором времени мы увидим, что мы избегаем инверсий на каждом шаге добавления и делаем только одну инверсию при нахождении точки в двумерном пространстве (например, когда нам нужно найти r = x1 в ECDSA). Конечно, нам это ничего не даст, если мы должны вычислить P = 2g; но если нам нужно вычислить P = kg, где k порядка 256 бит, мы сэкономили бы на множестве дорогостоящих инверсий. Z) будут изменяться, но мы можем вернуться к точке, принадлежащей кривой, просто проследив наши шаги к Z = 1 вдоль линии, проходящей через начало координат. Зачем идти так далеко? В скором времени мы увидим, что мы избегаем инверсий на каждом шаге добавления и делаем только одну инверсию при нахождении точки в двумерном пространстве (например, когда нам нужно найти r = x1 в ECDSA). Конечно, нам это ничего не даст, если мы должны вычислить P = 2g; но если нам нужно вычислить P = kg, где k порядка 256 бит, мы сэкономили бы на множестве дорогостоящих инверсий. что мы избегаем инверсий на каждом шаге сложения и делаем только одну инверсию при нахождении точки в двумерном пространстве (например, когда нам нужно найти r = x1 в ECDSA). Конечно, нам это ничего не даст, если мы должны вычислить P = 2g; но если нам нужно вычислить P = kg, где k порядка 256 бит, мы сэкономили бы на множестве дорогостоящих инверсий. что мы избегаем инверсий на каждом шаге сложения и делаем только одну инверсию при нахождении точки в двумерном пространстве (например, когда нам нужно найти r = x1 в ECDSA). Конечно, нам это ничего не даст, если мы должны вычислить P = 2g; но если нам нужно вычислить P = kg, где k порядка 256 бит, мы сэкономили бы на множестве дорогостоящих инверсий.

Эллиптическая кривая

y 2 + a₁xy + a₃y = x 3 + a₂x 2 + a₄x + a₆.

Содержание

Эллиптические кривые над действительными числами [ ]

Считаем, что характеристика поля — не 2 и 3. Тогда эллиптическая кривая — y 2 = x 3 + a x + b <\displaystyle y^<2>=x^<3>+ax+b> ,

не должен быть равен нулю.

Если кривая не имеет особых точек, то её график имеет две части, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.

Групповой закон [ ]

Описанная группа может быть описана и алгебраически. Пусть дана кривая y² = x³ − px − q над полем K (чья характеристика не равна ни 2, ни 3), и точки P = (x_P, y_P) и Q = (x_Q, y_Q) на кривой, допустим, что x_P ≠ x_Q. Пусть s = (y_P − y_Q)/(x_P − x_Q); так как K — поле, то s чётко определено. Тогда мы можем определить R = P + Q = (x_R, y_R) следующим образом:

Если x_P = x_Q, то у нас два варианта: если y_P = −y_Q, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её по оси Ox. Если y_P = y_Q ≠ 0, то R = P + P = 2P = (x_R, y_R) определяется так:

Если y_P = y_Q = 0, то P + P = 0.

Эллиптические кривые над полем комплексных чисел [ ]

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

Это отображение — j-инвариантом .

Классы изоморфизма можно рассмотреть более простым способом. Константы g 2 <\displaystyle g_<2>> и g 3 <\displaystyle g_<3>> , называемые полем разложения для многочленов, а значит, эллиптические кривые можно записать как

Можно показать, что

Здесь λ иногда называют лямбда-функцией модуляра .

Отметим, что теорема об униформации утверждает, что любая Эллиптические кривые над произвольным полем [ ]

Эллиптические кривые могут быть определены над любым полем K; формально, эллиптическая кривая определяется как невырожденная проективная алгебраическая кривая над K с Связь с теорией чисел [ ]

Этот факт можно истолковать и доказать с помощью некоторых общих тем; см. Локальная дзета-функция , Арифметика абелевых многообразий .

Доступно о криптографии на эллиптических кривых

Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.

До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

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

В частности, я рассмотрю следующие темы:

Эллиптические кривые над вещественными числами и групповой закон

Эллиптические кривые над конечными полями и задача дискретного логарифмирования

Генерирование пар ключей и два алгоритма ECC: ECDH и ECDSA

Алгоритмы для взлома защиты ECC и сравнение с RSA

Часть 1: эллиптические кривые над вещественными числами и групповой закон

Эллиптические кривые

Во-первых: что такое эллиптическая кривая? В Wolfram MathWorld есть отличное и исчерпывающее определение. Но для нас достаточно того, что эллиптическая кривая — это просто множество точек, описываемое уравнением:

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

Различные формы эллиптических кривых (, изменяется от 2 до -3).

Виды особенностей: слева — кривая с точкой возврата (каспом) (). Справа — кривая с самопересечением (). Оба этих примера не являются полноценными эллиптическими кривыми.

В зависимости от значений и эллиптические кривые могут принимать на плоскости разные формы. Как можно легко увидеть и проверить, эллиптические кривые симметричны относительно оси .

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

Если нам требуется явным образом учитывать точку в бесконечности, то определение эллиптической кривой можно уточнить следующим образом:

Группы

В математике группа — это множество, для которого мы определили двоичную операцию, называемую «сложением» и обозначаемую символом +. Чтобы множество было группой, сложение нужно определить таким образом, чтобы оно соответствовало четырём следующим свойствам:

замыкание: если и входят в , то входит в ;

ассоциативность: ;

существует единичный элемент 0, такой, что ;

у каждого элемента есть обратная величина, то есть: для каждого существует такое , что .

коммутативность: ,

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

Группы удобны тем, что если мы докажем соблюдение всех четырёх свойств, то получим автоматически некоторые другие свойства «в нагрузку». Например: единичный элемент уникален; кроме того, обратные величины уникальны, то есть: для каждого существует единственное , такое, что (и мы можем записать как ). Непосредственно или косвенно эти и другие свойства групп очень пригодятся нам в будущем.

Групповой закон для эллиптических кривых

Мы можем определить группу для эллиптических кривых. А именно:

элементы группы являются точками эллиптической кривой;

единичный элемент — это бесконечно удалённая точка 0;

обратная величина точки — это точка, симметричная относительно оси ;

сложение задаётся следующим правилом: сумма трёх ненулевых точек , и , лежащих на одной прямой, будет равна .

Сумма трёх точек, находящихся на одной прямой, равна 0.

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

Пока всё идёт отлично. Но как нам вычислить сумму двух произвольных точек?

Геометрическое сложение

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

Проводим прямую через и . Прямая пересекает третью точку . Симметричная ей точка является результатом .

Геометрический способ работает, но требует усовершенствования. В частности, нам нужно ответить на несколько вопросов:

Что если или ? Разумеется, мы не сможем провести прямую (0 не находится на плоскости ). Но поскольку мы определили 0 как единичный элемент, и для любой и любой .

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

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

При сближении двух точек проходящая через них прямая становится касательной к кривой.

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

Алгебраическое сложение

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

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

Если и не совпадают (), то проходящая через них прямая имеет наклон:

Пересечение этой прямой с эллиптической кривой — это третья точка :

Поэтому (обратите внимание на знаки и помните, что ).

Если бы нам нужно было проверить правильность результата, то пришлось бы проверить, принадлежит ли кривой и находятся ли , и на одной прямой. Проверка нахождения на одной прямой тривиальна, а проверка принадлежности кривой — нет, потому что нам придётся решать кубическое уравнение, что совсем невесело.

Вместо этого давайте поэкспериментируем с примером: согласно визуальному инструменту, при и , принадлежащих кривой , их сумма равна . Давайте проверим, соответствует ли это уравнениям:

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

Мы получили результат , который совпадает с результатом, полученным в визуальном инструменте.

К случаю нужно относиться немного иначе: уравнения для и остаются теми же, но с учётом того, что нам придётся использовать для наклона другое уравнение:

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

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

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

Скалярное умножение

Кроме сложения, мы можем определить и другую операцию: скалярное умножение, то есть:

где — натуральное число. Я написал визуальный инструмент и для скалярного умножения, так что можете поэкспериментировать с ним.

При записи в такой форме очевидно, что вычисление требует сложений. Если состоит из десятичных разрядов, то алгоритм будет иметь сложность , что не очень хорошо. Но существуют и более быстрые алгоритмы.

Один из них — алгоритм удвоения-сложения. Принцип его работы проще объяснить на примере. Возьмём . В двоичном форме оно имеет вид . Такую двоичную форму можно представить как сумму степеней двойки:

(Мы взяли каждый двоичный разряд и умножили на степень двойки.)

С учётом этого можно записать:

Алгоритм удвоения-сложения задаёт следующий порядок действий:

Взять .

Удвоить его, чтобы получить .

Сложить и (чтобы получить результат ).

Удвоить , чтобы получить .

Сложить с результатом (чтобы получить ).

Удвоить , получить .

Не выполнять сложение с .

Удвоить , чтобы получить .

Сложить с результатом (чтобы получить ).

.

Если вам это понятно не до конца, то вот скрипт на Python, реализующий этот алгоритм:

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

Логарифм

Для заданных и у нас есть по крайней мере один полиномиальный алгоритм вычисления . Но как насчёт обратной задачи? Что если мы знаем и , а нам нужно определить ? Эта задача известна как задача логарифмирования. Мы употребляем слово «логарифм» вместо термина «деление» для согласованности с другими криптосистемами (в которых вместо умножения используется возведение в степень).

Я не знаю ни одного «простого» алгоритма для решения задачи логарифмирования, однако экспериментируя с умножением, легко обнаружить некоторые закономерности. Например, возьмём кривую и точку . Мы можем сразу убедиться, что если нечётное, то находится на кривой в левой полуплоскости; если чётное, то — в правой полуплоскости. Если поэкспериментировать ещё, мы, возможно, найдём и другие закономерности, которые приведут нас к написанию алгоритма для эффективного вычисления логарифма этой кривой.

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

В следующей части мы исследуем конечные поля и задачу дискретной логарифмизации, а также примеры и инструменты для экспериментов.

Часть 2: эллиптические кривые над конечными полями и задача дискретного логарифмирования

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

Затем мы ввели понятие скалярного умножения () и нашли «простой» алгоритм для вычисления скалярного умножения: удвоение-сложение.

Теперь мы ограничим эллиптические кривые конечными полями, а не вещественными числами, и посмотрим, что это изменит.

Поле целых чисел по модулю p

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

Для полей существует две двухместные операции: сложение (+) и умножение (·). Обе они замкнуты, ассоциативны и коммутативны. Для обеих операций существует уникальный единичный элемент и для каждого элемента есть уникальный элемент обратной величины. И, наконец, умножение дистрибутивно относительно сложения: .

Множество целых чисел по модулю состоит из всех целых чисел от 0 до . Сложение и умножение работают как в модулярной арифметике. Вот несколько примеров операций над :

Сложение:

Вычитание:

Умножение:

Аддитивная инверсия: . Действительно:

Мультипликативная инверсия:

Как мы уже сказали целые числа по модулю — это поле, поэтому все перечисленные выше свойства сохраняются. Учтите, что требование того, чтобы было простым числом, очень важно! Множество целых чисел по модулю 4 не является полем: 2 не имеет мультипликативной инверсии (т.е. уравнение не имеет решений).

Деление по модулю p

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

Вычисление обратного числа можно «просто» выполнить с помощью расширенного алгоритма Евклида, который в худшем случае имеет сложность (или , если мы учитываем битовую длину).

Мы не будем вдаваться в подробности расширенного алгоритма Евклида, это не входит в рамки статьи, но я представлю работающую реализацию на Python:

Эллиптические кривые над

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

теперь превращаются в:

где 0 — по-прежнему точка в бесконечности, а и — два целых числа в .

Кривая с . Заметьте, что для каждого существует максимум две точки. Также заметьте симметрию относительно .

Кривая — особая и имеет тройную точку в . Она не является истинной эллиптической кривой.

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

Сложение точек

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

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

Сложение точек для кривой , при и . Заметьте, как соединяющая точки прямая «повторяет» себя на плоскости.

Учитывая то, что мы по-прежнему находимся в группе, сложение точек сохраняет уже известные нам свойства:

(из определения единичного элемента).

Для обратная величина — это точка, имеющая ту же абсциссу, но обратную ординату. Или, если угодно, . Например, если кривая над имеет точку , то обратной величиной будет .

Кроме того, (из определения обратной величины).

Алгебраическая сумма

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

Если , то наклон принимает форму:

Иначе, если , мы получаем:

Уравнения не изменились, и это не совпадение: на самом деле, эти уравнения работают над любым полем, и над конечным, и над бесконечным (за исключением и , которые являются особыми случаями). Я чувствую, что это нужно объяснить. Но есть проблема: для доказательств группового закона обычно требуются сложные математические понятия. Однако я нашёл доказательство Стефана Фридла в котором используются только простейшие концепции. Прочитайте его, если вам интересно, почему эти уравнения работают (почти) над любым полем.

Вернёмся к кривым — мы не будем определять геометрический способ: на самом деле, с ним возникнут проблемы. Например, в предыдущей части мы сказали, что для вычисления нам придётся взять касательную к кривой в . Но при отсутствии непрерывности слово «касательная» теряет всякий смысл. Мы можем найти способ обойти эту и другие проблемы, однако чисто геометрический способ будет слишком сложным и совершенно непрактичным.

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

Порядок группы эллиптической кривой

Мы сказали, что эллиптическая кривая, определённая над конечным полем, имеет конечное количество точек. Нам нужно ответить на важный вопрос: сколько же в ней точек?

Во-первых, давайте определим, что количество точек в группе называется порядком группы.

Проверка всех возможных значений для в интервале от 0 до будет невыполнимым способом подсчёта точек, потому что потребует шагов, а эта задача «сложна», если — большое простое число.

К счастью, для вычисления порядка существует более быстрый алгоритм: алгоритм Шуфа. Я не буду вдаваться в его подробности — главное, что он выполняется за полиномиальное время, а именно этого нам и нужно.

Скалярное умножение и циклические подгруппы

Для вещественных чисел умножение можно определить как:

И, повторюсь, мы можем использовать алгоритм удвоения-сложения для выполнения умножения за , где — это количество бит ). Я написал интерактивный инструмент для скалярного умножения.

Умножение точек для эллиптических кривых над обладает интересным свойством. Возьмём кривую и точку . Теперь вычислим все величины, кратные :

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

для любого целого . Заметьте, что благодаря оператору деления с остатком эти пять уравнений можно «ужать» в одно: .

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

То же относится и ко всем остальным точкам, не только к . На самом деле, если мы возьмём в общем виде:

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

«Подгруппа» — это группа, являющаяся подмножеством другой группы. «Циклическая подгруппа» — это подгруппа, элементы которой циклически повторяются, как мы показали в предыдущем примере. Точка называется генератором или базовой точкой циклической подгруппы.

Циклические подгруппы — фундамент для ECC и других криптосистем. Позже я объясню, почему это так.

Порядок подгруппы

Можно задаться вопросом, каков порядок подгруппы, порождённой точкой (или, иными словами, каков порядок ). Для ответа на этот вопрос мы не можем использовать алгоритм Шуфа, потому что этот алгоритм работает только для целых эллиптических кривых, но не для подгрупп. Прежде чем приступить к решению задачи, нам нужно ещё немного информации:

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

Вычисляем порядок эллиптической кривой с помощью алгоритма Шуфа.

Находим все делители .

Для каждого делителя порядка вычисляем .

Наименьшее , такое, что , является порядком подгруппы.

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

Ещё один пример: эллиптическая кривая, определяемая уравнением над полем , имеет порядок , которое является простым числом. Её подгруппы могут иметь порядок только или . Как вы можете догадаться, когда , подгруппа содержит только бесконечно удалённую точку; когда , подгруппа содержит все точки эллиптической кривой.

Поиск базовой точки

Для алгоритмов ECC требуются подгруппы с высоким порядком. Поэтому обычно выбирается эллиптическая кривая, вычисляется её порядок (), в качестве порядка группы () выбирается большой делитель, а потом находится подходящая базовая точка. То есть мы не выбираем базовую точку, после чего вычисляем её порядок, а производим обратную операцию: сначала выбираем достаточно хороший порядок, а потом ищем подходящую базовую точку. Как же это сделать?

Во-первых, нужно ввести ещё одно понятие. Теорема Лагранжа подразумевает, что число всегда целое (потому что — делитель ). Число имеет собственное название: это кофактор подгруппы.

Теперь рассмотрим, что для каждой точки эллиптической кривой есть . Это справедливо, потому что — это кратное любому возможному . Исходя из определения кофактора, мы можем записать:

Теперь допустим, что — простое число (мы предпочитаем простые порядки по причинам, изложенным в первой части статьи). Это уравнение, записанное в такой форме, говорит нам, что точка создаёт подгруппу порядка (за исключением случая , в котором подгруппа имеет порядок 1).

В свете этого мы можем определить следующий алгоритм:

Вычисляем порядок эллиптической кривой.

Выбираем порядок подгруппы. Чтобы алгоритм сработал, число должно быть простым и быть делителем .

Вычисляем кофактор .

Выбираем на кривой случайную точку .

Вычисляем .

Если равно 0, то возвращаемся к шагу 4. В противном случае мы нашли генератор подгруппы с порядком и кофактором .

Дискретный логарифм

Как и в случае с непрерывными эллиптическими кривыми, теперь мы должны обсудить следующий вопрос: если мы знаем и , то каким будет , такое, что ?

Эта задача, известная как задача дискретного логарифмирования для эллиптических кривых, считается «сложной», для которой не обнаружено алгоритма полиномиального времени, выполняемого на классическом компьютере. Однако у этой точки зрения нет математических доказательств.

Эта задача аналогична задаче дискретного логарифмирования, используемой в других криптосистемах, таких как Digital Signature Algorithm (DSA), протокол Диффи-Хеллмана (D-H) и схема Эль-Гамаля. Названия задач совпадают неслучайно. Их разница в том, что в этих алгоритмах используется не скалярное умножение, а возведение в степень по модулю. Их задачу дискретного логарифмирования можно сформулировать так: если известны и , то каким будет , такое, что ?

Обе эти задачи «дискретны», потому что в них используются конечные множества (а конкретнее — циклические подгруппы). И они являются «логарифмами», потому что аналогичны обычным логарифмам.

ECC интересна тем, что на сегодняшний момент задача дискретного логарифмирования для эллиптических кривых кажется «сложнее» по сравнению с другими схожими задачами, используемыми в криптографии. Это подразумевает, что нам потребуется меньше бит для целого , чтобы получить тот же уровень защиты, что и в других криптосистемах, и мы это подробно рассмотрим в четвёртой, последней, части статьи.

Часть 3: ECDH и ECDSA

Параметры области определения

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

Простое , задающее размер конечного поля.

Коэффициенты и уравнения эллиптической кривой.

Базовая точка , генерирующая подгруппу.

Порядок подгруппы.

Кофактор подгруппы.

Случайные кривые

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

Предположим теперь, что я дал вам параметры области определения кривой. Существует вероятность, что я обнаружил неизвестный никому новый класс слабых кривых, и, возможно, я создал «быстрый» алгоритм вычисления дискретных логарифмов для своей кривой. Как я могу убедить вас в обратном, т.е. в том, что мне неизвестно об уязвимостях? Как я могу гарантировать, что кривая «защищена» (в том смысле, что я не смогу её использовать для собственных атак)?

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

Простая схема генерирования случайной кривой из порождающего значения: хеш случайного числа используется для вычисления различных параметров кривой.

Если бы мы хотели сжульничать и воссоздать хеш из параметров области определения, то нам пришлось бы решать «сложную» задачу: инверсирование хеша.

Сгенерированная с помощью порождающего значения кривая называется проверяемо случайной. Принцип использования хешей для генерирования параметров известен как «nothing up my sleeve» («в рукавах ничего нет»), и широко распространён в криптографии.

Эта хитрость даёт определённую гарантию, что кривая не была специально создана таким образом, чтобы иметь известные её автору уязвимости. На самом деле, если я даю вам кривую вместе с порождающим значением, то это значит, что я не мог произвольно выбирать параметры и , и можно быть относительно спокойным, что я не смогу использовать специальные атаки. Причина использования слова «относительно» будет объяснена в четвёртой части.

Стандартизированный алгоритм генерирования и проверки случайных кривых описан в ANSI X9.62 и основан на SHA-1. Если интересно, можете прочитать об алгоритмах генерирования проверяемо случайных кривых в спецификации SECG (см. «Verifiably Random Curves and Base Point Generators»).

Я написал небольшой скрипт на Python, проверяющий все случайные кривые, поставляемые сейчас с OpenSSL. Крайне рекомендую посмотреть его!

Криптография на эллиптических кривых

Мы потратили много времени, но наконец добрались! Всё просто:

Закрытый ключ — это случайное целое , выбранное из (где — порядок подгруппы).

Открытый ключ — это точка (где — базовая точка подгруппы).

Теперь мы опишем два основанных на этом принципе алгоритма с открытым ключом: ECDH (Elliptic curve Diffie-Hellman, протокол Диффи-Хеллмана на эллиптических кривых), используемый для шифрования, и ECDSA (Elliptic Curve Digital Signature Algorithm), используемый для цифровых подписей.

Шифрование с помощью ECDH

ECDH — это разновидность алгоритма Диффи-Хеллмана для эллиптических кривых. На самом деле это скорее протокол согласования ключей, а не алгоритм шифрования. В сущности, это означает, что ECDH задаёт (в определённой степени) порядок генерирования ключей и обмена ими. Способ шифрования данных с помощью таких ключей мы можем выбирать сами.

Он решает следующую проблему: две стороны (обычно Алиса и Боб) хотят безопасно обмениваться информацией, чтобы третья сторона (посредник, Man In the Middle) мог перехватывать её, но не мог расшифровать. Например, это один из принципов TLS.

Вот как это работает:

Сначала Алиса и Боб генерируют собственные закрытые и открытые ключи. У Алисы есть закрытый ключ и открытый ключ , у Боба есть ключи и . Заметьте, что и Алиса, и Боб используют одинаковые параметры области определения: одну базовую точку на одной эллиптической кривой в одинаковом конечном поле.

Алиса и Боб обмениваются открытыми ключами и по незащищённому каналу. Посредник (Man In the Middle) перехватывает и , но не может определить ни , ни , не решив задачу дискретного логарифмирования.

Алиса вычисляет (с помощью собственного закрытого ключа и открытого ключа Боба), а Боб вычисляет (с помощью собственного закрытого ключа и открытого ключа Алисы). Учтите, что одинаков и для Алисы, и для Боба. На самом деле:

(Последняя формулировка используется в исходном алгоритме Диффи-Хеллмана, основанном на модулярной арифметике.)

Протокол Диффи-Хеллмана: Алиса и Боб могут «просто» вычислить общий секретный ключ, посреднику же придётся решать «сложную» задачу.

Принцип, лежащий в основе задачи Диффи-Хеллмана, также объяснён в отличном видео Академии Хана на YouTube, в котором чуть позже объясняется алгоритм Диффи-Хеллмана в приложении к модулярной арифметике (не к эллиптическим кривым).

Задача Диффи-Хеллмана для эллиптических кривых считается «сложной». Считается, что она так же «сложна», как задача дискретного логарифмирования, но математических доказательств этому нет. Мы можем только с уверенностью сказать, что она не может быть «сложнее», потому что решение задачи логарифмирования — это способ решения задачи Диффи-Хеллмана.

Получив общий секретный ключ, Алиса и Боб могут обмениваться данными с симметричным шифрованием.

Например, они могут использовать координату ключа как ключ для шифрования сообщений такими безопасными шифрами, как AES или 3DES. Примерно это и делает TLS, разница в том, что TLS соединяет координату с другими числами, относящимися к подключению, а затем вычисляет хеш получившейся строки байтов.

Эксперименты с ECDH

Я написал ещё один скрипт на Python для вычисления закрытых/открытых ключей и общих секретных ключей над эллиптической кривой.

В отличие от показанных ранее примеров, в этом скрипте используется стандартизированная кривая, а не простая кривая на небольшом поле. Я выбрал кривую secp256k1 группы SECG («Standards for Efficient Cryptography Group», основанной Certicom). Та же самая кривая используется в Bitcoin для цифровых подписей. Вот параметры области определения:

= 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f

= 0

= 7

= 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798

= 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8

= 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141

= 1

Разумеется, вы можете изменить скрипт и использовать другие кривые и параметры области определения, только обязательно используйте простые поля и обычную формулировку Вейерштрасса, иначе скрипт не будет работать.

Скрипт очень прост и содержит некоторые из описанных выше алгоритмов: сложение точек, удвоение-сложение, ECDH. Рекомендую изучить и запустить его. Он создаёт примерно такие выходные данные:

Эфемерное ECDH

Некоторые из вас, возможно, слышали об ECDHE, а не об ECDH. «E» в ECHDE обозначает «Ephemeral» (эфемерное) и связано с тем, что передаваемые ключи временны, а не статичны.

ECDHE используется, например, в TLS, где клиент и сервер генерируют свою пару закрытого-открытого ключа на лету, при установке соединения. Затем ключи подписываются сертификатом TLS (для авторизации) и передаются между сторонами.

Подписывание с помощью ECDSA

Сценарий следующий: Алиса хочет подписать сообщение своим закрытым ключом (), а Боб хочет проверить подпись с помощью открытого ключа Алисы (). Никто, кроме Алисы не должен иметь возможности создать действительные подписи. Каждый должен иметь возможность проверить подписи.

Алиса и Боб снова используют одинаковые параметры области определения. Мы рассмотрим алгоритм ECDSA, разновидность Digital Signature Algorithm, применённого к эллиптическим кривым.

ECDSA работает с хешем сообщения, а не с самим сообщением. Выбор хеш-функции остаётся за нами, но, очевидно, нужно выбирать криптографическую хеш-функцию. Хеш сообщения необходимо урезать, чтобы битовая длина хеша была такой же, что и битовая длина (порядок подгруппы). Урезанный хеш — это целое число и оно будет обозначаться как .

Алгоритм, выполняемый Алисой для подписывания сообщения, работает следующим образом:

Берём случайное целое , выбранное из (где — это по-прежнему порядок группы).

Вычисляем точку (где — базовая точка подгруппы).

Вычисляем число (где — это координата ).

Если , то выбираем другое и пробуем снова.

Вычисляем (где — закрытый ключ Алисы, а — мультипликативная инверсия по модулю ).

Если , то выбираем другое и пробуем снова.

Алиса подписывает хеш с помощью закрытого ключа и случайного . Боб проверяет правильность подписи сообщения с помощью открытого ключа Алисы .

Проще говоря, этот алгоритм сначала генерирует секретный ключ (). Благодаря умножению точек (которое, как мы знаем, является «простым» в одну сторону и «сложным» в обратную) секретный ключ прячется в . Затем привязывается к хешу сообщения уравнением .

Учтите, что для вычисления мы вычислили обратную величину по модулю . Как было сказано в предыдущей части, это гарантировано сработает только если — простое число. Если подгруппа имеет порядок непростого числа, ECDSA использовать не удастся. Неслучайно все стандартизированные кривые имеют простой порядок, а имеющие непростой порядок неприменимы для ECDSA.

Проверка подписей

Для проверки подписи необходим открытый ключ Алисы , (урезанный) хеш и, очевидно, подпись .

Вычисляем целое .

Вычисляем целое .

Вычисляем точку .

Корректность алгоритма

С первого взгляда логика алгоритма может быть неочевидной, однако если объединить все ранее записанные нами уравнения, всё становится понятнее.

Начнём с . Из определения открытого ключа мы знаем, что (где — закрытый ключ). Можно записать:

С учётом определений и можно записать:

Здесь мы опустили «», как для краткости, так и потому, что циклическая подгруппа, сгенерированная точкой , имеет порядок , то есть часть «» избыточна.

Ранее мы определили . Умножив обе части уравнения уравнения на и поделив на , мы получаем: . Подставляя этот результат в наше уравнение для , получаем:

Это то же самое уравнение , которое было у нас на шаге 2 алгоритма генерирования подписи! При генерировании подписей и при их проверке мы вычисляем одну и ту же точку , просто разными наборами уравнений. Именно поэтому алгоритм работает.

Экспериментируем с ECDSA

Разумеется, я написал скрипт на Python для генерирования и проверки подписей. Код копирует некоторые части из скрипта ECDH, в частности, параметры области определения и алгоритм генерирования пары закрытого/открытого ключей.

Вот какие выходные данные создаются этим скриптом:

Как видите, скрипт сначала подписывает сообщение (байтовую строку «Hello!»), а затем проверяет подпись. После чего он пробует проверить ту же подпись для другого сообщения («Hi there!») и проверка не удаётся. Наконец, он пробуем проверить проверить подпись для правильного сообщения, но с другим случайным открытым ключом, после чего проверка тоже не удаётся.

Важность k

При генерировании подписей ECDSA важно хранить секретный по-настоящему в тайне. Если бы мы использовали одну для всех подписей или генератор случайных чисел оказался бы в какой-нибудь степени предсказуемым, то атакующий смог бы определить закрытый ключ!

Подобную ошибку сделала Sony несколько лет назад. На игровой консоли PlayStation 3 можно было запускать игры, только подписанные Sony алгоритмом ECDSA. То есть, если бы я хотел создать новую игру для PlayStation 3, я не смог бы распространять её среди пользователей без подписи Sony. Проблема заключалась в том, что все созданные Sony подписи были сгенерированы с помощью статичного .

(Похоже, создатели генератора случайных чисел Sony вдохновлялись или XKCD, или Дилбертом.)

В такой ситуации можно запросто восстановить закрытый ключ Sony, купив всего две подписанные игры, после чего извлечь их хеши ( и ) и подписи ( и ) вместе с параметрами области определения. Это делается так:

Сначала нужно учесть, что (потому что и одинаковы для обеих подписей).

Принять, что (этот результат следует непосредственно из уравнения для ).

Умножить обе части уравнения на : .

Разделить на , чтобы получить .

Похожие техники можно применить, если не статично, но каким-то образом предсказуемо.

Часть 4: алгоритмы для взлома защиты ECC и сравнение с RSA

В предыдущей части мы рассмотрели два алгоритма (ECDH and ECDSA) и разобрались, почему задача дискретного логарифмирования для эллиптических кривых играет важную роль для их безопасности. Но, если вы помните, мы сказали, что математических доказательств сложности задачи дискретного логарифмирования нет: мы полагаем, что она «сложна», но не уверены в этом. В первой части статьи мы попробовали оценить, насколько «сложна» она на практике в условиях современных технологий.

Во второй части мы попытались ответить на вопрос: зачем нам нужна криптография на эллиптических кривых, если RSA (и другие криптосистемы, основанные на модулярной арифметике) хорошо работают?

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

Теперь мы рассмотрим два наиболее эффективных алгоритма вычисления дискретных алгоритмов на эллиптической кривой: алгоритм «baby-step, giant-step» и ρ-алгоритм Полларда.

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

Baby-step, giant-step

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

С учётом этого можно переписать уравнение задачи дискретного логарифмирования следующим образом:

Baby-step giant-step — это алгоритм «встречи посередине». В отличие от атаки перебором (при которой придётся вычислять все точки для каждого , пока мы не найдём ), можно вычислять «несколько» значений для и «несколько» значений для , пока мы не найдём соответствие. Алгоритм работает следующим образом:

Вычисляем

Для каждого из вычисляем и сохраняем результаты в хеш-таблицу.

Для каждого из :

вычисляем ;

вычисляем ;

проверяем хеш-таблицу и ищем точку , такую, что ;

если такая точка существует, то мы нашли .

Алгоритм baby-step, giant-step: сначала мы вычисляем несколько точек с небольшим шагом и сохраняем их в хеш-таблице. Затем делаем великанские шаги и сравниваем новые точки с точками в хеш-таблице. Найдя соответствие, мы можем вычислить дискретный алгоритм простой перестановкой членов.

Чтобы понять, как работает алгоритм, забудем на минуту о том, что кешируются, и возьмём уравнение . Рассмотрим, что из этого следует:

При мы проверяем, равно ли числу , где — одно из целых от 0 до . Таким образом, мы сравниваем со всеми точками от до .

При мы проверяем равно ли числу . Мы сравниваем со всеми точками от до .

При мы сравниваем со всеми точками от до .

.

При мы сравниваем со всеми точками от до .

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

Baby-step giant-step на практике

Имеет смысл разобраться, что же значит сложность на практике. Возьмём стандартизированную кривую: prime192v1 (она же secp192r1 , ansiX9p192r1 ). Эта кривая имеет порядок = 0xffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831. Квадратный корень из — это примерно 7,922816251426434 · 10 28 (почти восемьдесят октиллионов [прим. пер.: по короткой шкале]).

Представим, что мы храним точек в хеш-таблице. Предположим, что каждая точка занимает ровно 32 байта: для хеш-таблицы потребуется примерно 2,5 · 10 30 байт памяти. Поискав в Интернете, можно узнать, что современная общая ёмкость накопителей всего мира имеет порядок зеттабайта (10 21 байт). Это почти на десять порядков меньше, чем объём памяти, необходимый нашей хеш-таблице! Даже если бы точки занимали по 1 байт каждая, мы всё равно не смогли бы хранить их все.

Это впечатляет, и впечатляет ещё сильнее, если вспомнить, что prime192v1 — это одна из кривых с наименьшим порядком. Порядок secp521r1 (ещё одной стандартной кривой NIST) равен примерно 6,9 · 10 156 !

Эксперименты с baby-step giant-step

Я написал скрипт на Python, вычисляющий дискретные логарифмы с помощью алгоритма baby-step giant-step. Очевидно, что он работает только с кривыми малого порядка: не пытайтесь использовать secp521r1 , если только не хотите получить MemoryError .

Скрипт выдаёт примерно такие выходные данные:

ρ Полларда

ρ Полларда — это ещё один алгоритм вычисления дискретных логарифмов. Он имеет ту же асимптотическую временную сложность , что и baby-step giant-step, но его пространственная сложность равна всего . Если baby-step giant-step не мог решить дискретные логарифмы из-за огромных требований к памяти, может быть, ρ Полларда справится? Давайте проверим…

Для начала ещё раз напомню задачу дискретного логарифмирования: найти для заданных и целое , такое, что . В ρ-алгоритме Полларда мы будем решать немного другую задачу: найти для заданных и целые , , и , такие, что .

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

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

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

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

Задача заключается в следующем: как обнаружить цикл эффективным способом?

Черепаха и заяц

Для обнаружения цикла мы можем проверить все возможные значения и с помощью функции пересчёта пар, но при условии, что существует таких пар, алгоритм будет иметь сложность , что намного хуже атаки простым перебором.

Но существует и более быстрый способ: алгоритм черепахи и зайца (также известный как алгоритм нахождения цикла Флойда). На рисунке ниже показан принцип работы метода черепахи и зайца, на котором основан ρ-алгоритм Полларда.

У нас есть кривая и точки и . Точки принадлежат циклической подгруппе с порядком 5. Мы обходим последовательность пар с разными скоростями, пока не находим две разные пары и , дающих одну точку. В этом случае мы нашли пары и , что позволяет нам вычислить логарифм как . И на самом деле, у нас получилось .

В сущности, мы берём псевдослучайную последовательность пар вместе с соответствующей последовательностью точек . Последовательность пар может быть или не быть циклической, но последовательность точек точно циклическая, потому что и сгенерированы из одной базовой точки, а из свойство подгрупп мы знаем, что не можем «сбежать» из подгруппы только скалярным умножением и сложением.

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

Через какое-то время черепаха и заяц найдут одну точку, но с разными парами коэффициентов. Или, если выразить это уравнениями, черепаха найдёт пару , а заяц — пару , такие, что .

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

Экспериментируем с ρ Полларда

Я создал скрипт на Python, вычисляющий дискретные логарифмы с помощью ρ-алгоритма Полларда. Это не реализация исходного ρ Полларда, а небольшая его вариация (я использовал более эффективный способ генерирования псевдослучайной последовательности пар). В скрипте есть полезные комментарии, так что прочитайте его, если вам интересны подробности алгоритма.

Этот скрипт, как и baby-step giant-step, работает для маленьких кривых и создаёт те же выходные данные.

Ро Полларда на практике

Мы говорили, что baby-step giant-step невозможно использовать на практике из-за огромных требований к памяти. С другой стороны, ро-алгоритм Полларда требует очень мало памяти. Насколько же он практичен?

В 1998 году Certicom начала соревнование по вычислению дискретных логарифмов на эллиптических кривых с битовой длиной от 109 до 369. На сегодняшний день успешно взломаны только кривые длиной 109 бит. Последняя успешная попытка была совершена в 2004 году. Процитируем Википедию:

Как мы уже сказали, prime192v1 — это одна из «наименьших» эллиптических кривых. Мы также сказали, что ρ Полларда имеет временную сложность . Если бы мы использовали ту же технику, что и Крис Монико (тот же алгоритм, то же оборудование и количество машин), сколько бы заняло вычисление логарифма для prime192v1 ?

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

Сравниние ρ Полларда и Baby-step giant-step

Этот четвёртый скрипт вычисляет все логарифмы для всех точек на «маленькой» кривой с помощью разных алгоритмов и сообщает, сколько времени это заняло:

Как и можно ожидать, метод перебора чудовищно медленный по сравнению с двумя другими. Baby-step giant-step быстрее, а ро-алгоритм Полларда больше чем в три раза медленнее baby-step giant-step (хоть он и использует гораздо меньше памяти и меньшее количество шагов в среднем).

Посмотрите ещё и на количество шагов: для вычисления каждого логарифма способом перебора в среднем потребовалось 5193 шагов. 5193 очень близко к 10331 / 2 (половина порядка кривой). Baby-step giant-steps и ро Полларда использовали 152 шага и 138 шагов соответственно. Эти два числа очень близки к квадратному корню 10331 (101,64).

Дальнейшие рассуждения

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

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

Алгоритм Шора

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

Эффективность квантовых алгоритмов заключается в суперпозиции состояния. У классических компьютеров ячейки памяти (т.е. биты) могут иметь значение 1 или 0. Между ними нет промежуточных состояний. С другой стороны, ячейки памяти квантовых компьютеров (кубиты) подвержены принципу неопределённости: пока их не измерят, у них нет полностью определённого состояния. Суперпозиция состояния не значит, что каждый кубит может одновременно иметь значение 0 и 1 (как часто пишут в Интернете). Она значит, что при измерении кубита у нас есть определённая вероятность наблюдать 0 и другая вероятность наблюдать 1. Работа квантовых алгоритмов заключается в изменении вероятности каждого кубита.

Эта странность означает, что с ограниченным количеством кубитов мы можем одновременно иметь дело со множеством возможных входных данных одновременно. Например, мы можем сказать квантовому компьютеру, что существует число , равномерно распределённое между 0 и . При этом требуется всего кубитов вместо бит. Затем мы можем приказать квантовому компьютеру выполнить скалярное умножение . В результате мы получим суперпозицию состояний, заданную всеми точками от до , то есть если мы теперь измерим все кубиты, то получим одну из точек от до с вероятностью .

Я рассказал об этом, чтобы вы поняли всю мощь суперпозиции состояний. Алгоритм Шора работает не совсем так, на самом деле он более сложен. Его усложняет то, что хотя мы и можем «симулировать» состояний одновременно, на каком-то этапе нам придётся снизить это количество состояний до нескольких, потому что на выходе нам нужно одно число, а не несколько (т.е., нам нужно знать один логарифм, а не множество вероятно ошибочных логарифмов).

ECC и RSA

Теперь давайте забудем о квантовых вычислениях, которые пока ещё не стали серьёзной проблемой. Я хочу ответить на следующий вопрос: зачем возиться с эллиптическими кривыми, если RSA и так работает хорошо?

Простой ответ дал NIST, представив таблицу сравнения размеров ключей RSA и ECC, необходимых для получения одинакового уровня защиты.

Размер ключа RSA (биты) Размер ключа ECC (биты)

1024 160

2048 224

3072 256

7680 384

15360 521

Заметьте, что линейной связи между размерами ключей RSA и ECC нет (другими словами: если мы удваиваем размер ключа RSA, нам не нужно удваивать размер ключа ECC). Таблица говорит нам, что ECC не только использует меньше памяти, но и генерирование ключей с подписыванием в ней гораздо быстрее.

Но почему это так? Ответ заключается в том, что самые быстрые алгоритмы для вычисления дискретных алгоритмов над эллиптическими кривыми — это ρ-алгоритм Полларда и baby-step giant-step, а в случае RSA есть более быстрые алгоритмы. В частности, один из них — это общий метод решета числового поля: алгоритм для факторизации целых чисел, который можно использовать для вычисления дискретных логарифмов. Общий метод решета числового поля — это на сегодняшний день самый быстрый алгоритм для факторизации целых чисел.

Всё это относится и к другим криптосистемам, основанным на модулярной арифметике, в том числе к DSA, Диффи-Хеллману и Эль-Гамалю.

Скрытые угрозы АНБ

А теперь перейдём к сложной части. До этого момента мы обсуждали алгоритмы и математику. Настало время обсудить людей, и всё становится сложнее.

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

Если прочитать страницу Википедии о принципе «в рукавах ничего нет», можно заметить, что:

Случайные числа для MD5 получаются из синуса целых чисел.

Случайные числа для Blowfish получаются из первых чисел .

Случайные числа для RC5 получаются из и золотого сечения.

Теперь возникает следующий вопрос: откуда берутся случайные порождающие значения для кривых NIST? Ответ: к сожалению, мы не знаем. Эти значения не имеют никакого обоснования.

Возможно ли, что NIST обнаружил «значительно большой» класс слабых эллиптических кривых, попробовал различные возможные варианты порождающих значений и нашёл уязвимую кривую? Я не могу ответить на этот вопрос, но это закономерный и важный вопрос. Мы знаем, что NIST как минимум успешно стандартизировал уязвимый генератор случайных чисел (генератор, который, как ни странно, основан на эллиптических кривых). Возможно, он успешно стандартизировал и множество слабых эллиптических кривых? Как это проверить? Да никак.

Важно понимать, что «проверяемо случайный» и «защищённый» не являются синонимами. И неважно, насколько сложна задача логарифмирования или насколько длинны ключи — если алгоритмы взломаны, то мы ничего не можем поделать.

В этом отношении RSA побеждает, потому что ей не требуются специальные параметры области определения, которые можно эксплуатировать. RSA (как и другие системы модулярной арифметики) может быть хорошей альтернативой, если мы не можем доверять властям и если мы не можем создать собственные параметры области определения. И если вам любопытно: да, TLS может использовать кривые NIST. Если вы проверите в google, то увидите, что при подключении используются ECDHE и ECDSA с сертификатом, основанным на prime256v1 (она же secp256p1 ).

Вот и всё!

Надеюсь, вам понравилась эта статья. Я стремился познакомить вас с основной информацией, терминологией и допущениями, необходимыми для понимания текущего состояния криптографии на эллиптических кривых. Если мне это удалось, то теперь вы сможете разобраться с существующими криптосистемами на базе ECC и расширить свои знания чтением более глубокой документации. При написании статьи я пропустил очень многие подробности и использовал упрощённую терминологию, но я чувствовал, что в противном случае вы бы не поняли информацию, изложенную в Интернете. Я считаю, что мне удалось найти хороший компромисс между простотой и полнотой информации.

Стоит однако заметить, что прочитав только эту статью, вы не сможете реализовать защищённые криптосистемы на основе ECC: обеспечение безопасности требует знания многих тонких, но важных подробностей. Вспомните требования к атаке Смарта и ошибку Sony — это два примера того, как можно создать небезопасные алгоритмы и как легко их можно эксплуатировать.

Итак, если вам интересно глубже погрузиться в мир ECC, то с чего же начать?

Во-первых, пока мы видели кривые Вейерштрасса над простыми полями, но вы должны знать, что существуют и другие виды кривых и полей, а именно:

Кривые Коблица над двоичными полями. Это эллиптические кривые в форме (где — 0 или 1) над конечными полями, содержащими элементов (где — простое число). Они обеспечивают особо эффективное сложение точек и скалярное умножение.

И наконец, если вам интересны математические подробности, а не безопасность и эффективность алгоритмов, то нужно знать следующее:

Эллиптические кривые — это алгебраические многообразия рода 1.

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

Если вас интересует эта тема, то стоит искать по таким ключевым словам.

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

Похожие публикации:

Newrbb bid что это

Poc в трейдинге что это

Как майнить биткоин на ноутбуке 2021

Кто хранил деньги на каймановых островах