LLL practice 3

3번째로 연습할 문제는 ImaginaryCTF2023에 출제되었던 tan이라는 문제이다. 문제만 봤을 때, LLL알고리즘을 사용할 수 있을지 바로 알아채는 것이 어려웠고, 나중에서야 the miracle과 같은 형태임을 깨달았다.

문제 코드를 보자.

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

$tan(flag)$를 알려준게 전부이다. 주어진 소수를 $output$이라고 하면 다음과 같은 식이 성립한다.

$arctan(output) + kπ ≈ flag$

여기서 $arctan(output)$와 $kπ$는 소수이고 $flag$는 정수이다. 따라서, 소수인 $arctan(output)$와 $kπ$가 의미를 가지려면 매우 큰 정수를 곱해줘야 한다. 적당히 $2^{1024}$를 곱해보자. (위의 식은 =이 아닌 ≈이므로 $2^{1024}$를 곱해서 발생하는 작은 오차는 $small$이라고 두었다.)

$2^{1024}arctan(output) + 2^{1024}kπ = 2^{1024}flag + small$

위의 식에서 $flag$와 $small$은 $2^{1024}$에 비해 매우 작다고 예상할 수 있고 $2^{1024}arctan(output)$는 한 번만 곱해진 형태임을 알 수 있다.

따라서 the miracle과 비슷하게 행렬을 다음과 같이 구성할 수 있다.

$\begin{bmatrix}2^{1024}arctan(output)&1&0\\2^{1024}&0&1\\2^{1024}π&0&0 \end{bmatrix}$

위와 같이 행렬을 구성한다면, 두 번째 요소가 1인 행의 마지막 요소가 $flag$가 될 것이다.

exploit code

output = atan(-0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714)

M = matrix([
    [int(output*2^1024), 1, 0],
    [2^1024, 0, 1],
    [int(pi*2^1024), 0, 0],
])

for r in M.LLL().rows():
    if abs(int(r[1])) == 1:
        print(abs(int(r[-1])).to_bytes(64, "big").decode())
        print(r)

the miracle과 결과가 유사함을 볼 수 있다. $tan$값만 주어진 상황에서 LLL로 풀 수 있다는 것이 신기하다..
사실 이 문제의 writeup과 다른 형태로 행렬을 구성했지만, 사실상 의미는 똑같다. 나에게 익숙한 형태의 꼴을 찾아서 그것을 계속 사용하는게 좋을 것 같다.