Egyirányú funkció

Megoldatlan problémák a számítástechnikában : '' Vannak egyirányú függvények?''

Az egyirányú függvény olyan matematikai függvény , amely könnyen kiértékelhető bármilyen bemeneti érték esetén, de nehéz megtalálni az argumentumot a függvény értékének megfelelően. Itt a "könnyű" és a "nehéz" kifejezést a számítási komplexitás elmélete szerint kell érteni . Az előre és visszafelé történő transzformációk összetettsége közötti különbség meghatározza az egyirányú függvény kriptográfiai hatékonyságát. Egy függvény nem injektivitása nem elégséges feltétele annak, hogy egyoldalúnak nevezzük. Az egyirányú függvényeket nehezen visszafordíthatónak vagy visszafordíthatatlannak is nevezhetjük.

Az egyirányú függvények létezése még nem bizonyított. Létezésük bebizonyítja, hogy a P és az NP komplexitási osztályok nem egyenlőek , és az elméleti számítástechnika számos problémáját megoldják . Modern[ mikor? ] az aszimmetrikus kriptográfia azon a feltételezésen alapul, hogy léteznek egyirányú függvények.

Az egyirányú funkciók alapvető eszközök a kriptográfia , a személyazonosítás, a hitelesítés és az adatbiztonság egyéb területein. Bár az ilyen funkciók létezése még mindig nem bizonyított hipotézis, számos olyan versenyző van, amely kiállta a több évtizedes vizsgálatot. Sok közülük a legtöbb távközlési rendszer , valamint az e-kereskedelmi és internetes banki rendszer szerves részét képezi világszerte.

Definíció

Legyen az összes n hosszúságú bináris karakterlánc halmaza. Egy függvény egyirányú függvény , ha hatékonyan számítja ki polinomiális időben egy determinisztikus Turing-gépen , de nincs olyan polinom valószínűségi Turing-gép , amely exponenciálisan kicsinél nagyobb valószínűséggel invertálja ezt a függvényt. Vagyis bármely valószínűségi polinomiális géphez , bármilyen polinomhoz és elég nagyhoz : $\{0,1\}^{n}$ $f:\{0,1\}^{*}\jobbra \{0,1\}^{*}$ $M$ $p(n)$ $n\in \mathbb {N}$

Pr[M(f(m))\in f^{{-1}}(m)]<1/p(n)

ahol a sor véletlenszerűen kerül kiválasztásra a halmazon az egységes eloszlási törvény szerint. A gép működési idejét egy polinom korlátozza a kívánt előkép hosszában [1] . $m$ $\{0,1\}^{n}$ $M$

Létezés

Az egyirányú függvények létezése nem bizonyított. Ha f egyirányú függvény, akkor az inverz függvény megtalálása nehéz (definíció szerint), de könnyen ellenőrizhető ( f kiértékelésével ). Így az egyirányú függvény létezéséből következik, hogy P ≠ NP. Nem ismert azonban, hogy P ≠ NP egyirányú függvények létezését jelenti-e.

Az egyirányú funkciók létezése számos más hasznos kriptográfiai objektum létezését vonja maga után, beleértve a következőket:

pszeudo-véletlenszám-generátorok ;
ha van egy egyirányú függvény kemény bittel , akkor van elkötelezett bitminta ;
pszeudovéletlen függvénycsaládok ;
betétutánzatok ;
elektronikus digitális aláírás .

Használat

Egy egyirányú függvényről azt mondjuk, hogy hosszmegtartó, ha a függvényérték bithossza megegyezik az argumentum bithosszával. Ilyen függvényeket például pszeudovéletlen generátorokban használnak. Ha egy egyirányú függvény értékének bithossza bármilyen argumentumhossz esetén állandó, akkor azt hash függvénynek nevezzük . Tehát a hash funkciót jelszavak tárolására vagy elektronikus aláírás létrehozására használják [1] .

