Frage zur RSA-Verschlüsselung

curry-king

Hi Folks,

spiele gerade mit RSA rum und möchte das ganze mal in C proggen.

ich bin also bei der Verschlüsselung des plaintextes angekommen. Doch bei der Verschlüsselung können sehr hohe Zahlen entstehen, mit denen die Datentypen nicht zurechtkommen(Überlauf).

Wie kann ich folgendne Ausdruck vereinfachen, das er auch z. B. in einen long int typ passt

(10hoch77) mod 91 (also es geht um das 10hoch77 )

Hab da was von Kongruenzarithmetik gelesen, aber so ganz klar is mir die sache nicht.
Wär cool, wenn mir jemand helfen könnte

Danke für Eure Mühen

bash0R

camper

keine ahnung über kongruenzmathematik - aber es ist ja:

( a * b ) mod c = ( ( a mod c ) * ( b mod c ) ) mod c

man könnte also das 10^77 in hinreichend kleine faktoren zerlegen - die modulos multiplizieren und darüber noch einmal modulo laufen lassen. keine ahnung ob das effizient ist.

edit: wenn die faktoren alle gleich sind, 10^7 zum beispiel, wirds nat. noch einfacher, dann braucht man nur 2 modulos zu berechnen, gut für speed

curry-king

Mhm, das hoert sich gut an.....

Danke

Taurin

Dein Beispiel würd ich wie folgd Rechnen:

10^77 = 10 * (10^38)^2 = 10 * ( (10^19)^2 )^2 = 10 * ( (10 * (10^9)^2 )^2 )^2
= 10 * ( (10 * (10 * (10^4)^2 )^2 )^2 )^2
= 10 * ( (10 * (10 * ((10^2)^2)^2 )^2 )^2 )^2

Beim Ausrechnen jetzt immer mod 91 drauf anwenden: 10^2 = 9 mod 91
Wenn du genau hinschaust, wirst du feststellen, dass hinter den Exponenten die Binärdarstellung von 77 steckt.

Taurin

Hab eben noch mal ein bissl gebastelt:

unsigned mypow(unsigned b, unsigned exp, unsigned mod)
{
   if(exp == 0) return 1;

   unsigned tmp = mypow(b, exp >> 1, mod);

   if(exp & 1) return (b * ((tmp * tmp) % mod)) % mod;
   else        return (tmp * tmp) % mod;
}