[CryptoHack] MATHMATICS(Find the Lattice)

Find the Lattice

문제(및 설명)

보안 시스템에 대한 트랩도어 함수를 형성할 수 있는 어려운 문제를 포함하는 것으로 알려진 격자(lattices)를 살펴보았습니다. 또한, 암호 해독(cryptanalysis)에서는 격자가 격자와 관련이 없는 것처럼 보이는 암호 프로토콜을 깰 수 있습니다. 이 도전 과제는 플래그를 암호화하기 위해 모듈러 산술을 사용하지만, 프로토콜 내에는 2차원 격자가 숨겨져 있습니다. 이 도전에 시간을 투자하고 어떻게 격자를 사용하여 이를 깰 수 있는지 찾는 것을 강력히 권장합니다. 이것은 많은 자료가 있는 유명한 예제이지만, 시스템 내에서 격자를 찾아내는 것이 종종 깨는 핵심이 됩니다. 힌트로는 이 도전을 이전 도전에서 다룬 가우스 소거법(Gaussian reduction)를 사용하여 깰 수 있을 것입니다.

풀이

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}')

output.txt

 해당 문제에선 가우스 소거법을 이용하여 해보았다.

먼저 decrypt의 q,h 값은 공개키, e는 암호화된 플래그 값을 이용하고

 

v,u값을
v = vec(1, h)
u = vec(0, q)

으로 하여 해당 문제를 해결해본 결과

from Crypto.Util.number import long_to_bytes, inverse
from math import floor

class vec:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def mul(u, v):
    r = u.x * v.x + u.y * v.y
    return r

def multiple(k, a):
    x = k * a.x
    y = k * a.y
    u = vec(x, y)
    return u

def sub(u, v):
    x = u.x - v.x
    y = u.y - v.y
    r = vec(x, y)
    return r

def gaussian_reduction(v, u):
    while True:
        if mul(u, u) < mul(v, v):
            t = u
            u = v
            v = t
        m = floor(mul(v, u) / mul(v, v))
        if m == 0:
            break
        else:
            u = sub(u, multiple(m, v))
    return (v, u)

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


q = 7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257
h = 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800
e = 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523

v = vec(1, h)
u = vec(0, q)
v, u = gaussian_reduction(v, u)
f = v.x
g = v.y

print(long_to_bytes(decrypt(q, h, f, g, e)).decode())

플래그 값은 crypto{Gauss_lattice_attack!}이다.