М28. Криптография эллиптической кривой

Несмотря на свое название, рассматриваемые кривые не являются эллипсами, а относятся к типу

Y² = X³ + aX + b,

где a и b - целые числа. Нас интересуют пары (X,Y), также являющиеся целыми числами. Все вычисления модульные, и выполняются относительно некоторого (очень большого) модуля p. Кривые этого типа могут быть параметризованы с помощью эллиптических функций Вейерштрасса, откуда и происходит данное название.

Так, например, точки (1,5) являются целочисленными точками, лежащими на кривой

Y² = X³ + 2X + 3 (mod 19).

По любой точке (или паре точек) на кривой можно построить новую точку на кривой с использованием касательной (для случая одной точки) или хорды (соединяющей пару точек). Касательная или хорда пересекает кривую в третьей точке, которая должна иметь рациональные координаты. Эти координаты преобразуются в целые числа над GF(p), полем Галуа по модулю p. Так, например, для приведенной выше кривой и p=19 уравнение касательной в точке (1,5) составляет

2Y = X + 9.

Мы находим, что эта касательная снова пересекается с кривой в точке X=-7/4. Это число можно преобразовать в целое число над полем GF(19): поскольку знаменатель этой дроби равен 4, то нам нужно найти такое целое число n, что

4n1(mod 19).

Отсюда мы получаем, что n=5, поскольку 20=119+1; поэтому ‑7/4(‑7)5=‑353(mod 19), и поэтому дробь -7/4 эквивалентна целому значению 3 над полем GF(19). В качестве целого значения X получаем 3, а соответствующее значение Y, получаемое из приведенного выше уравнения касательной, равно 6. Так как

Y²=36, а X³+2X+3=27+6+3=36,

то мы убедились в том, что точки (3,6) действительно лежат на вышеупомянутой кривой. (Нам необходимо только показать, что они лежат на этой кривой над GF(19); на самом деле они лежат на этой кривой (mod p) для всех значений p, но это чистая случайность; обычно это вовсе не так).

Итак, мы нашли на кривой еще одну целочисленную точку. Поскольку все вычисления выполняются по модулю p, то существует лишь конечное число возможных точек (X,Y) с целочисленными координатами. Отсюда вытекает, что данный метод построения новых точек должен в конце концов исчерпать себя. Если начать с некоторой (целочисленной) точки Q(X,Y) на кривой, то можно построить конечное множество точек <Q>, элементы которого мы обозначим через 2Q, 3Q, 4Q,... и т.д. (не следует смешивать их с точками типа (2X,2Y) и т.д.). Например, начиная с точки Q(1,5) на вышеупомянутой кривой, мы с помощью касательной в точке Q только что вычислили следующую точку, 2Q. Продолжая вычисления таким же образом, получим следующие точки:

2Q=(3,6), 4Q=(10,4), 8Q=(12,8), и так далее

(другой пример можно найти в [13.9]).

Допустим, задана точка R(X',Y'), и от нас требуется выяснить, существует ли целое n, такое что R=nQ для некоторой точки из множества <Q>. В этом случае (если только значение простого модуля p не является маленьким) перед нами стоит очень трудная задача. Если R не принадлежит множеству <Q>, то такого значения n не существует. Применяемые значения p обычно превосходят 10⁵⁰, а число опробований, которые необходимо выполнить (за исключением нескольких редких случаев), имеет порядок квадратного корня из p. Благодаря этому данная вычислительная задача становится не по силам даже самому мощному компьютеру.

Метод использования Q, R и n для выработки подписи к сообщению довольно сложный, и поэтому здесь не описан. Сжатое и понятное описание можно найти в [13.9].

Любой, кто желает подробнее изучить эти аспекты теории Галуа, может обратиться к книгам по теории конечных полей. Сам Галуа был в 1832 году убит на дуэли в возрасте 20 лет. Будучи уверенным в том, что его почти наверняка убьют, он в ночь перед дуэлью не спал и написал работу, в которой изложил свои идеи, в надежде, что ее опубликуют. В конце концов эта работа действительно была опубликована в 1848 году. Подробности его жизни и научной работы можно найти в книгах по истории математики, например [13.13].