LLL Algorithm

LLL Algorithm

Orthogonality

SVP(Shortest Vector Problem)는 $L$ 위의 가장 짧은 벡터 $λ_1$을 구하는 문제로 NP-Hard이다. SVP를 푸는 가장 직관적인 답은 기저의 수직성(Orthogonality)를 생각하는 것이다. 왜냐하면, 다음이 성립하기 때문이다.

기저 $B$가 orthogonal하고, $\lambda_1 = \sum a_ib_i$라고 하자. 이 때 일반성을 잃지 않고 $a_i \neq 0$이라고 하자. (즉, coefficient가 nonzero인 기저만 생각하자).

\[\begin{aligned} \lVert \lambda_1 \rVert^2 &= \lVert a_1b_1 + ⋯ + a_kb_k \rVert^2 \\ &=a_1^2 \lVert b_1 \rVert^2 + ⋯ + a_k^2 \lVert b_k \rVert^2 \\ &\geq a_i^2 \min \lVert b_i \rVert^2 \\ &\geq \min \lVert b_i \rVert^2 \end{aligned}\]

2번째 줄을 보면, basis가 orthogonal하기 때문에 벡터의 길이(norm) 계산이 독립적으로 분리된다. 이를 통해 기저가 orthogonal하면 SVP문제를 풀 수 있음을 확인할 수 있다.

그렇다면, 격자(Lattice)를 orthogonal하게 만들기 전에 일반적인 벡터 공간에서 수직인 기저를 아주 효율적으로 찾는 방법인 Gram-Schmidt Orthogonalization부터 살펴보자.

Definition. (Gram-Schmidt Orthogonalization.) 벡터 공간 $V$의 기저 $B$가 주어져 있을 때, 다음 과정을 통해 orthogonal한 기저 $B^*$를 얻을 수 있다.

\[b_i^* = b_i - \sum_{j=1}^{i-1} \mu_{i,j}b_j^*\]

하지만 Gram-Schmidt Orthogonalization를 격자 문제에 그대로 적용할 수가 없는데, 이유는 격자의 특성상 정수 계수의 선형 결합만을 허용하지만 Gram-Schmidt 계수인 $\mu_ {i,j} = \frac{⟨b_ i, b_ j^* ⟩}{\lVert b_ j^* \rVert^2}$가 실수이기 때문이다. 따라서 Gram-Schmidt 결과인 $b_ i^*$는 일반적으로 정수 벡터가 아니고, 격자 벡터도 아니므로 이런 직교 기저는 격자 위에 존재할 수 없다.

이 때문에 SVP문제를 해결하기 위해 환원 알고리즘인 LLL을 사용하여 정수 조건을 유지한 채로 최대한 orthogonal에 근사한 기저를 찾는다. 이 과정에서 Gram-Schmidt를 이용하되, 직교한 실수 기저는 이후에 언급할 조건 비교로만 사용하고, 실제 격자 기저는 정수 조건을 만족하도록 조정한다.

LLL Reduction

Definition. (LLL-Reduced Basis) $\mathcal{L}$의 기저 $B$와, 그것을 Gram-Schmidt한 기저 $B^* $ 을 생각하자. (이 때, 물론 $B^* ⊂ ℝ^n$이다.) $B$와 $B^*$가 다음 조건을 만족한다면, $B$를 \(\mathcal{L}\)의 LLL-Reduced Basis라고 한다.

1. (Size Condition.) $\vert \mu_{i,j} \vert = \left\lvert \frac{\langle b_i, b_j^* \rangle}{\lVert b_j^* \rVert^2} \right\rvert \leq \frac{1}{2}$
2. (Lovasz Condition.) $\lVert b_{i+1}^* + \mu_{i+1, i}b_i^* \rVert^2 \geq \delta\lVert b_i^*\rVert^2　\delta \in \left(\frac{1}{4},1\right)$

Size Condition부터 살펴보면 Gram-Schmidt 계수 $\mu_{i,j}$는 $b_j^*$와 $b_i$ 사이의 각을 측정한다. 만약 $μ$가 1에 가까워 지면 각은 작아지고, $μ$가 0에 가까워 지면 각이 커지며 orthogonal에 근접한다. 따라서 Size Condition은 LLL-Reduced Basis가 orthogonal에 근사하도록 하는 조건임을 알 수 있다.