Az egyirányú függvényekből kriptográfiai sémák felépítésének problémáját a következő példa szemlélteti. Legyen egyirányú függvény, és létre kell hoznunk egy kriptorendszert egy titkos kulccsal . Egy ilyen titkosítási rendszerben csak egy kulcs van - egy titkos, amelyet a titkosított üzenet küldője és címzettje egyaránt ismer. A titkosítási és visszafejtési algoritmusok egyaránt ettől a titkos kulcstól függenek, és olyanok, mint bármely egyszerű szöveg esetén . Nyilvánvaló, hogy ha az üzenet kriptogramját a következővel számoljuk , akkor az ellenfél, aki elfogta , csak elhanyagolható valószínűséggel tud számolni . De először is nem világos, hogy egy legitim címzett hogyan tud visszaállítani egy üzenetet a kriptogramból? Másodszor, abból, hogy a függvény egyirányú, csak az következik, hogy az ellenfél nem tudja kiszámítani a teljes üzenetet. És ez a stabilitás nagyon alacsony szintje. Kívánatos, hogy egy ellenfél, aki ismeri a kriptogramot , ne tudja kiszámolni a nyílt szöveg egyetlen bitjét sem. $f$ $E_{K}$ $D_{K}$ $K$ $D_{K}(E_{K}(m))=m$ $m$ $d$ $m$ $d=f(m)$ $d$ $m$ $m$ $f$ $d$

Az első probléma megoldására egyirányú funkciókat találtak ki titkos bejárattal . Ez egy speciális típusú egyirányú függvény, amelyhez könnyű kiszámítani adott , de nehéz kiszámítani az ismertből . Van azonban néhány további titkos információ , amely, ha ismert, könnyen kiszámítható . $f(m)$ $m$ $f(m)$ $m$ $y$ $f(m)$ $y$ $m$

Egy másik példa az egyirányú függvények kriptográfiai sémákban való használatára a következő hitelesítési séma:

Az előfizető a következő üzenetsorozatot generálja: stb. , ahol egy egyirányú függvény. Ezután egy titkos csatornán (vagy egy értekezleten) továbbítják az előfizetőnek . Amikor meg kell erősíteni a személyazonosságát, üzenetet küld egy nyitott csatornán . ellenőrzések: . Legközelebb elküldi és ellenőrzi: stb. Az üzenetek elfogása a nyitott csatorna i-edik szakaszában nem ad semmit a támadónak, mivel nem fogja tudni megszerezni a megfelelő értéket , hogy ezután előfizetőként azonosítsa magát idő . Az ilyen sémákat a "barát/ellenség" azonosítására használják [2] . $A$ $m_{0},m_{1}=f(m_{0}),m_{2}=f(m_{1})$ $m_{100}}=f(m_{{99}})$ $f(m)$ $m_{100}}$ $B$ $A$ $B$ $m_{{99}}$ $B$ $f(m_{{99}})=?m_{{100}}$ $A$ $m_{{98}}$ $B$ $f(m_{{98}})=?m_{{99}}$ $m_{{i-1}}$ $A$

Munka igazolása

A számítógépes rendszerek szolgáltatással való visszaélésekkel szembeni védelme érdekében a kérelmező felet egy olyan probléma megoldására kérik, amelynek megoldása sok időt vesz igénybe, és az eredményt a kiszolgáló könnyen és gyorsan ellenőrzi. Az ilyen spam elleni védelemre példa a Hashcash [3] rendszer , amely részleges inverziós hash -t kér az e-mail feladójától.

A Bitcoin rendszer megköveteli, hogy a kapott hash összeg kisebb legyen egy speciális paraméternél. A kívánt hash összeg kereséséhez többször újra kell számítani a kiegészítő paraméter tetszőleges értékeinek felsorolásával. Körülbelül 10 percet vesz igénybe, amíg a rendszerben lévő összes számítógép megkeres egy hash összeget, amely szabályozza az új bitcoinok kibocsátásának sebességét. Az ellenőrzés csak egyetlen hash számítást igényel.

A kriptográfiai sémák erőssége

