Mathematik HTL 4/5, Schulbuch

297 Zusammenfassung Verschlüsselungsverfahren „Tauschchiffre mit Schlüssel (a, b)“: Wir wählen eine natürliche Zahl n und a, b in Z n = {0, 1, … , n – 1} so, dass ggT(b,n) = 1 ist. Eine Zahl z in Z n wird zu (b·z + a) mod n verschlüsselt. Man kann die Nachricht y mithilfe des euklidischen Algorithmus entschlüsseln, indem man u, v mit u·b + v·n = 1 und u > 0 berechnet. Dann ist z = u·(y – a). Verschlüsselungsverfahren „Vigenère“: Ein n-Tupel (t 1 , …, t n ) von natürlichen Zahlen, die kleiner als 26 (die Anzahl der Buchstaben) sind, wird durch ein „Schlüsselwort“ (s 1 , … , s n ), ein n-Tupel von natürlichen Zahlen, die kleiner als 26 sind, zu (v 1 , …, v n ) = (t 1 + s 1 ) mod 26, … , (t n + s n ) mod 26) verschlüsselt. Wer das Schlüsselwort kennt, gewinnt (t 1 , … , t n ) durch ((v 1 – s 1 ) mod 26, … , (v n – s n ) mod 26) = (t 1 , … , t n ) zurück. Eine natürliche Zahl p heißt Primzahl , wenn sie genau zwei Teiler hat, nämlich 1 und sich selbst. Mit p bezeichnen wir eine Primzahl und mit a eine positive natürliche Zahl, die nicht von p geteilt wird. Dann ist a p – 1 mod p = 1.  Bob möchte eine natürliche Zahl m verschlüsseln und an Alice senden. Alice gibt dazu öffentlich zwei (sehr große) Zahlen e und n bekannt.  Bob berechnet c = (m e ) mod n und sendet die Zahl c an Alice.  Alice hat die Zahlen e und n so gewählt: n ist das Produkt von zwei sehr großen Primzahlen p und q. Die sehr große Zahl e wurde so gewählt, dass ggT(e, (p – 1)(q – 1)) = 1 ist.  Alice berechnet mit dem erweiterten euklidischen Algorithmus eine natürliche Zahl d und eine negative ganze Zahl v so, dass d·e + v·(p – 1)(q – 1) = 1 ist. Dann berechnet Alice (c d ) mod n, diese Zahl ist m. Alice möchte Bob beweisen, dass eine Nachricht von ihr kommt. Sie hat Bob die Zahlen n und e als öffentlichen Schlüssel für den RSA-Algorithmus mitgeteilt.  Alice sendet Bob eine Zahl m < n und die Zahl z = (m d ) mod n. Diese kann nur Alice berechnet haben, weil sonst niemand den Exponenten d (wie im RSA-Algorithmus) kennt.  Bob überprüft, ob die Zahl wirklich (m d ) mod n ist, indem er (z e ) mod n berechnet. Wenn (z e ) mod n = m ist, stammt die Nachricht von Alice (und nicht von jemand, der nur vorgibt, Alice zu sein). Ein Graph ist durch eine endliche Menge von Ecken und eine Menge von Kanten zwischen zwei Ecken des Graphen gegeben. Eine Bewertung eines Graphen ordnet jeder Kante genau eine reelle Zahl zu, ist also eine Funktion von der Menge der Kanten in die Menge der reellen Zahlen. Ein (n + 1)-Tupel von paarweise verschiedenen Ecken (a 0 , a 1 , …, a n ) eines Graphen ist ein Weg von a 0 nach a n in diesem Graphen, wenn je zwei aufeinander folgende Ecken die Eckpunkte einer Kante dieses Graphen sind. Tauschchiffre Vigenère- Verschlüsselung Primzahl Kleiner Satz von Fermat RSA- Algorithmus elektronische Unterschrift Graph Bewertung eines Graphen Weg Nur zu Prüfzwecken – Eigen um des Verlags öbv