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 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

Codice PHP:

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

[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