Mathematik HTL 4/5, Schulbuch

271 7.1 Kryptographie Also wird s = m (p – 1)(q – 1) – 1 sowohl von der Primzahl p als auch von der Primzahl q geteilt. Weil p ein Teiler von s ist, gibt es eine natürliche Zahl t so, dass s = p·t ist. Weil auch q ein Teiler von s = p·t ist, muss die Primzahl q einen der Faktoren p oder t teilen. Weil p eine andere Primzahl ist, muss q ein Teiler von t sein, das heißt, es gibt eine natürliche Zahl u so, dass t = q·u ist. Daher ist s = p·t = p·q·u. Daraus folgt, dass s = m (p – 1)(q – 1) – 1 auch von p·q = n geteilt wird und somit m (p – 1)(q – 1) mod n = 1 ist. Zusammenfassend erhalten wir (c d ) mod n = (m·(m (p – 1)(q – 1) ) ‒v ) mod n = (m·1 ‒v ) mod n = m. Warum kann Alice den Schlüssel für Bob öffentlich bekanntgeben? Kann dann nicht jeder Bobs Nachricht entschlüsseln? Ja, theoretisch kann das jeder tun. Man muss „nur“ die Zahl n in ein Pro- dukt von zwei Primzahlen zerlegen, dann mit dem euklidischen Algorithmus die Zahl d berech- nen und schließlich die d-te Potenz des Restes von c nach Division mit Rest durch n berechnen. Aber Alice kann darauf vertrauen, dass das zumindest in den nächsten hundert Jahren nicht geschehen wird. Eine Zahl in ein Produkt von Primzahlen zu zerlegen, gehört zu den aufwändigsten Problemen der Mathematik. Mit einem Computer dauert zwar die Multiplikation von sehr großen Primzahlen meist kürzer als eine Sekunde, das Produkt wieder in die zwei Faktoren zu zerlegen, dauert auch mit den schnellsten Computern mehrere hundert Jahre. Nur weil Alice – und nur sie allein – die Primfaktoren von n schon kennt, kann sie in kurzer Zeit die Nachricht entschlüsseln. Man kann das mit einem gedruckten Telefonbuch vergleichen: Das Telefonbuch liegt öffentlich auf, jeder kann zu einem Namen schnell die Telefonnummer finden. Es wäre theoretisch auch möglich, zu einer Telefonnummer den entsprechenden Namen zu finden, aber das kostet sehr viel Zeit. 1046 Alice hat für das RSA-Verfahren den Schlüssel n = 153 und e = 7 bekannt gegeben. a. Verschlüssle damit die Zahl 100. b. Alice weiß, dass 153 = 17·9 ist. Ermittle mithilfe des erweiterten euklidischen Algorithmus die Zahlen d und v so, dass d·7 + v·(17 – 1)·(9 – 1) = 1 ist. c. Alice erhält den „Geheimtext“ 31. Berechne mithilfe eines CAS den „Klartext“. a. (100 7 ) mod 153 = (10000 3 ·100) mod 153 = (55 3 ·100) mod 153 = 127 b. Wir wenden den erweiterten euklidischen Algorithmus auf (17 – 1)(9 – 1) = 128 und 7 an: I) 128 = 0·7 + 1·128 II) 7 = 1·7 + 0·128 | I – 18·II III) 2 = ‒18·7 + 1·128 | III – 3·II IV) 1 = 55·7 – 3·128 Also ist d = 55 und v = ‒ 3. c. Mit einem CAS berechnen wir (31 55 ) mod 153 = 40. Der „Klartext“ war 40. Das RSA-Verfahren liefert auch die Möglichkeit für eine elektronische Unterschrift : Wie kann Bob sicher sein, dass eine Nachricht wirklich von Alice kommt und nicht von einer Per- son, die nur vorgibt, Alice zu sein? Bob hat von Alice die Zahlen n und e als öffentlichen Schlüssel erhalten und weiß, dass nur Alice die Zahl d kennt, mit der sie seine Nachrichten (durch Poten- zieren modulo n) entschlüsselt. Alice teilt Bob öffentlich eine Zahl m < n mit und schickt ihm zusammen mit einem Text als „Unterschrift“ die Zahl z = (m d ) mod n. Diese kann nur Alice berechnet haben, weil sonst niemand den Exponenten d kennt. Aber Bob kann jetzt überprüfen, ob die Zahl wirklich m d ist und damit von Alice kommt, indem er z e mod n berechnet. Wenn z = m d ist, muss (z e ) mod n = (m d·e ) mod n = m sein. 1047 Welche Zahlen, die kleiner als 35 sind, können für e gewählt werden, wenn man den Schlüssel (5·7, e) für den RSA-Algorithmus wählt? Begründe. B mit dem RSA- Algorithmus entschlüsseln xls 8j4u6a elektronische Unterschrift B, D Nur zu Prüfzwecken – Eigentum des Verlags öbv