大家好，又见面了，我是你们的朋友全栈君。

RSA加密算法c++实现

先码个代码：

/************************************************************************* > File Name: RSA.cpp > Author: YB > E-mail: 1348756432@qq.com > Created Time: 2019年03月05日 星期二 ************************************************************************/ #include<bits/stdc++.h> using namespace std; int Euler(int n)//欧拉函数 求1到n中有多少个整数与n互质 { int rs=1; for(int i=2;i*i<=n;i++) { if(n%i==0) { rs*=(i-1); n/=i; while(n%i==0) { rs*=(i-1); n/=i; } } } if(n>1) rs*=(n-1); return rs; } int gcd(int a,int b)//求a,b的最大公约数 { if(b==0) return a; return gcd(b,a%b); } int check(int n)//判断n是不是素数 { if(n==1) return 0; if(n==2) return 1; for(int i=3;i*i<=n;i=i+2) { if(n%i==0) return 0; } return 1; } int gnerating_primes(int n)//产生小于等于n的第一个素数 { if(n%2==0) n--; for(int i=n;i>1;i=i-2) { if(check(i)==1) return i; } return -1;//表示没有小于等于n的素数 } int multiplicative_inverse_element(int a,int r)//求a对于r的乘法逆元 { int rs=1; if(check(r)==1)//r是素数 采用费马小定理  { for(int i=1;i<=r-2;i++) rs*=a,rs%=r; }else //r不是素数，采用欧拉定理的推论  { int k=Euler(r)-1; for(int i=1;i<=k;i++) rs*=a,rs%=r; } return rs; } int get_pk(int w) { int pk=2; for(pk=2;pk<w;pk++) { if(gcd(w,pk)==1) return pk; } return pk; } int square_multiplication(int x,int c,int r)//平方乘算法，x的c次方%r { string str=""; while(c) { str=(char)(c%2+'0')+str; c/=2; } int rs=x; int l=str.length(); for(int i=1;i<l;i++) { if(str[i]=='0') rs=((rs%r)*(rs%r))%r; else rs=(((rs%r)*(rs%r))%r*x)%r; } return rs; } int main() { int p=47; int q=61; int r=p*q;//公开模数 cout<<"r="<<r<<endl; int w=Euler(r);//1到r中与r互质的数的个数 //求得公钥 int pk=get_pk(w); //pk=167; cout<<"公钥(pk,r):("<<pk<<","<<r<<")"<<endl; //求得私钥 int sk=multiplicative_inverse_element(pk,w); cout<<"私钥(sk,r):("<<sk<<","<<r<<")"<<endl; int M=123456789;//明文 int K=3;//K位一组 int temp=1; for(int k=1;k<=K;k++) temp*=10; cout<<"密文:"; for(int i=1;i<=K;i++) { cout<<square_multiplication(M%temp,pk,r)<<" "; M/=temp; } cout<<endl; return 0; }