Envägsfunktion

Olösta problem inom datavetenskap : '' Finns det envägsfunktioner?''

En envägsfunktion är en matematisk funktion som är lätt att utvärdera för vilket ingångsvärde som helst, men svårt att hitta argumentet givet funktionens värde. Här måste "lätt" och "hårt" förstås i termer av beräkningskomplexitetsteori . Gapet mellan komplexiteten hos transformationer framåt och bakåt bestämmer den kryptografiska effektiviteten för en enkelriktad funktion. En funktions icke-injektivitet är inte ett tillräckligt villkor för att kalla den ensidig. Envägsfunktioner kan också kallas svåråterställbara eller irreversibla.

Förekomsten av envägsfunktioner har ännu inte bevisats. Deras existens kommer att bevisa att komplexitetsklasserna P och NP inte är lika , vilket löser ett antal problem inom teoretisk datavetenskap längs vägen . Modern[ när? ] asymmetrisk kryptografi bygger på antagandet att envägsfunktioner existerar.

Envägsfunktioner är grundläggande verktyg inom kryptografi , personlig identifiering, autentisering och andra områden av datasäkerhet. Även om förekomsten av sådana funktioner fortfarande är en obevisad hypotes, finns det flera utmanare som har stått emot årtionden av granskning. Många av dem är en integrerad del av de flesta telekommunikationssystem , såväl som e-handel och internetbanksystem runt om i världen.

Definition

Låt vara mängden av alla binära strängar med längden n. En funktion är en enkelriktad funktion om den effektivt beräknas i polynomtid på en deterministisk Turing-maskin , men det finns ingen polynom -probabilistisk Turing-maskin som inverterar denna funktion med mer än exponentiellt liten sannolikhet. Det vill säga för alla probabilistiska polynommaskiner , för vilket polynom som helst och tillräckligt stort : $\{0,1\}^{n}$ $f:\{0,1\}^{*}\högerpil \{0,1\}^{*}$ $M$ $p(n)$ $n\in \mathbb {N}$

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

där raden är slumpmässigt vald på uppsättningen i enlighet med lagen om enhetlig fördelning. Maskinens drifttid begränsas av ett polynom i längden på den önskade förbilden [1] . $m$ $\{0,1\}^{n}$ $M$

Existens

Förekomsten av envägsfunktioner har inte bevisats. Om f är en enkelriktad funktion är det svårt (per definition) att hitta den inversa funktionen men lätt att verifiera (genom att utvärdera f på den). Det följer alltså av förekomsten av en envägsfunktion att P ≠ NP. Det är dock inte känt om P ≠ NP antyder förekomsten av envägsfunktioner.

Förekomsten av envägsfunktioner kommer att medföra förekomsten av många andra användbara kryptografiska objekt, inklusive:

pseudo-slumptalsgeneratorer ;
om det finns en envägsfunktion med en hård bit så finns det ett engagemangbitmönster ;
familjer av pseudoslumpmässiga funktioner ;
imitationsinsatser ;
elektronisk digital signatur .

Användning

En envägsfunktion sägs vara längdbevarande om funktionsvärdets bitlängd är lika med argumentets bitlängd. Sådana funktioner används till exempel i pseudo-slumpgeneratorer. Om bitlängden för värdet av en envägsfunktion är konstant för någon argumentlängd, kallas det en hashfunktion . Så hash-funktionen används för att lagra lösenord eller skapa en elektronisk signatur [1] .

Svårigheten med problemet med att konstruera kryptografiska scheman från envägsfunktioner kan illustreras av följande exempel. Låt vara en enkelriktad funktion och vi måste bygga ett kryptosystem med en hemlig nyckel . I ett sådant kryptosystem finns det bara en nyckel - en hemlig, som är känd för både avsändaren och mottagaren av det krypterade meddelandet. Krypterings- och dekrypteringsalgoritmerna är båda beroende av denna hemliga nyckel och är sådana att för alla klartext . Det är tydligt att om meddelandets kryptogram beräknas som , då kan motståndaren, som avlyssnade , beräkna endast med en försumbar sannolikhet. Men för det första är det inte klart hur en legitim mottagare kan återställa ett meddelande från ett kryptogram? För det andra, av det faktum att funktionen är enkelriktad, följer det bara att motståndaren inte kan beräkna hela meddelandet. Och detta är en mycket låg nivå av stabilitet. Det är önskvärt att en motståndare som känner till kryptogrammet inte kan beräkna en enda bit av klartexten. $f$ $E_{K}$ $D_{K}$ $K$ $D_{K}(E_{K}(m))=m$ $m$ $d$ $m$ $d=f(m)$ $d$ $m$ $m$ $f$ $d$

