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 die pow() -Funktion verwendest. Falls es sich dabei um std::pow() handelt, tut es sicherlich nicht das was du möchtest:
    Soweit ich weiss ist std::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;
    }
    

  • Mod

    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?


  • Mod

    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 arbeiten 😃

    Das schöne am fortgesetzten Quadrieren ist doch, dass man sich die Identität abac=ab+ca^b \cdot a^c = a^{b+c} zunutze macht um das Potenzieren von O(n)O(n) auf O(logn)O(\log n) zu drücken (wobei nn der Exponent ist):
    an=(((a2)2)2)...)2an2log2na^n = (((a^2)^2)^2)...)^2 \cdot a^{n - 2^{\lfloor \log_2 n \rfloor}}
    ...und dann nochmal das gleiche Spiel mit dem Restfaktor an2log2na^{n - 2^{\lfloor \log_2 n \rfloor}} ... usw. bis man die ganze Potenz zusammen hat (in O(logn)O(\log n) Schritten).
    Was du jetzt machst, ist eine weitere pow() -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 nicht 😉

    Gruss,
    Finnegan


Log in to reply