Funcție într-un singur sens

Probleme nerezolvate în informatică : „ Există funcții unidirecționale?”

O funcție unidirecțională este o funcție matematică care este ușor de evaluat pentru orice valoare de intrare, dar dificil de găsit argumentul având în vedere valoarea funcției. Aici „ușor” și „greu” trebuie înțeles în termenii teoriei complexității computaționale . Diferența dintre complexitatea transformărilor înainte și înapoi determină eficiența criptografică a unei funcții unidirecționale. Non- injectivitatea unei funcții nu este o condiție suficientă pentru a o numi unilaterală. Funcțiile unidirecționale pot fi, de asemenea, numite greu de anulat sau ireversibile.

Existența funcțiilor unidirecționale nu a fost încă dovedită. Existența lor va dovedi că clasele de complexitate P și NP nu sunt egale , rezolvând pe parcurs o serie de probleme din informatica teoretică . Modern[ când? ] criptografia asimetrică se bazează pe presupunerea că funcțiile unidirecționale există.

Funcțiile unidirecționale sunt instrumente fundamentale în criptografie , identificare personală, autentificare și alte domenii ale securității datelor. Deși existența unor astfel de funcții este încă o ipoteză nedovedită, există mai mulți concurenți care au rezistat decenii de analiză. Multe dintre ele sunt parte integrantă a majorității sistemelor de telecomunicații , precum și a sistemelor de comerț electronic și de internet banking din întreaga lume.

Definiție

Fie mulțimea tuturor șirurilor binare de lungime n. O funcție este o funcție unidirecțională dacă este calculată eficient în timp polinomial pe o mașină Turing deterministă , dar nu există o mașină Turing probabilistică polinomială care inversează această funcție cu o probabilitate mai mare decât exponențial mică. Adică, pentru orice mașină polinomială probabilistică , pentru orice polinom și suficient de mare : $\{0,1\}^{n}$ $f:\{0,1\}^{*}\rightarrow \{0,1\}^{*}$ $M$ $p(n)$ $n\în \mathbb {N}$

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

unde rândul este ales aleatoriu pe mulțime în conformitate cu legea distribuției uniforme. Timpul de funcționare al mașinii este limitat de un polinom în lungimea preimaginei dorite [1] . $m$ $\{0,1\}^{n}$ $M$

Existenta

Existența funcțiilor unidirecționale nu a fost dovedită. Dacă f este o funcție unidirecțională, atunci găsirea funcției inverse este dificilă (prin definiție), dar ușor de verificat (prin evaluarea lui f pe ea). Astfel, din existența unei funcții unidirecționale rezultă că P ≠ NP. Totuși, nu se știe dacă P ≠ NP implică existența funcțiilor unidirecționale.

Existența funcțiilor unidirecționale va presupune existența multor alte obiecte criptografice utile, inclusiv:

generatoare de numere pseudoaleatoare ;
dacă există o funcție unidirecțională cu un bit dur , atunci există un model de biți de angajament ;
familii de funcţii pseudoaleatoare ;
inserții de imitație ;
semnătură digitală electronică .

Utilizare

Se spune că o funcție unidirecțională păstrează lungimea dacă lungimea de biți a valorii funcției este egală cu lungimea de biți a argumentului. Astfel de funcții sunt utilizate, de exemplu, în generatoarele pseudoaleatoare. Dacă lungimea de biți a valorii unei funcții unidirecționale este constantă pentru orice lungime de argument, atunci se numește funcție hash . Deci, funcția hash este folosită pentru a stoca parole sau pentru a crea o semnătură electronică [1] .

Dificultatea problemei de construire a schemelor criptografice din funcții unidirecționale poate fi ilustrată prin următorul exemplu. Să fie o funcție unidirecțională și trebuie să construim un criptosistem cu o cheie secretă . Într-un astfel de sistem criptografic, există o singură cheie - una secretă, care este cunoscută atât de expeditor, cât și de destinatarul mesajului criptat. Algoritmii de criptare și de decriptare depind ambii de această cheie secretă și sunt astfel încât pentru orice text simplu . Este clar că dacă criptograma mesajului este calculată ca , atunci adversarul, care a interceptat , poate calcula doar cu o probabilitate neglijabilă. Dar, în primul rând, nu este clar cum un destinatar legitim poate recupera un mesaj dintr-o criptogramă? În al doilea rând, din faptul că funcția este unidirecțională, rezultă doar că adversarul nu poate calcula întregul mesaj. Și acesta este un nivel foarte scăzut de stabilitate. Este de dorit ca un adversar care cunoaște criptograma să nu poată calcula un singur bit din textul simplu. $f$ $E_{K}$ $D_{K}$ $K$ $D_{K}(E_{K}(m))=m$ $m$ $d$ $m$ $d=f(m)$ $d$ $m$ $m$ $f$ $d$

Pentru a rezolva prima problemă, au fost inventate funcții unidirecționale cu o intrare secretă . Acesta este un tip special de funcție unidirecțională pentru care este ușor de calculat dat , dar dificil de calculat din cunoscut . Cu toate acestea, există câteva informații secrete suplimentare care, dacă sunt cunoscute, pot fi calculate cu ușurință . $f(m)$ $m$ $f(m)$ $m$ $y$ $f(m)$ $y$ $m$

Un alt exemplu de utilizare a funcțiilor unidirecționale în schemele criptografice este următoarea schemă de autentificare:

Abonatul generează următoarea secvență de mesaje: etc. , unde este o funcție unidirecțională. Apoi este transmis pe un canal secret (sau la o întâlnire) către abonat . Când este necesar să-și confirme identitatea, el transmite un mesaj pe un canal deschis . verificări: . Data viitoare va trimite și va verifica: etc. Interceptarea mesajelor în etapa a i-a în canalul deschis nu va oferi nimic atacatorului, deoarece acesta nu va putea obține valoarea corespunzătoare pentru a se identifica ca abonat în continuare. timp . Astfel de scheme sunt folosite pentru a identifica „prietenul/dușmanul” [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$

Dovada muncii

Pentru a proteja sistemele informatice de abuzul de servicii, părții solicitante i se cere să rezolve o problemă care necesită mult timp pentru a găsi o soluție, iar rezultatul este ușor și rapid verificat de către partea care servește. Un exemplu de astfel de protecție anti -spam este sistemul Hashcash [3] , care solicită un hash de inversare parțială de la expeditorul e-mailului.

Sistemul Bitcoin necesită ca suma hash rezultată să fie mai mică decât un parametru special. Pentru a căuta suma hash dorită, este necesar să o recalculați de mai multe ori cu enumerarea valorilor arbitrare ale parametrului suplimentar. Este nevoie de aproximativ 10 minute pentru ca toate computerele din sistem să caute o sumă hash, care reglementează rata la care sunt emise noi bitcoini. Verificarea necesită doar un singur calcul hash.

Puterea schemelor criptografice

Existența funcțiilor unidirecționale este o condiție necesară pentru puterea multor tipuri de scheme criptografice. În unele cazuri, acest fapt este stabilit destul de simplu. Luați în considerare o funcție astfel încât . Este calculat prin algoritm în timp polinomial. Să arătăm că dacă nu este o funcție unidirecțională, atunci criptosistemul este instabil. Să presupunem că există un algoritm probabilist polinom care inversează cu probabilitate pentru cel puțin un polinom . Iată lungimea cheii . Un atacator poate introduce o cheie în algoritm și poate obține o valoare din preimagine cu probabilitatea specificată . Apoi, atacatorul alimentează algoritmul ca intrare și primește o pereche de chei . Deși nu este neapărat același cu , este totuși , prin definiție , un criptosistem pentru orice text simplu . Deoarece se găsește cu o probabilitate de cel puțin , ceea ce nu este considerat neglijabil în criptografie, criptosistemul este 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)$

Din cele spuse rezultă că ipoteza existenței funcțiilor unidirecționale este cea mai slabă ipoteză criptografică, care poate fi suficientă pentru a demonstra existența unor scheme criptografice puternice de diferite tipuri. Pentru a afla dacă această condiție este într-adevăr suficientă, sunt îndreptate eforturi considerabile ale specialiștilor.

In zilele de azi[ când? ] se dovedește că existența funcțiilor unidirecționale este o condiție necesară și suficientă pentru existența unor criptosisteme puternice cu cheie secretă, precum și protocoale criptografice puternice de mai multe tipuri, inclusiv protocoale de semnătură electronică. Pe de altă parte, există rezultatul lui Impagliazzo și Rudich, care este un argument suficient de puternic că anumite tipuri de scheme criptografice (inclusiv protocoale de distribuție a cheilor de tip Diffie-Hellman) necesită ipoteze mai puternice decât ipoteza funcției unidirecționale [4] .

Candidați pentru funcții unidirecționale

Mai jos sunt descriși mai mulți concurenți pentru funcții unidirecționale. Momentan nu se știe dacă acestea sunt cu adevărat unidirecționale, dar cercetări ample nu au reușit încă să găsească un algoritm invers eficient pentru fiecare dintre ele.

Înmulțirea și factorizarea

Funcția ia ca intrare două numere prime și în reprezentare binară și returnează produsul lor . Această funcție poate fi calculată în ordinea timpului , unde este lungimea totală (numărul de numere binare) a intrării. Construirea unei funcții inverse necesită găsirea factorilor unui număr întreg dat . Determinarea factorilor este o operație de calcul care necesită foarte mult timp. Pentru a estima complexitatea unui algoritm care descompune un întreg în factori primi, funcția este adesea folosită: $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 } ))

Dacă algoritmul are complexitate , atunci are nevoie de un timp polinom pentru a rula (dimensiunea problemei la intrare, numărul de biți ai numărului, ). Cu complexitate, va necesita timp exponențial. Astfel, rata de creștere a funcției este între polinom și exponențial. Prin urmare, se spune că algoritmii cu o asemenea complexitate necesită timp sub-exponențial [5] . $O(L_{N}(0,\beta ))$ $\ln N$ $O(L_{N}(1,\beta ))$ $L_{N}(\alpha ,\beta )$ $0 < \alpha < 1$

Există mai multe metode de factorizare a unui număr cu numere prime și . Unii dintre ei: $N=p*q$ $p$ $q$

Diviziune de probă - în acest algoritm, pentru toate numerele prime care nu depășesc , condiția este verificată . Un astfel de algoritm este aproape de căutare exhaustivă și are o complexitate exponențială . $p$ ${\sqrt {N}}$ $N/p\în {\mathbb Z}$ $O(L_{N}(1,1))$
Metoda curbei eliptice funcționează bine dacă unul dintre factorii primi nu depășește . Complexitatea sa este estimată ca . $p$ $2^{50}$ $L_{p}(1/2,c)$
Sita pătratică este probabil cea mai rapidă modalitate de factorizare a numerelor între și . Complexitatea sa este . $10^{{80}}$ $10^{{100}}$ $L_{p}(1/2,1)$
Sita pătratică într-un câmp numeric . Aceasta este în prezent cea mai de succes metodă pentru numere cu 100 sau mai multe zecimale. Poate fi folosit pentru factorizarea numerelor până la , iar complexitatea sa este estimată ca [5] . $10^{{155}}$ $L_N(1/3,\;(64/9)^{\frac{1}{3)))$

Funcția poate fi generalizată la o gamă de semiprime . Rețineți că nu poate fi unilateral pentru arbitrare , deoarece produsul lor are un factor de 2 cu probabilitate ¾. $f$ $p,q>1$

Rețineți că factorizarea cu complexitate polinomială este posibilă pe un computer cuantic folosind algoritmul lui Shor ( clasa BQP ).

Pătrarea și luarea rădăcinii pătrate modulo

Funcția ia două numere întregi: și , unde este produsul a două numere prime și . Ieșirea este restul după împărțirea la . Găsirea funcției inverse necesită calcularea rădăcinii pătrate modulo , adică găsirea dacă se știe și că . Se poate arăta că ultima problemă este la fel de dificilă din punct de vedere computațional precum factorizarea. $f$ $X$ $N$ $N$ $p$ $q$ $x^{2}$ $N$ $N$ $X$ $y$ $x^{2}{\bmod N}=y$ $N$

Criptosistemul Rabin se bazează pe presupunerea că funcția Rabin este unidirecțională.

Exponențial și logaritm discret

Funcția de exponent discret ia ca argumente un număr prim și un întreg în intervalul de la până la și returnează restul după împărțirea unora la . Această funcție poate fi ușor calculată în timp , unde este numărul de biți în . Inversarea acestei funcții necesită calcularea logaritmului discret modulo . Fie un grup abelian finit, de exemplu, un grup multiplicativ al unui câmp finit sau o curbă eliptică peste un câmp finit. Sarcina calculării logaritmilor discreti este de a determina un număr întreg care, având în vedere datele, satisface relația: $f$ $p$ $X$ $0$ $p-1$ $A^{x}$ $p$ $O$ $(n^{3})$ $n$ $p$ $p$ $(G*)$ $X$ $A,B$

A^{x}=B

Pentru unele grupuri , această sarcină este destul de simplă. De exemplu, dacă este un grup de numere întregi modulo adiție. Pentru alte grupuri însă, această sarcină este mai dificilă. De exemplu, într-un grup multiplicativ cu câmp finit, cel mai cunoscut algoritm pentru rezolvarea problemei logaritmului discret este metoda sităi pătratice într-un câmp numeric . Complexitatea calculării logaritmilor discreti în acest caz este estimată ca . Schema ElGamal se bazează pe această problemă [6] . $G$ $G$ $N$ $L_{N}(1/3,c)$

Pentru grupuri precum curba eliptică, problema logaritmului discret este și mai dificilă. Cea mai bună metodă disponibilă în prezent pentru calcularea logaritmilor discreti pe o curbă eliptică generală peste un câmp se numește metoda ρ a lui Pollard . Complexitatea sa . Acesta este un algoritm exponențial, așa că criptosistemele cu curbe eliptice tind să funcționeze cu o cheie mică, în jur de 160 de biți. În timp ce sistemele bazate pe factorizarea sau calculul de logaritmi discreti în câmpuri finite folosesc chei de 1024 de biți [6] . $\mathbb {F} _{q}$ $O(L_{N}(1,1/2))$

Câteva probleme strâns legate sunt, de asemenea, legate de problema logaritmului discret. Să fie dat un grup abelian finit : $(G*)$

Problema Diffie-Hellman , care este după cum urmează: elemente date de . Este necesar să se calculeze . $A\în G,B=A^{x},C=A^{y}$ $D=A^{{xy}}$
Problema selecției Diffie-Hellman . Având în vedere: . Este necesar să se determine dacă și este un produs . $A\în G,B=A^{x},C=A^{y},D=A^{z}$ $z$ $X$ $y$

Se poate demonstra că problema de selecție Diffie-Hellman nu este mai dificilă decât problema Diffie-Hellman, iar problema Diffie-Hellman nu este mai dificilă decât problema logaritmului discret [6] .

Funcții hash criptografice

Există multe funcții hash criptografice (de exemplu SHA-256 ) care sunt rapid de calculat. Unele dintre versiunile mai simple nu au trecut prin analize complexe, dar cele mai puternice versiuni continuă să ofere soluții rapide și practice pentru calcule unidirecționale. O mare parte din suportul teoretic pentru aceste caracteristici are ca scop contracararea unora dintre atacurile de succes anterior.

Alți concurenți

Alți concurenți pentru funcții unidirecționale se bazează pe dificultatea decodării codurilor liniare aleatoare și alte probleme.

Vezi și

Note

↑ 1 2 Ptitsyn, 2002 , p. 38-39.
↑ Schema de autentificare .
↑ Hashcash - A Denial of Service Counter-Measure (2002)
↑ Russell Impagliazzo, Steven Rudich. Recuperarea informațiilor private nu implică permutări unidirecționale .
↑ 1 2 Smart, 2005 , p. 185-186.
↑ 1 2 3 Smart, 2005 , p. 187-188.

Link -uri

Oded Goldreich. Volumul 1, Instrumente de bază // Fundamentele criptografiei . - Cambridge University Press , 2001. - ISBN 0-521-79172-3 .
Jonathan Katz, Yehuda Lindell. Introducere în criptografia modernă. - CRC Press , 2007. - ISBN 1-58488-551-3 .
Michael Sipser Secțiunea 10.6.3: Funcții unidirecționale // Introducere în teoria calculului . - Editura PWS, 1997. - P. 374 -376. — ISBN 0-534-94728-X .
Christos Papadimitriou . Secțiunea 12.1: Funcții unidirecționale // Complexitate computațională. — Ediția I. - Addison Wesley , 1993. - S. 279-298. — ISBN 0-201-53082-1 .
Capitolul 2.3. Funcții unidirecționale // Introducere în criptografie / Ed. V. V. Iascenko.
Capitolul 2.5.2 Funcția unidirecțională // Aplicarea teoriei haosului determinist în criptografie / Ptitsyn N. - 2002. (link inaccesibil)
Capitolul 7.2 Funcții unidirecționale // Criptografie / Smart N. - 2005. - ISBN 5-94836-043-1 .
Capitolul 4.1 Funcții unidirecționale (rusă) ? . Consultat la 9 octombrie 2014. Arhivat din original la 3 decembrie 2016. (nedefinit)