înregistrare Logare
Puncte:3
avatar Crypto

Cum se calculează securitatea n în n biți a unui algoritm cripto?

drapel ng
ystark

Cred că probabil că pierd termenul, deoarece căutarea acestuia aduce rezultate nu atât de precise. Caut să calculez securitatea pe n-biți, de exemplu, Paillier vs ElGamal vs EC ElGamal, când folosesc o cheie x-bit.

Acest Lucrarea afirmă că „pentru a atinge nivelul de securitate de 128 de biți, în ElGamal se folosesc în mod normal 4096 de biți p și 256 de biți q, în timp ce în Paillier, dimensiunea lui n este în mod normal aleasă să fie de 4096 de biți”.

Cum pot calcula ce valori sunt necesare pentru securitatea pe 256 de biți? Este pur și simplu înmulțit cu doi aici?

221
3 + 0
Puncte:5
ckamath avatar Crypto
drapel ag
ckamath

TLDR: Mărimea grupului/ inelului este dictată de cel mai rapid cunoscut în prezent atac (după cum este explicat în acest articol Wikipedia).

Detalii. Pentru cazul conectării discrete $\mathbb{Z}_p^*$ și factoring $\mathbb{Z}_N^*$, cel mai rapid algoritm cunoscut în prezent este sita de câmp cu număr general (GNFS). GNFS are un timp de rulare de (aproximativ) $L_n(1/3,2)$, Unde $$L_n(\alpha,c):=e^{(c+o_n(1))n^\alpha\ln^{1-\alpha}(n)}$$ este $L$-notaţie și $n$ denotă lungimea de biți a (reprezentarea standard a) $p$ sau $N$ (adică $\lceil(\log(p)\rceil$ și $\lceil(\log(N)\rceil$, respectiv).$^*$ De cand $b$-biți de securitate pentru o schemă înseamnă că ar trebui să ia orice algoritm $2^b$ operațiuni pentru a-l sparge, pentru a calcula $n$ pentru $\mathbb{Z}_p^*$ și $\mathbb{Z}_N^*$ care realizează $128$-biți de securitate pentru care trebuie să rezolvi $$2^{128}\aprox e^{2n^{1/3}\ln^{2/3}(n)}\Leftrightarrow n\ln^2(n)\approx64^3.$$ Acest lucru va oferi o cifră a ceea ce ar trebui să fie dimensiunea modulului - așa cum este calculată în acest răspuns, acesta se dovedește a fi în jur $3072$ biți (sau $4096$ biți pentru a fi pe partea mai sigură?). Deoarece nu cunoaștem mijloace mai bune de a rezolva DDH/CDH (problemele care stau la baza schemelor de tip El-Gamal) decât de a calcula loguri discrete, El-Gamal în (cotat) $\mathbb{Z}_p^*$ trebuie implementat cu numere prime de dimensiune $\aproximativ 3072/4096 $ biți.

În mod similar, din moment ce nu cunoaștem mijloace mai bune de a rezolva problema decizie problema reziduală pătratică în $\mathbb{Z}_{N^2}^*$ (problema care sta la baza Criposistemul lui Paillier) decât să factorizeze $N$, prin același argument de mai sus, trebuie să lucrăm $N$ de mărime $\aproximativ 3072/4096$ biți.

Pentru logul discret în curbele eliptice, cred că nu știm nimic mai bun decât algoritmii generici de log discret (de exemplu, rho lui Pollard) care rulează în timp rădăcină pătrată de dimensiunea grupului. Prin urmare, pentru $128$-biți de securitate a EC-El-Gamal, este suficient să lucrați cu curbe eliptice pe un câmp de dimensiune $2^{256}$. (Acest lucru înseamnă, de asemenea, că EC-El-Gamal este semnificativ mai eficient din punct de vedere al comunicării decât El-Gamal în $\mathbb{Z}_p^*$.)

$^*$GNFS original este o euristică. Dar așa cum a subliniat @djao (vezi acest comentariu), există variante demonstrabile care rulează $\aproximativ L_n(1/3,3)$.

0 + 2
djao avatar
drapel cn
djao
S-a dovedit că sita câmpului numeric rulează în timpul revendicat și, în special, este (probabil) mai rapidă decât sita pătratică. https://cstheory.stackexchange.com/questions/32508/
2
Răspunde
ckamath avatar
drapel ag
ckamath
Mulțumiri! Nu eram conștient. Va actualiza raspunsul.
0
Răspunde
Puncte:1
TurkBitig avatar Crypto
drapel fr
TurkBitig

Securitatea pe n-biți a fiecărui algoritm este calculată prin „cea mai bună metodă de atac”. De exemplu, RSA se bazează pe problema de factorizare și poate fi rezolvată cu algoritmul „Number Field Sieve”, așa că folosim „complexitatea de calcul” a NFS pentru a determina nivelul de securitate pe n-biți al RSA. Pentru funcțiile hash criptografice folosim „atac de naștere” pentru a calcula securitatea pe n-biți etc.

0 + 0
Puncte:0
SAI Peregrinus avatar Crypto
drapel si
SAI Peregrinus

Nu există un răspuns unic, simplu. Securitatea pe n biți înseamnă logaritmul de bază 2 (de obicei scris doar $\log$) din numărul de „operații” necesare pentru spargerea primitivei.

Pentru un cifru simetric precum AES-128, o „operație” este de obicei o criptare sau decriptare de probă, mult mai mult decât un singur ciclu CPU. AES-128 are în general securitate pe 128 de biți, deoarece există $2^{128}$ posibile chei și nu există niciun atac general mai rapid decât încercarea tuturor cheilor și $\log(2^{128})=128$.

Sistemele asimetrice precum Paillier, ElGamal și EC ElGamal au toate atacuri mult mai rapid decât încercarea tuturor cheilor posibile. Deci, pentru a calcula „securitatea simetrică echivalentă” în biți, trebuie să calculați costul celui mai cunoscut atac față de parametrii utilizați.

De asemenea, trebuie să decideți dacă costul unei „operațiuni” într-un astfel de atac este dramatic diferit de o „operație” care atacă cifrurile simetrice cu care comparați și, dacă da, scalați numărul de operațiuni în mod corespunzător.Această ultimă considerație este motivul pentru care sistemele asimetrice precum ElGamal ar avea jumătate din câte biți de securitate împotriva atacurilor de către computerele cuantice de uz general, corectate de erori, față de computerele actuale.

Nu sunt foarte familiarizat cu stadiul tehnicii în atacurile împotriva celor trei sisteme în cauză, așa că nu pot da cifre absolute. Acesta este, prin urmare, doar un răspuns parțial la întrebarea adresată.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.