간만에 휴식기에 풀었던 CTF 암호학 문제 라이트업을 아주 간단하게만 올려본다.
1. Investigation
> chall.sage
from flag import flag
assert len(flag) == 110
p = random_prime(2**100)
q = random_prime(2**100)
n = p * q
Rn = Zmod(n)
SIZE = 4
M = GL(SIZE, Rn)
def matrix_random():
while True:
try :
rands = [randint(0, n-1) for _ in range(SIZE ** 2)]
Mat = M(rands)
return Mat
except :
continue
#Making My Private KEY Not So Important
def priv_key(flag1) :
m = Rn(int.from_bytes(flag1.encode(),"big"))
a = Rn(randint(0, n-1))
coeffs = SIZE - 1
bound = coeffs * (coeffs + 1) // 2
b_s = [Rn(randint(0, n)) for _ in range(bound)]
c = m ** bound
c_s = []
for i in range(coeffs):
t = i * (i + 1) // 2
o = ((c + b_s[t]) if t else c ) ** 5
if not i:
c_s.append((a * o + b_s[t]))
continue
for j in range(0, i):
o *= a
o += b_s[t + j + 1]
c_s.append(o)
diag = [a**i + c for i in range(1,5)]
Mat = Matrix(Rn, [ i * [0] + [diag[i]] + ([c_s[i] ] if i < len(c_s) else []) + (2-i) * [ ((b_s[i] + b_s[i+1])*a)**20 ] for i in range(4)] )
return M(Mat) , b_s
def gen_pub(derived):
r = 5
while True:
A = matrix_random()
D , b_s = priv_key(derived)
try:
if D * A != A * D:
Dr = D^r
B = (~D) * (~A) * D
pubkey = ( A , B , Dr)
return pubkey , b_s ,D
except:
continue
def encrypt(pub , flag2):
s = randint(1 , 2**10)
gam = pub[-1] ^ s
eps = ~gam * pub[0] * gam
k = ~gam * pub[1] * gam
length = len(flag2) // 16
U = M(Matrix(Rn , 4 , 4 , [ int.from_bytes(flag2[i*length : (i+1)*length].encode() , "big") for i in range(16) ]))
U_ = k * U * k
return U_ , eps
pub , b_s , D = gen_pub(flag[:30])
U_ , eps = encrypt(pub , flag[30:])
# Output ..........
with open("out.txt" , "w") as f :
Dr = Matrix(pub[-1])
eps = eps.list()
U_ = U_.list()
A = pub[0].list()
f.write(f"{n = }\n")
f.write(f"{b_s = }\n")
for i in range(3):
f.write(f"Dr[{i}][{i+1}] = { Dr[i][i+1] }\n")
f.write(f"{A = }\n")
f.write(f"{eps = }\n")
f.write(f"{U_ = }\n")
pub , b_s , D = gen_pub(flag[:30])
U_ , eps = encrypt(pub , flag[30:])위에서 중요한 부분은 이 두 라인이다.
플래그를 앞 30바이트, 뒤 30바이트 이후로 나누어서 어떠한 작업을 해주고 있다.
먼저 gen_pub 부터 살펴보자.
def gen_pub(derived):
r = 5
while True:
A = matrix_random()
D , b_s = priv_key(derived)
try:
if D * A != A * D:
Dr = D^r
B = (~D) * (~A) * D
pubkey = ( A , B , Dr)
return pubkey , b_s ,D
except:
continue어떠한 조건(D * A != A * D)을 만족할 때 까지, 즉 교환 법칙이 성립하지 않을 때 까지 반복문을 돈다.
A = Z/Zn 위의 4x4 사이즈의 랜덤한 행렬.
D, b_s = priv_key(derived == flag[:30])
priv_key가 뭔지 살펴보자.
#Making My Private KEY Not So Important
def priv_key(flag1) :
m = Rn(int.from_bytes(flag1.encode(),"big"))
a = Rn(randint(0, n-1))
coeffs = SIZE - 1
bound = coeffs * (coeffs + 1) // 2
b_s = [Rn(randint(0, n)) for _ in range(bound)]
c = m ** bound
c_s = []
for i in range(coeffs):
t = i * (i + 1) // 2
o = ((c + b_s[t]) if t else c ) ** 5
if not i:
c_s.append((a * o + b_s[t]))
continue
for j in range(0, i):
o *= a
o += b_s[t + j + 1]
c_s.append(o)
diag = [a**i + c for i in range(1,5)]
Mat = Matrix(Rn, [ i * [0] + [diag[i]] + ([c_s[i] ] if i < len(c_s) else []) + (2-i) * [ ((b_s[i] + b_s[i+1])*a)**20 ] for i in range(4)] )
return M(Mat) , b_s뭔가 다항식 형태의 대각행렬을 구성해서 이를 개인키 Mat 변수로, 다항식에 포함되는 랜덤 정수 리스트 b_s를 만들어 반환해준다.
그리고 m == flag1 == flag[:30] 을 bound(=6) 만큼 제곱하여 암호문 c 로 만들어 다항식에 사용한다.
결론적으로 D, b_s = priv_key(derived == flag[:30]) 코드에 의해 gen_pub 함수 내에서 D = Mat 이 된다.
정확한 구조 파악을 위해서 AI를 이용해 코드 분석 후 D의 구조를 알려달라고 했다.
D = [[a+c, c_s[0], ((b_s[0]+b_s[1])*a)^20, ((b_s[0]+b_s[1])*a)^20],
[0, a²+c, c_s[1], ((b_s[1]+b_s[2])*a)^20],
[0, 0, a³+c, c_s[2] ],
[0, 0, 0, a⁴+c ]]뭔가 Lattice Reduction 을 활용해서 풀기 좋게 생겼다.
이제 다시 gen_pub 로 돌아가보자.
def gen_pub(derived):
r = 5
while True:
A = matrix_random()
D , b_s = priv_key(derived)
try:
if D * A != A * D:
Dr = D^r
B = (~D) * (~A) * D
pubkey = ( A , B , Dr)
return pubkey , b_s ,D
except:
continue랜덤한 행렬 A와 교환 법칙이 성립하지 않으면 Dr = D^5, 그리고 B = (D 역원) * (A 역원) * D 를 계산해서 pubkey = (A, B, Dr) 로 만들고, (pubkey, b_s, D) 를 반환한다.
결국 flag[:30] 부분을 얻기 위해서는 priv_key 함수에서 나온 개인키 D 행렬을 완전히 복원해야 어떻게 해볼 수 있을 것 같다.
다음으로는 encrypt 에 대해서 알아보자.
pub , b_s , D = gen_pub(flag[:30])
U_ , eps = encrypt(pub , flag[30:])
def encrypt(pub , flag2):
s = randint(1 , 2**10)
gam = pub[-1] ^ s
eps = ~gam * pub[0] * gam
k = ~gam * pub[1] * gam
length = len(flag2) // 16
U = M(Matrix(Rn , 4 , 4 , [ int.from_bytes(flag2[i*length : (i+1)*length].encode() , "big") for i in range(16) ]))
U_ = k * U * k
return U_ , eps뭔가 복잡한 계산을 하고 있는데 결론적으로는 4x4 사이즈 U 행렬에 flag[30:] 부분을 5바이트씩 끊어서 넣고 U_ = k * U * k 를 계산하여 eps 값과 함께 반환한다.
그런데 s 값이 1 ~ 1024 이내의 굉장히 작은 수라 Brute-forcing이 아주 쉽게 가능해보이고, 나머지 값들에 대해 pubkey를 활용해서 계산을 하고 있는데 pub[-1] == D, pub[0] == A 는 output.txt 에서 알려주는 값, pub[1] == B 는 (~D) * (~A) * D 이기 때문에 D 행렬만 복원된다면 쉽게쉽게 k 에 대해 계산할 수 있을 것 같다.
k 를 구했으면 U = (~k) * U_ * (~k) 로 U 행렬을 구하고 5바이트씩 평문 복원이 가능하다.
> output.txt
n = 445274615059837074703074129112359915057174632831812151523967
b_s = [394630328574245837271964995407645525864174759236154380643123, 181576505553348136346747373172404084614838614588476774583011, 47077957947512963105149976221929200145993567056781606375095, 89512069817356782446065533722663239350804126107686725128410, 373205572983197742790495284583000076470807977675517077486772, 23498650172584653123097600569326533466683470443976638497395]
Dr[0][1] = 65121623752613515130879120572450892437787062242339581021972
Dr[1][2] = 309119002962212926538831287621396239072826023374419794264806
Dr[2][3] = 347470190991251003796270760779117025940129782467301096539733
A = [[267488503328751734811097261113084423911438725622299714310906, 241117396863105959600754534694070834476850425262709687269036, 214258198847456276524419017061190255640640610747513321186897, 243908647245747968722106141408796681516825496314767254191757], [296319709221599349271057047062188865965114280077923836145107, 71529348777992013834622878352061278318971600308100689319273, 21591870354281474475646302816674067646780297577032674955185, 329768812477769930550184723256646545904725913270398836212842], [393454646582482661433381653516719745488323555925451955187902, 194746794540595232682055052374882607738478749014201463302499, 334558373377320943753331767654378770755387190446496860928551, 56161017168485902852067920208271199031653238414912499757534], [266977137695022785306720925811441529661962591963589182595205, 16753429262712563178096867265259745231766743278052644485337, 253490251626334837867786572868935770318733416332589112030380, 22145971392163310763756103453873785465919607151396748455019]]
eps = [[192586917014788390326312911581471749597377333033259137675184, 129168876551996260342874367540015182845788848550489794697324, 57831749904731123118404758141603855187866531365624335427344, 195022502697866726972189757984030560180344345109946796156325], [135781469480802094592765423575750583422293592849340942790362, 194570494824611028514594474010420293134634552797088093148718, 40197041087045646329648689121888972810337539641412154942753, 171488839407647249066021945353574939028890470126691251018950], [321574053868131893139085098301380237612683258740173520412344, 52517421891213975251433410788690537724250142992816345255227, 333466758500180143561934683481914639597381284613553905277784, 352008560551548268582889491138232791723183260602131415827535], [251489871649117676162415757114107100160422729328280616605867, 103056811001222772929081702577039570831201708883461825815960, 431531126172591487922735317410797819329355211209825121991402, 420372641596485515463040070611951491179498585916205028436030]]
U_ = [[284748677963482855560647580975430987796843309477842402790596, 242337483266671138784804936005948727710979699483520088294751, 222789040283490430347316580802423043491056060923158051369962, 191112897515604587611641191854510105473086622421743591204621], [238170838594983786682252829258413429179238271948287974513470, 277493478941503842166499052157318771559824990881681931185164, 175870003968434125688348973363665346473569841390671788315745, 298283886414644176621219824782985590557056515812318580574622], [224658814356409335319395178072646711675997551719107602968739, 262450329784813814501873286313684579762178308313152721306551, 127386310370756304739779430076739347844666760625671518036044, 114206800882087686184914497540226589380365955487371216456391], [116661993725296521336028467679022554919505922084876672576011, 299846461555326343107174129245788821779256198458100923490486, 169617077441479678088743611019939106784337042750354690307174, 382330202935869270742131324475593286027520744344616893665932]]참고로 output 맨 위를 보면 Z/Zn 에 사용된 200비트 크기의 n 값이 있는데 크기가 굉장히 작아서 금방 소인수분해 된다.
p = 460787053387729396804743714197
q = 966334908470530797510120137411
위 공개된 정보들을 가지고 어떻게 D를 복원할 수 있나 고민해보자.
2. Digging
D = [[a+c, c_s[0], ((b_s[0]+b_s[1])*a)^20, ((b_s[0]+b_s[1])*a)^20],
[0, a²+c, c_s[1], ((b_s[1]+b_s[2])*a)^20],
[0, 0, a³+c, c_s[2] ],
[0, 0, 0, a⁴+c ]]위 구조대로 a, c 값만 미지수로 두고 아래처럼 코드를 구성한다.
코드로 Symbolic한 D 행렬을 만들어봤다.
############################################################
# 1. Symbolic D construction (over Zn[a,c])
############################################################
R.<a,c> = PolynomialRing(Zn)
# b_s extraction
b0, b1, b2, b3, b4, b5 = b_s
# c_s definition
c_s0 = a * c^5 + b0
c_s1 = (c + b1)^5 * a + b2
c_s2 = (c + b3)^5 * a^2 + b4 * a + b5
# D_sym matrix
D_sym = Matrix(R, 4, 4, 0)
# Diagonal entries
D_sym[0, 0] = a + c
D_sym[1, 1] = a^2 + c
D_sym[2, 2] = a^3 + c
D_sym[3, 3] = a^4 + c
# Remaining entries of Upper triangle
D_sym[0, 1] = c_s0
D_sym[0, 2] = ((b0 + b1) * a)^20
D_sym[0, 3] = ((b0 + b1) * a)^20
D_sym[1, 2] = c_s1
D_sym[1, 3] = ((b1 + b2) * a)^20
D_sym[2, 3] = c_s2
print("[+] D_sym built")b_s는 output에서 알려주는 값이기 때문에 추출해서 사용한다.
############################################################
# 2. Compute D^5 and extract needed entries: (0,1), (1,2), (2,3)
############################################################
print("[+] Computing D_sym^5 (may be slow)...")
D5_sym = D_sym^5
print("[+] Done")
D5_01 = D5_sym[0, 1]
D5_12 = D5_sym[1, 2]
D5_23 = D5_sym[2, 3]다음으로 D_sym^5 를 계산한다. 왜냐하면 output에서 Dr[0][1], Dr[1][2], Dr[2][3] 값을 알려주고 있기 때문에 이 값들을 이용해서 a, c를 복원할 수 있기 때문이다.
############################################################
# 3. Solve for (a, c) modulo p and q via Groebner basis
############################################################
F01 = D5_01 - Dr01
F12 = D5_12 - Dr12
F23 = D5_23 - Dr23
primes = [p, q]
solutions = []
for prime in primes:
print(f"\n[+] Solving (a,c) mod {prime}")
Rp.<aprime, cprime> = PolynomialRing(GF(prime))
print(" Computing Groebner basis...")
I = Rp.ideal([F01, F12, F23])
gb = I.groebner_basis()
print(f" Groebner basis size: {len(gb)}")
print(f" gb: {gb}")
# Expect linear forms [aprime + const, cprime + const]
if len(gb) == 2:
g0, g1 = gb
a_sol = -g0.constant_coefficient()
c_sol = -g1.constant_coefficient()
solutions.append([a_sol, c_sol])
print(f" Solution: aprime={a_sol}, cprime={c_sol}")
else:
print(f" Failed to solve mod {prime}")Symbolic한 D^5 행렬의 [0, 1] 번째 원소에서 output 에서 알려주는 실제 D^5 행렬의 [0, 1] 번째 원소 값을 빼 결과가 0이 되는 함수 F01을 만든다. 똑같이 F12, F23도 만든다. 이는 f(x) = 0 구조를 만들어 근을 구할 수 있도록 한다.
Z/Zn 의 n 값은 소인수분해가 되어있기 때문에 더 작은 그룹인 p, q로 나누어 [F01, F12, F23] 이데알의 Groebner Basis 를 계산하면, 높은 확률로 a%p, c%p 그리고 a%q, c%q 값을 구할 수 있다.
############################################################
# 4. Reconstruct (a,c) via CRT and build D
############################################################
a_vals = [ZZ(sol[0]) for sol in solutions]
c_vals = [ZZ(sol[1]) for sol in solutions]
a_val = crt(a_vals, primes)
c_val = crt(c_vals, primes)
print(f"\n[+] Valid (a,c) found:")
print(f" a = {a_val}")
print(f" c = {c_val}")
D = D_sym(a=a_val, c=c_val)
print("\n[+] Matrix D reconstructed")이를 다시 CRT를 이용해 Z/Zn 에서의 원래 a, c 값을 복원한다.
그리고 D_sym의 미지수 a, c에 복원된 값을 넣어 원래 D를 복원한다.
############################################################
# 5. Recover m from c_val = m^6 (mod n) using known partial prefix
############################################################
prefix = b"shellmates{"
prefix_int = int.from_bytes(prefix, 'big')
shift_bits = (30 - len(prefix)) * 8
P.<x> = PolynomialRing(Zn)
f = (prefix_int * 2^shift_bits + x)^6 - c_val
for m_cand in f.roots(multiplicities=False):
m_cand = int(m_cand) # prevent Sage to compute in Zmod
m_cand = (prefix_int * 2^shift_bits + m_cand).to_bytes(30, "big")
if m_cand.startswith(prefix):
flag_head_bytes = m_cand
print(f"\n[+] Found flag[:30]: {flag_head_bytes}")
break원래 a, c 값을 복원했다면 c = m ^ 6 (mod n) 에서 m 을 복원할 수 있다.
다만 m은 flag[:30] 에 의해 30바이트 == 240비트 크기이기 때문에 200비트인 n의 나머지 연산에 의해 40비트가 사라져 원래 m 값을 복원할 수 없게 되어 있다.
때문에 사용한 방법이 CTF에서는 플래그 형식이 정해져 있기 때문에 해당 CTF의 플래그 형식인 shellmates{ 를 활용하여 알려진 prefix로 두면 나머지 19바이트(30 - 11 = 19)만 구하면 되고 이는 152비트이기 때문에 n의 나머지 연산에 의해 변형이 되지 않는다. 이를 이용해 f(x) = 0 이 되는 다항식을 구성한 뒤 근을 구하고 바이트 변환했을 때에 prefix 로 시작하는지 확인하면 flag[:30] 부분을 복원할 수 있다.
############################################################
# 6. Find s (1..1024) and decrypt U_
############################################################
print("\n[+] Brute-forcing s in [1..1024]")
for s in range(1, 2^10 + 1):
if s % 100 == 0:
print(f" s = {s} ...")
gam = D^(5 * s)
if not gam.is_invertible():
continue
check_eps = (~gam) * A * gam
if check_eps == eps:
print(f"[+] s found: {s}")
break
# B is not given explicitly, but from gen_pub: B = (~D) * (~A) * D
B = (~D) * (~A) * D
gam = D^(5 * s)
k = (~gam) * B * gam
if k.is_invertible():
U_plain = (~k) * U_ * (~k)
print("\n[+] U_plain matrix:")
print(U_plain)
flag_tail_bytes = b""
for x in U_plain.list():
v = int(x)
flag_tail_bytes += v.to_bytes(5, "big")
print("\n[+] Decrypted flag[30:] bytes:")
print(flag_tail_bytes)
else:
print("[-] k is not invertible")다음으로는 나머지 부분인 flag[30:] 을 복원하기 위해 먼저 1~1024의 작은 범위의 값인 s를 Brute-forcing을 통해 찾아낸다. (s=65)
이를 이용해 gam, B, k 행렬을 모두 알아내고 U_plain = (~k) * U_ * (~k) 계산을 통해 5바이트씩 저장된 4x4 사이즈의 행렬에서 평문을 복원해낸다.
마지막은 알아낸 flag[:30], flag[30:] 을 조합하면 끝.
3. Solution
> solve.sage
############################################################
# 0. Setup
############################################################
n = 445274615059837074703074129112359915057174632831812151523967
Zn = Zmod(n)
p = 460787053387729396804743714197
q = 966334908470530797510120137411
assert p*q == n
b_s = [394630328574245837271964995407645525864174759236154380643123, 181576505553348136346747373172404084614838614588476774583011, 47077957947512963105149976221929200145993567056781606375095, 89512069817356782446065533722663239350804126107686725128410, 373205572983197742790495284583000076470807977675517077486772, 23498650172584653123097600569326533466683470443976638497395]
Dr01 = 65121623752613515130879120572450892437787062242339581021972 # Dr[0][1]
Dr12 = 309119002962212926538831287621396239072826023374419794264806 # Dr[1][2]
Dr23 = 347470190991251003796270760779117025940129782467301096539733 # Dr[2][3]
A_list = [[267488503328751734811097261113084423911438725622299714310906, 241117396863105959600754534694070834476850425262709687269036, 214258198847456276524419017061190255640640610747513321186897, 243908647245747968722106141408796681516825496314767254191757], [296319709221599349271057047062188865965114280077923836145107, 71529348777992013834622878352061278318971600308100689319273, 21591870354281474475646302816674067646780297577032674955185, 329768812477769930550184723256646545904725913270398836212842], [393454646582482661433381653516719745488323555925451955187902, 194746794540595232682055052374882607738478749014201463302499, 334558373377320943753331767654378770755387190446496860928551, 56161017168485902852067920208271199031653238414912499757534], [266977137695022785306720925811441529661962591963589182595205, 16753429262712563178096867265259745231766743278052644485337, 253490251626334837867786572868935770318733416332589112030380, 22145971392163310763756103453873785465919607151396748455019]]
eps_list = [[192586917014788390326312911581471749597377333033259137675184, 129168876551996260342874367540015182845788848550489794697324, 57831749904731123118404758141603855187866531365624335427344, 195022502697866726972189757984030560180344345109946796156325], [135781469480802094592765423575750583422293592849340942790362, 194570494824611028514594474010420293134634552797088093148718, 40197041087045646329648689121888972810337539641412154942753, 171488839407647249066021945353574939028890470126691251018950], [321574053868131893139085098301380237612683258740173520412344, 52517421891213975251433410788690537724250142992816345255227, 333466758500180143561934683481914639597381284613553905277784, 352008560551548268582889491138232791723183260602131415827535], [251489871649117676162415757114107100160422729328280616605867, 103056811001222772929081702577039570831201708883461825815960, 431531126172591487922735317410797819329355211209825121991402, 420372641596485515463040070611951491179498585916205028436030]]
U__list = [[284748677963482855560647580975430987796843309477842402790596, 242337483266671138784804936005948727710979699483520088294751, 222789040283490430347316580802423043491056060923158051369962, 191112897515604587611641191854510105473086622421743591204621], [238170838594983786682252829258413429179238271948287974513470, 277493478941503842166499052157318771559824990881681931185164, 175870003968434125688348973363665346473569841390671788315745, 298283886414644176621219824782985590557056515812318580574622], [224658814356409335319395178072646711675997551719107602968739, 262450329784813814501873286313684579762178308313152721306551, 127386310370756304739779430076739347844666760625671518036044, 114206800882087686184914497540226589380365955487371216456391], [116661993725296521336028467679022554919505922084876672576011, 299846461555326343107174129245788821779256198458100923490486, 169617077441479678088743611019939106784337042750354690307174, 382330202935869270742131324475593286027520744344616893665932]]
A = Matrix(Zn, 4, 4, A_list)
eps = Matrix(Zn, 4, 4, eps_list)
U_ = Matrix(Zn, 4, 4, U__list)
############################################################
# 1. Symbolic D construction (over Zn[a,c])
############################################################
R.<a,c> = PolynomialRing(Zn)
# b_s extraction
b0, b1, b2, b3, b4, b5 = b_s
# c_s definition
c_s0 = a * c^5 + b0
c_s1 = (c + b1)^5 * a + b2
c_s2 = (c + b3)^5 * a^2 + b4 * a + b5
# D_sym matrix
D_sym = Matrix(R, 4, 4, 0)
# Diagonal entries
D_sym[0, 0] = a + c
D_sym[1, 1] = a^2 + c
D_sym[2, 2] = a^3 + c
D_sym[3, 3] = a^4 + c
# Remaining entries of Upper triangle
D_sym[0, 1] = c_s0
D_sym[0, 2] = ((b0 + b1) * a)^20
D_sym[0, 3] = ((b0 + b1) * a)^20
D_sym[1, 2] = c_s1
D_sym[1, 3] = ((b1 + b2) * a)^20
D_sym[2, 3] = c_s2
print("[+] D_sym built")
############################################################
# 2. Compute D^5 and extract needed entries: (0,1), (1,2), (2,3)
############################################################
print("[+] Computing D_sym^5 (may be slow)...")
D5_sym = D_sym^5
print("[+] Done")
D5_01 = D5_sym[0, 1]
D5_12 = D5_sym[1, 2]
D5_23 = D5_sym[2, 3]
############################################################
# 3. Solve for (a, c) modulo p and q via Groebner basis
############################################################
F01 = D5_01 - Dr01
F12 = D5_12 - Dr12
F23 = D5_23 - Dr23
primes = [p, q]
solutions = []
for prime in primes:
print(f"\n[+] Solving (a,c) mod {prime}")
Rp.<aprime, cprime> = PolynomialRing(GF(prime))
print(" Computing Groebner basis...")
I = Rp.ideal([F01, F12, F23])
gb = I.groebner_basis()
print(f" Groebner basis size: {len(gb)}")
print(f" gb: {gb}")
# Expect linear forms [aprime + const, cprime + const]
if len(gb) == 2:
g0, g1 = gb
a_sol = -g0.constant_coefficient()
c_sol = -g1.constant_coefficient()
solutions.append([a_sol, c_sol])
print(f" Solution: aprime={a_sol}, cprime={c_sol}")
else:
print(f" Failed to solve mod {prime}")
############################################################
# 4. Reconstruct (a,c) via CRT and build D
############################################################
a_vals = [ZZ(sol[0]) for sol in solutions]
c_vals = [ZZ(sol[1]) for sol in solutions]
a_val = crt(a_vals, primes)
c_val = crt(c_vals, primes)
print(f"\n[+] Valid (a,c) found:")
print(f" a = {a_val}")
print(f" c = {c_val}")
D = D_sym(a=a_val, c=c_val)
print("\n[+] Matrix D reconstructed")
############################################################
# 5. Recover m from c_val = m^6 (mod n) using known partial prefix
############################################################
prefix = b"shellmates{"
prefix_int = int.from_bytes(prefix, 'big')
shift_bits = (30 - len(prefix)) * 8
P.<x> = PolynomialRing(Zn)
f = (prefix_int * 2^shift_bits + x)^6 - c_val
for m_cand in f.roots(multiplicities=False):
m_cand = int(m_cand) # prevent Sage to compute in Zmod
m_cand = (prefix_int * 2^shift_bits + m_cand).to_bytes(30, "big")
if m_cand.startswith(prefix):
flag_head_bytes = m_cand
print(f"\n[+] Found flag[:30]: {flag_head_bytes}")
break
############################################################
# 6. Find s (1..1024) and decrypt U_
############################################################
print("\n[+] Brute-forcing s in [1..1024]")
for s in range(1, 2^10 + 1):
if s % 100 == 0:
print(f" s = {s} ...")
gam = D^(5 * s)
if not gam.is_invertible():
continue
check_eps = (~gam) * A * gam
if check_eps == eps:
print(f"[+] s found: {s}")
break
# B is not given explicitly, but from gen_pub: B = (~D) * (~A) * D
B = (~D) * (~A) * D
gam = D^(5 * s)
k = (~gam) * B * gam
if k.is_invertible():
U_plain = (~k) * U_ * (~k)
print("\n[+] U_plain matrix:")
print(U_plain)
flag_tail_bytes = b""
for x in U_plain.list():
v = int(x)
flag_tail_bytes += v.to_bytes(5, "big")
print("\n[+] Decrypted flag[30:] bytes:")
print(flag_tail_bytes)
else:
print("[-] k is not invertible")
### print final FLAG
print(f"\n[+] FLAG: {flag_head_bytes + flag_tail_bytes}")
> output
[+] D_sym built
[+] Computing D_sym^5 (may be slow)...
[+] Done
[+] Solving (a,c) mod 460787053387729396804743714197
Computing Groebner basis...
Groebner basis size: 2
gb: [aprime + 280298606918854739350729747621, cprime + 61756496956266078424452139909]
Solution: aprime=180488446468874657454013966576, cprime=399030556431463318380291574288
[+] Solving (a,c) mod 966334908470530797510120137411
Computing Groebner basis...
Groebner basis size: 2
gb: [aprime + 505635856485732946428464125503, cprime + 4369968139429109021813532246]
Solution: aprime=460699051984797851081656011908, cprime=961964940331101688488306605165
[+] Valid (a,c) found:
a = 6984562228976164308186288352048638049134096820033710941052
c = 423794457208599236789546473350747937877027098188338507803264
[+] Matrix D reconstructed
[+] Found flag1: b'shellmates{CayleyPurser_withou'
[+] Brute-forcing s in [1..1024]
[+] s found: 65
[+] U_plain matrix:
[499817411938 409823705407 409757445986 474148388703]
[418465281889 521291722608 435393224565 495622315892]
[448377352809 444134088557 478594166121 418430021490]
[431198726510 443982377844 448445769070 478711081085]
[+] Decrypted flag[30:] bytes:
b't_pub_key?_grobner?_anyway_hope_u_used_the_right_monomial_ordering_isthisenough}'
[+] FLAG: b'shellmates{CayleyPurser_without_pub_key?_grobner?_anyway_hope_u_used_the_right_monomial_ordering_isthisenough}'
'CTF writeups > Crypto' 카테고리의 다른 글
| [SSTF CTF 2022] CUSES (0) | 2022.08.31 |
|---|---|
| [n00bzCTF2022] RSA-OOPS (0) | 2022.06.08 |
| [Cyber Apocalypse CTF 2022] MOVs Like Jagger (0) | 2022.05.23 |
| [Cyber Apocalypse CTF 2022] How The Columns Have Turned (0) | 2022.05.20 |
| [Cyber Apocalypse CTF 2022] The Three-Eyed Oracle (0) | 2022.05.20 |