Modulo auf sehr komplexe Zahlen anwenden

[x0r]

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...

 

[Lord Kefir]

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

 

[schorsch312]

Was sind denn sehr komplexe Zahlen? :-)
http://de.wikipedia.org/wiki/Komplexe_Zahlen
Gruß, Georg

 

[supersucker]

Was sind denn sehr komplexe Zahlen? :-)

Die sind halt komplexer als normal komplexe Zahlen........

 

[x0r]

@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...

 

[schorsch312]

War nicht böse gemeint, sollte nur ein Scherz sein.
Gruß, Georg

 

[Lord Kefir]

Also wenn Du magst kann ich mal meine Festplatte durchforsten - irgendwo könnte ich den Algorithmus noch haben...

Mfg, Lord Kefir

 

[x0r]

War nicht böse gemeint, sollte nur ein Scherz sein.

war aber richtig, bin trotzdem nicht böse ^^

Also wenn Du magst kann ich mal meine Festplatte durchforsten - irgendwo könnte ich den Algorithmus noch haben...

angesichts:

High-level signed integer arithmetic functions (mpz). There are about 140 arithmetic and logic functions in this category.

...ist dass sicherlich ein guter Vorschlag

Nehm ich gern in Ansruch!
MfG...

 

[Lord Kefir]

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

 

[x0r]

Danke nochmal @Lord Kefir für die Hinweise auf die gmplib.

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

void mpz_powm (mpz t rop, mpz t base, mpz t exp, mpz t mod )
void mpz_powm_ui (mpz t rop, mpz t base, unsigned long int exp, mpz t
mod )
Set rop to base^exp mod mod.

... passt genau.
Muss zuvor via:

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!):

/* 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.