Jednosměrná funkce

Nevyřešené problémy v informatice : '' Existují jednosměrné funkce?''

Jednosměrná funkce je matematická funkce , kterou lze snadno vyhodnotit pro jakoukoli vstupní hodnotu, ale je obtížné najít argument vzhledem k hodnotě funkce. Zde je třeba chápat „snadné“ a „těžké“ z hlediska teorie výpočetní složitosti . Rozdíl mezi složitostí dopředných a zpětných transformací určuje kryptografickou účinnost jednosměrné funkce. Neinjektivita funkce není postačující podmínkou pro její volání jednosměrné. Jednosměrné funkce lze také nazvat obtížně vratné nebo nevratné.

Existence jednosměrných funkcí zatím nebyla prokázána. Jejich existence prokáže, že třídy složitosti P a NP si nejsou rovné a vyřeší přitom řadu problémů v teoretické informatice . Moderní[ kdy? ] asymetrická kryptografie je založena na předpokladu, že jednosměrné funkce existují.

Jednosměrné funkce jsou základními nástroji v kryptografii , osobní identifikaci, autentizaci a dalších oblastech zabezpečení dat. Ačkoli je existence takových funkcí stále neprokázanou hypotézou, existuje několik uchazečů, kteří obstáli v desetiletích zkoumání. Mnohé z nich jsou nedílnou součástí většiny telekomunikačních systémů , stejně jako systémů elektronického obchodování a internetového bankovnictví po celém světě.

Definice

Nechť je množina všech binárních řetězců délky n. Funkce je jednosměrná funkce , pokud je efektivně počítána v polynomiálním čase na deterministickém Turingově stroji , ale neexistuje žádný polynomiální pravděpodobnostní Turingův stroj , který by tuto funkci invertoval s více než exponenciálně malou pravděpodobností. To znamená pro jakýkoli pravděpodobnostní polynomický stroj , pro jakýkoli polynom a dostatečně velký : $\{0,1\}^{n}$ $f:\{0,1\}^{*}\rightarrow \{0,1\}^{*}$ $M$ $p(n)$ $n\in \mathbb {N}$

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

kde řada je vybrána náhodně na sadě v souladu se zákonem o rovnoměrném rozdělení. Provozní doba stroje je omezena polynomem v délce požadovaného předobrazu [1] . $m$ $\{0,1\}^{n}$ $M$

Existence

Existence jednosměrných funkcí nebyla prokázána. Je-li f jednosměrná funkce, pak je nalezení inverzní funkce obtížné (podle definice), ale snadno ověřitelné (vyhodnocením f na ní). Z existence jednosměrné funkce tedy vyplývá, že P ≠ NP. Není však známo, zda P ≠ NP implikuje existenci jednosměrných funkcí.

Existence jednosměrných funkcí bude znamenat existenci mnoha dalších užitečných kryptografických objektů, včetně:

generátory pseudonáhodných čísel ;
pokud existuje jednosměrná funkce s pevným bitem , pak existuje vzor potvrzení bitu ;
rodiny pseudonáhodných funkcí ;
imitace vložek ;
elektronický digitální podpis .

Použití

O jednosměrné funkci se říká, že si zachovává délku, pokud je bitová délka hodnoty funkce rovna bitové délce argumentu. Takové funkce se používají například v pseudonáhodných generátorech. Pokud je bitová délka hodnoty jednosměrné funkce konstantní pro jakoukoli délku argumentu, nazývá se hashovací funkce . Hašovací funkce se tedy používá k ukládání hesel nebo vytváření elektronického podpisu [1] .

Obtížnost problému konstrukce kryptografických schémat z jednosměrných funkcí lze ilustrovat na následujícím příkladu. Nechť je to jednosměrná funkce a potřebujeme vytvořit kryptosystém s tajným klíčem . V takovém kryptosystému existuje pouze jeden klíč – tajný, který zná odesílatel i příjemce šifrované zprávy. Šifrovací a dešifrovací algoritmy závisí na tomto tajném klíči a jsou takové, že pro jakýkoli prostý text . Je jasné, že pokud je kryptogram zprávy vypočítán jako , pak protivník, který zachytil , může počítat jen se zanedbatelnou pravděpodobností. Ale za prvé, není jasné, jak může legitimní příjemce obnovit zprávu z kryptogramu? Za druhé, z toho, že funkce je jednosměrná, vyplývá pouze to, že protivník nemůže vypočítat celou zprávu. A to je velmi nízká úroveň stability. Je žádoucí, aby protivník, který zná kryptogram , nemohl vypočítat jediný bit z otevřeného textu. $F$ $E_{K}$ $D_{K}$ $K$ $D_{K}(E_{K}(m))=m$ $m$ $d$ $m$ $d=f(m)$ $d$ $m$ $m$ $F$ $d$

