3. C++ RSA Verschlüsselung / "Fortgesetztes Quadrieren" / Riesige Zahlen

C++ RSA Verschlüsselung / "Fortgesetztes Quadrieren" / Riesige Zahlen

  • F

    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

    0
  • W

    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;
}
    0
  • 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;
}
    0
  • C

    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

    0
  • F

    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

    0
  • C

    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

    0 

  • 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?

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

    0
  • C

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

    0
  • F

    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 ab⋅ac=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)...)2⋅an−2⌊log2n⌋a^n = (((a^2)^2)^2)...)^2 \cdot a^{n - 2^{\lfloor \log_2 n \rfloor}}
    ...und dann nochmal das gleiche Spiel mit dem Restfaktor an−2⌊log2n⌋a^{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

    0
Anmelden zum Antworten