Математические байки

Итак, пусть у нас есть большое число N, и пусть для простоты оно есть произведение двух простых, N=pq. Китайская теорема об остатках учит нас, что кольцо вычетов по модулю N это не поле -- но декартово произведение двух полей, вычетов по модулю p и по модулю q. И "эллиптическая кривая", которую мы зададим каким-нибудь уравнением, будет декартовым произведением того, что это уравнение задаёт по модулю p и по модулю q.

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

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

https://en.wikipedia.org/wiki/Dual_EC_DRBG — а это к тому, что выбор публичной точки/кривой это вопрос тонкий... Цитата из Брюса Шнайдера, https://www.schneier.com/blog/archives/2013/12/nsa_spying_who.html :

Естественно, что за всем этим стоит ещё безумное количество деталей — в которые я вдаваться не буду; оставлю тут только ещё две ссылки: https://en.wikipedia.org/wiki/Curve25519 — одна конкретная эллиптическая кривая. Вот прямо явно выписанная:

(см.: https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman#Key_establishment_protocol )

Да — естественно, поскольку степень a (я буду писать именно «степень», а не «множитель», потому что хочу думать о точках эллиптической кривой как о группе, пусть и коммутативной) большая, то aP вычисляется не как P+P+…+P сложением a раз, а так же, как любая другая большая степень в группе — чередой удвоений (2^100 P =2 (2(…(2 P))) ), разложением a в двоичную запись и сложением соответствующих удвоений. Собственно, если бы степень a была столь маленькой, что можно было бы до неё «досчитать» просто сложением P+P+…+P, то это же мог бы проделать и атакующий — складывать P, пока не увидит совпадающий с переданным по открытому каналу результатом aP. И всё, атакующий знает секрет a.

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

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

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

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

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

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

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

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