Compromis de timp și memorie

Compromisul de timp și ___ _memorie informatică , care utilizează raportul invers dintre cantitatea necesară de memorie și viteza de execuție a programului: timpul de calcul poate fi mărit prin reducerea memoriei utilizate sau, dimpotrivă, redus prin creșterea cantității de memorie utilizată.

Datorită scăderii costurilor relative ale cantității de RAM (RAM) și memoriei pe hard disk (pentru o anumită perioadă de timp, costul spațiului pe hard disk a devenit mult mai ieftin decât costul altor componente ale computerului ), tehnici care folosesc disponibile memoria pentru a reduce timpul de calcul s-au răspândit treptat. În același timp, tehnici precum compresia datelor demonstrează o abordare alternativă - utilizarea economică a memoriei datorită conversiilor suplimentare de date dintr-un format în altul.

Exemple de aplicații

Tabele de căutare

Multe probleme de căutare, precum problema rucsacului continuu , problema logaritmului discret sau problema inversării unei funcții unidirecționale , fiind rezolvate, de fapt, prin enumerare, permit în același timp utilizarea așa-zisului. tabele de căutare ( tabele de căutare în engleză ) [1] . Ideea este următoarea: în loc să iterați peste toate soluțiile fezabile fără a utiliza memorie suplimentară sau să le calculați pe toate o dată în avans și să le stocați în memorie (de multe ori nu există nici prima, nici a doua posibilitate), puteți precalcula o parte din soluțiile fezabile. valorile și, organizându-le într-o structură specială de date - un tabel de căutare - să-l folosească pentru a efectua o enumerare ulterioară direct la rezolvarea problemei.

O secțiune separată a acestui articol este dedicată aplicării acestei abordări în criptografie.

Comprimarea datelor

Alegerea raportului optim „loc – timp” poate fi aplicată problemei stocării datelor. Stocarea datelor în formă necomprimată va necesita mai multă memorie, dar va dura mai puțin timp pentru a le prelua decât pentru a prelua datele stocate în formă comprimată. În funcție de sarcina specifică, una sau cealaltă opțiune poate fi de preferat.

Un exemplu clasic de reprezentare compactă a datelor este, de exemplu, formatul de reprezentare a formulei Τ Ε Χ utilizat pentru scrierea articolelor științifice. Rezultatul muncii utilizatorului este un fișier cu un format special, care, dacă este necesar, poate fi ușor convertit într-un fișier pdf mult mai „greu” , care, la rândul său, poate fi deja folosit pentru a vizualiza documentul în vizualizatoare mai populare. decât cele specifice lui Τ Ε Χ .

Promovarea ciclului

Derularea buclei este o tehnică de optimizare a codului foarte populară utilizată în multe compilatoare. Ideea este de a crește numărul de instrucțiuni executate în timpul unei iterații a buclei. Ca urmare, numărul de iterații scade (până la una în limită: toate instrucțiunile sunt executate una după alta), ceea ce, la rândul său, crește eficiența cache -ului de date .

Criptografie

Această secțiune discută un exemplu clasic de utilizare a abordării Space-Time Trade-Off în criptografie - utilizarea tabelelor de căutare în rezolvarea problemei criptografice de inversare a unei funcții hash criptografice .

Enumerarea criptonalitică necesită costuri de calcul semnificative. În cazul în care este necesară spargerea în mod repetat a criptosistemului, ar fi logic să efectuați o enumerare exhaustivă în prealabil și să stocați valorile calculate în memorie. După ce ați făcut acest lucru o dată, puteți enumera în continuare aproape instantaneu [2] . Cu toate acestea, în realitate, această metodă nu este aplicabilă din cauza costurilor uriașe de memorie.

Metoda lui Hellman

În 1980, Martin Hellman a propus o abordare de compromis a problemei criptoanalizei, care face posibilă analiza unui criptosistem care are chei în operațiuni, cu costuri de memorie și [1] . Acest lucru devine posibil după ce pre-obținerea O(n) a posibilelor chei a fost făcută o dată. $N$ $N^{{2/3}}$ $N^{{2/3}}$

Ideea este următoarea.

Lăsați algoritmul de criptare să folosească o funcție unidirecțională . Prin proprietățile unei funcții unidirecționale, derivarea unei chei utilizate dintr-o pereche cunoscută este o sarcină dificilă, în timp ce calcularea unei funcții dintr-un text simplu dat este o sarcină simplă. $S_{k_{i}}(P)$ $k_i$ $P_{0},C_{0}$

Criptanalistul folosește un atac de text simplu ales și obține un singur text cifrat care se potrivește cu textul simplu : $C_{0}$ $P_0$

C_{0}=S_{k}(P_{0})

Sarcina este de a găsi cheia care a fost folosită pentru criptare. Pentru a face acest lucru, trebuie să găsiți o modalitate de a calcula cheile posibile. Să introducem așa-numitul. funcția de reducere , care atribuie o anumită cheie textului cifrat (lungimea cheii este de obicei mai mică decât lungimea textului cifrat, de unde și termenul): $k$ $R(C)$ $C_{i}$ $k_{{i+1}}$

R(C_{i})=k_{i+1}

Calcularea funcției de reducere este o operație simplă.

Funcţie $f=R[S_{k_{i}}(P_{0})]$

