这个题应该是填空题中最难的一个了。

思路很简单，但是你需要一点python的基础

讲一下本题的思路。

首先我们要对公钥中的n进行质因子分解，得到p,q。然后根据 d * e %((p - 1) * (q - 1) == 1和扩展欧几里得

求出e。

RSA是一种不可逆的加密方法，不可逆的原因是公钥特别大，对它分解质因子时间上会很长，普通计算机大概是

10年左右，量子计算机一星期就可以了，基本不可能在常数时间分解出来；

本题能做的原因是公钥n特别小(在RSA中，1e18已经算特别小）

1.首先我们要对n进行分解质因数

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define mmset(a,b) memset(a,b,sizeof(a))  
#define UI64d unsigned __int64
UI64d FastPower(UI64d a , UI64d k);	
UI64d MOD = 1001733993063167141;



int main()
{
	UI64d res = 1001733993063167141;
	for(int i= 2; i * i < res; i++)
	{
		while(res % i == 0 && res != 1) 
		{
			printf("%I64d %I64d\n",i,res / i);
			res /= i;
		}
	}
		
	
	return 0;
}

可得p = 891234941, q = 1123984201;

2.求解e

令 sum = (p-1) * (q-1) = 1001733991047948000;

那么可得d * e % sum == 1, 这是一个典型的求解ax=c(mod b)问题。

也就是e*d =1(mod sum)，我们可以用扩展欧几里得算法来求解

为防止溢出，我用的是python写的


def computeD(fn, d):
    (x, y, r) = exGCD(fn, d)
   
    if y < 0:
        return fn + y
    return y
 
def exGCD(a, b):

    if b == 0:
        return (1, 0, a)
  
    x1 = 1
    y1 = 0

    x2 = 0
    y2 = 1
    while b != 0:
        q = a / b
    
        r = a % b
        a = b
        b = r
   
        x = x1 - q*x2
        x1 = x2
        x2 = x
   
        y = y1 - q*y2
        y1 = y2
        y2 = y
    return(x1, y1, a)
 
p = 891234941
q = 1123984201
d = 212353
 
sum = (p - 1) * (q - 1)
 
e = computeD(sum, d)
print e

e = 823816093931522017;

3.已知C,e,n,求解X = C^e mod n

   X是原文。

这一步思路很简单，快速幂就行了，但是我用c++写溢出了，只能用python

MOD = 1001733993063167141
def FastPower(a,k):
    res = a
    ans = 1
    while k != 0:
        if (k % 2) != 0:
            ans = (ans % MOD) * (res % MOD) % MOD
        res = (res % MOD) * (res % MOD) % MOD
        k = k / 2
    return ans
a = 20190324
k = 823816093931522017
res = FastPower(a1,k1)
print(res)

最终答案为579706994112328949。

我们可以把这个明文带去求密文的过程验证一下看写的对不对

得到密文20190320与题目一致，说明我们没写错