Ajan ja muistin kompromissi

Aika- ja muistikompromissi _ _ _ _ Kompromissilähestymistapa useiden tietojenkäsittelytieteen ongelmien tarvittavankäytetäänjossa, ratkaisemiseen muistin määrän ja ohjelman suoritusnopeuden käänteistä suhdetta: laskenta-aikaa voidaan pidentää vähentämällä käytettyä muistia tai päinvastoin vähentää lisäämällä käytetyn muistin määrää.

RAM- muistin (RAM) ja kiintolevymuistin suhteellisten kustannusten laskun vuoksi (jonkin ajanjakson aikana kiintolevytilan hinta tuli halvemmaksi paljon nopeammin kuin muiden tietokoneen komponenttien kustannukset ), tekniikoita, jotka käyttävät laskenta-ajan lyhentämiseen käytettävät muistit ovat vähitellen levinneet. Samaan aikaan tekniikat, kuten tietojen pakkaus , osoittavat vaihtoehtoisen lähestymistavan - taloudellista muistin käyttöä, koska tiedot muunnetaan tiedostomuodosta toiseen.

Sovellusesimerkkejä

Hakutaulukot

Monet hakuongelmat, kuten jatkuva selkäreppuongelma , diskreetti logaritmiongelma tai yksisuuntaisen funktion invertointiongelma , jotka ratkaistaan itse asiassa luetteloimalla, mahdollistavat samalla ns. hakutaulukot (englanniksi lookup tables ) [1] . Ajatuksena on tämä: sen sijaan, että iteroitaisiin kaikki mahdolliset ratkaisut ilman lisämuistia tai laskettaisiin ne kaikki kerran etukäteen ja tallennettaisiin muistiin (usein ei ole ensimmäistä eikä toista mahdollisuutta), voit laskea osan toteutettavissa olevasta. arvot, ja organisoituaan ne erityiseen tietorakenteeseen - hakutaulukkoon - käyttää sitä lisälaskennan suorittamiseen suoraan ongelmaa ratkaistaessa.

Tämän artikkelin erillinen osa on omistettu tämän lähestymistavan soveltamiselle kryptografiassa.

Tietojen pakkaus

Optimaalisen "paikka-aika" -suhteen valintaa voidaan soveltaa tiedon tallennusongelmaan. Tietojen tallentaminen pakkaamattomassa muodossa vaatii enemmän muistia, mutta sen hakeminen vie vähemmän aikaa kuin pakatussa muodossa tallennettujen tietojen hakeminen. Tehtävästä riippuen toinen tai toinen vaihtoehto voi olla parempi.

Klassinen esimerkki kompaktista dataesityksestä on esimerkiksi tieteellisten artikkeleiden kirjoittamiseen käytetty Τ Ε Χ -kaavaesitysmuoto . Käyttäjän työn tuloksena on erikoismuotoinen tiedosto, joka on tarvittaessa helposti muunnettavissa paljon "raskaampi" pdf -tiedostoksi, jota puolestaan voi jo käyttää dokumentin katseluun suosituimmissa katseluohjelmissa kuin ne, jotka ovat ominaisia Τ Ε Χ .

Kierrätyspromootio

Loop purkaus on erittäin suosittu koodin optimointitekniikka, jota käytetään monissa kääntäjissä. Ajatuksena on lisätä silmukan yhden iteraation aikana suoritettavien käskyjen määrää. Tämän seurauksena iteraatioiden määrä vähenee (yhteen rajassa: kaikki käskyt suoritetaan peräkkäin), mikä puolestaan lisää datavälimuistin tehokkuutta .

Kryptografia

Tässä osiossa käsitellään klassista esimerkkiä Space-Time Trade-Off -lähestymistavan käyttämisestä kryptografiassa - hakutaulukoiden käyttöä salausteknisen hajautusfunktion kääntämisen salausongelman ratkaisemisessa .

Kryptanalyyttinen laskenta vaatii huomattavia laskentakustannuksia. Siinä tapauksessa, että salausjärjestelmä joudutaan murtamaan toistuvasti, olisi loogista suorittaa tyhjentävä luettelo etukäteen ja tallentaa lasketut arvot muistiin. Kun olet tehnyt tämän kerran, voit luetella lisää lähes välittömästi [2] . Todellisuudessa tätä menetelmää ei kuitenkaan voida soveltaa valtavien muistikustannusten vuoksi.

Hellmanin menetelmä

Vuonna 1980 Martin Hellman ehdotti kompromissilähestymistapaa kryptoanalyysin ongelmaan, joka mahdollistaa salausjärjestelmän analysoinnin, jossa on avaimia toiminnassa, myös muistikustannuksilla [1] . Tämä tulee mahdolliseksi, kun mahdollisten avainten O(n)-esihankinta on suoritettu kerran. $N$ $N^{{2/3}}$ $N^{{2/3}}$

Idea on seuraava.

Salli salausalgoritmin käyttää yksisuuntaista toimintoa . Yksisuuntaisen funktion ominaisuuksien mukaan käytetyn avaimen johtaminen tunnetusta parista on vaikea tehtävä, kun taas funktion laskeminen tietystä selväkielisestä on yksinkertainen tehtävä. $S_{k_{i}}(P)$ $k_i$ $P_{0},C_{0}$

Kryptanalyytikko käyttää valittua selkeää tekstiä koskevaa hyökkäystä ja hankkii yhden salatekstin , joka vastaa selkeää tekstiä : $C_{0}$ $P_0$

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

Tehtävänä on löytää avain , jota käytettiin salaukseen. Tätä varten sinun on löydettävä tapa laskea mahdolliset avaimet. Otetaan käyttöön ns. vähennystoiminto , joka määrittää salatekstille tietyn avaimen (avaimen pituus on yleensä pienempi kuin salatekstin pituus, tästä syystä termi): $k$ $R(C)$ $C_{i}$ $k_{{i+1}}$

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

