第4章 非对称密码¶

非对称密码学（Asymmetric Cryptography），也称为公钥密码学（Public Key Cryptography），是现代密码学的重要分支。与对称密码学使用单一密钥不同，非对称密码学使用一对数学相关的密钥：公钥（Public Key）和私钥（Private Key）。这一革命性的概念解决了对称密码学中密钥分发的根本问题，为现代网络安全奠定了基础。

4.1 非对称密码的基本概念¶

4.1.1 核心思想¶

非对称密码学的核心思想是使用一对密钥，其中：

• 公钥（Public Key）：可以公开分享，用于加密数据或验证数字签名
• 私钥（Private Key）：必须严格保密，用于解密数据或生成数字签名

这两个密钥在数学上相关联，但从一个密钥推导出另一个密钥在计算上是不可行的。

4.1.2 工作原理¶

加密过程：

1. 接收方生成一对密钥（公钥和私钥）
2. 接收方公开分享公钥，保密私钥
3. 发送方使用接收方的公钥加密明文：\(C = E_{K_{pub}}(P)\)
4. 接收方使用自己的私钥解密密文：\(P = D_{K_{priv}}(C)\)

数字签名过程：

1. 发送方使用自己的私钥对消息生成签名：\(S = Sign_{K_{priv}}(M)\)
2. 接收方使用发送方的公钥验证签名：\(Verify_{K_{pub}}(M, S)\)

4.1.3 数学基础¶

非对称密码学的安全性基于某些数学难题，这些问题在正向计算时相对容易，但逆向计算时极其困难（单向函数）：

• 大整数分解问题：给定两个大质数的乘积，分解出原始质数
• 离散对数问题：在有限域中，已知 \(g^x \bmod p\)，求解 \(x\)
• 椭圆曲线离散对数问题：椭圆曲线上的离散对数变种

4.2 RSA算法¶

RSA算法由Rivest、Shamir和Adleman于1977年提出，是最著名和应用最广泛的非对称加密算法。

4.2.1 RSA密钥生成¶

步骤：

1. 选择两个大质数：选择两个不同的大质数 \(p\) 和 \(q\)（通常各为1024位或更长）
2. 计算模数：\(n = p \times q\)
3. 计算欧拉函数：\(\varphi(n) = (p-1)(q-1)\)
4. 选择公钥指数：选择整数 \(e\)，满足 \(1 < e < \varphi(n)\) 且 \(\gcd(e, \varphi(n)) = 1\)
5. 常用值：\(e = 65537 = 2^{16} + 1\)
6. 计算私钥指数：计算 \(d\)，使得 \(ed \equiv 1 \pmod{\varphi(n)}\)
7. 使用扩展欧几里得算法求解

密钥对：

• 公钥：\((n, e)\)
• 私钥：\((n, d)\)

4.2.2 RSA加密与解密¶

加密（使用公钥）： \(C = M^e \bmod n\)

解密（使用私钥）： \(M = C^d \bmod n\)

正确性证明： 根据欧拉定理，当 \(\gcd(M, n) = 1\) 时： \(M^{\varphi(n)} \equiv 1 \pmod{n}\)

由于 \(ed \equiv 1 \pmod{\varphi(n)}\)，存在整数 \(k\) 使得 \(ed = 1 + k\varphi(n)\)

因此： \(C^d = (M^e)^d = M^{ed} = M^{1+k\varphi(n)} = M \cdot (M^{\varphi(n)})^k \equiv M \cdot 1^k = M \pmod{n}\)

4.2.3 RSA数字签名¶

签名生成（使用私钥）： \(S = H(M)^d \bmod n\)

签名验证（使用公钥）： 验证 \(S^e \bmod n = H(M)\)

其中 \(H(M)\) 是消息 \(M\) 的哈希值。

4.2.4 RSA安全性¶

RSA的安全性基于大整数分解问题的困难性：

• 密钥长度：推荐使用2048位或更长的密钥
• 质数选择：\(p\) 和 \(q\) 应该长度相近但不能太接近
• 随机性：质数生成必须使用密码学安全的随机数生成器

