modulo von doubles // RSA Verschlüsselung

KingHobo

Hi Leute,
Ich schreibe zur zeit meine Facharbeit in Mathe über die RSA – Verschlüsselung. Ich bei ein Neuling in C++ habe jedoch ein paar Vorkenntnisse in C, deswegen seid mir nicht böse wenn ich mich ein wenig dumm anstelle .
Ich habe jetzt schon ein wenig gegoogelt und herausgefunden dass ich den Modulo von einer Double mit fmod berechnen kann, jedoch spuckt sie falsche Zahlen aus.

int encode(int k,int e,int m)
{
    double v;
    v=pow(k, e);
    v=fmod(v,m);
    return v;
}

Das ist die Funktion, welche die Zahl k, mit der Formel v=k^e mod(m) verschlüsseln soll. Die Funktion muss mit recht großen Zahlen fertig werden doch irgendwie …
Wenn ich für k=5, e=51 und m=943 einsetze spuckt die Funktion immer 560 aus, und nicht 569 wie es richtig wäre …
Wäre echt super, wenn mir jemand helfen würde und vielen dank schon mal im voraus !
LG KingHobo

KingHobo schrieb:

Das ist die Funktion, welche die Zahl k, mit der Formel v=k^e mod(m) verschlüsseln soll. Die Funktion muss mit recht großen Zahlen fertig werden doch irgendwie …

loool. Nein, double ist keine Lösung. Double bedeutet 10 signifikante Ziffern und wenn die Zahl k^e aus 11 Ziffern besteht ist die letzte immer eine 0 (wegen der Ungenauigkeit von double) und damit ist das Modulo sinnlos.

Für RSA musst du k^e mod m schon schlauer berechnen.

Ich lass mal den folgenden Wikipedia-Artikel liegen:
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Columbo

Kennst du schon modular exponentiation? Das ist ziemlich trivial.

Columbo

Einfache Implementierung:

#include <iostream>

unsigned modexp( unsigned base, unsigned exp, unsigned m )
{
	unsigned c = 1;

	for( unsigned i = 0; i != exp; ++i )
		(c *= base) %= m;

	return c;
}

int main()
{
	std::cout << modexp(5, 51, 943);
}

icarus2

Arcoth schrieb:

Einfache Implementierung:
...

Aber auch etwas ineffizient. Am besten kombiniert man Modular Exponentiation mit Square-And-Multiply.

KingHobo

Erstmal vielen dank für euren schnellen Antworten ! Ich habe es mit Exponentiation by squaring versucht doch scheint es mir so als könnte ein Integer keine so große Zahl wie 5^51 sein … oder ich habe es falsch gemacht .
Und an Arcoth, vielen dank, dein Lösungsansatz scheint da besser zu passen, da er die Zahl ja immer klein hält.
Jedoch nochmal vielen dank an euch alle !

cooky451

Der Algorithmus den man da implementieren muss wenn du Zahlen > 64 bit bzw sizeof(unsigned long long) verschlüsseln willst ist vermutlich noch nichts für dich.

Fytch

KingHobo schrieb:

Ich habe es mit Exponentiation by squaring versucht doch scheint es mir so als könnte ein Integer keine so große Zahl wie 5^51 sein … oder ich habe es falsch gemacht .

die idee ist es ja nicht dass du direkt binär potentierst (Exponentiation by squaring), sondern dass du dazwischen immer mod rechnest.

KingHobo

asfdlol schrieb:

die idee ist es ja nicht dass du direkt binär potentierst (Exponentiation by squaring), sondern dass du dazwischen immer mod rechnest.

Ja so hatte ich das auch schon verstanden, nachdem Arcoth mit Modular Exponentiation geantwortet hat und ich habe auch schon einen Algorithmus :

int ModularExponentiation(int base, int exponent,int m) {
    if (exponent==0)
        return 1;
    if (exponent==1)
        return base;
    int a=ModularExponentiation(base,exponent/2,m);
    a=a*a;
    a=a%m;
    if (exponent%2==1)
         a=a*base;
         a=a%m;
    return a;
}

cooky451 schrieb:

Der Algorithmus den man da implementieren muss wenn du Zahlen > 64 bit bzw sizeof(unsigned long long) verschlüsseln willst ist vermutlich noch nichts für dich.

