Envejs funktion

Uløste problemer i datalogi : '' Er der envejsfunktioner?''

En envejsfunktion er en matematisk funktion , der er let at evaluere for enhver inputværdi, men svær at finde argumentet givet funktionens værdi. Her skal "let" og "hårdt" forstås ud fra beregningsmæssig kompleksitetsteori . Gabet mellem kompleksiteten af fremadrettede og bagudgående transformationer bestemmer den kryptografiske effektivitet af en envejsfunktion. En funktions ikke-injektivitet er ikke en tilstrækkelig betingelse for at kalde den envejs. Envejsfunktioner kan også kaldes svære at vende tilbage eller irreversible.

Eksistensen af envejsfunktioner er endnu ikke blevet bevist. Deres eksistens vil bevise, at kompleksitetsklasserne P og NP ikke er ens , hvilket vil løse en række problemer inden for teoretisk datalogi undervejs . Moderne[ hvornår? ] asymmetrisk kryptografi er baseret på den antagelse, at envejsfunktioner eksisterer.

Envejsfunktioner er grundlæggende værktøjer inden for kryptografi , personlig identifikation, autentificering og andre områder af datasikkerhed. Selvom eksistensen af sådanne funktioner stadig er en ubevist hypotese, er der flere kandidater, der har modstået årtiers granskning. Mange af dem er en integreret del af de fleste telekommunikationssystemer , såvel som e-handel og internetbanksystemer rundt om i verden.

Definition

Lade være mængden af alle binære strenge med længden n. En funktion er en envejsfunktion, hvis den effektivt beregnes i polynomiel tid på en deterministisk Turing-maskine , men der er ingen polynomiel probabilistisk Turing-maskine , der inverterer denne funktion med mere end eksponentielt lille sandsynlighed. Det vil sige, for enhver probabilistisk polynomiemaskine , for ethvert polynomium og stort nok : $\{0,1\}^{n}$ $f:\{0,1\}^{*}\højrepil \{0,1\}^{*}$ $M$ $p(n)$ $n\in \mathbb {N}$

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

hvor rækken er valgt tilfældigt på sættet i henhold til den ensartede fordelingslov. Maskinens driftstid er begrænset af et polynomium i længden af det ønskede forbillede [1] . $m$ $\{0,1\}^{n}$ $M$

Eksistens

Eksistensen af envejsfunktioner er ikke blevet bevist. Hvis f er en envejsfunktion, så er det svært (per definition), at finde den inverse funktion, men let at verificere (ved at evaluere f på den). Det følger således af eksistensen af en envejsfunktion, at P ≠ NP. Det vides dog ikke, om P ≠ NP indebærer eksistensen af envejsfunktioner.

Eksistensen af envejsfunktioner vil medføre eksistensen af mange andre nyttige kryptografiske objekter, herunder:

pseudo-tilfældige tal generatorer ;
hvis der er en envejsfunktion med en hård bit , så er der et forpligtelsesbitmønster ;
familier af pseudorandom-funktioner ;
imiterede indsatser ;
elektronisk digital signatur .

Brug

En envejsfunktion siges at være længdebevarende, hvis bitlængden af funktionsværdien er lig med bitlængden af argumentet. Sådanne funktioner bruges for eksempel i pseudo-tilfældige generatorer. Hvis bitlængden af værdien af en envejsfunktion er konstant for en hvilken som helst argumentlængde, så kaldes den en hashfunktion . Så hash-funktionen bruges til at gemme adgangskoder eller oprette en elektronisk signatur [1] .

Vanskeligheden ved problemet med at konstruere kryptografiske skemaer ud fra envejsfunktioner kan illustreres ved det følgende eksempel. Lad være en envejsfunktion, og vi skal bygge et kryptosystem med en hemmelig nøgle . I et sådant kryptosystem er der kun én nøgle - en hemmelig, som både afsenderen og modtageren af den krypterede besked kender. Krypterings- og dekrypteringsalgoritmerne er begge afhængige af denne hemmelige nøgle og er sådanne for enhver almindelig tekst . Det er klart, at hvis meddelelsens kryptogram beregnes som , så kan modstanderen, der opsnappede , kun beregne med en ubetydelig sandsynlighed. Men for det første er det ikke klart, hvordan en legitim modtager kan gendanne en besked fra et kryptogram? For det andet, af det faktum, at funktionen er envejs, følger det kun, at modstanderen ikke kan beregne hele beskeden. Og det er et meget lavt modstandsniveau. Det er ønskeligt, at en modstander, der kender kryptogrammet , ikke kan beregne en enkelt bit af klarteksten. $f$ $E_{K}$ $D_{K}$ $K$ $D_{K}(E_{K}(m))=m$ $m$ $d$ $m$ $d=f(m)$ $d$ $m$ $m$ $f$ $d$

