Imaginary CTF 2023 | Tan - crypto-writeup-public

print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024))
# -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714

#math

$C = \tan(M)$ が与えられている。

$\tan$ の周期が $\pi$ なので、 $\tan(M) = tan(M' + \pi k)$

$\tan$ 外して $C' = \arctan(C) = M' + \pi k$

不明な値は $M', k$ で係数 $1, \pi$ 。これをLLL とかで求めたら良い

$(M', k, 1) \begin{pmatrix} 1 & 0 & 1 \ \pi & 1 & \pi \ -C & 0 & 0 \end{pmatrix} = (0, k, M' + k\pi)$

$k \approx 2^{1024}$ で $M' \simeq \pi$ 。このままだと1列目（一番左の列）だけが小さいので、ここを $K \approx 2^{1024}$ でスケーリングして大体全ての列が $k$ or $k$ くらいの大きさになるようにする

なんか微妙に誤差があるけど解ける

C = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714
C = arctan(C)
P = pi.n(1024)

K = 2**1024

# v = [M', k, 1]
M = matrix(QQ, [
    [1*K, 0, 1],
    [C*K, 1, P],
    [P*K, 0, 0],
])

L = M.LLL()

m = int(abs(L[0][-1]))
print(bytes.fromhex(hex(m)[2:]))

めちゃ久しぶりに純LLLさわった。Inequality ... は整数しか扱えないので

https://github.com/maple3142/My-CTF-Challenges/tree/master/ImaginaryCTF%202023/Tan