LLL practice 2

이어서 CCE2023에 출제되었던 the miracle문제로 연습을 해보자.
다른 부분들은 이 글의 목적에 있어서 지엽적이므로 LLL과 관련 있는 부분만 작성하겠다.
문제 상황의 식은 다음과 같다.

$2^{896}state + output = rand + pk$

여기서 $state$와 $rand$는 128bit이므로 896bit인 $output$과 512bit인 $p$에 비해 매우 작다. 따라서 $2^{896}, output, p$에 대하여 LLL알고리즘을 사용할 수 있다.

$\begin{bmatrix}output&1&0\\2^{896}&0&1\\p&0&0 \end{bmatrix}$

위와 같이 행렬을 구성하고 LLL을 사용한다면, 결과를 $M$이라 했을 때, $M[i][2]$의 값이 $2^{896}$에 곱해진 수일 것이며, $i$의 경우, $M[i][1]$이 1인 $i$를 찾으면 된다. ($output$은 1번 곱해졌기 때문)

실제로 결과를 보자.

첫 번째 행이 찾고자 하는 행임을 알 수 있다. 잘 활용만 한다면 정말 사기적인 기술인 것 같다..