正文

2024 网鼎杯 半决赛&决赛

admin
admin V管理员 /0 评论 /48 阅读
1202
此篇文章发布距今已超过59天，您需要注意文章的内容或图片是否可用！

这是 2024 年网鼎杯最后的题目了，其他没有分享的题目，比如朱雀组的 crypto001, 白虎组的 crypto003，可以参考糖醋小鸡块师傅的文章 https://tangcuxiaojikuai.xyz/post/76af431b.html#more，他写的实在太好啦。

半决赛

RSA加密分析

# sagemathimport randomfrom Crypto.Util.number import *flag = b''k = 3d = k/(2*(k+1))ns = []pqs = []es = []for i in range(3):    p = getPrime(512)    q = getPrime(512)if p < q:        tmp = p        p = q        q = tmp    n = p*q    ns.append(n)    pqs.append((p,q))n = min(ns)x = random.randint(0,int(n^(d/2)))x = next_prime(x)for i in range(3):    p,q = pqs[i][0],pqs[i][1]    bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)    bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)    z = random.randint(bound1,bound2)    f = (p-1)*(q-1)    e = inverse(x^2,f) * z % f    es.append(e)e = 8462913c = pow(bytes_to_long(flag),e,ns[0])print(f'ns={ns}')print(f'es={es}')print(f'c ={c }')'''ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729'''

—— 看过《Increment of Insecure RSA Private Exponent Bound Through Perfect Square RSA Diophantine Parameters Cryptanalysis》这篇论文的都知道里边儿的门道有多深

看着这个 bound 是特意构造的就能意识到应该是一道论文题，刚好之前准备出题，手里存了一手，其中的参数有点像

 

唯一的区别就是论文里是，题目是 。当时按照论文的条件生成的数据怎么也没攻击复现成功，所以题目就胎死腹中了，没想到被别的师傅出出来了。

解题流程就在下面，跟着实现一遍就完事了。

最后也还有一个已知 p 高位攻击，（感觉这一届网鼎在库库攻击 p 的高位）准备本地测上述攻击能搞出多少比特的时候发现，对于有些数据这个攻击是没用的。。。。坏了，那就纯赌了，赌出题人看的是这篇 paper，生成了这个攻击能奏效的数据。

从结果来看，赌对了。本地测了当攻击奏效的时候，大概能获取到 254-261 比特的高位，这道题最后是有 257 比特，根据朱雀组题目的测试结果，需要爆破 7 比特。（但如果运气不好只有 254，那就得爆破 10 比特了，那真得多线程了，可以用 pwntools 的 mbruteforce）

最后还有一点老套路，就是这个，但是，所以在 的子群下先 RSA 解   得到，最后Mod(m3,p).nth_root(3,all=True) 一下就好。