K vyřešení prvního problému byly vynalezeny jednosměrné funkce s tajným vchodem . Jedná se o speciální typ jednosměrné funkce, pro kterou je snadné vypočítat dané , ale obtížné vypočítat ze známých . Existují však některé další tajné informace , které, pokud jsou známy, lze snadno vypočítat . $f(m)$ $m$ $f(m)$ $m$ $y$ $f(m)$ $y$ $m$

Dalším příkladem použití jednosměrných funkcí v kryptografických schématech je následující schéma ověřování:

Účastník generuje následující sekvenci zpráv: atd. , kde je jednosměrná funkce. Poté je předán prostřednictvím tajného kanálu (nebo na schůzce) předplatiteli . Když je potřeba potvrdit jeho identitu, odešle zprávu přes otevřený kanál . kontroluje: . Příště odešle a zkontroluje: atd. Zachycení zpráv v i-té fázi v otevřeném kanálu útočníkovi nic nedá, protože nebude schopen získat odpovídající hodnotu , aby se identifikoval jako odběratel. čas . Taková schémata se používají k identifikaci „přítele/nepřítele“ [2] . $A$ $m_{0},m_{1}=f(m_{0}),m_{2}=f(m_{1})$ $m_{{100}}=f(m_{{99}})$ $f(m)$ $m_{100}{101}$ $B$ $A$ $B$ $m_{{99}}$ $B$ $f(m_{{99}})=?m_{100}}$ $A$ $m_{{98}}$ $B$ $f(m_{{98}})=?m_{{99}}$ $m_{{i-1}}$ $A$

Doklad o práci

K ochraně počítačových systémů před zneužitím služeb je požadující strana požádána, aby vyřešila problém, jehož řešení zabere mnoho času, a výsledek je snadno a rychle zkontrolován obsluhující stranou. Příkladem takové antispamové ochrany je systém Hashcash [3] , který od odesílatele e-mailu požaduje haš částečné inverze.

Bitcoinový systém vyžaduje, aby výsledný hash součet byl menší než speciální parametr. Chcete-li vyhledat požadovaný hash součet, je nutné jej několikrát přepočítat s výčtem libovolných hodnot dodatečného parametru. Všem počítačům v systému trvá asi 10 minut, než vyhledají jednu hashovací sumu, která reguluje rychlost vydávání nových bitcoinů. Ověření vyžaduje pouze jeden výpočet hash.

Síla kryptografických schémat

Existence jednosměrných funkcí je nezbytnou podmínkou síly mnoha typů kryptografických schémat. V některých případech je tato skutečnost stanovena zcela jednoduše. Uvažujme funkci takovou, že . Je vyčíslitelná pomocí algoritmu v polynomiálním čase. Ukažme, že pokud nejde o jednosměrnou funkci, pak je kryptosystém nestabilní. Předpokládejme, že existuje polynomiální pravděpodobnostní algoritmus , který invertuje s pravděpodobností alespoň pro nějaký polynom . Zde je délka klíče . Útočník může zadat klíč do algoritmu a získat nějakou hodnotu z předobrazu se zadanou pravděpodobností . Dále útočník zadá algoritmus jako vstup a obdrží pár klíčů . I když to není nutně stejné jako , je to nicméně z definice kryptosystém pro jakýkoli otevřený text . Vzhledem k tomu, že je nalezen s pravděpodobností nejméně , což není v kryptografii považováno za zanedbatelné, je kryptosystém nestabilní. $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)$

Z toho, co bylo řečeno, vyplývá, že předpoklad existence jednosměrných funkcí je nejslabším kryptografickým předpokladem, který může stačit k prokázání existence silných kryptografických schémat různého typu. Ke zjištění, zda je tato podmínka skutečně dostatečná, směřuje značné úsilí specialistů.

Dnes[ kdy? ] je prokázáno, že existence jednosměrných funkcí je nezbytnou a postačující podmínkou pro existenci silných kryptosystémů s tajným klíčem i silných kryptografických protokolů více typů, včetně protokolů elektronického podpisu. Na druhé straně existuje výsledek Impagliazzo a Rudich, což je dostatečně silný argument, že určité typy kryptografických schémat (včetně protokolů distribuce klíčů typu Diffie-Hellman) vyžadují silnější předpoklady než předpoklad jednosměrné funkce [4]. .

