Я новичок в криптографии на эллиптических кривых и работаю над задачей CTF, в которой используются эллиптические кривые. В настоящее время я пытаюсь найти генератор, $G$, и мне даны открытый и закрытый ключи, $P$ и $к$, ул. $P = [k]G$, а также еще одна случайная точка на кривой. Я знаю порядок, $n$, группы, и я знаю два простых числа, $р$ и $q$, которые являются единственными факторами $n$.
я читать что если у вас есть закрытый и открытый ключи, вы можете вычислить генератор как...
$$G = [k^{-1}]P\pmod n$$
... куда $k^{-1} = n - k$.
Это все здорово, но, к сожалению, я не знаю параметров, $а$ и $b$, эллиптической кривой, $у^2 = х^3 + топор + б$, поэтому у меня возникают проблемы с умножением точек EC на $к^{-1}$.
Я подумал, что, поскольку я знаю значения двух точек на кривой, у меня по существу есть следующая система линейных уравнений:
\начать{выравнивать}
y_1^2 &= x_1^3 + ax_1 + b\
y_2^2 &= x_2^3 + ax_2 + b\
\end{выравнивание}
Я попытался решить это с помощью решателя теоремы z3, но получил ответ, утверждающий, что система неудовлетворительна. Затем я попытался изменить свою систему уравнений так, чтобы обе части уравнения рассчитывались по модулю. $n$, но это привело к тому, что z3 долго не мог найти решение, предположительно потому, что $а$ и $b$ являются 128-битными числами и $n$ представляет собой 512-битное число. Это заставило меня вспомнить мои уроки информатики в бакалавриате, где я изучал различные проблемы в области информатики, и это похоже на Целочисленное программирование, который является NP-полным.
Следовательно, можно ли эффективно вычислить параметры, $а$ и $b$, эллиптической кривой, если я знаю порядок $n$ и две точки $P$ и $Q$ на кривой?