2025-R3CTF-r3tauq-wp-crypto

最近过得相当摸，正好这次R3CTF出了一道r3tauq来玩，写篇wp顺便水水博客(｡・ω・｡)

r3tauq

题目

题目描述：

1
2
3

As r3girl ventures deeper into the Crypto Block, she discovers an area operating under bewilderingly complex rules. The very essence of this space feels… different, almost alien. The familiar tools and understandings of the cyber-metropolis seem inadequate here.

"Too quat 4 me," she hears someone whisper, sobbing softly.

题目：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag
import string

p, q, r, x, y = [getPrime(256) for _ in range(3)] + [getPrime(256) << 128 for _ in range(2)]
secret = "".join([choice(string.ascii_letters) for _ in range(77)])
PR.<i, j, k> = QuaternionAlgebra(Zmod(p*q), -x, -y)
print("🎁 :", [p*q] + list(PR([x+y, p+x, q+y, r])^bytes_to_long(777*secret.encode())) + [AES.new(key=md5(secret.encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag).hex()])

🎁 : [9179146701312781699176828536776206089522408831979885137804817119605132824670673896777591947510882312771183820299882701673215709151977703193903616420702637, 188706257709485662889897107268939642280152413424908152855562194130538159229344166143895172825675717408926036013540426973122050052311570664470631060866326, 2682712522093551545327045002884555242296600010649692520986985330242254238488174707977608269114146421801908861117953931511928486194314901772151783668459458, 3450486865638869884029607240891787866556930082379406388731244160308196118526545881858756124529382085993846169512275853780392762817972043910244447967967496, 3978613946907291563196945341686358146709099241100401211979238259502207240204268447607153317575767659025152104242438128290935255838611081957683034411586841, 'fb459084099c44b75f2a1c256b604b187ab4877e78ea2b9fc5320471c319f9063428c72002310df82e1a424425189d0dabebe601031a']

这是一个很直白的四元数题目，其流程为：

生成五个256bit的随机素数$p,q,r,x,y$，并将$x,y$左移128bit，记$n=pq$
生成一个长度为77并由大小写字母组成的字符串作为secret，
生成$Z_{n}$下的四元代数，满足$\mathbf{i}^2=-x,\mathbf{j}^2=-y$
记$\mathbf{g} = (x+y) + (p+x)\mathbf{i} + (q+y)\mathbf{j} + r\mathbf{k}$，计算$\mathbf{g}’ = \mathbf{g}^{s}$，其中$s$为secret串重复777次对应的大整数

给出$n,\mathbf{g}’$，需要求解出secret从而解密AES得到flag。

思路

part 1 : 恢复$\mathbf{g}$

求解$s$似乎是一个四元数的dlp问题，然而对于dlp来说，题目缺少了初态$\mathbf{g}$，因此需要先想办法恢复$\mathbf{g}$。参考这个题目得知四元数的幂递推存在性质如下：

$\begin{cases} a_n = \displaystyle\sum_{i = 0}^{\lfloor\frac{n}{2}\rfloor} {n \choose n - 2i} \cdot a^{n - 2i} S^i \\ b_n = b X \\ c_n = c X \\ d_n = d X \end{cases} \quad , \quad \begin{cases} S = -(b^2 + c^2 + d^2) \\ X = \sum_{i = 0}^{\lfloor\frac{n - 1}{2}\rfloor} {n \choose n - 2i - 1} \cdot a^{n - 2i - 1} S^i \end{cases}$

这里主要利用$b_n,c_n,d_n$的递推，可以看出其递推均为初态乘同一个系数$X$，因此可以构造出等式：

$\frac{b}{b_n} = \frac{c}{c_n} = \frac{d}{d_n}$

由于模数$n$为512bit，初态系数$b=p+x,c=q+y,d=r$均较小，因此可以LLL恢复，界稍微有点紧，可以爆破几bit解决，此时相当于恢复了初态$\mathbf{g}$的后三项$p+x,q+y,r$。

part 2 : 恢复$p,q,x,y$

在拥有$p+x,q+y$以及$n=pq$的情况下，这个问题是很经典的$p$低位泄露问题，由于$x,y$均左移了128bit，所以恰好泄露一半，所以依然需要爆破几bit，此时可分解模数$n$得到$p,q$，也自然得到了$x,y$。

part 3 : 恢复$s$

得到$\mathbf{g}$之后问题完全转化到了一个四元数的dlp问题，而对于该题四元代数下的四元数$a + b\mathbf{i} + c\mathbf{j} + d\mathbf{k}$来说，其可以映射到如下矩阵：

$M = \left(\begin{matrix} a & -bx & -cy & -dxy \\ b & a & -dy & cy \\ c & dx & a & -bx \\ d & -c & b & a \\ \end{matrix}\right)$

因此可以将$\mathbf{g}$与$\mathbf{g}’$分别映射到矩阵$L$与矩阵$L^s$，此时四元数的dlp问题变成了矩阵dlp问题。

由于本题选用的数据恰好没有一次域$GF(p),GF(q)$下的特征值，因此无法利用jordan化将问题转化为求解方程组，一个简单的思路是直接利用矩阵行列式将问题转化为$GF(p),GF(q)$下乘法群的dlp问题，由于$p,q$均为256bit，因此需要利用cado-nfs求解出$s\%(p-1), s\%(q-1)$并CRT起来，大约可以获得有500bit出头的信息。

也可以利用扩域上的部分光滑因子扩大能获得信息的bit数量。

part 4 : 恢复secret

由于secret是由大小写字母组成的串，因此可以线性处理一下将所有字符均值减小，最后使用格规约出secret。

exp

exp和英文wp可以在这里找到。

其他

题目名字看上去很奇怪，是因为为了跟上队形把”quater”倒了过来，就正好变成带”r3”的”r3tauq”了:3