이제 Lovasz Condition을 살펴보자. 우린 LLL Algorithm을 통해 최단 벡터를 찾는 것이 목적이기 때문에, 앞쪽 벡터가 짧아야 전체 격자에서 더 빠르게 최단 벡터를 찾을 수 있다. 따라서 우리가 원하는 벡터 정렬 순서는 다음과 같다.

\[\lVert b_i \rVert \leq \lVert b_{i+1} \rVert\]

하지만 모든 $i$에 대해 위 조건을 만족하려면 알고리즘을 다항시간 내에 끝낼 수 없다. 또한 앞서 Size Condition을 보면 만약 $b_j^*$가 $b_i$에 비해 충분히 길면 각도와 상관없이 조건을 만족할 수도 있다. Lovasz Condition은 이 두 가지를 고려하며, $\delta$는 주로 $\frac{3}{4}$를 쓴다.

\[\begin{aligned} \lVert b_{i+1}^* + \mu_{i+1, i}b_i^*\rVert^2 &= \lVert b_{i+1}^*\rVert^2 + \mu_{i+1, i}^2 \lVert b_i^*\rVert^2 \\ \lVert b_{i+1}^*\rVert^2 + \mu_{i+1, i}^2 \lVert b_i^*\rVert^2 &\geq \frac{3}{4} \lVert b_i^*\rVert^2 \\ \lVert b_{i+1}^*\rVert^2 &\geq \left( \frac{3}{4} - μ_{i+1, i}^2 \right)\lVert b_i^*\rVert^2 \\ &\geq \frac{1}{2}\lVert b_i^*\rVert^2 \end{aligned}\]

결국 $\lVert b_ {i+1}^* \rVert^2 \geq \frac{1}{2}\lVert b_ i^* \rVert^2$ 조건을 통해 $b_{i+1}^* $의 길이가 $b_i^* $의 길이보다 아주 짧을 수는 없게 하여 Size Condition문제를 해결하고, 앞서 보았던 $\lVert b_i \rVert \leq \lVert b_{i+1} \rVert$ 벡터 정렬 순서를 조금 완화하여 벡터들의 순서를 어느정도 강제하면서 다항시간 $O(d^5n \log^3 B)$안에 해결될 수 있도록 한다.

위 관계를 통해 $\delta > \frac{1}{4}$이어야 함을 알 수 있고, 만약 $\delta=1$이 되면 최종적으로 $\lVert b_ {i+1}^* \rVert^2 \geq \frac{3}{4}\lVert b_ i^* \rVert^2$ 가 되어 벡터 정렬 순서를 조금 더 강제한다.

이렇게 구한 LLL-Reduced Basis는 기존 기저 벡터들에 대해 정수 계수로만 변형을 가해 원래 basis와 같은 Span 즉, 같은 Lattice를 생성한다.

LLL이 다항시간 안에 종료됨의 증명은 Polynomial time proof를 참고하자.

LLL Algorithm

LLL reduction의 조건에 따라 LLL Algorithm은 다음과 같이 동작한다.

Definition. (LLL Algorithm.) 다음 알고리즘은 임의의 기저 $B$를 LLL-Reduced Basis로 변환한다.

1. Gram-Schmidt Orthogonalization을 근사한다. ($\mu_{i, j}$ 대신 $⌈\mu_{i, j}⌋$을 사용해서.)
2. 모든 $i$에 대해서 Lovasz Condition을 확인한다. 이 때,
   • 조건을 만족한다면 종료한다.
   • $b_{i}^* $와 $b_{i+1}^* $가 조건을 만족하지 않는다면, $b_{i}$와 $b_{i+1}$의 순서를 바꾼 뒤(swap), 1번으로 돌아간다.

알고리즘의 Step 1을 거치면 Size Condition이 만족되고, Step 2를 거치면 Lovasz Condition이 만족된다.

최종적으로 LLL Algorithm의 결론인 다음 정리를 확인해보자.

Theorem. $L$의 LLL-Reduced Basis를 $B$라고 하자. 그렇다면 다음이 성립한다.

\[\lambda_1 \geq \sqrt{2}^{n-1}\lVert b_1\rVert\]

즉, LLL은 SVP를 $\sqrt{2}^{n-1}$의 factor로 푼다.

