RSA 加密算法解释

一、RSA 加密算法的数学原理

1. 生成密钥对

步骤如下：

• 选择两个大素数：( p ) 和 ( q )。

• 计算 ( n )：

  \[n = p \times q\]
• 计算((varphi(n)))：

\[\varphi (n) = (p-1) \times (q-1)\]

• 选择一个公钥指数 ( e )，要求 $1<e<\varphi(n)$，并且 $e$ 与 $\varphi(n)$ 互质(即 ( $gcd(e,\varphi(n))=1$) )。e 常为 65537
• 计算私钥指数 ( d )，使得：

\[d \times e \equiv 1 \pmod{\varphi (n)}\]

这意味着 ( d ) 是 ( e ) 在模 (($\varphi(n)$)) 下的乘法逆元。

• 生成密钥对：
  • 公钥（Public Key）：( (e, n) )
  • 私钥（Private Key）：( (d, n) )

2. 加密过程

假设要加密的明文为 ( M )（其中 ( M < n )）：

• 加密公式：

\[C = M^e\;mod\;n \; \text{即} \; M^e \equiv C(mod\;n)\]

• 这里，( C ) 是密文，( M ) 是明文。

3. 解密过程

使用私钥 ( (d, n) ) 对密文 ( C ) 进行解密：

• 解密公式：

\[M = C^d\;mod\;n\;即\;C^d \equiv M(mod\;n)\]

• 解密后得到原始明文 ( M )。

4. 使用中国剩余定理（CRT）加速解密

为了提高解密效率，可以使用中国剩余定理（CRT）对模 $( n = p \times q )$ 的指数运算进行加速：

• 预处理：

  \[d_p = d \bmod (p - 1), \quad d_q = d \bmod (q - 1)\] \[q_{\text{inv}} = q^{-1} \bmod p\]

• 解密:

\[\begin{cases} M \equiv m_1 \equiv C^{d_{p}} \mod p \\ M \equiv m_2 \equiv C^{d_{q}} \mod q \end{cases}\]

其中 ( p )、( q ) 是不同素数，$( n = p \cdot q )$，因此满足中国剩余定理（CRT）适用条件。

我们要构造这样的 ( M )：

\[M = m_2 + h \cdot q\]

我们希望它满足：

\[M \equiv m_1 \mod p\]

把上式代入：

\[m_2 + hq \equiv m_1 \mod p \\ \Rightarrow hq \equiv m_1 - m_2 \mod p\]

由于模运算中除法要变为乘逆元（因为 ( q ) 和 ( p ) 互素）：

\[h \equiv (m_1 - m_2) \cdot q^{-1} \mod p\]

所以：

\[h = (q^{-1} \cdot (m_1 - m_2)) \mod p\]

这正是我们所说的：

\[h = (q_{\text{inv}} \cdot (m_1 - m_2)) \mod p\]

最终我们得到合并结果：

\[M = m_2 + h \cdot q \mod n\]

二、RSA 算法中的数学原理

RSA 的安全性基于以下数学难题：

• 大整数分解问题：给定 ($n = p \times q$)，分解 ( n ) 得到 ( p ) 和 ( q ) 非常困难，尤其当 ( p ) 和 ( q ) 是非常大的素数时。
• 模幂运算和欧拉定理：

  • 根据欧拉定理：

    $$

M^{\varphi (n)} \equiv 1 \pmod{n}

$$

• 通过选择 ( d ) 和 ( e ) 满足($d \times e \equiv 1 \pmod{\varphi (n)}$)，可以确保加密和解密过程互为逆操作。

省流证明如下 (其实这个证明就是很简单的用到了指数的模逆元吧)

条件:

e: 要求 $1<e<\varphi(n)$，并且 $e$ 与 $\varphi(n)$ 互质 (即 ( $gcd(e,\varphi(n))=1$) )

d: 有如下得到:

$d \times e \equiv 1(mod\;\varphi(n))$

