2019年蓝桥杯软件类省赛（软件类）C/C++大学A组第5题 “RSA解密”，题目链接：

http://oj.ecustacm.cn/problem.php?id=1456

*本文内容由倪文迪（华东理工大学计算机系软件192班）和罗勇军老师提供。

01

题目描述

仍然是填空。

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 e mod n。

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

若加密数字 24，得 24 3 mod 55 = 19。

解密数字 19，得 19 2 7 mod 55 = 24。

02

题解

1

求p、q

1

●

C++代码

执行实际约十秒。

//大概10秒

展开全文

# includebits/stdc++.h

# definell long long

usingnamespacestd;

intmain{

ll n = 1001733993063167141;

ll k= sqrt(n);

for(ll i = 2; i k; i++)

if(n % i == 0)

cout i " " n / i endl;

return0;

}

2

●

python代码

竟然要几分钟！Python在做循环的时候失去了威力。

网上有大量吐槽Python的** for循环慢**的帖子。

from math import*

n = 1001733993063167141

k = int(sqrt(n))

fori in range( 2,k):

ifn%i == 0:

print(i,n //i)

2

求e

这时候要用到真正的大数了。c++的64位long long不够用，虽然有_int128，但是有些编译器不支持。

n = 1001733993063167141

d = 212353

p=891234941

q=1123984201

tmp = (p - 1) * (q - 1)

print(tmp)

fori inrange(2,n+1):

now = i * tmp + 1

if(now % d == 0):

print(now // d) #打印e

break#有很多e，求第一个就行了

3

求X = C e mod n

原来，本题是考了一个快速幂。还是用Python吧：

def qpow( a, b, mod):

ret= 1

whileb:

if( b 1):

ret= ret* a% mod

a= a* a% mod

b= 1

returnret

n = 1001733993063167141

e= 823816093931522017#试试其他的 e

C = 20190324

print(qpow(C, e,n)) # 579706994112328949

03

快速幂

快速幂的原理，在《算法竞赛入门到进阶》156页做了清晰简明的解释。大家可能没有这本书，这里贴图：

04

参考书籍