[DownUnder CTF 2023] apbq-rsa-ii

대회 중에는 못 풀었지만, 상당히 깔끔한 풀이가 있어서 적어본다.

chall

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001

hints = []
for _ in range(3):
    a, b = randint(0, 2**312), randint(0, 2**312)
    hints.append(a * p + b * q)

FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')

312bit 크기의 a, b에 대하여 ap+bq 3개가 주어진다. 주어진 hints를 $h1, h2, h3$라고 하면

이 되는 $s1, s2, s3$를 LLL로 찾는다면

위 식을 만족하게 된다. 여기서 p, q는 서로소이므로 p와 q의 계수는 0이다.

따라서 $s1, s2, s3$에 대하여 LLL을 통해 $a1, a2, a3$를 찾아낼 수 있다.

그 이후로는 $gcd(h1*a2-h2*a1, n)$ 로 $p$를 leak할 수 있다.

exploit code (sage)

from Crypto.Util.number import *

n = 19604411241131769363446674414275822275458180476470552084588074159518829172495704100505151090666577360738167275118902368371310303168115405693118232835691333564186301532462296609038929723894816307213749698854885742811071911120730847279568876996811433319487396434622751326281226335521193361938724747445445693062336009352580319440819629260614301234971135026395941954109172567154559773437059174108362692061503832044135079892892132874437669744266153424229215832487832220575345912010076934611701182205068942016022731469408259665250938484104489962832891496953003599692437819685070043991828977623632396604764153766442526750861
c = 16285668872352205553535195410427806596787838055817589230402081772267074935944610262823936480340920868690431897597533868262062616060037808676539290467732178272289192993251540763800683055555842878669862850848141950704501553807462214356142018528608581546359772903806691435935873069006470208826518183488708349814610769150918356795466688732617809664831695402633481224388822180989614886783145141129157248734213457746877012517003702540070132542733288350979858743766340483503277308585752213220454288897741262154622769402029906981612699288206404870733274360554941455758083078106150045394190625280336371690998959720015636304971
hints = [773921762798470573303163880380136299117907456177270598418425239064611119645412840945432294881005107606154919094297188183879147500755682510817840590276985061404198538395146658442221987303866921786284298394947485319583779671756246394491275898343836522004269864718405399287554020900395899143149709408762450693357109188640512875099087677956684946219071353228860650842182953922400081939934842271539450654323, 1506346165967409413422972644306025635334450240732478358292064973873339506571546529986180145578525288707094235933775031106971678278204568310035260899591267480098015553318079460357474533531922997212816264042117005473870580122983241038123126855791876827449194400045937398578284016176289760858365282167537689282643483235235028505475719615108102516557986483184881658418430287064598580231630440534438966422546, 531028473288853560172466570664059891687387973059926255729701774553291285115938502989142318123512885100092638435578692032744904444237266108167428726130739434630511943317357743527053899234918340191006102436386051432760331852295930159729030763033361158582919982579082557775409422474301977588011705535991555292564664521116375190464371518812625647175447427886432255779925378071998411170643507118426289778768]

h1, h2, h3 = hints

M = matrix([
    [h1<<3000, 1, 0, 0],
    [h2<<3000, 0, 1, 0],
    [h3<<3000, 0, 0, 1]
])

M = M.LLL()

s1, s2, s3 = M[0][1:]

M2 = matrix([
    [s1<<3000, 1, 0, 0],
    [s2<<3000, 0, 1, 0],
    [s3<<3000, 0, 0, 1]
])

M2 = M2.LLL()

a1, a2, a3 = M2[0][1:]

p = gcd(h1*a2-h2*a1, n)
q = n//p
d = inverse(0x10001, (p-1)*(q-1))
print(long_to_bytes(int(pow(c, d, n))).decode())

DUCTF{0rtho_l4tt1c3_1s_a_fun_and_gr34t_t3chn1que_f0r_the_t00lbox!}

*전체적인 문제 퀄리티가 상당히 좋은 ctf였지만 내 실력이 부족해 마음껏 즐기지 못했다. 좀 더 발전해서 나중에 다시 풀어보자.