ETH Zürich, D-INFK HS 2015, 16. November 2015 Prof. Ueli Maurer Daniel Tschudi Diskrete Mathematik Übung 10 10.1 Untergruppen der Diedergruppe D4 (? ? ?) In dieser Aufgabe betrachten wir die Diedergruppe D4 , welche durch Äquivalenzklassen von Wörtern als D4 = hr, s | rrrr = e, ss = e, rsrs = ei definiert werden kann, wobei e das leere Wort bezeichnet. Es gilt zum Beispiel, dass srs äquivalent zu rrr ist, da srs = rrrr srs = rrr rsrs = rrr. Wie in der Vorlesung gezeigt, hat die Gruppe D4 Ordnung 8. Da die Symmetriegruppe des Quadrats isomorph zu D4 ist, kann r auch als Drehung um 90◦ und s als eine Spiegelung aufgefasst werden (vgl. Beispiel 7.14). a) Bestimmen Sie alle Untergruppen von D4 und zeichnen Sie das Hasse-Diagramm der Untergruppenrelation. b) Bestimmen Sie die Isomorphieklassen der Untergruppen von D4 . 10.2 Elementare Eigenschaften von Ringen (? ?) (7 Punkte) Ziel dieser Aufgabe ist es, Lemma 7.17 (ii) – (iv) zu beweisen. Dazu dürfen Sie Lemma 7.17 (i) ohne Beweis verwenden. Sei hR; +, −, 0, ·, 1i ein Ring und a, b ∈ R. Zeigen Sie: a) (−a)b = −(ab) (2 Punkte) b) (−a)(−b) = ab (3 Punkte) c) Wenn R mindestens zwei Elemente enthält, gilt 1 6= 0. (2 Punkte) 10.3 Eigenschaften kommutativer Ringe (? ?) Ziel dieser Aufgabe ist es, Lemma 7.18 (ii) und (iii) zu beweisen. Sei hR; +, −, 0, ·, 1i ein kommutativer Ring und a, b, c ∈ R. Zeigen Sie: a) Falls a|b gilt a|bc für alle c. b) Falls a|b und a|c gilt a|(b + c). 10.4 Diffie-Hellman Revisited a) (? ?) Weil Alice schneller addieren als multiplizieren kann, schlägt sie vor, den DiffieHellman-Schlüsselaustausch in der Gruppe hZn ; ⊕i durchzuführen. Beschreiben Sie, welche Nachrichten in diesem Fall Alice und Bob austauschen. Zeigen Sie, warum dies unsicher ist, das heisst, zeigen Sie, wie Eve, die diese Nachrichten mitliest, den gemeinsamen Schlüssel von Alice und Bob effizient berechnen kann. b) (? ? ?) Da nach Aufgabenteil a) das Diffie-Hellman-Schlüsselaustauschprotokoll in der Gruppe hZn ; ⊕i unsicher ist und nach Theorem 7.7 jede zyklische Gruppe von Ordnung n zu hZn ; ⊕i isomorph ist, folgert Bob, dass das Protokoll für alle zyklischen Gruppen unsicher ist. Hat er recht? 10.5 RSA-Attacke (? ? ?) Ein Text m wurde mit RSA verschlüsselt an drei Personen gesendet, die als öffentliche Schlüssel (n1 , 3), (n2 , 3) beziehungsweise (n3 , 3) verwenden, die paarweise verschieden sind. Sie haben die drei Chiffrate c1 , c2 und c3 abgefangen. Wie können Sie daraus und aus den öffentlichen Schlüsseln m effizient berechnen? 10.6 Einheitengruppe (? ?) Beweisen Sie Lemma 7.19, d.h. zeigen Sie, dass die Menge der Einheiten R∗ eines Rings R eine multiplikative Gruppe bildet. Abgabe bis 23. November 2015, 10 Uhr Korrigiert wird Aufgabe 10.2