Lernziele

• Sie können die Grundkonzepte der asymmetrischen Kryptografie erklären, namentlich den öffentlichen und den privaten Schlüssel.
• Sie haben grundlegende Einsatzarten der asymmetrischen Kryptografie konzeptionell (mit Couverts) kennengelernt und können erklären, wann welcher Schlüssel von wem eingesetzt wird.
• Sie können mit dem Modulo-Rechner von Informatikgarten ein RSA-Schlüsselpaar nutzen, um Einsatzarten der assymmetrischen Kryptografie mit konkreten Zahlen nachzuvollziehen.

Einstieg: Couverts mit Schlössern

Stellen Sie sich vor, in unserer Klasse besitzt jede Person ihr eigenes, persönliches Couvert mit einem besonderen Schloss. Dieses Schloss hat einen Pfeil und drei Positionen:

• Pfeil nach oben (↑): Das Couvert ist offen.
• Pfeil nach links (←) oder rechts (→): Das Couvert ist verschlossen.

Für jedes Couvert gibt es zwei Schlüssel, die nur zu diesem einen Couvert passen:

• Den öffentlichen Schlüssel des Couverts gibt die Besitzerin frei an alle heraus. Jeder kann damit das Schloss nach links drehen (←).
• Den privaten Schlüssel behält die Besitzerin streng für sich. Nur sie kann damit das Schloss nach rechts drehen (→).

Wichtig: Wenn das Schloss einmal nach links gedreht wurde, kann es nur die Besitzerin mit ihrem privaten Schlüssel wieder öffnen (zurück auf ↑). Wenn es nach rechts gedreht wurde, kann es jeder mit dem öffentlichen Schlüssel wieder öffnen.

Das Grundkonzept der asymmetrischen Kryptografie

Jede Person besitzt ein eigenes Schlüsselpaar. Was der eine Schlüssel eines Paares verschliesst, kann nur der andere Schlüssel desselben Paares wieder öffnen.

Da jedes Couvert seiner Besitzerin gehört, gibt es also in der Klasse so viele verschiedene Schlüsselpaare wie Personen. Alices Couvert wird mit Alices öffentlichem Schlüssel oder Alices privatem Schlüssel bedient — Bobs Schlüssel passen da nicht.

Ihre Aufgabe: Was können Sie damit tun?

Ich habe für Sie solche Couverts vorbereitet. Arbeiten Sie zu zweit und bearbeiten Sie folgende Aufgaben der Reihe nach. Die Aufgaben werden zunehmend schwieriger. Nutzen Sie die Couverts aktiv — drehen Sie, öffnen Sie, verschliessen Sie!

Für jede Aufgabe notieren Sie sich:

1. Wessen Couvert wird verwendet?
2. Wer verwendet welchen Schlüssel und in welche Richtung wird gedreht?
3. Wer kann das Couvert wieder öffnen?

Aufgabe 1: Geheime Nachricht an Sie 🔒

Bob möchte Ihnen eine Nachricht schicken, die nur Sie lesen können sollen. Die ganze Welt (inklusive einer Lauscherin Eve) darf das Couvert unterwegs sehen, aber nicht öffnen können.

Wie geht Bob vor?

Welches Couvert nimmt er? Welchen Schlüssel verwendet er? In welche Richtung dreht er? Wieso können nur Sie das Couvert wieder öffnen?

Lösung

Bob nimmt Ihr Couvert, legt die Nachricht hinein und verwendet Ihren öffentlichen Schlüssel, um das Schloss nach links zu drehen (←).

Nur Sie können das Couvert wieder öffnen, denn nur Ihr privater Schlüssel passt zu Ihrem Couvert und kann ein nach-links-gedrehtes Schloss wieder auf ↑ drehen.

Erkenntnis: Ein mit dem öffentlichen Schlüssel verschlossenes Couvert kann nur von der Besitzerin des zugehörigen privaten Schlüssels geöffnet werden. → Das gewährleistet Vertraulichkeit.

Aufgabe 2: Sie unterschreiben ein Dokument ✍️

Sie möchten Bob ein Dokument schicken und ihm beweisen, dass es wirklich von Ihnen kommt und nicht von einer Fälscherin. Bob soll das Dokument lesen können, aber auch sicher sein, dass Sie der Absender sind.

Wie gehen Sie vor?

Wessen Couvert nehmen Sie? Welchen Schlüssel? In welche Richtung drehen Sie? Wer kann das Couvert öffnen, und was beweist das?

Lösung

Sie nehmen Ihr eigenes Couvert, legen das Dokument hinein und verwenden Ihren privaten Schlüssel, um das Schloss nach rechts zu drehen (→).