nn = []E = []k = 3N = min(nn)delta = k/(2*(k+1))epsilon = sqrt(5)*N^(delta-0.5)C = int(3^(k+1)*2^((k+1)*(k-4)/4)*epsilon^(-k-1))ci = [-(C*E[i])//(nn[i]+1) for i in range(k)]M = matrix(ZZ,[[1] + ci,    [0,C,0,0],    [0,0,C,0],    [0,0,0,C]])L = M.LLL()N_ = L*M^-1X = N_[0][0]Y = list(N_[0][1:])S = [N+i+1-E[i]*X/Y[i] for i in range(k)]s0 = int(S[0])from gmpy2 import iroot# for i in range(k):i = 0pibar = (s0+int(iroot(int(s0^2-4*nn[i]),int(2))[0]))//2pibar = (pibar >> 255) << 255print(pibar)R.<x> = Zmod(nn[i])[]from tqdm import *for j in trange(2^7-1,-1,-1): f = pibar + j*2^248 + x res = f.small_roots(X=2^248,beta=0.49,epsilon=0.013)if res:  p = f(res)  print(f(res))breakassert nn[i] % int(p) == 0q = int(nn[i] // int(p))print("[+] found p%d = %d"%(i,p))print("[+] found q%d = %d"%(i,q))

除了当 ”论文小子“，Tover 给出了另外一种更加优雅且自然的造格方法，2024网鼎杯半决赛的RSA加密分析 | Tover's Blog。并且他的解法适用于所有由题目代码生成的数据。——学过 HNP 的都知道这里边儿的门道有多深。

序列密码

task.py

import secrets, signalfrom utils import nbit, LFSR, NFSR, NOISEdefproof_of_work():import random, string, hashlib    ss = ''.join(random.choices(string.ascii_letters + string.digits, k=20))    sh = hashlib.sha256(ss.encode()).hexdigest()    print(f"|    sha256(XXXX + {ss[4:]}) == {sh}")    prefix = input("|    XXXX>")return prefix == ss[:4]if __name__ == "__main__":try:assert proof_of_work()        signal.alarm(666)        seed, mask = [secrets.randbits(12) | 2**(12-1) for _ in range(2)]        lfsr = LFSR(seed, mask)        noise = NOISE(lfsr)        seeds = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]        print(seeds)        masks = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]        print(f"|  {masks = }")        args = [(512, 128), (256, 256), (128, 512)]        n, m = args[0]        print("|  Good luck")for _ in range(n):            print("|  Menu:n|    [H]itn|    [S]tandn|    [Q]uit")            inp = input("|  inp>").lower()if inp == 'h':                lfsrs = [LFSR(seed, mask) for seed, mask in zip(seeds, masks)]                nfsr = NFSR(*lfsrs, noise=noise)                bits = nfsr.encrypt(b'x00'*m)                print(f"|  {bits.hex() = }")else:if inp == 's'and all(int(input('|  seed>')) == seed for seed in seeds):                    print('|  🏁', open('flag', 'r').read())break        print("|  Bye")except:        print("|  Nah")

utils.py

nbit = 128classLFSR:def__init__(self, seed: int, mask: int):        self.state = seed & (2**nbit - 1)        self.mask = mask & (2**nbit - 1)def__next__(self):        b = (self.state & self.mask).bit_count() & 1        self.state = ((self.state << 1) | b) & (2**nbit - 1)return bdef__call__(self, bits: int):        out = 0for _ in range(bits):            out = (out << 1) | next(self)return outclassNFSR:def__init__(self, lfsr0: LFSR, lfsr1: LFSR, noise: iter):        self.lfsr0 = lfsr0        self.lfsr1 = lfsr1        self.noise = noisedef__next__(self):        b0, b1 = self.lfsr0(1), self.lfsr1(1)        b = b0 ^ b1 ^ next(self.noise)return bdef__call__(self, bits: int):        out = 0for _ in range(bits):            out = (out << 1) | next(self)return outdefencrypt(self, msg: bytes):return bytes([m ^ self(8) for m in msg])defNOISE(lfsr: LFSR, p: float=2/3, prec: int=256):import secrets    t = 2**precwhileTrue:if lfsr(1):yield int(secrets.randbelow(t) / t > p)else:yield int(secrets.randbelow(t) / t <= p)

目前公开的情报：

  1. 密钥流输出收到两个 LFSR 和 一个 NOISE 控制，output = lfsr1^lfsr2^noise

  2. 极限可以获得 65536 个字节密钥流，但是可以选择：交互 512 次，每次搞 128 字节；交互 256 次，每次搞 256 字节；交互 128 次，每次搞 512 字节；（不过肯定得留一次交互去搞 flag）

  3. 每一次交互，两个 LFSR 的 seed 都会重置，但是 noise 不会，因此如果不存在这个 noise，每一次的 output 都是固定不变的。

  4. noise 的输出受独立的一个 lfsrn 影响，当 lfsrn 输出 1 时，noise 有 1/3 的概率为 1；当 lfsrn 输出 0 时，noise 有 2/3 的概率为 1；

  5. lfsrn 的 secret 和 mask 只有 12 比特，所以它的周期最大就是 2**12 = 4096比特=512字节

解题思路：

首先肯定要把这个 noise 消一消，毕竟周期故意给的很短了。不过爆破周期的时候，怎么判断这个周期正确与否呢？

考虑极端一点的情况，如果 lfsrn 决定了 noise 输出，假设周期是 100，那么第 0 个和第 100 个 noise 的输出就相等，如果把第 0 个输出和第 100 个输出异或，

由于 seed 固定，所以结果应该也是确定的，概率就是 100%。

如果重复收集多组这样的数据，也就是第一组的第 0 个异或第 100 个，第二组的第 0 个异或第 100 个，第三组的第 0 个异或第 100 个。。。。结果应该都是一样的。然后是第一组的第 1 个异或第 101 个，第二组的第 1 个异或第 101 个，第三组的第 1 个异或第 101 个。。。。结果也应该都是一样的。

我们创建一个列表，把所有组每个位置的结果求和，除以组数，放入对应位置，那么这个列表元素应该只有 1.0 和 0.0。

但如果选择的周期和实际周期不符，比如选了 99，那么

结果就受到    影响，有 1/2 翻转的可能（这里还是按照极端情况，按照 lfsrn 输出决定了 noise，并且 lfsrn 输出 0 和 1 的概率相等），那么同样按照上面的办法构造列表的话，这个列表的元素应该都在 0.5 附近。

那么再回到题目这种非极端情况，当周期正确时，两个 noise 的输出相同的概率只是比较大，所以列表里不会极端的只有 1 和 0，但是也会远离 0.5。于是正确与否，两者的区别可以用列表中元素的方差去表示。在爆破周期长度时，列表的方差越大，这个长度为周期的可能性就越大。【没有系统学过密码分析和信息论，只会用这样比较通俗的语言去描述，专业一点的术语应该涉及一些信息熵什么的】

所以先本地测试一下，周期正确的话这个方差大概会是多少。（这里为了组数多，选择 511 组交互，128 字节的方案）

先确定 nosie 的 seed 和 mask，把周期测出来先

import secrets, signalfrom utils import nbit, LFSR, NFSR, NOISEseed, mask = [secrets.randbits(12) | 2**(12-1) for _ in range(2)]       # 4096lfsr = LFSR(seed, mask)data = lfsr(10000)data = bin(data)[2:].rjust(10000,'0')for i in range(1,4096):if data[:100] == data[i:i+100]:        cycle = i        print("[+] cycle: ",cycle)break

然后获取 511 组数据

lfsr = LFSR(seed, mask)noise = NOISE(lfsr)value = [0]*1024times = [0]*1024bits = b""seeds = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]masks = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]for _ in range(511): lfsrs = [LFSR(seed, mask) for seed, mask in zip(seeds, masks)] nfsr = NFSR(*lfsrs, noise=noise) bits += nfsr.encrypt(b'x00'*128)bits = bin(int(bits.hex(),16))[2:].rjust(511*1024,'0')bits = list(bits)bits = [int(i) for i in bits]

然后计算正确周期时的方差

for i in range(511*1024-cycle): value[i%1024] += bits[i] ^ bits[i+cycle] times[i%1024] += 1prob = [0]*1024for i in range(1024): prob[i] = value[i]/times[i]from numpy import varprint(var(prob))

多次运行得到结果为

0.0035087152917410860.00358736491194218370.0035489397949916760.0034100473785452370.00364091432085767060.00366887548637987330.003419360973835426

基本大于 0.003

如果是错误周期，设置value[i%1024] += bits[i] ^ bits[i+cycle-1]

得到的结果为

0.00050342721356477680.000483127019651792860.00048960497313730150.00049176486346892270.00052699130223823710.00049873106542607750.00044184321417923760.0005145089290599805

明显不是一个数量级的

那么我们现在就可以确定周期了。【爆破的时候有一个小 trick，可以从 4096 倒着爆，能节省大量时间】

继续考虑极端情况，如果在确定周期后，noise 的影响可以完全消除，那么我们得到的 prob 列表里的应该是

，这里完全是线性的，就可以用 LFSR 的那个由 mask 构造的状态转移矩阵去表示

培训 PPT 里截的图

不过这里总共是四个部分复合的，所以需要略微改造一下这个矩阵。由于，所以