mapează o cheie cu o altă cheie . Acum putem obține un lanț de chei arbitrar lung: $k_i$ $k_{{i+1}}$

k_{i}{\stackrel {f}{\longrightarrow }}k_{i+1}{\stackrel {f}{\longrightarrow }}k_{i+2}{\stackrel {f}{\longrightarrow }}...

Pentru a construi un tabel de căutare, criptoanalistului i se oferă elemente aleatorii ale spațiului cheie. Din fiecare cheie, folosind metoda descrisă mai sus, obținem un lanț de chei de lungime . Scriem în memorie doar cheile inițiale și finale ale fiecărui lanț (sortăm perechile de chei după cheia finală ). Astfel, tabelul finit ocupă celule de memorie. Generarea tabelului necesită operații. $m$ $t$ $O(m)$ $mt$

Având tabelul construit, criptoanalistul poate enumera în felul următor. Pornim de la faptul că cheia folosită în criptare a fost găsită în timpul generării tabelului. În acest caz, una dintre cheile finale stocate în memorie poate fi obținută de la aceasta în cel mult t operațiuni de aplicare a funcției . $k$ $f$ $m$

După fiecare aplicare a operației de reducere, criptoanalistul caută următoarea cheie primită în tabel (o puteți găsi sau vă asigurați că nu există pentru operațiuni care utilizează căutarea binară , deoarece tabelul este sortat după cheia finală). După ce a întâlnit una dintre cheile finale, este posibil să se restabilească întregul lanț corespunzător din cheia inițială corespunzătoare acestuia; cheia dorită este penultima cheie. $log(m)$

Găsirea cheii necesită astfel [3] ; neglijând factorul logaritmic, avem . În acest caz, costurile de memorie pentru stocarea tabelului sunt . $O(t\cdot log(m))$ $O(t)$ $O(m)$

Analiza algoritmului trebuie însă să țină cont de faptul că probabilitatea de decriptare reușită este de fapt mai mică de unu, iar timpul de decriptare se poate dovedi a fi mai mare decât cel declarat, din motivele indicate mai jos. $P_{succes}$

Fuzionarea lanțurilor este posibilă atunci când a treia cheie a unuia și a treia cheie a altui lanț coincid pentru o pereche de indici. $i,j$ $i$ $j$
Posibil așa-zis. „alarme false” (ing. alarme false), când criptoanalistul găsește mai mult de o cheie finală în tabel. În acest caz, el trebuie să verifice toate lanțurile relevante.

O limită inferioară [1] pentru probabilitatea de decriptare reușită poate fi derivată :

P_{succes}\geq {\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}\ stânga(1-{\frac {it}{N}}\dreapta)^{j+1}

Expresia de mai sus corespunde aproximării că funcția este o variabilă aleatoare cu o distribuție uniformă pe mulțimea de chei. Cu toate acestea, un criptosistem stabil ar trebui să fie un bun generator pseudo-aleatoriu [1] . $f$

Evaluarea acestei expresii conduce la următorul rezultat: nu are sens să se ia produsul mai mare decât $mt^{2}$ $N$ : în caz contrar, limita inferioară a probabilității de succes scade rapid.

Când ajungem $mt^{2}=N$

P_{{succes}}\geq 0,8{\frac {mt}{N}}={\frac {1}{t}}

Criptanalistul poate genera acum nu doar unul, ci tabele, în fiecare tabel folosind propria funcție de reducere (care va evita îmbinarea lanțurilor din tabele diferite). În acest caz, limita inferioară a probabilității de decriptare reușită va fi: $l$

P_{succes,l}\geq 1-\left[{\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0} ^{t-1}\left(1-{\frac {it}{N}}\right)^{j+1}\right]^{l}

Alegând , criptoanalistul primește costuri de memorie și timp (fiecare tabel folosește propria funcție de reducere, deci atunci când decriptați trebuie să obțineți propriul lanț pentru fiecare tabel) cu o probabilitate de succes apropiată de unu [nota de subsol care explică de ce numărul de alarme false va fi fii mic și link pe Hellman]. Luând , obținem timpul necesar și costurile de memorie. $l=t$ $mt$ $t^{2}$ $t=m=N^{{1/3}}$ $N^{{2/3}}$

Alte exemple

Alți algoritmi care folosesc, de asemenea, „selecție optimă loc-timp”:

Algoritmul lui Shanks , folosit pentru a calcula logaritmi discreti .
Programare dinamică , în care complexitatea de timp a unei sarcini care este efectiv împărțită în subsarcini poate fi redusă semnificativ prin memorare - salvând soluțiile deja calculate pentru subsarcini.
Tabelele curcubeu în criptografie sunt o versiune îmbunătățită a tabelelor de căutare pentru inversarea funcțiilor hash criptografice .

Vezi și

Note

↑ 1 2 3 4 Martin E. Hellman. Un compromis criptoanalitic timp-memorie. // Tranzacții pe teoria informației. - iulie 1980. - Nr. 4.
↑ Philippe Oechslin. Efectuarea unui compromis criptoanalitic mai rapid între timp și memorie. // ISBN 3-540-40674-3 .
↑ Kormen T., Leyzerson Ch., Rivest R. Algorithms: construction and analysis. - al 2-lea. — M.: Williams, 2005. — 1296 p. — ISBN 5-8459-0857-4 .