Hibiscus
为鸽到2025年的nctf2024命制了三道Crypto题，下述为官方Writeup。
sign
这是恢复互联网的密钥，密码是实时生成的三万个随机数。
解析
签到题，主要是两部分：MT19937的逆向、和基于AGCD问题的FHE（全同态加密）。
显然我们的目标就是恢复string。而题目对string实行了逐字节加密，具体地：
1
2
3
4
5
6
7
8
9for m in string:
f = FHE()
s = long_to_bytes(Random().getrandbits(20000))
for i in s[4:]:
Keys.extend(f.encrypt([i]))
for i in s[:4]:
Keys.extend(f.encrypt([i * (m & 0x03) % 0x101]))
m >>= 2FHE、使用Random().getrandbits(20000)拿到了20000位随机数，将随机数的后19968位加密后直接输出，前32位用于和string的当前字节m按一个自定义规则进行加密。
python中getrandbits(n) 在 \(n
> 32\)
时会多次调用getrandbits(32)，将新随机数拼接在既有随机数的高位。如此，显然我们需要利用这个大随机数的后（低）19968位来预测前（高）32位的值。
已知完整的一组state的情况下随机数预测部分的资料/既有脚本都比较多实在不行问deepseek，这里不再赘述。任务由此变成了解密FHE。
FHE（全同态加密）相关：对于一个加/解密系统 \((E,D)\) 和其域下任意的 \((m_i,c_i)\)，
若其满足 \(E(\sum_{i=1}^{n} m_i) = \sum_{i=1}{n} c_i\) 且 \(D(\sum_{i=1}^{n} c_i) = \sum_{i=1}^{n} m_i\)，则称其是（完全）加法同态的；
若其满足 \(E(\prod_{i=1}^{n} m_i) = \prod_{i=1}{n} c_i\) 且 \(D(\prod_{i=1}^{n} c_i) = \prod_{i=1}^{n} m_i\)，则称其是（完全）乘法同态的；
若 \((E,D)\) 既是加法同态又是乘法同态的，则称之为全同态加密系统。
再观察FHE的加密逻辑：
1 | class FHE: |
初始化时，其会选定一个质数 \(p\)
，随后生成了一个公钥集 \(\{pk_i\}\)，其中 \(pk_i = pa_i + 256*b_i\)，\(\log_{2}a_i \approx 177\)，\(\log_{2}b_i \approx 17\)。
每次加密 \(m <
256\)，选择公钥集的一个随机小系数（各维度不大于16）的线性组合，与
\(m\) 求和得到密文。
首先考虑解密逻辑：AGCD-FHE的解密关键点在于获得私钥 \(p\)。
获得 \(p\) 后，对于任意密文 \(c = k_1p + 256*k_2 + m\)，\(m < 256\)、\(256*k_2 < p\)时不难证明存在 \(m \equiv (c \bmod p) \bmod 256\)。
此处不难发现FHE（全同态加密）性质的具体体现：
记加密函数为 \(E\)，显然 \(Z_{256}\) 下 \(E(\sum_{i=1}{n} m_i) = \sum_{i=1}{n} c_i\)。解密亦然，在 \(n\) 不太大时近似认为其是完全加法同态的。
同理可知其也存在乘法同态，但基于AGCD的FHE在进行密文乘时误差累积非常快，因而某种意义上只能算“部分”乘法同态。相比之下如RSA就满足完全乘法同态。
而对AGCD-FHE的攻击可以通过构造格进行。
AGCD(Approximate Greatest Common Divisor)/近似最大公约数问题简介：
已知 \(\{pq_1 + e_1,pq_2 + e_2, \cdots, pq_n + e_n\}\)，满足 \(e_i << p\)， 求 \(p\)。
可以发现其相较传统的GCD问题“无非”就是多了误差 \(e_i\)，但这会让求最大公约数的经典算法全部失效，必须另辟蹊径。
以上述AGCD的参数名为例：
记 \(x_i = pq_i + e_i\)，注意到存在
\(x_0q_i - x_iq_0 = e_0q_i -
e_iq_0\)，其中 \(\{x_i\}\)
均已知，\(\{q_i\}\) 是未知的整数，\(\{e_i\}\) 是未知的小整数。
构造格的矩阵等式如下：
\(\begin{bmatrix}q_1 & q_2 & \cdots & q_n & q_0 \end{bmatrix} \cdot \begin{bmatrix} \\ -x_0 \\ & -x_0 \\ && \ddots \\ &&& -x_0 \\ x_1 & x_2 & \cdots & x_n & 2^{\rho + 1} \end{bmatrix} = \begin{bmatrix} e_1q_0 - e_0q_1 & e_2q_0 - e_0q_2 & \cdots & e_nq_0 - e_0q_n & q_{0}2^{\rho+1} \end{bmatrix}\)
显然锚定的是格中的短向量（\(2^{\rho +
1}\) 用于配平），对格进行规约即可还原出 \(q_0\)，随后计算 \(e_0 \equiv x_0 (\bmod q_0)\)、\(p = \frac{x_0-e_0}{q_0}\)。
获得 \(p\)
后，完成对加密后数字的解密，随后MT19937逆向+预测随机数后，梳理下后续的模乘逻辑等步骤就都比较普通了。
完整exp
1 | # sage |
Arcahv
Delightful.
解析
题如其名 —— Arcahv，聚合，大杂烩。
核心考点包括 RSA LSB Orcale Pro Max版，LCG，Coppersmith。
RSA LSB Orcale
最简单的RSA LSB Orcale应是RSA Parity
Orcale（奇偶Orcale，每次解密返回结果的奇偶性），此时攻击所需要的次数为
\(\lceil \log_{2}N \rceil\)。
同样地，如果LSB Orcale每次返回的值是解密结果对 \(2^{k}\) 取模的结果，则解密所需要的次数应为
\(\lceil log_{2^{k}}N = \lceil
\frac{log_{2}N}{k} \rceil\)。
本题首先大幅约束了解密次数，旨在考验各位师傅对于 Parity Orcale的理解和数论推导。
Parity Orcale的核心就是“溢出”导致的余数变化，以及我们根据RSA的乘法同态能构造出使解密结果为 \(Cm (\bmod N)\) 的密文。
通过在 \(Z_{p}\) 下将密文乘以 \(C^{e}\)，我们解密得到的明文即为 \(m^{'} = Cm \bmod N\)。显然存在等式
\(m^{'} + kN =
Cm\)。本题中由于我们可以得到 \(m^{'} \bmod 256\)，因而亦令 $ C =
256$。由此，
- 若 \(k = 0\)，由于 \(256m \equiv 0 (\bmod 256)\)，则显然 \(m^{'} \bmod 256 = 0\)。
- 若 \(k \neq 0\)，则 \(m^{'} \equiv kN (\bmod 256)\)。又因为
\(N\) 必为奇数，\(gcd(N,256) = 1\)，因而 \(Z_{256}\) 下 \(N^{-1}\) 存在，即可以计算 \(k \equiv m^{'}N^{-1} (\bmod
256)\)。
又 \(m^{'} \in (0,N)\)，推定 \(256m = m^{'} + kN \in (kN,(k+1)N)\)，即
\(m \in
(\frac{k}{256}N,\frac{k+1}{256}N)\)。
重复上述步骤（每次将上一次得到的 \(m\) 在 \(Z_{N}\) 下乘以 \(256\)），每次可以将原明文 \(m\) 的取值范围缩小至原来的 \(\frac{1}{256}\)，近似于获得了高8位的信息。
同时，题目中原明文是 \(p \in
(0,2^{1024})\)，在交互次数有限的情况下，应选择跳过前127次交互（因为已知这127次交互必定会得到
\(k = 0\)；注意明文仍需直接乘以 \(2^{1016e} \bmod N\)）。最终我们近似可以得到
r1.p 的高600位信息。
LCG
LCG部分是非常经典的PRNG逆向。
本题中LCG没有给出任何参数而且还被玩坏了，但难度依然不大。唯一稍微有些迷惑性的点就是不会告诉你随机数的分隔点在哪里，但通过简单分析乱糊+瞎猜和获得随机数后的存在性校验也不难从一堆unsigned long long里得到五个LCG的连续输出随机数。
得到随机数后，由于LCG的参数 \((p,a,b)\)
均未知，因此需要通过这些随机数来从前向后逐个恢复，这里只讲恢复 \(p\)。
记恢复的随机数序列为 \(\{x_i\} (i \in
[0,5))\)，
\(x_{i+1} \equiv ax_i + b \bmod p, x_{i+2}
\equiv ax_{i+1} + b \bmod p \rightarrow x_{i+2}-x_{i+1} \equiv
a(x_{i+1}-x_i) \bmod p\)。
再记 \(x_{i+1}-x_{i} = D_{i} (i \in
[0,4))\)，既有 \(D_{i+2} \equiv
aD_{i+1} \bmod p, D_{i+1} \equiv aD_i \bmod p \rightarrow D^{2}_{i+1}
\equiv D_{i+2}D_{i} \bmod p\)，即 \(D^{2}_{i+1} - D_{i+2}D_{i} \equiv 0 \bmod
p\)。
对上式取 \(i =
0,1\)，得到的二式取最大公约数（即 \(gcd(D^{2}_{2} - D_{3}D_{1}, D^{2}_{1} -
D_{2}D_{0})\)），即有很大概率得到 \(p\)。
可以发现5个连续随机数是LCG参数完全未知时下还原 \(p\) 所需的最小数目，因此构造的最大公约数经常会掺杂一些其它的小因子，简单
factor一下的成功率还是不低的。
得到 \(p\)
后依述推导过程中的部分式即可得到 \(a,b\)，过程不再赘述。
至于被“玩坏”的LCG，注意到作为种子的AES密钥key只有128位长，而LCG的
\(p\)
为1024位，因此只需一直向前逆向，即可认为第一个遇到的不大于128位的数就是key。
相当于整道 Arcahv 两次应用到了“小明文攻击”的思想，即已知明文的部分信息的前提下攻击可以另辟蹊径，
同时也强调了密码学应用中pad的重要性
Coppersmith
RSA LSB Orcale中并没有获得 \(p\)
的全部信息，但已知其高位的情况下即可通过 Coppersmith 对 \(N\)
进行分解，具体构造方法也非常简单而且没有技巧，同样不再赘述。
完整exp
1 | #sage |
绮云
花灯百盏遥遥一线牵
解析
某种意义上的水题，RSA双Orcale(N-Orcale + fault injection orcale) 和简单的ECDSA守个门。
笔者设想过此类Encryption Orcale有一些偏现实的应用场景，比如存在一个小型的加密器，其提供由一个既定私钥 \(d\) 生成大量公钥对 \((N,e)\) 对输入的任意消息进行加密的功能，同时其并不会主动暴露自身公钥对（相当于攻击者/加密者只能得到密文，
唯密文攻击Plus）。攻击者可以对其进行 Fault injection，而现实中对于小型加密设备，通过侧信道攻击等方式同样也可以获取 \(e\)。
RSA N-Orcale
首先我们希望在没有公钥的情况下获得 \(N\)。
传递 \(m \in \{2,2^2,2^3,2^4,\cdots\}\)
，收集加密的密文。
设 \(m_i = 2^{i} (i \in Z_+)\)，显然
\(m_i = m_1^{i}\)。
又， \(c_i \equiv m_i^e (\bmod
N)\)，推定 \(c_1 \equiv m_1^e (\bmod
N)\)，结合上式可得 \(c_1^i - c_i \equiv
0 (\bmod N)\)，即 \(c_1^i - c_i = kN (k
\in Z)\)。
在加密了足够多的 \(m_i\) 后，对 \({c_1^i - c_i}\)
求其最大公约数，即可有很大把握得到 \(N\)。
RSA N-Orcale步中，由于 \(e < 2^{2048}\)，所以建议选择传输interfere位为2048。尽管单从 N-Orcale 这一步来看没有区别，但如此可以在解出 \(N\) 后立即获得 \(m^{e} \bmod N\) 的确值
进而避开了一些奇奇怪怪的if-elif的纠缠
RSA Fault injection
单个RSA Encryption Orcale的剩下部分就是比较经典的RSA Fault
injection攻击，虽然攻击目标不一样（从传统fault的针对私钥 \(d\) 变为现在针对公钥 \(e\)），但数学逻辑完全相同。具体原理不再赘述（既有wp太多了）。
格攻击
但至此我们得到的依然只是大量的公钥对 \((N,e)\)，题目中的 \(d\) 并不能通过 Wiener's
Attack获得（应用的私钥 \(d =
x^{4}\) 仍有928位）。
注意到每次RSA生成公钥对对应的私钥是相同的，由RSA的基本关系式可以列出：\(e_{i}d \equiv 1 \bmod
\varphi(N_{i})\)
进而，\(e_{i}d + k_{i}\varphi(N_{i}) - 1 =
0\)，得到 \(e_{i}d + k_{i}N_{i} - C_{i}
= 0\)，其中 \(C_{i}\) 的数量级与
\(k_{i}p_{i}\) 相当。
又，RSA中存在 \(e_{i}d \approx |k_i|(N_{i})\)（Wiener's attack 连分数逼近的基础），因此 \(k_{i} \approx \frac{e_{i}d}{N_{i}}\)，结合 \(e_{i}d \equiv 1 \bmod \varphi(N)\)，可以认为 \(k_{i}\) 数量级与 \(d\) 相当。
结合本题的实例，\(p_{i}\) 约为1024位，\(d_{i}\) 为928位，因而 \(C_{i}\) 应在1950位左右，满足明显小于 \(e_{i}\)、\(N_{i}\) 的条件。 考虑下述行向量的线性组合：
\(\begin{bmatrix} k_{1} & k_{2} & \cdots & k_{n} & d\end{bmatrix} \cdot \begin{bmatrix} N_{1} \\&N_{2} \\ && \ddots \\ &&& N_{n} \\ e_{1} & e_{2} & \cdots & e_{n} & K \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} & \cdots & C_{n} & Kd \end{bmatrix}\)
可以认为，等号右侧的向量是该矩阵构成的格中的短向量。因此由该矩阵构造格 \(L\)，对之进行规约即可从中提取出私钥 \(d\)。
关于配平和格维度的选择，笔者建议 \(K = 2^{1024}\)，\(n \geq 10\)。
同时本题也因为格维度的问题非常耗时，众所周知Fault injection交互的时间开销非常大，而本题中需要将这个步骤重复数遍，因而出现了大半个小时出flag的奇观，笔者最后懒得改题了，在这给各位师傅磕一个
ECDSA
这部分就没什么了为了让各位拿flag更舒服点，ECDSA类的。唯一的小插曲是需要进行非常轻度的爆破，不过每次交互
\(\frac{1}{256}\)
的概率出flag也不算太低（？）sign方法都留给各位了，不是坑
完整exp
远程交互时本exp耗时预计为45-90分钟。时间开销主要在每次 fault injection 获取 \(e\) 时都需要进行2048次交互才能得到结果，本应微不足道的ping、计算耗时等累加数万次后耗时依然极为可观
在这里给因为交互压力没做出来的师傅磕一个
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
__import__('os').environ['TERM'] = 'xterm'
from pwn import *
from sage.all import *
from time import time
from hashlib import sha256
io = remote('39.106.16.204',10645)
# io = process(['python3','task.py'])
nls = []
els = []
recv_hexint = lambda: int(io.recvline().strip().decode(),16)
t0 = time()
for _ in range(10):
io.sendlineafter(b'option:',b'1')
#decipher N via GCD
numls = []
for i in range(9):
msg = int(1 << (i + 1)).to_bytes(2,'big')
io.sendlineafter(b'exit:',b'e')
io.sendlineafter(b'message:',msg.hex().encode())
io.sendlineafter(b'interfere?',b'0')
io.recvuntil(b'Result:')
numls.append(int(io.recvline().strip().decode(),16))
gcdls = []
for i in range(1,9):
gcdls.append(numls[0] ^ (i+1) - numls[i])
n = gcd(gcdls)
nls.append(n)
print(f'n #{_} = {n}')
#decipher e via fault injection of e
orcale_msg = 3
io.sendlineafter(b'exit:',b'e')
io.sendlineafter(b'message:',int(orcale_msg).to_bytes(1,'big').hex().encode())
io.sendlineafter(b'interfere?',b'2048')
io.recvuntil(b'Result:')
basis = recv_hexint() * pow(orcale_msg, -2^2048, n) % n #basis, = pow(m,e,n)
e_rng = [0] * 2048
for i in range(2048):
io.sendlineafter(b'exit:',b'e')
io.sendlineafter(b'message:',int(orcale_msg).to_bytes(1,'big').hex().encode())
io.sendlineafter(b'interfere?',str(i).encode())
io.recvuntil(b'Result:')
temp = recv_hexint()
multiplier = pow(orcale_msg,2^i,n)
if temp == basis * multiplier % n: #0 -> 1, original = 0
e_rng[i] = 0
else: #1 -> 0, original = 1
assert temp == basis * pow(multiplier,-1,n) % n #ensure
e_rng[i] = 1
e_res = int(''.join(str(i) for i in e_rng)[::-1],2)
assert pow(orcale_msg,e_res,n) == basis
els.append(e_res)
print(f'e #{_} = {e_res}')
print(f'Time elasped: {time()-t0:.2f}s')
io.sendlineafter(b'exit:',b'')
const = 2^1024
mt = matrix.diagonal(ZZ,nls + [0]).dense_matrix()
mt[-1] = els + [const]
mt = mt.LLL()
temp = abs(mt[0,-1])
assert temp % const == 0
d = ZZ(temp / const)
x = d.nth_root(4)
E = EllipticCurve(Zmod(0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF),[0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC,0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93])
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
assert E.order() == n
G = E((0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7,0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0))
m0 = int.from_bytes(sha256('nctf2024-00'.encode()).digest(),'big')
while True:
k = int(time() * 1000) #should be smaller than n
P = k * G
r = int(P.xy()[0]) % n
s = (pow(k,-1,n) * (m0 + x*r)) % n
if r != 0 and s != 0:
break
send = f'{r} {s}'.encode()
while True:
io.sendlineafter(b'option:',b'2')
io.sendlineafter(b':',send)
msg = io.recvline()
if b'flag' in msg:
print(msg.decode())
break
io.close()