TLDR: если мы специализируемся на точке генератора $G$ группы эллиптических кривых простого порядка, мы можем последовательно определять НОД двух точек для этого генератора. Но мы не можем эффективно найти это для произвольных точек и группы криптографических интересов, где проблема дискретного логарифма сложна.
Прежде чем найти что-то, мы должны знать, что это такое. Отсюда подвопрос пончо:
Что будет означать «НОД двух точек на простой кривой»?
НОД означает наибольший общий делитель. Таким образом, нам нужно определить три понятия
- Что такое «основная кривая». В этом, изгиб означает Эллиптическая кривая. И основной является свойством либо
- база конечное полепорядок (этот простой порядок часто отмечается $р$, а затем поле представляет собой просто целые числа по модулю $р$);
- порядок кривой, то есть количество элементов в конечная группа точек кривой, включая нейтральную;
- или приказ а подгруппа кривой (тогда часто $n$, как мы это сделаем).
- Понятие «делитель» точки простой эллиптической кривой, которую мы будем считать точкой эллиптической кривой с некоторым свойством, которое необходимо определить.
- Понятие «наибольшей» среди точек эллиптической кривой.
Мы можем определить такие вещи последовательно! Мы утверждаем, что «простая кривая» — это некоторая подгруппа простого порядка $n$ эллиптической кривой (возможно, всей кривой, которая может использовать простое поле; например. secp256k1, секп256р1), и $G$ заданная точка кривой / элемент группы, отличный от нейтрального. Теперь набор из $n$ целые числа в $[0,n)$ изоморфна кривой в силу тривиального изоморфизма $i\mapsto i\,G$ определяется как обычно: $0\,G$ группа нейтральна, $i\,G$ является $((i-1)\,G)+G$ для любой $i\in[1,n)$ с $+$ закон группы.
Мы можем определить «делитель» и «наибольший» на множестве $[0,n)$. И мы можем определить НОД двух элементов этого множества (вместе с несколько произвольным $\НОД(0,0)=0$ ). Затем мы можем использовать этот изоморфизм для определения наибольшего общего делителя двух точек группы эллиптических кривых простого порядка, снабженной образующей точкой $G$.
Другими словами, я определяю НОД точек $P$ и $Q$ как точка, совпадающая с закрытым ключом (для генератора $G$) — это НОД закрытых ключей, совпадающих $P$ и $Q$, с соответствующий закрытый ключ целое число в $[0,n)$.
Если мы сможем эффективно решить задачу дискретного логарифмирования в рассматриваемой группе, то мы сможем эффективно вычислить НОД (мы решим два ДЛП, вычислим НОД целых чисел и вернемся к кривой).
Обновление: в некоторой степени верно обратное. Если мы можем эффективно вычислить НОД Любые две точки $P$ и $Q$, то мы можем использовать этот алгоритм для эффективного вычисления дискретного логарифма. $я$ любой $P$. Скетч: выбираем первые простые числа $r_j$ до тех пор $n<\prod r_j$, и для каждого $j$ мы нашли $i\bmod r_j$ запросив НОД $(P+k\,G,r_j\,G)$ что либо $G$ или же $r_j\,G$, в последнем случае показывая, что $i+k\equiv0\pmod{r_j}$. Затем мы находим $я$ по китайской теореме об остатках. Возможна оптимизация для группировки значительного количества запросов в один. Например. подчиняется $(P+k\,G,30\,G)$ и проверяет, является ли результат $G$, $2\,G$, $3\,G$, $5\,G$, $6\,G$, $10\,G$, $15\,G$ или же $30\,G$. Дальнейшие сокращения возможны путем вычисления дискретного логарифма выходных данных оракула с использованием вариантов Baby-Step/Giant-Step.
Я не знаю никакого применения, ни в криптографии, ни где-либо еще.
