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

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

Использование эллиптических кривых для создания криптосистем было независимо друг от друга предложено Нилом Коблицем и Виктором Миллером в 1985 году^[1].

Введение

В 1985 году независимо Нилом Коблицем и Виктором Миллером было предложено использовать в криптографии алгебраические свойства эллиптических кривых. С этого момента началось бурное развитие нового направления криптографии, для которого используется термин «криптография на эллиптических кривых». Роль основной криптографической операции выполняет операция скалярного умножения точки на эллиптической кривой на данное целое число, определяемая через операции сложения и удвоения точек эллиптической кривой. Последние, в свою очередь, выполняются на основе операций сложения, умножения и инвертирования в конечном поле, над которыми рассматривается кривая. Особый интерес к криптографии эллиптических кривых обусловлен теми преимуществами, которые дает её применение в беспроводных коммуникациях — высокое быстродействие и небольшая длина ключа^[2]. Асимметричная криптография основана на сложности решения некоторых математических задач. Ранние криптосистемы с открытым ключом, такие как алгоритм RSA, криптостойки благодаря тому, что сложно разложить составное число на простые множители. При использовании алгоритмов на эллиптических кривых полагается, что не существует субэкспоненциальных алгоритмов для решения задачи дискретного логарифмирования в группах их точек. При этом порядок группы точек эллиптической кривой определяет сложность задачи. Считается, что для достижения такого же уровня криптостойкости, как и в RSA, требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 Агентство национальной безопасности объявило о создании «Suite B», в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации, классифицируемой до «Top Secret», используются всего лишь 384-битные ключи.

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

Основная статья: Эллиптическая кривая

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

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}}$

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

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики (${\displaystyle \mathbb {Z} _{p}}$, где ${\displaystyle p>3}$ — простое число) и полями характеристики 2 (${\displaystyle GF(2^{m})}$).

Эллиптические кривые над полями нечётной характеристики

Над полем ${\displaystyle \mathbb {Z} _{p}}$ характеристики ${\displaystyle p>3}$ уравнение эллиптической кривой E можно привести к виду:

${\displaystyle E:\quad y^{2}=x^{3}+Ax+B{\pmod {p}},}$

где ${\displaystyle A,B\in \mathbb {Z} _{p}}$ — константы, удовлетворяющие ${\displaystyle 4A^{3}+27B^{2}\not \equiv 0{\pmod {p}}}$.

Группой точек эллиптической кривой E над полем ${\displaystyle \mathbb {Z} _{p}}$ называется множество пар ${\displaystyle (x,y)}$, лежащих на E, объединённое с нулевым элементом ${\displaystyle {\mathcal {O}}}$:

${\displaystyle E(\mathbb {Z} _{p})={\mathcal {O}}\cup \left\{(x,y)\in \mathbb {Z} _{p}\times \mathbb {Z} _{p}|y^{2}\equiv x^{3}+Ax+B{\pmod {p}}\right\}.}$

Следует отметить, что в ${\displaystyle \mathbb {Z} _{p}}$ у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида ${\displaystyle (x,y)}$ и ${\displaystyle (x,-y)}$.

Пример

Рассмотрим эллиптическую кривую ${\displaystyle y^{2}=x^{3}+3x+2}$ над полем ${\displaystyle \mathbb {Z} _{5}}$. На этой кривой, в частности, лежит точка ${\displaystyle (1,1)}$, так как ${\displaystyle 1^{2}\equiv 1^{3}+3\cdot 1+2{\pmod {5}}}$. Легко проверить, что точки ${\displaystyle (1,\pm 1)}$, ${\displaystyle (1,\pm 4)}$, ${\displaystyle (2,\pm 1)}$, ${\displaystyle (2,\pm 4)}$ это все точки данной кривой.

Теорема Хассе

Основная статья: Теорема Хассе

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

${\displaystyle ({\sqrt {p}}-1)^{2}\leqslant |E(\mathbb {Z} _{p})|\leqslant ({\sqrt {p}}+1)^{2},}$

что влечёт:

${\displaystyle \left||E(\mathbb {Z} _{p})|-p\right|<2{\sqrt {p}}+1.}$

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

Над полем характеристики 2 рассматривают два вида эллиптических кривых:

