Kompromiss med tid och minne

Tid och ___ _kompromissminne datavetenskap , som använder det omvända förhållandet mellan den nödvändiga mängden minne och hastigheten för programexekvering: beräkningstiden kan ökas genom att minska det använda minnet eller omvänt minskas genom att öka mängden minne som används.

På grund av minskningen av de relativa kostnaderna för mängden RAM (RAM) och hårddiskminne (under en viss tid blev kostnaden för hårddiskutrymme billigare mycket snabbare än kostnaden för andra datorkomponenter ), tekniker som använder tillgängliga minne för att minska beräkningstiden har gradvis spridit sig. Samtidigt visar tekniker som datakomprimering ett alternativt tillvägagångssätt - ekonomisk användning av minne på grund av ytterligare datakonverteringar från ett format till ett annat.

Applikationsexempel

Uppslagstabeller

Många sökproblem, såsom det kontinuerliga ryggsäcksproblemet , det diskreta logaritmproblemet eller problemet med att invertera en enkelriktad funktion , som i själva verket löses genom uppräkning, tillåter samtidigt användningen av den så kallade. uppslagstabeller (engelska uppslagstabeller ) [1] . Tanken är denna: istället för att iterera över alla möjliga lösningar utan att använda extra minne, eller beräkna dem alla en gång i förväg och lagra dem i minnet (ofta finns det varken den första eller den andra möjligheten), kan du förberäkna en del av det genomförbara värden, och, efter att ha organiserat dem i en speciell datastruktur - en uppslagstabell - att använda den för att utföra ytterligare uppräkningar direkt vid lösning av problemet.

Ett separat avsnitt av denna artikel ägnas åt tillämpningen av denna metod i kryptografi.

Datakomprimering

Valet av det optimala förhållandet "plats - tid" kan tillämpas på problemet med datalagring. Att lagra data i okomprimerad form kommer att kräva mer minne, men det kommer att ta kortare tid att hämta det än att hämta data som lagrats i komprimerad form. Beroende på den specifika uppgiften kan det ena eller det andra alternativet vara att föredra.

Ett klassiskt exempel på en kompakt datarepresentation är till exempel Τ Ε Χ formelrepresentationsformatet som används för att skriva vetenskapliga artiklar. Resultatet av användarens arbete är en fil av ett speciellt format, som vid behov enkelt kan konverteras till en mycket mer "tungvikts" pdf -fil, som i sin tur redan kan användas för att se dokumentet i mer populära tittare än de som är specifika för Τ Ε Χ .

Cykelkampanj

Loop unwinding är en mycket populär kodoptimeringsteknik som används i många kompilatorer. Tanken är att öka antalet instruktioner som exekveras under en iteration av loopen. Som ett resultat minskar antalet iterationer (upp till en i gränsen: alla instruktioner exekveras en efter en), vilket i sin tur ökar effektiviteten hos datacache .

Kryptografi

I det här avsnittet överväger vi ett klassiskt exempel på användning av Space-Time Trade-Off-metoden i kryptografi - användningen av uppslagstabeller för att lösa det kryptografiska problemet med att invertera en kryptografisk hashfunktion .

Kryptanalytisk uppräkning kräver betydande beräkningskostnader. I händelse av att det krävs att upprepade gånger knäcka kryptosystemet, skulle det vara logiskt att utföra en uttömmande uppräkning i förväg och lagra de beräknade värdena i minnet. Efter att ha gjort detta en gång kan du räkna upp ytterligare nästan omedelbart [2] . Men i verkligheten är denna metod inte tillämplig på grund av de enorma minneskostnaderna.

Hellmans metod

1980 föreslog Martin Hellman en kompromissstrategi för problemet med kryptoanalys, vilket gör det möjligt att analysera ett kryptosystem som har nycklar i operationer, med minneskostnader också [1] . Detta blir möjligt efter att O(n) förinhämtningen av möjliga nycklar har gjorts en gång. $N$ $N^{{2/3}}$ $N^{{2/3}}$

Tanken är följande.

Låt krypteringsalgoritmen använda en enkelriktad funktion . Genom egenskaperna hos en envägsfunktion är det en svår uppgift att härleda en använd nyckel från ett känt par , medan att beräkna en funktion från en given klartext är en enkel uppgift. $S_{k_{i}}(P)$ $k_i$ $P_{0},C_{0}$

Kryptanalytikern använder en vald klartextattack och får en enda chiffertext som matchar klartexten : $C_{0}$ $P_0$

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

Uppgiften är att hitta nyckeln som användes för att kryptera. För att göra detta måste du hitta ett sätt att beräkna möjliga nycklar. Låt oss introducera den så kallade. reduktionsfunktion , som tilldelar en viss nyckel till chiffertexten (nyckelns längd är vanligtvis mindre än chiffertextens längd, därav termen): $k$ $R(C)$ $C_{i}$ $k_{{i+1}}$

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

Att beräkna reduktionsfunktionen är en enkel operation.

Fungera $f=R[S_{k_{i}}(P_{0})]$