\[\begin{align} C = M^e\;mod\;n \; \text{即} \; M^e \equiv C(mod\;n) \tag{1} \end{align}\] \[\begin{align} M = C^d\;mod\;n\;即\;C^d \equiv M(mod\;n) \end{align} \tag{2}\]

由 1 公式左右两边进行 d 的幂次方可得 2 公式, 即:

\[\begin{align} &M^{de} \equiv C^d\equiv M(\text{mod n}) \text{即} \\ &M^{de}\equiv M(\text{mod n}) \end{align}\]

==我们想要证明为什么可以通过对密文 C 进行 d 次方就可以解密得到原文==

\[\begin{align} &M^{\varphi(n)}\equiv 1 \text{(mod n)} \\ &d\times e\equiv 1(\text{mod $\varphi(n)$}) \\ &\text{所以$\varphi(n)\mid de - 1$} \\ &\text{de - 1是$\varphi(n)的整数倍$}\\ &\text{所以}M^{de-1}\equiv 1(\text{mod n}) \\ \end{align}\]

得证！QED!

三、RSA 的实际应用场景

• 加密通信：用于加密对称密钥（如 TLS/SSL 证书交换中的密钥协商）。
• 数字签名：用于验证消息或文件的完整性和来源（如电子邮件签名、软件发布验证）。
• 身份认证：用于确保数据来自合法的发送方（如数字证书、身份验证）。

---

RSA 结合 Hash

RSA 与 Hash 算法的结合

1. 数字签名

RSA 常与 Hash 算法结合用于数字签名，以确保数据的完整性和来源的真实性。以下是流程：

• 步骤 1：对消息 ( M ) 进行 Hash 计算，得到 Hash 值 ( H (M) )。
• 步骤 2：用发送方的私钥 ( d ) 对 Hash 值进行加密，生成签名 ( S )：

\[S = H (M)^d \mod n\]

• 步骤 3：将签名 ( S ) 和消息 ( M ) 一同发送给接收方。
• 步骤 4（验证方）：
  • 接收方使用发送方的公钥 ( e ) 解密签名：