Kandidáti na jednosměrné funkce

Níže je popsáno několik uchazečů o jednosměrné funkce. V tuto chvíli není známo, zda jsou skutečně jednosměrné, ale rozsáhlý výzkum dosud nedokázal najít účinný inverzní algoritmus pro každý z nich.

Násobení a faktorizace

Funkce vezme jako vstup dvě prvočísla a v binární reprezentaci a vrátí jejich součin . Tuto funkci lze vypočítat v pořadí time , kde je celková délka (počet binárních čísel) vstupu. Sestavení inverzní funkce vyžaduje nalezení faktorů daného celého čísla . Stanovení faktorů je časově velmi náročná výpočetní operace. K odhadu složitosti algoritmu, který rozkládá celé číslo na prvočísla, se často používá funkce: $F$ $p$ $q$ $N=f(p,q)$ $Ó$ $(n^{2})$ $n$ $N$ $N$

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

Pokud má algoritmus složitost , pak potřebuje ke svému běhu polynomiální čas (velikost problému na vstupu, počet bitů čísla, ). Se složitostí to bude vyžadovat exponenciální čas. Rychlost růstu funkce je tedy mezi polynomiální a exponenciální. Proto se říká, že algoritmy s takovou složitostí vyžadují sub-exponenciální čas [5] . $O(L_{N}(0,\beta ))$ $\ln N$ $O(L_{N}(1,\beta ))$ $L_{N}(\alpha,\beta)$ $0 < \alpha < 1$

Existuje několik metod pro rozklad čísla s prvočísly a . Někteří z nich: $N=p*q$ $p$ $q$

Zkušební dělení - v tomto algoritmu se pro všechna prvočísla nepřesahující , kontroluje podmínka . Takový algoritmus se blíží vyčerpávajícímu vyhledávání a má exponenciální složitost . $p$ ${\sqrt {N}}$ $N/p\in {\mathbb Z}$ $O(L_{N}(1,1))$
Metoda eliptické křivky funguje dobře, pokud jeden z hlavních faktorů nepřekročí . Jeho složitost se odhaduje jako . $p$ $2^{50}$ $L_{p}(1/2,c)$
Kvadratické síto je pravděpodobně nejrychlejší způsob rozkladu čísel mezi a . Jeho složitost je . $10^{{80}}$ $10^{{100}{101}}$ $L_{p}(1/2,1)$
Kvadratické síto v číselném poli . Toto je v současnosti nejúspěšnější metoda pro čísla se 100 a více desetinnými místy. Lze jej použít k rozkladu čísel do , a jeho složitost se odhaduje jako [5] . $10^{{155}}$ $L_N(1/3;\;(64/9)^{\frac{1}{3)))$

Funkce může být zobecněna na řadu poloprvek . Všimněte si, že to nemůže být jednostranné pro libovolné , protože jejich součin má faktor 2 s pravděpodobností ¾. $F$ $p,q>1$

Všimněte si, že faktorizace s polynomiální složitostí je možná na kvantovém počítači pomocí Shorova algoritmu ( třída BQP ).

Druhá mocnina a odmocnina modulo

Funkce trvá dvě celá čísla: a , kde je součin dvou prvočísel a . Výstupem je zbytek po vydělení . Nalezení inverzní funkce vyžaduje výpočet druhé odmocniny modulo , tedy zjištění, zda je také známo, že . Lze ukázat, že druhý problém je výpočetně stejně obtížný jako faktorizace. $F$ $X$ $N$ $N$ $p$ $q$ $x^{2}$ $N$ $N$ $X$ $y$ $x^{2}{\bmod N}=y$ $N$

Rabinův kryptosystém je založen na předpokladu, že Rabinova funkce je jednosměrná.

Diskrétní exponenciála a logaritmus

Funkce diskrétního exponentu bere jako argumenty prvočíslo a celé číslo v rozsahu od do a vrací zbytek po dělení některých číslem . Tuto funkci lze snadno vypočítat v čase , kde je počet bitů v . Inverze této funkce vyžaduje výpočet diskrétního logaritmu modulo . Nechť je konečná abelovská grupa, například multiplikativní grupa konečného pole nebo eliptická křivka nad konečným polem. Úkolem výpočtu diskrétních logaritmů je určit celé číslo , které vzhledem k datům vyhovuje vztahu: $F$ $p$ $X$ $0$ $p-1$ $A^{x}$ $p$ $Ó$ $(n^{3})$ $n$ $p$ $p$ $(G*)$ $X$ $A,B$

