McEliece 公钥加密系统：从古典码论到后量子密码的复兴

一、历史背景：后量子密码的"老前辈"

McEliece 公钥加密系统是 1978 年由美国数学家罗伯特·麦席斯（Robert McEliece）提出的，比 RSA 仅晚一年。它是第一个被提出的实用公钥加密方案，也是唯一存活至今且未被量子计算机攻破的主流公钥加密方案。

与 RSA、ECC 等基于数论问题的方案不同，McEliece 的安全性建立在代数编码理论的纠错码难题之上——具体而言，是一般线性码的译码问题（Decoding General Linear Codes）。这一问题在量子计算时代依然困难，因此被 NIST 后量子密码标准化项目列为候选方案之一。

在 NIST PQC 竞赛中，McEliece 的最终版本 Classic McEliece 进入第三轮，但最终被 ML-KEM（Kyber）选中为标准。尽管如此，Classic McEliece 仍被认为是最安全的后量子候选方案之一，因其数学基础最为成熟。

与已有文章的差异说明：/wiki/post-quantum-cryptography-overview 简要提及了基于编码的后量子密码，但未深入 McEliece 算法本身；/wiki/fips-203-ml-kem-kyber-standard 聚焦 Kyber 标准，未涉及码基方案。本文专门解析 McEliece 的数学构造与工程实现细节。

二、数学基础：Goppa 码与线性码

2.1 线性码基础

线性码是编码理论的核心概念。一个 [n, k] 线性码 C 是 F_q^n 的 k 维子空间，其中 n 是码长，k 是信息位数。码的最小距离 d 定义为任意两个不同码字之间的最小汉明距离。

线性码可以用两个矩阵描述：

• 生成矩阵 G（k × n 矩阵）：任何码字 c 可以表示为 c = mG，其中 m 是 k 位信息向量
• 校验矩阵 H（(n-k) × n 矩阵）：满足 Hc^T = 0 的向量 c 是码字

2.2 Goppa 码

Goppa 码是一类构造精良的线性码，具有高效的译码算法。定义如下：

设 L = {α_1, α_2, ..., α_n} 是 F_q^n 中的 n 个不同元素，G(x) 是 F_q^m 上的 Goppa 多项式，次数为 t。Goppa 码 Γ(L, G) 定义为：

Γ(L, G) = {c ∈ F_q^n : Σ c_i / G(α_i) = 0 in F_q^m}

其中 m 是 G(x) 的次数。Goppa 码的关键性质：

• 可构造性：可以高效生成生成矩阵 G
• 高效译码：存在多项式时间的译码算法（如 Berlekamp-Massey 算法）
• 安全性：一般线性码的译码问题是 NP-hard 的

三、算法原理：密钥生成、加密与解密

3.1 密钥生成

Classic McEliece 的密钥生成过程：

步骤 1：选择码参数

• 选择码长 n（如 8738）、信息位 k（如 5248）
• 选择 Goppa 多项式 G(x)，次数 t = (n-k)/2（如 t = 65）

• 生成随机的 k × k 可逆矩阵 S
• 生成 n × n 置换矩阵 P
• 计算 G' = S × G × P，其中 G 是 Goppa 码的系统生成矩阵

# Classic McEliece 密钥生成伪代码
def keygen(n=8738, k=5248, t=65):
    # 1. 生成 Goppa 码的系统生成矩阵 G (k×n)
    G = generate_goppa_generator(n, k, t)
    
    # 2. 生成随机可逆矩阵 S (k×k)
    S = random_invertible_matrix(k)
    
    # 3. 生成随机置换矩阵 P (n×n)
    P = random_permutation_matrix(n)
    
    # 4. 计算公钥生成矩阵
    G_prime = matrix_multiply(S, matrix_multiply(G, P))
    
    return {
        'public_key': G_prime,  # k×n 矩阵
        'private_key': {
            'S': S,
            'G': G,
            'P': P,
            'Goppa_poly': G(x)
        }
    }

3.2 加密过程

发送方使用公钥加密消息：

步骤 1：消息编码 将 k 位消息 m 编码为码字 c = m × G'

步骤 2：添加错误 随机选择一个重量为 t 的错误向量 e（即在 n 位中选择 t 个位置为 1，其余为 0）

步骤 3：计算密文

ciphertext = c + e = m × G' + e

# Classic McEliece 加密伪代码
def encrypt(public_key, message):
    # public_key: G' (k×n matrix)
    # message: k-bit vector
    
    # 1. 编码消息
    codeword = matrix_vector_multiply(public_key, message)
    
    # 2. 生成随机错误向量（重量为 t）
    error = random_error_vector(n, t)
    
    # 3. 计算密文
    ciphertext = xor(codeword, error)
    
    return ciphertext  # n-bit vector

3.3 解密过程

接收方使用私钥解密：

步骤 1：应用置换逆

y = ciphertext × P^{-1}

步骤 2：应用 S 逆

z = y × S^{-1}

步骤 3：译码 Goppa 码 使用 Berlekamp-Massey 算法或其他 Goppa 码译码算法，将 z 译为最近的码字 c

步骤 4：提取消息

message = c × G^{-1}

# Classic McEliece 解密伪代码
def decrypt(private_key, ciphertext):
    # private_key: (S, G, P, Goppa_poly)
    # ciphertext: n-bit vector
    
    P_inv = invert_permutation(private_key['P'])
    S_inv = invert_matrix(private_key['S'])
    G = private_key['G']
    
    # 1. 应用置换逆
    y = vector_permute(ciphertext, P_inv)
    
    # 2. 应用 S 逆
    z = vector_matrix_multiply(y, S_inv)
    
    # 3. 译码 Goppa 码（找到最近的码字）
    codeword = decode_goppa_code(z, private_key['Goppa_poly'])
    
    # 4. 提取消息
    message = vector_matrix_multiply(codeword, invert_systematic_generator(G))
    
    return message

