Az idő és a memória kompromisszuma

Idő és memória kompromisszum _ _ _ _ kompromisszumos megközelítés számos számítástechnikai probléma szükségesaamely ,megoldására memória mennyiségének és a program végrehajtási sebességének fordított arányát használja: a számítási idő növelhető a felhasznált memória csökkentésével vagy fordítva, csökkenteni kell a felhasznált memória mennyiségének növelésével.

A RAM (RAM) és a merevlemez-memória relatív költségeinek csökkenése miatt (egy ideig a merevlemez-terület költsége sokkal gyorsabban vált olcsóbbá, mint a többi számítógép -alkatrész költsége ), a rendelkezésre álló technikák A számítási idő csökkentésére szolgáló memória fokozatosan elterjedt. Ugyanakkor az olyan technikák, mint például az adattömörítés , egy alternatív megközelítést mutatnak be – gazdaságos memóriahasználatot az egyik formátumból a másikba történő további adatkonverzió miatt.

Alkalmazási példák

Keresési táblázatok

Számos keresési probléma, mint például a folytonos hátizsák -probléma , a diszkrét logaritmus -probléma vagy az egyirányú függvény invertálásának problémája , valójában felsorolással oldják meg, egyúttal lehetővé teszik az ún. keresőtáblák (angolul lookup tables ) [1] . Az ötlet a következő: ahelyett, hogy az összes megvalósítható megoldást további memória használata nélkül iterálná, vagy egyszer előre kiszámolná és a memóriában tárolná (gyakran nincs sem az első, sem a második lehetőség), előre kiszámíthatja a megvalósítható egy részét. értékeket, és ezeket egy speciális adatstruktúrába - keresőtáblába - rendszerezve a probléma megoldása során közvetlenül a további felsorolás elvégzésére használja.

A cikk egy külön szakaszát szenteljük ennek a megközelítésnek a kriptográfiában való alkalmazásának.

Adattömörítés

Az optimális "hely-idő" arány megválasztása az adattárolás problémájára alkalmazható. Az adatok tömörítetlen formában történő tárolása több memóriát igényel, de a visszakeresés kevesebb időt vesz igénybe, mint a tömörített formában tárolt adatok visszakeresése. Az adott feladattól függően az egyik vagy a másik lehetőség előnyösebb lehet.

A kompakt adatábrázolás klasszikus példája például a tudományos cikkek írásához használt Τ Ε Χ képletábrázolási formátum. A felhasználó munkájának eredménye egy speciális formátumú fájl, amely szükség esetén könnyen konvertálható egy sokkal "nehezebb" pdf -fájllá, amivel viszont már népszerűbb nézőkben is megtekinthető a dokumentum mint a Τ Ε Χ -re jellemzők .

Cikluspromóció

A hurok feloldása egy nagyon népszerű kódoptimalizálási technika, amelyet sok fordító alkalmaz. Az ötlet az, hogy növeljük a ciklus egy iterációja során végrehajtott utasítások számát. Ennek eredményeként csökken az iterációk száma (a limitben egyig: minden utasítás egymás után fut), ami viszont növeli az adatgyorsítótár hatékonyságát .

Kriptográfia

Ez a rész a tér-idő kompromisszumos megközelítés kriptográfiában való használatának klasszikus példáját tárgyalja – a keresőtáblák használatát a kriptográfiai hash függvény megfordításával kapcsolatos kriptográfiai probléma megoldásában .

A kriptanalitikus felsorolás jelentős számítási költségeket igényel. Abban az esetben, ha ismételten fel kell törni a kriptorendszert, logikus lenne előzetesen kimerítő felsorolást végezni, és a számított értékeket a memóriában tárolni. Ha ezt egyszer megtette, szinte azonnal tovább sorolhatja [2] . A valóságban azonban ez a módszer nem alkalmazható a hatalmas memóriaköltségek miatt.

Hellman módszere

1980-ban Martin Hellman egy kompromisszumos megközelítést javasolt a kriptoanalízis problémájára, amely lehetővé teszi egy olyan titkosítási rendszer elemzését, amely műveletekben kulcsokat tartalmaz , memóriaköltségekkel is [1] . Ez akkor válik lehetségessé, ha egyszer megtörtént a lehetséges kulcsok O(n) előzetes megszerzése. $N$ $N^{{2/3}}$ $N^{{2/3}}$

Az ötlet a következő.

Hagyja, hogy a titkosítási algoritmus egyirányú függvényt használjon . Az egyirányú függvény tulajdonságainál fogva egy használt kulcs levezetése ismert párból nehéz feladat, míg egy függvény kiszámítása adott nyílt szövegből egyszerű feladat. $S_{k_{i}}(P)$ $k_i$ $P_{0},C_{0}$

A kriptoanalizátor egy kiválasztott nyílt szöveges támadást használ, és egyetlen titkosított szöveget kap, amely megegyezik a nyílt szöveggel : $C_{0}$ $P_0$

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

A feladat az, hogy megtaláljuk a titkosításhoz használt kulcsot. Ehhez meg kell találni a lehetséges kulcsok kiszámításának módját. Vezessük be az ún. redukciós függvény , amely egy bizonyos kulcsot rendel a rejtjelezett szöveghez (a kulcs hossza általában kisebb, mint a rejtjelezett szöveg hossza, innen ered a kifejezés): $k$ $R(C)$ $C_{i}$ $k_{{i+1}}$

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

A redukciós függvény kiszámítása egyszerű művelet.

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

leképez egy kulcsot egy másik kulcsra . Most egy tetszőlegesen hosszú kulcstartót kaphatunk: $k_i$ $k_{{i+1}}$

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

A keresési tábla felépítéséhez a kriptoanalizátor a kulcstér véletlenszerű elemeit kapja. Mindegyik kulcsból a fent leírt módszerrel egy hosszúságú kulcsláncot kapunk . Minden láncnak csak a kezdő és a végső kulcsát írjuk a memóriába (a kulcspárokat a végső kulcs szerint rendezzük). Így a kész táblázat memóriacellákat foglal el. A táblázat generálása műveleteket igényel. $m$ $t$ $O(m)$ $mt$

A megszerkesztett táblázat birtokában a kriptaelemző a következő módon tud felsorolni. Abból indulunk ki, hogy a tábla generálása során megtaláltuk a titkosításhoz használt kulcsot . Ebben az esetben a memóriában tárolt utolsó kulcsok egyike a függvény alkalmazásának legfeljebb t műveletével nyerhető ki belőle . $k$ $f$ $m$

A redukciós művelet minden egyes alkalmazása után a kriptoanalizátor megkeresi a következő kapott kulcsot a táblázatban (megtalálhatja, vagy győződjön meg arról, hogy nem létezik a bináris keresést használó műveleteknél , mivel a táblázat a végső kulcs szerint van rendezve). Az egyik végső kulcs találkozása után lehetséges a teljes megfelelő lánc visszaállítása a hozzá tartozó kezdeti kulcsból; a kívánt billentyű az utolsó előtti billentyű. $log(m)$

A kulcs megtalálása tehát [3] ; a logaritmikus tényezőt figyelmen kívül hagyva van . Ebben az esetben a tábla tárolásának memóriaköltségei . $O(t\cdot log(m))$ $O(t)$ $O(m)$

Az algoritmus elemzésénél azonban figyelembe kell venni, hogy a sikeres dekódolás valószínűsége valójában kisebb egynél, és a visszafejtési idő a deklaráltnál nagyobbnak bizonyulhat, az alábbiakban bemutatott okok miatt. $P_{siker}$

A láncok összevonása akkor lehetséges , ha az egyik és a másik lánc harmadik kulcsa egy indexpár esetén egybeesik . $i,j$ $én$ $j$
Lehetséges ún. "téves riasztások" (eng. false alarms), amikor a kriptoanalizátor egynél több végső kulcsot talál a táblázatban. Ebben az esetben ellenőriznie kell az összes releváns láncot.

A sikeres dekódolás valószínűségének [1] alsó korlátja származtatható :

P_{siker}\geq {\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}\ bal (1-{\frac {it}{N}}\jobb)^{j+1}

A fenti kifejezés megfelel annak a közelítésnek, hogy a függvény egy valószínűségi változó, amely egyenletes eloszlású a kulcsok halmazán. Egy stabil kriptorendszernek azonban jó pszeudo-véletlen generátornak kell lennie [1] . $f$

Ennek a kifejezésnek az értékelése a következő eredményhez vezet: nincs értelme nagyobbnak venni a szorzatot $mt^{2}$ $N$ , mint : ellenkező esetben a siker valószínűségének alsó korlátja gyorsan csökken.

Amikor megkapjuk $mt^{2}=N$

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

A kriptoanalizátor immár nem csak egyet, hanem táblákat is generálhat minden táblában a saját redukciós függvényével (amely elkerüli a különböző táblákból származó láncok összevonását). Ebben az esetben a sikeres visszafejtés valószínűségének alsó korlátja: $l$

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

A kiválasztásával a kriptoanalizátor memória- és időköltségeket kap (minden tábla saját redukciós funkciót használ, így a visszafejtéshez saját láncot kell szereznie minden táblához) egyhez közeli siker valószínűséggel [lábjegyzet, amely elmagyarázza, hogy miért fog a téves riasztások száma legyen kicsi, és linkeld a Hellman-en]. Felvétellel megkapjuk a szükséges idő- és memóriaköltséget. $l=t$ $mt$ $t^{2}$ $t=m=N^{{1/3}}$ $N^{{2/3}}$

Egyéb példák

Egyéb algoritmusok, amelyek szintén "optimális hely-idő-választást" használnak:

Shanks algoritmusa , diszkrét logaritmusok kiszámítására szolgál .
Dinamikus programozás , amelyben a hatékonyan részfeladatokra bontott feladat időbonyolultsága jelentősen csökkenthető memoizálással - a részfeladatok már kiszámított megoldásainak elmentésével.
A kriptográfiai szivárványtáblák a kriptográfiai hash függvények invertálására szolgáló keresőtáblák továbbfejlesztett változatai .

Lásd még

Jegyzetek

↑ 1 2 3 4 Martin E. Hellman. Kriptanalitikus idő-memória kompromisszum. // Tranzakciók az információelméletről. - 1980. július - 4. sz.
↑ Philippe Oechslin. Gyorsabb kriptanalitikus időmemória csere. // ISBN 3-540-40674-3 .
↑ Kormen T., Leyzerson Ch., Rivest R. Algoritmusok: konstrukció és elemzés. - 2. — M.: Williams, 2005. — 1296 p. — ISBN 5-8459-0857-4 .