题目
RSA 解密
【问题描述】
RSA 是一种经典的加密算法。它的基本加密过程如下。
首先生成两个质数 p, q，令 n = p · q，设 d 与 (p − 1) · (q − 1) 互质，则可 找到 e 使得 d · e 除 (p − 1) · (q − 1) 的余数为 1。
n, d, e 组成了私钥，n, d 组成了公钥。
当使用公钥加密一个整数 X 时（小于 n），计算 C = Xd mod n，则 C 是加 密后的密文。
当收到密文 C 时，可使用私钥解开，计算公式为 X = Ce mod n。 例如，当 p = 5, q = 11, d = 3 时，n = 55, e = 27。
若加密数字 24，得 243 mod 55 = 19。 解密数字 19，得 1927 mod 55 = 24。
现在你知道公钥中 n = 1001733993063167141, d = 212353，同时你截获了 别人发送的密文 C = 20190324，请问，原文是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
答案
579706994112328949
代码
1 #include<iostream> 2 #include<cmath> 3 #define ll long long 4 using namespace std; 5 ll n,d,p,q,e,k; 6 ll C,X; 7 ll get_prime(ll num){//num为符合条件的质数d 8 for(ll i=2;i<num;i++){ 9 if(num%i==0){//找到能整除的质数！ 10 return i; 11 } 12 } 13 } 14 ll phi(ll kk){ 15 ll ans=kk; 16 ll end=sqrt(kk+0.5); 17 for(ll i=2;i<=end;i++){ 18 if(kk%i==0){ 19 ans=ans/i*(i-1); 20 while(kk%i==0) kk/=i; 21 } 22 } 23 if(kk>1) ans=ans/kk*(kk-1); 24 return ans; 25 } 26 ll fast_mul(ll a,ll b,ll mod){//快速乘,将乘法变成尽可能少加的加法， 27 //比如，2*5=2+2+2+2+2=（（2+2）+（2+2））+（2） 1次乘法->4次加法->3次加法 28 ll ans=0; 29 a%=mod; 30 b%=mod; 31 while(b>0){ 32 if(b&1){ 33 ans=(ans+a)%mod; 34 } 35 b>>=1; 36 a=(a+a)%mod; 37 } 38 return ans; 39 40 } 41 ll fast_pow(ll a,ll b,ll mod){//快速幂，比挨着一个个乘快，可以减少乘法次数，比如算，a^5=((a^2)*(a^2))*a； 42 ll mul=1; 43 mul%=mod; 44 while(b>0){ 45 if(b&1){ 46 mul=fast_mul(mul,a,mod);//二进制表示的b的末尾数为1,就可以相乘 47 } 48 b>>=1;//二进制表示右移，实际上就是把末尾二进制位置去掉 49 a=fast_mul(a,a,mod);//计算每一个二次项位置处的值也就是a^(2^i),i∈Z&&i∈[0,len),len为b的二进制表示的位数， 50 //比如,b是5,那么对应二进制表示就是101，len=3 51 } 52 return mul; 53 } 54 int main(){ 55 /* 56 n=55; 57 d=3; 58 C=19; 59 */ 60 n=1001733993063167141; 61 d=212353; 62 C=20190324; 63 p=get_prime(n); 64 q=n/p; 65 k=(q-1)*(p-1); 66 ll index=phi(k); 67 //cout<<"p,q,k,index:"<<p<<","<<q<<","<<k<<" "<<index<<endl; 68 e=fast_pow(d,index-1,k); 69 //cout<<"e:"<<e<<endl; 70 X=fast_pow(C,e,n); 71 cout<<"X:"<<X<<endl; 72 73 }