Criptografia necomutativă
Criptografia necomutativă este un domeniu al criptologiei în care primitivele , metodele și sistemele de criptare se bazează pe structuri algebrice necomutative .
Criptografia necomutativă se bazează pe operații pe un grup necomutativ 𝐺 din (𝐺, ∗), format din grupuri , semigrupe sau inele , în care există cel puțin două elemente ale grupului 𝑎 și 𝑏 din 𝐺 pentru care inegalitatea 𝑎∗𝑏 ≠ 𝑏∗𝑎 [ 1] . Au fost dezvoltate protocoale care utilizează această structură pentru a rezolva diverse probleme de criptare.Exemple sunt sarcinile de autentificare , criptare -decriptare și stabilirea unei sesiuni de schimb de chei [1] .
Relevanță
Una dintre cele mai timpurii utilizări ale unei structuri algebrice necomutative în scopuri de cifrare a fost utilizarea grupului de împletituri , cu dezvoltarea ulterioară a protocolului de cifrare. Mai târziu, câteva alte structuri necomutative, cum ar fi grupurile Thompson , grupurile policiclice , grupurile Grigorchuk și grupurile matrice, au fost identificate ca potențiali candidați pentru aplicațiile de criptare. Spre deosebire de criptografia necomutativă, criptosistemele cu cheie publică utilizate pe scară largă, cum ar fi RSA , protocolul Diffie-Hellman și criptografia eliptică, se bazează pe teoria numerelor și, prin urmare, depind de structuri algebrice comutative [1] . Cu toate acestea, utilizarea unui computer cuantic în criptografie, care poate apărea în viitorul apropiat, va accelera semnificativ rezolvarea problemelor de factorizare și logaritm discret într-un grup ciclic (aceste probleme vor fi rezolvate în timp polinomial ) [2] . Aceasta din urmă înseamnă că toate criptosistemele cele mai utilizate pe scară largă vor deveni nesigure, deoarece securitatea lor se bazează pe complexitatea superpolinomială a acestor două probleme atunci când sunt rezolvate pe calculatoarele disponibile în prezent.În acest caz, securitatea poate fi realizată prin construirea de criptosisteme bazate pe un grup necommutativ.
Grup de bază
Grupul necomutativ care este utilizat în centrul unui protocol de criptare se numește grupul de bază al protocolului respectiv. Doar grupurile care au anumite proprietăți pot fi folosite ca grupuri de bază pentru implementarea în criptosisteme necomutative.Fie G un grup propus ca grup de bază pentru construirea unui criptosistem necomutativ. Mai jos este o listă de proprietăți pe care G trebuie să le îndeplinească.
- Grupul G trebuie să fie bine cunoscut. Cu alte cuvinte, problema găsirii conjugației pentru aceasta fie a fost studiată de mult timp și fără succes, fie poate fi redusă la o altă problemă binecunoscută.
- Problema de egalitate a cuvântului din grupul G trebuie rezolvată rapidalgoritm determinist . Trebuie să existe o „formă normală” calculabilă eficient pentru elementele lui G.
- G trebuie să fie un grup de creștere superpolinomială, adică numărul de elemente de lungime n din G crește mai repede decât orice polinom din n. (Protejează împotriva enumerarii simple)
- Întoarcerea elementelor x și y din produsul lui xy în G nu ar trebui să fie posibilă.
Exemple de grupuri de bază
Grup de împletituri
Fie n un număr întreg pozitiv. Grupul de împletituri B n poate fi definit prin ( n − 1) generatoare și relații [3] :
În special, orice element al lui B4 poate fi scris ca o compoziție a următoarelor trei elemente (și inversele lor) :
| σ 1 | σ2 _ | σ 3 |
Thompson Group
Grupul Thompson este un grup infinit F având următoarea reprezentare infinită [4] :
Grupul lui Grigorchuk
Fie T să desemneze un arbore binar cu rădăcină infinită . Mulțimea V de vârfuri este mulțimea tuturor secvențelor binare finite. Fie A(T) setul tuturor automorfismelor lui T. (Automorfismul T permută vârfurile păstrând conexiunea.) Grupul Grigorchuk Γ este un subgrup al lui A(T) generat de automorfismele a, b, c, d definit după cum urmează:
Grupul lui Artin
Grupul Artin A(Γ) este un grup cu următoarea reprezentare [5] :
Unde
Pentru , denotă produsul alternativ de și lung , începând de la . De exemplu,
și
Dacă , atunci (prin convenție) nu există nicio relație între și .
Grupuri de matrice
Fie F un câmp finit. Grupurile de matrice peste F au fost folosite ca grupuri de bază pentru unele protocoale criptografice necomutative.
Unele protocoale criptografice necomutative
Aceste protocoale presupun că G este un grup non-abelian . Dacă w și a sunt elemente ale grupului G, atunci notația w a va desemna elementul a −1 wa .
Protocoale de schimb de chei
Protocol de Ko, Lee și colab.Următorul protocol este similar cu protocolul Diffie-Hellman. Stabilește o cheie secretă partajată K pentru Alice și Bob .
- Elementul w din G este cunoscut de toată lumea.
- Sunt publicate două subgrupuri A și B din G astfel încât ab = ba pentru toate a din A și b din B.
- Alice alege un element a din A și îi transmite w a lui Bob. Alice păstrează un secret.
- Bob selectează elementul b din B și îi transmite w b lui Alice. Bob păstrează secretul .
- Alice calculează K = ( w b ) a = w ba .
- Bob calculează K' = ( w a ) b = w ab .
- Când ab = ba și K = K' , atunci Alice și Bob au o cheie secretă comună K .
Acesta este un protocol de schimb de chei care utilizează un grup non-Abelian G. Acest lucru este important deoarece nu necesită două subgrupuri de comutare A și B din G ca în cazul protocolului anterior.
- Elementele a 1 , a 2 , . . . , a k , b 1 , b 2 , . . . , b m din G sunt selectate și publicate.
- Alice alege un x secret din G ca cuvânt format dintr- un 1 , un 2 , . . . , a k ; deci x = x ( a 1 , a 2 ,..., a k ).
- Alice trimite b 1 x , b 2 x , . . . , b m x Bob.
- Bob alege un secret y din G ca un cuvânt format din b 1 , b 2 , . . . , b m ; prin urmare y = y ( b 1 , b 2 , . . . , b m ).
- Bob trimite un 1 y , un 2 y . . . , a k y Alice.
- Alice și Bob împărtășesc o cheie secretă comună K = x −1 y −1 xy .
- Alice calculează x ( a 1 y , a 2 y , . . . , a k y ) = y −1 xy . Înmulțind cu x −1 , Alice obține K .
- Bob calculează y ( b 1 x , b 2 x , . . . , b m x ) = x −1 yx . Înmulțind-o cu y −1 și luând elementul invers, Bob obține K .
Formularea originală a acestui protocol a folosit grupul de matrici inversabile pe un câmp finit.
- Fie G un grup finit non-abelian cunoscut .
- Fie a , b o pereche cunoscută de elemente din G astfel încât: ab ≠ ba . Fie ordinea lui a și b să corespundă lui N și M .
- Alice alege două numere aleatoare n < N și m < M și îi trimite lui Bob u = a m b n .
- Bob ia două numere aleatoare r < N și s < M și îi trimite lui Alice v = a r b s .
- Cheia comună pentru Alice și Bob va fi K = a m + r b n + s .
- Alice calculează cheia folosind formula: K = a m vb n .
- Bob calculează cheia folosind formula: K = a r ub s .
Protocoale de criptare și decriptare
Acest protocol descrie cum să criptați un mesaj secret și apoi să îl decriptați folosind un grup necomutativ. Lasă-l pe Alice să-i trimită lui Bob un mesaj secret m.
- Fie G un grup necomutativ. De asemenea, fie A și B subgrupuri publice ale lui G pentru care ab = ba pentru toate a din A și b din B .
- Elementul x din G este selectat și publicat.
- Bob alege o cheie secretă b din A și publică z = x b ca cheie publică.
- Alice alege un r aleator din B și calculează t = z r .
- Mesajul criptat este C = ( x r , H ( t ) m ), unde H este o funcție hash și denotă operația XOR . Alice îi trimite C lui Bob.
- Pentru a decripta C , Bob reconstruiește t prin: ( x r ) b = x rb = x br = ( x b ) r = z r = t . Mesajul text trimis de Alice este calculat ca P = ( H ( t ) m ) H ( t ) = m .
Protocoale de autentificare
Bob vrea să verifice dacă expeditorul mesajului este Alice.
- Fie G un grup necomutativ. De asemenea, fie A și B subgrupuri ale lui G pentru care ab = ba pentru toate a din A și b din B .
- Elementul w din G este selectat și publicat.
- Alice alege un secret s din A și publică o pereche ( w , t ) unde t = w s .
- Bob alege r din B și îi trimite lui Alice mesajul w ' = w r .
- Alice îi trimite lui Bob răspunsul w ' ' = ( w ') s .
- Bob verifică egalitatea w ' ' = t r . Dacă egalitatea este valabilă, atunci identitatea lui Alice este confirmată.
Fundamentele securității protocolului
Baza pentru securitatea și puterea diferitelor protocoale prezentate mai sus este dificultatea de a rezolva următoarele două probleme:
- Problemă de existență a conjugației : Având în vedere două elementeușivdintr-un grupG. Determinați dacă există un elementxdinGastfel încâtv=u x , adică astfel încâtv=x−1 ux.
- Problemă de conjugare : dat fiind două elemente u și v dintr -un grup G. Găsiți un element x din G astfel încât v = u x , adică astfel încât v = x −1 ux
Dacă algoritmul pentru rezolvarea problemei de conjugare este necunoscut, atunci funcția x → u x poate fi considerată ca o funcție unidirecțională .
Note
- ↑ 1 2 3 Kumar, Saini. Nouă schemă de criptare necomutativă folosind un grup extra special . - 2017. - ianuarie. - P. 1-3 . Arhivat din original pe 26 decembrie 2018.
- ↑ D.N. Moldovyan. Primitive ale criptosistemelor cu cheie publică: grupuri finite necomutative de vectori patru-dimensionali (rusă) . — 2010. Arhivat 26 martie 2020.
- ↑ David Garber. CRIPTOGRAFIA GRUPULUI IMPLICE PRELIMINAR . - 2007. - Decembrie. Arhivat din original pe 26 decembrie 2018.
- ↑ Vladimir Şpilrain, Alexander Uşakov. Grupul lui Thompson și criptografia cu cheie publică . - 2007. - Decembrie. Arhivat din original pe 9 aprilie 2019.
- ↑ K.I.Appel, PESchupp. Grupuri Artin și grupuri infinite Coxeter . - 1983. - Iunie. Arhivat din original pe 26 decembrie 2018.
Literatură
- Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Criptografia necomutativă și complexitatea problemelor teoretice de grup. — ISBN 9780821853603 .
- Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Criptografie bazată pe grup.
- Benjamin Fine, et. al. Aspecte ale criptografiei bazate pe grup nonabelian: un sondaj și probleme deschise .
Link -uri
- Alexey Myasnikov; Vladimir Shpilrain; Alexandru Uşakov. Criptografie bazată pe grup (neopr.) . Berlin: Birkhauser Verlag, 2008.
- Zhenfu Cao. Noile direcții ale criptografiei moderne (neopr.) . - Boca Raton: CRC Press, Taylor & Francis Group, 2012. - ISBN 978-1-4665-0140-9 .
- Benjamin Fine, et. al., Aspecte ale criptografiei bazate pe grupe nonabeliene: un sondaj și probleme deschise, arΧiv : 1103.4093 .
- Alexei G. Myasnikov; Vladimir Shpilrain; Alexandru Uşakov. Criptografia necomutativă și complexitatea problemelor teoretice de grup (engleză) . - Societatea Americană de Matematică, 2011. - ISBN 9780821853603 .
| Criptosisteme simetrice | |
|---|---|
| Cifruri în flux | |
| Rețeaua Feistel | |
| Rețeaua SP | |
| Alte | |
| Funcții hash | |
|---|---|
| scop general | |
| Criptografic | |
| Funcții de generare a cheilor | |
| Numărul de verificare ( comparație ) | |
| Hashes |
|