Schlüsselaustausch

Alice und Bob möchten sich geheime Unterlagen senden. Doch wie können sie den Schlüssel austauschen?

Schlüsselaustausch

Vielleicht hilft es, wenn wir uns in Erinnerung rufen, dass im Handel mehrere Schlösser mit unterschiedlichen Schlüsseln zu kaufen sind:

Schlüsselaustausch

Aufgabe: Schlüsselaustausch

Findet eine Möglichkeit, den Inhalt der Truhe sicher zu übertragen?

Versetzt euch dabei auch in die Rollen der anderen Krypto-Charaktere!

Lösung: Schlüsseltausch

1. 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.

2. 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.

3. 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:

1. Alice und Bob mischen sich je in einem Farbkübel eine persönliche, geheime Farbe, die sie niemandem mitteilen (private Farbe genannt).
2. 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).
3. 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.
4. 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.

C5 %

M66 %

Y3 %

K0 %

C0 %

M12 %

Y88 %

K0 %

C54 %

M53 %

Y68 %

K0 %

Fragen

Aufgabe: Geheime Farbe herausfinden

1. Wieso erhalten Alice und Bob schlussendlich dieselbe Farbe?
2. Ü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
$41$	$83$	?
?	?	$3397$

1. Berechne $41\ast 83$ auf Papier. Überlege dir dabei wie du vorgehst.
2. Schaffst du es die Zahl $3397$ 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
$41$	$83$	$3403$
$43$	$79$	$3397$

1. $41\ast 83=3403$. Berechnet nach den Regeln der schriftliche Multiplikation.
2. $3397=43\ast 79$. 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.

Asymmetrische Ver- und Entschlüsselung mit verschiedenen Schlüsseln

Generierung des Schlüsselpaares für die asymmetrische Verschlüsselung

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.

Jede Person besitzt ein Schlüsselpaar

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.

Asymmetrische Verschlüsselung

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

Asymmetrische Verschlüsselung für zwei Personen

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 und asymmetrische Verschlüsselung kombiniert

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

1. nicht mehrmals verschlüsselt werden müssen (Zeitbedarf) und
2. 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:

1. Er ist wirklich zufällig und gleichverteilt im gesamten Schlüsselraum (ein Passwort, das von einer Person gewählt wird, schafft dies nicht).
2. 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.

Symmetrische und asymmetrische Verschlüsselung kombiniert

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

Symmetrische und asymmetrische Entschlüsselung kombiniert

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.