Naja deswegen frage ich ja auch hier ^^

Nova900

Keine Ahnung, ob noch relevant, aber:

Integer sind oftmals 32 Bit groß, und damit kann man maximal 2 hoch 32 Zahlen (2^32) darstellen. In unseren PCs sind es meistens die Zahlen von -(2^31) bis (2^31)-1 oder halt von 0 bis (2^32)-1
Maximal bekommt man wohl im Normalfall 64 Bit, also 2^64. Sind ungefähr 18 Trillionen, also ungefähr 10^19 - auf alle Fälle zu wenig, um mit RSA arbeiten zu können.

Das interessante für das Potenzieren von großen Zahlen, wenn man dabei Modulo rechnen will, ist ja: Du kannst die Berechnung in kleinere Teile aufteilen.
7^53 mod 77 ist 35. Wie kommt man da jetzt drauf, ohne wirklich 7^53 rechnen zu müssen? Schließlich ist das viel zu groß für unsere Computer. (Jedenfalls ohne spezielle Berechnungsgrundlagen.)
Wichtig ist dabei folgende Grundlage:
7^2 mod 77 = 49
7^3 mod 77 = 35
7^4 mod 77 = 17
Und da können wir uns jetzt mal etwas angucken:
7^4 = 7^(3+1) = 7^3 * 7^1
Wenn wir jetzt die 7^3 durch (7^3 mod 77) ersetzten, kommen wir zu:
35 * 7 = 245
Das wieder modulo 77:
245 mod 77 = 14
Mh, kommt uns doch bekannt vor, oder? Stimmt, das ist das gleiche Ergebnis wie bei 7^4 mod 77.
Das deutet bereits auf den Trick hin:
x ^ (a+b) mod y = ((x^a mod y) * (x^b mod y)) mod y
Somit können wir selbst gigantische Zahlen modulo rechnen, ohne auf spezielle Bibliotheken zurückgreifen zu müssen.

7^53 mod 77 =
(7^32 mod 77 * 7^21 mod 77) mod 77 =
(7^32 mod 77 * 7^16 mod 77 * 7^5 mod 77) mod 77 =
(7^32 mod 77 * 7^16 mod 77 * 7^4 mod 77 * 7) mod 77 =
(7^32 mod 77 * 7^16 mod 77 * 14 * 7) mod 77 =
(7^32 mod 77 * 14^4 mod 77 * 14 * 7) mod 77 =
(14^8 mod 77 * 14^4 mod 77 * 14 * 7) mod 77 =
[hier eben ausrechnen, was 14^2 mod 77 ist = 42]
(42^4 mod 77 * 42^2 mod 77 * 14 * 7) mod 77 =
[Und hier eben 42^2 mod 77 = 70]
(70^2 mod 77 * 70 * 14 * 7) mod 77 =
[Und hier noch 70^2 mod 77 = 49]
(49 * 70 * 14 * 7) mod 77 =
((49*70 mod 77) * (14*7 mod 77)) mod 77 =
(42 * 21) mod 77 =
35

(Es gibt schnellere Wege, das ganze zu berechnen, erst recht für die hier verwendeten Zahlen 7, 53 und 77, aber dieses Beispiel sollte zeigen, wie es für jede Zahlenkombination funktioniert. Liegt an dir, dafür einen Weg zu finden. Die Potenzgesetze helfen da ziemlich. )

Die Erklärung von loool im ersten Teil seines Beitrags ist übrigens falsch: Die 11. Ziffer von Double ist nicht "immer 0". Zum einen, ist die Genauigkeit von Double (mit 8 Byte) bei ungefähr 16 Stellen, zum anderen werden weitere Stellen nicht einfach 0, sondern sind durch die interne Darstellung der Zahlen als Dualzahl meistens irgendwas, weil die exakte Null an späteren Stellen (im Dezimalsystem) nicht so gut darstellbar ist.

volkard

Arcoth schrieb:

Einfache Implementierung:

for( unsigned i = 0; i != exp; ++i )
		(c *= base) %= m;

for( unsigned i = 0; i != exp; ++i )
		c *= base, c %= m;