Mathematik HTL 4/5, Schulbuch

265 7.1 Kryptographie 1021 Brutus schreibt an Cäsar: Wo treffen wir uns am 15. März? Cäsar schreibt verschlüsselt zurück: LQ URP. Cäsar hat Verschiebung um 3 verwendet und nur die Buchstaben, nicht das Leerzeichen, verschlüsselt. Was hat er geschrieben? Cäsar hat mit der Funktion f: Z 26 ¥ Z 26 , z ¦ (z + 3) mod 26, verschlüsselt. Die Umkehrfunktion ist Z 26 ¥ Z 26 , z ¦ z – 3 mod 26, wir müssen also in seiner Nachricht jeden Buchstaben durch den ersetzen, der im Alphabet drei Stellen vorher kommt. Aus L wird I, aus Q wird N … Cäsars Nachricht war: IN ROM. Wählen wir a, b in Z n so, dass die Funktion Z n ¥ Z n , z ¦ (b·z + a) mod n, umkehrbar ist, dann nennt man das entsprechende Verschlüsselungsverfahren eine Tauschchiffre mit Schlüssel (a, b) . Für b = 1 erhält man als Spezialfall das Verfahren durch Verschiebung um a. Wenn ggT(b, n) = 1 ist, können wir mit dem erweiterten euklidischen Algorithmus Zahlen u und v so berechnen, dass u·b + v·n = 1 und u positiv ist. Das hat zur Folge, dass (u·b) mod n = (1 – v·n) mod n = 1 mod n ist. Dann ist die Funktion Z n ¥ Z n , z ¦ (b·z) mod n, umkehrbar und ihre Umkehrfunktion ist Z n ¥ Z n , y ¦ (u·y) mod n. Denn: Multiplizieren wir b·z mod n mit u und bestimmen dann den Rest nach Division mit Rest durch n, erhalten wir (u·b·z) mod n = (1·z) mod n = (z) mod n. Wenn ggT(b, n) = c > 1 ist, dann ist die Funktion Z n ¥ Z n , z ¦ (b·z) mod n nicht umkehrbar. Denn in diesem Fall werden sowohl 0 als auch n _ c (das ist eine Zahl in Z n , weil c ein Teiler von n ist!) auf 0 abgebildet. Die Funktion f: Z n ¥ Z n , z ¦ (b·z + a) mod n, ist genau dann umkehrbar, wenn die Funktion g: Z n ¥ Z n , z ¦ ( b·z) mod n, umkehrbar ist. Ist nämlich Z n ¥ Z n , y ¦ ( u·y) mod n, die Umkehr- funktion von g, dann ist Z n ¥ Z n , y ¦ (u·(y – a)) mod n, die Umkehrfunktion von f. Beispiel: Aus den Wertetabellen für die Funktionen Z n ¥ Z n , z ¦ (b·z + a) mod n für n = 6 und (a, b) = (0, 5) bzw. (0, 4) bzw. (1, 5) sieht man, dass die Funktionen mit (a, b) = (0, 5) und (a, b) = (1, 5) invertierbar sind, die mit (a, b) = (0, 4) aber nicht. z (5·z) mod 6 z (4·z) mod 6 z (5z + 1) mod 6 0 0 0 0 0 1 1 5 1 4 1 0 2 4 2 2 2 5 3 3 3 0 3 4 4 2 4 4 4 3 5 1 5 2 5 2 umkehrbar nicht umkehrbar umkehrbar Für Elemente a, b von Z n erhält man aus der Funktion f: Z n ¥ Z n , z ¦ (b·z + a) mod n, genau dann eine Tauschchiffre mit Schlüssel (a, b), wenn ggT(b, n) = 1 ist. In diesem Fall können wir mithilfe des erweiterten euklidischen Algorithmus entschlüsseln: Man berechnet u, v mit u·b + v·n = 1 und u positiv, dann ist f ‒1 (y) = (u·(y – a)) mod n. 1022 Bestimme die Umkehrfunktion zu f: Z 7 ¥ Z 7 , f(z) = (3·z + 5) mod 7. Mithilfe des erweiterten euklidischen Algorithmus berechnen wir u und v mit u·5 + v· 7 = 1: I) 7 = 0·5 + 1·7 II) 5 = 1·5 + 0·7 | I – II III) 2 = ‒1·5 + 1·7 | II – 2·III IV) 1 = 3·5 + (-2)·7 Wegen f ‒1 (y) = (u·(y – 5)) mod 7, ist f ‒1 (y) = 3·(y – 5)) mod 7. mcd pw46vv B einen durch Ver- schiebung um a verschlüsselten Text entschlüsseln Tauschchiffren mit Schlüssel (a, b) entschlüsseln von Tauschchiffren mit Schlüssel (a, b) B Umkehr- funktion bestimmen Nur zu Prüfzwecken – Eigentum des Verlags öbv