problema numeri molto grandi in c++

[NuclearBlast]

ciao a tutti,
ho questo problema. Ho realizzato un codice in c++ per la risoluzione dell'algoritmo di cifratura RSA, ma sbaglia a fare i calcoli perché vengono risultati molto grandi e nonostante come tipo dato ho messo unsigned long long int non funziona bene.
Qualcuno potrebbe aiutarmi a risolvere?
grazie

[-MiStO-]

supponendo che sia davvero questo l'errore, perchè non butti un occhio su qualche libreria bigint?

[Kaya]

Puoi postare il codice che hai fatto per farci un idea?

[NuclearBlast]

#include <iostream>
#include <sstream>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;

int MCD(int a, int b) {
int risultato, resto;

while (b != 0) {
resto = a % b;
a = b;
b = resto;
}
risultato = a;

return risultato;
}

int main ()
{
#define MAX 2000
int N1, N2, mcd, i, k, p, q, n, fi, r, e, d, m;
unsigned long long int tc, td;
int coprimi[MAX];
for (i=0;i<MAX;i++) {
coprimi[i]=0;} //per inizializzare a 0 il vettore MAX

// ----- VERIFICA se 2 numeri sono COPRIMI cioè MCD=1 ----------
cout << "Inserire il 1° numero: ";
cin >> N1;
cout << "Inserire il 2° numero: ";
cin >> N2;
mcd=MCD(N1,N2);
cout << "Il MCD e': " << mcd<<endl;
if (mcd==1) {cout << N1<<" e "<<N2<<" sono coprimi"<<endl;}
if (mcd!=1) {cout << N1<<" e "<<N2<<" non sono coprimi"<<endl;}
// ---------------------------


// ---- ALGORITMO RSA --------

cout << "\n\nALGORITMO RSA"<<endl;
cout << "Inserire il numero primo p: "; cin >> p;
cout << "Inserire il numero primo q: "; cin >> q;
n=p*q;
fi=(p-1)*(q-1); // formula di eulero per determinare fi(n)
cout << "n = " << p<<" * "<<q<<" = "<<n<<endl;
p--;q--;
cout << "fi(n) = " << p<<" * "<<q<<" = "<<fi<<" coprimi "<<endl;

// determina tutti i numeri comprimi di n e li inserisce nel vettore coprimi
i=1;k=0;
while (i<=n){
mcd=MCD(i,n);
if (mcd==1)
{coprimi[k]=i;
k=k+1;
}
i++;
}

cout<<"\nVisualizzo gli elementi coprimi \n";
for (i=0;i<MAX;i++) {
if (coprimi[i]!=0) cout<<coprimi[i]<<'\t';
}

cout<<"\nscegli chiave pubblica = ";
cin>>e;

//determina la chiave privata
k=0;
while (k>=0){
r=(k*fi+1)%e;
cout<<k<<"\t"<<r<<endl;
if (r==0)
{
d=(k*fi+1)/e;
k=-10;}
else k++;
}
cout<<"\nLa chiave privata = "<<d<<endl;

cout<<"\nscegli m = ";
cin>>m;
tc=pow(m,e);
tc=tc%n;

td=pow(tc,d);
td=td%n;
cout<<"messaggio cifrato = "<<tc<<endl;
cout<<"messaggio decifrato = "<<td<<endl;
return 0;
}

[misterx]

guardando qui (https://en.wikipedia.org/wiki/C_data_types) con unsigned long long int hai a disposizione 64 bit ma si può arrivare a 128, compilatore permettendo.

Dovresti identare il codice per una migliore lettura e comprensione


#include <iostream>
#include <sstream>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;

int MCD(int a, int b) {
int risultato, resto;

while (b != 0) {
resto = a % b;
a = b;
b = resto;
}
risultato = a;

return risultato;
}

int main ()
{
#define MAX 2000
int N1, N2, mcd, i, k, p, q, n, fi, r, e, d, m;
unsigned long long int tc, td;
int coprimi[MAX];
for (i=0;i<MAX;i++) {
coprimi[i]=0;} //per inizializzare a 0 il vettore MAX

// ----- VERIFICA se 2 numeri sono COPRIMI cioè MCD=1 ----------
cout << "Inserire il 1° numero: ";
cin >> N1;
cout << "Inserire il 2° numero: ";
cin >> N2;
mcd=MCD(N1,N2);
cout << "Il MCD e': " << mcd<<endl;
if (mcd==1) {cout << N1<<" e "<<N2<<" sono coprimi"<<endl;}
if (mcd!=1) {cout << N1<<" e "<<N2<<" non sono coprimi"<<endl;}
// ---------------------------


// ---- ALGORITMO RSA --------

cout << "\n\nALGORITMO RSA"<<endl;
cout << "Inserire il numero primo p: "; cin >> p;
cout << "Inserire il numero primo q: "; cin >> q;
n=p*q;
fi=(p-1)*(q-1); // formula di eulero per determinare fi(n)
cout << "n = " << p<<" * "<<q<<" = "<<n<<endl;
p--;q--;
cout << "fi(n) = " << p<<" * "<<q<<" = "<<fi<<" coprimi "<<endl;

// determina tutti i numeri comprimi di n e li inserisce nel vettore coprimi
i=1;k=0;
while (i<=n){
mcd=MCD(i,n);
if (mcd==1)
{coprimi[k]=i;
k=k+1;
}
i++;
}

cout<<"\nVisualizzo gli elementi coprimi \n";
for (i=0;i<MAX;i++) {
if (coprimi[i]!=0) cout<<coprimi[i]<<'\t';
}

cout<<"\nscegli chiave pubblica = ";
cin>>e;

//determina la chiave privata
k=0;
while (k>=0){
r=(k*fi+1)%e;
cout<<k<<"\t"<<r<<endl;
if (r==0)
{
d=(k*fi+1)/e;
k=-10;}
else k++;
}
cout<<"\nLa chiave privata = "<<d<<endl;

cout<<"\nscegli m = ";
cin>>m;
tc=pow(m,e);
tc=tc%n;

td=pow(tc,d);
td=td%n;
cout<<"messaggio cifrato = "<<tc<<endl;
cout<<"messaggio decifrato = "<<td<<endl;
return 0;
}

[NuclearBlast]

e come si fa a portare a 128 bit?

[-MiStO-]

in ogni caso, la chiave di tutto è questa
tc=pow(m,e);
tc=tc%n;

td=pow(tc,d);
td=td%n;
è qua che devi lavorare, e trovare strade alternative, come ad esempio in questo link (https://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n)

[dileoa]

Ho avuto lo stesso problema nello scrivere classi che implementano RSA e l'ho risolto usando le librerie BOOST (https://www.boost.org/) che consentono di maneggiare numeri lunghi 1048 bit o maggiori.
ADL