Jeder auf der Welt kann mit Ihrem öffentlichen Schlüssel das Schloss wieder auf ↑ drehen — also das Couvert öffnen. Aber da nur Sie den privaten Schlüssel zu Ihrem Couvert besitzen, konnten nur Sie das Couvert verschlossen haben. Das ist der Beweis, dass das Dokument von Ihnen kommt.

Erkenntnis: Ein mit dem privaten Schlüssel verschlossenes Couvert beweist die Identität des Absenders. → Das gewährleistet Authentizität und ist das Grundprinzip der digitalen Signatur.

Aufgabe 3: Identitätsprüfung (Challenge-Response) 🕵️

Sie bekommen einen Anruf von jemandem, der behauptet, Bob zu sein. Sie wollen prüfen, ob das stimmt. Sie haben Bobs öffentlichen Schlüssel (den hat er ja frei verteilt), aber natürlich nicht seinen privaten.

Wie prüfen Sie, ob die Person am Telefon wirklich Bob ist?

Überlegen Sie: Was könnten Sie der Person geben, damit sie beweisen muss, Bob zu sein?

Lösung

Sie schreiben eine zufällige Zahl (eine "Challenge") auf einen Zettel und legen ihn in Bobs Couvert (das Bob Ihnen zur Verfügung gestellt hat, oder das Sie sich beschaffen können). Sie schicken das offene Couvert an die Person und bitten: "Verschliesse dein Couvert mit deinem privaten Schlüssel und schicke es mir zurück."

Wenn die Person wirklich Bob ist, kann sie das Schloss an seinem eigenen Couvert nach rechts (→) drehen. Sie öffnen das zurückkommende Couvert mit Bobs öffentlichem Schlüssel. Wenn die gleiche Zufallszahl darin ist, wissen Sie: Die Person besitzt tatsächlich den privaten Schlüssel zu Bobs Couvert — es ist wirklich Bob.

Erkenntnis: Das ist das Challenge-Response-Verfahren. Es wird z.B. beim Login per SSH verwendet, um zu beweisen, dass Sie wirklich der Kontoinhaber sind, ohne dass Sie ein Passwort übertragen müssen.

Aufgabe 4: Schlüsselaustausch für schnelle Kommunikation 🔑

Asymmetrische Verschlüsselung ist langsam. Für lange Gespräche ist sie unpraktisch. Sie und Bob möchten daher einen gemeinsamen, geheimen Schlüssel für schnellere symmetrische Verschlüsselung (z.B. Vigenère) austauschen.

Wie können Sie Bob einen geheimen Schlüssel zuschicken, den wirklich nur er erfährt?

Tipp: Sie können auch etwas in das Couvert hineinlegen, bevor Sie es verschliessen.

Lösung

Sie schreiben einen frisch erfundenen geheimen Schlüssel (z.B. "Katze42") auf einen Zettel, legen ihn in Bobs Couvert und verschliessen es mit Bobs öffentlichem Schlüssel (nach links ←).

Nur Bob kann das Couvert öffnen und erfährt dadurch den geheimen Schlüssel. Danach können Sie beide mit diesem Schlüssel schnell und symmetrisch (z.B. mit Vigenère) kommunizieren.

Erkenntnis: Das ist die hybride Verschlüsselung. Asymmetrische Kryptografie wird nur kurz verwendet, um einen symmetrischen Schlüssel auszutauschen — den Rest erledigt dann die schnellere symmetrische Verschlüsselung. Genau so funktioniert HTTPS im Web.

Aufgabe 5: Geheim UND signiert 🎭🔒

Jetzt die Königsdisziplin: Sie möchten Bob eine Nachricht schicken, die:

• Nur Bob lesen kann (Vertraulichkeit), UND
• beweist, dass sie von Ihnen kommt (Authentizität).

Wie kombinieren Sie beides?

Tipp: Sie können ein Couvert in ein zweites Couvert stecken. Überlegen Sie genau: Wessen Couverts nehmen Sie für welchen Schritt?

Lösung

Schritt 1 (Signieren): Sie legen Ihre Nachricht in Ihr eigenes Couvert und verschliessen es mit Ihrem privaten Schlüssel (→). Das signiert die Nachricht.

Schritt 2 (Verschlüsseln): Sie legen dieses signierte Couvert in Bobs Couvert und verschliessen dieses mit Bobs öffentlichem Schlüssel (←). Das verbirgt die Nachricht vor der Welt.

Bob entschlüsselt:

1. Öffnet das äussere Couvert (sein eigenes) mit seinem privaten Schlüssel → findet Ihr verschlossenes Couvert darin.
2. Öffnet Ihr Couvert mit Ihrem öffentlichen Schlüssel → wenn das funktioniert, weiss er: Die Nachricht ist wirklich von Ihnen.