För att lösa det första problemet uppfanns envägsfunktioner med en hemlig ingång . Detta är en speciell typ av envägsfunktion för vilken det är lätt att beräkna givet , men svårt att beräkna från kända . Det finns dock ytterligare hemlig information som, om den är känd, lätt kan beräknas . $f(m)$ $m$ $f(m)$ $m$ $y$ $f(m)$ $y$ $m$

Ett annat exempel på att använda envägsfunktioner i kryptografiska scheman är följande autentiseringsschema:

Abonnenten genererar följande sekvens av meddelanden: etc. , där är en enkelriktad funktion. Sedan sänds det över en hemlig kanal (eller vid ett möte) till abonnenten . När det är nödvändigt att bekräfta sin identitet sänder han ett meddelande över en öppen kanal . checkar: . Nästa gång kommer det att skicka och kontrollera: etc. Avlyssning av meddelanden i det i-te steget i den öppna kanalen kommer inte att ge något till angriparen, eftersom han inte kommer att kunna få motsvarande värde för att identifiera sig som abonnent nästa tid . Sådana system används för att identifiera "vän/fiende" [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$

Bevis på arbete

För att skydda datorsystem från missbruk av tjänster ombeds den begärande parten att lösa ett problem som tar mycket tid att hitta en lösning och resultatet kontrolleras enkelt och snabbt av den serverande parten. Ett exempel på ett sådant anti -spam- skydd är Hashcash [3] -systemet , som begär en partiell inversionshash från avsändaren av e-postmeddelandet.

Bitcoin - systemet kräver att den resulterande hashsumman är mindre än en speciell parameter. För att söka efter den önskade hashsumman måste du räkna om den flera gånger med uppräkning av godtyckliga värden för den extra parametern. Det tar cirka 10 minuter för alla datorer i systemet att söka efter en hashsumma, som reglerar takten med vilken nya bitcoins ges ut. Verifiering kräver endast en enda hashberäkning.

Styrkan hos kryptografiska scheman

Förekomsten av envägsfunktioner är ett nödvändigt villkor för styrkan hos många typer av kryptografiska system. I vissa fall fastställs detta faktum helt enkelt. Betrakta en funktion sådan att . Den kan beräknas av algoritmen i polynomtid. Låt oss visa att om inte en enkelriktad funktion så är kryptosystemet instabilt. Anta att det finns en polynomisk probabilistisk algoritm som inverterar med sannolikhet för åtminstone något polynom . Här är nyckellängden . En angripare kan mata in en nyckel till algoritmen och få ett visst värde från förbilden med den angivna sannolikheten . Därefter matar angriparen algoritmen som indata och får ett par nycklar . Även om det inte nödvändigtvis är samma som , är det ändå per definition ett kryptosystem för vilken klartext som helst . Eftersom det hittas med en sannolikhet på minst , vilket inte anses vara försumbart i kryptografi, är kryptosystemet instabilt. $f$ $f(r)=K_{1}$ $G$ $f$ $A$ $f$ $1/p(n)$ $sid$ $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)$

Av det sagda följer att antagandet om förekomsten av envägsfunktioner är det svagaste kryptografiska antagandet, vilket kan vara tillräckligt för att bevisa förekomsten av starka kryptografiska system av olika slag. För att ta reda på om detta tillstånd faktiskt är tillräckligt, riktas betydande ansträngningar från specialister.

Nu för tiden[ när? ] är det bevisat att förekomsten av envägsfunktioner är en nödvändig och tillräcklig förutsättning för att det ska finnas starka kryptosystem med hemlig nyckel, samt starka kryptografiska protokoll av flera slag, inklusive elektroniska signaturprotokoll. Å andra sidan finns resultatet av Impagliazzo och Rudich, som är ett tillräckligt starkt argument för att vissa typer av kryptografiska system (inklusive nyckeldistributionsprotokoll av Diffie-Hellman-typ) kräver starkare antaganden än antagandet om envägsfunktion [4] .

Kandidater för envägsfunktioner