pf. 먼저 다음 보조정리를 증명하자.
Lemma 1. $\lambda_1 \geq \lVert b_1{min}^* \rVert$

일반성을 잃지 않고 $a_i ≠ 0$이라고 하자.

\[\begin{aligned} \lambda_1^2 &= \lVert \sum a_ib_i \rVert^2 \\ &=\lVert \sum a_i \sum \mu_{i,j}b_i^* \rVert^2 (\mu_{i,j} = 1) \\ &=\lVert a_1b_1^* + a_2(b_2^* + \mu_{2,1}b_1^* )+ ⋯ \rVert^2 \\ &\geq a_n^2\lVert b_n^* \rVert^2 \\ &\geq\lVert b_{min}^* \rVert^2 \end{aligned}\]

이제 $b_{min} = b_m$이라고 하자. 위에서 보았듯이, Lovasz Condition에 의해 $\lVert b_1^* \rVert^2 \leq 2\lVert b_2^* \rVert^2 \leq ⋯ \leq 2^{k-1}\lVert b_k^* \rVert^2$ 이 성립한다. 따라서,

\[\begin{aligned} \lVert b_1 \rVert^2 &= \lVert b_1^* \rVert^2 \\ &\leq 2^{m-1}\lVert b_m^* \rVert^2 \\ &\leq 2^{n-1}\lambda_1^2 \end{aligned}\]

양변에 루트를 씌우면 원하는 결과를 얻는다.

Lattices configuration by type

LLL을 사용해 해결할 수 있는 문제들과 각 상황에 따른 격자를 어떻게 구성해야 하는지 예시를 몇가지 살펴보자.

Subset Sum Problem

집합 $A ∈ ℤ$와 자연수 $M$이 주어져 있다고 하자. 이 때, $∑S = M$을 만족하는 $A$의 부분집합 $S$를 찾는 문제가 있다고 하자. $A = \lbrace a_1, ⋯, a_n \rbrace$이라 하면 이 문제를 다음과 같은 방정식으로 변형할 수 있다.

\[a_1x_1 + ⋯ + a_nx_n - M = 0, x_i = 1 \vert 0\]

이제 $S = \lbrace a_i \vert x_i = 1 \rbrace$가 Subset Sum Problem의 해가 되고, $x_1, \cdots, x_n$은 선형이고 작은 해 이므로 LLL을 통해 해결할 수 있다.

\[\mathcal{L} = \begin{bmatrix} 1 & 0 & \cdots & 0 & -a_1 \\ 0 & 1 & \cdots & 0 & -a_2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & -a_n \\ 0 & 0 & \cdots & 0 & M \end{bmatrix}\]

각 row들을 $b_i$라고 하면,

\[\begin{aligned} x_1b_1 + ⋯ + x_nb_n &= (x_1, ⋯, x_n, M - \sum x_ia_i) \\ &= (x_1, ⋯, x_n, 0) \end{aligned}\]

위 벡터는 $\mathcal{L}$위의 작은 벡터이고, 따라서 SVP의 답이 될 가능성이 크다.

arr = [1562, 1283, 1381, 1272, 1540]
target = 4483

L = []
N = len(arr)

for i, a in enumerate(arr):
    row = [0] * (N+1)
    row[i] = 1
    row[-1] = -a
    L.append(row)
L.append([0] * N + [target])

L = Matrix(L)

L = L.LLL()
print(L)
# [ 1  0  1  0  1  0]
# [-1  2  0 -2  1  0]
# [-3 -1  2 -1  0 -4]
# [ 2 -2 -2 -3  1 -3]
# [ 1  1 -4  2  3 -2]
# [-4 -2  1  1  4  1]

L[0] 이 우리가 정확히 원하는 형식으로 나왔음을 알 수 있다. (맨 끝의 값은 0이고, 나머지 값은 0 또는 1이다.)

Polynomial Coefficient Estimation

이번엔 반대로 아래 합동식에서 다항식의 $x$와 $N$이 주어지고, 계수 $c_i$가 작다고 가정할 때 이 값들을 찾는 문제를 살펴보자.

\[\sum_{i=1}^n c_ix^i \equiv 0 \pmod{N}\]

역시 구하려는 $c_i$가 작은 값이므로 short vector 문제로 변환해서 LLL로 해결이 가능하다.

