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:
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.
Berechnen Sie auf Papier. Überlegen Sie sich dabei, wie Sie vorgehen.
Schaffen Sie es, die Zahl in ihre zwei Primfaktoren zu zerlegen? Und ? Wie könnte man dabei vorgehen?
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,7und8Stellen einige (>3) Messungen vor.Halten Sie die Messergebnisse fest (kopieren Sie den Plot und fügen diesen in der Antwort ein...)
Was bedeutet es für eine kryptographische Anwendungen, wenn die beiden Primzahlen statt
8Stellen mehrere mehrere hundert Stellen lang sind?
Zeitanalyse Primfaktorzerlegung
Primzahlen mitStellen
Asymmetrie