第五十四 量子密码学

用量子对抗量子：密码学的新战场

量子计算机的出现是21世纪计算领域最具颠覆性的技术变革之一。对于密码学而言，这既是巨大的威胁，也是全新的机遇。一方面，量子计算机有能力破解当前广泛使用的RSA和椭圆曲线密码；另一方面，量子力学原理也为构建理论上不可破解的密码系统提供了全新的工具。

本章将探讨量子计算对传统密码的威胁、量子密钥分发技术，以及正在兴起的后量子密码学标准。

54.1 量子计算对传统密码的威胁

量子计算的威力

传统计算机使用比特（bit）作为信息的基本单位，每个比特要么是0要么是1。量子计算机使用量子比特（qubit），它可以同时处于0和1的叠加态。这使得量子计算机在处理特定问题上具有指数级加速的潜力。

Shor 算法：公钥密码的噩梦

1994年，数学家 Peter Shor 提出了Shor 算法，证明量子计算机可以在多项式时间内解决以下问题：

• 大整数分解：给定大合数 n = p * q，快速找到素因子 p 和 q
• 离散对数问题：在有限域或椭圆曲线群上求解离散对数

这意味着：

实际影响：一台拥有约4000个逻辑量子比特的量子计算机，就能在合理时间内破解2048位RSA密钥。虽然目前的量子计算机距离这个规模还很远，但密码系统的部署周期往往长达数十年，因此必须提前准备。

Grover 算法：对称密码的减半威胁

1996年，Lov Grover 提出了Grover 搜索算法，它可以将无序数据库的搜索复杂度从 O(N) 降低到 O(√N)。

对密码学的影响：

• 对称加密：有效密钥长度减半。例如，AES-256 的安全性降低到约128位（仍然安全），但 AES-128 的安全性降低到约64位（不再安全）
• 哈希函数：碰撞攻击的复杂度从 O(2^(n/2)) 降低到 O(2^(n/3))， preimage 攻击从 O(2^n) 降低到 O(2^(n/2))

应对策略：对称加密和哈希函数只需加倍密钥/输出长度即可恢复安全性。例如，使用 AES-256 代替 AES-128，使用 SHA-384/512 代替 SHA-256。

54.2 量子密钥分发（QKD）

量子密钥分发利用量子力学原理，让两个通信方可以生成共享的随机密钥，并确保任何窃听行为都会被发现。与基于数学难题的传统密码不同，QKD 的安全性由物理定律保证。

BB84 协议

1984年，Charles Bennett 和 Gilles Brassard 提出了第一个量子密钥分发协议——BB84。其核心思想是利用量子态的不可克隆性和测量坍缩特性来检测窃听。

基本原理

1. 量子态编码：发送方 Alice 使用两种基（ rectilinear + 和 diagonal × ）来编码比特：

   • + 基：0° = 0，90° = 1
   • × 基：45° = 0，135° = 1

2. 随机选择：Alice 随机选择基和比特值发送光子。Bob 也随机选择基进行测量。

3. 基比对：通过公开信道，Alice 和 Bob 比较各自使用的基，只保留使用相同基的那些比特。

4. 错误检测：随机抽取部分比特公开比较，计算误码率。如果误码率超过阈值（通常11%），说明存在窃听者 Eve。

为什么能检测窃听？

量子力学的两个核心原理保证了安全性：

• 不可克隆定理：未知量子态不能被完美复制。Eve 无法复制光子留一份给自己。
• 测量坍缩：测量会改变量子态。Eve 的测量会引入可检测的错误。

如果 Eve 试图窃听：

1. 她必须选择基来测量光子
2. 她有50%的概率选错基
3. 选错基时，她的测量会改变光子状态
4. 这导致 Bob 接收到的数据中有约25%的错误
5. Alice 和 Bob 通过比对可以发现这些异常

QKD 的局限性

尽管 QKD 在理论上是完美的，但实际部署面临挑战：

1. 距离限制：光纤传输损耗限制了距离，目前最长约400-500公里
2. 需要认证信道：经典信道需要认证，防止中间人攻击
3. 设备安全性：实际设备可能存在侧信道漏洞
4. 速率限制：密钥生成速率远低于传统密钥交换

54.3 后量子密码学（PQC）

后量子密码学（Post-Quantum Cryptography）研究的是能够抵抗量子计算机攻击的密码算法。与 QKD 不同，PQC 仍然基于数学难题，只是选择了量子计算机也难以解决的问题。

量子安全的数学难题

