0 Daumen
342 Aufrufe

Ich habe für den öffentlichen Schlüssel n=203 und e=11 gegeben.

Der öffentliche Schlüssel lautet also y ≡ x^11 mod 203

Person A verschickt die Nachricht x=2, verschlüsselt also y=18

Ich kriege für den private key f^-1(y) ≡ y^107 mod 203 raus

Ich möchte nun als Person B die verschlüsselte Nachricht y=18 mit meinem private key entschlüsseln, dies kann ich mit Euler Fermat bestimmen, da 18^107 zu groß ist...

Ich erhalte jedoch keine Lösung:

18^107 ≡ x mod 203

phi (203) = 168

107 = k*168 ???

Wie soll ich nun 18^107 kleiner kauen, wenn ich letzteres nicht rauskriege?

Freue mich für jede Hilfe.

von

1 Antwort

0 Daumen

Guten Morgen yolo, 

der RSA funktioniert wie folgt (Auszug aus meiner Zusammenfassung für Kryptologie):

Bild Mathematik

Es ist \(n=203=7\cdot 29\) und \(\varphi(n)=\varphi(203)=\varphi(7)\cdot \varphi(29)=(7-1)\cdot (29-1)=168\). Der öffentliche Schlüssel ist \((n,e)=(203,11)\). Die verschlüsselte Nachricht lautet $$2^{11}\equiv 18\mod 203$$ Den geheimen Schlüssel berechnen wir, indem wir das multiplikative Inverse von \(11\mod \varphi(n)\) berechnen. \(\varphi(203)=168\) und das multiplikative Inverse von \(11\mod 168\) ist \(107\), denn \(11\cdot 107\equiv 1\mod 168\). Der geheime Schlüssel lautet also: $$(n,d)=(203,107)$$ Du hast also alles richtig berechnet!

Wir entschlüsseln die Nachricht \(18\) mit dem geheimen Schlüssel wie folgt: $$c^d\mod n= 18^{107} \equiv \mod 203$$ Dieses Ergebnis kannst Du durch "schnelle Exponentiation" errechnen, die ich hier (https://www.mathelounge.de/416619/was-ist-mit-schneller-exponentiation-gemeint) sehr ausführlich erklärt habe. Verwende dazu \(107_{(10)}=1101011_{(2)}\). Du musst also \(7\) Teilergebnisse berechnen, von denen Du \(5\) für die finale Multiplikation benötigst (die Einser). Orientiere Dich am besten an meiner verlinkten Antwort und stelle Rückfragen, wenn Du etwas nicht verstehst.

EDIT

Ich rechne es Dir hier zur Sicherheit doch einmal vor:

\(18^{2^0}=18\mod 203\)

\(18^{2^1}=18^2\equiv 121\mod 203\)

\(18^{2^2}=121^2 \equiv 25\mod 203\)

\(18^{2^3}=25^2 \equiv 16\mod 203\)

\(18^{2^4}=16^2 \equiv 53\mod 203\)

\(18^{2^5}=53^2 \equiv 170\mod 203\)

\(18^{2^6}=170^2 \equiv 74\mod 203\)

Multipliziert werden nun die Ergebnisse an den "Einser-Stellen" und das Produkt modulo \(203\) gerechnet: 

\(18\cdot 121\cdot 16\cdot 170\cdot 74=438387840\equiv 2\mod 203\)

Du kannst bei jedem Zwischenprodukt durch Modulieren die Ergebnisse etwas "handlicher" (d.h. hier kleiner) machen.

Viele Grüße

André

von

Hallo André :-)

Danke dir für deine schnelle Antwort und Mühe!

Ich verstehe deinen Lösungsweg, ich empfinde diesen jedoch als viel zu aufwendig... zunächst den Exponenten ins Binärsystem übersetzen und dann 7 Teilrechnungen durchführen... gibt es denn keine andere Möglichkeit? Geht es nicht allein mit Hilfe von den Euler-Fermat-Sätzen? 

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community