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