主要 PQC 方案家族

基于格的密码（Lattice-based）

格是 n 维空间中的离散点集。格密码基于以下困难问题：

• 最短向量问题（SVP）：在格中找到最短的非零向量
• 最近向量问题（CVP）：找到格中最接近给定向量的点
• LWE（Learning With Errors）：从带噪声的线性方程中恢复秘密

格密码的优势：

• 密钥和密文尺寸相对较小
• 计算效率高
• 功能丰富（支持加密、签名、同态运算）

基于编码的密码（Code-based）

基于纠错码理论，最早由 Robert McEliece 于1978年提出。

• McEliece 密码系统：使用随机线性码的译码困难性
• 优势：历史悠久，安全性研究充分
• 劣势：公钥尺寸很大（MB级别）

基于多变量的密码（Multivariate-based）

基于有限域上多元多项式方程组的求解困难性。

• 优势：签名方案速度快，签名尺寸小
• 劣势：密钥尺寸较大，部分方案已被攻破

基于哈希的密码（Hash-based）

利用哈希函数的安全性构建签名方案。

• Lamport 签名、Merkle 签名：安全性完全依赖于哈希函数
• 优势：安全性分析简单直观
• 劣势：一次性签名或有状态签名，使用复杂

54.4 NIST 后量子密码标准

2022年至2024年，美国国家标准与技术研究院（NIST）经过多轮评估，正式发布了首批后量子密码标准算法。

标准化算法

CRYSTALS-Kyber

Kyber 是一种 IND-CCA2 安全的密钥封装机制（KEM），用于替代 ECDH 密钥交换。

核心特点：

• 安全性基于模格上的 LWE 问题（Module-LWE）
• 密钥尺寸小，计算速度快
• 提供三种安全级别：Kyber-512、Kyber-768、Kyber-1024

工作流程：

1. 接收方生成公钥 pk 和私钥 sk
2. 发送方使用 pk 封装，得到密文 c 和共享密钥 k
3. 接收方使用 sk 解封装 c，恢复相同的共享密钥 k

CRYSTALS-Dilithium

Dilithium 是一种数字签名算法，用于替代 ECDSA 和 RSA 签名。

核心特点：

• 安全性基于模格上的短整数解问题（Module-SIS）和 LWE
• 签名尺寸较小，验证速度快
• 提供三种安全级别

54.5 Rust 实现

Rust 生态中已有多个后量子密码库实现。下面介绍使用 pqcrypto 的示例。

Cargo.toml 依赖

[dependencies]
pqcrypto-traits = "0.3"
pqcrypto-kyber = "0.7"
pqcrypto-dilithium = "0.5"
rand = "0.8"

Kyber 密钥封装示例

use pqcrypto_kyber::kyber768;
use pqcrypto_traits::kem::{Ciphertext, PublicKey, SecretKey, SharedSecret};

fn main() {
    // 1. 接收方（Bob）生成密钥对
    let (pk, sk) = kyber768::keypair();
    println!("Bob 生成了 Kyber-768 密钥对");
    println!("公钥长度: {} bytes", pk.as_bytes().len());
    println!("私钥长度: {} bytes", sk.as_bytes().len());

    // 2. 发送方（Alice）使用 Bob 的公钥封装密钥
    let (ciphertext, shared_secret_alice) = kyber768::encapsulate(&pk);
    println!("\nAlice 封装了共享密钥");
    println!("密文长度: {} bytes", ciphertext.as_bytes().len());
    println!("Alice 的共享密钥: {:02x?}", shared_secret_alice.as_bytes());

    // 3. Bob 使用私钥解封装，恢复共享密钥
    let shared_secret_bob = kyber768::decapsulate(&ciphertext, &sk);
    println!("\nBob 解封装了共享密钥");
    println!("Bob 的共享密钥:   {:02x?}", shared_secret_bob.as_bytes());

    // 4. 验证双方密钥一致
    assert_eq!(
        shared_secret_alice.as_bytes(),
        shared_secret_bob.as_bytes(),
        "共享密钥不一致！"
    );
    println!("\n✓ 共享密钥一致，可以开始对称加密通信");
}

Dilithium 数字签名示例

use pqcrypto_dilithium::dilithium3;
use pqcrypto_traits::sign::{PublicKey, SecretKey, SignedMessage, Signer, Verifier};

