Nekomutativní kryptografie - Non-commutative cryptography

Nekomutativní kryptografie je oblast kryptologie Kde kryptografické primitivy, metody a systémy jsou založeny na algebraické struktury jako poloskupiny, skupiny a prsteny což jsou nekomutativní. Jednou z prvních aplikací nekomutativní algebraické struktury pro kryptografické účely bylo použití opletení skupiny vyvíjet kryptografické protokoly. Později několik dalších nekomutativních struktur jako Thompsonovy skupiny, polycyklické skupiny, Grigorchuk skupiny, a maticové skupiny byli identifikováni jako potenciální kandidáti na kryptografické aplikace. Na rozdíl od nekomutativní kryptografie je v současnosti široce používaná kryptosystémy veřejného klíče jako Kryptosystém RSA, Výměna klíčů Diffie – Hellman a kryptografie eliptické křivky jsou založeny na teorii čísel, a proto závisí na komutativních algebraických strukturách.

Pro řešení různých kryptografických problémů byly vyvinuty nekomutativní kryptografické protokoly výměna klíčů, šifrování -šifrování a ověřování. Tyto protokoly jsou velmi podobné odpovídajícím protokolům v komutativním případě.

Některé nekomutativní kryptografické protokoly

V těchto protokolech by se předpokládalo, že G je neabelský skupina. Li w a A jsou prvky G zápis w^A by označoval prvek A⁻¹wa.

Protokoly pro výměnu klíčů

Protokol kvůli Ko, Lee a kol.

Následující protokol podle Ko, Lee a kol. Stanoví společný tajný klíč K. pro Alice a Bob.

1. Prvek w z G je zveřejněn.
2. Dva podskupiny A a B z G takhle ab = ba pro všechny A v A a b v B jsou zveřejněny.
3. Alice si vybere prvek A z A a pošle w^A Bobovi. Alice drží A soukromé.
4. Bob si vybere prvek b z B a pošle w^b Alice. Bob drží b soukromé.
5. Alice počítá K. = (w^b)^A = w^ba.
6. Bob počítá K ' = (w^A)^b=w^ab.
7. Od té doby ab = ba, K. = K '. Alice a Bob sdílejí společný tajný klíč K..

Protokol Anshel-Anshel-Goldfeld

Toto je protokol výměny klíčů využívající neabelovskou skupinu G. Je významný, protože nevyžaduje dvě podskupiny dojíždějící A a B z G jako v případě protokolu kvůli Ko, Lee a kol.

1. Elementy A₁, A₂, . . . , A_k, b₁, b₂, . . . , b_m z G jsou vybrány a zveřejněny.
2. Alice si vybere soukromého X v G jako slovo v A₁, A₂, . . . , A_k; to je X = X( A₁, A₂, . . . , A_k ).
3. Alice pošle b₁^X, b₂^X, . . . , b_m^X Bobovi.
4. Bob si vybere soukromého y v G jako slovo v b₁, b₂, . . . , b_m; to je y = y ( b₁, b₂, . . . , b_m ).
5. Bob pošle A₁^y, A₂^y, . . . , A_k^y Alice.
6. Alice a Bob sdílejí společný tajný klíč K. = X⁻¹y⁻¹xy.
7. Alice počítá X ( A₁^y, A₂^y, . . . , A_k^y ) = y⁻¹ xy. Přednásobte to X⁻¹, Alice dostane K..
8. Bob počítá y ( b₁^X, b₂^X, . . . , b_m^X) = X⁻¹yx. Přednásobte to y⁻¹ a potom převrácení, Bob dostane K..

Stickelův protokol pro výměnu klíčů

V původní formulaci tohoto protokolu byla použitá skupina skupina invertibilní matice přes konečné pole.

1. Nechat G být veřejný neabelian konečná skupina.
2. Nechat A, b být veřejnými prvky G takhle ab ≠ ba. Nechte rozkazy A a b být N a M resp.
3. Alice vybere dvě náhodná čísla n < N a m < M a pošle u = A^mbⁿ Bobovi.
4. Bob vybere dvě náhodná čísla r < N a s < M a pošle proti = A^rb^s Alice.
5. Společný klíč sdílený Alice a Bobem je K. = A^{m + r}b^{n + s}.
6. Alice spočítá klíč podle K. = a^mvbⁿ.
7. Bob vypočítá klíč podle K. = A^rub^s.

Protokoly pro šifrování a dešifrování

Tento protokol popisuje, jak zašifrovat tajnou zprávu a pak dešifrovat pomocí nekomutativní skupiny. Nechte Alici chtít poslat tajnou zprávu m Bobovi.

1. Nechat G být nekomutativní skupinou. Nechat A a B být veřejnými podskupinami G takhle ab = ba pro všechny A v A a b v B.
2. Prvek X z G je vybrán a zveřejněn.
3. Bob si vybere tajný klíč b z A a publikuje z = X^b jako jeho veřejný klíč.
4. Alice vybere náhodně r z B a počítá t = z^r.
5. Šifrovaná zpráva je C = (X^r, H(t) ${ displaystyle oplus}$ m), kde H je nějaký hashovací funkce a ${ displaystyle oplus}$ označuje XOR úkon. Alice pošle C Bobovi.
6. Dešifrovat C, Bob se vzpamatuje t jak následuje: (X^r)^b = X^rb = X^br = (X^b)^r = z^r = t. Jednoduchá textová zpráva odeslaná Alicí je P = ( H(t) ${ displaystyle oplus}$ m ) ${ displaystyle oplus}$ H(t) = m.

