Nekomutativní kryptografie

Nekomutativní kryptografie je obor kryptologie , ve kterém jsou šifrovací primitiva , metody a systémy založeny na nekomutativních algebraických strukturách.

Nekomutativní kryptografie je založena na operacích s nekomutativní grupou 𝐺 z (𝐺, ∗), skládající se ze skupin , pologrup nebo kruhů , ve kterých jsou alespoň dva prvky grupy 𝑎 a 𝑏 z 𝐺, pro které je nerovnost 𝑎∗𝑏 ≠ 𝑏∗𝑎 [1] . Protokoly využívající tuto strukturu byly vyvinuty pro řešení různých problémů s šifrováním, příkladem jsou úkoly autentizace , šifrování -dešifrování a vytvoření relace výměny klíčů [1] .

Relevance

Jedním z prvních použití nekomutativní algebraické struktury pro účely šifry bylo použití skupiny opletení s následným vývojem protokolu šifry. Později bylo jako potenciální kandidáti pro šifrovací aplikace identifikováno několik dalších nekomutativních struktur, jako jsou Thompsonovy skupiny , polycyklické skupiny , Grigorchukovy skupiny a maticové skupiny. Na rozdíl od nekomutativní kryptografie jsou v současnosti široce používané kryptosystémy s veřejným klíčem, jako je RSA , protokol Diffie-Hellman a eliptická kryptografie , založeny na teorii čísel, a proto závisí na komutativních algebraických strukturách [1] . Využití kvantového počítače v kryptografii, ke kterému může dojít v blízké budoucnosti, však výrazně urychlí řešení úloh faktorizace a diskrétního logaritmu v cyklické grupě (tyto úlohy budou řešeny v polynomiálním čase) [2] . To znamená, že všechny nejrozšířenější kryptosystémy se stanou nezabezpečenými, protože jejich bezpečnost je založena na superpolynomiální složitosti těchto dvou problémů, když jsou řešeny na aktuálně dostupných počítačích. V tomto případě lze bezpečnosti dosáhnout konstrukcí kryptosystémů založených na nekomutativní skupina.

Základní skupina

Nekomutativní skupina, která se používá v srdci šifrovacího protokolu, se nazývá základní skupina tohoto protokolu. Pouze skupiny, které mají určité vlastnosti, mohou být použity jako základní skupiny pro implementaci v nekomutativních kryptosystémech Nechť G je skupina navržená jako základní skupina pro budování nekomutativního kryptosystému. Níže je uveden seznam vlastností, které musí G splňovat.

Skupina G musí být dobře známá. Jinými slovy, problém nalezení konjugace pro něj byl buď dlouho a neúspěšně studován, nebo může být redukován na jiný dobře známý problém.
Slovní problém rovnosti ve skupině G musí být rychle vyřešen deterministickým algoritmem. Musí existovat efektivně vypočítatelná "normální forma" pro prvky G.
G musí být grupa superpolynomického růstu, to znamená, že počet prvků délky n v G roste rychleji než jakýkoli polynom v n. (Chrání před jednoduchým výčtem)
Vrácení prvků x a y ze součinu xy v G by nemělo být možné.

Příklady základních skupin

Skupina copánků

Nechť n je kladné celé číslo. Pletenou skupinu B n lze definovat pomocí ( n − 1) generátorů a vztahů [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{for))\ |ij|\geq 2\rangle :$

Zejména jakýkoli prvek B 4 lze zapsat jako složení následujících tří prvků (a jejich převrácených hodnot):


σ 1	σ2 _	σ 3

Thompson Group

Thompsonova grupa je nekonečná grupa F, která má následující nekonečné zobrazení [4] :

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

Grigorčukova skupina

Nechť T označuje nekonečný binární strom . Množina V vrcholů je množina všech konečných binárních posloupností. Nechť A(T) označuje množinu všech automorfismů T. (Automorfismus T permutuje vrcholy při zachování spojení.) Grigorchukova grupa Γ je podgrupa A(T) generovaná automorfismy a, b, c, d definován takto:

$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{cases}}$
$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{cases}}$
$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{cases}}$

Artinova skupina

Artinova grupa A(Γ) je grupa s následujícím zastoupením [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}}{\Velký \rangle }\end{aligned}}

kde

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

For , označuje střídavý součin of a long , počínaje od . Například, $m<\infty$ ${\displaystyle \langle x_{i},x_{j}\rangle ^{m))$ $x_{i}$ $x_{j}$ $m$ $x_{i}$

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

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

Jestliže , pak (podle konvence) neexistuje žádný vztah mezi a . $m=\infty$ $x_{i}$ $x_{j}$

Maticové skupiny

Nechť F je konečné těleso. Maticové skupiny nad F byly použity jako základní skupiny pro některé nekomutativní kryptografické protokoly.

Některé nekomutativní kryptografické protokoly

Tyto protokoly předpokládají, že G je neabelovská skupina . Jsou-li w a a prvky grupy G, pak zápis w a bude označovat prvek a −1 wa .

Protokoly výměny klíčů

Protokol Ko, Lee a kol

Následující protokol je podobný protokolu Diffie-Hellman. Založí sdílený tajný klíč K pro Alici a Boba .

Prvek w z G zná každý.
Jsou publikovány dvě podskupiny A a B z G tak, že ab = ba pro všechna a z A a b z B.
Alice vybere prvek a z A a předá w a Bobovi. Alice drží tajemství .
Bob vybere prvek b z B a předá w b Alici. Bob drží b tajemství.
Alice vypočítá K = ( w b ) a = w ba .
Bob vypočítá K' = ( w a ) b = w ab .
Když ab = ba a K = K' , pak Alice a Bob sdílejí sdílený tajný klíč K .

Protokol Anshel-Anshel-Goldfeld

Toto je protokol výměny klíčů využívající neabelovskou skupinu G. To je důležité, protože nevyžaduje dvě přepínací podskupiny A a B z G jako v případě předchozího protokolu.

Prvky a 1 , a 2 , . . . , ak , b 1 , b 2 , . . . , b m z G jsou vybrány a zveřejněny.
Alice vybere tajenku x z G jako slovo skládající se z a 1 , a 2 , . . . , a k ; proto x = x ( ai , a2 , ... , ak ) .
Alice posílá b 1 x , b 2 x , . . . , b m x Bob.
Bob vybere tajenku y od G jako slovo sestávající z b 1 , b 2 , . . . , b m ; proto y = y ( bi , b2 , ... , bm ) .
Bob posílá 1 y , 2 y , . . . , a k y Alice.
Alice a Bob sdílejí sdílený tajný klíč K = x −1 y −1 xy .
Alice vypočítá x ( a 1 y , a 2 y , . . . , a k y ) = y −1 xy . Vynásobením x −1 dostane Alice K .
Bob vypočítá y ( b 1 x , b 2 x , . . . , b m x ) = x −1 yx . Vynásobením y −1 a převzetím inverzního prvku dostane Bob K .

Stickel Key Exchange Protocol

Původní formulace tohoto protokolu používala skupinu invertibilních matic nad konečným polem.

Nechť G je známá neabelovská konečná grupa .
Nechť a , b je známá dvojice prvků z G taková, že: ab ≠ ba . Nechť řád aab odpovídá N a M . _
Alice vybere dvě náhodná čísla n < N a m < M a pošle u = a m b n Bobovi.
Bob vezme dvě náhodná čísla r < N a s < M a pošle v = a r b s Alici.
Společný klíč pro Alice a Boba bude K = a m + r b n + s .
Alice vypočítá klíč pomocí vzorce: K = a m vb n .
Bob vypočítá klíč pomocí vzorce: K = a r ub s .

Šifrovací a dešifrovací protokoly

Tento protokol popisuje, jak zašifrovat tajnou zprávu a poté ji dešifrovat pomocí nekomutativní skupiny. Ať Alice chce poslat Bobovi tajnou zprávu m.

