rsa.cpp

现代密码学！RSA算法

#include<math.h>
#include<iostream.h>
#include<string.h>
int f(double p)
{ double k=sqrt(p);
 for(int i=2;i<=k;i++)
	 if((int)p%i==0) break;
	 if(i>k) return 1;
     else return 0;
}
int ff(double nnn,double d)
{ int r; double temp;
  if(d>nnn)
  { temp=d;
    d=nnn;
	nnn=temp;
  }
  while(r!=0)
  { r=(int)nnn%(int)d;
    nnn=d;
	d=r;
  }
  return (int)nnn;
}
int fff(double nn,double d)
{                           
	double a,A,b,B,te,TE;
	int j=1,i,r,rr;
    A=a=nn;B=b=d;
	if(a<b)
	{
		te=a;
		a=b;
		b=te;
		TE=A;
		A=B;
		B=TE;

	}
	int aa[100];
	while(r!=0)
	{   rr=(int)a/(int)b;
	    aa[j]=rr;
		r=(int)a%(int)b;
		a=b;
		b=r;
		j++;
	}
	int s[100],t[100];
	s[0]=1;
	s[1]=0;
	t[0]=0;
	t[1]=1;
	for(i=2;i<=j-1;i++)
	{
		s[i]=s[i-2]-aa[i-1]*s[i-1];
		t[i]=t[i-2]-aa[i-1]*t[i-1];
	}
	if(t[j-1]>0)
	return t[j-1];
	else
	return (int)(A+t[j-1]);
}
int g(int x,int y,int z)      
{ 
  int	a=x;
int	m=y;
int	n=z;
int j=0,i;
  int bb[100];
  while(m>=2)
  { bb[j]=m%2;
    m=m/2;
	j++;
  }
  if(m==0)
	  j--;
  else
	  bb[j]=m;
  int k=j;
  int A[100],b[100];
  A[0]=a;
  if(bb[0]==0)
	  b[0]=1%n;
  else
	  b[0]=A[0]%n;

  for( i=1;i<=k;i++)
  {   
	  A[i]=(int)pow(A[i-1],2)%n;
      b[i]=(int)(b[i-1]*pow(A[i],bb[i]))%n;
  }
  
return b[k];
}
void main()
{ double p,q,n,nn,d;int f1,e,f2,f3,flag=1;
  cout<<"请输大素数p"<<endl;
  cout<<"p=";
  cin>>p;
  while(flag)
  { f1=f(p);                 
    if(f1)
	flag=0;
	else
	{ cout<<p<<"不是素数,请重新输入"<<endl;
	  cout<<"p=";
	  cin>>p;
	}
  }
  flag=1;
  cout<<"请输入大素数q"<<endl;
  cout<<"q=";
  cin>>q;
  while(flag)
  { f2=f(q);
    if(f2)
		flag=0;
	else
	{ cout<<q<<"不是素数,请重新输入"<<endl;
	  cin>>q;
	}
  }
  n=p*q;nn=(p-1)*(q-1);
  cout<<"所以"<<"p*q="<<n<<"    "<<"(p-1)*(q-1)="<<nn<<endl;
  cout<<"请随即输入整数d"<<endl;
  cout<<"d=";
  cin>>d;
  flag=1;
  while(flag)
  {  f3=ff(nn,d);           
	if(f3!=1)
    { cout<<"d不符合要求，请重新输入"<<endl;
    cout<<"d=";
	cin>>d; }
   else
	 flag=0;
  }

e=fff(nn,d);
cout<<d<<"的逆元是"<<e<<endl; 
int L;
cout<<"请为明文动态分配空间"<<endl;
cout<<"L=";
cin>>L;
char *mingwen=new char[L+1];
int *miwen=new int[L+1];
cout<<"请输入明文"<<endl;
cin>>mingwen;
int len=strlen(mingwen);

cout<<"密文是"<<endl;
for(int i=0;i<=len-1;i++)
{cout<<g(mingwen[i],e,n)<<" ";
miwen[i]=g(mingwen[i],e,n);
}
cout<<endl;
cout<<"下面的内容将密文转化为明文"<<endl;

for( i=0;i<=len-1;i++)
cout<<(char)g(miwen[i],d,n);
cout<<endl;
delete []mingwen;
delete []miwen;
}