Zum Hauptinhalt springen
25h

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 Vorgangaufwändiger/schwieriger Vorgang
offenes Bügelschloss schliessenBügelschloss ohne Schlüssel öffnen
Farben mischenFarben 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 418341 \cdot 83 auf Papier. Überlegen Sie sich dabei, wie Sie vorgehen.

  2. Schaffen Sie es, die Zahl 33973397 in ihre zwei Primfaktoren zu zerlegen? Und 11171117? Wie könnte man dabei vorgehen?

Aufwand für den Computer
  1. Wie schnell kann der Computer multiplizieren und faktorisieren? Überprüfen Sie mit dem folgenden Tool, wie schnell Ihr Computer beim Multiplizieren und Faktorisieren ist. Nehmen Sie für Primzahlen mit 6, 7 und 8 Stellen einige (>3) Messungen vor.

  2. Halten Sie die Messergebnisse fest (kopieren Sie den Plot und fügen diesen in der Antwort ein...)

  3. Was bedeutet es für eine kryptographische Anwendungen, wenn die beiden Primzahlen statt 8 Stellen mehrere mehrere hundert Stellen lang sind?

Zeitanalyse Primfaktorzerlegung

Primzahlen mit
Stellen

Zwei Primzahlen zwische 0 und 0 wählen