✔ Potenz mit unsigned __int64, RSA-Verschlüsselung

[Aiju]

Ich schreibe im Moment ein Programm zur Verschlüsselung mit RSA. (Nun ja eigentlich test ich erstmal die rsa-verschlüsselung aus)
Und da hab ich ein Prob: Zum Verschlüsseln muss ich fmod(pow(m, e), n) rechnen
m = 88 = 'X', e = 7, n = 187. Dass klappt ja noch, aber zum Entschlüsseln muss ich fmod(pow(c, d), n) rechnen und da hackts! (c = 11, d = 23, n = 187)
Hier erst mal der ganze Code des Experiments:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream>
#include <conio>
#include <math>
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
typedef unsigned long int ulong;
typedef unsigned __int64 rsatyp;
rsatyp power(rsatyp x, rsatyp y)
{
rsatyp z = x;
for(rsatyp i=0;i<y;i++)
 z *= z;
return z;
}


rsatyp rest(rsatyp x, rsatyp y)
{
long double z = (x * 1.0) / (y * 1.0);
z -= (rsatyp)z;
rsatyp r = z * y;
return r;
}


int main(int argc, char* argv[])
{
        using namespace std;
        rsatyp p = 11, q = 17, n = p * q, m = 'X', d, e = 7, c;
        c = fmod(pow(m, e), n);
        cout << "Verschlüsselte Botschaft: " << c << endl;
        for(d=1;;d++)
        {
         rsatyp g = (p-1) * (q-1);
         rsatyp x = (d * 7) % g;
         if(x == 1)
          break;
        }
        m = rest((rsatyp)pow(c, d), n);
        cout << "Entschlüsselte Botschaft: " << m << endl;
        getch();
        return 0;
}
//---------------------------------------------------------------------------

Wenn irgendwer den Code bzw. das Verschlüsselungsverfahren nicht kapiert, soll er ne Frage posten!
Mit PHP hab ich es schon hingekriegt: http://profjulius.cjb.cc
(n=187, e=7, p=11, q=17 o. was Anderes(bis auf n müssen das aber primzahlen sein) und k=Zahl die Verschlüsselt werden soll, c=Zahl die Entschlüsselt werden soll)
Weiß jemand wo der Fehler liegt?
EDIT: die vcl.h ist unwichtig

 

[Aiju]

Die Addresse (vom PHP-Programm) hat sich geändert: http://profjulius.cjb.cc/rsa

 

[Beichtpfarrer]

rsatyp power(rsatyp x, rsatyp y)
{
rsatyp z = x;
for(rsatyp i=0;i<y;i++)
 z *= z;
return z;
}

Ich versteh, zwar nicht, was du machst ( ), aber falls du hier x hoch y rechnen willst, ist die Schleife falsch, es müsste darin z*=x; heißen und z mit 1, nicht x, initialisiert werden müssen.
Falls der Teil so gewollt ist, wie er gerade ist, melde dich einfach nochmal, dann denke ich erst über den Rest nach, sonst würd ich ja was unnötiges tun.... (denn ich hab bisher nur den Code der ersten Funktion gelesen )

Mfg

 

[Aiju]

ich komme dabei auf 65 und nicht auf 88
hier erst mal das rsa verfahren:
1. Suche dir drei Primzahlen p,q und e, hier 11, 17, 7
2. berechne n = p*q, m = (p-1)*(q-1),
3. überlege d, 7*d = 1 (mod m)
4. chiffrieren: rechne k(klartext) hoch e (mod n)
5. dechiffrieren: rechne c hoch d (mod n)
ich habe andere namen benutzt (m statt k)

 

[rockbaer]

Hi,

Zu deiner Power Funktion (die du aber scheinbar nicht benutzt, sonder mit der pow() Funktion
aus der math.h ersetzt hast, und die folglich bei pow(11, 23) ein korrektes Resultat bringt):

for(rsatyp i=0;i<y-1;i++)
z *= x;

so ist die Berechnung korrekt, das bringt dir aber nicht viel, weil du den rsatyp als unsigned __int64
definest, und die Berechnung "11 hoch 23" sprengt bei weitem den Rahmen einer 64bit Zahl, du kommst
hin wenn du den rsatyp als long double definierst..aber ok, das nur am Rande.

Deine Rest Funktion verstehe ich überhaupt nicht, wenn du z -=z; schreibst dann wird das Resultat immer 0 sein,
eine bessere Lösung wäre wohl, die rest Funktion durch dieses hier zu ersetzen:;

rsatyp rest(rsatyp x, rsatyp y)
{
rsatyp z = floor(x / y);
return x - (z * y);
}

aber das auch nur wenn du rsatyp als long double definierst, aber auch dies wird dir nicht viel bringen , da durch
die floating point division kostbare Präzision verloren geht, eine bessere Methode wäre die fmod Funktion aus der Math.h
zu benutzen, aber selbst die ist hier zu ungenau.

Meine Vermutung wieso das bei dir mit php geklappt hat, ist, dass du die bcpowmod() Funktion benutzt hast, die arbitrary
precision erlaubt.

Um das ganze unter c++ hinzubekommen , solltest du auf eine externe lib zugreifen, zb freelip oder miracl, wobei ich dir
eher miracl empfehlen kann, bekommste hier.

 

[Aiju]

Zu deiner Power Funktion (die du aber scheinbar nicht benutzt, sonder mit der pow() Funktion
aus der math.h ersetzt hast, und die folglich bei pow(11, 23) ein korrektes Resultat bringt):

Da habe ich nur was andres ausprobiert...

... Berechnung "11 hoch 23" sprengt bei weitem den Rahmen einer 64bit Zahl ...

da ist was dran...

... überhaupt nicht, wenn du z -=z; schreibst dann wird das Resultat immer 0 sein ...

ich schreibe ja nicht z -= z; sondern z -= (rsatyp)z; dadurch wird aus 1,5 0,5 aus 5,754 0,754
so hatte ich das gedacht

Meine Vermutung wieso das bei dir mit php geklappt hat, ist, dass du die bcpowmod() Funktion benutzt hast, die arbitrary
precision erlaubt.

das wollte ich nur...
und zu ner lib sag ich nein weil ich schon die vcl verwende und die schon 400-500k+ will...

 

[Aiju]

probier doch mal miracle...