常见攻击：

• 小指数攻击：当 \(e\) 很小且明文也很小时
• 共模攻击：多个用户使用相同的 \(n\) 但不同的 \(e\)
• 时间攻击：通过分析解密时间推断私钥信息

4.3 椭圆曲线密码学（ECC）¶

椭圆曲线密码学（Elliptic Curve Cryptography, ECC）是基于椭圆曲线数学结构的公钥密码学方法。

4.3.1 椭圆曲线基础¶

椭圆曲线方程（Weierstrass形式）： \(y^2 = x^3 + ax + b \pmod{p}\)

其中 \(4a^3 + 27b^2 \not\equiv 0 \pmod{p}\)（确保曲线非奇异）

点运算：

• 点加法：椭圆曲线上两点的加法运算
• 标量乘法：点 \(P\) 的 \(k\) 倍：\(kP = P + P + \cdots + P\)（\(k\) 次）

4.3.2 椭圆曲线离散对数问题（ECDLP）¶

给定椭圆曲线上的点 \(P\) 和 \(Q = kP\)，求解标量 \(k\) 的问题。这个问题比传统的离散对数问题更难解决。

4.3.3 椭圆曲线密钥生成¶

1. 选择椭圆曲线：选择合适的椭圆曲线和基点 \(G\)
2. 生成私钥：随机选择整数 \(d\)（\(1 < d < n\)，\(n\) 是基点的阶）
3. 计算公钥：\(Q = dG\)

密钥对： - 私钥：\(d\) - 公钥：\((E, G, Q)\)，其中 \(E\) 是椭圆曲线，\(G\) 是基点

4.3.4 ECDH密钥交换¶

椭圆曲线Diffie-Hellman（ECDH）密钥交换协议：

1. Alice选择私钥 \(d_A\)，计算公钥 \(Q_A = d_A G\)
2. Bob选择私钥 \(d_B\)，计算公钥 \(Q_B = d_B G\)
3. Alice和Bob交换公钥
4. 共享密钥：\(K = d_A Q_B = d_B Q_A = d_A d_B G\)

4.3.5 ECC优势¶

相比RSA，ECC具有以下优势：

• 密钥长度短：256位ECC密钥提供与3072位RSA相当的安全性
• 计算效率高：加密解密速度更快
• 存储空间小：适合资源受限的环境
• 带宽需求低：传输开销更小

4.4 Diffie-Hellman密钥交换¶

Diffie-Hellman密钥交换协议是第一个公开发表的公钥密码学方案，解决了密钥分发问题。

4.4.1 协议步骤¶

1. 公共参数：选择大质数 \(p\) 和生成元 \(g\)
2. Alice的操作：
3. 选择私钥 \(a\)（随机整数）
4. 计算并发送 \(A = g^a \bmod p\)
5. Bob的操作：
6. 选择私钥 \(b\)（随机整数）
7. 计算并发送 \(B = g^b \bmod p\)
8. 共享密钥计算：
9. Alice计算：\(K = B^a = (g^b)^a = g^{ab} \bmod p\)
10. Bob计算：\(K = A^b = (g^a)^b = g^{ab} \bmod p\)

4.4.2 安全性分析¶

安全性基础：离散对数问题的困难性

中间人攻击：DH协议本身不提供身份认证，容易受到中间人攻击。解决方案包括：

• 使用数字证书
• 结合身份认证机制
• 使用认证的密钥交换协议

4.5 数字签名¶

数字签名提供消息的完整性、认证性和不可否认性。

4.5.1 数字签名的特性¶

• 完整性：确保消息未被篡改
• 认证性：确认消息来源的真实性
• 不可否认性：发送方无法否认已发送的消息

4.5.2 DSA（数字签名算法）¶

DSA是基于离散对数问题的数字签名标准。

参数生成：

