RSA加密算法
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\)) )。
- 计算私钥指数 ( 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 )。
二、RSA 算法中的数学原理
RSA 的安全性基于以下数学难题：
- 大整数分解问题：给定 ( n = p q )，分解 ( n ) 得到 ( p ) 和 ( q ) 非常困难，尤其当 ( p ) 和 ( q ) 是非常大的素数时。
- 模幂运算和欧拉定理：
- 根据欧拉定理： $$
M^{(n)} $$
- 通过选择 ( d ) 和 ( e ) 满足(\(d \times e \equiv 1 \pmod{\varphi (n)}\))，可以确保加密和解密过程互为逆操作。
[!TIPS] 省流证明如下:
条件:
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}) \\ \text{得证} \end{align} \]
三、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 性能优化
[!TIPS] 这个优化只是对消息的签名的优化，并不是说对大文件的加密的优化
问题：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、数字证书、电子邮件签名等场景。