Erkenntnis: Durch Kombination der beiden Grundoperationen erreicht man Vertraulichkeit UND Authentizität gleichzeitig. Das ist z.B. die Grundlage von verschlüsselten E-Mails (PGP).

Übersicht: Die zwei Grundoperationen

Alle Anwendungen basieren auf zwei Grundoperationen:

Drehrichtung	Couvert	Verschlossen mit	Geöffnet mit	Zweck
← (nach links)	Couvert des Empfängers	öffentlichem Schlüssel des Empfängers	privatem Schlüssel des Empfängers	Vertraulichkeit: Nur der Empfänger kann lesen
→ (nach rechts)	Couvert des Absenders	privatem Schlüssel des Absenders	öffentlichem Schlüssel des Absenders	Authentizität: Beweist, wer der Absender ist

Alles andere — Schlüsselaustausch, Identitätsprüfung, signierte und verschlüsselte Nachrichten — sind Kombinationen dieser zwei Grundoperationen.

Wie funktioniert das in der Informatik?

Sie haben jetzt das Prinzip verstanden. Aber wie kann so ein "Couvert mit zwei Schlüsseln" überhaupt erzeugt werden? Das schauen wir uns nun an — mit dem berühmtesten Verfahren der asymmetrischen Kryptografie: RSA.

V.l.n.r: Adi Shamir, Ron Rivest, and Len Adleman. Photo von Dan Wrights RSA-Algorithmuskurs auf imps.mcmaster.ca.

Kurz nach Diffie und Hellman veröffentlichten diese drei Forscher — Ronald Rivest, Adi Shamir und Leonard Adleman — im Jahr 1977 das RSA-Kryptosystem. Sie entdeckten, dass man mit der gleichen Einbahnstrassen-Idee wie bei Diffie-Hellman — der modularen Exponentiation — durch die geschickte Wahl der Zahlen ein System schaffen kann, bei dem zwei Schlüssel jeweils in umgekehrter Richtung eine Einbahnstrasse schaffen.

Ein konkretes Rechenbeispiel

Unser öffentlicher Schlüssel ist $\textcolor{lightgreen}{k_{pub}} = \textcolor{lightgreen}{1007}$, unser privater Schlüssel ist $\textcolor{orange}{k_{priv}} = \textcolor{orange}{1103}$ und $n = 3233$. Diese Zahlen wurden speziell so gewählt, dass sie als Schlüsselpaar zusammenpassen.

Nehmen wir an, jemand möchte uns eine Nachricht schicken, die nur wir verstehen, z.B. den Buchstaben "a", also Code 97 in der ASCII-Tabelle. Die Person würde mit dem öffentlichen Schlüssel verschlüsseln:

$\textcolor{cyan}{\text{klartext}}^{\textcolor{lightgreen}{k_{pub}}}\mod{n}= \textcolor{lightgreen}{\text{ciphertext}_{pub}}$

$\textcolor{cyan}{97}^{\textcolor{lightgreen}{1007}} \mod{3233}= \textcolor{lightgreen}{1388}$

Beachten Sie: Mit dem öffentlichen Schlüssel $\textcolor{lightgreen}{k_{pub}}$ lässt sich der Ciphertext nicht mehr entschlüsseln — es kommt eine ganz andere Zahl heraus:

$\textcolor{lightgreen}{1388}^{\textcolor{lightgreen}{1007}} \mod 3233 = \textcolor{red}{1056}$

Erst mit dem privaten Schlüssel $\textcolor{orange}{k_{priv}} = \textcolor{orange}{1103}$ kommen wir zurück zur ursprünglichen Nachricht:

$\textcolor{lightgreen}{\text{ciphertext}_{pub}}^{\textcolor{orange}{k_{priv}}} \mod{n}= \textcolor{cyan}{\text{klartext}}$

$\textcolor{lightgreen}{1388}^{\textcolor{orange}{1103}} \mod 3233 = \textcolor{cyan}{97}$

Nachrechnen

Probieren Sie es selbst aus:

Übung: Verschlüsseln Sie den Buchstaben "b" (ASCII 98).

Verwenden Sie den Rechner und berechnen Sie $98^{1007} \mod 3233$.

Lösung: $98^{1007} \mod 3233 = 3042$. Entschlüsseln Sie dann mit $3042^{1103} \mod 3233 = 98$ ✓

Einen Buchstaben verschlüsseln mit neuen Schlüsseln

Hier ist ein neues, kleines Schlüsselpaar, mit dem Sie die Schritte komplett selbst durchspielen können:

• Modul: $n = 143$
• Öffentlicher Schlüssel: $k_{pub} = 7$
• Privater Schlüssel: $k_{priv} = 103$

Nutzen Sie den Rechner oberhalb, um die folgenden Aufgaben zu lösen.

Sie möchten den Buchstaben "C" verschlüsseln.

1. Schlagen Sie den dezimalen ASCII-Wert für den Grossbuchstaben "C" nach.
2. Verschlüsseln Sie diesen Wert mit dem öffentlichen Schlüssel.
3. Welchen Geheimtext erhalten Sie?

Lösung

1. In der ASCII-Tabelle hat der Buchstabe "C" den Wert 67.
2. Die Formel für das Verschlüsseln lautet: $\text{Klartext}^{k_{pub}} \mod n$.
3. Sie rechnen also: $67^7 \mod 143$. Das ergibt als Geheimtext 89.

Das Faktorisierungsproblem

Anders als bei Diffie-Hellman wird für den Modulo keine Primzahl verwendet, sondern das Produkt zweier Primzahlen. Das hat einen entscheidenden Effekt: Die Sicherheit von RSA beruht zusätzlich zur Einbahnstrasse der modularen Exponentiation auch auf dem Faktorisierungsproblem.

Es ist einfach, zwei grosse Primzahlen zu multiplizieren, aber extrem schwierig, aus dem Produkt wieder die ursprünglichen Primzahlen zu ermitteln.

Beispiel:

$61 \times 53 = 3233$

Die Multiplikation dauert Sekundenbruchteile. Aber wenn Sie nur die Zahl 3233 haben und herausfinden müssen, welche zwei Primzahlen multipliziert wurden, wird es deutlich schwieriger. Bei grossen Zahlen (mit hunderten von Stellen) ist dies praktisch unmöglich.

Vertiefung: Wie funktionieren digitale Signaturen wirklich?

In Aufgabe 2 haben Sie gesehen, dass man ein Dokument mit dem privaten Schlüssel "verschliessen" kann, um es zu signieren. In der Praxis hat das aber ein Problem:

Grössenbeschränkung und Effizienz

Problem 1: RSA kann nur Nachrichten verschlüsseln, die kleiner sind als $n$. Bei einem typischen 2048-Bit-RSA-Schlüssel sind das maximal ~256 Bytes. Ein ganzes PDF-Dokument wäre viel zu gross.

Problem 2: Asymmetrische Verschlüsselung ist rechenintensiv. Ein ganzes Dokument zu verschlüsseln wäre sehr langsam.

Die Lösung: Man signiert nicht das ganze Dokument, sondern nur seinen Hash.

Ein Hash ist eine Art "Fingerabdruck" des Dokuments — eine kurze Zahl (z.B. 256 Bit bei SHA-256), die sich bei jeder noch so kleinen Änderung am Dokument komplett ändert.

Ablauf einer digitalen Signatur in der Praxis:

1. Alice berechnet $\text{Hash}(\text{dokument})$.
2. Alice verschlüsselt diesen Hash mit ihrem privaten Schlüssel → das ist die Signatur.
3. Alice schickt: $\text{dokument} + \text{signatur}$.
4. Bob berechnet selbst $\text{Hash}(\text{dokument})$.
5. Bob entschlüsselt die Signatur mit Alice' öffentlichem Schlüssel → er erhält einen Hash.
6. Wenn beide Hashes übereinstimmen → Das Dokument stammt wirklich von Alice und wurde nicht verändert.

Das ist genau das, was beim Couvert-Modell passiert — nur dass nicht das Dokument selbst im Couvert liegt, sondern sein Fingerabdruck.

Zusammenfassung

• Die asymmetrische Kryptografie arbeitet mit einem Schlüsselpaar: einem öffentlichen und einem privaten Schlüssel.
• Jedes Schlüsselpaar gehört zu einem bestimmten Couvert bzw. einer bestimmten Person.
• Was der eine Schlüssel eines Paares verschliesst, kann nur der andere Schlüssel desselben Paares wieder öffnen.
• Daraus ergeben sich zwei Grundoperationen: Vertraulichkeit (Verschlüsseln mit öffentlichem Schlüssel des Empfängers) und Authentizität (Signieren mit privatem Schlüssel des Absenders).
• Alle praktischen Anwendungen — HTTPS, Messenger, SSH, digitale Signaturen, verschlüsselte E-Mails — sind Kombinationen dieser zwei Operationen.
• RSA war das erste praktisch nutzbare asymmetrische Verfahren. Seine Sicherheit beruht auf dem Faktorisierungsproblem: Es ist einfach, zwei Primzahlen zu multiplizieren, aber extrem schwer, das Produkt wieder in Primzahlen zu zerlegen.