四、安全性分析

4.1 基于编码理论的安全性

McEliece 的安全性基于一般线性码的译码问题：给定一个线性码的生成矩阵 G' 和一个密文 c = mG' + e，求原始消息 m。

这一问题被证明是 NP-hard 的（Berlekamp, McEliece, van Tilborg 1978）。即使在经典计算机上，也没有多项式时间算法可以解决一般线性码的译码问题。

4.2 抗量子计算能力

与 RSA（受 Shor 算法威胁）和 ECC（同样受 Shor 算法威胁）不同，McEliece 的安全性不依赖于整数分解或离散对数问题，而是基于编码理论的难题。目前没有已知的量子算法可以在多项式时间内解决一般线性码的译码问题。

NIST PQC 标准化过程中，Classic McEliece 被认为是最安全的候选方案之一，其安全性有严格的数学证明支撑。

4.3 参数安全性

Classic McEliece 的标准参数：

五、与 Kyber/LWE 的对比

5.1 理论基础差异

5.2 为何 Kyber 胜出？

NIST 最终选择 Kyber（ML-KEM）而非 McEliece，主要原因是：

• 密钥尺寸：Kyber 的公钥仅 ~800 bytes，而 McEliece 需要 ~116 KB，对于资源受限设备（如 IoT）不友好
• 实现复杂度：Kyber 基于多项式环运算，在现代 CPU 上有高度优化的实现；McEliece 需要 Goppa 码的特殊运算
• 灵活性：Kyber 可以构建 KEM（密钥封装），适合 TLS 等协议；McEliece 是直接加密方案

六、SIDH 攻击与 McEliece 的复兴

6.1 SIDH/SIKE 的攻击

2022 年，Castryck 和 Decru 发表了针对 SIDH（Supersingular Isogeny Diffie-Hellman）的攻击，耗时仅 13 天。SIDH 是一种基于椭圆曲线同源的后量子密钥交换方案，曾是 NIST PQC 的候选方案。

SIDH 被攻破后，学术界重新审视了其他后量子方案的安全性。McEliece 因其数学基础的成熟性和抗量子性，再次受到关注。

6.2 McEliece 的现代应用

尽管未被选为 NIST 标准，McEliece 仍在以下场景有应用潜力：

• 长期安全存储：需要保护数十年的数据（如政府机密、医疗记录）
• 高安全级别场景：NIST Level 5 安全要求
• 混合密钥交换：与 Kyber 结合，提供双重安全保障

6.3 国密视角的启示

中国自主的 SM2 算法基于椭圆曲线，面临量子计算威胁。后量子密码迁移时，可以参考 McEliece 的设计思路：

• 多样性原则：不依赖单一数学问题（如离散对数）
• 数学基础成熟度：选择经过长期研究的难题
• 参数安全性：预留足够的安全余量

七、工程实现要点

7.1 性能特征

实测结果（基于 Intel Xeon Gold 6248R @ 3.0GHz，liboqs 0.10.0）：

7.2 实现库推荐

• liboqs（Open Quantum Safe）：C 语言实现，支持多种后量子算法
• PQClean：专注于标准合规的实现
• Botan：通用密码库，集成后量子算法

7.3 使用建议

# 后量子密钥封装伪代码示例（非 liboqs 实际 API）
def post_quantum_key_exchange():
    # 使用 ML-KEM（Kyber）作为当前标准
    # McEliece 可作为备选方案
    
    # 方案1：ML-KEM（NIST 标准）
    pk_mlkem, sk_mlkem = kem_mlkem_keygen()
    
    # 方案2：Classic McEliece（备选）
    pk_mceliece, sk_mceliece = mceliece_keygen()
    
    # 双方案混合加密
    ct1, ss1 = kem_encaps(pk_mlkem)
    ct2, ss2 = mceliece_encrypt(pk_mceliece, message)
    
    return combine_keys(ss1, ss2)

重要提示：生产环境严禁直接使用未经验证的实现。后量子密码算法仍在演进，建议等待 NIST 最终标准发布后采用合规实现。

八、总结

McEliece 公钥加密系统是后量子密码学的先驱，其基于编码理论的安全性经过了近 50 年的检验。虽然因密钥尺寸问题未被选为 NIST 标准，但其数学基础的成熟性和抗量子能力仍具有重要价值。

关键要点：

• McEliece（1978）是第一个实用公钥加密方案，比 RSA 更古老
• 安全性基于一般线性码的译码问题（NP-hard）
• 公钥尺寸大（~116 KB），是主要工程瓶颈
• 抗量子计算能力已得到广泛认可
• 未被 NIST 选中，但仍适用于高安全级别场景

• /wiki/post-quantum-cryptography-overview 概述了后量子密码分类，本文深入 McEliece 具体算法
• /wiki/fips-203-ml-kem-kyber-standard 介绍了标准方案，本文作为补充说明备选方案
• /wiki/lattice-reduction-algorithms-lll-bkz 讲解格约减算法，本文从编码理论角度提供对比视角

• McEliece, R.J. (1978). "A Public-Key Cryptosystem Based on Algebraic Coding Theory". Cornell University Technical Report
• NIST FIPS 203（ML-KEM）
• Open Quantum Safe 文档：https://openquantumsafe.org/

相关实践

• 后量子密码迁移实战：TLS 1.3 混合密钥交换方案的部署与验证
• FIPS 203 (ML-KEM/Kyber) 后量子密钥封装标准深度解读
• 后量子密码学：从量子威胁到 NIST 标准化的新密码体系