Asymmetrie

Wir haben in den beiden vorherigen Abschnitten 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:

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.

Multiplizieren vs. Faktorisieren

1. Berechnen Sie $41 \cdot 83$ auf Papier. Überlegen Sie sich dabei, wie Sie vorgehen.
2. Schaffen Sie es, die Zahl $3397$ in ihre zwei Primfaktoren zu zerlegen? Und $1117$? Wie könnte man dabei vorgehen?

Laden...

Laden...

Aufwand für den Computer

1. Wie schnell sind Computer beim Multiplizieren und Faktorisieren? Überprüfen Sie mit dem untenstehenden Experimentier-Tool, wie schnell Ihr Computer beim Multiplizieren und Faktorisieren von grossen Primzahlen ist. Verwenden Sie für jede Grössenordnung (6, 7, 8, evtl. 9 und 10 stellige Primzahlen) mehrere ($>3$) Messungen vor.
2. Halten Sie die Messergebnisse fest - kopieren Sie dazu den Plott der Messwerte als Bild in die Antwort.
3. Was bedeutet es für eine kryptographische Anwendungen, wenn die beiden Primzahlen statt 9 oder 10 Stellen mehrere hundert Stellen lang sind?

Laden...

Laden...

Zeitanalyse Primfaktorzerlegung

Mit diesem Tool können Sie die Zeit messen, die Ihr Computer benötigt, um

1. zwei Primzahlen zu finden
2. das Produkt der beiden Primzahlen zu berechnen
3. das Produkt wieder in seine Primfaktoren zu zerlegen

Die Ergebnisse werden in einem Scatterplot dargestellt, wobei auf der x-Achse die Anzahl Stellen des Produkts und auf der y-Achse die benötigte Zeit in Millisekunden aufgetragen ist.

Primzahlen mit

Stellen

Zwei Primzahlen zwischen 0 und 0 wählen

Gemeinsame Geheimzahl

Sie haben bereits gelernt, wie sich Bob und Alice auf eine 👉 gemeinsame Geheimfarbe einigen können. Noch praktischer wäre es, wenn sie sich stattdessen auf eine gemeinsame Geheimzahl einigen könnten. Diese könnten sie dann mit einer entsprechenden Abmachung als geheimen Schlüssel für ein symmetrisches Verschlüsselungsverfahren verwenden.

Wie könnten Bob und Alice eine gemeinsame Geheimzahl als Schlüssel für ein symmetrisches Verschlüsselungsverfahren verwenden?

Laden...

⭐️ Die mathematische Seite

Wenn Sie wissen möchten, wie Bob und Alice aus mathematischer Sicht zu einer solchen gemeinsamen Geheimzahl kommen können, dann schauen Sie sich dieses Video an:

Vereinfachung

Im Video werden einige mathematische Prinzipien etwas vereinfacht dargestellt. Tatsächlich werden nicht $g^a$ und $g^b$ über den öffentlichen Kanal ausgetauscht, sondern $g^a \mod n$, respektive $g^b \mod n$.

---