RSA是一种广泛使用的公钥加密算法，旨在保障数据的机密性和安全性。它由Ron Rivest、Adi Shamir和Leonard Adleman于1977年发明，RSA的名字即来源于他们三人的姓氏首字母。 以下是RSA的一些关键点：
公钥加密和私钥解密
- 公钥 (Public Key)：用于加密数据，可以公开分享。
- 私钥 (Private Key)：用于解密数据，必须保密。
密钥生成
- 大素数选择：选择两个大素数 pp 和 qq。
- 计算 nn：n=p×qn=p×q，这个 nn 将是密钥的一部分。
- 计算欧拉函数 ϕ(n)ϕ(n)：ϕ(n)=(p−1)×(q−1)ϕ(n)=(p−1)×(q−1)。
- 选择公钥指数 ee：ee 与 ϕ(n)ϕ(n) 互质，且 1<e<ϕ(n)1<e<ϕ(n)。
- 计算私钥指数 dd：dd 满足 d×e≡1(modϕ(n))d×e≡1(modϕ(n))。
加密和解密过程
- 加密：使用公钥 (e,n)(e,n)，将消息 MM 转换为密文 CC：C=MemodnC=Memodn。
- 解密：使用私钥 (d,n)(d,n)，将密文 CC 转换为消息 MM：M=CdmodnM=Cdmodn。
安全性
RSA的安全性基于大整数分解的难度，即将 nn 分解为其素因子 pp 和 qq 是计算上非常困难的。这使得在没有私钥的情况下，破解RSA加密变得极为困难。
应用
RSA广泛应用于各种安全协议和系统中，例如SSL/TLS（用于保护互联网通信）、PGP（用于电子邮件加密）、以及数字签名等。
例子
假设我们选择 p=61p=61 和 q=53q=53：
- n=61×53=3233n=61×53=3233
- ϕ(n)=(61−1)×(53−1)=3120ϕ(n)=(61−1)×(53−1)=3120
- 选择 e=17e=17
- 计算 dd，使得 d×17≡1(mod3120)d×17≡1(mod3120)，结果是 d=2753d=2753
公钥是 (17,3233)(17,3233)，私钥是 (2753,3233)(2753,3233)。 如果我们要加密消息 M=123M=123：
- 加密：C=12317mod3233=855C=12317mod3233=855
- 解密：M=8552753mod3233=123M=8552753mod3233=123
这样，消息成功加密和解密。
疑问
为什么同一个文本，使用相同的公钥加密，每次得到的加密内容不一样？
RSA本身在纯形式上，对于相同的消息和公钥，每次加密产生的密文都是相同的。但为了增加安全性，防止一些特定的攻击（如已知明文攻击），现代加密标准加入了填充方案。这些填充方案使得同一个明文在多次加密时产生不同的密文。主要的填充方案包括：
- PKCS#1 v1.5 填充
这是早期广泛使用的填充方案。它通过在明文前添加随机数据来使每次加密结果不同。
- OAEP (Optimal Asymmetric Encryption Padding)
OAEP是现代RSA加密的标准填充方案。它提供了更强的安全性和防御特定攻击的方法。它的工作原理如下：
- 填充：在明文前面添加随机填充数据，确保每次加密前的输入都不同。
- 加密：对填充后的明文进行RSA加密。
具体步骤如下：
- 生成一个随机数 rr。
- 使用一个散列函数 GG 生成填充数据 G(r)G(r)。
- 将明文和填充数据结合起来。
- 使用另一个散列函数 HH 生成掩码数据 H(G(r)⊕M)H(G(r)⊕M)。
- 最终的加密数据是这些填充数据和掩码数据的结合，确保每次加密输入都不同，从而生成不同的密文。
这种填充方案确保了即使使用相同的公钥和相同的明文，每次加密生成的密文都不相同。 为什么填充方案很重要？ 填充方案的主要目的是增加随机性，防止攻击者通过观察密文模式来推断明文。没有填充的情况下，如果同一明文总是生成相同的密文，攻击者可以通过频率分析或已知明文攻击来破坏系统的安全性。
为什么私钥可以正确解密？
因为无论填充的数据是什么，私钥解密的核心是逆向公钥加密的过程。填充只是增加了一层复杂性来保证每次加密得到的密文不同，但解密过程中这层复杂性会被正确地去除。
以下是一个可能的加密、解密过程，填充方案为（OAEP）
假设原始消息 M = "Hello"，以下是更具体的步骤：
- 加密：
- 原始消息：
M = "Hello" - 随机数：
r = 42 - 生成掩码：
mask = G(42)（假设mask是一个与M长度相同的随机字符串） - 填充后的消息：
X = "Hello" ⊕ mask - 生成填充掩码：
pad = H(X) - 最终数据：
Y = 42 ⊕ pad - 组合数据：
XY=X || Y - RSA加密：
C = RSA_ENCRYPT(XY)
- 原始消息：
- 解密：
- RSA解密：
XY = RSA_DECRYPT(C) - 拆分数据：
X和Y - 恢复随机数：
r = Y ⊕ pad - 恢复原始消息：
M = X ⊕ mask
- RSA解密：
通过这种方式，RSA加密后的数据总是有特定的结构（由填充方案定义），解密时可以明确识别哪些部分是填充数据，哪些部分是原始消息。填充方案保证了每次加密得到不同的密文，同时保证了解密的正确性。
