LLL practice 1

처음 볼 문제는 Cryptohack의 Find the Lattice이다. 문제 코드를 보자.

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'crypto{?????????????????????}'


def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')

상황을 보면

$m, r, f < \sqrt \frac {q}{2}, \sqrt \frac {q}{4} < g < \sqrt \frac {q}{2}$

$hf ≡ g \ (mod \ q)$

$e ≡ rh + m \ (mod \ q)$

위와 같다.

첫 번째 식은 $fh = g + kq$ 로 볼 수 있다. 여기서 중요한 것은 $h, q$ 끼리 크기가 비슷하고, $k, f, g$ 끼리 크기가 비슷하며 이들은 $h, q$ 에 비해 매우 작다는 것이다.

따라서 식을 다음과 같이 변형해보자.
$f(h, 1) - k(q, 0) = (g, f)$

이를 행렬로 표현하면

$\begin{bmatrix}h&1\\q&0\\ \end{bmatrix} \begin{bmatrix}f\\-k\\ \end{bmatrix} = \begin{bmatrix}g\\f\\ \end{bmatrix}$

위와 같다.

여기서 $\begin{bmatrix}h&1\\q&0\\ \end{bmatrix}$에 비해 $\begin{bmatrix}f\\-k\\ \end{bmatrix}$와 $\begin{bmatrix}g\\f\\ \end{bmatrix}$의 길이는 매우 작기 때문에 $\begin{bmatrix}h&1\\q&0\\ \end{bmatrix}$에서 LLL알고리즘을 쓸 수 있다.

결과로 나온 두 벡터 중 두 수의 부호가 같은 벡터의 원소가 각각 $g, f$ 일 것이다.