• Суперсингулярная кривая

  ${\displaystyle y^{2}+ay=x^{3}+bx+c}$

• Несуперсингулярная кривая

  ${\displaystyle y^{2}+axy=x^{3}+bx^{2}+c}$

Особое удобство суперсингулярных эллиптических кривых в том, что для них легко вычислить порядок, в то время как вычисление порядка несуперсингулярных кривых вызывает трудности. Суперсингулярные кривые особенно удобны для создания самодельной ЕСС (Elliptic-curve cryptography) криптосистемы. Для их использования можно обойтись без трудоёмкой процедуры вычисления порядка.

Проективные координаты

Для вычисления суммы пары точек на эллиптической кривой требуется не только несколько операций сложения и умножения в ${\displaystyle \mathbb {F} _{q}}$, но и операция обращения, то есть для заданного ${\displaystyle x\in \mathbb {F} _{q}}$ нахождение такого ${\displaystyle y\in \mathbb {F} _{q}}$, что ${\displaystyle xy=1}$, которая на один-два порядка медленнее, чем умножение. К счастью, точки на эллиптической кривой могут быть представлены в различных системах координат, которые не требуют использования обращения при сложении точек:

• в проективной системе координат каждая точка ${\displaystyle (x,y)}$ представляется тремя координатами ${\displaystyle (X,Y,Z)}$, которые удовлетворяют соотношениям:

  ${\displaystyle x={\frac {X}{Z}}}$, ${\displaystyle y={\frac {Y}{Z}}}$.

