C++ RSA Verschlüsselung / "Fortgesetztes Quadrieren" / Riesige Zahlen
-
Guten Tag zusammen,
in letzter Zeit beschäftige ich mich mit diesem (übrigens gut erklärten)
Artikel: https://www.mathematik.de/ger/information/wasistmathematik/rsa/rsa.html
und versuche die dort gezeigten Rechenschritte in C++ umzusetzen...
Die Erzeugung einer beliebigen Primzahl funktioniert, auch die im Artikel
beschriebenen Variablen e und d konnte ich erzeugen / bestimmen, allerdings bin
ich jetzt an dem Punkt, das ich jetzt mit Potenzen rechnen muss wie z.B.
82^29 mod 91 (aus dem Rechenbeispiel des Artikels). Es ist natürlich klar, dass dabei
sehr große Zahlen herauskommen, zumindest bevor man "modulo 91" rechnet, daher wird
in einem weiteren Artikel das "fortgesetze Quadrieren" beschrieben:
https://www.mathematik.de/ger/information/wasistmathematik/rsa/rsa_potenzen.html
Das hab ich jetzt auch in einer Funktion umgesetzt die so aussieht:int pow_ex(int base, int expo, int ex_mod) //basis, exponent, modulo "Faktor" { int counter = 1, bin = 2, power; for (;;){ //in Endlosschleife 2er Potenzen ausrechnen bis eine gefunden wurde die kleiner als "int expo" ist bin *= 2; if (bin < expo){ counter++; } else{ break; } } bin /= 2; power = pow(base, 2); // ab hier fortgesetztes Quadrieren power %= ex_mod; for (int i = 1; i < counter; i++){ power = pow(power, 2); power %= ex_mod; } for (int x = 0; x < expo - bin; x++){ //Problem !!! in dieser Schleife enstehen unter Umständen riesige Zahlen, da // die Zahlen, welche nicht durch die 2er Potenzen gedeckt wurden hinten angehängt werden power *= base; //z.B. bei 82^29 muss man (29-16) 13 mal die basis mit dem ganzen davor mulitiplizieren } //und bei 82^13 kommt eine Zahl mit locker über 15 Ziffern heraus, welche natürlich nicht //in ein integer passt (ich bekomme dann immer negative Zahlen, was ja gar nicht sein kann) power %= ex_mod; return power; }
Nun brauche ich entweder eine Lösung, wie ich die Zahlen klein halten, was das fortgesetze Quadrieren ja eigentlich schon macht, aber eben nicht klein genug, oder einen Datentyp der riesige Zahlen speichern kann, allerdings wäre ich damit nicht so zufrieden (die BigInt Bibliothek wäre ja theoretisch eine Möglichkeit). Oder gibt es noch einen komplett anderen Lösungsweg den ich übersehen habe?
Vielen Dank für jegliche Hilfe im Vorraus
Gruß
Cyax
-
Ohne BigInt geht da nichts. RSA/ElGamal/etc. sind erst für sehr große Schlüssel sicher (also ints mit mehr als 512 Bit). Und eine effiziente BigInt-Klasse hat es in sich, denn du musst z.B. effiziente Multiplikationsverfahren (z.B. Karatsuba) implementieren. Auch das Auffinden von Primzahlen mit BigInts ist alles andere als einfach in diesen Dimensionen; meist beschränkt man sich auf Pseudoprimzahlen, für welche du Tests wie den von Miller-Rabin implementieren kannst.
In der Regel wird ModExp eine der teuren Operationen sein, die du auf einem BigInt ausführst.Fakt ist: kleine Zahlen gibt es in der Kryptografie eher nicht so.
-
Ich denke wenn du auch längere Schlüssel ermöglichen möchtest, wie sie auch in RSA-Implementierungen für den produktiven Einsatz verwendet werden, kommst du nicht umhin eine BigInt-Bibliothek zu verwenden, da dann dein Exponent und der Modulus schonmal ein paar tausend Bits lang sein können.
Was deinen Algorithmus betrifft, den habe ich mir jetzt nicht genau angesehen, im englischen Wikipedia-Artikel zu dem Thema sind allerdings 2 Algorithmen, die fortgesetztes Quadrieren nutzen, in Pseudocode angegeben:
http://en.wikipedia.org/wiki/Modular_exponentiation
Vielleicht lässt du dich davon inspirieren und verbesserst deine Variante entsprechend.
Auf den ersten Blick fällt mir z.B. bei dir auf, dass du diepow()
-Funktion verwendest. Falls es sich dabei umstd::pow()
handelt, tut es sicherlich nicht das was du möchtest:
Soweit ich weiss iststd::pow()
nur für Floating Point definiert, bzw. führt einen impliziten Cast in einen Floating-Point-Wert durch.Finnegan
-
Dein Problem lässt sich lösen, wenn Du in Zeile 22 schreibst:
(power *= base) %= ex_mod;
Dann bekommst Du keinen integer overflow solange
ex_mod^2 < numeric_limits< int >::max()
ist. Und die 91 ist da weit von entfernt.Abgesehen davon erscheint mir Dein Algorithmus etwas umständlich .. wie wär's mit:
int pow_ex( int base, int expo, int ex_mod ) { assert( expo >= 0 ); assert( base >= 0 ); assert( ex_mod > 0 ); assert( ex_mod <= std::numeric_limits< int >::max() / ex_mod ); // so kann es nie einen integer overflow geben base %= ex_mod; int result = 1; for( ; expo > 0; (base *= base) %= ex_mod, expo >>= 1 ) if( expo & 1 ) (result *= base) %= ex_mod; return result; }
-
assert( ex_mod <= std::numeric_limits< int >::max() / ex_mod ); // so kann es nie einen integer overflow geben
lol
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) { uint64_t r; asm ( "mulq %2; divq %3" : "=&d" (r), "+%a" (a) : "rm" (b), "rm" (m) : "cc" ); return r; } uint64_t powmod( uint64_t x, uint64_t exp, uint64_t mod ) { uint64_t res = 1; for (; exp; exp >>= 1) { if (exp&1) res = mulmod(res, x, mod); x = mulmod(x, x, mod); } return res; }
-
Jodocus schrieb:
Fakt ist: kleine Zahlen gibt es in der Kryptografie eher nicht so.
Ja, das ist mir auch schon aufgefallen, allerdings ist das ja lediglich ein kleiner Test von mir
und soll ja nicht eine super sichere Verschlüsselung sein, sondern mir geht es mehr darum, das
Prinzip hinter einer Verschlüsselung zu verstehen. Zudem möchte ich erstmal mit kleinen Zahlen
rechnen, damit ich besser nachvollziehen kann, was mein Programm eigentlich macht und ob das
auch alles korrekt ist... mit den riesigen Zahlen, welche normalerweise eingesetzt werden, ist
das leider nur schwer möglich Trotzdem danke für den Hinweis!Finnegan schrieb:
Was deinen Algorithmus betrifft, den habe ich mir jetzt nicht genau angesehen, im englischen Wikipedia-Artikel zu dem Thema sind allerdings 2 Algorithmen, die fortgesetztes Quadrieren nutzen, in Pseudocode angegeben:
http://en.wikipedia.org/wiki/Modular_exponentiation
Vielleicht lässt du dich davon inspirieren und verbesserst deine Variante entsprechend.
Perfekt, vielen Dank, so etwas hab ich gesucht.
Was std::pow angeht, magst du vielleicht recht haben, allerdings kenne ich keine andere Funktion um Potenzen zu berechnen.
Immer mit base*=base in einer for-Schleife zu rechnen, ist ja auch nicht gerade die schönste Lösung...Werner Salomon schrieb:
Dein Problem lässt sich lösen, wenn Du in Zeile 22 schreibst:
(power *= base) %= ex_mod;
Achja stimmt... Danke vielmals
Werner Salomon schrieb:
Abgesehen davon erscheint mir Dein Algorithmus etwas umständlich
Ja, da hast du vermutlich recht, aber wie gesagt: das ist nur ein kleiner test, die Optimierungen kommen dann zu einem späteren
Zeitpunkt, aber Danke, jetzt weiß ich wenigstens wie ich das Ganze angehen kann.Gruß
Cyax
-
Cyax schrieb:
Perfekt, vielen Dank, so etwas hab ich gesucht.
Was std::pow angeht, magst du vielleicht recht haben, allerdings kenne ich keine andere Funktion um Potenzen zu berechnen.
Immer mit base*=base in einer for-Schleife zu rechnen, ist ja auch nicht gerade die schönste Lösung...Doch! Das ist die schönste Lösung! Allein schon weil sie korrekt ist! (Floating Point liefert dir bei großen Zahlen falsche Ergebnisse) ... ansonsten schreib vielleicht noch eine
sqr()
-Funktion, mit der du quadrieren kannst - aber damit ist nicht viel gewonnen.Finnegan
-
Finnegan schrieb:
Doch! Das ist die schönste Lösung! Allein schon weil sie korrekt ist! (Floating Point liefert dir bei großen Zahlen falsche Ergebnisse) ... ansonsten schreib vielleicht noch eine sqr()-Funktion, mit der du quadrieren kannst - aber damit ist nicht viel gewonnen.
Ok alles klar, mach ich, danke
Hier mal meine Lösung (für eine eigene pow funktion):
int poW(int base, int exponent) { int result = base; if (exponent == 2){ return base * base; } if (exponent == 0){ return 1; } for (int i = 1; i < exponent; i++){ result *= base; } return result; }
Cyax
//edit: code funktioniert jetzt
-
int main() { int base = 2; for( unsigned i = 0; i < 10; ++i ) std::cout << poW( base, i ) << '\n'; }
2 4 4 256 65536 0 0 0 0 0
Echt jetzt?
-
int poW(int base, int exponent) { if(exponent == 2){ return base*=base; } for(int i = 0; i < exponent; i++){ base *= base; } return base; }
Das ist Unsinn. Vor allem Zeile 7. Du brauchst eine temporäre Variable die die ursprüngliche Basis repräsentiert. Wenn möglich Code rudimentär Testen bevor du ihn hier abschickst.
-
Das ist Unsinn. Vor allem Zeile 7. Du brauchst eine temporäre Variable die die ursprüngliche Basis repräsentiert. Wenn möglich Code rudimentär Testen bevor du ihn hier abschickst.
Ja alles klar, ich werds gleich ändern...
-
Ich verstehe deine Obsession mit der
pow()
-Funktion nicht so ganz. Du schreibst doch sowieso gerade eine (!), indem du fortgesetztes Quadrieren implementierst! (der einzige Unterschied ist, dass sie im Anschluss noch ein Modulo macht!).
Bei der darfst du ruhig für das quadrieren mit Multiplikation arbeitenDas schöne am fortgesetzten Quadrieren ist doch, dass man sich die Identität zunutze macht um das Potenzieren von auf zu drücken (wobei der Exponent ist):
...und dann nochmal das gleiche Spiel mit dem Restfaktor ... usw. bis man die ganze Potenz zusammen hat (in Schritten).
Was du jetzt machst, ist eine weiterepow()
-Funktion zu schreiben, die eben nicht das elegante quadrieren nutzt, nur um deine Quadrate auszurechnen (!).
Multiplizier' die Zahl einfach mit sich selbst um sie zu quadrieren - einfacher wirds nichtGruss,
Finnegan