WriteUp(HFCTF) - Crypto | 0xDktb's Blog

GM

[题目考点]

Goldwasser–Micali (GM) cryptosystem (Legendre符号)

[题目文件]

Click Here to Download

[题解分析]

GM密钥生成：

生成大素数p,q，N=pq，再通过随机选择找到x，使得x是模p和模q的二次非剩余，则由Legendre定义知$(\frac{x}{p})=(\frac{x}{q})=-1$

公钥(x, N)，私钥(p, q)

GM加密：

明文二进制表示为$(m_{1},m_{2},…,m_{n})$

对每个$m_{i}$，生成随机值$y_{i}$，$c_{i}=y_{i}^{2}x^{y_{i}|m_{i}}\ mod\ N$

GM解密：

密文二进制表示为$(c_{1},x_{2},…,c_{n})$

对每个$c_{i}$，验证$(\frac{c_{i}}{p})$和$(\frac{c_{i}}{q})$，则由x为二次非剩余易得，勒让德符号均为1时$m_{i}=0$，均为-1时$m_{i}=1$

题目中泄露了$\varphi(N)$，因此相当于暴露私钥，直接解密即可

[exp]

from Crypto.Util.number import *
from gmpy2 import iroot

phi = ...
n = ...
sum = n + 1 - phi
delta = (sum**2) - 4 * n
sqrt_delta = int(iroot(delta, 2)[0])
p = (sum + sqrt_delta) // 2
q = n // p

cipher = [...]
flag = ''
for i in cipher:
    if pow(i, (p - 1) // 2, p) == 1 and pow(i, (q - 1) // 2, q) == 1:
        flag += '0'
    else:
        flag += '1'
print(long_to_bytes(int(flag, 2)))

mceliece

比赛期间找到的paper有点杂，再加上Goppa码看得云里雾里，于是结束前三四个小时就去摸鱼了- -赛后填了下坑，在此做下记录

[题目考点]

Information-set decoding

[题目文件]

Click Here to Download

[题解分析]

Goppa码：(具体纠错原理这里不费篇幅写，因为和本题涉及攻击方法基本无关联)

可以用[n, k, d]线性码来描述Goppa码，满足维度$k\geq n-mt$，最小汉明重量$d\geq t+1$

其对应generator matrix为$k\times n$，且rank(G)=k，满足$GH^{T}=0(H^{T}为校验矩阵)$

最多能纠正t个错误

The McEliece cryptosystem：

$G’=SGP$（S是随机生成的$k\times k$可逆矩阵，G是Goppa码的$k\times n$生成矩阵，P是随机的$n\times n$排列矩阵(即每行/每列上仅有一个1，其他均为0)）

公钥为$(G’,k,n)$，私钥为$(S,G,P)$及Goppa码的g等

$GF(2)$上的McEliece二进制分组长度为k，加密时$c=mG’,y=c+e$，y作为密文发送

攻击者主要有以下两种攻击途径：

这里不介绍第一种结构攻击，重点在第二种借助Information Set的攻击方法

设I为$\{1,…,n\}$的一k元子集，则$G_{I}$定义为：以I作列索引，从G’中得到的$k\times k$子矩阵，如果$G_{I}$可逆，则I满足Information Set定义

Information-set decoding一般形式下，要求输入

$F_{q}^{n}$下的向量y(即McEliece系统的密文，与c的汉明距离为w)
$k\times n$矩阵G’

则令I为Information Set，以其作为列索引得到$y_{I},G_{I}$，计算$y_{I}G_{I}^{-1}G’(1\times n)$，即认为其等于c或是c的一个近似估计

[Lee–Brickell’s algorithm]

$g_{a}$表示$G_{I}^{-1}G’$中a索引的列上唯一的1所在的行向量（由定义易知该列上仅有1个1，其他均为零元）

Step 1中Information-set作列索引对应的$y_{I}$，如果k个元素均无误差，则$y_{I}G_{I}^{-1}G’$能直接恢复出c（这一点很好证明），但k个元素中存在误差元时，要进行Step 3的汉明变换（$p_{max}=w$，但一般p不取$p_{max}$，尽管取$p_{max}$能保证任意Information-set都能在Step 3得到正确的e，但p过大会使得Step 3中的(A, m)组合过多，适宜即可）

下图为$p=p_{max}=w$时的运行截图

[exp]

import itertools
from Crypto.Util.number import *

cipher = load("cipher.sobj")
pubkey = load("pubkey.sobj")

def Lee_Brickell(y, G, Fq, w, p_max):
    n, k = G.ncols(), G.nrows()
    #cnt = 0
    while True:
        # step 1
        I = sample(range(n), k) # Information Set
        G_I = G.matrix_from_columns(I)
        if not G_I.is_invertible():
            continue
        invG_I = G_I.inverse()
        y_I = y.matrix_from_columns(I)
        # step 2
        e_base = y - y_I * invG_I * G # e which may be inaccurate
        # step 3
        g = (invG_I * G).rows()
        #cnt += 1
        #print(cnt)
        for p in range(p_max + 1): # size-p subset
            for A in itertools.combinations(range(k), p):
                for m in itertools.product(Fq.list()[1:], repeat=p):
                    e = e_base[0] - sum(m[i] * g[A[i]] for i in range(p))
                    if e.hamming_weight() == w:
                        return e
                    
F2 = GF(2)
flag = ""
for y in cipher:
    e = Lee_Brickell(y, pubkey, F2, 6, 2)
    c = y - Matrix(e) # m * pubkey == c
    m = pubkey.solve_left(c)
    flag += "".join([str(i) for i in m[0]])
flag += "0" * (8 - len(flag) % 8)
long_to_bytes(int(flag, 2))
# b'flag{c941a3cc-85e3-4401-a0f1-764206e71bf3}\x00\x00\x00\x00'