Problem mit Beispielrechnung für RSA

Guten Tag liebes ComputerBase Forum.
Ich habe aktuell folgendes Problem: Ich muss nächste Woche Dienstag einen Vortrag über Kryptographie halten und gehe dabei unter Anderem auf den RSA-Algorithmus ein.
Ich sollte, um das ganze dem Kurs noch etwas zu verdeutlichen, die Chiffre an einem Beispiel mit selbstgewählten, kleinen Primzahlen durchrechnen.
Ich stoße dabei allerdings auf einen Fehler, ich hoffe ihr könnt mir helfen ^^
Ich habe dafür benutzt:
P = 7 ; Q = 17 ;
N = P * Q = 119;
Phi(N) = (P-1) * (Q-1) = 96
e = teilerfremde Zahl zu Phi(N) = 5

Zu Testzwecken hab ich dann einfach mal den Buchstaben 'H' (ASCII-Wert 72) mit
C(Code) = K (Klartext)^e mod N = 4 ausgerechnet.

Dann kommt es zum erweiterten Euklidischen Algorithmus zur bestimmung von d, welches für die entschlüsselung (K = C^d mod N) benötigt wird.

Rechne ich den eEA durch, komme ich für d auf einen wert von -19, oder insgesamt auf die Formel für den ggT: 1=-19 * 5 + 1 * 96.
Entschlüssele ich nun aber mit K = 4^(-19) mod N komme ich auf einen Wert mit x*10^-12 etc.
Weiß jemand, wo ich einen Fehler gemacht haben könnte?

Hallo,
bei der Division von d * e = d * 5 mit Phi(N) = 96 muss der Rest 1 sein (d ist somit das Inverse zu e bzgl. der Multiplikation in gewählten Restklasse). Im Bsp. bietet sich d = 77 an. Vermutlich muss d mit Hinblick auf die Entschlüsselung eine natürliche Zahl sein, denn es gilt:
0 < x^(-y) < 1 für y > 1 und somit ist x^(-y) keine ganze Zahl mehr. Es gilt 77 * 5 = 385 und 385/96 = 4 Rest 1.
Mit diesem d kannst du deinen Code entschlüsseln. Beachte, falls z.B. Excel erst nicht will:
C^d = 4^77 = (4^11)^7, wobei man die Multiplikation in Restklassen vor Augen haben sollte.

Frank

Dein Professor hat aber nicht zufälligerweise die Initialen G.H.? ;-)

@FrankR Danke schonmal vielmals, dass das mit x^(-y) nicht hinkommen kann war mir auch schon aufgefallen.
Aber wie kommst du jetzt genau auf die 77?

Hallo,
77*5 = (-19+96)*5, wobei du selbst schon bemerkt hast, dass -19*5 bei Division durch 96 den Rest 1 läßt.
Für die Addition innerhalb einer Restklasse gilt: [x]+[y] = [x+y]. 96 läßt bei Division durch 96 den Rest 0 => [1]+[0]=[1+0]=[1]. Somit läßt auch 77*5 bei Division durch 96 den Rest 1.

Frank

Ah, okay. Vielen dank, ich habs jetzt.
Bin dir sehr dankbar, hast mir wirklich geholfen