[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;
}