而 可以由上图中的由 构造的状态转移矩阵 T 进行幂次运算然后取最后一列得来。【——做过2021-西湖论剑-FilterRandom 都知道这里边儿的门道有多深】（https://jayxv.github.io/2020/12/18/密码学学习笔记之CTF）

由于两个 seed 拼在一起是 256 比特，因此我们可以选取 256 个输出，然后计算好所用到的 mask，构造矩阵 MASK 矩阵，满足 。然后计算 就行了。

讨论完极端情况让我们回到现实，现实就是我们得到的 prob 列表里面不是只有 0 和 1，大部分都是 0.55 和 0.44 这样的数（因为去掉 lsfrn 的影响后，两次 noise 输出相同，即不影响结果的概率为 5/9），那么我们暂且把大于 0.55 的设为 1（1的概率大），小于 0.44 的设为 0 （0 的概率大），其他就抛掉不要。然后随机从里面抽 256 个出来构造输出向量和MASK矩阵，计算 seed。（本地测了一下赢的概率蛮大的，如果不放心，可以抽 50 次，然后取出现次数多的）

本地测试代码

task.py

import secrets, signalfrom utils import nbit, LFSR, NFSR, NOISEdefproof_of_work():import random, string, hashlib    ss = ''.join(random.choices(string.ascii_letters + string.digits, k=20))    sh = hashlib.sha256(ss.encode()).hexdigest()    print(f"|    sha256(XXXX + {ss[4:]}) == {sh}")    prefix = input("|    XXXX>")return prefix == ss[:4]if __name__ == "__main__":try:#assert proof_of_work()#signal.alarm(666)        seed, mask = [secrets.randbits(12) | 2**(12-1) for _ in range(2)]        lfsr = LFSR(seed, mask)        noise = NOISE(lfsr)        seeds = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]        masks = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]        print(f"|  {masks = }")        print(f"|  {seeds = }")        args = [(512, 128), (256, 256), (128, 512)]        n, m = args[int(input('|  args>')) % len(args)]        print("|  Good luck")for _ in range(n):            print("|  Menu:n|    [H]itn|    [S]tandn|    [Q]uit")            inp = input("|  inp>").lower()if inp == 'h':                lfsrs = [LFSR(seed, mask) for seed, mask in zip(seeds, masks)]                nfsr = NFSR(*lfsrs, noise=noise)                bits = nfsr.encrypt(b'x00'*m)                print(f"|  {bits.hex() = }")else:if inp == 's'and all(int(input('|  seed>')) == seed for seed in seeds):                    print('|  🏁', open('flag', 'r').read())break        print("|  Bye")except:        print("|  Nah")

exp.sage（注意到代码中构造的 MASK 矩阵也就是getmatix 函数和上文分析中的略有一点不同，转置了一下，所以最后是 solve right，不是 solve left）

nn = []E = []k = 3N = min(nn)delta = k/(2*(k+1))epsilon = sqrt(5)*N^(delta-0.5)C = int(3^(k+1)*2^((k+1)*(k-4)/4)*epsilon^(-k-1))ci = [-(C*E[i])//(nn[i]+1) for i in range(k)]M = matrix(ZZ,[[1] + ci,    [0,C,0,0],    [0,0,C,0],    [0,0,0,C]])L = M.LLL()N_ = L*M^-1X = N_[0][0]Y = list(N_[0][1:])S = [N+i+1-E[i]*X/Y[i] for i in range(k)]s0 = int(S[0])from gmpy2 import iroot# for i in range(k):i = 0pibar = (s0+int(iroot(int(s0^2-4*nn[i]),int(2))[0]))//2pibar = (pibar >> 255) << 255print(pibar)R.<x> = Zmod(nn[i])[]from tqdm import *for j in trange(2^7-1,-1,-1): f = pibar + j*2^248 + x res = f.small_roots(X=2^248,beta=0.49,epsilon=0.013)if res:  p = f(res)  print(f(res))breakassert nn[i] % int(p) == 0q = int(nn[i] // int(p))print("[+] found p%d = %d"%(i,p))print("[+] found q%d = %d"%(i,q))0

有时候有非常好的结果

有时候也会比较烂，不容易分辨，甚至可能比特会全部反掉

所以比赛最后二十分钟好不容易本地调通了（最大的 bug 是 solve right 和 solve left 搞反了，这对于左右不分选手来说实在是太具有挑战性了），然后手动在那抽奖，1/4的概率，

截图留着纪念一下

决赛

piff

nn = []E = []k = 3N = min(nn)delta = k/(2*(k+1))epsilon = sqrt(5)*N^(delta-0.5)C = int(3^(k+1)*2^((k+1)*(k-4)/4)*epsilon^(-k-1))ci = [-(C*E[i])//(nn[i]+1) for i in range(k)]M = matrix(ZZ,[[1] + ci,    [0,C,0,0],    [0,0,C,0],    [0,0,0,C]])L = M.LLL()N_ = L*M^-1X = N_[0][0]Y = list(N_[0][1:])S = [N+i+1-E[i]*X/Y[i] for i in range(k)]s0 = int(S[0])from gmpy2 import iroot# for i in range(k):i = 0pibar = (s0+int(iroot(int(s0^2-4*nn[i]),int(2))[0]))//2pibar = (pibar >> 255) << 255print(pibar)R.<x> = Zmod(nn[i])[]from tqdm import *for j in trange(2^7-1,-1,-1): f = pibar + j*2^248 + x res = f.small_roots(X=2^248,beta=0.49,epsilon=0.013)if res:  p = f(res)  print(f(res))breakassert nn[i] % int(p) == 0q = int(nn[i] // int(p))print("[+] found p%d = %d"%(i,p))print("[+] found q%d = %d"%(i,q))1

这是一道有限域同构问题（finite field isomorphism problem）题目名字就是缩写反过来。。。

相关的基础知识可以参考寻找有限域同构映射这篇文章。

为了方便区分，我们设 函数用变量， 函数用变量 。

题目中 均是 上的不可约多项式，那么 ， ， 都是 个元素的有限域，并且同构

其中   为 的同构映射， 为 的同构映射。

满足

加密函数：

因此我们只需要求得其逆映射使得   即，可以得到。然后换到二元域上即可得到。

至于逆映射 怎么找？——打过 2023 miniL  的都知道这里边儿的门道有多深。

参考 https://github.com/XDSEC/miniLCTF_2023/blob/main/Official/Crypto.md 使用线代的办法找到逆映射 的各个系数

我们以此可以找到 的逆映射， 的逆映射，由于，所以我们对 做一个GCD 就可以得到 了。然后就跟 MiniFFI 这道题没什么区别了。【一行 GCD，狂砍 800 分】

nn = []E = []k = 3N = min(nn)delta = k/(2*(k+1))epsilon = sqrt(5)*N^(delta-0.5)C = int(3^(k+1)*2^((k+1)*(k-4)/4)*epsilon^(-k-1))ci = [-(C*E[i])//(nn[i]+1) for i in range(k)]M = matrix(ZZ,[[1] + ci,    [0,C,0,0],    [0,0,C,0],    [0,0,0,C]])L = M.LLL()N_ = L*M^-1X = N_[0][0]Y = list(N_[0][1:])S = [N+i+1-E[i]*X/Y[i] for i in range(k)]s0 = int(S[0])from gmpy2 import iroot# for i in range(k):i = 0pibar = (s0+int(iroot(int(s0^2-4*nn[i]),int(2))[0]))//2pibar = (pibar >> 255) << 255print(pibar)R.<x> = Zmod(nn[i])[]from tqdm import *for j in trange(2^7-1,-1,-1): f = pibar + j*2^248 + x res = f.small_roots(X=2^248,beta=0.49,epsilon=0.013)if res:  p = f(res)  print(f(res))breakassert nn[i] % int(p) == 0q = int(nn[i] // int(p))print("[+] found p%d = %d"%(i,p))print("[+] found q%d = %d"%(i,q))2


推荐站内搜索：最好用的开发软件、免费开源系统、渗透测试工具云盘下载、最新渗透测试资料、最新黑客工具下载……
ZhouSa.com