În „Iau 3072 pentru Paillier’s $n$", 3072 este cu siguranță dimensiunea biților a $n$. Astfel, voi citi întrebarea ca:
Cât de lățime ar trebui să fie OU $n=p^2q$ să fie la fel de sigur ca a lui Paillier $n=pq$ de 3072 de biți?
Cel mai cunoscut atac împotriva ambelor criptosisteme este factorizarea $n$.
Cea mai cunoscută metodă de factorizare pentru $n=pq$ cu $p$ și $q$ numere prime aleatorii de aproximativ aceeași dimensiune este GNFS, de cost $L_n[1/3,4\cdot3^{-2/3}]$, per Notaţia L.
Pentru factorizarea $n=p^2q$, GNFS funcționează și cu costuri similare, așa că trebuie să avem $n$ cel puțin 3072 de biți. In orice caz, ECM-ul lui Lenstra este de asemenea de luat în considerare și (cred) costul este de aproximativ $L_{\min(p,q)}[1/2,2^{1/2}]$. Astfel, pentru a maximiza rezistența la acel algoritm ulterior ar trebui să avem $p$ și $q$ de aproape aceeași dimensiune. Acea dimensiune trebuie să fie de cel puțin 1024 de biți pentru a obține un 3072 de biți $n$. Și dacă facem calculul și ignorăm $o(1)$ în $L_k[\alpha,c]=e^{(c+o(1))\ln(k)^\alpha\ln(\ln(k))^{1-\alpha}}$, obținem acel 1024 de biți $p$ și $q$ este (abia) suficient pentru ca ECM să fie mai costisitor decât GNFS.
Prin urmare ar trebui să avem $p$ și $q$ de cel puțin 1024 de biți, de ex. in raza de actiune $[2^{1024-1/3},2^{1024}]$ pentru 3072 de biți $n$. Dacă vrem să greșim pe partea sigură pentru că am ignorat $o(1)$, putem lovi asta puțin de ex. 1152 de biți, de ex. in raza de actiune $[2^{1152-1/3},2^{1152}]$ pentru 3456 de biți $n$.
Același calcul acceptă Citatul misterios al căpitanului Nemo „RSA Moduli ar trebui să aibă 3 factori primi”..
Adăugare: dovezi justificative în Mathematica, producând 0,5⦠(respectiv 10,3â¦) pentru logaritmul de bază 2 al raportului de lucru dintre factorii ECM @1024-bit (resp. @1152 biți), la lucrul pentru Produs GNFS @3072-bit. Încearcă online!.
L[n_, a_, c_] := Exp[c (Log[n]^a) (Log[Log[n]]^(1-a))];
LGNFS[n_] := L[n, 1/3, 4 3^(-2/3)];
LLenstra[p_] := L[p, 1/2, 2^(1/2)];
Jurnal[2., LLenstra[2^{1024,1152}]/LGNFS[2^3072]]