A^{x}=B

Pro některé skupiny je tento úkol docela jednoduchý. Pokud je například skupina celých čísel modulo sčítání. Pro ostatní skupiny je však tento úkol obtížnější. Například v multiplikativní grupě konečných polí je nejznámějším algoritmem pro řešení problému diskrétního logaritmu metoda kvadratického síta v číselném poli . Složitost výpočtu diskrétních logaritmů se v tomto případě odhaduje jako . Na tomto problému je založeno schéma ElGamal [6] . $G$ $G$ $N$ $L_{N}(1/3,c)$

Pro skupiny, jako je eliptická křivka, je problém diskrétního logaritmu ještě obtížnější. Nejlepší metoda aktuálně dostupná pro výpočet jednotlivých logaritmů přes obecnou eliptickou křivku nad polem se nazývá Pollardova ρ-metoda . Jeho složitost . Toto je exponenciální algoritmus, takže kryptosystémy s eliptickou křivkou mají tendenci pracovat s malým klíčem, kolem 160 bitů. Zatímco systémy založené na faktoringu nebo počítání diskrétních logaritmů v konečných polích používají klíče 1024 bitů [6] . $\mathbb {F} _{q}$ $O(L_{N}(1,1/2))$

Několik úzce souvisejících problémů také souvisí s problémem diskrétního logaritmu. Nechť je dána konečná abelovská grupa : $(G*)$

Problém Diffie-Hellman , který je následující: dané prvky . Je nutné vypočítat . $A\in G,B=A^{x},C=A^{y}$ $D=A^{{xy}}$
Problém výběru Diffie-Hellmana . Vzhledem k tomu: . Je nutné určit, zda a je produktem . $A\in G,B=A^{x},C=A^{y},D=A^{z}$ $z$ $X$ $y$

Lze ukázat, že problém Diffie-Hellmanova výběru není o nic obtížnější než problém Diffie-Hellman a problém Diffie-Hellman není o nic obtížnější než problém diskrétního logaritmu [6] .

Kryptografické hašovací funkce

Existuje mnoho kryptografických hashovacích funkcí (např . SHA-256 ), které se rychle počítají. Některé jednodušší verze neprošly komplexní analýzou, ale nejsilnější verze nadále nabízejí rychlá a praktická řešení pro jednosměrné výpočty. Velká část teoretické podpory těchto funkcí je zaměřena na zmaření některých dříve úspěšných útoků.

Další uchazeči

Další uchazeči o jednosměrné funkce vycházejí z obtížnosti dekódování náhodných lineárních kódů a dalších problémů.

Viz také

Poznámky

↑ 1 2 Ptitsyn, 2002 , str. 38-39.
↑ Schéma autentizace .
↑ Hashcash – A Denial of Service Counter-Measure (2002)
↑ Russell Impagliazzo, Steven Rudich. Získávání soukromých informací neznamená jednosměrné permutace .
↑ 1 2 Smart, 2005 , str. 185-186.
↑ 1 2 3 Smart, 2005 , str. 187-188.

Odkazy

Oded Goldreich. Svazek 1, Základní nástroje // Základy kryptografie . - Cambridge University Press , 2001. - ISBN 0-521-79172-3 .
Jonathan Katz, Yehuda Lindell. Úvod do moderní kryptografie. - CRC Press , 2007. - ISBN 1-58488-551-3 .
Michael Sipser Oddíl 10.6.3: Jednosměrné funkce // Úvod do teorie počítání . - PWS Publishing, 1997. - S. 374 -376. — ISBN 0-534-94728-X .
Christos Papadimitriou . Oddíl 12.1: Jednosměrné funkce // Výpočetní složitost. — 1. vydání. - Addison Wesley , 1993. - S. 279-298. — ISBN 0-201-53082-1 .
Kapitola 2.3. Jednosměrné funkce // Úvod do kryptografie / Ed. V. V. Jaščenko.
Kapitola 2.5.2 Jednosměrná funkce // Aplikace teorie deterministického chaosu v kryptografii / Ptitsyn N. - 2002. (nepřístupný odkaz)
Kapitola 7.2 Jednosměrné funkce // Kryptografie / Smart N. - 2005. - ISBN 5-94836-043-1 .
Kapitola 4.1 Jednosměrné funkce (ruština) ? . Získáno 9. října 2014. Archivováno z originálu 3. prosince 2016. (neurčitý)