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 发送一条消息，并确保消息的真实性和完整性：

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

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

Alice 将签名 $ S $ 和原始消息 $ M $ 一同发送给 Bob。
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、数字证书、电子邮件签名等场景.