RSA算法科普

加密中间件的RSA算法科普

Posted by XYH on July 1, 2024

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本身在纯形式上,对于相同的消息和公钥,每次加密产生的密文都是相同的。但为了增加安全性,防止一些特定的攻击(如已知明文攻击),现代加密标准加入了填充方案。这些填充方案使得同一个明文在多次加密时产生不同的密文。主要的填充方案包括:

  1. PKCS#1 v1.5 填充

这是早期广泛使用的填充方案。它通过在明文前添加随机数据来使每次加密结果不同。

  1. OAEP (Optimal Asymmetric Encryption Padding)

OAEP是现代RSA加密的标准填充方案。它提供了更强的安全性和防御特定攻击的方法。它的工作原理如下:

  • 填充:在明文前面添加随机填充数据,确保每次加密前的输入都不同。
  • 加密:对填充后的明文进行RSA加密。

具体步骤如下:

  1. 生成一个随机数 rr。
  2. 使用一个散列函数 GG 生成填充数据 G(r)G(r)。
  3. 将明文和填充数据结合起来。
  4. 使用另一个散列函数 HH 生成掩码数据 H(G(r)⊕M)H(G(r)⊕M)。
  5. 最终的加密数据是这些填充数据和掩码数据的结合,确保每次加密输入都不同,从而生成不同的密文。

这种填充方案确保了即使使用相同的公钥和相同的明文,每次加密生成的密文都不相同。 为什么填充方案很重要? 填充方案的主要目的是增加随机性,防止攻击者通过观察密文模式来推断明文。没有填充的情况下,如果同一明文总是生成相同的密文,攻击者可以通过频率分析或已知明文攻击来破坏系统的安全性。

为什么私钥可以正确解密?

因为无论填充的数据是什么,私钥解密的核心是逆向公钥加密的过程。填充只是增加了一层复杂性来保证每次加密得到的密文不同,但解密过程中这层复杂性会被正确地去除。 以下是一个可能的加密、解密过程,填充方案为(OAEP) 假设原始消息 M = "Hello",以下是更具体的步骤:

  1. 加密
    • 原始消息: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)
  2. 解密
    • RSA解密:XY = RSA_DECRYPT(C)
    • 拆分数据:XY
    • 恢复随机数:r = Y ⊕ pad
    • 恢复原始消息:M = X ⊕ mask

通过这种方式,RSA加密后的数据总是有特定的结构(由填充方案定义),解密时可以明确识别哪些部分是填充数据,哪些部分是原始消息。填充方案保证了每次加密得到不同的密文,同时保证了解密的正确性。