Modul n
φ(n) (p − 1)(q − 1)
Öffentlicher Schlüssel (e, n)
Privater Schlüssel d e · d mod φ(n) = 1

Die Schlüssel

    So wird d gefunden: der erweiterte euklidische Algorithmus

    Jede Zeile entsteht durch Division der beiden Zeilen darüber. In der Zeile mit Rest 1 steht in der letzten Spalte d (addieren Sie φ(n), wenn es negativ ist).

    QuotientRestKoeffizient von e

    Die Nachricht

    Zeichen Code m Ergebnis

    Über das Netzwerk gesendet

    BitQuadrierenMit m multiplizieren

    Den Schlüssel knacken

    Aktion

    Mehr Informationen über RSA

    Demo zur RSA-Verschlüsselung

    Mit RSA kann jeder eine Nachricht mit Ihrem öffentlichen Schlüssel verschließen, während nur Sie sie mit Ihrem privaten Schlüssel öffnen können. Dahinter stecken ein paar Zeilen Schulmathematik: zwei Primzahlen, eine Multiplikation, ein Rest und ein raffiniertes Inverses. Erzeugen Sie ein Schlüsselpaar aus Primzahlen Ihrer Wahl, ver- und entschlüsseln Sie eine Nachricht Zeichen für Zeichen, signieren Sie sie, damit jeder prüfen kann, dass sie von Ihnen stammt, und schlüpfen Sie dann in die Rolle des Angreifers und faktorisieren Sie n, um zu sehen, warum echte Schlüssel Hunderte von Stellen brauchen. Wählen Sie zwei Primzahlen p und q oder drücken Sie Neue Primzahlen. Die App erzeugt den öffentlichen Schlüssel (e, n) und den privaten Schlüssel d und zeigt, wie der erweiterte euklidische Algorithmus d findet. Geben Sie eine Nachricht ein: Jedes Zeichen wird mit dem öffentlichen Schlüssel verschlüsselt und mit dem privaten Schlüssel entschlüsselt. Klicken Sie auf eine Zeile, um die durch wiederholtes Quadrieren berechnete Potenz zu sehen. Wechseln Sie zu Signieren, um stattdessen mit dem privaten Schlüssel zu signieren, und drücken Sie n faktorisieren, um zu sehen, wie schnell kleine Schlüssel brechen.

    Wie es funktioniert

    1. Geben Sie zwei Primzahlen p und q ein oder wählen Sie eine Größe und drücken Sie Neue Primzahlen; die App berechnet n, φ(n), e und d und zeigt, wie d gefunden wird.
    2. Geben Sie eine Nachricht ein und wählen Sie Verschlüsseln oder Signieren. Jedes Zeichen wird in eine Zahl umgewandelt und mod n potenziert; klicken Sie auf eine Zeile, um das wiederholte Quadrieren zu sehen.
    3. Drücken Sie n faktorisieren, damit Eve n in seine beiden Primzahlen zerlegt und den privaten Schlüssel ermittelt.

    So funktionieren die Schlüssel

    Multiplizieren Sie zwei Primzahlen: n = p × q. Mit p = 61 und q = 53 ist n = 3233. Die Zahl φ(n) = (p − 1)(q − 1) = 3120 zählt die Zahlen unterhalb von n, die zu n teilerfremd sind, und sie kann nur von jemandem berechnet werden, der p und q kennt. Wählen Sie e = 17, das zu 3120 teilerfremd ist, und bestimmen Sie d so, dass e × d um 1 größer ist als ein Vielfaches von φ(n): hier d = 2753, denn 17 × 2753 = 46801 = 15 × 3120 + 1. Veröffentlichen Sie (e, n) und behalten Sie d für sich. Eine Nachricht m wird zu c = mᵉ mod n, und der Satz von Euler garantiert, dass cᵈ mod n wieder m ergibt.

    Warum es schwer zu knacken ist

    Alles, was ein Angreifer braucht, steckt in den Faktoren von n. Bei n = 3233 ist das kein Schutz: Das Ausprobieren ungerader Teiler findet 53 nach etwa zwei Dutzend Versuchen. Doch der Aufwand wächst mit der Quadratwurzel von n. Ein Modul mit 2048 Bit hat etwa 617 Stellen, und kein bekanntes Verfahren kann ihn auf irgendeinem heute existierenden Computer in brauchbarer Zeit faktorisieren. Beim Signieren läuft RSA rückwärts: s = mᵈ mod n kann nur mit dem privaten Schlüssel erzeugt werden, und jeder kann prüfen, dass sᵉ mod n wieder m ergibt.

    Häufig gestellte Fragen

    Warum kann niemand d aus dem öffentlichen Schlüssel berechnen?

    Um d zu finden, braucht man φ(n) = (p − 1)(q − 1), und um φ(n) zu erhalten, braucht man p und q. Sie aus n zurückzugewinnen heißt, n zu faktorisieren, und für Zahlen mit Hunderten von Stellen ist kein schnelles Verfahren bekannt. In der Demo können Sie Spielzeugschlüssel in Sekundenbruchteilen faktorisieren, was genau zeigt, warum echte Schlüssel so groß sind.

    Warum wird die Nachricht Zeichen für Zeichen verschlüsselt?

    Weil die Spielzeugschlüssel klein sind: RSA kann nur eine Zahl verschlüsseln, die kleiner als n ist. Bei n = 3233 passt jeder Zeichencode, ein ganzer Satz aber nicht. Echtes RSA verwendet einen Modul mit 2048 Bit oder mehr, füllt die Nachricht mit zufälligen Bytes auf, damit dieselbe Nachricht nie zweimal gleich verschlüsselt wird, und verschlüsselt in der Praxis nur einen kurzen Schlüssel für eine schnellere Verschlüsselung wie AES.

    Was bewirkt wiederholtes Quadrieren?

    Es berechnet riesige Potenzen wie m²⁷⁵³ mod n, ohne die riesige Zahl je aufzuschreiben. Schreiben Sie den Exponenten binär und gehen Sie dann seine Bits durch: Quadrieren Sie das Zwischenergebnis bei jedem Bit und multiplizieren Sie bei jeder 1 mit m, wobei Sie jedes Mal den Rest mod n nehmen. Ein Exponent mit 2048 Bit braucht nur etwa 2048 Quadrierungen.

    Was ist der Unterschied zwischen Verschlüsseln und Signieren?

    Beim Verschlüsseln wird der öffentliche Schlüssel des Empfängers verwendet, sodass nur der private Schlüssel des Empfängers es rückgängig machen kann. Beim Signieren wird der private Schlüssel des Absenders verwendet, sodass jeder die Signatur mit dem öffentlichen Schlüssel des Absenders prüfen kann und weiß, dass die Nachricht vom Inhaber dieses Schlüssels stammt und nicht verändert wurde.

    Wird meine Nachricht irgendwohin gesendet?

    Nein. Alles wird in Ihrem Browser berechnet, und Ihre Primzahlen und Ihre Nachricht bleiben im lokalen Speicher dieses Browsers.

    Bereit, es auszuprobieren?

    Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

    Zum Editor