Kryptieren mit RSA

[Wolfs]

hallo,

da ich eigendlich ein Newby bin weis ich nicht ob das hier das richtige Forum ist um die Frage zu stellen da es aber um Datensicherung geht dachte ich es sei ok um meine Frage hier zu stellen.

Ich schreibe gerade ein Referat das ueber Kryptographie geht und haenge bei den Erweiterten Euklidischen Alghorithmus.

nehmen wir das beispiel von Wikipedia:

Vorarbeiten

-----------

Die oben genannten Schritte sollen nun an einem vollständigen Beispiel erläutert werden. Um einen Text zu verschlüsseln, müssen zunächst Buchstaben in Zahlen umgewandelt werden. Dazu verwendet man in der Praxis zum Beispiel den ASCII-Code. Hier sei willkürlich die folgende Zuordnung gewählt:

A=01 B=02 C=03 usw. (00 = Leerzeichen)

Darüber hinaus sei angenommen, dass jeweils drei Zeichen zu einer Zahl zusammengefasst werden. Die Buchstabenfolge AXT wird also zu 012420. Die kleinste zu verschlüsselnde Zahl ist dann 000000 (drei Leerzeichen), die größte 262626 (ZZZ). Der Modulus N = p \cdot q muss also größer 262626 sein.

Klartext: W I K I P E D I A

Kodierung: 230911 091605 040901

Schlüsselerzeugung

------------------

Zunächst werden geheim zwei Primzahlen gewählt, beispielsweise p = 307 und q = 859. Damit ergibt sich:

N = p * q = 263713

phi(N) = (p-1) * (q-1) = 262548

e = 1721 (zufällig, teilerfremd zu phi(N))

d = 1373 (das multiplikative Inverse zu e mod phi(N) mit Hilfe des Erweiterten euklidischen Algorithmus)

Öffentlicher Schlüssel: e = 1721 und N = 263713

Geheimer Schlüssel: d = 1373 und N = 263713

Verschlüsselung

---------------

Cn = Kne mod N für n=1,2,3(,...)

C1 = 2309111721 mod 263713 = 001715

C2 = 0916051721 mod 263713 = 184304

C3 = 0409011721 mod 263713 = 219983

Entschlüsselung

---------------

Kn = Cnd mod N für n=1,2,3(,...)

K1 = 0017151373 mod 263713 = 230911

K2 = 1843041373 mod 263713 = 091605

K3 = 2199831373 mod 263713 = 040901

Die Frage die sich mir jetzt stellt ist wie berechne ich das d? Ich verstehe die Formel nicht waere erfreut wenn sich jemand diesem Problem stellt und mir eine Antwort geben kann die ich verstehe.

Vielen dank schon einmal im Voraus.

[Wolfs]

hi,

hat den keiner eine ahnung wie die Rechnung funktioniert?

D = E mod (phi(N))

mit den erweiterten euklidischen algorithmus?

bitte dankeshön

[lupo49]

Das ist eher eine Frage bzw. Thema für ein Matheforum.

Viele Fachinformatiker hatten kein Mathe in der Berufsschule

[Wolfs]

ah ok. Kennste ein gutes mathe forum?

hoffe auf baldige antwort

[flashpixx]

mit den erweiterten euklidischen algorithmus?

Das wäre die Basis. Das multiplikative Inverse ist dann nichts anderes bei dem formal gilt: p * p^-1 = 1