\[H' (M) = S^e \mod n\]

• 接收方再对消息 ( M ) 计算 Hash 值 ( H (M) )，并与解密得到的 ( H’ (M) ) 进行比较：
  • 如果 ( H (M) = H’ (M) )，则说明签名有效，消息未被篡改。

2. 为什么结合 Hash 算法？

• 性能优化：RSA 对大数据加密速度较慢，因此通常只对 Hash 值（而不是整个消息）进行签名。
• 数据完整性：Hash 算法能将任意长度的消息转换为固定长度的 Hash 值，且能快速检测数据篡改。
• 防止碰撞攻击：通过结合强 Hash 算法，可以确保不同的消息生成不同的 Hash 值，进一步增强安全性。

2.1 性能优化

[!TIP] 这个优化只是对消息的签名的优化，并不是说对大文件的加密的优化

• 问题：RSA 对大数据的加密和解密非常耗时，因为 RSA 的加密解密是基于大整数的模幂运算。如果直接用 RSA 对一整段消息（比如一个文件）进行加密或签名，会导致性能低下，尤其是数据量很大时。
• 解决方案：
  • 通过 Hash 算法将任意长度的消息 ( M ) 生成固定长度的 Hash 值 ( H (M) )（例如 256 位）。
  • 只对这个固定长度的 Hash 值进行 RSA 加密，而不是对整个消息加密。
  • 这样就大幅减少了计算量，提高了加密签名的速度。

示例：

• 假设我们要签名一份 1 GB 的文件，如果直接用 RSA 签名，需要处理 1 GB 的数据，这会非常耗时。
• 相反，如果先对文件使用 Hash 算法（如 SHA-256），将其压缩成一个 256 位（32 字节）的 Hash 值，再用 RSA 签名，那么只需处理 32 字节的数据，这会大大提升签名效率。

2.2 数据完整性

• 问题：我们需要确保消息在传输过程中未被篡改。直接使用 RSA 加密原始消息虽然能提供安全性，但效率低且成本高。
• 解决方案：
  • 通过 Hash 算法将消息 ( M ) 转换为固定长度的 Hash 值 ( H (M) )。
  • 任何对消息 ( M ) 的修改都会导致 Hash 值 ( H (M) ) 的改变。
  • 这意味着接收方可以轻松检测出消息是否被篡改。

示例：

• 发送方要传输消息 ( M )（例如 “Hello, World!”）。
• 发送前计算其 Hash 值 ( H (M) )，得到 ( H (M) = \text{0x1a2b3c…})。
• 发送方用自己的私钥对 ( H (M) ) 进行 RSA 签名，并将签名和消息 ( M ) 一起发送。
• 接收方收到后，重新计算消息的 Hash 值 ( H’ (M) ) 并验证签名：
  • 如果 ( H (M) = H’ (M) )，则消息未被篡改。
  • 否则，说明消息可能被修改。

2.3 防止碰撞攻击

• 问题：攻击者可能尝试构造两条不同的消息 ( $M_{1}$ ) 和 ( $M_{2}$ )，使它们产生相同的 Hash 值 ( H ($M_{1}$) = H ($M_{2}$) )。如果攻击成功，攻击者可以用合法消息 ( $M_{1}$ ) 签名，而接收方验证的却是伪造消息 ( $M_{2}$ )。
• 解决方案：
  • 使用安全的 Hash 算法（如 SHA-256、SHA-3 等）来生成 Hash 值，确保其抗碰撞性（即不同的输入产生不同的 Hash 值）。
  • 强 Hash 算法使得找到碰撞的难度极高，从而提升整体安全性。

示例：

• 假设 Alice 对一条合法消息 ($M_{1}$) 进行签名，生成($S = H (M_{1})^d\text{(mod n)}$)。
• Bob 试图找到另一条消息($M_{2}$)，使得 ($H(M_{2}=H(M_{1}))$)，从而冒充 Alice 的签名。
• 如果 Alice 使用的是强 Hash 算法（如 SHA-256），则 Bob 几乎不可能找到这样的 ($M_{2}$)。
• 因此，结合 Hash 算法后，RSA 数字签名可以有效防止碰撞攻击。

完整示例：RSA 与 Hash 算法结合的数字签名流程

假设 Alice 需要给 Bob 发送一条消息，并确保消息的真实性和完整性：

1. Alice 计算消息的 Hash 值：
   • 消息 ( M )：“Hello, Bob!”
   • 使用 Hash 算法(如 SHA-256)得到 Hash 值 ( H (M) )。
2. Alice 生成数字签名：
   • Alice 使用她的私钥 ( d ) 对 Hash 值 ( H (M) ) 进行 RSA 加密，生成签名 ( S )：

\[S = H (M)^d \mod n\]

• Alice 将签名 ( S ) 和原始消息 ( M ) 一同发送给 Bob。

1. Bob 验证签名：
   • Bob 收到消息 ( M ) 和签名 ( S ) 后，用 Alice 的公钥 ( e ) 解密签名

\[H' (M) = S^e \mod n\]

• Bob 再对收到的消息 ( M ) 重新计算Hash值 ( H (M) )。
• 如果 ( H’ (M) = H (M) )，则签名有效，消息未被篡改且确实来自 Alice。

总结

结合 Hash 算法后，RSA 加密系统在性能和安全性上得到了显著提升：

• 性能优化：只对固定长度的 Hash 值进行 RSA 运算，而不是整个消息。
• 数据完整性：任何对消息的篡改都会导致 Hash 值变化，从而被检测到。
• 防碰撞攻击：强 Hash 算法确保不同消息产生不同的 Hash 值，保护签名的安全性。

因此，RSA 和 Hash 算法的结合在现代安全通信中非常重要，如 SSL/TLS、数字证书、电子邮件签名等场景.