Care este aici parametrul de securitate $1^\kappa$?

Lăsați-l să fie $K$ un algoritm de generare a cheilor care ia $(k,d)$ ca intrare cu $k$ ca lungime de bit pentru $n=pq$ cu $p,q \in \mathbb{P}$ și $d=|p-q|$ ca distanta minima intre $p$ și $q$ (RSA).Care ar fi parametrul de securitate $1^\kappa$?

Ar fi $\kappa=k+d$ sau numai $\kappa=k$ si daca ar fi cazul de ce ar depinde?

Am căutat următoarele link-uri și nu am găsit un răspuns la întrebarea mea:

Ce înseamnă expresia $1^n$ înseamnă ca argument al funcției? De ce generarea cheii necesită o intrare $1^k$, și cum îl reprezint în practică?

Din motive în comentariul meu Presupun că schimbăm întrebarea pentru a defini $δ$ cu $2^\delta<\lvert p-q\rvert$, și $\kappa=k+\delta$. FIPS 186-4 generarea cheilor ar folosi, de exemplu $k=3072$ și $\delta=k/2-100=1436$.

Nu găsesc nicio referință care să discute despre securitatea RSA asimptotică cu o notație de genul $1^k$ care specifică un minim $\lvert p-q\rvert$. Asta-i pentru că:

• Crescând $\delta$ după un anumit punct scade în mod demonstrabil securitatea. De exemplu. pentru $k=3072$ (care ar da aproximativ 128 de biți de securitate simetrică) și $δ=1912$ am avea $\min(p,q)<2^{161}$ și ECM-ul lui Lentra ar permite probabil să trageți acel factor de $n$.
• Argumente simple care cresc $\delta$ îmbunătățește securitatea sunt defecte.
• $\delta=0$ se crede bine.
• Motivul istoric pentru a introduce o limită inferioară pentru $\lvert p-q\rvert$ este că factorizarea Fermat are un cost aproximativ proporțional cu $(p-q)^2/n$ ori un polinom în $k$, prin urmare $\lvert p-q\rvert$ nu trebuie să fie prea mic. S-a sărit de la acest fapt la concluzia că este necesar să se precizeze un minim explicit $\lvert p-q\rvert$, chiar dacă este suficient de demonstrat pentru a preciza asta $p$ și $q$ sunt alese independent și aproximativ uniform dintre numerele prime într-un interval cum ar fi $[2^{(k-1)/2},2^{k/2})$ pentru a asigura că factorizarea Fermat este fără speranță, oricând $k$ este suficient de mare pentru a rezista GNFS (sau PPMPQS, care era cunoscut de mult în 1998, când decizia contestabilă a fost scrisă în ANS X9.31).

După cum se solicită în cometariu Cu toate acestea, presupun că există un motiv să precizez $\delta$, și asta în creștere $\delta$ crește securitatea într-un anumit domeniu. Pentru a nu contrazice faptul din primul punct de mai sus, voi presupune $0\le\delta\le\alpha\,k+\beta$ pentru unele reale $\alpha$ și $\beta$ cu $\alpha\in[0,1)$. În cadrul unei astfel de ipoteze, are sens să se definească $\kappa=k+\delta$și utilizați-l ca parametru de securitate.

Am putea defini generarea de chei RSA pentru un întreg impar constant $e>1$ ca: la intrare $1^\kappa$

1. În timp polinomial, alegeți numere întregi $k$ și $\delta$ cu $\kappa=k+\delta$ și $0\le\delta\le\alpha k+\beta$ (eșuează dacă acest lucru este imposibil); modalitățile adecvate includ $\delta\gets\left\lfloor\frac\alpha2\kappa\right\rfloor$ și $k\gets\kappa-\delta$.
2. Alege $p$ uniform aleatoriu între numere prime $p$ în $[2^{(k-1)/2},2^{k/2})$ cu $\gcd(p-1,e)=1$
3. Alege $q$ uniform aleatoriu între numere prime $q$ în $[2^{(k-1)/2},2^{k/2})$ cu $\gcd(q-1,e)=1$ și $2^\delta<\lvert p-q\rvert$.
4. Calcula $n\obține p\,q$ și $d\obține e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, cheie publică de ieșire $(n,e)$ și cheie privată $(n,d)$.

Este credibil că: pentru orice alegere validă de $e$ în acest algoritm de generare a cheilor, pentru orice polinom $P$, nu există un algoritm Probabilistic Polynomial Time care atunci când $\kappa$ crește întrerupe criptarea RSA cu probabilitate care nu dispare în timp $P(\kappa)$.

Acea presupunere plauzibilă este în mod demonstrabil implicată de o formă comună și mai simplă a conjecturii RSA pentru exponent public fix/mic, care elimină pasul (1.), înlocuiește condiția $2^\delta<\lvert p-q\rvert$ cu $p\ne q$ în pasul (3.) și folosește $k$ unde este $\kappa$. Nu avem nicio dovadă că presupunerile sunt echivalente, dar nici un motiv convingător să credem altfel, astfel încât mulți practicieni și majoritatea teoreticienilor folosesc conjectura mai simplă².

¹ Schiță dovedită: presupunem că există o $e$ și algoritm $\mathcal A$ care rupe criptarea RSA cu probabilitate de nedispărut în timp $P(\kappa)$ atunci când utilizați generarea cheii RSA cu $2^\delta<\lvert p-q\rvert$. Folosim $\mathcal A$ pentru a construi un algoritm $\mathcal A'$ invocând $\mathcal A$ ca subprogram, care pentru același $e$ rupe criptarea RSA cu o oarecare probabilitate în timp $P'(k)$ atunci când utilizați generarea cheii RSA cu $p\ne q$. Probabilitatea nu dispare deoarece $p$ și $q$ indeplineste conditia de asigurare $\mathcal A$ funcționează cu o probabilitate că putem limita inferioară și nu dispare. Putem stabili $P'$ din $P$, $\alpha$ și $\beta$, și asta $P'$ este încă un polinom. $\alpha<1$ intră în joc.

² Adesea condiția $p\ne q$ este de asemenea eliminat, ceea ce introduce posibilitatea ca decriptarea să eșueze.Acest lucru se întâmplă pentru o proporție care dispare de chei generate, dar unele definiții ale unui cifru nu au nicio excludere pentru un astfel de caz de colț, motiv pentru care păstrăm $p\ne q$.