Mathematik HTL 4/5, Schulbuch

270 Diskrete Mathematik 1045 Gegeben sind die Primzahl p und die natürlichen Zahlen n und b. Überprüfe, ob ggT(n, p – 1) = 1 ist. Berechne dann die n-te Wurzel aus b modulo p. a. p = 523, n = 5, b = 100 c. p = 547, n = 17, b = 20 b. p = 523, n = 19, b = 500 d. p = 547, n = 37, b = 5 Der RSA-Algorithmus Der RSA-Algorithmus wurde von den Mathematikern Rivest, Shamir und Adleman im Jahr 1978 publiziert. Überraschend dabei ist, dass der Schlüssel zum Verschlüsseln öffentlich bekannt gegeben wird. Bob möchte eine Nachricht (wir können annehmen, dass diese durch eine natürliche Zahl m dargestellt wird) verschlüsseln und an Alice senden. Alice gibt dazu öffentlich bekannt, wie Bob die Nachricht m verschlüsseln soll:  Alice gibt zwei (sehr große) Zahlen e und n bekannt.  Bob berechnet den Rest von m e nach Division mit Rest durch n, also (m e ) mod n = c und teilt diese Zahl Alice mit. Damit Bob nicht zu lange rechnen muss, haben wir uns im 3. Jahrgang überlegt, wie man schnell Reste von Potenzen berechnen kann. Beachte aber, dass der kleine Satz von Fermat nicht verwendet werden kann, weil n keine Primzahl ist! Alice hat die Zahlen e und n nicht irgendwie, sondern geschickt so gewählt, dass ihr Aufwand für die Entschlüsselung gering ist:  Alice hat zwei verschiedene, sehr große Primzahlen p und q gewählt und ihr Produkt n = p·q berechnet.  Die ebenfalls sehr große Zahl e wählt sie dann so, dass ggT(e, (p – 1)(q – 1)) = 1 ist. Dazu muss sie vielleicht ein paarmal probieren, aber mit dem euklidischen Algorithmus ist die Berechnung des ggT für einen Computer kein Problem.  Diese Zahlen n und e gibt sie Bob öffentlich bekannt. Die Primzahlen p und q gibt sie aber nicht bekannt! Wie entschlüsselt Alice nun die Nachricht c von Bob?  Alice berechnet mit dem erweiterten euklidischen Algorithmus eine natürliche Zahl d und eine ganze Zahl v so, dass d·e + v·(p – 1)(q – 1) = 1 ist. Das ist immer möglich, weil e so gewählt wurde, dass ggT(e, (p – 1)(q – 1)) = 1 ist.  Dann berechnet Alice den Rest von c d nach Division mit Rest durch n, also (c d ) mod n. Unsere Überlegungen zum schnellen Berechnen von Resten von Potenzen kommen also nicht nur Bob, sondern auch Alice zugute.  Alice kann Bobs Nachricht jetzt lesen, denn m = (c d ) mod n. Warum ist (c d ) mod n = m? Wir können das mithilfe des kleinen Satzes von Fermat nachprüfen: (c d ) mod n = (m e ) d mod n = (m ed ) mod n = (m 1 – v(p – 1)(q – 1) ) mod n = = (m·(m (p – 1)(q – 1) ) ‒v ) mod n Wir können annehmen, dass die Zahl m kleiner als p und als q ist, also von beiden Zahlen nicht geteilt wird. Aus dem kleinen Satz von Fermat folgt nun:  (m (p – 1)(q – 1) ) mod p = ((m (p – 1) ) (q – 1) ) mod p = 1  (m (p – 1)(q – 1) ) mod q = ((m (q – 1) ) (p – 1) ) mod q = 1 B, D ggb p7ct3j tns 4s6k8b RSA- Algorithmus Nur zu Prüfzwecken – Eigentum des Verlags öbv