一、前言

 

RSA 是目前应用最广泛的非对称加密算法，也是密码学考试、面试、工程落地必考核心。很多同学只会背公式，不会完整推导。本篇从数学原理、加密解密流程、手工例题、代码实现全方位讲透 RSA，零基础也能看懂。

 

二、RSA 核心原理

 

RSA 依赖三大数论基础：

 

1. 大质数分解困难

 

2. 欧拉函数

 

3. 模逆元运算

 

密钥生成流程

 

1. 随机选取两个大素数 p、q

2. 计算公钥模数：n = p\times q

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

4. 选取公钥指数 e（1<\varphi(n)，且互质）

 

5. 求解私钥 d：e\cdot d \equiv 1 \pmod{\varphi(n)}

加密公式

 

C = M^e \bmod n

解密公式

 

M = C^d \bmod n

三、标准手工例题（考试原题）

 

已知：p=17,q=23,e=3,M=88

1. n=17\times23=391

2. \varphi(n)=16\times22=352

3. 求解逆元得：d=235

4. 加密：C=88^3 \bmod 391=350

5. 解密：M=350^{235}\bmod391=88

完全可逆，加密解密正确。

 

四、Python 完整可运行代码

def mod_inverse(a, m):

    for i in range(1, m):

        if (a * i) % m == 1:

            return i

    return -1

 

# 1.参数初始化

p, q = 17, 23

e = 3

M = 88

 

# 2.计算公钥、欧拉值

n = p * q

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

 

# 3.求私钥d

d = mod_inverse(e, phi)

 

# 4.RSA加解密

C = pow(M, e, n)

res = pow(C, d, n)

 

print("公钥 (e,n)：",(e,n))

print("私钥 d：",d)

print("密文 C：",C)

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

五、RSA 优缺点总结

 

优点

 

• 非对称体系，密钥安全分发

 

• 可加密、可签名、可验签

 

• 理论安全性高

 

缺点

 

• 运算速度极慢

 

• 不适合加密大文件

 

六、总结

 

RSA 的核心精髓：公钥加密、私钥解密；私钥签名、公钥验签。

实际工程中不会用 RSA 加密明文，只用来加密对称密钥，也就是「RSA+AES 混合加密」。