1. 选择质数 \(p\)（1024位或更长）和 \(q\)（160位或更长），满足 \(q | (p-1)\)
2. 选择生成元 \(g\)，满足 \(g^q \equiv 1 \pmod{p}\) 且 \(g > 1\)
3. 选择私钥 \(x\)（\(0 < x < q\)）
4. 计算公钥 \(y = g^x \bmod p\)

签名生成：

1. 选择随机数 \(k\)（\(0 < k < q\)）
2. 计算 \(r = (g^k \bmod p) \bmod q\)
3. 计算 \(s = k^{-1}(H(m) + xr) \bmod q\)
4. 签名为 \((r, s)\)

签名验证：

1. 计算 \(w = s^{-1} \bmod q\)
2. 计算 \(u_1 = H(m) \cdot w \bmod q\)
3. 计算 \(u_2 = r \cdot w \bmod q\)
4. 计算 \(v = ((g^{u_1} \cdot y^{u_2}) \bmod p) \bmod q\)
5. 验证 \(v = r\)

4.6 非对称密码的应用¶

4.6.1 HTTPS/TLS¶

HTTPS协议使用非对称密码学建立安全连接：

1. 证书验证：使用RSA或ECC验证服务器身份
2. 密钥交换：使用DH或ECDH交换会话密钥
3. 对称加密：使用交换的密钥进行后续通信加密

4.6.2 数字证书与PKI¶

公钥基础设施（PKI）包括： - 证书颁发机构（CA）：颁发和管理数字证书 - 数字证书：绑定公钥与身份信息 - 证书撤销列表（CRL）：列出已撤销的证书

4.6.3 电子邮件安全¶

• PGP/GPG：使用RSA或ECC进行邮件加密和签名
• S/MIME：基于X.509证书的邮件安全标准

4.6.4 区块链与加密货币¶

• 比特币：使用ECDSA进行交易签名
• 以太坊：使用secp256k1椭圆曲线
• 数字钱包：私钥管理和交易签名

4.7 性能比较与选择¶

4.7.1 算法性能对比¶

4.7.2 选择建议¶

RSA适用场景： - 兼容性要求高的系统 - 主要用于签名验证的场景 - 传统系统升级

ECC适用场景： - 移动设备和物联网 - 高性能要求的系统 - 带宽受限的环境 - 新系统设计

4.8 安全考虑与最佳实践¶

4.8.1 密钥管理¶

• 密钥长度：使用足够长的密钥（RSA ≥ 2048位，ECC ≥ 256位）
• 密钥存储：使用硬件安全模块（HSM）或安全存储
• 密钥轮换：定期更换密钥
• 密钥备份：安全备份关键密钥

4.8.2 实现安全¶

• 侧信道攻击防护：防止时间攻击、功耗攻击等
• 随机数生成：使用密码学安全的随机数生成器
• 填充方案：使用安全的填充方案（如OAEP）
• 哈希函数：使用安全的哈希函数（SHA-256或更强）

4.8.3 协议安全¶

• 前向安全性：使用临时密钥确保前向安全
• 身份认证：结合数字证书进行身份验证
• 重放攻击防护：使用时间戳或随机数防止重放
• 中间人攻击防护：验证证书链和主机名

结论¶

非对称密码学是现代信息安全的基石，解决了对称密码学中密钥分发的根本问题。通过RSA、ECC、DH等算法，非对称密码学为数字通信提供了加密、数字签名和密钥交换等核心功能。

随着量子计算的发展，传统的非对称密码算法面临新的挑战。后量子密码学正在兴起，基于格、编码理论、多变量等数学问题的新算法正在研发中。未来的密码学将需要在安全性、性能和实用性之间找到新的平衡。

在实际应用中，应根据具体需求选择合适的算法，注重密钥管理和实现安全，并持续关注密码学技术的发展趋势，确保系统的长期安全性。

算法对比总结¶

引文¶

• Wikipedia: Public-key cryptography
• NIST Special Publication 800-57: Recommendation for Key Management
• RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3
• FIPS 186-4: Digital Signature Standard (DSS)
• IEEE P1363: Standard Specifications for Public Key Cryptography