programm Daten Primzahlen Zeile Waterloo Datentyp pgp

RSA-Problem

Von: , Frage gestellt am So, 29. Dez 2002

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

4 Antworten zu dieser Frage

1. Antwort von nach 3 Stunden 0 hilfreich

   Re: RSA-Problem

   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
   

   • Antwort von nach 10 Stunden 0 hilfreich

     Re^2: RSA-Problem

     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
     

     • Antwort von nach 11 Stunden 0 hilfreich

       Re^3: RSA-Problem

       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 < (a+1))
       {
       // wird nie ausgeführt !!!!!!
       // Da a nur auf 19 Stellen genau dargestellt wird und a+1 erst eine Änderung in der 31. Stelle verursachen würde.
       } 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)?
       Maple muss ja in jedem Fall einen Algorithmus verwenden, welcher auf deinem Computer funktioniert. Somit sind diejenigen Rechenzeiten welche Maple benötigt, logischerweise, machbar.
       Aber auf Grund deiner Frage bezweifle ich, dass du das mit deinem jetzigen Wissensstand auch so gut selber hinbekommst.
       Aber Übung macht den Meister !!
       
       MfG Peter(TOO)
       

     • Antwort von nach 14 Stunden 0 hilfreich

       Re^3: RSA-Problem

       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
       

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!