珠海端茶倒水一日游(bushi)
2025年湾区杯糊出来几道题的Writeup,以及做prng题有感。
Writeup
prng
题目
解析
题目实现了一个LCG变种的PRNG(伪随机数生成器),其状态间的关系如下:
$ s_{i+1} s_{i}^{2}a + b ^{512} $
难点有二:
- 其只给出了PRNG的两个状态,要求逆向出seed;
- 对于PRNG的每个状态,其都随机抹去了0.19倍总位数的信息(此处体现为
\(s_{1}\)、\(s_{2}\)、\(a\)、\(b\)
中各97个
?
。
由于被抹去的位数分布不均,因而很难用传统的代数分析方法攻击之包括第一反应的格攻击。
因此此处需要用到特技“逐怨”处理之——具况见下方exp和解析。
大致思路:逐未知位爆破,利用位运算的截断特性不断校验、排除“缓存”的可能性。
exp
赛时紧张,exp近乎于缝缝补补能跑就行,至于语言规范什么的看个乐呵就好awa
一段(Python):
1 | #python3 |
二段:
1 | #sage |
闲谈“逐怨”
数学基础
狭义上(即部分题目的“实例”),若 \(Z_{2^{p}}\) 下 \(f(x_{1},x_{2},\cdots,x_{n}) = 0\) 成立,则 \(Z_{2^{q}}\) 下 \(f(x^{'}_{1},x^{'}_{2},\cdots,x^{'}_{n}) = 0\) 亦成立,其中 \(q < p\),\(x^{'}_{1} \equiv x_{1} \bmod 2^{q}\)。
广义上,对阶为 \(p\) 的群 \(G\) 下的元素 \(x_{i} (i \in \[1,n\])\),考虑将 \(x_{i} \rightarrow x^{'}_{i}\)
,即将之映射至另一个群 \(G^{'}\)
上,且 \(G^{'}\) 的阶 \(p^{'} | p\),使得 \(ord(x^{'}_{i}) \equiv ord(x_{i}) \bmod
p^{'}\)。
假设 \(G\) 和 \(G^{'}\) 对群上运算 \(f\) 是同构的,则存在 \(ord(f(x_{1},x_{2},\cdots,x_{n})) \equiv
ord(f(x^{'}_{1},x^{'}_{2},\cdots,x^{'}_{n})) \bmod
p^{'}\)。
虽然推广的结论
非常不讲人话,但其为这一攻击的拓展运用提供了理论基础。
算法实践
“逐怨”的数学基础各异,但其算法流程上是大同小异的。此处以上述情景为例: