Modular Exponentiation C++

cooky451

Ja, das ist tatsächlich ein Problem. Ich habe aus Spaß mal Mini-RSA für 64-bit Zahlen implementiert, und da braucht man das. (Das da ist quasi der ganze RSA Algorithmus. :D) Also kommt man selbst bei RSA-64 nicht um "BigInts" herum? Ich will ein uint128_t!

SeppJ

cooky451 schrieb:

Ja, das ist tatsächlich ein Problem. Ich habe aus Spaß mal Mini-RSA für 64-bit Zahlen implementiert, und da braucht man das. (Das da ist quasi der ganze RSA Algorithmus. :D)

Das dachte ich mir schon.

Also kommt man selbst bei RSA-64 nicht um "BigInts" herum?

Du brauchst eben einen 128 Bit Integer oder musst dich mit RSA-32 zufrieden geben. Denk auch dran, dass die Rechnung selber mit 128 Bit durchgeführt werden muss, nicht bloß die Speicherung des Zwischenergebnisses.

Ich will ein uint128_t!

Dann schreib dir einen!

cooky451

SeppJ schrieb:

Dann schreib dir einen!

Ich musste leider feststellen, dass man schöne big-ints in Standard-C++ momentan so gut wie vergessen kann. Jedenfalls konnte ich meinen Compiler nicht dazu bewegen, add-with-carry Instruktionen oÄ zu generieren. Heißt, letztlich müsste man da alles in ASM schreiben, und darauf habe ich eigentlich eher wenig Lust. (BCD halte ich bei der Größenordnung auch für eher hinderlich was die Performance angeht.)

Shade Of Mine

http://stackoverflow.com/questions/6659414/efficient-128-bit-addition-using-carry-flag

Klar ists Compilerabhaengig aber dafuer fuer jeden Compiler eigentlich relativ trivial zu machen...

knivil

google fuer gcc, nein ist nicht portabel:

__uint128_t a;

cooky451

Nutze leider VS, die haben glaube ich kein uint128.
Shade Of Mine: Also ich sehe da jetzt keine add-with-carry instruction, gucke ich nicht richtig? Sicher, das jmp ist weg, cmp macht er trotzdem unnötigerweise.

knivil

Es gibt mehr als eine Antwort. Alternativ kann auch eine der vielen Bibliotheken benutzt werden.

Generell wuerde mich eine Bibliothek interessieren, die Integer<128> oder Integer<256> als Template abstrahiert aehnlich wie std::bitset

Oooch, man findet so einiges: http://stackoverflow.com/questions/9145644/visual-c-x64-add-with-carry

volkard

knivil schrieb:

Generell wuerde mich eine Bibliothek interessieren, die Integer<128> oder Integer<256> als Template abstrahiert aehnlich wie std::bitset

Jo, die wäre fein. Zweierkomplementdarstellung und + und - macht man mit Schleifen und * per Karatsuba rekursiv. Dividieren traue ich mich nicht.

cooky451

knivil: Ja, arbitrary_integer<128/256/512/1024..> wäre cool. Aber nur, wenn das dann auch auf Machine-Words basiert und das Carry-Bit benutzt, sonst bringt mir das nichts.

knivil

Der erste Schritt bei Kryptographie sind eben BigIntegers.

cooky451

Nun ja, eher bei asymmetrischer Verschlüsselung und speziell bei RSA. Die meisten Block-Cipher inlusive AES (und damit auch (fast?) alle Hash-Funktionen und PRNGs) brauchen sowas nicht.

knivil

Vielleicht interessiert es dich: http://locklessinc.com/articles/256bit_arithmetic/ , kann man wahrscheinlich auch irgendwie mit Standard-C++ beschreiben, um den gleichen Asm-Code zu bekommen. mul128 braucht kein adc .

krümelkacker

cooky451 schrieb:

Hi,

ich suche einen Algorithmus um b^e mod n exakt (mit Integern) auszurechnen. Ich hatte diesen hier verwendet:
T result = 1;
	while (exponent != 0)
	{
		if ((exponent & 1) != 0)
			result = (result * base) % modulus;

		exponent >>= 1;
		base = (base * base);
		base %= modulus;
	}
	return result;
Das Problem dabei ist aber, dass base * base overflowen kann. Gibt es eine effiziente Möglichkeit das (ohne ASM) zu beheben?

Was du implementiert hast ist ja hier eine Variante des Square-and-Multiply-Algorithmus. So etwas ähnliches gibt es auch für die Multiplikation: Double-and-Add. Du könntest also statt base*base einfach mul(base,base,n) schreiben und mult per Double-and-Add implementieren, wobei du dann beim Verdoppeln auf aufaddieren immer das Ergebnis modulo n reduzierst.

cooky451 schrieb:

Hi,

ich suche einen Algorithmus um b^e mod n exakt (mit Integern) auszurechnen. Ich hatte diesen hier verwendet:
T result = 1;
	while (exponent != 0)
	{
		if ((exponent & 1) != 0)
			result = (result * base) % modulus;

		exponent >>= 1;
		base = (base * base);
		base %= modulus;
	}
	return result;
Das Problem dabei ist aber, dass base * base overflowen kann. Gibt es eine effiziente Möglichkeit das (ohne ASM) zu beheben?

Nimm dies: http://philzimmermann.com/EN/bnlib/index.html