То есть — у нас есть некоторая общеизвестная «начальная точка» P, после чего стороны применяют к ней каждая свой шифр, пересылая друг другу результаты A(P) и B(P), и применяют к полученному от собеседника свой шифр — получая A(B(P)) и B(A(P)).

Если шифры коммутировали — то вот у них и получился общий секретный ключ. Вот только где добыть коммутирующие шифры?

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

Пусть на плоскости нарисована кривая, задаваемая уравнением третьей степени — F(x,y)=0 — и пусть она гладкая: без особых точек, как у « клюва » y^2=x^3, или самопересечения, как у
y^2=x^2(x+1).
Будем называть такую кривую эллиптической.

Если быть более точным, то правильно эллиптическую кривую рассматривать не на обычной плоскости, а на проективной, добавляя к ней «точки на бесконечности».
Можно показать, что проективными преобразованиями такую кривую можно привести к более простому виду:
y^2=P(x),
где P — многочлен степени 3.

В этом виде единственной точкой на бесконечности будет точка на « вертикальной бесконечности » (в направлении (0,1)), к которой эта кривая стремится; кстати — это точка перегиба: касание кривой с бесконечно удалённой прямой третьего порядка.

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

Об этом можно почитать в брошюре Цфасмана и Острика (которую я очень люблю) —
https://www.mccme.ru/mmmf-lectures/books/#book-8 — но « парой штрихов » я это всё расскажу.

Итак: пусть у нас задана какая-то эллиптическая кривая, и заданы две точки на ней. Проведём через них прямую. Ограничение уравнение кривой на неё — это уравнение (в типичном случае) третьей степени, у которого уже есть два корня. Значит, будет и третий —
третья точка пересечения. Так вот, мы определим сложение точек на эллиптической кривой исходя из вот такого правила: сумма трёх точек, лежащих на одной прямой, равна нулю.

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

Теперь понятно, как найти сумму P+Q точек P и Q на кривой — нужно провести прямую PQ, найти третью точку пересечения: (-P-Q). Теперь проведём прямую через (-P-Q) и O — и найдём искомую сумму P+Q.

Очевидно, что такое сложение коммутативно. А вот будет ли оно ассоциативно, правда ли, что (P+Q)+R=P+(Q+R)?

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

(картинка из Цфасмана-Острика)

А доказательство ассоциативности основано на таком факте:
Пусть есть восемь точек достаточно общего положения, и мы возьмём две проходящие через них кривые третьего порядка,
F_1(x,y)=0 и F_2(x,y)=0.
Они пересекаются в девяти ( =3*3, « теорема Безу ») точках, восьми наших, плюс ещё одна девятая. Так вот, тогда любая другая кривая третьего порядка
F(x,y)=0,
проходящая через исходные восемь точек, проходит и через девятую.

И происходит это по очень простой причине: уравнения тех кривых, которые проходят через эти 8 точек, это линейные комбинации F_1 и F_2. Которые, конечно, все обращаются в ноль в общих корнях F_1 и F_2, включая девятую точку.

А вот эта картинка из статьи Н. Васильева в Кванте —
http://kvant.mccme.ru/1987/08/geksagrammy_paskalya_i_kubiche.htm

Эта статья называется "Гексаграммы Паскаля и кубические кривые" — потому что из этой же "теоремы о 9 точках" следует теорема Паскаля: три точки пересечения пар прямых, продолжающих противоположные стороны вписанного шестиугольника, лежат на одной прямой.
Что, собственно, правда не только для шестиугольника, вписанного в окружность, но и в любую другую конику [=кривую второго порядка].

И получается теорема Паскаля очень просто: девять точек это шесть вершин и три точки пересечения пар противоположных сторон, а три кривых третьего порядка это (совсем вырожденные) произведения уравнений сторон
l_1 l_3 l_5 =0 и l_2 l_4 l_6 =0
и чуть менее вырожденная
S*L=0,
где S — уравнение коники (на которой лежат 6 вершин), а L=0 — уравнение прямой, проходящей через две из трёх точек пересечения (и потому по теореме о девяти точках проходящей и через третью — что и доказывает теорему Паскаля).

(Картинка из всё той же статьи Н. Васильева)

Итак, точки на эллиптической кривой можно складывать. Причём — и это важно — эта операция рациональная: если у нас есть координаты двух складываемых точек (и уравнение самой кривой), то координаты суммы через них выражаются как рациональные функции, безо всяких там корней. Потому что нахождение третьего корня кубического уравнения при известных первых двух делается через теорему Виета про коэффициент при x^2, и там нужно только складывать/вычитать/делить, но не извлекать корни.

(Кстати, удвоение точки тоже оказывается "рациональной" операцией — единственное, что нужно сказать, это что прямая PQ в этом случае заменяется на касательную к кривой.)

А раз все операции рациональные — значит, всё то же самое можно делать и над конечными полями. (Давайте на всякий случай вынесем за скобки поля характеристик 2 и 3 — чтобы не контролировать, не могли ли двойки и тройки где-нибудь пробраться в знаменатели наших выражений)...

(Продолжая вчерашнее:)
Ну и теперь понятно, как через эллиптические кривые устроить протокол Диффи-Хеллмана. Пусть у нас публично объявлена эллиптическая кривая над большим конечным полем и точка P на ней. Для создания общего секретного ключа А и Б выбирают по большому числу a и b и вычисляют aP и bP соответственно. После этого А посылает Б точку aP (открыто), а Б посылает А точку bP (тоже открыто). И А вычисляет a(bP), а Б – b(aP), и вот они получили общий секретный ключ abP. Ура!