fn main() {
    // 1. 生成签名密钥对
    let (pk, sk) = dilithium3::keypair();
    println!("生成了 Dilithium3 签名密钥对");
    println!("公钥长度: {} bytes", pk.as_bytes().len());
    println!("私钥长度: {} bytes", sk.as_bytes().len());

    // 2. 待签名的消息
    let message = b"这是一份需要量子安全保护的重要合同";
    println!("\n待签名消息: {}", String::from_utf8_lossy(message));

    // 3. 使用私钥签名
    let signed_msg = sk.sign(message);
    println!("签名完成");
    println!("签名长度: {} bytes", signed_msg.as_bytes().len());

    // 4. 使用公钥验证签名
    let verified = pk.verify(&signed_msg, message);
    match verified {
        Ok(()) => println!("✓ 签名验证通过"),
        Err(e) => println!("✗ 签名验证失败: {:?}", e),
    }

    // 5. 验证篡改检测
    let mut tampered_msg = message.to_vec();
    tampered_msg[0] ^= 0xFF; // 篡改第一个字节
    let tampered_signed = sk.sign(&tampered_msg);
    
    match pk.verify(&tampered_signed, message) {
        Ok(()) => println!("异常：篡改未被发现"),
        Err(_) => println!("✓ 正确检测到消息篡改"),
    }
}

混合加密：传统 + 后量子

在量子计算机真正出现之前，一种务实的策略是采用混合方案：同时使用传统算法和后量子算法，确保即使其中一种被攻破，整体仍然安全。

#![allow(unused)]
fn main() {
use pqcrypto_kyber::kyber768;
use pqcrypto_traits::kem::{Ciphertext, PublicKey, SecretKey, SharedSecret};
use rand::thread_rng;
use x25519_dalek::{EphemeralSecret, PublicKey as X25519PublicKey};

/// 混合密钥交换：X25519 + Kyber768
fn hybrid_key_exchange() {
    // ===== 传统部分：X25519 =====
    let alice_x_secret = EphemeralSecret::random_from_rng(thread_rng());
    let alice_x_public = X25519PublicKey::from(&alice_x_secret);

    let bob_x_secret = EphemeralSecret::random_from_rng(thread_rng());
    let bob_x_public = X25519PublicKey::from(&bob_x_secret);

    let alice_x_shared = alice_x_secret.diffie_hellman(&bob_x_public);
    let bob_x_shared = bob_x_secret.diffie_hellman(&alice_x_public);
    assert_eq!(alice_x_shared.as_bytes(), bob_x_shared.as_bytes());

    // ===== 后量子部分：Kyber768 =====
    let (kyber_pk, kyber_sk) = kyber768::keypair();
    let (kyber_ct, kyber_ss_enc) = kyber768::encapsulate(&kyber_pk);
    let kyber_ss_dec = kyber768::decapsulate(&kyber_ct, &kyber_sk);
    assert_eq!(kyber_ss_enc.as_bytes(), kyber_ss_dec.as_bytes());

    // ===== 混合共享密钥 =====
    // 将两个共享密钥进行哈希混合，即使其中一个被攻破，另一个仍提供安全性
    use sha2::{Sha256, Digest};
    let mut hasher = Sha256::new();
    hasher.update(alice_x_shared.as_bytes());
    hasher.update(kyber_ss_enc.as_bytes());
    let hybrid_shared_secret = hasher.finalize();

    println!("混合共享密钥: {:02x?}", hybrid_shared_secret);
    println!("✓ 同时受 X25519 和 Kyber768 保护");
}
}

54.6 迁移路线图

向量子安全密码的迁移是一项长期工程，建议采取以下策略：

1. 密码清单：梳理系统中所有使用的密码算法和密钥长度
2. 风险评估：识别需要优先保护的高价值数据和长期保密数据
3. 混合部署：在关键系统中同时部署传统和后量子算法
4. 算法敏捷性：设计支持算法替换的架构，避免硬编码特定算法
5. 持续跟踪：关注 NIST 等标准化组织的最新进展

54.7 本章总结

练习建议

1. 基础练习：使用 pqcrypto-kyber 实现完整的密钥封装流程，验证封装/解封装的一致性。

2. 中级练习：使用 pqcrypto-dilithium 实现文件签名工具，能够对任意文件进行签名和验证。

3. 高级练习：实现一个混合 TLS 握手模拟：结合 X25519 和 Kyber768 进行密钥交换，比较纯传统方案和混合方案的性能开销。

4. 实践项目：调研你的现有项目（或常用开源项目）中使用的密码算法，制定一份向量子安全密码迁移的评估报告。