Nem kommutatív kriptográfia

A nem kommutatív kriptográfia a kriptológia olyan területe , amelyben a titkosítási primitívek , módszerek és rendszerek nem kommutatív algebrai struktúrákon alapulnak .

A nem kommutatív kriptográfia egy ( 𝐺 , ∗ -ból származó nem kommutatív csoporton) végzett műveleteken alapul, amelyek csoportokból , félcsoportokból vagy gyűrűkből állnak , és amelyekben legalább két eleme van a csoportnak 𝑎 és 𝑏 a 𝐺-ből, amelyeknél az egyenlőtlenség 𝑎∗𝑏 ≠ 𝑏∗𝑎 [1] . Különféle titkosítási problémák megoldására fejlesztették ki ezt a struktúrát használó protokollokat, például a hitelesítés , a titkosítás -dekódolás, valamint a kulcscsere munkamenet létrehozásának feladatait [1] .

Relevancia

A nem kommutatív algebrai struktúra egyik legkorábbi felhasználása rejtjelezési célokra a fonatcsoport használata volt , a rejtjelezési protokoll későbbi fejlesztésével. Később számos más, nem kommutatív struktúrát azonosítottak, mint például a Thompson-csoportokat , a policiklusos csoportokat , a Grigorchuk -csoportokat és a mátrixcsoportokat, mint potenciális jelölteket a titkosítási alkalmazásokhoz. A nem kommutatív kriptográfiától eltérően a jelenleg széles körben használt nyilvános kulcsú titkosítási rendszerek, mint például az RSA , a Diffie-Hellman protokoll és az elliptikus kriptográfia , számelméleten alapulnak, és ezért kommutatív algebrai struktúráktól függenek [1] . A közeljövőben előforduló kvantumszámítógép kriptográfiában történő alkalmazása azonban jelentősen felgyorsítja a faktorizációs és diszkrét logaritmus feladatok ciklikus csoportban történő megoldását (ezek a problémák polinomiális időben fognak megoldódni ) [2] . Ez utóbbi azt jelenti, hogy a legszélesebb körben használt kriptorendszerek mindegyike bizonytalanná válik, hiszen a biztonságuk e két probléma szuperpolinomiális összetettségén alapul, amikor a jelenleg elérhető számítógépeken megoldják őket, ebben az esetben a biztonságot úgy lehet elérni, hogy egy kriptorendszert építenek fel egy kriptográfiai alapon. nem kommutatív csoport.

Alapcsoport

A nem kommutatív csoportot, amelyet a titkosítási protokollok középpontjában használnak, a protokoll alapcsoportjának nevezik. Csak bizonyos tulajdonságokkal rendelkező csoportok használhatók alapcsoportként a nem kommutatív kriptorendszerek megvalósításához Legyen G egy nem kommutatív kriptorendszer felépítéséhez báziscsoportként javasolt csoport. Az alábbiakban felsoroljuk azokat a tulajdonságokat, amelyeknek G-nek meg kell felelnie.

A G csoportnak jól ismertnek kell lennie. Más szóval, a konjugácia megtalálásának problémáját vagy hosszú ideig és sikertelenül tanulmányozták, vagy egy másik jól ismert problémára redukálható.
A G csoportban szereplő egyenlőségi problémát gyorsan meg kell oldani egy determinisztikus algoritmussal. Kell lennie egy hatékonyan kiszámítható "normál alaknak" a G elemei számára.
G-nek szuperpolinomiális növekedési csoportnak kell lennie, vagyis a G-ben lévő n hosszúságú elemek száma gyorsabban nő, mint bármely n-beli polinom. (Véd az egyszerű felsorolás ellen)
Az x és y elemek visszaadása a G-beli xy szorzatából nem lehetséges.

Példák alapcsoportokra

Zsinórcsoport

Legyen n pozitív egész szám. A B n fonatcsoport ( n − 1) generátorokkal és relációkkal határozható meg [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 :$

A B 4 bármely eleme felírható a következő három elem (és azok inverzei) összetételeként:


σ 1	σ2 _	σ 3

Thompson Group

A Thompson-csoport egy végtelen F csoport, amelynek a következő végtelen reprezentációja [4] :

F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_ {n+1}{\text{ a következőhöz: }}k<n\right\rangle

Grigorcsuk csoportja

Jelöljön T egy végtelen gyökerű bináris fát . A csúcsok V halmaza az összes véges bináris sorozat halmaza. Jelölje A(T) a T összes automorfizmusának halmazát . (A T automorfizmus permutálja a csúcsokat, miközben megőrzi a kapcsolatot.) A Γ Grigorcsuk csoport az A(T) a, b, c, d automorfizmusok által generált alcsoportja. az alábbiak szerint határozzák meg:

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

Artin csoportja

Az Artin-csoport A(Γ) egy csoport a következő reprezentációval [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{igazított}}

ahol

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

A , a és a hosszú váltakozó szorzatát jelöli , kezdve -tól . Például, $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))

és

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

Ha , akkor (megállapodás szerint) nincs kapcsolat és között . $m=\infty$ $x_{i}$ $x_{j}$

Mátrix csoportok

Legyen F véges mező. Az F feletti mátrixcsoportokat alapcsoportokként használták néhány nem kommutatív kriptográfiai protokollhoz.

Néhány nem kommutatív kriptográfiai protokoll

Ezek a protokollok feltételezik, hogy G egy nem Abel-csoport . Ha w és a a G csoport elemei, akkor a w a jelölés az a −1 wa elemet jelöli .

Kulcscsere protokollok

Ko, Lee és társai protokollja

A következő protokoll hasonló a Diffie-Hellman protokollhoz. Megosztott titkos kulcsot K hoz létre Alice és Bob számára .

A G - ből származó w elem mindenki számára ismert.
Két A és B alcsoport G -ből , úgyhogy ab = ba minden a -ra A - ból és b -re B -ből .
Alice kiválaszt egy a elemet az A -ból , és átadja w a -t Bobnak. Alice titkot őriz .
Bob kiválasztja a b elemet B -ből , és átadja w b elemet Alice-nek. Bob titkot tart .
Alice kiszámítja a K = ( w b ) a = w ba .
Bob kiszámítja , hogy K' = ( w a ) b = w a .
Ha ab = ba és K = K' , akkor Alice és Bob egy K közös titkos kulcson osztoznak .

Anshel-Anshel-Goldfeld Protokoll

Ez egy nem Abel-féle G csoportot használó kulcscsere protokoll. Ez azért fontos, mert nem igényel két G-beli A és B kapcsolási alcsoportot, mint az előző protokoll esetében.

Elemek a 1 , a 2 , . . . , a k , b 1 , b 2 , . . . , b m -t G -ből kiválasztjuk és közzétesszük.
Alice egy titkos x -et választ G - ből szónak , amely 1 , a 2 , . . . , a k ; innen x = x ( a 1 , a 2 , . . . , a k ).
Alice küld b 1 x , b 2 x , . . . , b m x Bob.
Bob egy titkos y -t választ G -ből b 1 , b 2 , . . . , b m ; innen y = y ( b 1 , b 2 , . . . , b m ).
Bob küld egy 1 y , egy 2 y , . . . , a k y Alice.
Alice és Bob megosztott titkos kulcson K = x −1 y −1 xy .
Alice kiszámítja x ( a 1 y , a 2 y , ... , a k y ) = y −1 xy . Ha megszorozzuk x −1 -gyel , Alice K -t kap .
Bob kiszámítja az y -t ( b 1 x , b 2 x ,..., b m x ) = x −1 yx . Ha megszorozzuk y −1 -gyel, és felvesszük az inverz elemet, Bob K -t kap .

Stickel Key Exchange Protocol

Ennek a protokollnak az eredeti megfogalmazása az invertálható mátrixok csoportját használta egy véges mező felett.

Legyen G egy ismert nem-abeli véges csoport .
Legyen a , b G -ből ismert elempár , amelyre: ab ≠ ba . Legyen a és b sorrendje N - nek és M -nek .
Alice kiválaszt két véletlenszerű számot n < N és m < M , és elküldi Bobnak az u = a m b n értéket .
Bob vesz két véletlenszerű számot, r < N és s < M , és elküldi a v = a r b s -t Alice-nek.
Alice és Bob közös kulcsa K = a m + r b n + s .
Alice a kulcsot a következő képlet segítségével számítja ki: K = a m vb n .
Bob a kulcsot a következő képlettel számítja ki: K = a r ub s .

Titkosítási és visszafejtési protokollok

Ez a protokoll leírja, hogyan lehet titkosítani egy titkos üzenetet, majd visszafejteni egy nem kommutatív csoport használatával. Hadd akarjon Alice titkos üzenetet küldeni Bobnak.

Legyen G nemkommutatív csoport. Legyen A és B is G nyilvános alcsoportjai, amelyekre ab = ba minden a -ra A - ból és b -re B -ből .
A G-ből az x elemet kiválasztjuk és közzétesszük.
Bob kiválaszt egy b titkos kulcsot A -ból , és nyilvános kulcsaként közzéteszi a z = x b -t.
Alice kiválaszt egy véletlenszerű r -t B -ből , és kiszámítja a t = z r értéket .
A titkosított üzenet C = ( x r , H ( t ) m ), ahol H valamilyen hash függvény , és az XOR műveletet jelöli . Alice C -t küld Bobnak. $\oplus$ $\oplus$
A C dekódolásához Bob rekonstruálja a t -t a következő módon: ( x r ) b = x rb = x br = ( x b ) r = z r = t . Az Alice által küldött szöveges üzenet kiszámítása a következőképpen történik: P = ( H ( t ) m ) H ( t ) = m . $\oplus$ $\oplus$

Hitelesítési protokollok

Bob szeretné ellenőrizni, hogy az üzenet feladója-e Alice.

Legyen G nemkommutatív csoport. Legyen A és B is G részcsoportjai, amelyekre ab = ba minden a -ra A - ból és b -re B -ből .
A G elem w eleme kiválasztásra kerül és közzétételre kerül.
Alice kiválaszt egy titkos s -t A -ból , és közzétesz egy párt ( w , t ), ahol t = w s .
Bob kiválasztja az r -t a B közül, és elküldi a w ' = w r üzenetet Alice-nek.
Alice elküldi a w ' ' = ( w ') s választ Bobnak.
Bob ellenőrzi a w ' ' = t r egyenlőséget . Ha az egyenlőség fennáll, akkor Alice személyazonosságát megerősítik.

A protokollbiztonság alapjai

A fent bemutatott különböző protokollok biztonságának és erősségének alapja a következő két probléma megoldásának nehézsége:

Konjugácia létezési probléma : Adott kétuésvGcsoportból. Határozzuk meg, van-eGbőlx, amelyrev=u x , azazv=x−1ux.
Konjugálati probléma : Adott két u és v elem egy G csoportból . Keressünk olyan x elemet G -ből , amelyre v = u x , azaz v = x −1 ux

Ha a konjugálási probléma megoldásának algoritmusa ismeretlen, akkor az x → u x függvény egyirányú függvénynek tekinthető .

Jegyzetek

↑ 1 2 3 Kumar, Saini. Új, nem kommutatív kriptográfiai rendszer Extra speciális csoport használatával . - 2017. - január. - P. 1-3 . Az eredetiből archiválva : 2018. december 26.
↑ D.N. Moldovyan. A nyilvános kulcsú kriptorendszerek primitívumai: Négydimenziós vektorok véges, nem kommutatív csoportjai (orosz) . — 2010. Archiválva : 2020. március 26.
↑ David Garber. BRAID GROUP KRIPTOGRÁFIA ELŐZETES TERVEZET . - 2007. - december. Az eredetiből archiválva : 2018. december 26.
↑ Vlagyimir Shpilrain, Alekszandr Ushakov. Thompson's Group és nyilvános kulcsú kriptográfia . - 2007. - december. Az eredetiből archiválva : 2019. április 9.
↑ K.I.Appel, PESchupp. Artin csoportok és végtelen Coxeter csoportok . - 1983. - június. Az eredetiből archiválva : 2018. december 26.

Irodalom

Alekszej G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Nem kommutatív kriptográfia és csoportelméleti problémák összetettsége. — ISBN 9780821853603 .
Alekszej Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Csoport alapú kriptográfia.
Benjamin Fine et. al. A Nonabeli-csoport alapú kriptográfia szempontjai: felmérés és nyitott problémák .

Linkek

Alekszej Myasnikov; Vladimir Shpilrain; Alekszandr Ushakov. Csoportalapú kriptográfia (neopr.) . Berlin: Birkhauser Verlag, 2008.
Zhenfu Cao. A modern kriptográfia új irányai (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 .
Alekszej G. Myasnikov; Vladimir Shpilrain; Alekszandr Ushakov. Nem kommutatív kriptográfia és csoportelméleti problémák összetettsége (angol) . - Amerikai Matematikai Társaság, 2011. - ISBN 9780821853603 .

Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam	A3 A5 A8 Decim F-FCSR Gabona HC-256 KCipher-2 MICKEY MUGI CSUKA Phelix RC4 Nyúl FÓKA HÓ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel hálózat	GOST 28147-89 (Magma) blowfish Kamélia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra ÜZLET DES DESX DFC E2 EnRUPT FEAL HPC ÖTLET KASUMI Khafre Khufu LOKI97 MacGuffin MARS HÁLÓ MISTY1 NewDES NDS RC5 RC6 MAG Simon Sinopoli skipjack SM4 Folt TEA XTEA XXTEA Raiden RTEA Tripla DES Kéthal
SP hálózat	Szöcske 3 út ABC ÁRIA AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Öv CRYPTON Gyémánt2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer jelenlegi Szivárvány BIZTONSÁGOSBAN CÁPA NÉGYZET Kígyó háromhal
Egyéb	BÉKA NUSH REDOC SC2000 SHACAL CS-Cipher

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya

Hash függvények
Általános rendeltetésű	Adler-32 CRC Fletcher ellenőrző összeg FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH – Hash Tree jenkins hash hash összeg
Kriptográfia	Stribog GOST R 34.11-94 Öv BLAKE BMW CubeHash VISSZHANG edonkey2k FSB Fúga 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 Bőr Snefru Tigris Örvény
Kulcsgenerálási funkciók	bcrypt PBKDF2 scrypt Argon2 Lyra2
Csekkszám ( összehasonlítás )	Ellenőrző összeg Verhouff algoritmusa Hold algoritmus Damm algoritmus Vonalkód bankszámlák bankkártyák VAN SNILS OKPO ÓN OKATO ISBN OGRN és OGRNIP VIN
Hashes	A csekkszámok összehasonlítása Hitelesítési protokollok Vonalkód összehasonlítás Kriptográfia Mágneses kapcsolat Merkle aláírása ed2k URNA