Естественно, что за всем этим стоит ещё безумное количество деталей — в которые я вдаваться не буду; оставлю тут только ещё две ссылки:
https://en.wikipedia.org/wiki/Curve25519 — одна конкретная эллиптическая кривая. Вот прямо явно выписанная:
https://en.wikipedia.org/wiki/Curve25519 — одна конкретная эллиптическая кривая. Вот прямо явно выписанная:
https://en.wikipedia.org/wiki/Dual_EC_DRBG — а это к тому, что выбор публичной точки/кривой это вопрос тонкий... Цитата из Брюса Шнайдера, https://www.schneier.com/blog/archives/2013/12/nsa_spying_who.html :
Я не знаю, и не могу знать, так ли это — повторюсь, совсем не моя область — и что специалисты знают сейчас, шесть лет спустя. Но возможности "плохих кривых" как минимум вполне обсуждаемы:
Вот. Несмотря на все эти тонкости — по крайней мере, как в принципе работают эллиптические кривые "на стороне общающихся", мы посмотрели.
А теперь давайте вернёмся к другой математике, к обещанному в самом начале методу Ленстры : к эллиптическим кривым на стороне нападающего в классической задаче разложения на множители.
А теперь давайте вернёмся к другой математике, к обещанному в самом начале методу Ленстры : к эллиптическим кривым на стороне нападающего в классической задаче разложения на множители.
Итак, пусть у нас есть большое число N, и пусть для простоты оно есть произведение двух простых, N=pq.
Китайская теорема об остатках учит нас, что кольцо вычетов по модулю N это не поле -- но декартово произведение двух полей, вычетов по модулю p и по модулю q. И "эллиптическая кривая", которую мы зададим каким-нибудь уравнением, будет декартовым произведением того, что это уравнение задаёт по модулю p и по модулю q.
Китайская теорема об остатках учит нас, что кольцо вычетов по модулю N это не поле -- но декартово произведение двух полей, вычетов по модулю p и по модулю q. И "эллиптическая кривая", которую мы зададим каким-нибудь уравнением, будет декартовым произведением того, что это уравнение задаёт по модулю p и по модулю q.
Пусть у нас есть такая кривая и точка Q на ней.
Причём кривую мы будем брать вида y^2=P(x) -- с нулём на "вертикальной бесконечности".
Давайте умножать точку Q на разные множители -- в групповом смысле, возводить её в степень, причём не 2-3-4, а с большим количеством разных делителей. Если бы у нас и впрямь была группа -- то мы бы в какой-то момент ("выбрав" все делители порядка Q) пришли бы в нейтральный элемент -- то есть улетели бы на бесконечность.
Но у нас такая картина происходит с одной кривой mod p, и с другой mod q.
Что, если мы уже исчерпали порядок Q по одному модулю, но не по другому?
Формула для суммы точек рациональная -- там есть знаменатель:
Когда мы убегаем на бесконечность (как раз сваливаясь в нейтральный элемент группы) -- он обращается в ноль.
А вообще, когда мы делим в кольце вычетов по модулю n, мы вычисляем алгоритмом Евклида обратный элемент к знаменателю D (после чего соотношение aD-bn=1 как раз и говорит, что 1/D = a по модулю n).
Математические байки
Что, если мы уже исчерпали порядок Q по одному модулю, но не по другому?
И когда мы по модулю p убегаем на бесконечность, а по модулю q нет — знаменатель по модулю p ноль, а по модулю q нет. И алгоритм Евклида вместо 1 выдаёт нам p — то есть мы нашли на делитель n. Ура!
Вот такая прекрасная история — эллиптические кривые приводят к тому, что поскладывав точки на эллиптической кривой, мы «естественным образом» натыкаемся на делитель n.
Кстати — ещё можно спросить, а как мы вообще берём пару из эллиптической кривой и точки на ней? Скажем, если мы сначала напишем уравнение кривой,
y^2=x^3+ax+b,
то неясно, как на ней искать точки. Если выбрать x и пытаться извлечь квадратный корень по модулю n из правой части — так это задача более-менее той же огромной сложности (потому что по модулю n=pq разных квадратных корней 4, а не 2, и найти для m^2 два других корня, кроме (m,-m), равносильно разложению n на множители).
Но есть простой ответ: можно, как тот ковбой из анекдота, сначала стрелять, а потом уже рисовать круги вокруг попаданий. Берём любые (x,y,a), и полагаем b:=y^2-x^3-ax. Готово, у нас есть и эллиптическая кривая, и точка (x,y) на ней.
y^2=x^3+ax+b,
то неясно, как на ней искать точки. Если выбрать x и пытаться извлечь квадратный корень по модулю n из правой части — так это задача более-менее той же огромной сложности (потому что по модулю n=pq разных квадратных корней 4, а не 2, и найти для m^2 два других корня, кроме (m,-m), равносильно разложению n на множители).
Но есть простой ответ: можно, как тот ковбой из анекдота, сначала стрелять, а потом уже рисовать круги вокруг попаданий. Берём любые (x,y,a), и полагаем b:=y^2-x^3-ax. Готово, у нас есть и эллиптическая кривая, и точка (x,y) на ней.