Nechť G je nekomutativní grupa. Nechť také A a B jsou veřejné podgrupy G , pro které ab = ba pro všechna a z A ab z B .
Prvek x z G je vybrán a publikován.
Bob si vybere tajný klíč b z A a zveřejní z = x b jako svůj veřejný klíč.
Alice vybere náhodné r z B a vypočítá t = z r .
Zašifrovaná zpráva je C = ( x r , H ( t ) m ), kde H je nějaká hashovací funkce a označuje operaci XOR . Alice pošle C Bobovi. $\oplus$ $\oplus$
Aby Bob dešifroval C , rekonstruuje t pomocí: ( x r ) b = x rb = x br = ( x b ) r = z r = t . Textová zpráva odeslaná Alicí se vypočítá jako P = ( H ( t ) m ) H ( t ) = m . $\oplus$ $\oplus$

Autentizační protokoly

Bob chce zkontrolovat, zda odesílatel zprávy je Alice.

Nechť G je nekomutativní grupa. Nechť také A a B jsou podgrupy G , pro které ab = ba pro všechna a z A ab z B .
Prvek w z G je vybrán a publikován.
Alice vybere tajemství s od A a zveřejní pár ( w , t ), kde t = w s .
Bob vybere r z B a pošle zprávu w ' = w r Alici.
Alice odešle odpověď w ' ' = ( w ') s Bobovi.
Bob kontroluje rovnost w ' ' = t r . Pokud platí rovnost, pak je Alicina identita potvrzena.

Základy zabezpečení protokolu

Základem bezpečnosti a síly různých výše uvedených protokolů je obtížnost řešení následujících dvou problémů:

Problém existence konjugace : Jsou dány dva prvkyuavze skupinyG. Určete, zda existuje prvekxzGtakový, žev=u x , tedy takový, žev=x−1 ux.
Problém konjugace : Jsou dány dva prvky u a v ze skupiny G. Najděte prvek x z G takový, že v = u x , tedy takový, že v = x −1 ux

Jestliže algoritmus pro řešení problému konjugace není znám, pak lze funkci x → u x považovat za jednosměrnou funkci .

Poznámky

↑ 1 2 3 Kumar, Saini. Nové schéma nekomutativní kryptografie využívající zvláštní speciální skupinu . - 2017. - leden. - str. 1-3 . Archivováno z originálu 26. prosince 2018.
↑ D.N. Moldavsko. Primitiva kryptosystémů s veřejným klíčem: Konečné nekomutativní grupy čtyřrozměrných vektorů (ruština) . — 2010. Archivováno 26. března 2020.
↑ David Garber. BRAID GROUP CRYPTOGRAPHY PŘEDBĚŽNÝ NÁVRH . - 2007. - Prosinec. Archivováno z originálu 26. prosince 2018.
↑ Vladimir Shpilrain, Alexander Ushakov. Thompsonova skupina a kryptografie veřejného klíče . - 2007. - Prosinec. Archivováno z originálu 9. dubna 2019.
↑ K.I.Appel, PESchupp. Artinovy skupiny a nekonečné Coxeterovy skupiny . - 1983. - Červen. Archivováno z originálu 26. prosince 2018.

Literatura

Alexej G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Nekomutativní kryptografie a složitost grupových teoretických problémů. — ISBN 9780821853603 .
Alexej Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Skupinová kryptografie.
Benjamin Fine, et. al. Aspekty nenabelovské skupinové kryptografie: Průzkum a otevřené problémy .

Odkazy

Alexey Myasnikov; Vladimír Shpilrain; Alexandr Ušakov. Skupinová kryptografie (neopr.) . Berlín: Birkhauser Verlag, 2008.
Zhenfu Cao. Nové směry moderní kryptografie (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 .
Alexej G. Myasnikov; Vladimír Shpilrain; Alexandr Ušakov. Nekomutativní kryptografie a složitost skupinově teoretických problémů (anglicky) . - Americká matematická společnost, 2011. - ISBN 9780821853603 .

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsobem ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH 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 Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA