Výměna klíčů Anshel – Anshel – Goldfeld - Anshel–Anshel–Goldfeld key exchange

Protokol Anshel – Anshel – Goldfeld, také známý jako a komutátorová výměna klíčů, je protokol pro výměnu klíčů pomocí nonabelianské skupiny. To bylo vynalezeno Dr. Michael Anshel, Iris Anshel a Dorian Goldfeld. Na rozdíl od jiných skupinových protokolů nevyužívá žádné dojíždějící ani komutativní podskupiny dané skupiny platforem a může používat jakoukoli neabelianskou skupinu s efektivně vypočítatelnými normálními formami. Často se o něm diskutuje konkrétně při aplikaci opletení skupiny, které jsou zejména nekonečné (a prvky skupiny mohou reprezentovat různá množství prostoru). Vypočítaný sdílený tajný klíč je prvkem skupiny, takže v praxi musí být toto schéma doprovázeno dostatečně zabezpečenou kompresní hashovací funkcí, aby se prvek skupiny normalizoval na použitelný bitstring.

Popis

Nechat G být pevným nonabelianem skupina volal a skupina platforem.

Alice veřejné / soukromé informace:

Alicin veřejný klíč je n-tice prvků ${ displaystyle { bf {a}} = (a_ {1}, ldots, a_ {n})}$ v G.
Alicin soukromý klíč je posloupnost prvků z ${ displaystyle { bf {a}}}$ a jejich inverze: ${ displaystyle a_ {i_ {1}} ^ { varepsilon _ {1}}, ldots, a_ {i_ {L}} ^ { varepsilon _ {L}}}$ , kde ${ displaystyle a_ {i_ {k}} in { bf {a}}}$ a ${ displaystyle varepsilon _ {k} = pm 1}$ . Na základě této sekvence vypočítá produkt ${ displaystyle A = a_ {i_ {1}} ^ { varepsilon _ {1}} ldots a_ {i_ {L}} ^ { varepsilon _ {L}}}$ .

Bobovy veřejné / soukromé informace:

Bobův veřejný klíč je n-tice prvků ${ displaystyle { bf {b}} = (b_ {1}, ldots, b_ {n})}$ v ${ displaystyle G}$ .
Bobův soukromý klíč je posloupnost prvků z ${ displaystyle { bf {b}}}$ a jejich inverze: ${ displaystyle b_ {j_ {1}} ^ { delta _ {1}}, ldots, b_ {j_ {L}} ^ { delta _ {L}}}$ , kde ${ displaystyle b_ {j_ {k}} in { bf {b}}}$ a ${ displaystyle delta _ {k} = pm 1}$ . Na základě této sekvence vypočítá produkt ${ displaystyle B = b_ {j_ {1}} ^ { delta _ {1}} ldots b_ {j_ {L}} ^ { delta _ {L}}}$ .

Přechody:

Alice pošle n-tici ${ displaystyle { overline { bf {a}}} = (A ^ {- 1} b_ {1} A, ldots, A ^ {- 1} b_ {n} A)}$ Bobovi.
Bob pošle n-tici ${ displaystyle { overline { bf {b}}} = (B ^ {- 1} a_ {1} B, ldots, B ^ {- 1} a_ {n} B)}$ Alice.

Sdílený klíč:

Klíč sdílený Alice a Bobem je prvek skupiny ${ displaystyle K = A ^ {- 1} B ^ {- 1} AB v G}$ volal komutátor z ${ displaystyle A}$ a ${ displaystyle B}$ .

Alice počítá ${ displaystyle K}$ jako produkt ${ displaystyle A ^ {- 1} cdot left (B ^ {- 1} a_ {i_ {1}} ^ { varepsilon _ {1}} B right) cdots left (B ^ {- 1 } a_ {i_ {L}} ^ { varepsilon _ {L}} B vpravo) = A ^ {- 1} B ^ {- 1} AB}$ .
Bob počítá ${ displaystyle K}$ jako produkt ${ displaystyle left (A ^ {- 1} b_ {i_ {1}} ^ { varepsilon _ {1}} A right) cdots left (A ^ {- 1} b_ {i_ {L}} ^ { varepsilon _ {L}} A ^ {} vpravo) cdot B}$ .

Bezpečnostní

Z hlediska útočníka, který se pokouší zaútočit na protokol, se obvykle učí veřejné klíče ${ displaystyle { bf {a}}}$ a ${ displaystyle { bf {b}}}$ a konjugované veřejné klíče ${ displaystyle { overline { bf {a}}}}$ a ${ displaystyle { overline { bf {b}}}}$ . Přímý útok pak spočívá ve snaze najít vhodný ${ displaystyle A}$ který je generován prvky ${ displaystyle { bf {a}}}$ , a tím vzniknou příslušné konjugace ${ displaystyle { overline { bf {a}}}}$ při aplikaci. („Nepřímý“ útok by spočíval ve snaze najít ${ displaystyle K}$ přímo, což by vyžadovalo nějakou další speciální strukturu skupiny.) Z tohoto důvodu veřejné klíče ${ displaystyle { bf {a}}}$ a ${ displaystyle { bf {b}}}$ musí být vybráno pro generování velké podskupiny ${ displaystyle G}$ - v ideálním případě tvoří úplnou sadu generátorů, takže ${ displaystyle A}$ nelze omezit pouhým vědomím, že je generováno z ${ displaystyle { bf {a}}}$ .

Řešení pro vhodné ${ displaystyle A}$ vzhledem k tomu, že konjugační vztahy se nazývají konjugační probléma byl proveden důkladný výzkum útoků na problém konjugace opletení skupiny, ačkoli nebylo dosaženo žádného plně efektivního řešení.

Viz také

Reference

I. Anshel, M. Anshel a D. Goldfeld, Algebraická metoda pro kryptografii veřejného klíče, Math. Res. Lett. 6 (1999), s. 287–291.