McEliece密码系统攻击：从GRS码到Sidelnikov-Shestakov攻击的完整解析

官方公众号企业安全新浪微博

FreeBuf.COM网络安全行业门户，每日发布专业的安全资讯、技术剖析。

FreeBuf+小程序

FreeBuf+小程序把安全装进口袋

其他

一、题目背景

本题是一道经典的后量子密码学CTF挑战,涉及McEliece公钥密码系统的安全性分析。题目提供了两个文件:

publickey.sobj: 公钥矩阵(64×128,定义在GF(2^8)上)
ciphertext.sobj: 密文向量(128维,GF(2^8))

我们的目标是从公钥和密文中恢复出原始明文(flag)。

二、McEliece密码系统简介

2.1 系统原理

McEliece密码系统是由Robert McEliece于1978年提出的基于编码理论的公钥加密系统,是后量子密码学的候选方案之一。其核心思想是利用线性纠错码的解码困难性来构建加密系统。

密钥生成:

选择一个[n, k, d]线性纠错码C,具有高效的解码算法D
选择k×k的可逆矩阵S和n×n的置换矩阵P
计算G' = S·G·P,其中G是码C的生成矩阵
公钥:G' (k×n矩阵)
私钥:(S, G, P, D)

加密过程:

明文m是k维向量
随机选择权重为t的错误向量e(n维)
密文 c = m·G' + e

解密过程:

计算 c' = c·P^(-1) = m·S·G + e·P^(-1)
使用解码算法D解码c',得到m·S
计算 m = (m·S)·S^(-1)

2.2 安全性基础

McEliece系统的安全性建立在两个假设上:

码结构隐藏:经过S和P变换后的G'应当看起来像随机矩阵
译码困难性:在不知道码结构的情况下,从c恢复m是计算困难的

三、本题的致命弱点:使用GRS码

3.1 什么是广义里德-所罗门(GRS)码

广义里德-所罗门码是一类特殊的线性码,定义如下:

给定:

支撑向量 α = (α₀, α₁, ..., α_{n-1}),所有αᵢ互不相同
列乘子向量 v = (v₀, v₁, ..., v_{n-1}),所有vᵢ≠0
参数 k < n

GRS码的生成矩阵G为:

G[i,j] = vⱼ · αⱼⁱ   (i=0,1,...,k-1; j=0,1,...,n-1)

即第j列是 vⱼ·(1, αⱼ, αⱼ², ..., αⱼ^(k-1))^T

3.2 GRS码的结构性弱点

GRS码具有明显的代数结构:

范德蒙德结构:生成矩阵的每一列都是范德蒙向量
列之间的多项式关系:由于是在有限域上的幂次,列之间存在可识别的代数关系
对偶码也是GRS:GRS码的对偶码仍然是GRS码

这些结构特征使得即使经过线性变换S和置换P,攻击者仍然可以从公钥G'中恢复出原始的GRS码参数。

四、Sidelnikov-Shestakov攻击详解

4.1 攻击原理

Sidelnikov和Shestakov在1992年提出了针对基于GRS码的McEliece变体的多项式时间攻击。攻击的核心思想是:

即使经过S·G·P变换,GRS码的某些代数性质仍然可以被识别和恢复。

具体来说,攻击通过分析公钥矩阵的行间比值来重构支撑向量α。

4.2 攻击步骤

步骤1: 将公钥转换为阶梯形式

首先对公钥矩阵G'进行行简化阶梯形(RREF)变换:

gpe = gp.echelon_form()

这一步不会改变码的结构,但使得矩阵更易于分析。

步骤2: 枚举并测试比率参数

核心算法枚举GF(2^8)中的所有非零元素作为候选的"比率"参数:

for ratio in F.list()[1:]:  # 255个候选值

步骤3: 重构支撑向量α

对于每个ratio,尝试恢复支撑向量a[0], a[1], ..., a[127]:

初始化:

设 a[0] = 0, a[1] = 1 (无损一般性)

恢复后半部分 a[k]到a[n-1]:

利用阶梯形式的性质,通过以下关系恢复:

tar = (gpe[0][i] / gpe[1][i]) / ratio

然后找到满足条件的x:

(x - a[1]) / (x - a[0]) == tar

这里利用了GRS码中支撑点之间的代数关系。

恢复前半部分 a[2]到a[k-1]:

使用更复杂的二次方程组:

v0 = gpe[0][k]/gpe[i][k] * (a[k] - a[0])
v1 = gpe[0][k+1]/gpe[i][k+1] * (a[k+1] - a[0])

找到x和r2使得:

r2 * (a[k] - x) == v0
r2 * (a[k+1] - x) == v1

步骤4: 重构列乘子向量

一旦找到正确的支撑向量α,需要重构列乘子向量v:

mp = gp.matrix_from_rows_and_columns(range(k), range(k+1))
cp = mp.right_kernel().basis()[-1]

通过分析公钥的核空间结构来恢复乘子。

步骤5: 构造原始GRS码并解码

现在我们有了完整的GRS码参数(α, k, v),可以:

构造GRS码对象:

C = codes.GeneralizedReedSolomonCode(a, k, cols)

使用Berlekamp-Welch解码器:

D = codes.decoders.GRSBerlekampWelchDecoder(C)

解码密文:

tmp = D.decode_to_message(cmsg)
msg = vector(tmp) * h.inverse()

五、实战解题过程

5.1 环境准备

需要安装SageMath数学软件:

# Sage提供了丰富的编码理论库
sage --version

5.2 加载数据

F = GF(2^8)
n, k = 128, 64
cmsg = load("ciphertext.sobj")
gp = load("publickey.sobj")

5.3 执行攻击

运行完整的Sidelnikov-Shestakov攻击脚本(见exploit.sage)。

关键观察:

总共只需要枚举255个ratio值
对于正确的ratio,所有验证步骤都会成功
攻击在第一个ratio时就成功了,说明α[0]=0的选择是标准的

5.4 获取Flag

解码成功后得到64个GF(2^8)元素:

(102, 108, 97, 103, 123, 82, 101, 101, 100, 83, 111, 108, ...)

转换为ASCII:

flag{ReedSolomonCodesAreNoGoodIdeaForMcElieceIfYouWantTopCrypto}

Flag揭示:使用里德-所罗门码(GRS码的特例)来实现McEliece是一个糟糕的主意!

六、为什么GRS码不安全?

6.1 结构可识别性

GRS码的生成矩阵具有明显的数学结构:每一列都是某个元素的幂次序列。即使经过线性变换和置换,这种幂次关系在某种程度上仍然保留在公钥矩阵中。

6.2 攻击复杂度

Sidelnikov-Shestakov攻击的时间复杂度约为 O(q² · n³),其中:

q = |F| = 256 (有限域大小)
n = 128 (码长度)

对于本题参数:

需要枚举255个ratio
每个ratio需要进行n次查找和验证
总体可以在秒级完成

相比之下,使用二元Goppa码的正确McEliece实现目前还没有已知的多项式时间攻击。

6.3 正确的码选择

安全的McEliece实现应该使用:

二元Goppa码:目前最安全的选择,是NIST后量子密码标准的候选
参数要求:
- 码长 n ≥ 2000
- 错误能力 t ≥ 50
- 定义在GF(2^m),m ≥ 11

七、后量子密码学的思考

7.1 McEliece的优势

尽管本题展示了错误实现的McEliece是脆弱的,正确实现的McEliece具有重要优势:

抗量子:没有已知的量子算法能有效攻击
简单高效:加密和解密都是线性运算
长期安全:40多年的密码分析没有发现本质性弱点

7.2 实现的重要性

本题强调了一个关键教训:

在密码学中,算法的正确选择和实现细节同样重要!

使用GRS码看似简化了实现,实际上完全破坏了系统的安全性。

八、完整解题代码

#https://eprint.iacr.org/2009/452.pdf
# Sidelnikov-Shestakov attack

