Icke-kommutativ kryptografi

Icke-kommutativ kryptografi är ett område inom kryptologi där krypteringsprimitiver , metoder och system är baserade på icke- kommutativa algebraiska strukturer.

Icke -kommutativ kryptografi är baserad på operationer på en icke-kommutativ grupp 𝐺 från (𝐺, ∗), bestående av grupper , semigrupper eller ringar , i vilka det finns minst två element i gruppen 𝑎 och 𝑏 från 𝐺 för vilka ojämlikheten 𝑎∗𝑏 ≠ 𝑏∗𝑎 [ 1] . Protokoll som använder denna struktur har utvecklats för att lösa olika krypteringsproblem, till exempel uppgifterna för autentisering , kryptering - dekryptering och upprättande av en nyckelutbytessession [1] .

Relevans

En av de tidigaste användningarna av en icke-kommutativ algebraisk struktur för chifferändamål var användningen av flätgruppen , med den efterföljande utvecklingen av chifferprotokollet. Senare identifierades flera andra icke-kommutativa strukturer som Thompson-grupper , polycykliska grupper , Grigorchuk- grupper och matrisgrupper som potentiella kandidater för krypteringsapplikationer. Till skillnad från icke-kommutativ kryptografi, är för närvarande allmänt använda kryptosystem med offentlig nyckel som RSA , Diffie-Hellman-protokoll och elliptisk kryptografi baserade på talteori och beror därför på kommutativa algebraiska strukturer [1] . Användningen av en kvantdator i kryptografi, som kan inträffa inom en snar framtid, kommer dock att avsevärt påskynda lösningen av faktorisering och diskreta logaritmproblem i en cyklisk grupp (dessa problem kommer att lösas i polynomtid ) [2] . Det senare innebär att alla de mest använda kryptosystemen kommer att bli osäkra, eftersom deras säkerhet är baserad på superpolynomisk komplexitet av dessa två problem när de löses på för närvarande tillgängliga datorer.I detta fall kan säkerhet uppnås genom att konstruera kryptosystem baserade på en icke-kommutativ grupp.

Grundgrupp

Den icke-kommutativa gruppen som används i hjärtat av ett krypteringsprotokoll kallas basgruppen för det protokollet. Endast grupper som har vissa egenskaper kan användas som basgrupper för implementering i icke-kommutativa kryptosystem Låt G vara en grupp som föreslås som basgrupp för att bygga ett icke-kommutativt kryptosystem. Nedan följer en lista över egenskaper som G måste uppfylla.

Gruppen G måste vara välkänd. Med andra ord, problemet med att hitta konjugation för det har antingen studerats under lång tid och utan framgång, eller kan reduceras till ett annat välkänt problem.
Ordet jämställdhetsproblem i gruppen G måste snabbt lösas med en deterministisk algoritm. Det måste finnas en effektivt beräkningsbar "normal form" för element i G.
G måste vara en grupp av superpolynomtillväxt, det vill säga antalet element med längden n i G växer snabbare än något polynom i n. (Skyddar mot enkel uppräkning)
Det borde inte vara möjligt att returnera elementen x och y från produkten av xy i G.

Exempel på grundläggande grupper

Flätgrupp

Låt n vara ett positivt heltal. Flätgruppen B n kan definieras av ( n − 1) generatorer och relationer [3] : ${\tfrac {n\cdot (n-1)}{2))$

$B_{n}=\langle \sigma _{1},\ldots ,\sigma _{n-1}\ \mid \ \sigma _{i}\sigma _{i+1}\sigma _{ i}=\sigma _{i+1}\sigma _{i}\sigma _{i+1}\ {\text{at))\ 1\leq i\leq n-2\ {\text{i} }\ \sigma _{i}\sigma _{j}=\sigma _{j}\sigma _{i}\ {\text{för))\ |ij|\geq 2\rangle :$

I synnerhet kan vilket element av B 4 som helst skrivas som en sammansättning av följande tre element (och deras inverser):


σ 1	σ2 _	σ 3

Thompson Group

Thompson-gruppen är en oändlig grupp F som har följande oändliga representation [4] :

F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_ {n+1}{\text{ för }}k<n\right\rangle

Grigorchuks grupp

Låt T beteckna ett oändligt rotat binärt träd . Mängden V av hörn är mängden av alla finita binära sekvenser. Låt A(T) beteckna mängden av alla automorfismer av T. (Automorfismen T permuterar hörnen samtidigt som kopplingen bevaras.) Grigorchuk-gruppen Γ är en undergrupp av A(T) genererad av automorfismerna a, b, c, d definieras enligt följande:

$a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})$
$b(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n} )&{\text{ if }}b_{1}=0\\(b_{1},c(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1 }=1\end{case}}$
$c(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n} )&{\text{ if }}b_{1}=0\\(b_{1},d(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1 }=1\end{case}}$
$d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n} )&{\text{ if }}b_{1}=0\\(b_{1},b(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1 }=1\end{case}}$

Artins grupp

Artin-gruppen A(Γ) är en grupp med följande representation [5] :

{\begin{aligned}{\Big \langle }x_{1},x_{2},\ldots ,x_{n}{\Big |}\langle x_{1},x_{2}\rangle ^{m_{1,2}}&=\langle x_{2},x_{1}\rangle ^{m_{2,1}},\ldots \\&\ldots ,\langle x_{n-1} ,x_{n}\rangle ^{m_{n-1,n}}=\langle x_{n},x_{n-1}\rangle ^{m_{n,n-1}}{\Big \rangle }\end{aligned}}

var

m_{i,j}=m_{j,i}\in \{2,3,\ldots ,\infty \}.

För , betecknar den alternerande produkten av och lång , med början från . Till exempel, $m<\infty$ ${\displaystyle \langle x_{i},x_{j}\rangle ^{m))$ $x_{i}$ $x_{j}$ $m$ $x_{i}$

\langle x_{i},x_{j}\rangle ^{3}=x_{i}x_{j}x_{i}

och

\langle x_{i},x_{j}\rangle ^{4}=x_{i}x_{j}x_{i}x_{j}.

Om , då (enligt konvention) finns det inget samband mellan och . $m=\infty$ $x_{i}$ $x_{j}$

Matrisgrupper

Låt F vara ett ändligt fält. Matrisgrupper över F har använts som basgrupper för vissa icke-kommutativa kryptografiska protokoll.

Vissa icke-kommutativa kryptografiska protokoll

Dessa protokoll antar att G är en icke-abelisk grupp . Om w och a är element i gruppen G, så kommer notationen w a att beteckna elementet a −1 wa .

Nyckelutbytesprotokoll

Protokoll av Ko, Lee, et al.

Följande protokoll liknar Diffie-Hellman-protokollet. Det etablerar en delad hemlig nyckel K för Alice och Bob .

Elementet w från G är känt för alla.
Två undergrupper A och B från G så att ab = ba för alla a från A och b från B publiceras.
Alice väljer ett element a från A och skickar w a till Bob. Alice håller en hemlighet.
Bob väljer element b från B och skickar w b till Alice. Bob håller b en hemlighet.
Alice beräknar K = ( w b ) a = w ba .
Bob beräknar K' = ( w a ) b = w ab .
När ab = ba och K = K' , då delar Alice och Bob en delad hemlig nyckel K.

Anshel-Anshel-Goldfeld-protokollet

Detta är ett nyckelutbytesprotokoll som använder en icke-abelsk grupp G. Detta är viktigt eftersom det inte kräver två omkopplingsundergrupper A och B av G som i fallet med det tidigare protokollet.

Element a 1 , a 2 , . . . , a k , b 1 , b 2 , . . . , b m från G väljs och publiceras.
Alice väljer ett hemligt x från G som ett ord bestående av en 1 , en 2 , . . . a k ; _ alltså x = x ( a 1 , a 2 , ..., a k ).
Alice skickar b 1 x , b 2 x , . . . , b m x Bob.
Bob väljer ett hemligt y från G som ett ord bestående av b 1 , b 2 , . . . , b m ; följaktligen y = y ( b 1 , b 2 , ..., b m ).
Bob skickar ett 1 y , a 2 y , . . . , a k y Alice.
Alice och Bob delar en delad hemlig nyckel K = x −1 y −1 xy .
Alice beräknar x ( a 1 y , a 2 y , . . . , a k y ) = y −1 xy . Om du multiplicerar det med x − 1 får Alice K .
Bob beräknar y ( b 1 x , b 2 x , . . . , b m x ) = x −1 yx . Multiplicerar det med y −1 och tar det inversa elementet, Bob får K .

Stickel Key Exchange Protocol

Den ursprungliga formuleringen av detta protokoll använde gruppen av inverterbara matriser över ett ändligt fält.

