RSA-Problem

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo!
Ich möchte ein kleines Verschlüsselungsprogramm nach RSA schreiben. Große Primzahlen kombiniert mit der Modulorechnung ergeben einen schwerknackbaren coktail. Es soll mit C++ 6 folgendes berechnet werden:
c=65^228901 mod (509329*11197); //fmod oder % ist im Grunde egal

Warum tut das nicht? Es kommt ständig Überlauf. Ich speichere die Werte niergend zwischen, sondern es kommt alles in eine Zeile als ein Ausdruck. Auch am Datentyp zu basteln bringt nicht (float, long double, usw.).
Wenn ich die Gleichung in Maple 8 eingebe, kmmt nach ein paar Milisekunden das Ergebnis raus, in diesem Fall c = 246714407.
Außerdem für kleinere Werte (> = 11) rechnet C ++ was anderes aus als das CAS-System Ti92+, wem kann ich dann trauen?
Was mache ich falsch? Wie schaffen es die von Waterloo oder PGP? Hat mir jemanden einen funktionierenden Rat? Aber bitte keine RSA-Header oder dll aus dem Netz, weil ich es selbst verstehen will.
Vielen Dank im Voraus!

Gruß Christian

#2

Hi Christian,

ganz einfach:
Hast du überhaupt eine Ahnung, was du deinem Rechner da zum Rechnen gibst?
Lassen wir ihn mal 65^22 rechnen:
Ergebnis: 7.657620615851533E39

und 65^170: 1.5677276905294754E308

Das wars dann auch schon, zumindest für den Zahlenbereich von double in Java.
Für C++ kannst du auch hier nachlesen:
http://www.mathematik.uni-marburg.de/~cpp/grundlagen…

Mmh. Du musst also einen Weg finden, solch große Zahlen von deinem Rechner rechnen zu lassen. Da hilft wahrscheinlich nur ein Workaround in Form von „Ich rechne nach den 4 Grundrechenarten“.
Ich kann mich noch erinnern, dass wir im Studium mal einen Algorithmus entwickelt haben, damit man sehr große Zahlen miteinander multiplizieren kann. Das lief im Prinzip auf folgendes hinaus:
Jede der beiden Zahlen wird in einem Array gespeichert.
Dann wird (wie in der Grundschule) multipliziert:

 12 \* 65
 -------
 72
 60
----
=780

Kennst du das noch?

So in etwa könntest du ein Workaround entwickeln, was aber wahrscheinlich eine ganze Weile dauern dürfte, denn ich hab oben nur von den Grundrechenarten gesprochen. Dann musst du ja auch noch die Potenz entwickeln …

Ich würde sagen: uferlos, da es dies mit Sicherheit schon irgendwo gibt. Nur wo?
Ich hoffe, ich konnte dir trotzdem ein bisschen helfen.

Ciao, Bill

#3

Hi!
Vielen Dank, das ist wenigstens ein kleiner Schritt nach vorne. Aber ich hätte nch zwei Rückfragen:

  1. Rechenfehler sind dann nur bedingt aus Fehlern im Algorythmus, oder können solche auch einfach durch Fehler im SPeicher entstehen?
  2. Braucht es sehr viel längere Rechenzeit einen solchen Algorithmus berechnen zu lassen, als wie wenn ich es herkömliche Weise berechne (z.B. Maple)?
    Vielen DAnk aber schon mal!!!

Christian

#4

Hallo Christian,

Vielen Dank, das ist wenigstens ein kleiner Schritt nach
vorne. Aber ich hätte nch zwei Rückfragen:

  1. Rechenfehler sind dann nur bedingt aus Fehlern im
    Algorythmus, oder können solche auch einfach durch Fehler im
    SPeicher entstehen?

Wenn sie durch Fehler im RAM entstehen hast du einen defekten Computer und somit ein System welches nicht vorhersehbare Resultate liefert !!!

Der FloatingPoint-Coprozessor arbeitet mit einem festen Format (total 80 Bit für Mantisse, Exponent und die zwei Vorzeichen) somit ergibt sich

  1. eine grösste und kleinste darstellbare Zahl auf Grund der Anzahl der verwendeten Bit für den Exponenten
  2. Eine Endliche Anzahl Ziffern für die Mantisse (ca 18).

Dadurch ist es unsinnig Algorithmen zu verwenden, welche Resultate erzeugen würden die genauer wären als die Auflösung der Mantisse.
Durch die endliche Dahrstellung der Mantisse ergeben sich Zwangsläufig Rechenungenauigkeiten:

long double a;
a = 1e30;
if (a

#5

Hi,

look a mal hier:
http://www.iti.fh-flensburg.de/lang/algorithmen/code…

Vielleicht hilft dir das weiter.
Musst einfach bissel suchen, irgendwann kommst du der Lösung deines Problems näher…

Ciao, Bill