Dată o CE cu cardinalitate $C=P^3+c$ cu $P$ un prim $P \aprox \sqrt[3]{C}$ și $c>0$.
Dintr-un generator dat $G$ generăm două generatoare suplimentare $F,H$ cu
$$F = P \cdot G$$
$$H = P^2 \cdot G$$
(toate ar genera în continuare o secvență de lungime $P^3+c$)
Dat acum un membru aleatoriu $M_1$ din acel EC putem genera a $P\times P \times P$ cub de membri diferiți cu
$$ M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$
$$ i,j,k \in [0,P-1]$$
$$|\{V_{M_1ijk}\}| = P^3$$
Fiecare alt membru aleatoriu $M_2$ poate fi produs din $M_1$ cu:
$$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H $$
$$ i,j,k \in [0,P]$$
Întrebare:
Dați acum doi membri la întâmplare $M_1,M_2 $ câți pași sunt necesari pentru a găsi cele aferente $i,j,k$ (în timp mediu)? Cum ar funcționa?
Ar fi (mult) mai sigur dacă alegem $P = 2\cdot p+1$ cu $p$ un prim?
Ar fi (mult) mai sigur dacă alegem trei factori primi (secreți). $P_1,P_2,P_3$ in schimb? cu $P_1 \cdot P_2 \cdot P_3 \aprox C$
(Caut estimări aproximative legate de $C,P$ în ($O$-notaţie). Putem de ex. ignorați impactul diferit legat de lungimea de biți la multiplicarea cu 2 numere)
Adversarul știe despre EC folosit, generatoare $G,F,H$ și inversele lor $G^{-1},F^{-1},H^{-1}$, membrii aleatoriu $M_1,M_2$ și structura internă. El nu știe despre $P,d$ dar, deoarece nu există prea multe opțiuni, presupunem că el știe și acest lucru.
Vrea să găsească necunoscut $i,j,k$ pentru cunoscut aleatoriu $M_1,M_2$.
Întrebare secundară: Există restricții ale EC sigure care pot fi utilizate pentru aceasta? De exemplu.
ar M-221 cu $y^2 = x^3+117050x^2+x$ $\bmod p = 2^{221} - 3$ lucrezi pentru asta?
Proces:
Dacă avem doar un singur generator $G$ ar trebui să ia $O(\sqrt{C})$ folosind baby-step-giant-step. Dacă $P$ este cunoscut $i,j,k$ poate fi construit din aceasta.
Cu $F,H$ am putea face o suprafață în jur $M_1$ și o linie dreaptă cu $G$ la $M_2$ până la o intersecție a acestora. Asta ar dura $O(P^2+P)\săgeată la dreapta O(P^2)$ care ar fi mai mare decât $O(\sqrt{C})=O(P\sqrt{P})$. Asa de $F,H$ nici un ajutor aici.
Ar putea acele generatoare $F,H$ ajuta să-l faci cumva mai rapid?
