Název:
Kombinatorická teorie grup v kryptografii
Překlad názvu:
Combinatorial group theory and cryptography
Autoři:
Ferov, Michal ; Příhoda, Pavel (vedoucí práce) ; Růžička, Pavel (oponent) Typ dokumentu: Diplomové práce
Rok:
2012
Jazyk:
cze
Abstrakt: [cze][eng] V předkládané práci se zabýváme aplikací rozhodovacích problémů z kombinatorické teorie grup v kryptografii, konkrétně protokolem Shpilrain- Zapata. Formálně dokážeme, že grupy s malým krácením slouží jako vhodná platforma pro získávání páru soukromý-veřejný klíč, protože problém slov v nich lze řešit v lineárním čase a jsou generické. Dále se zabýváme složitostí útoku hrubou silou a ukážeme, že protokol je po teoretické stránce odolný vůči útočníkovi s libovolnou výpočetní sílou.In the presented work we focus on applications of decision problems from combinatorial group theory. Namely we analyse the Shpilrain-Zapata pro- tocol. We give formal proof that small cancellation groups are good platform for the protocol because the word problem is solvable in linear time and they are generic. We also analyse the complexity of the brute force attack on the protocol and show that in a theoretical way the protocol is immune to attack by adversary with arbitrary computing power.
Klíčová slova:
grupy s malým krácením; konečně presentované grupy; kryptografie s veřejným klíčem; rozhodovací problémy; decision problems; finitely presented groups; public-key cryptography; small cancellation groups