Kompromis času a paměti

Kompromis času a ___ _paměti informatice , který využívá obrácený poměr potřebného množství paměti a rychlosti provádění programu: čas výpočtu lze prodloužit snížením použité paměti nebo naopak snížit zvýšením množství použité paměti.

Vzhledem ke snížení relativních nákladů na množství paměti RAM (RAM) a paměti na pevném disku (po určitou dobu se náklady na místo na pevném disku zlevnily mnohem rychleji než náklady na jiné počítačové komponenty ), techniky, které využívají dostupné paměti ke zkrácení doby výpočtu se postupně rozšířily. Techniky jako je komprese dat zároveň demonstrují alternativní přístup – ekonomické využití paměti díky dodatečným převodům dat z jednoho formátu do druhého.

Příklady aplikací

Vyhledávací tabulky

Mnoho problémů s hledáním, jako je problém spojitého batohu , problém diskrétního logaritmu nebo problém invertování jednosměrné funkce , které jsou ve skutečnosti řešeny výčtem, zároveň umožňuje použití tzv. vyhledávací tabulky (anglicky lookup tables ) [1] . Myšlenka je taková: namísto iterování všech proveditelných řešení bez použití další paměti nebo jejich výpočtu jednou předem a uložení do paměti (často neexistuje ani první ani druhá možnost), můžete předpočítat část proveditelného řešení. hodnoty a poté, co je uspořádali do speciální datové struktury - vyhledávací tabulky - ji použít k provedení dalšího výčtu přímo při řešení problému.

Aplikaci tohoto přístupu v kryptografii je věnována samostatná část tohoto článku.

Komprese dat

Volbu optimálního poměru „místo – čas“ lze aplikovat na problém ukládání dat. Ukládání dat v nekomprimované podobě bude vyžadovat více paměti, ale jejich načtení zabere méně času než načtení dat uložených v komprimované podobě. V závislosti na konkrétním úkolu může být výhodnější jedna nebo druhá možnost.

Klasickým příkladem kompaktní reprezentace dat je například formát reprezentace vzorce Τ Ε Χ používaný pro psaní vědeckých článků. Výsledkem práce uživatele je soubor speciálního formátu, který lze v případě potřeby snadno převést na mnohem „těžší“ soubor pdf , který již lze použít k prohlížení dokumentu v populárnějších prohlížečích. než ty specifické pro Τ Ε Χ .

Propagace cyklu

Odvíjení smyčky je velmi populární technika optimalizace kódu používaná v mnoha kompilátorech. Cílem je zvýšit počet instrukcí provedených během jedné iterace cyklu. V důsledku toho se počet iterací snižuje (až na jednu v limitu: všechny instrukce se provádějí jedna po druhé), což zase zvyšuje efektivitu datové mezipaměti .

Kryptografie

Tato část pojednává o klasickém příkladu použití přístupu Space-Time Trade-Off v kryptografii – použití vyhledávacích tabulek při řešení kryptografického problému inverze kryptografické hashovací funkce .

Kryptanalytický výčet vyžaduje značné výpočetní náklady. V případě, že je potřeba kryptosystém opakovaně prolomit, bylo by logické předem provést vyčerpávající výčet a vypočítané hodnoty uložit do paměti. Jakmile to jednou uděláte, můžete téměř okamžitě dále vyjmenovávat [2] . Ve skutečnosti však tato metoda není použitelná kvůli obrovským nákladům na paměť.

Hellmanova metoda

V roce 1980 Martin Hellman navrhl kompromisní přístup k problému kryptoanalýzy, který umožňuje analyzovat kryptosystém, který má klíče v operacích, s náklady na paměť [1] . To bude možné poté, co bylo jednou provedeno předběžné získání O(n) možných klíčů. $N$ $N^{{2/}}}$ $N^{{2/}}}$

Myšlenka je následující.

Nechte šifrovací algoritmus používat jednosměrnou funkci . Podle vlastností jednosměrné funkce je odvození použitého klíče ze známé dvojice obtížný úkol, zatímco výpočet funkce z daného otevřeného textu je jednoduchý úkol. $S_{k_{i}}(P)$ $k_i$ $P_{0},C_{0}$

Kryptanalytik použije vybraný útok v otevřeném textu a získá jediný šifrovaný text , který odpovídá otevřenému textu : $C_{0}$ $P_0$

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

Úkolem je najít klíč , který byl použit k šifrování. Chcete-li to provést, musíte najít způsob, jak vypočítat možné klíče. Pojďme si představit tzv. redukční funkce , která přiřadí šifrovanému textu určitý klíč (délka klíče je obvykle menší než délka šifrovaného textu, odtud termín): $k$ $R(C)$ $C_{i}$ $k_{{i+1}}$

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

Výpočet redukční funkce je jednoduchá operace.

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

mapuje klíč na jiný klíč . Nyní můžeme získat libovolně dlouhou klíčenku: $k_i$ $k_{{i+1}}$

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

Aby bylo možné sestavit vyhledávací tabulku, kryptoanalytik dostane náhodné prvky klíčového prostoru. Z každého klíče pomocí výše popsané metody získáme klíčenku délky . Do paměti zapisujeme pouze počáteční a koncový klíč každého řetězce (páry klíčů třídíme podle konečného klíče). Hotová tabulka tak zabírá paměťové buňky. Generování tabulky vyžaduje operace. $m$ $t$ $O(m)$ $mt$

Po zkonstruované tabulce může kryptoanalytik provést výčet následujícím způsobem. Vycházíme z toho, že klíč použitý při šifrování byl nalezen při generování tabulky. V tomto případě z něj lze získat jeden z posledních klíčů uložených v paměti za maximálně t operací aplikace funkce . $k$ $F$ $m$

Po každé aplikaci operace redukce kryptanalytik hledá další přijatý klíč v tabulce (můžete jej najít nebo se ujistit, že neexistuje pro operace pomocí binárního vyhledávání , protože tabulka je řazena podle konečného klíče). Po splnění jednoho z konečných klíčů je možné obnovit celý odpovídající řetězec z původního klíče, který mu odpovídá; požadovaný klíč je jeho předposlední klíč. $log(m)$

Najít klíč tedy trvá [3] ; při zanedbání logaritmického faktoru máme . V tomto případě jsou náklady na paměť pro uložení tabulky . $O(t\cdot log(m))$ $O(t)$ $O(m)$

Analýza algoritmu však musí vzít v úvahu, že pravděpodobnost úspěšného dešifrování je ve skutečnosti menší než jedna a doba dešifrování se může ukázat jako větší než deklarovaná z důvodů uvedených níže. $P_{úspěch}$

Sloučení řetězců je možné , když se tý klíč jednoho a tý klíč jiného řetězce shodují pro nějaký pár indexů. $i,j$ $i$ $j$
Možné tzv. "falešné poplachy" (angl. false alarms), kdy kryptoanalytik najde v tabulce více než jeden konečný klíč. V tomto případě musí zkontrolovat všechny relevantní řetězy.

[1] dolní mez pro pravděpodobnost úspěšného dešifrování lze odvodit :

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

Výše uvedený výraz odpovídá aproximaci, že funkce je náhodná veličina s rovnoměrným rozložením na množině klíčů. Stabilní kryptosystém by však měl být dobrým pseudonáhodným generátorem [1] . $F$

Vyhodnocení tohoto výrazu vede k následujícímu výsledku: nemá smysl brát součin větší než $mt^{2}$ $N$ : jinak spodní hranice pravděpodobnosti úspěchu rychle klesá.

Když se dostaneme $mt^{2}=N$

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

Kryptanalytik nyní může generovat nejen jednu, ale tabulky v každé tabulce pomocí vlastní redukční funkce (což zabrání slučování řetězců z různých tabulek). V tomto případě bude spodní hranice pravděpodobnosti úspěšného dešifrování: $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}

Volbou , kryptoanalytik obdrží paměťové a časové náklady (každá tabulka používá svou vlastní redukční funkci, takže při dešifrování musíte pro každou tabulku získat svůj vlastní řetězec) s pravděpodobností úspěchu blízkou jedné [poznámka pod čarou vysvětlující, proč bude počet falešných poplachů být malý a odkaz na Hellmana]. Vezmeme-li , získáme požadovaný čas a náklady na paměť. $l=t$ $mt$ $t^{2}$ $t=m=N^{{1/3}}$ $N^{{2/}}}$

Další příklady

Další algoritmy, které také používají „optimální výběr místa a času“:

Shanksův algoritmus , používaný k výpočtu diskrétních logaritmů .
Dynamické programování , ve kterém lze časovou náročnost úkolu, který je efektivně rozčleněn na dílčí úkoly, výrazně snížit zapamatováním – uložením již vypočítaných řešení dílčích úkolů.
Rainbow tabulky v kryptografii jsou vylepšenou verzí vyhledávacích tabulek pro invertování kryptografických hašovacích funkcí .

Viz také

Poznámky

↑ 1 2 3 4 Martin E. Hellman. Kryptanalytický kompromis s časovou pamětí. // Transakce na teorii informace. - červenec 1980. - č. 4.
↑ Philippe Oechslin. Rychlejší kryptoanalytický kompromis mezi časem a pamětí. // ISBN 3-540-40674-3 .
↑ Kormen T., Leyzerson Ch., Rivest R. Algoritmy: konstrukce a analýza. - 2. — M.: Williams, 2005. — 1296 s. — ISBN 5-8459-0857-4 .