elikaski/ecc_attacksИзвестные атаки на криптографию на эллиптических кривых
В последние годы подход криптографии на эллиптических кривых стал популярным благодаря своей высокой эффективности и высокой стойкости. Цель этой статьи — представить данную тему в относительно более ясном виде, чем она представлена сегодня в интернете.
В этой статье я расскажу, что такое эллиптические кривые, какие основные операции можно выполнять над ними и как их можно использовать в криптографическом контексте. Большая часть статьи состоит из примеров известных атак на некорректные реализации или неправильные применения этих кривых. На протяжении всей статьи я стараюсь разделять объяснение на интуитивно понятную часть высокого уровня и математическую часть, в которой рассматриваются более детальные аспекты. Читателю предлагается сосредоточиться на той части, которая интересует его в данном месте, и пропустить менее интересные.
Приятного чтения!
В общем случае эллиптическая кривая — это некоторая изогнутая линия. Примером такой линии является парабола, уравнение которой имеет вид $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$, и выглядит она так:
В контексте криптографии принято использовать эллиптические кривые, уравнение которых имеет вид
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Например, эллиптическая кривая, соответствующая уравнению $𝑦^2 = 𝑥^3 − 3𝑥 + 3$, выглядит так:
Уравнение кривой определяет связь между координатой 𝑥 точки на кривой и её координатой 𝑦. В криптографическом контексте мы ограничиваем 𝑥, 𝑦, 𝑎, 𝑏 целыми числами и выполняем вычисления по модулю некоторого большого простого числа. Таким образом, уравнение эллиптической кривой имеет вид:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Это означает, что на кривой имеется конечное число точек. На математическом языке говорят, что кривая определена над конечным полем порядка 𝑝. В результате теперь не обязательно каждой координате 𝑥 будет соответствовать точка на кривой, поскольку соответствующая ей координата 𝑦 может не быть целым числом.
Множество точек на кривой состоит из пар целых чисел (𝑥, 𝑦), удовлетворяющих уравнению кривой. Помимо этих точек, определяется ещё одна особая точка, называемая «бесконечностью», которая обозначается через 𝒪. На математическом языке эта точка является нейтральным элементом множества точек на кривой относительно операции сложения, которую мы определим в следующем разделе. Число точек на кривой (включая точку 𝒪) называется «порядком кривой».
Ещё одно наблюдение заключается в том, что эллиптические кривые симметричны относительно оси X. Это означает, что если точка 𝑃 = (𝑥, 𝑦) находится на кривой, то точка −𝑃 = (𝑥, −𝑦) также находится на кривой. Фактически эти точки считаются «обратными» друг другу (отсюда обозначение −𝑃 для второй точки), и результат операции сложения между ними определяется как нейтральный элемент 𝒪.
Теорема, называемая теоремой Хассе, даёт оценку #𝐸 — порядка кривой, который имеет порядок величины Θ(𝑝). Более точно:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Имея две точки на кривой, можно определить операцию сложения между ними, результатом которой является третья точка, также лежащая на кривой. Чтобы найти эту точку геометрически, мы проводим линию между двумя заданными точками и продолжаем её до тех пор, пока она не пересечёт кривую в третьей точке. Эта точка отражается относительно оси 𝑋, и полученная точка определяется как результат сложения.
Вот диаграмма, показывающая, как, имея точки 𝑃 и 𝑄, можно найти точку 𝑃 + 𝑄:
Вопрос, который может возникнуть из этого описания: что произойдёт, если линия, проведённая между двумя точками, больше не пересечёт кривую? В этом случае говорят, что линия пересекает кривую в «бесконечности», и результатом сложения является точка 𝒪. Заметим, что этот случай возникает, если проведённая линия вертикальна, то есть мы пытаемся сложить точку 𝑃 с обратной ей точкой, −𝑃:
Из этого выводятся два основных тождества. Для каждой точки 𝑃 выполняется:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Ещё один вопрос, возникающий из геометрического описания: как сложить точку саму с собой? Мы видели, что для сложения двух различных точек 𝑃 и 𝑄 мы проводим линию между ними и смотрим на точку пересечения её продолжения с кривой. Интуитивно мы оставим 𝑃 неизменной и будем рассматривать линию, которая образуется по мере того, как 𝑄 приближается «всё ближе и ближе» к 𝑃, пока 𝑄 не сольётся с 𝑃. В результате мы получим линию, которая становится всё более «касательной» к кривой в точке 𝑃, и именно эту линию мы будем рассматривать, когда захотим сложить 𝑃 саму с собой:
Чтобы сложить точку 𝑃 саму с собой, мы проводим касательную к кривой в точке 𝑃 и продолжаем её до пересечения с кривой во второй точке. Эта точка отражается относительно оси 𝑋, и полученная точка определяется как результат сложения. Результат сложения принято обозначать как 𝑃 + 𝑃 = 2𝑃. Опять же, если касательная не пересекает кривую во второй точке, то говорят, что она пересекает кривую в «бесконечности», и в этом случае результатом сложения является точка 𝒪.
Эти наглядные геометрические описания хорошо иллюстрируют и помогают понять, как работает сложение точек. Но как же мы вычисляем его на самом деле? Конечно же, с помощью математических уравнений!
Пусть даны точки $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ и $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$. Результатом их сложения является точка $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ такая, что:
