[SECCON CTF 2021] XXX

 

import os

flag = os.getenv("FLAG", "fake{fakeflag_blahblah}") ##319bit
x = int.from_bytes(flag.encode(), "big")

p = random_prime(1 << int(x.bit_length() * 2.5)) #796
Fp = GF(p)

params = []
while len(params) != 6:
    try:
        y = randint(2, x)
        a = randint(2, p-1)
        b = (y^2 - (x^3 + a*x)) % p

        EC = EllipticCurve(Fp, [a, b])
        EC(x, y)

        params.append([a, b])
    except ValueError:
        pass

print(p)
print(params)

 

문제를 보면 고정 값 x, p가 있을 때,

p와 $x^3+ax+b=y^2 (mod\;p)$를 만족하는 $(a,b)$쌍 6개를 제공해준다.

 

이때, p의 bit를 알기 때문에, 다른 변수들의 bit도 예상 가능하다.

** 각 변수 크기

x, y : 319bit

a, b, p : 796bit

 

x가 고정 값이기 때문에 식 2개를 빼보면 아래와 같은 식을 얻을 수 있다.

 

$$(a_0-a_1)*x+(b_0-b_1)=y_0^2-y_1^2\;(mod\;p)$$

 

주어진 값이 총 6개이기 때문에 위와 동일한 형태의 식 5개를 얻을 수 있는 것이다.

 

$$ -2^{319}<(a_i-a_{i+1})*x+(b_i-b_{i+1})\;(mod\;p)<2^{319} $$

 

여기서 x를 구하기 위해 여러 부등식들을 세우고, rkm님의 CVP repository를 이용하면 풀 수 있어 보인다.

해당 문제의 경우 부등식이 $Zmod(p)$위에서 존재하기 때문에 어떻게 CVP repo에 적용할 수 있을지 몰랐는데, rkm님의 도움을 얻어 변수를 하나 더 추가해주면 modulo 연산을 무시할 수 있다는 사실을 깨달았다.

 

$$ -2^{319}<(a_i-a_{i+1})*x+(b_i-b_{i+1})+p*c_i <2^{319}$$

 

여기서{b_i}​는 주어진 값이므로 lower/upper bound 쪽으로 넘기면 된다.

 

$$ -2^{319}-(b_i-b_{i+1})<(a_i-a_{i+1})*x+p*c_i <2^{319}-(b_0-b_i) $$

 

추가적으로 우리가 아는 식이 1개 더 있다.

 

$$ 0<x<2^{319} $$

 

이제 변수는$x$, $c_1$, ... $c_5$​로 총 6개이고 식이 6개이므로 아래와 같은 6x6 Matrix를 만들어서 rkm’s CVP repo를 적용하면 각 변수의 값을 구할 수 있다.

 

$$ \begin{bmatrix} a_0-a_1 &a_1-a_2 & a_2-a_3 & a_3-a_4 & a_4-a_5 & 1 \\p & 0 & 0 & 0 & 0 & 0 \\0 & p & 0 & 0 & 0 & 0 \\0 & 0 & p & 0 & 0 & 0 \\0 & 0 & 0 & p & 0 & 0 \\0 & 0 & 0 & 0 & p & 0 \end{bmatrix}$$

​

첨언 하자면 각 열이 하나의 부등식이고 각 행이 변수의 계수라고 보면 된다.

1번 행은 $x$, 2번행은 $c0$ , 6번행은 $c5$인 것이다.

 

ans.sage

from sage.modules.free_module_integer import IntegerLattice
from Crypto.Util.number import *
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin


f = open("output.txt",'rb')
a = f.read().split(b'\n')
p = int(a[0])
params = eval(a[1])

M = Matrix(ZZ,6)
lb = [0] * 6
ub = [0] * 6 
for i in range(5):
    M[0,i] = (params[i][0] - params[i+1][0]) % p
    M[i+1,i] = p
    dy = (params[i][1] - params[i+1][1]) % p
    lb[i] = -1 * (2 ^ 638) - dy
    ub[i] = (2^638) - dy
M[0,5] = 1
lb[-1] = 0
ub[-1] = 2 ^ 319


result, applied_weights, fin = solve(M, lb, ub)
print(long_to_bytes(int(fin[0])))
#SECCON{9dd4e461268c8034f5c8564e155c67a6}

 

진짜 갓갓 repo인데 아직 문제에 쉽게 적용하지 못하고 있다.. 여러 문제에 적용해보면서 빨리 익혀야지