보안 시스템에 대한 트랩도어 함수를 형성할 수 있는 어려운 문제를 포함하는 것으로 알려진 격자(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())