Flera utmanare för envägsfunktioner beskrivs nedan. För närvarande är det inte känt om de verkligen är enkelriktade, men omfattande forskning har ännu inte lyckats hitta en effektiv invers algoritm för var och en av dem.

Multiplikation och faktorisering

Funktionen tar som indata två primtal och i binär representation och returnerar deras produkt . Denna funktion kan beräknas i ordning time , där är den totala längden (antal binära tal) för ingången. Att bygga en invers funktion kräver att man hittar faktorerna för ett givet heltal . Bestämning av faktorer är en mycket tidskrävande beräkningsoperation. För att uppskatta komplexiteten hos en algoritm som bryter ner ett heltal i primtalsfaktorer, används ofta funktionen: $f$ $sid$ $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 } ))

Om algoritmen har komplexitet behöver den en polynomtid för att köras (storleken på problemet vid ingången, antalet bitar av talet, ). Med komplexitet kommer det att kräva exponentiell tid. Funktionens tillväxthastighet är alltså mellan polynom och exponentiell. Därför sägs algoritmer med sådan komplexitet kräva subexponentiell tid [5] . $O(L_{N}(0,\beta ))$ $\ln N$ $O(L_{N}(1,\beta ))$ $L_{N}(\alpha ,\beta )$ $0 < \alfa < 1$

Det finns flera metoder för att faktorisera ett tal med primtal och . Några av dem: $N=p*q$ $sid$ $q$

Provdelning - i denna algoritm kontrolleras villkoret för alla primtal som inte överstiger . En sådan algoritm är nära en uttömmande sökning och har exponentiell komplexitet . $sid$ ${\sqrt {N}}$ $N/p\in {\mathbb Z}$ $O(L_{N}(1,1))$
Den elliptiska kurvan fungerar bra om en av primfaktorerna inte överstiger . Dess komplexitet uppskattas till . $sid$ $2^{50}$ $L_{p}(1/2,c)$
Den kvadratiska sikten är förmodligen det snabbaste sättet att faktorisera tal mellan och . Dess komplexitet är . $10^{{80}}$ $10^{{100}}$ $L_{p}(1/2,1)$
Kvadratisk sil i ett nummerfält . Detta är för närvarande den mest framgångsrika metoden för tal med 100 eller fler decimaler. Den kan användas för att faktorisera tal upp till , och dess komplexitet uppskattas till [5] . $10^{{155}}$ $L_N(1/3,\;(64/9)^{\frac{1}{3)))$

Funktionen kan generaliseras till en rad semiprimtal . Observera att det inte kan vara ensidigt för godtycklig , eftersom deras produkt har en faktor på 2 med sannolikheten ¾. $f$ $p,q>1$

Observera att faktorisering med polynomkomplexitet är möjlig på en kvantdator med Shors algoritm ( BQP-klass ).

Kvadratering och ta kvadratroten modulo

Funktionen tar två heltal: och , där är produkten av två primtal och . Utdata är resten efter division med . Att hitta den inversa funktionen kräver att man beräknar kvadratroten modulo , det vill säga att hitta om det också är känt att . Det kan visas att det senare problemet är beräkningsmässigt lika svårt som faktoriseringen. $f$ $x$ $N$ $N$ $sid$ $q$ $x^{2}$ $N$ $N$ $x$ $y$ $x^{2}{\bmod N}=y$ $N$

Rabins kryptosystem bygger på antagandet att Rabinfunktionen är enkelriktad.

Diskret exponentiell och logaritm

Den diskreta exponentfunktionen tar som argument ett primtal och ett heltal i intervallet från till och returnerar resten efter att ha dividerat en del med . Denna funktion kan lätt beräknas i tid , där är antalet bitar i . Inversionen av denna funktion kräver beräkning av den diskreta logaritmen modulo . Låta vara en ändlig Abelisk grupp, till exempel en multiplikativ grupp av ett ändligt fält eller en elliptisk kurva över ett ändligt fält. Uppgiften att beräkna diskreta logaritmer är att bestämma ett heltal som, givet data, uppfyller förhållandet: $f$ $sid$ $x$ $0$ $p-1$ $A^{x}$ $sid$ $O$ $(n^{3})$ $n$ $sid$ $sid$ $(G*)$ $x$ $A,B$

A^{x}=B