Vähennysfunktion laskeminen on yksinkertainen toimenpide.

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

yhdistää avaimen toiseen avaimeen . Nyt saamme mielivaltaisen pitkän avaimenperän: $k_i$ $k_{{i+1}}$

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

Hakutaulukon rakentamiseksi kryptanalyytikolle annetaan satunnaisia avaintilan elementtejä. Jokaisesta avaimesta saadaan edellä kuvatulla menetelmällä avainketju, jonka pituus on . Kirjoitamme muistiin vain kunkin ketjun alku- ja loppuavaimet (lajittelemme avainparit viimeisen avaimen mukaan ). Siten valmis taulukko vie muistisoluja. Taulukon luominen vaatii operaatioita. $m$ $t$ $O(m)$ $mt$

Kun taulukko on muodostettu, kryptanalyytikko voi luetella seuraavalla tavalla. Lähdemme siitä, että salauksessa käytetty avain löytyi taulukon luomisen yhteydessä. Tässä tapauksessa yksi viimeisistä muistiin tallennetuista avaimista voidaan saada siitä enintään t funktion käyttöoperaatiolla . $k$ $f$ $m$

Jokaisen vähennysoperaation sovelluksen jälkeen kryptanalyytikko etsii taulukosta seuraavan vastaanotetun avaimen (voit löytää sen tai varmistaa, että sitä ei ole olemassa binäärihakua käyttäville toiminnoille , koska taulukko lajitellaan lopullisen avaimen mukaan). Kun yksi viimeisistä avaimista on tavattu, on mahdollista palauttaa koko vastaava ketju sitä vastaavasta alkuperäisestä avaimesta; haluttu avain on sen toiseksi viimeinen avain. $log(m)$

Avaimen löytäminen kestää siis [3] ; Logaritmisen tekijän huomioimatta meillä on . Tässä tapauksessa muistikustannukset taulukon tallentamisesta ovat . $O(t\cdot log(m))$ $O t)$ $O(m)$

Algoritmin analysoinnissa on kuitenkin otettava huomioon, että onnistuneen salauksen purkamisen todennäköisyys on itse asiassa pienempi kuin yksi ja salauksen purkuaika voi osoittautua ilmoitettua pidemmäksi alla mainituista syistä. $P_{menestys}$

Ketjujen yhdistäminen on mahdollista , kun yhden ketjun th avain ja toisen ketjun avain osuvat yhteen jollekin indeksiparille. $i, j$ $i$ $j$
Mahdollinen ns. "vääriä hälytyksiä" (eng. false alarms), kun kryptanalyytikko löytää taulukosta useamman kuin yhden lopullisen avaimen. Tässä tapauksessa hänen on tarkistettava kaikki asiaankuuluvat ketjut.

[1] alaraja onnistuneen salauksen todennäköisyydelle voidaan johtaa :

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

Yllä oleva lauseke vastaa approksimaatiota, että funktio on satunnaismuuttuja, jolla on tasainen jakautuminen avainjoukolle. Vakaan kryptojärjestelmän tulisi kuitenkin olla hyvä näennäissatunnainen generaattori [1] . $f$

Tämän lausekkeen arviointi johtaa seuraavaan tulokseen: ei ole mitään järkeä ottaa tuotetta suurempaa kuin $mt^{2}$ $N$ : muuten onnistumisen todennäköisyyden alaraja putoaa nopeasti.

Kun saamme $mt^{2}=N$

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

Kryptanalyytikko voi nyt luoda ei vain yhtä, vaan taulukoita jokaiseen taulukkoon käyttämällä omaa pelkistystoimintoaan (joka välttää ketjujen yhdistämisen eri taulukoista). Tässä tapauksessa onnistuneen salauksen purkamisen todennäköisyyden alaraja on: $l$

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

Valitsemalla , kryptanalyytikko saa muisti- ja aikakustannukset (jokainen taulukko käyttää omaa vähennystoimintoaan, joten salauksen purkamisen yhteydessä on hankittava oma ketju jokaiselle taulukolle) onnistumistodennäköisyydellä, joka on lähellä yhtä [alaviite, jossa selitetään, miksi väärien hälytysten määrä ole pieni ja linkitä Hellman]. Ottamalla , saamme tarvittavat aika- ja muistikustannukset. $l=t$ $mt$ $t^{2}$ $t=m=N^{{1/3}}$ $N^{{2/3}}$

Muita esimerkkejä

Muut algoritmit, jotka käyttävät myös "optimaalista paikka-ajan valintaa":

Shanksin algoritmi , jota käytetään diskreettien logaritmien laskemiseen .
Dynaaminen ohjelmointi , jossa tehokkaasti alitehtäviin jaetun tehtävän aikamonimutkaisuutta voidaan vähentää merkittävästi muistiin tallentamalla - tallentaa alitehtäviin jo lasketut ratkaisut.
Sateenkaaritaulukot kryptografiassa ovat paranneltu versio hakutaulukoista kryptografisten hajautusfunktioiden kääntämiseen .

Katso myös

Muistiinpanot

↑ 1 2 3 4 Martin E. Hellman. Kryptanalyyttinen aika-muistin vaihtokauppa. // Transactions on Information Theory. - Heinäkuu 1980. - Nro 4.
↑ Philippe Oechslin. Nopeampi kryptanalyyttinen aikamuistin vaihtokauppa. // ISBN 3-540-40674-3 .
↑ Kormen T., Leyzerson Ch., Rivest R. Algoritmit: rakentaminen ja analyysi. - 2. - M.: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .