---

Geschrieben von J.Dylan am 14.09.2009 um 00:07:

  Problem mit RSA-Verschlüsselung

Hallo,
Ich hätte mal ein paar fragen und hoffe, dass ihr mir da helfen könnt.
Spezielles problem mit einem RSA- Verschlüsselungsbeispiel und meinem Taschenrechner.
Ich wähle p=7 q=11 dann ist n=77 und phi(n)=60 nun wähle ich als Teilerfremden öffentlichen Schlüssel e=13 nun berechne ich über den erweiterten euklidischen algorithmus den privaten schlüssel d=37;
Nun wähle ich meine Nachricht M=3 und verschlüssele diese gemäß C=M^e mod n
also C=3^13 mod 77=38
Nun mein Problem beim wieder entschlüsseln das geht ja so M=C^d mod n
also M=38^37 mod 77
Soweit so gut. Jetzt kommt mein Problem: In meinem handtaschenrechner kann ich kein Modulo rechnen der normale Taschenrechner unter windows lässt sich auf wissenschaftlich erweitern und dann kommt auch M=3 raus. Aber wenn ich es in einen anderen wissenschaftlichen Taschenrechner eingebe kommt heraus das 38^37mod77=69 ist. Was stimmt jetzt?
Habe ich mich beim Schlüssel erzeugen verrechnet?
Wieso ergen 2 verschiedene Taschenrechner 2 verschiedene Ergebnisse.
Ich hoffe wirklich ihr könnt mir helfen.
Vielen dank im vorraus.

---

Geschrieben von woll997 am 14.09.2009 um 12:36:

  RE: Problem mit RSA-Verschlüsselung

38^37 = 28313468473157736370011296127792731029354930758695159595008

Aber das wird wohl kein Taschenrechner ausrechnen.

Überleg Dir einen besseren Rechenweg.

zum Beispiel.:
38^37 = 38 * 38^12 * 38^12 * 38^12

38^37 mod 77 = (38 * (38^12 mod 77) * (38^12 mod 77) * (38^12 mod 77)) mod 77