For at løse det første problem blev envejsfunktioner med en hemmelig indgang opfundet . Dette er en speciel type envejsfunktion, for hvilken det er let at beregne givet , men vanskeligt at beregne ud fra kendte . Der er dog nogle yderligere hemmelige oplysninger , som, hvis de kendes, let kan beregnes . $f(m)$ $m$ $f(m)$ $m$ $y$ $f(m)$ $y$ $m$

Et andet eksempel på brug af envejsfunktioner i kryptografiske skemaer er følgende godkendelsesskema:

Abonnenten genererer følgende sekvens af beskeder: osv. , hvor er en envejsfunktion. Derefter sendes det over en hemmelig kanal (eller ved et møde) til abonnenten . Når det er nødvendigt at bekræfte sin identitet, sender han en besked over en åben kanal . checks :. Næste gang vil den sende og kontrollere: osv. Aflytning af beskeder på i-te trin i den åbne kanal vil ikke give noget til angriberen, da han ikke vil være i stand til at få den tilsvarende værdi til at identificere sig selv som abonnenten næste gang tid . Sådanne skemaer bruges til at identificere "ven/fjende" [2] . $EN$ $m_{0},m_{1}=f(m_{0}),m_{2}=f(m_{1})$ $m_{{100}}=f(m_{{99}})$ $f(m)$ $m_{{100}}$ $B$ $EN$ $B$ $m_{{99}}$ $B$ $f(m_{{99}})=?m_{{100}}$ $EN$ $m_{{98}}$ $B$ $f(m_{{98}})=?m_{{99}}$ $m_{{i-1}}$ $EN$

Bevis for arbejde

For at beskytte computersystemer mod misbrug af tjenester, bliver rekvirenten bedt om at løse et problem, der tager lang tid at finde en løsning, og resultatet bliver nemt og hurtigt tjekket af den serverende part. Et eksempel på en sådan anti - spam beskyttelse er Hashcash [3] systemet , som anmoder om en delvis inversion hash fra afsenderen af e-mailen.

Bitcoin - systemet kræver, at den resulterende hash-sum er mindre end en speciel parameter. For at søge efter den ønskede hash-sum er det nødvendigt at genberegne det flere gange med opregning af vilkårlige værdier af den ekstra parameter. Det tager cirka 10 minutter for alle computere i systemet at søge efter én hash-sum, som regulerer hastigheden, hvormed nye bitcoins udstedes. Verifikation kræver kun en enkelt hash-beregning.

Styrken af kryptografiske skemaer

Eksistensen af envejsfunktioner er en nødvendig betingelse for styrken af mange typer kryptografiske skemaer. I nogle tilfælde fastslås dette faktum ganske enkelt. Overvej en funktion sådan, at . Det kan beregnes af algoritmen i polynomiel tid. Lad os vise, at hvis ikke en envejsfunktion, så er kryptosystemet ustabilt. Antag, at der er en polynomiel probabilistisk algoritme , der inverterer med sandsynlighed for i det mindste et eller andet polynomium . Her er nøglelængden . En angriber kan indtaste en nøgle til algoritmen og få noget værdi fra preimaget med den specificerede sandsynlighed . Derefter feeder angriberen algoritmen som input og modtager et par nøgler . Selvom det ikke nødvendigvis er det samme som , er det ikke desto mindre per definition et kryptosystem for enhver almindelig tekst . Da det findes med en sandsynlighed på mindst , hvilket ikke anses for ubetydeligt i kryptografi, er kryptosystemet ustabilt. $f$ $f(r)=K_{1}$ $G$ $f$ $EN$ $f$ $1/p(n)$ $s$ $n$ $K_1$ $EN$ $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)$

Det følger af det nævnte, at antagelsen om eksistensen af envejsfunktioner er den svageste kryptografiske antagelse, som kan være tilstrækkelig til at bevise eksistensen af stærke kryptografiske skemaer af forskellige typer. For at finde ud af, om denne tilstand faktisk er tilstrækkelig, rettes der en betydelig indsats fra specialister.

Nu om dage[ hvornår? ] er det bevist, at eksistensen af envejsfunktioner er en nødvendig og tilstrækkelig betingelse for, at der findes stærke kryptosystemer med hemmelig nøgle, samt stærke kryptografiske protokoller af flere typer, herunder elektroniske signaturprotokoller. På den anden side er der resultatet af Impagliazzo og Rudich, som er et stærkt nok argument for, at visse typer kryptografiske skemaer (inklusive nøgledistributionsprotokoller af Diffie-Hellman-typen) kræver stærkere antagelser end envejsfunktionsantagelsen [4] .

Kandidater til envejsfunktioner

Flere kandidater til envejsfunktioner er beskrevet nedenfor. I øjeblikket vides det ikke, om de virkelig er envejs, men omfattende forskning har endnu ikke været i stand til at finde en effektiv invers algoritme for hver af dem.

Multiplikation og faktorisering

Funktionen tager som input to primtal og i binær repræsentation og returnerer deres produkt . Denne funktion kan beregnes i orden tid , hvor er den samlede længde (antal binære tal) af input. Opbygning af en invers funktion kræver at finde faktorerne for et givet heltal . Bestemmelse af faktorer er en meget tidskrævende beregningsoperation. For at estimere kompleksiteten af en algoritme, der dekomponerer et heltal i primfaktorer, bruges funktionen ofte: $f$ $s$ $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 } ))

Hvis algoritmen har kompleksitet , så har den brug for en polynomiel tid til at køre (størrelsen af problemet ved input, antallet af bits af tallet, ). Med kompleksitet vil det kræve eksponentiel tid. Væksthastigheden af funktionen er således mellem polynomium og eksponentiel. Derfor siges algoritmer med en sådan kompleksitet at kræve sub-eksponentiel tid [5] . $O(L_{N}(0,\beta ))$ $\ln N$ $O(L_{N}(1,\beta ))$ $L_{N}(\alpha ,\beta )$ $0 < \alfa < 1$

Der er flere metoder til faktorisering af et tal med primtal og . Nogle af dem: $N=p*q$ $s$ $q$

Prøvedeling - i denne algoritme kontrolleres betingelsen for alle primtal, der ikke overstiger . En sådan algoritme er tæt på udtømmende søgning og har eksponentiel kompleksitet . $s$ ${\sqrt {N}}$ $N/p\in {\mathbb Z}$ $O(L_{N}(1,1))$
Den elliptiske kurvemetode fungerer godt, hvis en af primfaktorerne ikke overstiger . Dens kompleksitet anslås til . $s$ $2^{50}$ $L_{p}(1/2,c)$
Den kvadratiske sigte er nok den hurtigste måde at faktorisere tal mellem og . Dens kompleksitet er . $10^{{80}}$ $10^{{100}}$ $L_{p}(1/2,1)$
Kvadratsigte i et talfelt . Dette er i øjeblikket den mest succesrige metode for tal med 100 eller flere decimaler. Det kan bruges til at faktorisere tal op til , og dets kompleksitet estimeres til [5] . $10^{{155}}$ $L_N(1/3,\;(64/9)^{\frac{1}{3)))$

Funktionen kan generaliseres til en række semiprimtal . Bemærk, at det ikke kan være ensidigt for vilkårlig , da deres produkt har en faktor på 2 med sandsynlighed ¾. $f$ $p,q>1$

Bemærk, at faktorisering med polynomiel kompleksitet er mulig på en kvantecomputer ved hjælp af Shor 's algoritme ( BQP klasse ).

Kvadring og tage kvadratroden modulo

Funktionen tager to heltal: og , hvor er produktet af to primtal og . Udgangen er resten efter at have divideret med . At finde den omvendte funktion kræver udregning af kvadratroden modulo , det vil sige at finde om det også er kendt at . Det kan påvises, at det sidste problem er beregningsmæssigt lige så vanskeligt som faktoriseringen. $f$ $x$ $N$ $N$ $s$ $q$ $x^{2}$ $N$ $N$ $x$ $y$ $x^{2}{\bmod N}=y$ $N$