Az egyirányú függvények megléte szükséges feltétele sokféle kriptográfiai séma erősségének. Egyes esetekben ezt a tényt egészen egyszerűen megállapítják. Tekintsünk egy olyan függvényt , amely . Az algoritmus polinomiális időben kiszámítja. Mutassuk meg, hogy ha nem egyirányú függvény, akkor a kriptorendszer instabil. Tegyük fel, hogy létezik egy polinom valószínűségi algoritmus , amely valószínűséggel invertál legalább néhány polinom esetében . Itt van a kulcs hossza . A támadó megadhat egy kulcsot az algoritmushoz, és a megadott valószínűséggel értéket kaphat az előképből . Ezután a támadó bemenetként megadja az algoritmust, és kap egy kulcspárt . Bár nem feltétlenül ugyanaz, mint a , mégis definíció szerint egy titkosítási rendszer bármely egyszerű szöveghez . Mivel legalább a valószínűsége megtalálható , ami nem tekinthető elhanyagolhatónak a kriptográfiában, a kriptorendszer instabil. $f$ $f(r)=K_{1}$ $G$ $f$ $A$ $f$ $1/p(n)$ $p$ $n$ $K_1$ $A$ $K_1$ $r'$ $r'$ $G$ $(K_{1},K'_{2})$ $K'_{2}$ $K_{2}$ $D_{{K_{2}'}}(E_{{K_{1}}}(m))=m$ $m$ $K'_{2}$ $1/p(n)$

Az elmondottakból következik, hogy az egyirányú függvények létezésének feltételezése a leggyengébb kriptográfiai feltevés, ami elegendő lehet a különféle típusú erős kriptográfiai sémák létezésének bizonyítására. Annak megállapítására, hogy ez a feltétel valóban elegendő-e, a szakemberek jelentős erőfeszítéseit irányítják.

Manapság[ mikor? ] bebizonyosodott, hogy az egyirányú függvények megléte szükséges és elégséges feltétele a titkos kulccsal rendelkező erős kriptorendszerek, valamint többféle erős kriptográfiai protokoll, köztük az elektronikus aláírási protokollok létezésének. Másrészt ott van Impagliazzo és Rudich eredménye, amely elég erős érv amellett, hogy bizonyos típusú kriptográfiai sémák (beleértve a Diffie-Hellman-típusú kulcselosztási protokollokat is) erősebb feltételezéseket igényelnek, mint az egyirányú függvényfeltevés [4]. .

Jelöltek egyirányú funkciókra

Az alábbiakban az egyirányú funkciókra számos versenyzőt ismertetünk. Egyelőre nem tudni, hogy valóban egyirányúak-e, de a kiterjedt kutatások még nem tudtak mindegyikre hatékony inverz algoritmust találni.

Szorzás és szorzás

A függvény bemenetként két prímszámot vesz fel bináris ábrázolásban, és a szorzatukat adja vissza . Ezt a függvényt a sorrendben számíthatjuk ki , ahol a bemenet teljes hossza (bináris számok száma). Egy inverz függvény felépítéséhez meg kell találni egy adott egész szám tényezőit . A tényezők meghatározása nagyon időigényes számítási művelet. Egy egész számot prímtényezőkre bontó algoritmus összetettségének becslésére gyakran használják a függvényt: $f$ $p$ $q$ $N=f(p,q)$ $O$ $(n^{2})$ $n$ $N$ $N$

L_{N}(\alpha ,\beta )=\exp((\beta +o(1)(\ln N)^{\alpha }(\ln \ln N)^{1-\alpha } ))

Ha az algoritmus összetettsége , akkor polinomiális időre van szüksége a futáshoz (a feladat mérete a bemeneten, a szám bitjeinek száma, ). A bonyolultság miatt exponenciális időre lesz szükség. Így a függvény növekedési üteme polinomiális és exponenciális között van. Ezért az ilyen bonyolultságú algoritmusok szubexponenciális időt igényelnek [5] . $O(L_{N}(0,\béta ))$ $\ln N$ $O(L_{N}(1,\béta ))$ $L_{N}(\alpha ,\beta )$ $0 < \alpha < 1$

Számos módszer létezik egy szám faktorálására prímszámokkal és . Néhány közülük: $N=p*q$ $p$ $q$

Próbaosztás - ebben az algoritmusban minden olyan prímszám esetén, amely nem haladja meg a -t, a feltétel ellenőrzésre kerül . Egy ilyen algoritmus közel áll a kimerítő kereséshez, és exponenciálisan bonyolult . $p$ ${\sqrt {N}}$ $N/p\in {\mathbb Z}$ $O(L_{N}(1,1))$
Az elliptikus görbe módszer akkor működik jól, ha az egyik prímtényező nem haladja meg a . Bonyolultságát a következőre becsüljük . $p$ $2^{50}$ $L_{p}(1/2,c)$
A négyzetes szita valószínűleg a leggyorsabb módja a és közötti számok faktorizálásának . A komplexitása az . $10^{{80}}$ $10^{{100}}$ $L_{p}(1/2,1)$
Kvadratikus szita egy számmezőben . Jelenleg ez a legsikeresebb módszer a 100 vagy több tizedesjegyet tartalmazó számokhoz. ig használható számok faktorizálására , összetettségét pedig [5] -re becsüljük . $10^{{155}}$ $L_N(1/3,\;(64/9)^{\frac{1}{3)))$

A függvény félprímek tartományára általánosítható . Ne feledje, hogy tetszőleges esetén nem lehet egyoldalú , mivel a szorzatuk 2-es tényező ¾ valószínűséggel. $f$ $p,q>1$

Vegye figyelembe, hogy a polinomiális összetettségű faktorizáció lehetséges kvantumszámítógépen Shor algoritmusát használva ( BQP osztály ).

Négyzetre emelés és a négyzetgyök vétele modulo

A függvény két egész számot vesz fel: és , ahol két és két prímszám szorzata . A kimenet a maradék a -val való osztás után . Az inverz függvény megtalálásához ki kell számítani a modulo négyzetgyököt , vagyis meg kell találni, hogy ismert-e az is . Kimutatható, hogy ez utóbbi probléma számításilag ugyanolyan nehéz, mint a faktorizálás. $f$ $x$ $N$ $N$ $p$ $q$ $x^{2}$ $N$ $N$ $x$ $y$ $x^{2}{\bmod N}=y$ $N$

A Rabin kriptorendszer azon a feltételezésen alapul, hogy a Rabin függvény egyirányú.

Diszkrét exponenciális és logaritmus

A diszkrét kitevő függvény argumentumként egy prímszámot és egy egész számot vesz fel a -tól tartományba , és a maradékot adja vissza, miután elosztja néhányat -val . Ez a függvény könnyen kiszámítható időben , ahol a bitek száma a -ban . Ennek a függvénynek a megfordításához a modulo diszkrét logaritmus kiszámítása szükséges . Legyen véges Abel-csoport, például véges mező multiplikatív csoportja vagy véges mező feletti elliptikus görbe. A diszkrét logaritmusok számításának feladata egy egész szám meghatározása , amely az adatok ismeretében kielégíti a következő összefüggést: $f$ $p$ $x$ $0$ $p-1$ $A^{x}$ $p$ $O$ $(n^{3})$ $n$ $p$ $p$ $(G*)$ $x$ $A,B$

A^{x}=B

Egyes csoportok számára ez a feladat meglehetősen egyszerű. Például ha egész számok csoportja modulo összeadás. Más csoportok számára azonban ez a feladat nehezebb. Például egy véges mezős multiplikatív csoportban a diszkrét logaritmus probléma megoldásának legismertebb algoritmusa a másodfokú szita módszer egy számmezőben . A diszkrét logaritmusok kiszámításának bonyolultságát ebben az esetben a következőre becsüljük . Az ElGamal-séma ezen a problémán alapul [6] . $G$ $G$ $N$ $L_{N}(1/3,c)$

Az olyan csoportok esetében, mint az elliptikus görbe, a diszkrét logaritmus probléma még nehezebb. A jelenleg elérhető legjobb módszer a diszkrét logaritmusok kiszámítására egy mező feletti általános elliptikus görbén, a Pollard -féle ρ-módszer . A komplexitása . Ez egy exponenciális algoritmus, így az elliptikus görbe titkosítási rendszerek általában kis, körülbelül 160 bites kulccsal működnek. Míg a faktoráláson vagy véges mezőkben diszkrét logaritmusok kiszámításán alapuló rendszerek 1024 bites kulcsokat használnak [6] . $\mathbb {F} _{q}$ $O(L_{N}(1,1/2))$

A diszkrét logaritmus problémához számos szorosan kapcsolódó probléma is kapcsolódik. Adjunk meg egy véges Abel-csoportot : $(G*)$

A Diffie-Hellman probléma , amely a következő: adott elemei . Ki kell számolni . $A\in G,B=A^{x},C=A^{y}$ $D=A^{{xy}}$
A Diffie-Hellman kiválasztási probléma . Adott: . Meg kell határozni, hogy termék -e és az-e . $A\in G,B=A^{x},C=A^{y},D=A^{z}$ $z$ $x$ $y$

Kimutatható, hogy a Diffie-Hellman-kiválasztási probléma semmivel sem nehezebb, mint a Diffie-Hellman-probléma, és a Diffie-Hellman-probléma sem nehezebb, mint a diszkrét logaritmus [6] .

Kriptográfiai hash függvények

Számos kriptográfiai hash függvény van (pl . SHA-256 ), amelyek gyorsan kiszámíthatók. Az egyszerűbb verziók egy része nem ment át komplex elemzésen, de a legerősebb változatok továbbra is gyors, praktikus megoldásokat kínálnak az egyirányú számításokhoz. E funkciók elméleti támogatásának nagy része a korábban sikeres támadások meghiúsítására irányul.

További versenyzők

Az egyirányú függvények más versenyzői a véletlenszerű lineáris kódok dekódolásának nehézségén és más problémákon alapulnak.

Lásd még

Jegyzetek

↑ 1 2 Ptitsyn, 2002 , p. 38-39.
↑ Hitelesítési séma .
↑ Hashcash – A szolgáltatásmegtagadás elleni ellenintézkedés (2002)
↑ Russell Impagliazzo, Steven Rudich. A személyes adatok visszakeresése nem jelent egyirányú permutációt .
↑ 1 2 Smart, 2005 , p. 185-186.
↑ 1 2 3 Smart, 2005 , p. 187-188.

Linkek

Oded Goldreich. 1. kötet, Alapvető eszközök // A kriptográfia alapjai . - Cambridge University Press , 2001. - ISBN 0-521-79172-3 .
Jonathan Katz, Yehuda Lindell. Bevezetés a modern kriptográfiába. - CRC Press , 2007. - ISBN 1-58488-551-3 .
Michael Sipser 10.6.3. szakasz: Egyirányú függvények // Bevezetés a számításelméletbe . - PWS Kiadó, 1997. - P. 374 -376. — ISBN 0-534-94728-X .
Christos Papadimitriou . 12.1. szakasz: Egyirányú függvények // Számítási komplexitás. — 1. kiadás. - Addison Wesley , 1993. - S. 279-298. — ISBN 0-201-53082-1 .
fejezet 2.3. Egyirányú függvények // Bevezetés a kriptográfiába / Szerk. V. V. Jascsenko.
2.5.2. fejezet Egyirányú függvény // A determinisztikus káosz elméletének alkalmazása a kriptográfiában / Ptitsyn N. - 2002. (elérhetetlen link)
7.2. fejezet Egyirányú funkciók // Kriptográfia / Smart N. - 2005. - ISBN 5-94836-043-1 .
4.1. fejezet Egyirányú funkciók (orosz) ? . Letöltve: 2014. október 9. Az eredetiből archiválva : 2016. december 3.. (határozatlan)