Putem inversa funcția curbă eliptică mul?

Am un sistem de curbe eliptice cu un singur punct P. Să presupunem că clientul A și serverul B generează un secret R1 și R2.

A trimite X1 = mul(R1, P) către B și B trimite X2 = mul(R2, P) către A atunci secretul partajat este același pentru ambele: S = X1R2 = X2R1

Sistemul are un singur punct și am X1,X2 și P. Încerc să calculez secretul partajat, calculând R1 și R2. Cu toate acestea, funcția de curbă este greu de inversat din cauza n = n // 2.

Functia :

#R este numărul privat generat de partea client/server
# P este punctul
def mul(R, P):
         
        Q = P.copie()
        Q2 = PointInf()
        în timp ce R > 0:
            dacă R % 2 == 1:
                Q2 = adăugați (Q2, Q)
            Q = adăugați (Q, Q)

            R //= 2
    
        întoarce Q2

Pe numărul mic n, putem inversa cu ușurință funcția și găsim R pentru că nu există multă iterație, astfel încât să putem face o aproximare și apoi forța brută, dar ce putem face pentru R mare (cazul meu este de 175 de iterații) .

Este posibil asta din punct de vedere matematic?

Ceea ce descrii este Diffie-Hellman pe un grup cu neutru PointInf() [se notează în continuare $\infty$] și legea adăuga() [se notează în continuare $\boxplus$]. Declarația problemei nu spune care, dar titlul sugerează un grup de curbe eliptice pe un câmp finit. Funcţie mul(R, P) calculează înmulțirea scalară $R\boxtimes P=\underbrace{P\boxplus \ldots\boxplus P}_{R\text{ termeni}}$. Din asociativitatea lui $\boxplus$ urmează $R\boxtimes P$ este bine definit, și asta $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)$ [Unde $\ori$ este înmulțirea întregului].

Încerc să calculez secretul partajat, prin calcul $R_1$ și $R_2$.

$R_2\boxtimes P$ și $R_1\boxtimes P$ sunt cunoscute, astfel încât un atacator trebuie doar să calculeze $R_1$ sau $R_2$ pentru a recupera cele partajate $S$.

Pe număr mic $n$, putem inversa cu ușurință funcția și găsim $R$ pentru că nu există multe iterații, așa că putem face o aproximare și apoi forța brută, dar ce putem face pentru mare $R$ (cazul meu este de 175 de iterații).

Dacă într-adevăr suntem pe o curbă eliptică peste un câmp finit, nu văd cum putem „face o aproximare”. Le voi presupune pe amândouă $R_i$ sunt aleatorii în $[0,n)$ cu $n\boxtimes P=\infty$ sau un interval similar și $\log_2(n)\aproximativ175$.

Putem inversa multiplicarea curbei eliptice?

Găsind $R$ dat $R\boxtimes P$ și $P$ este problema logaritmului discret. Este cel mai cunoscut general metoda de a gasi $S$. Cel mai cunoscut general metodele de rezolvare a DLP (de exemplu, rho-ul lui Pollard distribuit cu puncte distincte) au costuri de ordinul $2\sqrt n$ adăugiri, iar asta nu este la îndemână (cu excepția cazului în care se pot investi miliarde în proiectarea, producerea și funcționarea echipamentelor specializate). in orice caz

• există algoritmi mult mai buni pentru unele curbe eliptice (de exemplu, supersingular sau când $n$ este compus).
• poate unul dintre $R_i$ nu este chiar întâmplător
• poate unele scurgeri de informații suplimentare (cum ar fi timpul necesar pentru calculul $R\boxplus P$, sau liniile cache ale CPU utilizate de acel calcul; ambele ar putea ajuta).
• sau poate că acesta este un CTF deformat și problema nu necesită găsire $S$.