Låt G vara en känd icke-Abelsk ändlig grupp .
Låt a , b vara ett känt par av element från G så att: ab ≠ ba . Låt ordningen av a och b motsvara N och M .
Alice väljer två slumpmässiga tal n < N och m < M och skickar u = a m b n till Bob.
Bob tar två slumpmässiga tal r < N och s < M och skickar v = a r b s till Alice.
Den gemensamma nyckeln för Alice och Bob kommer att vara K = a m + r b n + s .
Alice beräknar nyckeln med formeln: K = a m vb n .
Bob beräknar nyckeln med formeln: K = a r ub s .

Krypterings- och dekrypteringsprotokoll

Detta protokoll beskriver hur man krypterar ett hemligt meddelande och sedan dekrypterar det med en icke-kommutativ grupp. Låt Alice vilja skicka ett hemligt meddelande till Bob.

Låt G vara en icke-kommutativ grupp. Låt också A och B vara offentliga undergrupper av G för vilka ab = ba för alla a från A och b från B .
Element x från G väljs och publiceras.
Bob väljer en hemlig nyckel b från A och publicerar z = x b som sin publika nyckel.
Alice väljer ett slumpmässigt r från B och beräknar t = z r .
Det krypterade meddelandet är C =( xr , H ( t ) m ) , där H är någon hashfunktion och anger XOR- operationen . Alice skickar C till Bob. $\ plus$ $\ plus$
För att dekryptera C rekonstruerar Bob t via: ( x r ) b = x rb = x br = ( x b ) r = z r = t . Textmeddelandet som skickas av Alice beräknas som P = ( H ( t ) m ) H ( t ) = m . $\ plus$ $\ plus$

Autentiseringsprotokoll

Bob vill kontrollera om avsändaren av meddelandet är Alice.

Låt G vara en icke-kommutativ grupp. Låt också A och B vara undergrupper av G för vilka ab = ba för alla a från A och b från B .
Elementet w i G väljs och publiceras.
Alice väljer ett hemligt s från A och publicerar ett par ( w , t ) där t = w s .
Bob väljer r från B och skickar meddelandet w ' = w r till Alice.
Alice skickar svaret w ' ' = ( w ') s till Bob.
Bob kontrollerar jämställdhet w ' ' = t r . Om jämställdheten håller, så bekräftas Alices identitet.

Grunderna för protokollsäkerhet

Grunden för säkerheten och styrkan hos de olika protokollen som presenteras ovan är svårigheten att lösa följande två problem:

Konjugationsexistensproblem : Givet två elementuochvfrån en gruppG. Bestäm om det finns ett elementxfrånGså attv=u x , det vill säga så attv=x−1 ux.
Konjugationsproblem : Givet två element u och v från en grupp G. Hitta ett element x från G så att v = u x , det vill säga så att v = x −1 ux

Om algoritmen för att lösa konjugationsproblemet är okänd, kan funktionen x → u x betraktas som en envägsfunktion .

Anteckningar

↑ 1 2 3 Kumar, Saini. Nytt icke-kommutativt kryptografischema som använder extra specialgrupp . - 2017. - Januari. - S. 1-3 . Arkiverad från originalet den 26 december 2018.
↑ D.N. Moldovyan. Primitiver för kryptosystem med offentlig nyckel: Finita icke-kommutativa grupper av fyrdimensionella vektorer (ryska) . — 2010. Arkiverad 26 mars 2020.
↑ David Garber. FLÄTAGRUPP KRYPTOGRAFI PRELIMINÄRT UTKAST . - 2007. - December. Arkiverad från originalet den 26 december 2018.
↑ Vladimir Shpilrain, Alexander Ushakov. Thompsons Group och Public Key Cryptography . - 2007. - December. Arkiverad från originalet den 9 april 2019.
↑ K.I.Appel, PESchupp. Artin-grupper och oändliga Coxeter-grupper . - 1983. - Juni. Arkiverad från originalet den 26 december 2018.

Litteratur

Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Icke-kommutativ kryptografi och komplexitet hos gruppteoretiska problem. — ISBN 9780821853603 .
Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Gruppbaserad kryptografi.
Benjamin Fine, et. al. Aspekter av icke-abelsk gruppbaserad kryptografi: en undersökning och öppna problem .

Länkar

Alexey Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Gruppbaserad kryptografi (neopr.) . Berlin: Birkhauser Verlag, 2008.
Zhenfu Cao. New Directions of Modern Cryptography (neopr.) . - Boca Raton: CRC Press, Taylor & Francis Group, 2012. - ISBN 978-1-4665-0140-9 .
Benjamin Fine, et. al., Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems, arΧiv : 1103.4093 .
Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Icke-kommutativ kryptografi och komplexitet av gruppteoretiska problem (engelska) . - American Mathematical Society, 2011. - ISBN 9780821853603 .

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA