H4CKING GAME - cryptograhpy, Season1 : AGCD

Season1 : AGCD

문제는 다음과 같음.'

output-2.txt

0.05MB

prob-2.py

0.00MB

xi = p*qi + 127ri 부분을 잘 보자

 

여기서

p: 1024-bit 소수이며 비밀값

qi: 최대 1024-bit

ri: 최대 760-bit

127: 작은 고정된 수

이다.

 

즉 모든 xi는 공통적으로 큰 비밀값 p의 배수에 작은 오차 127ri가 더해진 형태이다.

이러한 문제를 Approximate GCD(AGCD) 문제라고 볼 수 있다.

 

일반적인 GCD 문제라면

xi = p * qi 형태이므로 여러 xi의 GCD를 계산하면 p를 쉽게 구할 수 있다.

근데 이 문제에서는 xi = p*qi + 127ri 이므로 단순히 gcd를 계산해도 p가 나오지 않는다.

 

그래도 다행히 모든 값이 같은 p를 공유하고 있음

그래서 xi 를 대충 p*qi 라고 생각할 수 있음 (여러 개의 값으로부터 공통된 큰 인수 p를 찾아내면 됨)

 

 

 

각 문자마다 랜덤하게 선택된 x[i]들의 subset sum이 더해진다. 암호문 하나를 c, 원래 flag의 한 바이트를 m이라고 하면

 

c 는 m+(bi*xi)의 합 이다.

 

근데 그냥 subset sum을 풀려고 하면 경우의 수가 2^50개라서 불가능 

 

그래서 xi 자체에 AGCD 구조가 있다는 걸 이용해서 p를 먼저 찾을 수 있다.

 

 

AGCD에서는 다음과 같은 형태의 lattice 코드를 구성할 수 있다. (LLL알고리즘 이용)

from sympy import Matrix

rho = 256
n = 10

B = [[0] * n for _ in range(n)]

B[0][0] = 1 << (rho + 1)

for i in range(1, n):
    B[0][i] = public_keys[i]
    B[i][i] = -public_keys[0]

L = Matrix(B).lll()

 

LLL은 lattice 안에서 좀 짧은 벡터들을 찾아준다.

 

이제 p를 구해보자 

 

첫 번째 공개값은 x0=p*q0+127r0

 

LLL에서 q0를 얻었으면 p = x0/q0 으로 계산할 수 있다.

 

코드로 구해봄

q0 = abs(int(L[0, 0]))
p = public_keys[0]

 

162530024130330901339431266478830544725812071439069831773185019191892265573912236753751459668873008760325742686592087118336048148625756655731142198947624755104152108403214219021047514597003696621388331057476308810883505452878014649547532953665654013287897621651989317203699941307991413730975730559621002345317

 

 

 

 

이제 p를 구했으니까 복호화를 해보자.

 

암호문은 xi=p*qi+127*ri 이었므로 modulo p를 취하면 xi mod p=127ri

 

즉, c mod p = m + (bi*ri)
 i=0~127

 

여기서 한 번 더 modulo 127을 취하면 ( c mod p ) mod 127 = m 

flag = bytes((c % p) % 127 for c in ciphertexts)
print(flag.decode())

 

결과는

H4CGM{th1s_1s_gcd_pr0bl3m_with_latt1c3}