Compromis timp-memorie
Compensarea timp-memorie (sau compensarea spațiu-timp ), în informatică , este o situație în care utilizarea memoriei poate fi redusă cu prețul reducerii vitezei de execuție a programului sau, dimpotrivă, timpul de calcul poate fi redus. prețul creșterii utilizării memoriei. Pe măsură ce costurile relative ale ciclurilor CPU, spațiul RAM și spațiul pe hard disk se schimbă, alegerile dvs. pentru schimbul de timp până la memorie se pot schimba radical. Adesea, efectuarea unui compromis între timp și memorie poate duce la un program care rulează mult mai repede.
Aplicații în domeniul IT
Cea mai frecventă situație este un algoritm care funcționează pe o tabelă de asociere : o implementare poate include întreaga tabelă, ceea ce reduce timpul de calcul, dar crește cantitatea de memorie necesară; o altă implementare poate calcula tabelul din mers, ceea ce crește timpul de calcul, dar reduce cantitatea de memorie necesară.
Un compromis spațiu-timp poate fi aplicat problemei stocării datelor. Dacă datele sunt stocate într-o formă necomprimată, poate ocupa mult spațiu, dar poate dura mai puțin timp pentru citire decât datele stocate în formă comprimată (acest lucru se datorează faptului că compresia datelor reduce spațiul necesar pentru stocarea lor, dar durează ceva timp pentru a rula algoritmul de compresie). În funcție de nevoi, una sau alta soluție poate fi utilă. Un alt exemplu este afișarea formulelor matematice pe site-uri web cu informații în principal în format text, cum ar fi Wikipedia însăși. Stocarea sursei LaTex și redarea acesteia ca imagine numai atunci când pagina este solicitată este un proces care economisește spațiu pe disc, dar implică mai mult timp pentru vizualizare. Cealaltă soluție este să redați imaginea atunci când pagina este schimbată și să o stocați pe disc pentru încărcare atunci când pagina este vizualizată. Această soluție are ca rezultat un consum mai mare de spațiu pe disc, dar mai puțin timp pentru accesarea datelor. Trebuie remarcat faptul că există situații rare în care este posibil să lucrați direct cu date comprimate, cum ar fi în cazul indexurilor de imagini comprimate în care este mai rapid să lucrați cu compresie decât fără ea.
Aplicații în domeniul criptografic
În câmpul criptografic , unde un atacator încearcă să spargă un cifru cu orice tehnică care îi permite rezultate mai bune decât cele obținute prin aplicarea forței brute simple, avantajele unui compromis de memorie în timp sunt clar vizibile.
Prima aplicație a compromisului timp-memorie în acest domeniu este realizată de Martin Hellman, care în 1980 a demonstrat modul în care utilizarea tabelelor precompilate pentru a căuta posibilele chei secrete ale cifrelor bloc distribuite spațiul posibilelor chei între memorie și timpul de calcul [1] ] . Această metodă criptanalitică a fost apoi aplicată la fluxul de cifre de către Alex Biryukov și Adi Shamir luând în considerare și cunoașterea datelor de ieșire. Recent, Philippe Oechslin a publicat o versiune îmbunătățită a ideii originale a lui Hellman, prin care timpul de calcul este redus în continuare prin utilizarea tabelelor curcubeu [2] . Oechslin și-a folosit și tehnica ca metodă de recuperare a parolelor pentru sistemul de operare Microsoft Windows [3] [4] .
Tabelele curcubeu sunt tabele speciale de asociere care utilizează hashuri precompilate de o funcție hash criptografică pentru a sparge cheile secrete în câteva minute în loc de săptămâni sau luni. Reducerea dimensiunii mesei curcubeu crește timpul necesar pentru a itera peste toate hashurile posibile. Atacul Meet-in-the-middle folosește un compromis de memorie-timp pentru a găsi cheia criptografică cu doar cifre 2n + 1 (și un spațiu de O (2n)) împotriva cifrelor estimate de 22n (dar cu un spațiu de numai O ( 1)) a unui atac simplu.
Notă
- ^ Martin Hellman: Un compromis criptanalitic al memoriei în timp
- ^ Philippe Oechslin: Efectuarea unui compromis criptanalitic mai rapid de memorie în timp
- ^ Philippe Oechslin: Les compromis temps-memoire et leur utilisation pour casser les mots de passe Windows Arhivat 17 februarie 2015 la Internet Archive .
- ^ Philippe Oechslin, Ophcrack: Programul scris de Oechslin pentru utilizarea tabelelor Rainbow , la ophcrack.sourceforge.net , Philippe Oechslin, 17 februarie 2015.
Elemente conexe
linkuri externe
- Mark Stamp: Once Upon a Time-Memory Tradeoff
