Pentru alți algoritmi, notația big-O ascunde de obicei factorii constanți, făcând operația elementară exactă un detaliu neimportant. Dar documentele criptografice precizează exact complexitățile, ceea ce este surprinzător pentru mine.
Ai dreptate să fii surprins --- în general, scrierea „complexităților exacte” este fără speranță din cauza a ceea ce este cunoscut sub numele de teorema de accelerare liniară --- putem stabili complexitățile de calcul doar până la un factor multiplicativ arbitrar.
Acest lucru se datorează faptului că putem crește oricând dimensiunea alfabetului subiacent cu un factor constant pentru a ne permite să calculăm un număr mai mare de operații pe unitatea de timp. Aceasta (un fel de) are o componentă practică --- puteți crește dimensiunea arhitecturii unui set de instrucțiuni pentru a face mai multe calcule pe ciclu de ceas (cu prețul cipurilor care folosesc mai mult siliciu).
Deci, ce măsură de cost folosesc oamenii? Aceasta într-adevăr depinde de aplicație.
De exemplu, un atac binecunoscut asupra AES este Atacul Biclique, care recuperează cheia AES în complexitate $2^{126.1}$. Desigur, autorii nu tind să pretindă numere arbitrare drept rezultate --- cum calculează acest lucru?
Complexitatea deplină a abordării biclique independente
se evaluează după cum urmează:
$$C_{full} = 2^{nâ2d}[C_{biclique} + C_{precomp} + C_{recomp} + C_{falsepos}],$$
Unde
- $C_{precomp}$ este complexitatea precalculării din Pasul 3. Este echivalent cu mai puțin de $2^d$ runde ale subcifrului $g$.
- $C_{recomp}$ este complexitatea recalculării variabilei interne $v$ $2^{2d}$ ori. Aceasta
depinde puternic de proprietățile de difuzie ale cifrului. Pentru AES această valoare variază de la
$2^{2dâ1,5}$ la $2^{2dâ4}$.
Construcția biclique este destul de ieftină în această paradigmă. Metoda din Secțiunea 3.1 permite
construirea unei biclique in numai $2^{d+1}$ apeluri de subcifrare $f$. Prin urmare, de obicei cheia completă
complexitatea recuperării va fi dominată de $2^{nâ2d}C_{recomp}$. Cu toate acestea, depinde de
lățimea variabilei de potrivire și dimensiunea biclique $d$ de asemenea. Vă oferim mai multe detalii pentru caz
a AES în secțiunile ulterioare. Complexitatea memoriei recuperării cheii este limita superioară
prin depozitare $2^d$ calcule complete ale cifrului.
Pentru AES în special, spun ei
În total, avem nevoie de un echivalent al $3.4375$ Operații cu subocteți (adică, 55 de casete S), 2.3125
Operațiuni MixColumns și o cantitate neglijabilă de XOR în programul cheie. Numarul
SubBytes calculele este în mod clar un sumar mai mare. S-box-urile sunt, de asemenea, contribuția majoră
la complexitatea practică a AES atât în hardware cât și în software. Prin urmare, dacă urmărim a
un singur număr care se referă la complexitate, este logic să numărați numărul de subocteți
operațiunile de care avem nevoie și le comparăm cu cele din cifrul complet. Ultimul număr este
$10 + 2.5 = 12.5$ întrucât trebuie să luăm în considerare neliniaritatea programului cheie. Ca urmare,
$C_{recomp}$ este echivalent cu $2^{16}\time 3,4375/12,5 = 2^{14,14}$ rulează complet AES-128. Valorile $C_{biclique}$
și $C_{precomp}$ împreună nu depăşesc $2^8$ apeluri ale AES-128 complet.
Complexitatea totală de calcul se ridică la aproximativ
$2^{112} (2^7 + 2^7 + 2^{14.14} + 2^8) = 2^{126.18}$.
Aceasta înseamnă că „operația primitivă” a atacului biclique este numărul de apeluri SubBytes, în care se normalizează lucrurile astfel încât atacul cu forță brută ar dura $2^{128}$ complexități.
Există desigur și alte noțiuni de complexitate.
De exemplu
Am auzit de o metrică „Area x Time”, care măsoară complexitatea unui atac în termeni de timp necesar unui circuit de o anumită dimensiune pentru a-l finaliza (dar nu pot găsi referințe acum),
în mod similar, este obișnuit ca atacurile să măsoare atât o noțiune de complexitate computațională, cât și o noțiune de complexitate memorie/eșantion,
în criptografia bazată pe zăbrele, o anumită măsurătoare cunoscută sub numele de „Numărul Core SVP” este destul de populară în analiză.
În general însă, deoarece nu este deloc evident ce $2^{128}$ operațiile primitive înseamnă (de exemplu), este la latitudinea autorilor să definească acești termeni, așa că în general o fac.