F=GF(2^8)
n, k = 128, 64
cmsg = load("ciphertext.sobj")
gp = load("publickey.sobj")

gpe = gp.echelon_form()

for ratio in F.list()[1:]:
    a = [0]*n
    a[1] = 1
    succ = True

    # 恢复支撑向量
    for i in range(k, n):
        tar = gpe[0][i]/gpe[1][i] / ratio
        res = 0
        for x in F.list():
            if x!=0 and (x-a[1])/(x-a[0])==tar:
                if res!=0:
                    succ = False
                    break
                res = x
        if res==0:
            succ = False
        if not succ:
            break
        a[i] = res

    if not succ:
        continue

    # 恢复剩余元素
    for i in range(2, k):
        v0 = gpe[0][k]/gpe[i][k]*(a[k]-a[0])
        v1 = gpe[0][k+1]/gpe[i][k+1]*(a[k+1]-a[0])
        res = 0
        for r2 in F.list()[1:]:
            for x in F.list()[1:]:
                if r2*(a[k]-x)==v0 and r2*(a[k+1]-x)==v1:
                    res = x
                    break
            if res!=0:
                break
        if res==0:
            succ = False
        if not succ:
            break
        a[i] = res

    if not succ:
        continue

    try:
        # 重构GRS码
        mp = gp.matrix_from_rows_and_columns(range(k), range(k+1))
        cp = mp.right_kernel().basis()[-1]
        Ct = codes.GeneralizedReedSolomonCode(a[:k+1], k, cp)
        Et = codes.encoders.GRSEvaluationVectorEncoder(Ct)
        gm = Et.generator_matrix()
        co = gm.right_kernel().basis()[-1]
        Ct = codes.GeneralizedReedSolomonCode(a[:k+1], k, co)
        Et = codes.encoders.GRSEvaluationVectorEncoder(Ct)
        gtmp1 = Et.generator_matrix()
        gtmp2 = gtmp1.matrix_from_rows_and_columns(range(k), range(k))
        mtmp2 = gp.matrix_from_rows_and_columns(range(k), range(k))
        h = mtmp2*gtmp2.inverse()
        g = h.inverse()*gp
        cols = g[0]

        # 解码
        C = codes.GeneralizedReedSolomonCode(a, k, cols)
        E = codes.encoders.GRSEvaluationVectorEncoder(C)
        D = codes.decoders.GRSBerlekampWelchDecoder(C)
        g = E.generator_matrix()
        tmp = D.decode_to_message(cmsg)
        msg = vector(tmp)*h.inverse()

        # 输出flag
        msg_bytes = [int(str(x)) for x in msg]
        print(bytes(msg_bytes))
        break
    except:
        continue

九、总结

本题通过一个精心设计的密码挑战,展示了:

McEliece密码系统的工作原理
GRS码的代数结构及其安全弱点
Sidelnikov-Shestakov攻击的实现细节
密码系统实现中参数选择的重要性

关键要点:

McEliece本身是安全的后量子密码系统
使用GRS/Reed-Solomon码实现会导致多项式时间攻击
正确的实现应使用二元Goppa码
在后量子时代,基于编码理论的密码学仍然是重要的研究方向

Flag:flag{ReedSolomonCodesAreNoGoodIdeaForMcElieceIfYouWantTopCrypto}

参考文献

Sidelnikov, V.M., Shestakov, S.O. (1992). "On insecurity of cryptosystems based on generalized Reed-Solomon codes"
IACR ePrint 2009/452: "Algebraic Cryptanalysis of McEliece Variants with Compact Keys"
NIST Post-Quantum Cryptography Standardization Project
Hack.lu CTF 2017 - McEliece Challenge Writeups

本文详细解析了一道McEliece密码学挑战题,展示了从理论到实践的完整攻击过程。希望能帮助读者理解后量子密码学的安全性分析方法。

已在FreeBuf发表 0 篇文章

本文为独立观点，未经授权禁止转载。
如需授权、对文章有疑问或需删除稿件，请联系 FreeBuf 客服小蜜蜂（微信：freebee1024）