这篇文章是RSA加密算法的简易版本，密钥支持不了1024位，水平有限，只是拿来作为理解RSA加密的（怕自己以后忘了）
#include<iostream> #include<cmath> using namespace std; int fast_mod(int base,int exp,int mod)//快速幂模运算 { int ans=1; while(exp!=0) { if(exp&1) { ans=(ans*base)%mod; } base=(base*base)%mod; exp=exp>>1; } return ans; } int gcd(int a,int b)//最大公约数计算 { int c=0; if(a<b)//默认a为不小于b { c=a; a=b; b=c; } c=a; a=b; b=c%b; if(b==0) return a; else return gcd(a,b); } bool test_prime_number(int num)//利用费马定理进行概率素数检验 { int k=fast_mod(2,num-1,num)+fast_mod(3,num-1,num)+ fast_mod(5,num-1,num); if(k==3) return true; else { return false; } } int count_Euler_value(int v)//计算一个数的欧拉值 { int re=v; for(int i=2;i<v;i++) { if(v%i==0) { re/=i; re*=i-1; } } return re; } int count_private_key(int e, int u)//计算私钥 ex=1(mod u) => ex+uy=1 { int count_d(int,int,int); if(gcd(e,u)!=1) { cout<<"ERROR1:公钥和模数的欧拉值不互质"<<endl; } return count_d(e,u,1); } int count_d(int a,int b,int c)//ax+by=c { if(c%(gcd(a,b))!=0) { cout<<"ERROR2:该一元二次方程无解"<<endl; return 0; } void ext_gcd(int,int,int,int &,int &); if(a<b) { int y=count_d(b,a,c); int x=(c-b*y)/a; return x; } int x,y; int s=gcd(gcd(a,b),c); a/=s; b/=s; c/=s; int k=gcd(a,b); ext_gcd(a,b,k,x,y);//结果为k的解x,y return x*(c/k); } void ext_gcd(int a,int b,int k,int & x,int &y)//扩展欧几里得算法 { int c=a/b;//a=b*c+d int d=a%b; if(d==k) { x=1; y=-1*c; return; } else if(d==0) { x=0;y=1; return; } int x1,y1; ext_gcd(b,d,k,x1,y1); x=y1; y=c*y1*-1+x1; } int main() { int p,q,public_key,private_key; cout<<"input the first prime number"<<endl; while (1) { /* code */ cin>>p; if(test_prime_number(p)) break; cout<<"It is not a prime number, please input another one"<<endl; } cout<<"input the second prime number"<<endl; while (1) { /* code */ cin>>q; if(test_prime_number(q)) break; cout<<"It is not a prime number, please input another one"<<endl; } cout<<"input a number which coprime with the product of the front two prime number "<<endl; int pq=p*q; while (1) { cin>>public_key; if(gcd(public_key,count_Euler_value(pq))!=1) { cout<<"the number isn't appropriate"<<endl; continue; } break; /* code */ } private_key=count_private_key(public_key,count_Euler_value(pq)); if(private_key<0) private_key+=count_Euler_value(pq); cout<<"---------------------------------------------------------------------------------------------------"<<endl; cout<<"The public key is ("<<p*q<<","<<public_key<<")"<<endl; cout<<"The private key is ("<<p*q<<","<<private_key<<")"<<endl; cout<<"---------------------------------------------------------------------------------------------------"<<endl; cout<<"the string for encoding "; string str; cin>>str; cout<<"the result of encoding"<<endl; int asc; char ch; int list[1000]; for(int i=0;i<str.length();i++) { asc=(char)str[i]; list[i]= fast_mod(asc,public_key,pq); cout<<list[i]<<" "; } cout<<endl; cout<<"the result of decoding"<<endl; for(int i=0;i<str.length();i++) { int k=fast_mod(list[i],private_key,pq); ch=fast_mod(list[i],private_key,pq); cout<<ch<<" "; } cout<<endl; //cout<<fast_mod(100,1000,9)<<endl<<gcd(1234,8)<<endl<<test_prime_number(111)<<endl<<; return 0; }附：由于使用int类型，所以那两个素数的乘积最好不超过4位数
结果
