Warnung
Auf dieser Seite findet ihr das Skript von fts. Diese Lektion wurde aber von Frau Helmy unterrrichtet!
Die Unterlagen von Frau Helmy findet man hier:
https://sites.google.com/view/praktikuminformatik/kryptologie/asymmetrsiche-verschlüsselung
Schlüsselaustausch
Alice und Bob möchten sich geheime Unterlagen senden. Doch wie können sie den Schlüssel austauschen?
Vielleicht hilft es, wenn wir uns in Erinnerung rufen, dass im Handel mehrere Schlösser mit unterschiedlichen Schlüsseln zu kaufen sind:
Aufgabe: Schlüsselaustausch
Findet eine Möglichkeit, den
der Truhe sicher zu übertragen?
Versetzt euch dabei auch in die Rollen der anderen Krypto-Charaktere!
Lösung: Schlüsseltausch
Variante 1
Bob könnte Alice das eigene Schloss senden, mit dem Alice anschliessend die Truhe verschliesst.
Problem: Wie weiss Alice, dass es sich um Bobs Schloss handelt? Jemand unterwegs könnte das Schloss austauschen.
Variante 2
Alice verschliesst die Truhe mit dem eigenen Schloss, um ungewollten Zugriff zu unterbinden. So verschlossen schickt sie die Truhe an Bob. Auch er kann sie nicht öffnen. Daher fügt er noch sein Schloss hinzu und sendet die Truhe zurück. Nun kann Alice ihr Schloss entfernen und die Truhe ein letztes Mal schicken.
Dass es sich um Alices Schloss handelt, kann Bob glauben, da die Absenderin die Informationen ja sicher nicht offen transportieren würde.
Problem: Wie weiss Alice, dass es sich um Bobs Schloss handelt? Jemand unterwegs könnte das Schloss austauschen.
Variante 3
Hier handelt es sich eigentlich um die erste, einfache Variante mit nur einer Sendung. Allerdings erhält Alice das Schloss nicht von Bob, sondern von einer vertrauenswürdigen Dritten Stelle (Trent). Trent hat eine ganze Sammlung von Schlössern – natürlich nicht nur von Bob, sondern von ganz vielen Leuten. So können alle, die Trent vertrauen, dort Schlösser abholen.
Schlösser beim vertrauenswürdigen Trent beziehen
Geheime Farbe
Alice und Bob arbeiten an einem neuen Kunstwerk, auf das die Öffentlichkeit gespannt wartet. Die beiden möchten dafür eine ganz besondere Farbe verwenden. Diese Farbe soll aber unbedingt bis zur Vernissage geheim bleiben. Alice und Bob wohnen weit auseinander und können sich nicht treffen, um die geheime Farbe gemeinsam herzustellen, sie können sich lediglich Farbkübel per Post zusenden.
Alice und Bob
Sie haben eine Idee und gehen wie folgt vor:
- Alice und Bob mischen sich je in einem Farbkübel eine persönliche, geheime Farbe, die sie niemandem mitteilen (private Farbe genannt).
- Alice wählt nun zusätzlich eine Farbe, die nicht geheim gehalten wird. Sie füllt zwei grosse Farbkübel mit dieser Farbe, einen behält sie für sich selbst, den anderen schickt sie per Post an Bob (gemeinsame Farbe genannt).
- Im nächsten Schritt mischen sich Alice und Bob je in einem leeren Farbkübel eine neue Farbe: Sie nehmen dazu genau dieselbe Menge der eigenen privaten Farbe und der gemeinsamen Farbe. Diese neue Farbe schicken sie sich wieder gegenseitig zu.
- Im letzten Schritt nehmen sie zwei Einheiten der soeben erhaltenen Farbe und eine Einheit der privaten Farbe und erhalten die gemeinsame private Farbe, mit der sie die Teile des neuen Kunstwerks bemalen.
Eve
Die neugierige Journalistin Eve möchte unbedingt wissen, was Alice und Bob aushecken, um noch vor der Vernissage einen exklusiven Zeitungsbericht zu veröffentlichen. Daher versucht sie, an die gemeinsame private Farbe zu gelangen. Sie überwacht die Post und füllt sich von jeder transportierten Farbe ein wenig in eigene Behälter ab.
Ausprobieren
Werde selbst aktiv, bestimme die Farben für Alice und Bob und schaue dir die Ergebnisse an. In der Mitte siehst du die Farben, die ausgetauscht werden. Aussen werden die privaten Farben angezeigt.
Fragen
Aufgabe: Geheime Farbe herausfinden
- Wieso erhalten Alice und Bob schlussendlich dieselbe Farbe?
- Überlege, wieso Eve aus den verschickten Farben die geheime Farbe nicht herstellen kann?
Aufgabe: Digitale Farben
Würde dieses Verfahren auch mit digitalen Farben (also RGB-Werten) funktionieren?
Besprecht dies zu zweit und begründet!
Asymmetrie
Wir haben in den beiden vorherigen Kapiteln gesehen, dass es Vorgänge gibt, die in die eine Richtung einfach durchzuführen sind, in die entgegengesetzte Richtung allerdings sehr aufwändig oder gar unmöglich:
| einfacher Vorgang | aufwändiger/schwieriger Vorgang |
|---|---|
| offenes Bügelschloss schliessen | Bügelschloss ohne Schlüssel öffnen |
| Farben mischen | Farben trennen |
Diese Beispiele zeigen deutlich, worauf die asymmetrische Verschlüsselung basiert:
Tipp: Asymmetrische Verschlüsselung
Die asymmetrische Verschlüsselung basiert auf Aufgaben, die in eine Richtung einfach auszuführen sind, während man eine geheime Information braucht, um den Vorgang rückgängig zu machen.
Verfügt jemand nicht über diese geheime Information, ist die Umkehrung des Vorgangs nicht in sinnvoller Zeit zu bewältigen.
Ein mathematisches Problem dieser Art
Auch in der Mathematik gibt es Operationen, die einfach und schnell auszuführen sind. Die Umkehrung jedoch ist selbst für einen Computer aufwändig und kann Jahre dauern.
Ein Beispiel dafür ist das Multiplizieren zweier (Prim-)Zahlen. Jeder Computer kann pro Sekunde mehrere Milliarden Multiplikationen ausführen. Ein Produkt zweier Primzahlen in die beiden Faktoren zu zerlegen, ist jedoch ungleich aufwändiger – insbesondere wenn die Zahlen mehrere hundert Stellen lang sind.
Aufgabe: Multiplizieren vs. Faktorisieren
| 1. Primzahl | 2. Primzahl | Produkt der beiden Primzahlen |
|---|---|---|
| ? | ||
| ? | ? |
- Berechne
auf Papier. Überlege dir dabei wie du vorgehst. - Schaffst du es die Zahl
in ihre zwei Primfaktoren zu zerlegen? Wie könnte man dabei vorgehen?
Lösung: Multiplizieren vs. Faktorisieren
| 1. Primzahl | 2. Primzahl | Produkt der beiden Primzahlen |
|---|---|---|
. Berechnet nach den Regeln der schriftliche Multiplikation. . Durch Ausprobieren, also Division aller Primzahlen zwischen 0 und der Hälfte der Zahl.
Aufgabe: Computer zur Hilfe
Der Computer berechnet schnell! Das folgende interaktive Tool kennt alle Primzahlen zwischen 0 und 100’000. Du kannst damit deinen Computer testen.
Versuche einen durschnittlichen Faktor zu berechnen, der aussagt wie viel zeitaufwändiger die Faktorisierung gegenüber der Mutliplizierung ist:
Asymmetrische Verschlüsselung
Das Prinzip der asymmetrischen Verschlüsselung beruht also auf zwei verschiedenen Schlüsseln, dem sogenannten Schlüsselpaar (engl. key pair). Die beiden Schlüssel eines Schlüsselpaars nennt man öffentlichen und privaten Schlüssel (engl. public und private key).
Da für den Verschlüsselungsvorgang nicht derselbe Schlüssel verwendet wird wie für den Entschlüsselungsvorgang, sprich man von einem asymmetrischen Verfahren.
Schlüsselpaar
Jede Person besitzt ein eigenes Schlüsselpaar, so auch Bob. Die beiden Schlüssel, die dieses Schlüsselpaar bilden, sind mathematisch verwandt. Der private Schlüssel lässt sich aus dem öffentlichen Schlüssel nicht in sinnvoller Zeit berechnen.
Bobs öffentlicher Schlüssel entspricht also dem Bügelschloss aus unserem ersten Beispiel. Bobs privater Schlüssel ist der Schlüssel, der zum Bügelschloss passt. Das Schloss kann (in geöffneter Form natürlich) bei einer vertrauenswürdigen Stelle (Trent) deponiert werden, wo es von Alice abgeholt werden kann. Den Schlüssel behält Bob stets für sich.
Verschlüsselung
In der Abbildung links sieht man, dass bei der Verschlüsselung der öffentliche Schlüssel des Empfängers (also Bobs Schloss) zum Einsatz kommt. Dieser öffentliche Schlüssel ist für alle Leute zugänglich (z.B. via eine vertrauenswürdige Stelle), somit können alle eine Nachricht für Bob verschlüsseln.
Entschlüsselung
In derselben Abbildung ist zu sehen, dass Bob bei der Entschlüsselung seinen privaten Schlüssel verwendet werden muss. Somit ist sichergestellt, dass nur Bob die Nachricht entschlüsseln kann.
Tipp: Achtung
Um Verwechslungen zu vermeiden, spricht man bei der symmetrischen Verschlüsselung vom geheimen Schlüssel (engl. secret key), während man bei asymmetrischen Verfahren vom privaten Schlüssel spricht und nicht vom geheimen Schlüssel, weil jede involvierte Person ein eigenes Schlüsselpaar und somit einen eigenen privaten Schlüssel besitzt.
Aufgabe: Aufgabe «asymmetrische Verschlüsselung»
Überlege dir und zeichne, wie die Verschlüsselung funktioniert, wenn ein Dokument an verschiedene Leute versendet wird.
Welche Nachteile erkennst du?
Lösung: asymmetrische Verschlüsselung
Nachteile
- Das Dokument muss separat für zwei Personen verschlüsselt werden.
- Eine separate Nachricht pro Person.
Verfahren kombinieren
Vergleich symmetrischer und asymmetrischer Verschlüsselung
Wir haben in der letzten Aufgabe gesehen, dass asymmetrische Verschlüsselung auch Nachteile hat. Wir wollen die Vor- und Nachteile einander gegenüberstellen.
| Symmetrische Verschlüsselung | Asymmetrische Verschlüsselung |
|---|---|
| ✔ sehr schnell | ✘ ~ 1’000x langsamer |
| ✔ 1 Nachricht für alle | ✘ 1 Nachricht pro Person |
| ✘ geheimen Schlüssel austauschen | ✔ Public Key ist öffentlich |
| → nur 1 gemeinsamer Schlüssel | → 1 Schlüsselpaar pro Person |
Beide Verfahren kombinieren
In kryptographischen Verfahren, die heutzutage eingesetzt werden, ist das Ziel, die Vorteile beider Verfahren zu nutzen und die Nachteile zu eliminieren. Daher werden zur Verschlüsselung von Daten beide Verfahren eingesetzt:
Symmetrische Verfahren zur Verschlüsselung der Daten
Da asymmetrische Verfahren ca. 1’000x langsamer sind als symmetrische Verfahren, werden zur Verschlüsselung der Daten symmetrische Verfahren eingesetzt. Denn kryptographische Verfahren werden nicht nur zur Verschlüsselung kurzer Nachrichten (wie z.B. Textnachrichten) eingesetzt, häufig müssen auch grosse Datenmengen (z.B. hochauflösende Bilder, Tondokumente, Videos, …) verschlüsselt werden, folglich spielt die Geschwindigkeit eine zentrale Rolle.
Zudem ist bei symmetrischer Verschlüsselung praktisch, dass die Daten somit für sämtliche Empfänger gleich verschlüsselt sind und somit
- nicht mehrmals verschlüsselt werden müssen (Zeitbedarf) und
- in derselben Nachricht an alle Empfänger verschickt werden können, ohne dass die Nachricht unnötig ein Mehrfaches ihrer ursprünglichen Länge erreicht (Platzbedarf).
Asymmetrische Verfahren zur sicheren Schlüsselübertragung
Asymmetrische Verfahren sind langsamer, aber zur Verschlüsselung des symmetrischen Schlüssels perfekt geeignet, da dieser sehr kurz ist im Vergleich zu den Daten spielt die Geschwindigkeit keine Rolle.
Zudem ist auch der verschlüsselte symmetrische Schlüssel sehr kurz, so dass die Nachricht nur unwesentlich länger wird, wenn diese für mehrere Personen verfasst wird.
Zusätzlicher Vorteil
Der symmetrische Schlüssel kann so problemlos vom Computer gewählt werden. Dies hat zwei Vorteile:
- Er ist wirklich zufällig und gleichverteilt im gesamten Schlüsselraum (ein Passwort, das von einer Person gewählt wird, schafft dies nicht).
- Er kann für jede Nachricht neu gewählt werden. Somit erhält jede Nachricht einen eigenen Schlüssel.
Man spricht daher von einem Sitzungsschlüssel (engl. session key) für die symmetrische Verschlüsselung. Die folgende Übersicht stellt prinzipiell dasselbe dar wie die Abbildung oben, allerdings mit einem anderen Fokus.
Aufgabe: Kombinierte Entschlüsselung
Schau dir das obenstehende Diagramm genau an und überlege wie der Rückweg funktioniert. Zeichne anschliessend ein analoges Diagramm für die Entschlüsslung der kombinierten Verschlüsselung, also ausgehend vom Geheimtext.
Lösung: Kombinierte Entschlüsselung
Tipp: Auch symmetrische Verfahren sind sicher!
Asymmetrische Verfahren sind also nicht besser als symmetrische! Sie erfüllen einen anderen Zweck und werden gleichzeitig mit symmetrischen Verfahren eingesetzt. Symmetrische Verfahren sind also nicht unsicher, einzig die Erstellung des Schlüssels und der Schlüsselaustausch sind ein Problem.