Day-169-非对称加密算法详解

# Day 183: 非对称加密算法详解

> 密码学系列第 3 天 | 预计阅读时间：50 分钟 | 难度：★★★★☆

---

## 清单 目录

1. [非对称加密概述](#非对称加密概述)
2. [RSA 算法详解](#rsa 算法详解)
3. [ECC 椭圆曲线密码](#ecc 椭圆曲线密码)
4. [Diffie-Hellman 密钥交换](#diffie-hellman 密钥交换)
5. [ElGamal 加密](#elgamal 加密)
6. [算法对比与选型](#算法对比与选型)
7. [后量子密码学](#后量子密码学)
8. [实战应用](#实战应用)
9. [安全实践](#安全实践)
10. [总结与思考](#总结与思考)
11. [参考资料](#参考资料)

---

## 非对称加密概述

### 基本原理

**非对称加密定义**：

```
┌─────────────────────────────────────────────────────────────┐
│              非对称加密（公钥密码）基本原理                 │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  核心概念：                                                  │
│  ├── 使用密钥对：公钥 (Public Key) + 私钥 (Private Key)    │
│  ├── 公钥：可以公开分享，用于加密或验证签名                 │
│  ├── 私钥：必须保密，用于解密或生成签名                     │
│  └── 从公钥无法（在计算上）推导私钥                         │
│                                                             │
│  加密场景：                                                  │
│  ┌─────────┐                ┌─────────┐                    │
│  │ 发送方  │                │ 接收方  │                    │
│  │         │  ① 获取公钥    │         │                    │
│  │         │◀───────────────│ 公钥    │                    │
│  │         │                │ 私钥    │                    │
│  │ 明文    │  ② 公钥加密    │         │                    │
│  │   +     │───────────────▶│         │                    │
│  │ 公钥    │     密文       │         │                    │
│  │         │                │ ③ 私钥解密 │                 │
│  │         │                │   明文   │                   │
│  └─────────┘                └─────────┘                    │
│                                                             │
│  签名场景：                                                  │
│  ┌─────────┐                ┌─────────┐                    │
│  │ 发送方  │                │ 接收方  │                    │
│  │ 私钥    │                │ 公钥    │                    │
│  │   +     │  ① 私钥签名    │   +     │                    │
│  │ 明文    │───────────────▶│ 密文    │                    │
│  │         │  密文 + 签名   │         │  ② 公钥验证        │
│  │         │                │         │  ✓ 签名有效        │
│  └─────────┘                └─────────┘                    │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 与对称加密对比

```
┌─────────────────────────────────────────────────────────────┐
│              对称加密 vs 非对称加密                         │
├──────────────────────┬──────────────────────────────────────┤
│      对称加密        │          非对称加密                  │
├──────────────────────┼──────────────────────────────────────┤
│ 单密钥（共享）       │ 密钥对（公钥 + 私钥）                │
│ 加解密速度快         │ 加解密速度慢（1000 倍差距）           │
│ 适合大数据加密       │ 适合小数据加密/密钥交换              │
│ 密钥分发困难         │ 解决密钥分发问题                     │
│ 无法实现数字签名     │ 可实现数字签名                       │
│ AES、ChaCha20        │ RSA、ECC、ElGamal                    │
│ 密钥管理：n(n-1)/2   │ 密钥管理：2n                         │
└──────────────────────┴──────────────────────────────────────┘

实际应用：
✓ 混合加密系统：非对称加密交换对称密钥，对称加密数据
✓ TLS/SSL：RSA/ECC 握手 + AES 加密
✓ PGP：RSA/ECC 签名 + AES 加密
```

### 数学基础

**非对称加密的数学难题**：

```
┌─────────────────────────────────────────────────────────────┐
│              非对称加密依赖的数学难题                       │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 大整数分解问题（RSA 基础）                               │
│     问题：给定 n = p × q（p、q 为大素数），求 p、q          │
│     难度：目前无多项式时间算法                              │
│     安全参数：2048 位及以上                                 │
│     量子威胁：Shor 算法可高效解决                           │
│                                                             │
│  2. 离散对数问题（DH、ElGamal 基础）                         │
│     问题：给定 g、p、y = g^x mod p，求 x                    │
│     难度：目前无多项式时间算法                              │
│     安全参数：2048 位及以上                                 │
│     量子威胁：Shor 算法可高效解决                           │
│                                                             │
│  3. 椭圆曲线离散对数问题（ECC 基础）                         │
│     问题：给定 P、Q = kP（椭圆曲线点乘），求 k              │
│     难度：比离散对数更难                                    │
│     安全参数：256 位（相当于 RSA 3072 位）                   │
│     量子威胁：Shor 算法可高效解决                           │
│                                                             │
│  4. 格问题（后量子密码基础）                                 │
│     问题：最短向量问题 (SVP)、学习带误差 (LWE)              │
│     难度：NP 困难问题                                       │
│     安全参数：根据具体方案                                  │
│     量子威胁：目前无已知高效量子算法                        │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

---

## RSA 算法详解

### 算法原理

**RSA 算法基础**：

```
┌─────────────────────────────────────────────────────────────┐
│                  RSA 算法原理                               │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  发明者：Ron Rivest, Adi Shamir, Leonard Adleman (1977 年) │
│  基础：大整数分解难题                                        │
│  状态：最广泛使用的非对称加密算法                            │
│                                                             │
│  密钥生成：                                                  │
│  1. 选择两个大素数 p、q（各 1024 位以上）                    │
│  2. 计算 n = p × q（模数）                                  │
│  3. 计算 φ(n) = (p-1)(q-1)（欧拉函数）                     │
│  4. 选择 e（公钥指数），通常 e = 65537                     │
│     要求：1 < e < φ(n)，gcd(e, φ(n)) = 1                  │
│  5. 计算 d（私钥指数），d = e^(-1) mod φ(n)                │
│     即：d × e ≡ 1 (mod φ(n))                               │
│  6. 公钥：(n, e)                                           │
│  7. 私钥：(n, d) 或 (p, q, d)                              │
│                                                             │
│  加密：                                                      │
│  c = m^e mod n                                             │
│  m: 明文（整数表示，0 ≤ m < n）                            │
│  c: 密文                                                    │
│                                                             │
│  解密：                                                      │
│  m = c^d mod n                                             │
│                                                             │
│  签名：                                                      │
│  s = m^d mod n（私钥签名）                                 │
│                                                             │
│  验签：                                                      │
│  m' = s^e mod n（公钥验证）                                │
│  验证：m' == m                                             │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 密钥长度与安全性

**RSA 密钥长度建议**：

```
┌─────────────────────────────────────────────────────────────┐
│              RSA 密钥长度与安全性                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1024 位：                                                   │
│  ├── 安全性：已不安全                                       │
│  ├── 分解难度：约 2^80 次运算                               │
│  ├── 状态：✗ 已淘汰（NIST 2013 年后禁用）                   │
│  └── 建议：立即升级到 2048 位以上                           │
│                                                             │
│  2048 位：                                                   │
│  ├── 安全性：目前安全                                       │
│  ├── 分解难度：约 2^112 次运算                              │
│  ├── 状态：✓ 最低要求（推荐用于兼容性）                     │
│  └── 建议：2030 年前可用                                    │
│                                                             │
│  3072 位：                                                   │
│  ├── 安全性：高安全性                                       │
│  ├── 分解难度：约 2^128 次运算                              │
│  ├── 状态：✓✓ 推荐（新系统首选）                            │
│  └── 建议：2030 年后推荐                                    │
│                                                             │
│  4096 位：                                                   │
│  ├── 安全性：最高安全                                       │
│  ├── 分解难度：约 2^140 次运算                              │
│  ├── 状态：✓ 可选（高安全需求）                             │
│  └── 建议：CA 根证书、长期密钥                              │
│                                                             │
│  性能对比（相对速度）：                                      │
│  2048 位：1.0x（基准）                                      │
│  3072 位：0.3x（慢 3 倍）                                    │
│  4096 位：0.1x（慢 10 倍）                                   │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 填充方案

**RSA 填充方案详解**：

```
┌─────────────────────────────────────────────────────────────┐
│                  RSA 填充方案                               │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  为什么需要填充？                                            │
│  ├── 防止确定性加密（相同明文产生相同密文）                 │
│  ├── 防止小指数攻击                                         │
│  ├── 防止共模攻击                                           │
│  └── 增加安全性                                             │
│                                                             │
│  PKCS#1 v1.5（传统方案）：                                   │
│  ├── 结构：0x00 || 0x02 || PS || 0x00 || M                │
│  ├── PS：至少 8 字节随机非零填充                            │
│  ├── 优点：广泛支持                                         │
│  ├── 缺点：易受 Bleichenbacher 攻击                        │
│  └── 状态：△ 可用但非首选                                   │
│                                                             │
│  OAEP（Optimal Asymmetric Encryption Padding）：            │
│  ├── 结构：使用哈希函数和掩码生成函数                       │
│  ├── 安全性：可证明安全（随机预言模型）                     │
│  ├── 优点：安全性高                                         │
│  ├── 缺点：实现复杂                                         │
│  └── 状态：✓✓ 推荐（新系统首选）                            │
│                                                             │
│  PSS（Probabilistic Signature Scheme）：                    │
│  ├── 用途：数字签名                                         │
│  ├── 安全性：可证明安全                                     │
│  ├── 优点：比 PKCS#1 v1.5 签名更安全                        │
│  └── 状态：✓✓ 推荐（新系统首选）                            │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 代码实现

**Python RSA 实现**：

```python
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP, PKCS1_v1_5
from Crypto.Signature import pss, pkcs1_15
from Crypto.Hash import SHA256
from Crypto.Random import get_random_bytes

# ============= RSA 密钥生成 =============
def rsa_keygen(bits=2048):
    """生成 RSA 密钥对"""
    key = RSA.generate(bits)
    private_key = key
    public_key = key.publickey()
    
    # 导出密钥
    pem_private = private_key.export_key()
    pem_public = public_key.export_key()
    
    return private_key, public_key, pem_private, pem_public

# ============= RSA 加密/解密（OAEP） =============
def rsa_encrypt_oaep(public_key, plaintext: bytes) -> bytes:
    """RSA-OAEP 加密"""
    cipher = PKCS1_OAEP.new(public_key, hashAlgo=SHA256)
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext

def rsa_decrypt_oaep(private_key, ciphertext: bytes) -> bytes:
    """RSA-OAEP 解密"""
    cipher = PKCS1_OAEP.new(private_key, hashAlgo=SHA256)
    plaintext = cipher.decrypt(ciphertext)
    return plaintext

# ============= RSA 签名/验签（PSS） =============
def rsa_sign_pss(private_key, message: bytes) -> bytes:
    """RSA-PSS 签名"""
    h = SHA256.new(message)
    signature = pss.new(private_key).sign(h)
    return signature

def rsa_verify_pss(public_key, message: bytes, signature: bytes) -> bool:
    """RSA-PSS 验签"""
    h = SHA256.new(message)
    try:
        pss.new(public_key).verify(h, signature)
        return True
    except (ValueError, TypeError):
        return False

# ============= 完整示例 =============
def rsa_demo():
    # 生成密钥对
    print("=== 生成 RSA-2048 密钥对 ===")
    private_key, public_key, pem_private, pem_public = rsa_keygen(2048)
    
    print(f"公钥模数位数：{public_key.n.bit_length()}")
    print(f"私钥模数位数：{private_key.n.bit_length()}")
    
    # 加密/解密
    print("\n=== RSA-OAEP 加密/解密 ===")
    plaintext = b"Secret message for RSA encryption!"
    print(f"明文：{plaintext}")
    
    ciphertext = rsa_encrypt_oaep(public_key, plaintext)
    print(f"密文：{ciphertext.hex()}")
    
    decrypted = rsa_decrypt_oaep(private_key, ciphertext)
    print(f"解密：{decrypted}")
    print(f"✓ 加密解密成功：{plaintext == decrypted}")
    
    # 签名/验签
    print("\n=== RSA-PSS 签名/验签 ===")
    message = b"Important document to sign"
    print(f"消息：{message}")
    
    signature = rsa_sign_pss(private_key, message)
    print(f"签名：{signature.hex()[:64]}...")
    
    valid = rsa_verify_pss(public_key, message, signature)
    print(f"✓ 验签结果：{valid}")
    
    # 测试篡改检测
    print("\n=== 测试篡改检测 ===")
    tampered_message = b"Tampered document"
    valid_tampered = rsa_verify_pss(public_key, tampered_message, signature)
    print(f"✓ 篡改消息验签失败：{not valid_tampered}")

if __name__ == "__main__":
    rsa_demo()
```

### 实际应用

**RSA 典型应用场景**：

```
┌─────────────────────────────────────────────────────────────┐
│                  RSA 典型应用场景                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. TLS/SSL 证书                                            │
│     ├── 服务器证书：RSA-2048/3072 签名                      │
│     ├── 密钥交换：RSA 密钥传输（TLS 1.2 及之前）            │
│     └── 趋势：逐渐被 ECC 替代                               │
│                                                             │
│  2. SSH 密钥                                                │
│     ├── SSH-RSA：传统 RSA 密钥                              │
│     ├── 推荐：RSA-4096 或 Ed25519                           │
│     └── 命令：ssh-keygen -t rsa -b 4096                    │
│                                                             │
│  3. PGP/GPG 加密                                            │
│     ├── 密钥对：RSA-4096                                   │
│     ├── 用途：邮件加密、文件签名                            │
│     └── 命令：gpg --gen-key                                │
│                                                             │
│  4. 代码签名                                                │
│     ├── 软件发布：签名验证完整性                            │
│     ├── 证书：代码签名证书                                  │
│     └── 平台：Windows Authenticode、Apple Notarization     │
│                                                             │
│  5. JWT 签名                                                │
│     ├── 算法：RS256（RSA-SHA256）                          │
│     ├── 用途：API 认证、令牌签名                            │
│     └── 库：PyJWT、jsonwebtoken                           │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

---

## ECC 椭圆曲线密码

### 算法原理

**ECC 基础概念**：

```
┌─────────────────────────────────────────────────────────────┐
│              ECC 椭圆曲线密码学基础                         │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  椭圆曲线方程（Weierstrass 形式）：                          │
│  y² = x³ + ax + b  (mod p)                                 │
│                                                             │
│  其中：                                                      │
│  ├── a, b：曲线参数                                         │
│  ├── p：素数域（或 2^m 二元域）                              │
│  ├── 4a³ + 27b² ≠ 0 (mod p)（非奇异条件）                  │
│  └── 曲线上的点构成阿贝尔群                                 │
│                                                             │
│  椭圆曲线点运算：                                            │
│  ├── 点加 P + Q：几何解释为弦切法                          │
│  ├── 点乘 kP：P + P + ... + P（k 次）                      │
│  └── 逆元 -P：关于 x 轴对称                                 │
│                                                             │
│  椭圆曲线离散对数问题（ECDLP）：                             │
│  给定 P（基点）和 Q = kP，求 k                             │
│  难度：目前最好的算法需要 O(√n) 次运算                      │
│  安全性：256 位 ECC ≈ 3072 位 RSA                           │
│                                                             │
│  常用曲线：                                                  │
│  ├── NIST 曲线：P-256、P-384、P-521                       │
│  ├── Curve25519：现代设计，性能更好                        │
│  ├── secp256k1：比特币使用                                 │
│  └── SM2：中国国密标准                                     │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 常用曲线

**ECC 曲线对比**：

```
┌─────────────────────────────────────────────────────────────┐
│                  常用 ECC 曲线对比                          │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  NIST P-256 (secp256r1)：                                   │
│  ├── 安全强度：128 位                                       │
│  ├── 密钥长度：256 位                                       │
│  ├── 签名长度：64 字节（r + s 各 32 字节）                   │
│  ├── 状态：✓ 广泛使用（TLS、证书）                         │
│  └── 注意：NIST 曲线存在潜在后门担忧                       │
│                                                             │
│  NIST P-384 (secp384r1)：                                   │
│  ├── 安全强度：192 位                                       │
│  ├── 密钥长度：384 位                                       │
│  ├── 签名长度：96 字节                                      │
│  └── 状态：✓ 高安全性需求                                  │
│                                                             │
│  Curve25519：                                               │
│  ├── 设计者：Daniel J. Bernstein (2006 年)                 │
│  ├── 安全强度：~128 位                                      │
│  ├── 密钥长度：256 位                                       │
│  ├── 特点：                                                  │
│  │   ✓ 现代设计（无 NIST 曲线问题）                         │
│  │   ✓ 高性能（比 P-256 快）                               │
│  │   ✓ 抗侧信道攻击                                        │
│  │   ✓ 实现简单                                            │
│  └── 应用：                                                  │
│      ✓ TLS 1.3（X25519 密钥交换）                           │
│      ✓ SSH（Curve25519 密钥）                              │
│      ✓ Signal 协议                                         │
│      ✓ WhatsApp                                            │
│                                                             │
│  Ed25519（Edwards 曲线）：                                  │
│  ├── 基于：Curve25519                                       │
│  ├── 用途：数字签名                                         │
│  ├── 签名长度：64 字节                                      │
│  ├── 特点：                                                  │
│  │   ✓ 确定性签名（无需随机数）                            │
│  │   ✓ 抗侧信道攻击                                        │
│  │   ✓ 高性能                                              │
│  └── 应用：SSH、GPG、加密货币                              │
│                                                             │
│  secp256k1：                                                │
│  ├── 特点：Koblitz 曲线，计算优化                           │
│  ├── 应用：比特币、以太坊                                  │
│  └── 密钥生成：私钥 → 公钥 = 私钥 × G                      │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### ECDH 密钥交换

**椭圆曲线 Diffie-Hellman**：

```
┌─────────────────────────────────────────────────────────────┐
│              ECDH 密钥交换协议                              │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  协议流程：                                                  │
│                                                             │
│  Alice                          Bob                         │
│    │                              │                         │
│    │  生成私钥 a                    │  生成私钥 b            │
│    │  计算公钥 A = aG              │  计算公钥 B = bG       │
│    │                              │                         │
│    │─────── 发送 A ──────────────▶│                         │
│    │                              │                         │
│    │◀─────── 发送 B ──────────────│                         │
│    │                              │                         │
│    │  计算共享密钥 S = aB          │  计算共享密钥 S = bA   │
│    │           = abG               │           = baG        │
│    │                              │                         │
│    │  ✓ S = abG = baG ✓          │                         │
│    │                              │                         │
│                                                             │
│  安全性：                                                    │
│  ├── 被动攻击者看到 A、B，无法计算 S = abG                 │
│  ├── 需要解决 ECDLP 问题                                    │
│  └── 前向安全：每次会话使用新密钥对                        │
│                                                             │
│  实际应用（TLS 1.3）：                                       │
│  ├── 密钥交换：X25519（Curve25519 ECDH）                   │
│  ├── 或：P-256 ECDH                                        │
│  └── 派生：HKDF 派生会话密钥                               │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 代码实现

**Python ECC 实现**：

```python
from cryptography.hazmat.primitives.asymmetric import ec, ed25519
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.backends import default_backend

# ============= ECDH 密钥交换 =============
def ecdh_key_exchange():
    """ECDH 密钥交换示例"""
    # Alice 生成密钥对
    alice_private = ec.generate_private_key(ec.SECP256R1(), default_backend())
    alice_public = alice_private.public_key()
    
    # Bob 生成密钥对
    bob_private = ec.generate_private_key(ec.SECP256R1(), default_backend())
    bob_public = bob_private.public_key()
    
    # 交换公钥并计算共享密钥
    alice_shared = alice_private.exchange(ec.ECDH(), bob_public)
    bob_shared = bob_private.exchange(ec.ECDH(), alice_public)
    
    # 验证共享密钥相同
    assert alice_shared == bob_shared
    
    print("=== ECDH 密钥交换 ===")
    print(f"Alice 公钥：{alice_public.public_numbers().x}")
    print(f"Bob 公钥：{bob_public.public_numbers().x}")
    print(f"共享密钥：{alice_shared.hex()[:32]}...")
    print(f"✓ 密钥匹配：{alice_shared == bob_shared}")
    
    return alice_shared

# ============= ECDSA 签名 =============
def ecdsa_sign_verify():
    """ECDSA 签名/验签示例"""
    # 生成密钥对
    private_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
    public_key = private_key.public_key()
    
    # 签名
    message = b"Important message to sign"
    signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))
    
    # 验签
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        valid = True
    except Exception:
        valid = False
    
    print("\n=== ECDSA 签名/验签 ===")
    print(f"消息：{message}")
    print(f"签名：{signature.hex()[:64]}...")
    print(f"✓ 验签结果：{valid}")
    
    return valid

# ============= Ed25519 签名 =============
def ed25519_sign_verify():
    """Ed25519 签名/验签示例"""
    # 生成密钥对
    private_key = ed25519.Ed25519PrivateKey.generate()
    public_key = private_key.public_key()
    
    # 签名
    message = b"Message signed with Ed25519"
    signature = private_key.sign(message)
    
    # 验签
    try:
        public_key.verify(signature, message)
        valid = True
    except Exception:
        valid = False
    
    print("\n=== Ed25519 签名/验签 ===")
    print(f"消息：{message}")
    print(f"签名：{signature.hex()}")
    print(f"✓ 验签结果：{valid}")
    
    # 测试篡改检测
    tampered = b"Tampered message"
    try:
        public_key.verify(signature, tampered)
        print("✗ 未检测到篡改")
    except Exception:
        print("✓ 检测到篡改")
    
    return valid

# ============= X25519 密钥交换 =============
def x25519_key_exchange():
    """X25519 (Curve25519) 密钥交换"""
    from cryptography.hazmat.primitives.asymmetric import x25519
    
    # 生成密钥对
    alice_private = x25519.X25519PrivateKey.generate()
    alice_public = alice_private.public_key()
    
    bob_private = x25519.X25519PrivateKey.generate()
    bob_public = bob_private.public_key()
    
    # 计算共享密钥
    alice_shared = alice_private.exchange(bob_public)
    bob_shared = bob_private.exchange(alice_public)
    
    print("\n=== X25519 密钥交换 ===")
    print(f"共享密钥：{alice_shared.hex()[:32]}...")
    print(f"✓ 密钥匹配：{alice_shared == bob_shared}")
    
    return alice_shared

if __name__ == "__main__":
    ecdh_key_exchange()
    ecdsa_sign_verify()
    ed25519_sign_verify()
    x25519_key_exchange()
```

---

## Diffie-Hellman 密钥交换

### 经典 DH

**Diffie-Hellman 协议**：

```
┌─────────────────────────────────────────────────────────────┐
│          Diffie-Hellman 密钥交换（经典 DH）                 │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  发明者：Whitfield Diffie, Martin Hellman (1976 年)         │
│  基础：离散对数问题                                          │
│  意义：第一个公钥密码协议                                   │
│                                                             │
│  协议参数：                                                  │
│  ├── p：大素数（2048 位以上）                               │
│  ├── g：生成元（通常为 2 或 5）                            │
│  └── 公开：p、g 可以公开                                    │
│                                                             │
│  协议流程：                                                  │
│                                                             │
│  Alice                          Bob                         │
│    │  选择私钥 a                     │  选择私钥 b           │
│    │  计算 A = g^a mod p            │  计算 B = g^b mod p   │
│    │                              │                         │
│    │─────── 发送 A ──────────────▶│                         │
│    │                              │                         │
│    │◀─────── 发送 B ──────────────│                         │
│    │                              │                         │
│    │  计算 S = B^a mod p          │  计算 S = A^b mod p    │
│    │           = g^(ba) mod p      │           = g^(ab) mod p│
│    │                              │                         │
│    │  ✓ S = g^(ab) = g^(ba) ✓    │                         │
│    │                              │                         │
│                                                             │
│  安全性：                                                    │
│  ├── 被动攻击者看到 p、g、A、B，无法计算 S = g^(ab)        │
│  ├── 需要解决离散对数问题                                   │
│  └── 中间人攻击：需要认证（配合数字签名）                  │
│                                                             │
│  参数建议：                                                  │
│  ├── p：至少 2048 位（推荐 3072 位）                        │
│  ├── g：2 或 5（安全素数）                                  │
│  └── 使用 RFC 3526 定义的标准群                            │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### DHE 与 ECDHE

**临时 DH 与前向安全**：

```
┌─────────────────────────────────────────────────────────────┐
│              DHE vs ECDHE（临时密钥交换）                   │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  静态 DH/RSA：                                               │
│  ├── 密钥对长期使用                                         │
│  ├── 问题：私钥泄露后，所有历史通信可解密                  │
│  └── 状态：✗ 不推荐（无前向安全）                          │
│                                                             │
│  临时 DH (DHE)：                                            │
│  ├── 每次会话生成新密钥对                                   │
│  ├── 会话结束后销毁私钥                                     │
│  ├── 优点：前向安全（私钥泄露不影响历史会话）              │
│  └── 缺点：计算开销大                                       │
│                                                             │
│  临时 ECDH (ECDHE)：                                        │
│  ├── 同 DHE，但使用椭圆曲线                                 │
│  ├── 优点：                                                  │
│  │   ✓ 前向安全                                            │
│  │   ✓ 性能更好（比 DHE 快 10 倍）                          │
│  │   ✓ 密钥更短                                            │
│  └── 状态：✓✓ TLS 1.3 强制使用                             │
│                                                             │
│  TLS 1.2 vs TLS 1.3：                                        │
│  ├── TLS 1.2：支持 RSA、DHE、ECDHE（可选）                 │
│  └── TLS 1.3：仅支持 ECDHE（强制前向安全）                 │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

---

## ElGamal 加密

### 算法原理

**ElGamal 加密系统**：

```
┌─────────────────────────────────────────────────────────────┐
│                  ElGamal 加密系统                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  发明者：Taher ElGamal (1985 年)                            │
│  基础：离散对数问题                                          │
│  特点：概率加密（相同明文产生不同密文）                     │
│                                                             │
│  密钥生成：                                                  │
│  1. 选择大素数 p                                            │
│  2. 选择生成元 g                                            │
│  3. 选择私钥 x（1 < x < p-1）                              │
│  4. 计算公钥 y = g^x mod p                                 │
│  5. 公钥：(p, g, y)                                        │
│  6. 私钥：x                                                │
│                                                             │
│  加密：                                                      │
│  1. 选择随机数 k（1 < k < p-1）                            │
│  2. 计算 c1 = g^k mod p                                    │
│  3. 计算 c2 = m × y^k mod p                                │
│  4. 密文：(c1, c2)                                         │
│                                                             │
│  解密：                                                      │
│  1. 计算 s = c1^x mod p                                    │
│  2. 计算 s^(-1) mod p（s 的模逆）                          │
│  3. 计算 m = c2 × s^(-1) mod p                             │
│                                                             │
│  特点：                                                      │
│  ✓ 概率加密（每次加密使用不同随机数 k）                    │
│  ✓ 语义安全                                                 │
│  ✓ 同态性质：E(m1) × E(m2) = E(m1 × m2)                   │
│  ✗ 密文膨胀（2 倍）                                         │
│  ✗ 较慢（相比 RSA）                                        │
│                                                             │
│  应用：                                                      │
│  ├── PGP/GPG（可选算法）                                    │
│  ├── 电子投票系统                                           │
│  └── 安全多方计算                                           │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

---

## 算法对比与选型

### 综合对比

**非对称算法全面对比**：

```
┌─────────────────────────────────────────────────────────────┐
│              非对称加密算法综合对比                         │
├──────────────┬──────────────┬──────────────┬───────────────┤
│     特性     │     RSA      │     ECC      │    DH/ECDH    │
├──────────────┼──────────────┼──────────────┼───────────────┤
│  数学基础    │ 整数分解     │ 椭圆曲线     │ 离散对数      │
│  密钥长度    │ 2048-4096 位  │ 256-521 位   │ 2048-3072 位   │
│  安全性      │ 高           │ 高           │ 高            │
│  加密速度    │ 慢           │ 快           │ 中            │
│  解密速度    │ 慢           │ 快           │ N/A           │
│  签名速度    │ 慢           │ 快           │ N/A           │
│  验签速度    │ 快           │ 慢           │ N/A           │
│  密钥交换    │ 不直接支持   │ 支持 (ECDH)  │ 主要用途      │
│  数字签名    │ 支持 (RSA)   │ 支持 (ECDSA) │ 不直接支持    │
│  密文大小    │ 大（256 字节） │ 小（64 字节） │ N/A          │
│  带宽占用    │ 大           │ 小           │ 中            │
│  计算资源    │ 高           │ 低           │ 中            │
│  移动友好    │ 一般         │ 优秀         │ 良好          │
│  兼容性      │ 优秀         │ 良好         │ 优秀          │
│  量子威胁    │ 高（Shor）   │ 高（Shor）   │ 高（Shor）    │
└──────────────┴──────────────┴──────────────┴───────────────┘
```

### 选型指南

```
┌─────────────────────────────────────────────────────────────┐
│                  非对称算法选型指南                         │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  场景 1: TLS/HTTPS                                          │
│  首选：ECDHE + ECDSA（P-256 或 X25519）                    │
│  备选：ECDHE + RSA-2048                                    │
│  理由：前向安全、高性能、小带宽                            │
│                                                             │
│  场景 2: SSH 密钥                                            │
│  首选：Ed25519                                             │
│  备选：ECDSA P-256                                         │
│  备选：RSA-4096（兼容性）                                  │
│  理由：Ed25519 性能最好、安全性高                          │
│                                                             │
│  场景 3: 代码/文档签名                                      │
│  首选：RSA-3072/4096                                       │
│  备选：ECDSA P-384                                         │
│  理由：广泛支持、长期验证需求                              │
│                                                             │
│  场景 4: JWT 令牌                                            │
│  首选：RS256（RSA-SHA256）                                 │
│  备选：ES256（ECDSA-SHA256）                               │
│  理由：标准支持好、库成熟                                  │
│                                                             │
│  场景 5: 加密邮件（PGP）                                    │
│  首选：RSA-4096 或 Ed25519                                 │
│  理由：长期安全、广泛支持                                  │
│                                                             │
│  场景 6: 区块链/加密货币                                    │
│  首选：secp256k1 ECDSA（比特币）                           │
│  首选：Ed25519（部分新链）                                 │
│  理由：行业标准、生态成熟                                  │
│                                                             │
│  场景 7: 移动应用                                            │
│  首选：X25519 + Ed25519                                    │
│  理由：低功耗、高性能、小密钥                              │
│                                                             │
│  场景 8: 中国合规项目                                        │
│  首选：SM2（国密椭圆曲线）                                 │
│  理由：符合国密标准                                        │
│                                                             │
│  通用建议：                                                  │
│  ✓ 新系统：优先 ECC（Ed25519/X25519）                      │
│  ✓ 兼容旧系统：RSA-3072                                    │
│  ✓ 长期密钥：RSA-4096 或 ECC P-384                         │
│  ✓ 前向安全：必须使用临时密钥（DHE/ECDHE）                 │
│  ✗ 避免：RSA-1024、DSA、静态 DH                           │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

---

## 后量子密码学

### 量子威胁

**量子计算对密码学的威胁**：

```
┌─────────────────────────────────────────────────────────────┐
│              量子计算对密码学的威胁                         │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Shor 算法（1994 年）：                                       │
│  ├── 威胁：可高效解决整数分解、离散对数问题                 │
│  ├── 影响：RSA、ECC、DH 完全破解                            │
│  ├── 要求：需要足够大的量子计算机                           │
│  └── 现状：目前量子计算机规模不足（~100 量子比特）          │
│                                                             │
│  Grover 算法（1996 年）：                                     │
│  ├── 威胁：二次加速暴力搜索                                 │
│  ├── 影响：对称加密强度减半                                 │
│  ├── AES-128 → 64 位安全（不安全）                         │
│  ├── AES-256 → 128 位安全（仍安全）                        │
│  └── SHA-256 → 128 位安全（仍安全）                        │
│                                                             │
│  时间线预测：                                                │
│  ├── 2025-2030：中型量子计算机（数百量子比特）             │
│  ├── 2030-2035：大型量子计算机（数千量子比特）             │
│  ├── 2035-2040：容错量子计算机（百万量子比特）             │
│  └── 2040+：可破解 RSA-2048 的量子计算机                    │
│                                                             │
│  应对策略：                                                  │
│  ├── 短期：增加密钥长度（RSA-4096、AES-256）               │
│  ├── 中期：迁移到后量子密码算法                             │
│  └── 长期：量子密钥分发（QKD）                              │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 后量子密码算法

**NIST 后量子密码标准化**：

```
┌─────────────────────────────────────────────────────────────┐
│              NIST 后量子密码标准化（2022-2024）             │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  入选算法（第 3 轮）：                                       │
│                                                             │
│  1. CRYSTALS-Kyber（KEM）                                   │
│     ├── 类型：基于格（Module-LWE）                         │
│     ├── 用途：密钥封装/密钥交换                            │
│     ├── 密钥大小：公钥 800 字节，私钥 1600 字节             │
│     ├── 密文大小：768 字节                                 │
│     └── 状态：✓ NIST 推荐（2024 年标准化）                 │
│                                                             │
│  2. CRYSTALS-Dilithium（签名）                              │
│     ├── 类型：基于格（Module-LWE）                         │
│     ├── 用途：数字签名                                     │
│     ├── 密钥大小：公钥 1312 字节，私钥 2528 字节            │
│     ├── 签名大小：2420 字节                                │
│     └── 状态：✓✓ NIST 首选（2024 年标准化）                │
│                                                             │
│  3. FALCON（签名）                                          │
│     ├── 类型：基于格（NTRU 格）                             │
│     ├── 用途：数字签名（小签名）                           │
│     ├── 密钥大小：公钥 897 字节，私钥 1280 字节             │
│     ├── 签名大小：666 字节                                 │
│     └── 状态：✓ NIST 推荐（2024 年标准化）                 │
│                                                             │
│  4. SPHINCS+（签名）                                        │
│     ├── 类型：基于哈希                                     │
│     ├── 用途：数字签名（保守选择）                         │
│     ├── 密钥大小：公钥 32 字节，私钥 64 字节                │
│     ├── 签名大小：8000-49000 字节                          │
│     └── 状态：✓ 备选（不同数学基础）                       │
│                                                             │
│  其他候选算法：                                              │
│  ├── BIKE、HQC（基于编码）                                  │
│  ├── SIKE（基于超奇异同源，已被攻破）                      │
│  └── ...                                                   │
│                                                             │
│  迁移挑战：                                                  │
│  ├── 密钥/签名尺寸大（10-100 倍于 ECC）                    │
│  ├── 性能开销（计算慢）                                     │
│  ├── 兼容性（需要新库、新协议）                             │
│  └── 混合部署（传统 + 后量子过渡期）                        │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 混合方案

**传统 + 后量子混合方案**：

```
┌─────────────────────────────────────────────────────────────┐
│              传统 + 后量子混合方案                          │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  为什么需要混合？                                            │
│  ├── 后量子算法新，可能存在未发现漏洞                       │
│  ├── 传统算法成熟，提供安全保障                             │
│  ├── 平滑过渡，兼容旧系统                                   │
│  └── 双重保护，即使一种被攻破仍安全                        │
│                                                             │
│  混合密钥交换：                                              │
│  ├── ECDH + Kyber                                          │
│  ├── 共享密钥 = KDF(ECDH_shared || Kyber_shared)          │
│  └── 即使一种被攻破，另一种仍保护                          │
│                                                             │
│  混合签名：                                                  │
│  ├── ECDSA + Dilithium                                     │
│  ├── 签名 = (ECDSA_sig, Dilithium_sig)                    │
│  └── 验证时需两种签名都有效                                │
│                                                             │
│  实际应用：                                                  │
│  ├── Cloudflare：ECDH + Kyber（实验性）                    │
│  ├── Google Chrome：X25519 + Kyber-768                     │
│  ├── Apple：iMessage PQ3 协议                              │
│  └── Signal：PQXDH 协议                                    │
│                                                             │
│  迁移时间线：                                                │
│  ├── 2024-2025：实验部署                                    │
│  ├── 2025-2028：混合部署                                    │
│  ├── 2028-2035：逐步淘汰传统算法                            │
│  └── 2035+：纯后量子密码                                    │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

---

## 实战应用

### TLS 握手

**TLS 1.3 握手流程**：

```
┌─────────────────────────────────────────────────────────────┐
│                  TLS 1.3 握手流程                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Client                          Server                     │
│    │                              │                         │
│    │──── ClientHello ────────────▶│  密码套件、密钥共享     │
│    │  (X25519 公钥)                │  (X25519 公钥)          │
│    │                              │                         │
│    │◀────── ServerHello ──────────│  选择密码套件          │
│    │  (X25519 公钥)                │  密钥共享              │
│    │                              │                         │
│    │◀────── Certificate ──────────│  服务器证书            │
│    │                              │                         │
│    │◀────── CertificateVerify ────│  签名验证              │
│    │                              │                         │
│    │◀────── Finished ─────────────│  握手完成              │
│    │                              │                         │
│    │──── Finished ───────────────▶│  握手完成              │
│    │                              │                         │
│    │◀══════ 加密通信 ════════════▶│  应用数据              │
│    │                              │                         │
│                                                             │
│  密钥派生：                                                  │
│  1. ECDH 交换：shared_secret = X25519(client, server)      │
│  2. HKDF 派生：                                             │
│     ├── early_secret                                      │
│     ├── handshake_secret → 握手密钥                        │
│     └── master_secret → 应用密钥                          │
│                                                             │
│  密码套件（TLS 1.3）：                                       │
│  ├── TLS_AES_128_GCM_SHA256                               │
│  ├── TLS_AES_256_GCM_SHA384                               │
│  └── TLS_CHACHA20_POLY1305_SHA256                         │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### JWT 签名

**JWT 非对称签名示例**：

```python
import jwt
from cryptography.hazmat.primitives.asymmetric import rsa, ec
from cryptography.hazmat.backends import default_backend

# ============= RSA 签名 JWT =============
def jwt_rsa_example():
    """使用 RSA 签名 JWT"""
    # 生成 RSA 密钥对
    private_key = rsa.generate_private_key(
        public_exponent=65537,
        key_size=2048,
        backend=default_backend()
    )
    public_key = private_key.public_key()
    
    # 导出 PEM 格式
    pem_private = private_key.private_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PrivateFormat.PKCS8,
        encryption_algorithm=serialization.NoEncryption()
    )
    pem_public = public_key.public_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PublicFormat.SubjectPublicKeyInfo
    )
    
    # 创建 JWT（RS256 = RSA-SHA256）
    payload = {
        'user_id': 123,
        'username': 'alice',
        'exp': 3600  # 1 小时过期
    }
    
    token = jwt.encode(payload, pem_private, algorithm='RS256')
    print(f"JWT Token: {token[:50]}...")
    
    # 验证 JWT
    try:
        decoded = jwt.decode(token, pem_public, algorithms=['RS256'])
        print(f"✓ 验证成功：{decoded}")
    except jwt.ExpiredSignatureError:
        print("✗ Token 已过期")
    except jwt.InvalidSignatureError:
        print("✗ 签名无效")

# ============= ECDSA 签名 JWT =============
def jwt_ecdsa_example():
    """使用 ECDSA 签名 JWT"""
    # 生成 EC 密钥对
    private_key = ec.generate_private_key(
        ec.SECP256R1(),
        backend=default_backend()
    )
    public_key = private_key.public_key()
    
    # 导出 PEM
    pem_private = private_key.private_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PrivateFormat.PKCS8,
        encryption_algorithm=serialization.NoEncryption()
    )
    pem_public = public_key.public_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PublicFormat.SubjectPublicKeyInfo
    )
    
    # 创建 JWT（ES256 = ECDSA-SHA256）
    payload = {
        'user_id': 456,
        'username': 'bob',
        'exp': 3600
    }
    
    token = jwt.encode(payload, pem_private, algorithm='ES256')
    print(f"JWT Token: {token[:50]}...")
    
    # 验证 JWT
    try:
        decoded = jwt.decode(token, pem_public, algorithms=['ES256'])
        print(f"✓ 验证成功：{decoded}")
    except Exception as e:
        print(f"✗ 验证失败：{e}")

if __name__ == "__main__":
    jwt_rsa_example()
    jwt_ecdsa_example()
```

---

## 安全实践

### 最佳实践

```
┌─────────────────────────────────────────────────────────────┐
│              非对称加密安全实践                             │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  ✓ 应该做的                                                 │
│  ├── 使用足够长的密钥（RSA-3072+、ECC-256+）               │
│  ├── 使用安全的填充方案（OAEP、PSS）                       │
│  ├── 使用前向安全密钥交换（ECDHE）                         │
│  ├── 使用成熟的密码学库                                     │
│  ├── 妥善管理私钥（HSM、KMS）                               │
│  ├── 定期轮换密钥                                            │
│  ├── 实施证书吊销检查（CRL/OCSP）                          │
│  └── 考虑后量子迁移                                         │
│                                                             │
│  ✗ 不应该做的                                               │
│  ├── 不要使用 RSA-1024 或更短密钥                           │
│  ├── 不要使用 PKCS#1 v1.5 加密（仅签名可用）               │
│  ├── 不要硬编码私钥                                          │
│  ├── 不要自己实现密码算法                                    │
│  ├── 不要忽略证书验证                                        │
│  ├── 不要使用静态 DH（无前向安全）                         │
│  └── 不要使用已攻破的曲线（如 secp160r1）                  │
│                                                             │
│  密钥长度建议（2024 年）：                                   │
│  ├── RSA：最低 2048 位，推荐 3072 位                         │
│  ├── ECC：P-256 或 X25519/Ed25519                          │
│  ├── DH：最低 2048 位，推荐 3072 位                         │
│  └── 后量子：遵循 NIST 建议                                 │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 常见错误

**错误 1：使用过短的密钥**：

```python
# ✗ 错误：RSA-1024 已不安全
key = RSA.generate(1024)  # 不安全！

# ✓ 正确：使用 RSA-3072 或更长
key = RSA.generate(3072)  # 安全
```

**错误 2：忽略证书验证**：

```python
# ✗ 错误：不验证证书
requests.get('https://example.com', verify=False)

# ✓ 正确：严格验证证书
requests.get('https://example.com', verify=True)
```

**错误 3：使用静态密钥（无前向安全）**：

```python
# ✗ 错误：静态 RSA 密钥交换
# TLS_RSA_* 密码套件（无前向安全）

# ✓ 正确：使用 ECDHE
# TLS_ECDHE_* 密码套件（前向安全）
```

---

## 总结与思考

### 核心要点回顾

**非对称加密知识框架**：

```
┌─────────────────────────────────────────────────────────────┐
│              非对称加密知识框架                             │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  主要算法                                                   │
│  ├── RSA：最广泛，密钥长，速度慢                           │
│  ├── ECC：密钥短，速度快，移动友好                         │
│  ├── DH/ECDH：密钥交换专用                                 │
│  └── ElGamal：概率加密，较少使用                           │
│                                                             │
│  数学基础                                                   │
│  ├── 整数分解：RSA                                         │
│  ├── 离散对数：DH、ElGamal                                 │
│  └── 椭圆曲线：ECC、ECDH                                   │
│                                                             │
│  应用场景                                                   │
│  ├── 密钥交换：TLS 握手、SSH                               │
│  ├── 数字签名：证书、代码签名、JWT                         │
│  ├── 加密：PGP、小数据加密                                 │
│  └── 身份认证：证书体系                                     │
│                                                             │
│  未来趋势                                                   │
│  ├── 后量子密码：Kyber、Dilithium                          │
│  ├── 混合方案：传统 + 后量子                               │
│  └── 迁移时间线：2024-2035                                 │
│                                                             │
└─────────────────────────────────────────────────────────────┘
```

### 深入思考

**1. 为什么 ECC 正在取代 RSA？**

- 相同安全性，密钥更短（256 位 vs 3072 位）
- 性能更好（签名、密钥交换更快）
- 带宽占用小（适合移动网络）
- 功耗低（适合移动设备）

**2. 量子计算真的会破解密码学吗？**

- 理论上：Shor 算法可破解 RSA、ECC
- 实际上：需要百万级量子比特（目前~100）
- 时间线：预计 2035-2040 年构成威胁
- 应对：后量子密码已在标准化

**3. 如何选择算法？**

- 新系统：优先 ECC（Ed25519/X25519）
- 兼容性：RSA-3072
- 长期安全：考虑后量子混合
- 合规要求：遵循行业标准

---

## 参考资料

### 标准与规范

```
- NIST FIPS 186-5: 数字签名标准
- RFC 8017: PKCS#1 v2.2 (RSA)
- RFC 8446: TLS 1.3
- NIST PQC: 后量子密码标准化
```

### 实现库

```
Python:
- cryptography: https://cryptography.io/
- pycryptodome: https://www.pycryptodome.org/
- PyJWT: https://pyjwt.readthedocs.io/

Java:
- Bouncy Castle: https://www.bouncycastle.org/
- JCA: Java Cryptography Architecture

Go:
- crypto/rsa, crypto/ecdsa: 标准库
```

### 学习资源

```
- 《Serious Cryptography》- Jean-Philippe Aumasson
- 《Understanding Cryptography》- Christof Paar
- Coursera: Cryptography I & II (Stanford)
```

---

*365 天信息安全技术系列 | Day 183 | 密码学系列第 3 篇*

> 非对称加密是公钥密码学的核心。理解 RSA 和 ECC，是理解现代安全通信的基础。

> 本文内容仅供学习和研究使用，请勿用于非法目的。

---

*本文是 365 天信息安全技术系列的第 183 篇，密码学系列第 3 篇*

*密码学系列继续！*