mappar en nyckel till en annan nyckel . Nu kan vi få en godtyckligt lång nyckelring: $k_i$ $k_{{i+1}}$

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

För att bygga en uppslagstabell får kryptoanalytikern slumpmässiga element i nyckelutrymmet. Från varje nyckel, med den metod som beskrivs ovan, får vi en nyckelkedja med längd . Vi skriver till minnet endast de initiala och sista nycklarna för varje kedja (vi sorterar nycklarna efter den sista nyckeln). Således upptar den färdiga tabellen minnesceller. Tabellgenerering kräver operationer. $m$ $t$ $O(m)$ $mt$

Med den konstruerade tabellen kan kryptoanalytikern räkna upp på följande sätt. Vi utgår från det faktum att nyckeln som används vid kryptering hittades under genereringen av tabellen. I detta fall kan en av de sista nycklarna som är lagrade i minnet erhållas från den i högst t operationer för att tillämpa funktionen . $k$ $f$ $m$

Efter varje tillämpning av reduktionsoperationen letar kryptoanalytikern efter nästa mottagna nyckel i tabellen (du kan hitta den eller se till att den inte finns för operationer som använder binär sökning , eftersom tabellen sorteras efter den sista nyckeln). Efter att ha träffat en av de sista nycklarna är det möjligt att återställa hela motsvarande kedja från den initiala nyckeln som motsvarar den; den önskade nyckeln är dess näst sista nyckel. $log(m)$

Att hitta nyckeln tar alltså [3] ; om man försummar den logaritmiska faktorn har vi . I detta fall är minneskostnaderna för lagring av bordet . $O(t\cdot log(m))$ $O(t)$ $O(m)$

Analysen av algoritmen måste dock ta hänsyn till att sannolikheten för framgångsrik dekryptering faktiskt är mindre än en, och dekrypteringstiden kan visa sig vara längre än den deklarerade, av de skäl som anges nedan. $P_{framgång}$

Sammanfogning av kedjor är möjligt när den e nyckeln i en och den e nyckeln i en annan kedja sammanfaller för ett par index. $I j$ $i$ $j$
Eventuellt sk. "false alarms" (eng. false alarms), när kryptoanalytikern hittar mer än en sista nyckel i tabellen. I det här fallet måste han kontrollera alla relevanta kedjor.

En [1] nedre gräns för sannolikheten för framgångsrik dekryptering kan härledas :

P_{framgång}\geq {\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}\ vänster(1-{\frac {it}{N}}\höger)^{j+1}

Ovanstående uttryck motsvarar approximationen att funktionen är en slumpvariabel med en enhetlig fördelning på uppsättningen nycklar. Ett stabilt kryptosystem bör dock vara en bra pseudo-slumpgenerator [1] . $f$

Utvärdering av detta uttryck leder till följande resultat: det är ingen mening att ta produkten större än $mt^{2}$ $N$ : annars faller den nedre gränsen för sannolikheten för framgång snabbt.

När vi får $mt^{2}=N$

P_{{framgång}}\geq 0.8{\frac {mt}{N}}={\frac {1}{t}}

Kryptanalytikern kan nu generera inte bara en, utan tabeller, i varje tabell med sin egen reduktionsfunktion (som kommer att undvika att slå samman kedjor från olika tabeller). I det här fallet kommer den nedre gränsen för sannolikheten för framgångsrik dekryptering att vara: $l$

P_{success,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}

Genom att välja , får kryptoanalytikern minnes- och tidskostnader (varje tabell använder sin egen reduktionsfunktion, så vid dekryptering måste du få en egen kedja för varje tabell) med en framgångsannolikhet nära en [fotnot som förklarar varför antalet falska larm kommer vara liten och länka på Hellman]. Med , får vi erforderlig tid och minneskostnader. $l=t$ $mt$ $t^{2}$ $t=m=N^{{1/3}}$ $N^{{2/3}}$

Andra exempel

Andra algoritmer som också använder "optimalt val av platstid":

Shanks algoritm , används för att beräkna diskreta logaritmer .
Dynamisk programmering , där tidskomplexiteten för en uppgift som effektivt bryts ned i deluppgifter kan reduceras avsevärt genom att spara redan beräknade lösningar på deluppgifter.
Rainbow-tabeller i kryptografi är en förbättrad version av uppslagstabeller för att invertera kryptografiska hashfunktioner .

Se även

Algoritm effektivitet
Beräkningsresurs
Blums speedup-
Savitchs teorem
Slinga avveckning

Anteckningar

↑ 1 2 3 4 Martin E. Hellman. En avvägning mellan kryptoanalytisk tid och minne. // Transaktioner på informationsteori. - Juli 1980. - Nr 4.
↑ Philippe Oechslin. Gör en snabbare avvägning mellan kryptoanalytisk tid och minne. // ISBN 3-540-40674-3 .
↑ Kormen T., Leyzerson Ch., Rivest R. Algoritmer: konstruktion och analys. - 2:a. — M.: Williams, 2005. — 1296 sid. — ISBN 5-8459-0857-4 .