Funcție unidirecțională cu intrare secretă

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 septembrie 2017; verificările necesită 37 de modificări .

O funcție unidirecțională cu o intrare secretă ( ing. funcția trapdoor , TDF ) este o funcție unidirecțională de la set la set , care are o proprietate (intrare secretă, portiță), datorită căreia devine posibil să găsiți pentru orice astfel de adică inversează funcția. $f$ $X$ $Y$ $y\in Im{f},x\in X$ $f(x) = y$

Funcțiile de introducere secretă unidirecțională sunt utilizate pe scară largă în metodele de criptare asimetrică (criptare cu cheie publică), cum ar fi: RSA , funcția Rabin , schemele ElGamal , sistemul criptografic McEliece , sistemul criptografic NTRUEncrypt , Polly Cracker și, de asemenea, mai puțin popular, datorită instabilității sale criptografice, criptosistem de rucsac Merkle-Hellman .

În prezent, nu este stabilit cu certitudine că funcțiile unidirecționale cu intrare secretă sunt într-adevăr unidirecționale, adică nu există dovezi că, fără a cunoaște intrarea secretă, un criptoanalist nu poate inversa funcția.

Definiție

Funcția , unde $f:\{0,1\}^{l(n)}\times \{0,1\}^{n}{\xrightarrow[{}]{}}\{0,1\}^ {m(n)}$

$\{0,1\}^{l(n)}$ - set de chei publice,

$\{0,1\}^{m(n))$ este un element de afișare format din n biți,

se numeste un sens cu intrare secreta, daca

Este unilateral ;
Există un algoritm eficient care, având în vedere cheia publică , mesajul și valoarea funcției, calculează astfel încât pentru o cheie ; $Y$ $M$ $M'$ $f(M)=f(M')$ $Z$
Pentru un anumit mesaj și funcție, este dificil să găsiți un mesaj astfel încât . $M$ $f(M)$ $M'\neq M$ $f(M)=f(M')$

Istorie

Dezvoltarea de funcții unidirecționale cu intrare secretă

Noțiunea de funcție unidirecțională a ușilor din spate a fost introdusă la mijlocul anilor 1970 , după publicarea unui articol de Whitfield Diffie , Martin Hellman și Ralph Merkle despre metodele de criptare asimetrică (criptare cu cheie publică). Diffie și Hellman au fost cei care au inventat termenul [1] . Dar primul sistem în care au fost folosite astfel de idei este considerat a fi un sistem inventat în 1973 de Clifford Cox , care lucra la centrul de comunicații guvernamental ( GCHQ ), dar această lucrare a fost păstrată doar în documentele interne ale centrului. , deci existența sa nu a fost cunoscută până în 1977 [2] .

Articolul descrie o nouă metodă de minimizare a necesității de a transfera chei pe canale securizate și, de asemenea, a dezasamblat un sistem criptografic care poate fi utilizat în crearea unei semnături digitale [3] .

Autorii au arătat că o funcție de introducere secretă unidirecțională poate fi utilizată în criptosistemele cu cheie publică și dispozitivele de semnătură digitală [4] . Un criptosistem cu cheie publică este un sistem în care cheia publică este transmisă pe un canal nesigur. Semnificația unei semnături digitale este că atunci când trimite un mesaj semnat de la Alice către Bob , Bob poate verifica dacă mesajul a fost într-adevăr trimis de Alice.

Datorită funcțiilor de introducere secretă unidirecțională, pot fi implementate diverse cifre de intrare secretă care sunt sigure criptografic [1] .

Au fost propuse mai multe clase de funcții, dar în curând a devenit clar că funcțiile potrivite erau mai greu de găsit decât se credea inițial. De exemplu, inițial a fost intenționat să se utilizeze funcții bazate pe problema sumei subsetului . Curând a devenit clar că această metodă era inacceptabilă. Un exemplu de astfel de implementare este criptosistemul de rucsac Merkle-Hellman .

În 2005, cei mai potriviți candidați pentru funcții de backdoor unidirecțional au fost cei din clasele RSA și Rabin [5] . Aceste funcții folosesc exponențiarea modulo un număr compus și ambele se bazează pe problema factorizării întregilor .

În 2008, au fost introduse funcții backdoor unidirecționale, permițând pierderea informațiilor despre mesajul original.

Dezvoltarea funcțiilor unidirecționale, cu pierderi, backdoor

Acest tip de funcție (funcția trapdoor cu pierderi ), bazată pe ideea de a deteriora o parte semnificativă a informațiilor [6] , a fost introdusă de Chris Peikert și Brent Waters [7] în special, ca mijloc de a construi o schemă de criptare cu cheie publică cu un text criptat ales.

Setul acestor funcții este format dintr-o familie de două funcții:

Ei repetă munca unei funcții unidirecționale cu o intrare secretă fără a pierde o parte din informații, adică dacă există o „lacună”, aceasta poate fi calculată eficient din valoarea . $X$ $f(x)$
Ei pierd o parte din informațiile despre intrare, apoi ieșirea are multe preimagini (adică este imposibil să inversați în mod unic funcția). $f(x)$

Punctul cheie este că familiile de funcții alese nu se pot distinge polinomial . Prin urmare, cheile pot fi înlocuite cu chei cu pierderi fără a anunța pe nimeni. Dar odată ce toate cheile sunt pierdute, textul cifrat nu mai conține informații (semnificative) despre mesajul criptat. În același timp, dacă pur și simplu se înlocuiește funcția de lacune cu o funcție cu pierderi, nu există nicio modalitate de a răspunde nici măcar la o solicitare de decriptare bine formată, deoarece informațiile de text simplu se vor pierde. Prin urmare, sunt folosite abstracții mai complete

Funcții unidirecționale cu intrare secretă „Toate-mai-unu”

O funcție All-but-one (ABO) poate fi construită dintr-un set de funcții unidirecționale cu intrare secretă și pierdere suficientă de informații.

Mulțimea funcțiilor ABO este asociată cu mulțimea , ale cărei elemente se numesc ramuri. Generatorul de funcții ABO preia un parametru suplimentar , numit ramură cu pierderi, și emite o funcție și o ușă din spate t. Funcția are proprietatea că pentru orice ramură funcția are o intrare ascunsă (și poate fi inversată cu ), dar funcția este o funcție cu pierderi. Mai mult, ramura cu pierderi este ascunsă (computațional) de descrierea lui . [8] . $B$ $b^{*}\în B$ $g({\cdot },{\cdot })$ $g$ $b\not =b^{*}$ $g(b,\cdot )$ $t$ $g(b^{*},\cdot )$ $g$

Funcții unidirecționale cu intrare secretă „All-but-N”

Funcțiile All-but-N (ABN) au exact ramuri cu pierderi; toate celelalte ramuri au o intrare secretă. Acesta poate fi folosit pentru a identifica textele cifrate folosind ramuri cu pierderi - toate celelalte texte cifrate se potrivesc cu funcțiile backdoor și pot fi decriptate. Rețineți că ABN-urile codifică un set de ramuri cu pierderi după cheia lor. Adică, un adversar nelimitat din punct de vedere computațional poate folosi întotdeauna forța brută pentru a găsi ramuri care conduc la o funcție cu pierderi. $N$

Prin urmare, funcțiile ABN au un dezavantaj serios: și anume, complexitatea spațială a tastelor este liniară în [9] $N.$

Funcții de introducere secretă unidirecțională, dar multe

Funcția all-but-many (ABM) are un set superpolinom de ramuri cu pierderi care necesită o ușă specială.

Cea mai importantă diferență față de funcția ABN este că, cu ABN, setul de ramuri cu pierderi este specificat inițial, la momentul construirii, în timp ce funcțiile ABM au o lacună care vă permite să încercați decriptarea din mers dintr-un mare bazin de ramuri cu pierderi. Fără acest pasaj secret și chiar și cu un set arbitrar cunoscut de ramuri cu pierderi, nu există nicio modalitate de a găsi o altă ramură care să nu aparțină setului cunoscut. Acest lucru, în special, vă permite să creați instanțe ABM cu chei și imagini compacte, a căror dimensiune nu depinde de numărul de ramuri cu pierderi.

Aceste modele pot fi văzute ca variante „deghizate” ale circuitelor de semnal Boneh-Boyen (BB). În special, ramurile cu pierderi corespund semnăturilor reale. Totuși, pentru ca semnele de pierdere și semnele de trecere secretă să pară indistinse, este necesar să se facă semnături oarbe , fie prin criptarea lor, fie prin multiplicarea lor cu un element aleatoriu al subgrupului. [9]

Construirea de funcții unidirecționale cu intrare ascunsă cu pierderi

Pentru a observa principiile de bază, să presupunem că un criptosistem general compatibil CPA are câteva proprietăți speciale (dar descrise informal).

Prima proprietate presupune că criptosistemul de bază este omomorf aditiv. Funcția (lacună unidirecțională sau funcție cu pierderi) este determinată prin criptarea elementelor cu matrice pătrată . $f$ $\{0,1\}^{n)$ $M$

Pentru a estima , furnizăm o intrare - un vector binar n-dimensional și calculăm (în etape) criptarea unui produs liniar prin aplicarea operațiilor homomorfe înregistrărilor criptate . $f(x)$ $x\in \{0,1\}^{n)$ $x*M$ $M$

Pentru o funcție de intrare secretă, matricea criptată este matricea de identitate , iar lacuna este cheia de decriptare pentru criptosistem. Funcția este reversibilă cu o intrare secretă, deoarece este criptarea de intrare care poate fi decriptată la valoarea fiecărui bit . $M$ $eu$ $f$ $f(x)$ $x*I=x$ $X$

Pentru o funcție cu pierderi, matricea criptată este o matrice formată din zerouri: . Apoi, pentru fiecare mesaj de intrare , valoarea este o criptare în funcție de element a vectorului nul, deci „pierde” informații despre . Totuși, acest lucru nu este suficient pentru a asigura o pierdere completă, deoarece mesajele criptate de ieșire poartă încă unele informații aleatorii interne care pot servi ca sursă de date despre mesajul de intrare. Prin urmare, este necesar un control suplimentar asupra comportamentului lor. Pentru aceasta, există proprietăți speciale ale criptosistemului: $M$ $M=0$ $X$ $f(x)$ $f$ $X$

aleatoritatea poate fi refolosită în combinații cu diferite taste fără a compromite puterea.
operația homomorfă izolează aleatorietatea, adică aleatorietatea textului cifrat de ieșire depinde doar de aleatoriile din mesajul de intrare (și nu de cheia publică sau de mesajele criptate). Multe criptosisteme cunoscute sunt homomorfe în ceea ce privește caracterul aleatoriu.

Cu aceste două proprietăți, criptăm matricea într-un mod special. Fiecare coloană a matricei este asociată cu o cheie diferită , iar lacuna este un set de chei de decriptare corespunzătoare. Prin fiecare linie , criptăm intrarea sub cheie și aceeași aleatorie (folosind o nouă aleatorie pentru fiecare linie). Prin convenție, este sigură reutilizarea aleatoriei cu o cheie , astfel încât matricea este ascunsă din punct de vedere computațional. De asemenea, deoarece homomorfismul izolează aleatoriu, toate textele cifrate din vectorul final sunt, de asemenea, criptate cu aceeași aleatorie (care depinde doar de . $M$ $j$ $p_{kj}$ $i$ $m_{i,j}$ $p_{kj}$ $r_{i}$ $p_{kj}$ $M$ $f(x)$ $R$ $(r_{1},r_{2}...r_{m})$

Când , încă putem inversa funcția (printr-o lacună), decriptând fiecare intrare criptată . Pe de altă parte, când matricea este zero , rezultatul funcției este întotdeauna un vector de mesaje nule criptate, unde fiecare intrare este criptată cu aceeași aleatorie (dar sub chei fixe diferite). Prin urmare, numărul de ieșiri posibile este limitat de numărul de șiruri aleatorii posibile care pot apărea. Alegând o dimensiune astfel încât numărul de intrări să fie semnificativ mai mare decât numărul de rânduri aleatorii, ne putem asigura că funcția conține o mulțime de informații. $M=I$ $f(x)$ $M=0$ $f$ $n$ $2^{n}$

Construirea de funcții cu toate acestea

Construcția funcțiilor „All-but-one” cu o intrare secretă este oarecum mai generală. Fiecare ramură a funcției corespunde pur și simplu unei matrice diferite , a cărei criptare poate fi obținută din descrierea publică a funcției. Funcția este generată astfel încât să fie o matrice inversabilă (și calculată folosind o intrare secretă) pentru toate ramurile , în timp ce pentru ramurile cu pierderi $b$ $M_{b)$ $M_{b)$ $b$ $M_{b^{*}}=0$ $b^{*}$

Exemple de funcții unidirecționale cu intrări ascunse

rsa

Luați un număr , unde și aparțin mulțimii de numere prime . Se crede că pentru un număr dat , calculul este o sarcină dificilă din punct de vedere matematic. Funcția de criptare RSA este , unde este coprime cu . Numerele și sunt o intrare secretă, știind care este ușor de calculat funcția inversă . De departe, cel mai bun atac asupra RSA este factorizarea numerelor [ 10] [11] . $n=p\cdot q$ $p$ $q$ $n$ $p$ $q$ $E(m)=m^{e}\mod n$ $e$ $(p-1)(q-1)$ $p$ $q$ $E^{-1}$ $n$

Funcția lui Rabin

Luați în considerare funcția , unde , și p și q aparțin mulțimii primelor. Rabin a arătat că este ușor de calculat o funcție dacă și numai dacă factorizarea unui număr compus din două numere prime este o sarcină simplă [12] . $F(x,n)=x^{2}mod(n)$ $n=p\cdot q$ $f^{-1}$

Schema lui ElGamal

Această schemă a fost propusă de Taher El-Gamal în 1984 . Se bazează pe problema logaritmului discret [13] .

Algoritm

Alice alege un număr prim p și un număr arbitrar a .
Alice își calculează cheia publică ( a , b ), unde , $b=a^{c}$ $1<c<p$
Bob alege și criptează un mesaj m : $1<d<p$ $(m_{1},m_{2})=(a^{d},m\cdot b^{d})$
Alice decriptează mesajul $m=m_{2}\cdot (m_{1}^{c})^{-1}.$

Criptosistem Polly Cracker

Algoritm [14]

Alice alege aleatoriu un vector într-un câmp finit .
Alice construiește polinoame care dispar în punctul dat de acest vector.
Bob generează o sumă $p=\sum {q_{i}\cdot b_{i}}$
Bob trimite $p+m$

Alte exemple

Se știe că funcțiile asociate cu problema logaritmului discret nu sunt funcții unidirecționale cu intrare secretă, deoarece nu există informații despre „lacună” care să permită calcularea eficientă a logaritmului discret. Cu toate acestea, problema logaritmului discret poate fi folosită ca bază pentru o „lacună”, cum ar fi problema computațională Diffie-Hellman (CDH) și variațiile acesteia. Algoritmul de semnătură digitală se bazează pe această problemă de calcul.

Note

Funcțiile de intrare secretă unidirecțională au o utilizare foarte specifică în criptografie și nu trebuie confundate cu o ușă din spate (deseori un concept este înlocuit cu altul, dar acest lucru este greșit). O ușă din spate este un mecanism care este adăugat în mod deliberat unui algoritm de criptare (cum ar fi un algoritm de generare de perechi de chei , un algoritm de semnătură digitală etc.) sau la sistemele de operare, permițând uneia sau mai multor terți să ocolească sau să compromită securitatea sistemului.

Vezi și

Funcție într-un singur sens

Note

↑ 1 2 Diffie, Hellman, 1976 , p. 652.
↑ Cliff Cocks. Document Cliff Cocks (link indisponibil) . Consultat la 23 noiembrie 2017. Arhivat din original la 16 februarie 2017. (nedefinit)
↑ Diffie, Hellman, 1976 , p. 644.
↑ Diffie, Hellman, 1976 , pp. 647-649.
↑ Katja Schmidt-Samoa. O nouă permutare a trapei de tip Rabin, echivalentă cu factorizarea și aplicațiile sale // Note electronice în informatica teoretică. - Elsevier, 2006. - Vol. 157 . - P. 79-94 . — ISSN 1571-0661 . - doi : 10.1016/j.entcs.2005.09.039 .
↑ Peikert, Waters, 2008 , pp. opt.
↑ Peikert, Waters, 2008 , pp. 6.
↑ Peikert, Waters, 2008 , pp. 13-14.
↑ 1 2 Chris Peikert, Brent Waters. Funcțiile Trapdoor cu pierderi și aplicațiile lor∗ // Proceeding STOC '08 Proceedings of the four0th annual ACM symposium on Theory of computing. - 2008. - Vol. 41 . - P. 79-94 . — ISSN 1571-0661 . - doi : 10.1145/1374376.1374406 .
↑ Daniel Lerch Hostalot. Atacul de factorizare la RSA (engleză) // Hakin9 : jurnal. — 2007.
↑ S. Goldwasser, M. Bellaret. Note de curs despre criptografie (engleză) : jurnal. — 2008.
↑ Katja Schmidt-Samoa. O nouă permutare de trapă de tip Rabin echivalentă cu factorizarea și aplicațiile sale : jurnal . — 2005.
↑ Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - P. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
↑ Neal Koblitz, 1998 , pp. 105-106.

Literatură

Xavier Boyen, Xiaofeng Chen. Construcția generală a funcțiilor de trapă Cameleon All-But-One // Securitate dovedibilă: a 5- a Conferință internațională . - Springer, 2011. - P. 257-261 . — ISBN 9783642243158 .
Giuseppe Longo. Secțiunea 4.2: Funcții criptografice // Comunicații digitale securizate (neopr.) . - 1983. - S. 29-30. — ISBN 0-387-81784-0 .
Chris Peikert, Brent Waters. Funcțiile trapei cu pierderi și aplicațiile lor . - 2008. - ISBN 978-1-60558-047-0 .
Julien Cathalo, Christophe Petit. Funcții unice pentru trapă unidirecțională . - Springer, 2011. - ISBN 9783642181771 .
Ronald C. Mullin, Gary L. Mullen. Câmpuri finite: teorie, aplicații și algoritmi: a patra conferință internațională privind câmpurile finite: teorie, aplicații și algoritmi . — Providence, RI: Societatea Americană de Matematică, 1998. — ISBN 0821808176 .
Neal Koblitz . Aspecte algebrice ale criptografiei. — Springer. - 1998. - ISBN 3540634460 .
Diffie W. , Hellman M. E. Noi direcții în criptografie // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638