\[\sum_{i=1}^n c_ix^i - N = 0\]

위 관계를 이용해 아래 Lattice를 만들 수 있다.

\[\mathcal{L} = \begin{bmatrix} 1 & 0 & \cdots & 0 & x^n \\ 0 & 1 & \cdots & 0 & x^{n-1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & x \\ 0 & 0 & \cdots & 0 & -N \end{bmatrix}\]

각 row를 basis로 생각하면 $(c_n,c_{n-1} ⋯,c_1, 0)$ 가 결과로 나오게 된다.

N = 10007
mark = 7

L = matrix(
    [
        [1, 0, mark^2],
        [0, 1, mark^1],
        [0, 0,     -N]
    ]
)

L = L.LLL()

# print(L)
# [  0   1   7]
# [  1  -7   0]
# [200  29  -4]

L = L[2] 

R.<x> = PolynomialRing(ZZ)
f = 0
for j in range(2):
    f += L[j] * x^(2 -j)
f -= L[2]

# print(f)
# 200*x^2 + 29*x + 4

L[2]이 우리가 찾는 해 임을 알 수 있다.

Bytes Recovery

CTF에서 바이트로 이루어진 플래그의 길이를 안다면 LLL로 복구할 수도 있다. 플래그도 결국 바이트 배열 $x=[x_0, x_1, \cdots, x_n]$ 이고, 바이트 값이 작기(ASCII) 때문에 아래와 같이 하나의 정수로 표현하고, 이를 LLL 격자로 만들면 된다.

\[X=x_0\cdot 256^{n} + x_1 \cdot 256^{n-1} + \cdots + x_n \cdot 256^0\]

결국 flag 정수값을 $X$라 했을 때, 아래의 합동식을 해결하는 문제이므로 앞선 문제들과 비슷해진다.

\[X \equiv 0 \pmod{N}\]

이때 현재 바이트에서 다음 바이트로의 관계는 다음과 같다.

\[x_{i+1}-256 \cdot x_i =0 \to x_{i+1}=256 \cdot x_i\]

따라서 위 관계를 이용해 격자를 구성하면 다음과 같다.

\[\mathcal{L} = \begin{bmatrix} N & 0 & 0 & \cdots & 0 & 0 \\ -256 & 1 & 0 & \cdots & 0 & 0 \\ 0 & -256 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & 0 & \cdots & -256 & 1 \end{bmatrix}\]

이외에도 앞서 살펴본 다항식의 계수 문제처럼 $x$를 256이라 생각하여 격자를 아래와 같이 구성할 수도 있다.

\[\mathcal{L} = \begin{bmatrix} 1 & 0 & \cdots & 0 & 256^n \\ 0 & 1 & \cdots & 0 & 256^{n-1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 256 \\ 0 & 0 & \cdots & 0 & -N \end{bmatrix}\]

다음은 이와 관련된 문제인 SeeTF 2023 Onelinecrypto Writeup으로 LLL을 통한 Bytes Recovery의 예를 보여준다.

# "https://web.archive.org/web/20240412075022/https://demo.hedgedoc.org/s/DnzmwnCd7"
# "https://nush.app/blog/2023/06/21/see-tf-2023/"

from sage.all import *
from cpmpy import *
import re

n = 13**37
empty = b'SEE{' + bytes(23) + b'}'
target = int.from_bytes(empty, 'big') * pow(256, -1, n)

m = matrix(24, 24)
m[0,0] = n
for i in range(22):
    m[i+1,i:i+2] = [[-256, 1]]
m[-1,0] = -target
m[-1,-1] = 2**256 # some arbitrarily large number

def disp():
    flag = bytes(x.value())[-8::-8].decode()
    print(flag, '<--- WIN' if re.fullmatch(r'\w+', flag) else '')

x = cpm_array(list(intvar(-99999, 99999, 23)) + [1]) @ m.LLL()[:,:-1]
Model([x >= 48, x <= 122]).solveAll(display=disp)

Reference

1. https://blog.sp301415.com/solving-integer-problems-using-lll/
2. https://cryptohack.gitbook.io/cryptobook/lattices/definitions
3. https://crypto.stackexchange.com/questions/39532/why-is-the-lov%C3%A1sz-condition-used-in-the-lll-algorithm