题目描述

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 = X^d mod n，则 C 是加密后的密文。

当收到密文 C 时，可使用私钥解开，计算公式为 X = C^emod n。

例如，当p=5，q= 11，d= 3时，n = 55，e = 27。

若加密数字 24，得 24³ mod 55 = 19。解密数字 19，得 19²⁷mod 55=24。

现在你知道公钥中n= 1001733993063167141，d = 212353，同时你截获了别人发送的密文C= 20190324，请问，原文是多少？

解题步骤

在这里插入图片描述

//大概10秒
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ll n = 1001733993063167141;
    ll k= sqrt(n);
    for(ll i = 2 ; i < k; i++)
        if(n % i == 0)
            cout << i << " " << n / i << endl;
    return 0;
}

在这里插入图片描述

n = 1001733993063167141
d = 212353
p=891234941
q=1123984201
tmp = (p - 1) * (q - 1)
print(tmp)
for i in range(2,n+1):
    now = i * tmp + 1
    if (now % d == 0):
           print(now // d)   #打印e
           break             #有很多e，求第一个就行了

在这里插入图片描述

def fastPow(a,b,mod):
    ret = 1
    while b:
        if(b&1):
             ret = ret*a % mod
        a = a*a % mod
        b>>=1
    return ret
 
n = 1001733993063167141
e = 823816093931522017   #试试其他的e
C = 20190324
print(fastPow(C,e,n))        #579706994112328949