Protokoly pro autentizaci

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

1. Nechat G být nekomutativní skupina a nechat A a B být podskupinami G takhle ab = ba pro všechny A v A a b v B.
2. Prvek w z G je vybrán a publikován.
3. Alice si vybere soukromého s z A a publikuje dvojici ( w, t ) kde t = w ^s.
4. Bob si vybere r z B a pošle výzvu w ' = w^r Alice.
5. Alice pošle odpověď w ' ' = (w ')^s Bobovi.
6. Bob zkontroluje, zda w ' ' = t^r. Pokud je to pravda, pak je stanovena identita Alice.

Bezpečnostní základy protokolů

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

• The problém rozhodování o konjugaci (nazývané také problém konjugace): Vzhledem k tomu, dva prvky u a proti ve skupině G určit, zda existuje prvek X v G takhle proti = u^X, to znamená, že takový proti = X⁻¹ ux.
• The problém hledání konjugace: Vzhledem ke dvěma prvkům u a proti ve skupině G najít prvek X v G takhle proti = u^X, to znamená, že takový proti = X⁻¹ ux.

Pokud není znám žádný algoritmus, který by vyřešil problém s hledáním konjugace, pak funkce X → u^X lze považovat za jednosměrná funkce.

Skupiny platforem

Nekomutativní skupina, která se používá v konkrétním kryptografickém protokolu, se nazývá platformová skupina daného protokolu. Jako skupiny platforem pro implementaci nekomutativních kryptografických protokolů lze použít pouze skupiny, které mají určité vlastnosti. Nechat G být skupinou navrženou jako skupina platforem pro určitý nekomutativní kryptografický systém. Následuje seznam očekávaných vlastností G.

1. Skupina G musí být dobře známé a dobře prostudované.
2. The slovní úloha v G by mělo mít rychlé řešení pomocí deterministického algoritmu. Měl by existovat efektivně vypočítatelný "normální tvar" pro prvky G.
3. Mělo by být nemožné tyto faktory obnovit X a y z produktu xy v G.
4. Počet prvků délky n v G by měl růst rychleji než jakýkoli polynom v n. (Tady "délka." n"je délka slova představujícího prvek skupiny.)

Příklady skupin platforem

Opletení skupiny

Nechat n být kladné celé číslo. Skupina copu B_n je skupina generovaná uživatelem X₁, X₂, . . . , X_n-1 s následující prezentací:

${ displaystyle B_ {n} = left langle x_ {1}, x_ {2}, ldots, x_ {n-1} { big |} x_ {i} x_ {j} = x_ {j} x_ {i} { text {if}} | ij |> 1 { text {and}} x_ {i} x_ {j} x_ {i} = x_ {j} x_ {i} x_ {j} { text {if}} | ij | = 1 pravý rangle}$

Thompsonova skupina

Thompsonova skupina je nekonečná skupina F s následující nekonečnou prezentací:

${ displaystyle F = left langle x_ {0}, x_ {1}, x_ {2}, ldots { big |} x_ {k} ^ {- 1} x_ {n} x_ {k} = x_ {n + 1} { text {for}} k$

Grigorchukova skupina

Nechat T označit nekonečno zakořeněné binární strom. Sada PROTI vrcholů je množina všech konečných binárních sekvencí. Nechat A(T) označují množinu všech automorfismů T. (Automorfismus z T permutuje vrcholy zachovávající propojenost.) Grigorchukova skupina Γ je podskupinou A(T) generované automatismy A, b, C, d definováno takto:

• ${ displaystyle a (b_ {1}, b_ {2}, ldots, b_ {n}) = (1-b_ {1}, b_ {2}, ldots, b_ {n})}$
• ${ displaystyle 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}}}$
• ${ displaystyle 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}}}$
• ${ displaystyle d (b_ {1}, b_ {2}, ldots, b_ {n}) = { begin {cases} (b_ {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 {případů}}}$

Artinová skupina

Skupina Artin A(Γ) je skupina s následující prezentací:

${ displaystyle A ( Gamma) = left langle a_ {1}, a_ {2}, ldots, a_ {n} | mu _ {ij} = mu _ {ji} { text {pro} } 1 leq i$

kde ${ displaystyle mu _ {ij} = a_ {i} a_ {j} a_ {i} ldots}$ (${ displaystyle m_ {ij}}$ faktory) a ${ displaystyle m_ {ij} = m_ {ji}}$.

Maticové skupiny

Nechat F být konečným polem. Skupiny matic přes F byly použity jako skupiny platforem určitých nekomutativních kryptografických protokolů.

Produkty Semidirect

^[1]

Viz také

• Skupinová kryptografie

Další čtení

1. Alexej Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2008). Skupinová kryptografie. Berlín: Birkhäuser Verlag.
2. Zhenfu Cao (2012). Nové směry moderní kryptografie. Boca Raton: CRC Press, Taylor & Francis Group. ISBN  978-1-4665-0140-9.
3. Benjamin Fine; et al. (2011). "Aspekty kryptografie založené na nonabelianské skupině: průzkum a otevřené problémy". arXiv:1103.4093 [cs.CR ].
4. Alexej G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2011). Nekomutativní kryptografie a složitost skupinově teoretických problémů. Americká matematická společnost. ISBN  9780821853603.

Reference