Kryptografie
Asymmetrische Verschlüsselung
8.-14. März
Ältere Verfahren der Kryptografie basieren auf der Idee, dem Sender und dem Empfänger einen gemeinsam verwendeten Schlüssel an die Hand zu geben. Ver- und Entschlüsselung geschehen mit dem gleichen Schlüssel. Das bezeichnet man als symmetrische Verschlüsselung.
Ein Problem ist hier, den Schlüssel geheim übergeben zu müssen, das heißt auch, auf einem anderen Kanal als die Nachricht. Bei der Enigma mussten die gedruckten Codebücher unter Bewaffnung an die militärischen Einheiten verteilt werden, der Geheimtext wurde öffentlich als Funkspruch versendet.
Den Schlüssel öffentlich versenden ...
... ist das überhaupt möglich? Ihn sogar auf einer Webseite zum Download anbieten? Das geht, und in dieser Woche werden wir sehen, wie.
Idee eines fast unknackbaren Schlüssels
Die zündende Idee kam in den 1970er Jahren auf. Man kann Zahlen einfach und schnell multiplizieren, aber die Faktoren wieder zu ermitteln, kann ziemlich lange dauern. Ich habe Euch ein Programm geschrieben, das gegebene Zahlen (Vielfache von 10 + 1) in ihre Primfaktoren zerlegt und dabei die Zeit misst.
In dem Diagramm ist die Rechenzeit über die Anzahl der Nullen in der gegebenen Zahl minus Eins aufgetragen. Rechts sieht man, wie sich die Rechenzeit nach Einfügen der nächsten Null vervielfacht. Daran sieht man das exponentielle Wachstum (immer etwa mal 3), das wir aus den Pandemieberichten kennen. Beim Verschlüsseln ist es nicht gefährlich, sondern sogar gut: Wir müssen die Zahlen nur recht groß machen, dann dauert das Ermitteln der Primfaktoren so lange, dass es kein Computer herausbekommt, solange die Nachricht gebraucht wird.
Am besten sind zwei etwa gleich große riesige Primzahlen, die multipliziert werden. Riesig heißt hier: viele hundert Stellen. Dann ist das Produkt einfach zu groß zum Zerlegen (solange uns da Quantencomputer keinen Strich durch die Rechnung machen).
So funktioniert RSA
Das RSA-Verfahren nutzt das Multiplizieren großer Primzahlen und einige weitere Techniken. Ich erkläre es Euch in diesem Film, den Ihr aufmerksam anseht und Euch Notizen macht (10 min reine Filmdauer).
Ergänzung zur Erläuterung:
Der öffentliche Schlüssel von Alice besteht aus den Zahlen n und a,
der private Schlüssel von Alice ist die Zahl b.
Nehmt Euch die Zeit, den Ver- und Entschlüsselungsvorgang zu verstehen. Schreibt das Beispiel auf und rechnet alle Schritte nach. Wenn Ihr Fragen habt, dann stehe ich per E-Mail zur Verfügung.
Aufgabe 1: Was bedeuten die Buchtaben R, S und A im RSA-Verfahren?
Aufgabe 2: (für BastlerInnen) Wer gern die Flash-Animation ausprobieren möchte, kann das in folgenden Schritten tun:
- Auf der Seite https://ruffle.rs/#releases das Plugin herunterladen (Browser Extension) und entpacken
(hier für Chrome) 
die entpackte Erweiterung laden (Weitere Tools/Erweiterungen, Entwicklermodus einschalten)- die Webseite https://www.mathe-online.at/materialien/Franz.Embacher/files/RSA/ öffnen und damit arbeiten, z. B. das Filmbeispiel nachrechnen
Aufgabe 3: Rechne das Beispiel aus dem Film nach (Anleitung siehe Aufgabe 4). Das geht auch ohne die Flash-Animation, einfach mit einem Blatt Papier und dem Computer.
Aufgabe 4: Wähle eigene Zahlen: Die Primzahlen p und q, berechne daraus n und m und wähle eine teilerfremde Zahl a (Primzahlen gehen da immer).
- Notiere den öffentlichen Schlüssel.
- Nimm eine (kleine) Zahl als Nachricht von Bob. Verschlüssle sie nach der Formel. Nutze Wolfram Alpha für die großen Zahlen und schreibe die Geheimtextnachricht (die Zahl also) auf.
- Lass Alice den privaten Schlüssel b errechnen. Mache dazu ein Rechenblatt wie im Film (Excel oder Libre/OpenOffice).
- Berechne die Klartextbotschaft von Bob aus der Geheimtextbotschaft mit Wolfram Alpha. Wenn sie wieder herauskommt, stimmt die Rechnung.
Schickt Eure Ergebnisse bis Freitag 14. 3. an mich. Viel Erfolg! Bei Fragen stehe ich gerne per E-Mail zur Verfügung.
Übung zur RSA-Verschlüsselung
Schwachstelle von RSA
Im obigen Abschnitt habt Ihr gelernt, wie die RSA-Verschlüsselung funktioniert. Dabei fällt vermutlich auf, dass bei diesem einfach erklärten Verfahren jede Zahl immer gleich verschlüsselt wird. Denn wenn jeder Buchstabe mit einer Zahl, zum Beispiel seinem ASCII-Wert oder Unicode, verschlüsselt wird, ist der hohe Aufwand von RSA nutzlos, denn dann kann man ja mit Häufigkeitsanalyse die häufigsten verschlüsselten Zahlen den häufigsten Buchstaben E, N, I, ... zuordnen.
Deshalb werden in der Praxis
- mehrere Buchstaben zu einer großen Zahl zusammengefasst (siehe unten)
- die Texte zusätzlich mit einem weiteren (symmetrischen) Verfahren verschlüsselt werden, z. B. AES, das wir hier nicht behandeln werden
Gruppen von mehreren Buchstaben / Zeichen
Für die Codierung der Nachricht verwenden wir in unserer Übung den ASCII eines Zeichens als Dezimalwert, der in Tabellen im Internet (Suchbegriffe: ascii tabelle) und in Eurem Tafelwerk aufgelistet ist.
Beispiele: A - 65, B - 66, a - 97, 1 (die Ziffer) - 49, Leerzeichen - 32. Vergleicht das mit Eurer ASCII-Tabelle.
Nun gruppieren wir immer zwei Zeichen der Nachricht, indem wir die ASCII-Werte hintereinander als eine Zahl lesen. Der übrige Buchstabe bei ungerader Anzahl wird durch 000 ergänzt.
Beispiel: Der Klartext sei CzG. Die ASCII-Werte sind 67, 122, 71.
Codiert besteht also die Klartextbotschaft aus den beiden Zahlen 67122 und 71000.
Erzeugung des RSA-Schlüsselpaars
Für das weitere Verfahren habe ich Euch ein Formular hochgeladen, das Ihr Euch am besten ausdruckt und in die Schule mitbringt (falls Ihr keinen Drucker habt, könnt Ihr in der Schule noch drucken).
Weil unsere Klartextnachrichten x nun aus Zahlen bestehen, die maximal 255*255 groß sind, aber kleiner als das Produkt n=p*q der beiden Primzahlen müssen, wählt Ihr zwei verschiedene dreistellige Primzahlen über 256, um das Schlüsselpaar zu erzeugen. Jetzt werden die Zahlen schnell sehr groß, aber keine Sorge, das Programm Wolfram Alpha rechnet mit sehr großen Zahlen genau.
Beispiel: Ich wähle p=661, q=769. Dann ist n=661*769=508309, m=660*768=506880
Als zu m teilerfremde Zahl a nehme ich eine große Primzahl, die knapp unter 506880 liegt: a=406177.
Ihr findet große Primzahlen auf einer Webseite unter dem Suchbegriff "Primzahlen bis 1000000".
Jetzt steht der öffentliche Schlüssel fest: n=508309, a=406177
Nun berechne ich meinen privaten Schlüssel: Gesucht ist ein Vielfaches von a, das beim Teilen durch 506880 den Rest 1 ergibt. Da die Zahlen so groß sind, hilft uns wieder Wolfram Alpha mit der Suche nach b, indem ich die Formel eingebe (eine Tabelle würde jetzt zu lang werden):
Damit ist der private Schlüssel b=174433 mit n=508309.
Nachrichtenaustausch
Nun wird der öffentliche Schlüssel von Alice an Bob geschickt, der seine Nachricht damit verschlüsselt und als y an Alice schickt. Alice entschlüsselt die Geheimtextbotschaft mit ihrem privaten Schlüssel.
Beispiel:
Bob schreibt die obige Nachricht 67122 und 71000 und verschlüsselt sie:
y=x^a (mod n)
y=67122 ^ 406177 (mod 508309) = 203484 (erste Zahl des Geheimtextes)
y=71000 ^ 406177 (mod 508309) = 87749 (zweite Zahl)
und schickt Alice diese beiden Zahlen, gern über einen öffentlichen Kanal.
Alice entschlüsselt und setzt also diese Zahlen in ihre Formel ein:
x=y^b (mod n)
x=203484^174433 (mod 508309) = 67122 (erste Zahl des Klartextes)
x=87749^174433 (mod 508309) = 71000 (zweite Zahl)
Nun bildet Alice in jeder Zahl von links immer Zahlen unter 256. Bei sehr kleinen ASCII-Werten kann es wenige Mehrdeutigkeiten geben, die sich aber durch Ausprobieren auflösen.Diese Zahlen sind 67, 122, 71, 000, womit die Botschaft entschlüsselt ist: CzG
Übung in der Stunde
Für diese Übung ist ein wenig Konzentration und Disziplin notwendig. Ihr werdet aber sehen, dass die konzentrierte Tätigkeit Spaß machen wird.
Ihr bildet Zweiergruppen (vier oder fünf). Jede Gruppe arbeitet zusammen. Wichtig ist, dass alle in der Gruppe das Verfahren verstehen!
1. Zuerst berechnet Ihr nach der obigen Anleitung Euer RSA-Schlüsselpaar. Die Zahl b behaltet Ihr natürlich für Euch. Eure Rolle ist jetzt Alice.
Der öffentliche Bereich ist unser Sdui-Gruppenchat 20/21 if1 12 KOE. Hier werden die öffentlichen Schlüssel (n, a) und die Geheimbotschaften y ausgetauscht, sonst nichts, höchstens Fragen zum Ablauf. Ihr könnt Sdui auf dem Smartphone betreiben, wenn möglich, dann müsst Ihr Euch nicht in der Schule anmelden. Ansonsten vergesst nicht Euer Sdui-Passwort mitzubringen!
2. Nun schreibt Ihr in den öffentlichen Bereich Euren öffentlichen Schlüssel mit der Nachricht: "Gruppe 1 = Maria und Norbert haben n=... und a=... als öffentlichen Schlüssel.". Wichtig: b dürft Ihr nicht verraten! Eure Rolle ist immer noch Alice.
3. Nun denkt Ihr Euch eine kurze Textnachricht aus (max. 10 Zeichen, sonst schafft Ihr die Rechnungen nicht in der Zeit. Jetzt habt Ihr die Rolle von Bob. Bildet die Zahlen x aus den ASCII-Werten wie oben beschrieben.
4. Gruppe 1 nimmt jetzt den öffentlichen Schlüssel von Gruppe 2, 2 von 3, 3 von 4, 4 von 5 und 5 von 1. Verschlüsselt Eure Nachricht und bildet die Folge der Zahlen y. Rolle: Bob
5. Schickt die Geheimbotschaft (die Zahlen y) im öffentlichen Bereich an die Gruppe mit der um 1 höheren Zahl (5 schickt an 1). "An Gruppe 2: Die Botschaft lautet yyyyyyyy, yyyy, yyyyy, yyy" (wie gesagt, max. 5 Zahlen). Rolle ist immer noch Bob.
6. Nun habt Ihr bald selbst eine verschlüsselte Nachricht und nehmt wieder die Rolle von Alice ein. Entschlüsselt die Nachricht mit Eurem privaten Schlüssel b und bildet die Zeichen aus den ASCII-Werten. Die Botschaft sollte für Euch einen Sinn ergeben.
7. Ich schicke Euch ebenso einen öffentlichen Schlüssel und verschlüsselte Nachrichten. Schickt mir Nachrichten und entschlüsselt meine.
Ich wünsche Euch viel Erfolg!