• в системе координат Якоби точка также представляется тремя координатами ${\displaystyle (X,Y,Z)}$ с соотношениями: ${\displaystyle x={\frac {X}{Z^{2}}}}$, ${\displaystyle y={\frac {Y}{Z^{3}}}}$.
• в системе координат Лопес-Дахаб (洛佩斯·達哈卜 кит. / Lopez-Dahab лат.) выполняется соотношение: ${\displaystyle x={\frac {X}{Z}}}$, ${\displaystyle y={\frac {Y}{Z^{2}}}}$.
• в модифицированной системе координат Якоби используются 4 координаты ${\displaystyle (X,Y,Z,aZ^{4})}$ с теми же соотношениями.
• в системе координат Чудновского-Якоби используется 5 координат ${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$.

Важно отметить, что могут существовать различные именования — например, IEEE P1363-2000 называет проективными координатами то, что обычно называют координатами Якоби.

Шифрование/дешифрование с использованием эллиптических кривых

Первой задачей в рассматриваемой системе является шифрование открытого текста сообщения ${\displaystyle m}$, которое должно будет пересылаться в виде значения ${\displaystyle x-y}$ (Как?)^[3] для точки ${\displaystyle P_{m}}$. Здесь точка ${\displaystyle P_{m}}$ будет представлять закодированный в неё текст и впоследствии будет раскодироваться. Обратите внимание, невозможно закодировать сообщение просто координатой ${\displaystyle x}$ или ${\displaystyle y}$ точки, так как не все такие координаты имеются в ${\displaystyle E_{p}(a,b)}$.
Как и в случае системы обмена ключами, в системе шифрования, расшифрования в качестве параметров тоже рассматривается точка ${\displaystyle G}$ и эллиптическая группа ${\displaystyle E_{p}(a,b)}$. Пользователь ${\displaystyle A}$ выбирает личный ключ ${\displaystyle n_{A}}$ и генерирует открытый ключ ${\displaystyle P_{A}=n_{A}G}$. Чтобы зашифровать и послать сообщение ${\displaystyle P_{m}}$ пользователю ${\displaystyle B}$, пользователь ${\displaystyle A}$ выбирает случайное положительное целое число ${\displaystyle k}$ и вычисляет шифрованный текст ${\displaystyle G_{m}}$, состоящий из пары точек

${\displaystyle G_{m}=(kG,P_{m}+kP_{B})}$. При этом, ${\displaystyle G_{m}\neq P_{m},G_{m}}$ — пара точек.

Заметим, что сторона ${\displaystyle A}$ использует открытый ключ стороны ${\displaystyle B}$: ${\displaystyle P_{B}}$. Чтобы дешифровать этот шифрованный текст, ${\displaystyle B}$ умножает первую точку в паре на секретный ключ ${\displaystyle n_{B}}$ и вычитает результат из второй точки:
${\displaystyle (P_{m}+kP_{B})-n_{B}(kG)=P_{m}+k(n_{B}G)-n_{B}(kG)=P_{m}+{\cancel {kn_{B}(G)}}-{\cancel {kn_{B}(G)}}=P_{m}}$

Пользователь ${\displaystyle A}$ замаскировал сообщение ${\displaystyle P_{m}}$ с помощью добавления к нему ${\displaystyle kP_{B}}$. Никто, кроме этого пользователя не знает значения ${\displaystyle k}$, поэтому, хотя ${\displaystyle P_{B}}$ и является открытым ключом, никто не сможет убрать маску ${\displaystyle kP_{B}}$. Однако, пользователь ${\displaystyle A}$ включает в сообщение и "подсказку", которой будет достаточно, чтобы убрать маску тому, кто имеет личный ключ ${\displaystyle n_{B}}$. Противнику для восстановления сообщения придется вычислить ${\displaystyle k}$ по данным ${\displaystyle G}$ и ${\displaystyle kG}$, что представляется трудной задачей^[4].

Арифметические операции с точками на эллиптической кривой не эквивалентны этим арифметическим операциям с их координатами.

Точки эллиптической кривой над конечным полем представляют собой группу^[5]. Умножение сводится к многократным удвоению и суммированию.

Например, G+G ≠ 2G (это разные операции), 2G + 2^115G = 2^115G + 2G (суммирование коммутативно);

2G = 2*G; 4G = 2*2G; 8G = 2*4G; 16G = 2*8G, и т. д. (для двух одинаковых точек — только операция удвоения);

25*G; 25 = 11001 (in binary); 25 = 1*2^0 + 0*2^1 + 0*2^2 + 1*2^3 + 1*2^4 = 1 + 8 + 16; 25G = 16G + 8G + G = 1*(2^4)G + 1*(2^3)G + 1*G (операция суммирования).

24G/3 = 24G * (3^-1 mod P); where 3^(-1) mod P - modular multiplicative inverse,

5G - 3G = 5G + (-3G); где -3G = nG - 3G = O - 3G - additive inverse, point opposite.

Пример

Рассмотрим случай ${\displaystyle p=751}$, ${\displaystyle E_{p}(-1,188)}$, что соответствует кривой

${\displaystyle y^{2}=x^{3}-x+188}$ и ${\displaystyle G=(0,376)}$.

Предположим, что пользователь ${\displaystyle A}$ собирается отправить пользователю ${\displaystyle B}$ сообщение, которое кодируется эллиптической точкой ${\displaystyle P_{m}=(562,201)}$, и что пользователь ${\displaystyle A}$ выбирает случайное число ${\displaystyle k=386}$. Открытым ключом ${\displaystyle B}$ является ${\displaystyle P_{B}=(201,5)}$. Имеем:

${\displaystyle 386(0,376)=(676,558)}$

${\displaystyle (562,201)+386(201,5)=(385,328)}$.

Таким образом, пользователь ${\displaystyle A}$ должен послать шифрованный текст ${\displaystyle (676,558),(385,328)}$.

Реализация шифрования

Конкретные реализации алгоритмов шифрования на эллиптической кривой описаны ниже. Здесь рассмотрим общие принципы эллиптической криптографии.

Набор параметров

Для использования эллиптической криптографии все участники должны согласовать все параметры, определяющие эллиптическую кривую, т. е. набор параметров криптографического протокола. Эллиптическая кривая определяется константами ${\displaystyle a}$ и ${\displaystyle b}$ из уравнения (2). Абелева подгруппа точек является циклической и задается одной порождающей точкой G. При этом кофактор ${\displaystyle h={\frac {|E|}{n}}}$, где n — порядок точки G, должен быть небольшим (${\displaystyle h\leq 4}$, желательно даже ${\displaystyle h=1}$).

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

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

• NIST^[6]
• SECG^[7]

Для создания собственного набора параметров необходимо сделать следующее.

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

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

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

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

• Кривые над ${\displaystyle \mathbb {F} _{2^{m}}}$, где ${\displaystyle m}$ — не простое число. Шифрование на этих кривых подвержено атакам Вейля.
• Кривые с ${\displaystyle |E(\mathbb {F} _{q})|=q}$ уязвимы для атаки, которая отображает точки данной кривой в аддитивную группу поля ${\displaystyle \mathbb {F} _{q}}$.

Быстрая редукция (NIST-кривые)

Деление по модулю p (которое необходимо для операций сложения и умножения) может выполняться быстрее, если в качестве p выбрать простое число, близкое к степени числа 2. В частности, в роли p может выступать простое число Мерсенна. Например, хорошим выбором являются ${\displaystyle p=2^{251}-1}$ или ${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1}$. Национальный институт стандартов и технологий (NIST) рекомендует использовать подобные простые числа в качестве p.

Ещё одним преимуществом кривых, рекомендованных NIST, является выбор значения ${\displaystyle a=-3}$, что ускоряет операцию сложения в координатах Якоби.

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

NIST рекомендует 15 эллиптических кривых, многие из которых были получены Jerry Solinas (NSA) на базе наработок Нила Коблица^[10]. В частности, FIPS 186-3^[11] рекомендует 10 конечных полей. Некоторые из них:

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

Причём для каждого конечного поля рекомендуется одна эллиптическая кривая. Эти конечные поля и эллиптические кривые выбраны, как часто ошибочно считается, из-за высокого уровня безопасности. По заявлениям NIST, их выбор был обоснован эффективностью программной реализации^[13]. Имеются сомнения в безопасности по крайней мере нескольких из них^[14][15][16].

Размер ключа

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

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

Аналог обмена ключами по алгоритму Диффи-Хеллмана

Предположим, что абоненты А и Б хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего, они открыто выбирают какое-либо конечное поле ${\displaystyle F_{q}}$ и какую-либо эллиптическую кривую ${\displaystyle E}$ над ним. Их ключ строится по случайной точке ${\displaystyle P}$ на этой эллиптической кривой. Если у них есть случайная точка ${\displaystyle P}$, то, например, её ${\displaystyle x}$-координата дает случайный элемент ${\displaystyle F_{q}}$, который можно затем преобразовать в ${\displaystyle r}$-разрядное целое число в ${\displaystyle p}$-ичной системе счисления (где ${\displaystyle rq=p}$ ), и это число может служить ключом в их классической криптосистеме. Они должны выбрать точку ${\displaystyle P}$ так, чтобы все их сообщения друг другу были открытыми и все же никто, кроме них двоих, ничего бы не знал о ${\displaystyle P}$.

Абоненты (пользователи) А и Б первым делом открыто выбирают точку ${\displaystyle B}$ ∈ ${\displaystyle E}$ в качестве «основания»; ${\displaystyle B}$ играет ту же роль, что образующий ${\displaystyle q}$ в системе Диффи-Хеллмана для конечных полей. Однако, не требуем, чтобы ${\displaystyle B}$ была образующим элементом в группе точек кривой ${\displaystyle E}$. Эта группа может и не быть циклической. Даже если она циклическая, не будем тратить время на проверку того, что ${\displaystyle B}$ — образующий элемент (или даже на нахождение общего числа N точек, которое нам не понадобится в последующем). Нам хотелось бы, чтобы порожденная В подгруппа была большой, предпочтительно того же порядка величины, что и сама ${\displaystyle E}$. Пока что предположим, что ${\displaystyle B}$ — взятая открыто точка на ${\displaystyle E}$ весьма большого порядка (равного либо ${\displaystyle N}$, либо большому делителю ${\displaystyle N}$).

Чтобы образовать ключ, ${\displaystyle A}$ вначале случайным образом выбирает целое число ${\displaystyle a}$, сравнимое по порядку величины с ${\displaystyle q}$ (которое близко к ${\displaystyle N}$); это число он держит в секрете. Он вычисляет ${\displaystyle aB}$ ∈ ${\displaystyle E}$ и передает эту точку открыто. Абонент Б делает то же самое: он выбирает случайно ${\displaystyle b}$ и открыто передает ${\displaystyle bB}$ ∈ ${\displaystyle E}$. Тогда используемый ими секретный ключ — это ${\displaystyle P=abB}$ ∈ ${\displaystyle E}$. Оба пользователя могут вычислить этот ключ. Например, ${\displaystyle A}$ знает ${\displaystyle bB}$ (точка была передана открыто) и своё собственное секретное ${\displaystyle a}$. Однако любая третья сторона знает лишь ${\displaystyle aB}$ и ${\displaystyle bB}$. Кроме решения задачи дискретного логарифмирования — нахождения а по ${\displaystyle B}$ и ${\displaystyle aB}$ (или нахождения ${\displaystyle b}$ по ${\displaystyle B}$ и ${\displaystyle bB}$) по-видимому, нет способа найти ${\displaystyle abB}$, зная лишь ${\displaystyle aB}$ и ${\displaystyle bB}$^[17].

Пример обмена ключами по схеме Диффи-Хеллмана

В качестве примера возьмем

${\displaystyle p=211}$, ${\displaystyle E_{p}(0,-4)}$,

что соответствует кривой

Безопасность криптографии с использованием эллиптических кривых

Безопасность, обеспечиваемая криптографическим подходом на основе эллиптических кривых, зависит от того, насколько трудной для решения оказывается задача определения ${\displaystyle k}$ по данным ${\displaystyle kP}$ и ${\displaystyle P}$. Эту задачу обычно называют задачей дискретного логарифмирования на эллиптической кривой. Наиболее быстрым из известных на сегодня методов логарифмирования на эллиптической кривой является так называемый ${\displaystyle p}$-метод Полларда. В таблице (см. ниже) сравнивается эффективность этого метода и метод разложения на простые множители с помощью решета в поле чисел общего вида. Из нее видно, что по сравнению с RSA в случае применения методов криптографии на эллиптических кривых примерно тот же уровень защиты достигается со значительно меньшими значениями длины ключей.

К тому же, при равных длинах ключей вычислительные усилия, требуемые при использовании RSA и криптографии на основе эллиптических кривых, не сильно различаются. Таким образом, в сравнении с RSA при равных уровнях защиты явное вычислительное преимущество принадлежит криптографии на основе эллиптических кривых с более короткой длиной ключа^[18].

Таблица: Вычислительные усилия, необходимые для криптоанализа при использовании эллиптических кривых и RSA

• Логарифмирование на эллиптической кривой с помощью ${\displaystyle p}$-метода Полларда.

Размер ключа	MIPS-годы
150	3,8 * 10^10
205	7,1 * 10^18
234	1,6 * 10^28

• Разложение на множители в целых числах с помощью метода решета в поле чисел общего вида.

Размер ключа	MIPS-годы
512	3 * 10^4
768	3 * 10^7
1024	3 * 10^11
1280	3 * 10^14
1536	3 * 10^16
2048	3 * 10^20

Построение электронной цифровой подписи с использованием эллиптических кривых

Алгоритм ECDSA (Elliptic Curve Digital Signature Algorithm) принят в качестве стандартов ANSI X9F1 и IEEE P1363.

Создание ключей

1. Выбирается эллиптическая кривая ${\displaystyle E_{p}(a,b)}$. Число точек на ней должно делиться на большое простое число n.
2. Выбирается базовая точка ${\displaystyle G\in E_{p}(a,b)}$ порядка ${\displaystyle n,n\cdot G=\infty }$.
3. Выбирается случайное число ${\displaystyle d\in (1,n)}$.
4. Вычисляется ${\displaystyle Q=d\cdot G}$.
5. Закрытым ключом является d, открытым ключом — кортеж <a, b, G, n, Q>.

Создание подписи

1. Выбирается случайное число ${\displaystyle k\in (1,n)}$.
2. Вычисляется ${\displaystyle k\cdot G=(x_{1},y_{1})}$ и ${\displaystyle r=x_{1}(\operatorname {mod} n)}$.
3. Проверяется условие ${\displaystyle r\neq 0}$, так как иначе подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k.
4. Вычисляется ${\displaystyle k^{-1}(\operatorname {mod} n)}$.
5. Вычисляется ${\displaystyle s=k^{-1}\cdot (H(M)+dr)(\operatorname {mod} n)}$.
6. Проверяется условие ${\displaystyle s\neq 0}$, так как в этом случае необходимого для проверки подписи числа ${\displaystyle s^{-1}(\operatorname {mod} n)}$ не существует. Если s = 0, то выбирается другое случайное число k .

Подписью для сообщения М является пара чисел (r, s).

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

1. Проверим, что числа r и s принадлежат диапазону чисел (1, n). В противном случае результат проверки отрицательный, и подпись отвергается.
2. Вычислить ${\displaystyle w=s^{-1}(\operatorname {mod} n)}$ и H(M).
3. Вычислить ${\displaystyle u_{1}=H(M)w(\operatorname {mod} n)}$ и ${\displaystyle u_{2}=rw(\operatorname {mod} n)}$.
4. Вычислить ${\displaystyle u_{1}G+u_{2}Q=(x_{0},y_{0}),v=x_{0}(\operatorname {mod} n)}$.
5. Подпись верна в том и только том случае, когда v = r^[19].

Приложения

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

• алгоритм ECDSA, основывающийся на ЭЦП,
• алгоритм ECDH, основывающийся на алгоритме Диффи — Хеллмана,
• алгоритм ECMQV, основывающийся на MQV, протоколе распределения ключей Менезеса-Кью-Венстоуна,
• ГОСТ Р 34.10-2012,
• факторизация Ленстры с помощью эллиптических кривых,
• dual EC DRBG.

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

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

Примечания

1. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography. — Springer, 2008. — 524 с. — (Undergraduate Texts in Mathematics). — ISBN 9780387779942.
2. Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А.. Элементарное введение в эллиптическую криптографию. 11 с.
3. "Кодирование чисел в точки на эллиптической кривой в конечном поле и шифрование-дешифрование их". Дата обращения: 29 октября 2019.
4. Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. 167 с.
5. "Эллиптическая криптография: теория". Архивировано 13 октября 2016. Дата обращения: 13 октября 2016.
6. Recommended Elliptic Curves for Government Use  (неопр.). Дата обращения: 16 декабря 2009. Архивировано 5 июня 2011 года.
7. SEC 2: Recommended Elliptic Curve Domain Parameters
8. Schoof's algorithm (недоступная ссылка)
9. Schoof–Elkies–Atkin algorithm
10. Neal Koblitz. Random Curves: Journeys of a Mathematician. — Springer, 2009. — С. 312-313. — 402 с. — ISBN 9783540740780.
11. FIPS 186-3 Архивировано 7 октября 2013 года. // NIST, 2009; устарел в 2013 году с выходом FIPS 186-4
12. Может показаться, что в этой последовательности допущена ошибка. Однако, последняя величина именно 521, а не 512 битов.
13. Daniel J. Bernstein, Tanja Lange, Security dangers of the NIST curves Архивная копия от 20 декабря 2015 на Wayback Machine // 2013.09.16: "Why did NIST choose these curves? * Most people we have asked: security * Actual NIST design document: eficiency" ([1] Архивная копия от 20 декабря 2013 на Wayback Machine)
14. Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe curves for elliptic-curve cryptography. (англ.). safecurves.cr.yp.to (18 ноября 2013). Дата обращения: 20 декабря 2013. Архивировано 20 декабря 2013 года.
15. Евгений Золотов (2013-09-16). "Сноуден и эллиптическое крипто: Bitcoin и TOR вне подозрений, но что с другими проектами?". Компьютерра. Архивировано 20 декабря 2013. Дата обращения: 20 декабря 2013.
16. Dr Michael Scott, Backdoors in NIST elliptic curves Архивная копия от 20 декабря 2013 на Wayback Machine, Oct 24, 2013: "The curves themselves were suggested by Jerry Solinas who worked at the NSA."
17. Чалкин Т.А. Жданов О.Н. Применение эллиптических кривых в криптографии.
18. Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. 186 с.
19. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел.99 с.
20. Bos et al, Elliptic Curve Cryptography in Practice Архивная копия от 7 февраля 2016 на Wayback Machine // MSR-TR-2013-119, November 2013

Ссылки

• Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Алгоритмические основы эллиптической криптографии. — Москва: МЭИ, 2000. — 100 с.
• Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы.. — Москва: КомКнига, 2006. — 328 с.
• Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. — Красноярск: «Город», 2007. — 217 с.
• Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. — Казань: КФУ, 2011. — 190 с.
• Koblitz N.A. Course in number theory and cryptography.. — USA: Springer-Verlag, 1994. — 235 с.