Aufgabe:
Das Pohlig-Hellman-Verfahren
Es sei G eine Gruppe mit |G| = n ∈ N. Für k ∈ {1, . . . , n} betrachten wir die Potenz-Abbildung
πk :G→G;x→x^k.
Zeigen Sie, dass πk invertierbar ist, wenn ggT(k, n) = 1, indem Sie die Inverse angeben. Hinweis: Die Inverse ist von der Form πd , gesucht ist also d .
(b) Wir definieren das Kryptosystem:
(G,G,K,f), mit K = {...} ⊆ Z und f : G×K → G;(a,k) → a^k. Es ist also f(.,k) = πk.
i. Wie muss man K wählen, damit (G, G, K, f ) tatsächlich ein Kryptosystem ist.
ii. Zeigen Sie, dass dann (G,G,K,f) ein Kryptosystem ist, indem Sie die Dechiffrier-
Abbildung g angeben und die definierende Eigenschaft nachweisen.
(c) Diskutieren Sie die Möglichkeit das System zu brechen bei folgenden Angriffen:
Cipher-Text-Only: Gefahr droht, wenn a (bzw. a^k ) eine „kleine“ Ordnung hat. Wieso? Known-Plain-Text bzw. Chosen-Plain-Text: Kann man den Schlüssel k ermittelten?
