Modulo auf sehr komplexe Zahlen anwenden

Dieses Thema im Forum "C/C++" wurde erstellt von x0r, 07.05.2007.

  1. x0r

    x0r Bitschubser

    Dabei seit:
    20.12.2005
    Beiträge:
    169
    Zustimmungen:
    0
    Ort:
    Berlin
    Mahltid folgendes Problem,

    habe zu Lernzwecken mich mit dem RSA-Verfahren zum Zerwürfeln von Nachrichten auseinandergesetzt. Das Ganze dann implementiert, und mit Schreibtischtest auch überprüft. Klappt soweit mit hardgenerated Schlüsselpaaren, die sind aber auch erheblich kleiner.

    Bei der Verwendung richtiger Schlüsselpaare bekommen wir es allerdings mit echt großen Zahlen zu tun, die dann als Exponenten in den Ver- und Entschlüsselungsalgoritmen den Wertebereich der Standarddatentypen sprengen.

    Es gibt einige Hinweise in diesem Zusammenhang auf ein math. Verfahren:
    die Binäre Exponentiation.

    Im Grunde genommen soll es so funktionieren:

    Folgender Ausdruck sei gegeben:

    b^n mod m

    Dann würde dieser Ausdruck in Teilschritte zerlegt so aussehen:

    b^n mod m = ((((b^2)^2)^2)..*b (mod m))

    So weit so gut. Wie kann ich das Ganze jetzt in Form eines brauchbaren Algoritmus 'sublimieren' lassen ?

    Ein Hinweis auf einen Codeschnipsel, oder ein (ANSI-C spez.) Beispiel-PDF zu diesem Thema wäre klasse.

    MfG...
     
  2. Anzeige

    Schau dir mal diese Kategorie an. Dort findest du bestimmt etwas.
    Registrieren bzw. einloggen, um diese und auch andere Anzeigen zu deaktivieren
  3. #2 Lord Kefir, 07.05.2007
    Lord Kefir

    Lord Kefir König

    Dabei seit:
    10.06.2004
    Beiträge:
    944
    Zustimmungen:
    0
    Das ist jetzt keine direkte Antwort aber ich habe mal 'nen RSA-Algorithmus mit dieser Library implementiert:

    http://gmplib.org/

    Vielleicht hast'e Spaß daran ;)

    Mfg, Lord Kefir
     
  4. #3 schorsch312, 07.05.2007
    schorsch312

    schorsch312 Routinier

    Dabei seit:
    18.07.2006
    Beiträge:
    372
    Zustimmungen:
    0
  5. #4 supersucker, 07.05.2007
    supersucker

    supersucker Foren Gott

    Dabei seit:
    21.02.2005
    Beiträge:
    3.873
    Zustimmungen:
    0
    Die sind halt komplexer als normal komplexe Zahlen........:D
     
  6. x0r

    x0r Bitschubser

    Dabei seit:
    20.12.2005
    Beiträge:
    169
    Zustimmungen:
    0
    Ort:
    Berlin
    @schorsch312 : ja, hast recht. das mit 'komlex' ist unsinn. sind nur eben sehr große zahlen, als mathe-n00b seh` ich über solche feinsinnigen Unterschiede relaxed hinweg xD

    @Lord Kefir : Klasse, jetzt muss ich es mir nimmer aus den rippen leiern.
    Dat isset !!!

    Und alles in <40min., unixboard rokkz like hell !!!

    MfG...
     
  7. #6 schorsch312, 07.05.2007
    schorsch312

    schorsch312 Routinier

    Dabei seit:
    18.07.2006
    Beiträge:
    372
    Zustimmungen:
    0
    War nicht böse gemeint, sollte nur ein Scherz sein.
    Gruß, Georg
     
  8. #7 Lord Kefir, 07.05.2007
    Lord Kefir

    Lord Kefir König

    Dabei seit:
    10.06.2004
    Beiträge:
    944
    Zustimmungen:
    0
    Also wenn Du magst kann ich mal meine Festplatte durchforsten - irgendwo könnte ich den Algorithmus noch haben...

    Mfg, Lord Kefir
     
  9. x0r

    x0r Bitschubser

    Dabei seit:
    20.12.2005
    Beiträge:
    169
    Zustimmungen:
    0
    Ort:
    Berlin
    war aber richtig, bin trotzdem nicht böse :D ^^

    angesichts:
    ...ist dass sicherlich ein guter Vorschlag :D

    Nehm ich gern in Ansruch!
    MfG...
     
  10. Anzeige

    Vielleicht findest du HIER Antworten.
    Registrieren bzw. einloggen, um diese und auch andere Anzeigen zu deaktivieren
  11. #9 Lord Kefir, 07.05.2007
    Lord Kefir

    Lord Kefir König

    Dabei seit:
    10.06.2004
    Beiträge:
    944
    Zustimmungen:
    0
    Hab' gerade mal geguckt - habe den Code leider nicht mehr. Im Grunde ist das alles aber recht einfach - zieh' Dir mal die Dokumentation (ich hatte mir damals glaub' ich das PDF heruntergeladen), da steht das wichtigste drin.

    Mfg, Lord Kefir
     
  12. #10 x0r, 08.05.2007
    Zuletzt bearbeitet: 08.05.2007
    x0r

    x0r Bitschubser

    Dabei seit:
    20.12.2005
    Beiträge:
    169
    Zustimmungen:
    0
    Ort:
    Berlin
    Danke nochmal @Lord Kefir für die Hinweise auf die gmplib.

    Um den Thread abzuschließen, hier die Auflösung des Problems:

    ... passt genau.
    Muss zuvor via:
    Code:
    mpz_t integ; */ der Klasseninterne Datentyp für die sehr großen Zahlen */
    mpz_init (integ); /* initialisierung mittels memberfunktion */
    ... 
    /* Unless the program is about to exit, do ... */ 
    mpz_clear (integ); /* 'delete'-ähnliche wirkung wie */
    } 
    
    initialisiert werden.


    Die Funktionen sind Teil der Klasse mpz_t

    We mit OOP nix am Hut hat kann dan auch über das LL-CI den entsprechend funktionalen Unterbau ansprechen, hierbei muss dann allerdings die (WORT)Länge der zahlen kennen, und diese selbst als unsigned Zeiger auf das geringst- signifikante Datenwort des ersten und zweiten Operanden übergeben.

    Einen ebenfalls gangbaren Weg habe ich in einem wikipedia-Artikel entnommen (zu sehen hier!):

    Code:
    /* ausgehend vom bereits geposteten Ausdruck: b^x mod m */
    
    int mod_exp(int b, int x, int m)
    {
            int erg = 1;
            while ( x > 0 ) 
            {
                    if ( x%2 > 0 ) { erg = ( erg*b ) % m; }
                    b = ( b*b ) % m;
                    x = x / 2;
            }
            return erg;
    }
    
    
    Womit wir wieder bei der Exponentiation großer Ausdrücke angekommen sind. Diese Anwendung erscheint mir im sez. Fall von RSA sinnvoller, da ich ja eigentlich nur an den 'Resten' der Exponentiation interessiert bin, und hier durch die Quantisierung in entsrechend viele kleine Teilschritte, die Ergebnisse schneller berechnet werden (bis jetzt masslose behautung ohne beweis). Ich werde mal ein seperates Beispiel implementieren um zu schauen in wie weit sich das auf die Laufzeit auswirkt.
     
Thema:

Modulo auf sehr komplexe Zahlen anwenden

Die Seite wird geladen...

Modulo auf sehr komplexe Zahlen anwenden - Ähnliche Themen

  1. Modulo C++ implementation (Diffie-Hellman-Schlüsselaustausch)

    Modulo C++ implementation (Diffie-Hellman-Schlüsselaustausch): Hi! Also ich hoffe einmal (ich gehe fast davon aus :D ), dass einige Leute hier im Forum den Diffie-Hellman-Schlüsselaustausch kennen. Unser...
  2. Nordrhein-Westfalen: In sehr kleinen Schritten zu freier Software

    Nordrhein-Westfalen: In sehr kleinen Schritten zu freier Software: Die Landesregierung von Nordrhein-Westfalen hat auf eine Kleine Anfrage der Piratenfraktion im Landtag bezüglich proprietärer Software und Formate...
  3. umount sehr langsam, device mapper schuld ?

    umount sehr langsam, device mapper schuld ?: Hi Leute, ich habe mal wieder ein verrücktes Problem, das ich nicht ganz nachvollziehen kann. Folgendes vorgehen: - erstellen eines...
  4. Sehr große Datei in Teilschritten auslesen.

    Sehr große Datei in Teilschritten auslesen.: Hallo an das Forum, ich brauche Eure Hilfe, der Groschen will bei mir nicht fallen: Ich habe eine sehr große Datei mit „über“ 100000 Zeilen....
  5. pm-suspend sehr langsam

    pm-suspend sehr langsam: Hallo zusammen Ich habe auf meinem neuen Sony Vaio VPCw12S1E ein CrunchBang 10 mit wmii installiert. Soweit funktioniert alles prächtig....