För vissa grupper är denna uppgift ganska enkel. Till exempel, if är en grupp av heltal modulo addition. För andra grupper är dock denna uppgift svårare. Till exempel, i en multiplikativ grupp med finita fält, är den mest kända algoritmen för att lösa det diskreta logaritmproblemet den kvadratiska siktmetoden i ett talfält . Komplexiteten för att beräkna diskreta logaritmer i detta fall uppskattas till . ElGamal-schemat är baserat på detta problem [6] . $G$ $G$ $N$ $L_{N}(1/3,c)$

För grupper som den elliptiska kurvan är det diskreta logaritmproblemet ännu svårare. Den bästa metoden som för närvarande är tillgänglig för att beräkna diskreta logaritmer över en allmän elliptisk kurva över ett fält kallas Pollards ρ-metod . Dess komplexitet . Detta är en exponentiell algoritm, så kryptosystem med elliptiska kurvor tenderar att arbeta med en liten nyckel, runt 160 bitar. Medan system baserade på factoring eller beräkning av diskreta logaritmer i finita fält använder nycklar på 1024 bitar [6] . $\mathbb {F} _{q}$ $O(L_{N}(1,1/2))$

Flera närbesläktade problem är också relaterade till det diskreta logaritmproblemet. Låt en ändlig Abelisk grupp ges : $(G*)$

Diffie-Hellman-problemet , som är följande: givna element av . Det krävs för att beräkna . $A\i G,B=A^{x},C=A^{y}$ $D=A^{{xy}}$
Diffie-Hellmans urvalsproblem . Givet: . Det krävs för att avgöra om och är en produkt . $A\i G,B=A^{x},C=A^{y},D=A^{z}$ $z$ $x$ $y$

Det kan visas att Diffie-Hellman-selektionsproblemet inte är svårare än Diffie-Hellman-problemet, och Diffie-Hellman-problemet är inte svårare än det diskreta logaritmproblemet [6] .

Kryptografiska hashfunktioner

Det finns många kryptografiska hashfunktioner (t.ex. SHA-256 ) som är snabba att beräkna. Vissa av de enklare versionerna gick inte igenom komplexa analyser, men de starkaste versionerna fortsätter att erbjuda snabba och praktiska lösningar för enkelriktade beräkningar. Mycket av det teoretiska stödet för dessa funktioner syftar till att motverka några av de tidigare framgångsrika attackerna.

Andra utmanare

Andra utmanare för envägsfunktioner är baserade på svårigheten att avkoda slumpmässiga linjära koder och andra problem.

Se även

Anteckningar

↑ 1 2 Ptitsyn, 2002 , sid. 38-39.
↑ Autentiseringsschema .
↑ Hashcash - A Denial of Service Counter-Measure (2002)
↑ Russell Impagliazzo, Steven Rudich. Privat informationshämtning innebär inte enkelriktade permutationer .
↑ 1 2 Smart, 2005 , sid. 185-186.
↑ 1 2 3 Smart, 2005 , sid. 187-188.

Länkar

Oded Goldreich. Volym 1, Grundläggande verktyg // Kryptografins grunder . - Cambridge University Press , 2001. - ISBN 0-521-79172-3 .
Jonathan Katz, Yehuda Lindell. Introduktion till modern kryptografi. - CRC Press , 2007. - ISBN 1-58488-551-3 .
Michael Sipser Avsnitt 10.6.3: Envägsfunktioner // Introduktion till teorin om beräkning . - PWS Publishing, 1997. - P. 374 -376. — ISBN 0-534-94728-X .
Christos Papadimitriou . Avsnitt 12.1: Envägsfunktioner // Computational Complexity. — 1:a upplagan. - Addison Wesley , 1993. - S. 279-298. — ISBN 0-201-53082-1 .
Kapitel 2.3. Envägsfunktioner // Introduktion till kryptografi / Ed. V. V. Jasjtjenko.
Kapitel 2.5.2 Envägsfunktion // Tillämpning av teorin om deterministiskt kaos i kryptografi / Ptitsyn N. - 2002. (otillgänglig länk)
Kapitel 7.2 Envägsfunktioner // Kryptografi / Smart N. - 2005. - ISBN 5-94836-043-1 .
Kapitel 4.1 Envägsfunktioner (ryska) ? . Hämtad 9 oktober 2014. Arkiverad från originalet 3 december 2016. (obestämd)