Rabin-kryptosystemet er baseret på den antagelse, at Rabin-funktionen er envejs.

Diskret eksponentiel og logaritme

Den diskrete eksponentfunktion tager som argumenter et primtal og et heltal i intervallet fra til og returnerer resten efter at have divideret nogle med . Denne funktion kan let beregnes i tid , hvor er antallet af bits i . Inversionen af denne funktion kræver beregning af den diskrete logaritme modulo . Lad være en endelig Abelsk gruppe, for eksempel en multiplikativ gruppe af et endeligt felt eller en elliptisk kurve over et endeligt felt. Opgaven med at beregne diskrete logaritmer er at bestemme et heltal , som, givet dataene, opfylder relationen: $f$ $s$ $x$ $0$ $p-1$ $A^{x}$ $s$ $O$ $(n^{3})$ $n$ $s$ $s$ $(G*)$ $x$ $A,B$

A^{x}=B

For nogle grupper er denne opgave ret enkel. For eksempel, hvis er en gruppe af heltal modulo addition. For andre grupper er denne opgave dog sværere. For eksempel i en multiplikativ gruppe med begrænset felt er den bedst kendte algoritme til at løse det diskrete logaritmeproblem den kvadratiske sigtemetode i et talfelt . Kompleksiteten af at beregne diskrete logaritmer i dette tilfælde estimeres til . ElGamal-ordningen er baseret på dette problem [6] . $G$ $G$ $N$ $L_{N}(1/3,c)$

For grupper som den elliptiske kurve er det diskrete logaritmeproblem endnu sværere. Den bedste metode, der i øjeblikket er tilgængelig til at beregne diskrete logaritmer over en generel elliptisk kurve over et felt , kaldes Pollards ρ-metode . Dens kompleksitet . Dette er en eksponentiel algoritme, så elliptiske kurvekryptosystemer har en tendens til at arbejde med en lille nøgle, omkring 160 bit. Mens systemer baseret på factoring eller beregning af diskrete logaritmer i endelige felter bruger nøgler på 1024 bit [6] . $\mathbb {F} _{q}$ $O(L_{N}(1,1/2))$

Flere nært beslægtede problemer er også relateret til det diskrete logaritmeproblem. Lad en endelig abelsk gruppe gives : $(G*)$

Diffie-Hellman-problemet , som er som følger: givne elementer af . Det er nødvendigt at beregne . $A\i G,B=A^{x},C=A^{y}$ $D=A^{{xy}}$
Diffie-Hellman-udvælgelsesproblemet . Givet :. Det er nødvendigt at afgøre, om og er et produkt . $A\i G,B=A^{x},C=A^{y},D=A^{z}$ $z$ $x$ $y$

Det kan påvises, at Diffie-Hellman-udvælgelsesproblemet ikke er sværere end Diffie-Hellman-problemet, og Diffie-Hellman-problemet er ikke sværere end det diskrete logaritmeproblem [6] .

Kryptografiske hash-funktioner

Der er mange kryptografiske hash-funktioner (f.eks . SHA-256 ), som er hurtige at beregne. Nogle af de mere simple versioner gennemgik ikke komplekse analyser, men de stærkeste versioner tilbyder fortsat hurtige, praktiske løsninger til envejsberegninger. Meget af den teoretiske støtte til disse funktioner er rettet mod at forpurre nogle af de tidligere vellykkede angreb.

Andre kandidater

Andre konkurrenter til envejsfunktioner er baseret på vanskeligheden ved at afkode tilfældige lineære koder og andre problemer.

Se også

Noter

↑ 1 2 Ptitsyn, 2002 , s. 38-39.
↑ Godkendelsesskema .
↑ Hashcash - A Denial of Service Counter-Measure (2002)
↑ Russell Impagliazzo, Steven Rudich. Privat informationshentning indebærer ikke envejs-permutationer .
↑ 1 2 Smart, 2005 , s. 185-186.
↑ 1 2 3 Smart, 2005 , s. 187-188.