Можем ли мы обратить функцию mul на эллиптической кривой?

У меня есть система эллиптических кривых только с одной точкой P. Допустим, клиент A и сервер B генерируют секреты R1 и R2.

A отправляет X1 = mul(R1, P) в B, а B отправляет X2 = mul(R2, P) в A тогда общий секрет одинаков для обоих: S = X1Р2 = Х2R1

В системе есть только одна точка, и у меня есть X1, X2 и P. Я пытаюсь вычислить общий секрет, вычислив R1 и R2. Однако функцию кривой трудно обратить из-за того, что n = n // 2.

Функция :

#R — частный номер, сгенерированный на стороне клиент/сервер.
# P - точка
деф мул(R, P):
         
        Q = P.copy()
        Q2 = PointInf()
        в то время как R > 0:
            если R % 2 == 1:
                Q2 = добавить (Q2, Q)
            Q = добавить (Q, Q)

            Р //= 2
    
        возврат Q2

При небольшом числе n мы можем легко обратить функцию и найти R, потому что итераций не так много, поэтому мы можем сделать аппроксимацию, а затем перебор, но что мы можем сделать для большого R (мой случай — 175 итераций).

Это математически возможно?

То, что вы описываете, это Диффи-Хеллман в какой-то группе с нейтральным PointInf() [далее отмечено $\infty$] и закон Добавлять() [далее отмечено $\боксплюс$]. В постановке задачи не сказано, какой, но название предполагает группу эллиптических кривых над некоторым конечным полем. Функция мул (R, P) вычисляет скалярное умножение $R\boxtimes P=\underbrace{P\boxplus \ldots\boxplus P}_{R\text{terms}}$. От ассоциативности $\боксплюс$ следует $R\boxtimes P$ четко определено, и что $R_1\boxtimes (R_2\boxtimes P)=(R_1\times R_2)\boxtimes P=(R_2\times R_1)\boxtimes P=R_2\boxtimes (R_1\boxtimes P)$ [куда $\раз$ целочисленное умножение].

Я пытаюсь вычислить общий секрет, вычислив $R_1$ и $R_2$.

$R_2\boxtimes P$ и $R_1\boxtimes P$ известны, поэтому злоумышленнику нужно только вычислить $R_1$ или же $R_2$ для восстановления общего $S$.

На малом количестве $n$, мы можем легко обратить функцию и найти $R$ потому что итераций не так много, поэтому мы можем сделать приближение, а затем брутфорс, но что мы можем сделать для больших $R$ (в моем случае 175 итераций).

Если мы действительно находимся на эллиптической кривой над некоторым конечным полем, я не понимаю, как мы можем «сделать приближение». Я предполагаю, что оба $R_i$ случайны в $[0,n)$ с $n\boxtimes P=\infty$ или аналогичный интервал, и $\log_2(n)\приблизительно175$.

Можем ли мы обратить умножение на эллиптической кривой?

Нахождение $R$ данный $R\boxtimes P$ и $P$ это проблема дискретного логарифма. Это самый известный генеральный способ найти $S$. Самый известный генеральный методы решения DLP (например, распределенное ро Полларда с выделенными точками) имеют стоимость порядка $2\кв.п$ дополнения, и это недостижимо (если только вы не можете инвестировать миллиарды в проектирование, производство и эксплуатацию специализированного оборудования). Однако

• существуют гораздо лучшие алгоритмы для некоторых эллиптических кривых (например, суперсингулярные или когда $n$ является составным).
• возможно, один из $R_i$ на самом деле не случайно
• возможно, какие-то дополнительные утечки информации (например, время, необходимое для вычисления $R\boxplus P$, или строки кэша ЦП, используемые этим вычислением; оба могут помочь).
• или, возможно, это коварный CTF, и проблема не требует поиска $S$.