CTF密码学必考RSA算法｜例题完整演算过程+加密解密数学原理

一、CTF考题原题

已知RSA参数：大素数p=11，q=13，公钥e=7，密文C=32，求解明文Flag。

二、RSA核心数学公式

1. 模数计算：n=p\times q

2. 欧拉函数：\varphi(n)=(p-1)(q-1)

3. 私钥d：e\times d \equiv 1 \pmod{\varphi(n)}

4. 解密公式：M=C^d \bmod n

三、分步演算解题

1. 计算模数：n = 11\times13 = 143

2. 欧拉值：\varphi(n)=10\times12=120

3. 求解私钥d：7d mod 120 = 1，算出d=103

4. 解密运算：M = 32^{103} \bmod 143 = 45

最终明文flag：crypto{45}

四、Python代码实现RSA解密

import pow

p = 11

q = 13

e = 7

c = 32

n = p * q

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

d = pow(e,-1,phi)

m = pow(c,d,n)

print("解密明文：",m)

五、CTF考点复盘

基础RSA题型考点固定，依托欧拉逆元完成私钥求解。进阶比赛题型会利用模数分解漏洞、低指数攻击、共模攻击破解RSA，是应用密码学课程以及CTF进阶的重中之重。