ImageinaryCTF 2023 Crypto

出了两个中等难度

tan

题目

tan(m).n(1024)

还原m

先用内置函数arctan还原一个初始解$\phi$

周期性得

$$m=k*\pi+\phi$$

满足这个关系，我一开始也是用格子解的，忘记给第一行加平衡向量了。就稍微弄的有点复杂，先把小数均扩大为整数，因为有小量误差，然后求解二元cop。也算是出了。格子还是不熟练呀，总之就是理解不到位，脚本小子当多了。

贴一下格解法

$$M=\begin{pmatrix}1&&\\\phi&1&\\\pi&&1\end{pmatrix}\\ \begin{pmatrix}-m&1&k\end{pmatrix}*M=(0,1,k)$$

第一行做平衡，相当于最大的满足等式，从而出现目标解k

c = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714
c = arctan(c)

pie=pi.n(1024)

L = matrix(QQ, [[1, 0, 0], [c, 1, 0], [pie, 0, 1]])
L[:, 0] *= 2**1024
k=int(L.LLL()[0][-1])
long_to_bytes(int(k*pie+c))

Wasteful

这个就比较简单，但是没有烂掉

已知$e_{slow},n,c$

$$e_{slow}=e_{fast}+A*phi\\A:683bits\\phi:2048bits\\e_{fast}:1024bits$$

这里很明显

$$A=e_{slow}//n+1，可以直接解出来$$

继续变换

$$e_{slow}//A=e_{fast}//A+n-(p+q)+1\\ n-e_{slow}//A\approx p+q-e_{fast}//A$$

这里$e_{fast}//A$相比于其他值显得很小，所以可得到p+q的近似解，通过z3求解，得到p的近似解，然后就是cop已知p高位的那一套

exp也不贴了，看个解题思路就行

SUS

没出，觉得很nb，来复现一下

题目

def sus(sz, d):
    while True:
        p = getPrime(sz)
        pp = sum([p**i for i in range(d)])
        if isPrime(pp):
            return p, pp
sus(512,3)
r=getPrime(512*3)
n=p*q*r

目标分解n

$$q=p^2+p+1\\ n=p*(p^2+p+1)*r$$

r是p^3^一样大小，很明显这里cop什么的都用不了

比赛的时候啥都想到了，包括关键的式子

$$p^3-1=(p-1)*(p^2+p+1)$$

然后在构建一个群，它的阶为$p^3-1$这里卡住了

$$假设群G的阶为(p^3-1)\\ q=g^n=g^{p*(p^2+p+1)*r}\\ q的阶为p-1，后续总有利用点$$

看了wp，突然就想到了，degree为3的多项式商环的阶不就是p^3-1

狠狠学习

有了这个，求解思路就很清晰了

$$f(x)=x^3+a*x^2+b*x+c\\ \mathbb{R}=\mathbb{Z}_n[x]/f(x)\\ \mathbb{K}=\mathbb{F}_p[x]/f(x)$$

随机生成多项式f(x)，多项式环K的阶即为（p^3-1）。

对于环K上的任意元素a,a^n^ 的order为p-1，所以a^n^系数为(u,0,0)这样的形式。

所以对环R上的任意元素经过n次方操作后的一次项或者二次项的系数gcd一下就得到n