1. はじめに
2022/7/15(金) 23:00 JST ～ 7/16(土) 23:00 JSTに開催された「4th Crypto CTF 2022」にチーム「N30Z30N」でソロ参加し、"Mic Check"問以外で18問を解き、1782点（得点を得た421チーム中23位）を獲得しました。
Crypto CTF には毎年出場していますが、自分にとって比較的解きやすい問題が多数出題されているので、ソロで出て 24 時間頑張れる感じです。反省点としては、難易度 hard の問題をすべて残してしまった（トライすらしなかった）点です。
以下、簡単にですが（難易度易しい順、solve数多い順に） Writeupを記します。
2. Writeup
2-1. Baphomet (難易度：easy, 56 points, 93 solves)
☆設問
以下のスクリプトと、暗号化データの入った「flag.enc」が与えられます。
baphomet.py
#!/usr/bin/env python3
from base64 import b64encode
from flag import flag
def encrypt(msg):
ba = b64encode(msg.encode('utf-8'))
baph, key = '', ''
for b in ba.decode('utf-8'):
if b.islower():
baph += b.upper()
key += '0'
else:
baph += b.lower()
key += '1'
baph = baph.encode('utf-8')
key = int(key, 2).to_bytes(len(key) // 8, 'big')
enc = b''
for i in range(len(baph)):
enc += (baph[i] ^ key[i % len(key)]).to_bytes(1, 'big')
return enc
enc = encrypt(flag)
f = open('flag.enc', 'wb')
f.write(enc)
f.close()
☆方針・解法
既知平文攻撃的な考え方で解けます。
暗号文の長さは 48 バイトで、また Key の作り方から Key の長さは 6 バイトであることが分かります。フラグの始まりは「CCTF」なので1、Base64 エンコードした結果の先頭 6バイトは必ず「Q0NURn」になります。Key と xor する直前のデータの先頭は「q0nurN」ですから、これと暗号文の先頭 6 バイトを xor すれば Key は求まります。この Key を使って暗号化と逆の手順を踏めば復号できます。
☆ソルバ
solve.py
from base64 import b64decode
from pwn import xor
enc = open('flag.enc', 'rb').read()
_k = b"q0nurN"
key = xor(_k, enc[0:6])
_dec = b''
for i in range(len(enc)):
_dec += (enc[i] ^ key[i % len(key)]).to_bytes(1, 'big')
dec = ""
for b in _dec.decode('utf-8'):
if b.islower():
dec += b.upper()
else:
dec += b.lower()
dec = b64decode(dec.encode('utf-8'))
print(dec)
☆フラグ
CCTF{UpP3r_0R_lOwER_17Z_tH3_Pr0bL3M}
2-2. Klamkin (難易度：easy, 61 points, 83 solves)
☆設問
サーバに接続して解く問題です。
q, r, s が指定され、(a * r + b * s) % q == 0 となる a, b に対し (a * x + b * y) % q == 0 となる x, yを求めます。但し x, y いずれかのビット数が指定されます。
☆方針・解法
q, r, s が与えられた段階で、拡張ユークリッド互除法で条件を満た a, b を計算します。x や y の条件（ビット数、以下 "bits" と記す）が示されたら、サーバに以下の x, y を送ります。
・ x にビット数指定があった場合： x = 2**(bits-1)+1, y = s * x * a % q
・ y にビット数指定があった場合： x = -r * y * b % q, y = 2**(bits-1)+1
5 問正答するとフラグを得られました。
☆フラグ
CCTF{f1nDin9_In7Eg3R_50Lut1Ons_iZ_in73rEStIn9!}
2-3. polyRSA (難易度：medium-easy, 42 points, 145 solves)
☆設問
以下のスクリプト等が与えられます。
polyRSA.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def keygen(nbit = 64):
while True:
k = getRandomNBitInteger(nbit)
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
if isPrime(p) and isPrime(q):
return p, q
def encrypt(msg, n, e = 31337):
m = bytes_to_long(msg)
return pow(m, e, n)
p, q = keygen()
n = p * q
enc = encrypt(flag, n)
print(f'n = {n}')
print(f'enc = {enc}')
output.txt
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
☆方針・解法
SageMath の力を借りて解くことにしました。
競技中に行った解法は、「p, q を k を変数とする多項式と見たとき、p * q の定数項 を n から引いた数は k を割りるので、n - [p * q の定数項] の約数から k の候補を探索する」というものでした。
しかし、素直に f = p * q - n と置き、f の factor を見ればすぐ解けました。反省。
☆ソルバ（反省後）
solve2.sage
from Crypto.Util.number import *
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
e = 31337
PR.<k> = PolynomialRing(ZZ)
_p = k**6 + 7 * k**4 - 40 * k**3 + 12 * k**2 - 114 * k + 31377
_q = k**5 - 8 * k**4 + 19 * k**3 - 313 * k**2 - 14 * k + 14011
f = _p * _q - n
for x in f.factor():
if x[0].degree() == 1:
_k = -x[0].coefficients()[0]
p = _p(k=_k)
q = _q(k=_k)
phi = (p-1)*(q-1)
d = inverse(e, int(phi))
_pt = pow(int(enc), int(d), int(n))
m = long_to_bytes(pow(int(enc), int(d), int(n)))
if b"CCTF{" in m:
print(m)
break
☆フラグ
CCTF{F4C70r!N9_tRIcK5_aR3_fUN_iN_RSA?!!!}
2-4. SOTS (難易度：medium-easy, 49 points, 113 solves)
☆設問
サーバに接続して解く問題です。
n が示され、 x^2 + y^2 == n を満たす x と y を求める問題です。
☆方針・解法
Gauss 数体（の整数環）での素因数分解を考えれば OK です。
yafu を使ってn を素因数分解し、各素因数に対して SageMath で Gauss 数体での分解を計算し、その結果をもとに送信する x, y を構築しました。
競技時に示された n は整数の範囲で 3 つの素因数に分解されたため、
$$(x_1^2 + y_1^2) (x_2^2 + y_2^2) (x_3^2 + y_3^2) = X^2 + Y^2$$
ただし
$$(X,Y) := (x_1x_2x_3 + x_3y_1y_2 - x_2y_1y_3 + x_1y_2y_3, x_2x_3y_1 - x_1x_3y_2 + x_1x_2y_3 + y_1y_2y_3)$$
を利用して解を求めました。
☆ソルバ（n を素因数分解した後の計算に使ったもの）
solve.sage
n1 = 1403575103598950078497501
n2 = 1832215985571864173006269
n3 = 824314708499254102530821
R = ZZ[I]
n1 = R(n1)
x1 = factor(n1)[1][0][0]
y1 = factor(n1)[1][0][1]
n2 = R(n2)
x2 = factor(n2)[1][0][0]
y2 = factor(n2)[1][0][1]
n3 = R(n3)
x3 = factor(n3)[1][0][0]
y3 = factor(n3)[1][0][1]
X = abs(x1*x2*x3 + x3*y1*y2 - x2*y1*y3 + x1*y2*y3)
Y = abs(x2*x3*y1 - x1*x3*y2 + x1*x2*y3 + y1*y2*y3)
print(n1*n2*n3)
print((x1^2+y1^2)*(x2^2+y2^2)*(x3^2+y3^2))
print(X+Y)
print(f"{X},{Y}")
☆フラグ
CCTF{3Xpr3sS_4z_Th3_sUm_oF_7w0_Squ4rE5!}
2-5. Volgo (難易度：medium-easy, 65 points, 77 solves)
☆設問
Web サイトが示され、そこでは M-209 2 で任意（アルファベット大文字のみ）の平文を暗号化するサービスと、同じ暗号化方式・キーで暗号化したフラグが提供されます。
☆方針・解法
この暗号装置では 5 文字 1 ブロックで扱われ、またいろいろ試してみると先頭 2 ブロックと末尾 2 ブロックは Padding であることが推測されます。
また、鍵はわかりませんが、試してみると各文字の暗号化は独立している（他の暗号文に影響されない）ことが推測されます。
以上のことから、平文に相当する文字数（155文字）分、各アルファベット大文字を暗号化し。その結果から平文を求めることができます。
☆ソルバ
solve.py
import requests
alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
url1 = "http://<省略>/flag/fetch"
res = requests.get(url1)
enc = eval(res.text)['flag'].replace(' ', '')[10:-10]
d = {}
url2 = "http://<省略>/m209/encipher"
for i in range(0x41, 0x41+26):
to_send = chr(i)*155
res = requests.post(url2,data={"plain":to_send})
d[chr(i)] = eval(res.text)['cipher'].replace(' ', '')[10:-10]
flag = ""
for i in range(len(enc)):
for c in alpha:
print(enc[i], d[c][i], c)
if enc[i] == d[c][i]:
flag += c
break
print(flag.replace("Z"," "))
#YOU KNOW HOW TO FORMAT FLAG JUST PUT UPCOMING LETTERS WITHIN CURLY BRACES FOLLOWED BY CCTF OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR
☆フラグ
CCTF{OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR}
2-6. Jeksign (難易度：medium-easy, 100 points, 45 solves)
☆設問
サーバに接続して解く問題です。
本問ではスクリプトが示されています3。
1337(z^4 - x^2) == 31337(y^2 - z^4) を満たす x, y, z を答える問題です。設問は 19 個あり、z のビット数は 30-bit から 1 ずつ増え 48-bit まで指定されます。
jeksign.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from secret import gensol, nbit_gensol
from flag import flag
m = bytes_to_long(flag.encode('utf-8'))
print(m)
a = 1337
b = 31337
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "|"
pr(border*72)
pr(border, "Welcome crypto guys! Here we are looking for the solution of special", border)
pr(border, "Diophantine equation: 1337(z^4 - x^2) = 31337(y^2 - z^4) in natural ", border)
pr(border, "numbers, in each stage solve the equation in mentioned interval :) ", border)
pr(border*72)
STEP, level = 0, 19
while True:
p, q = nbit_gensol(1337, 31337, STEP + 30)
x, y, z = gensol(a, b, p, q)
pr(border, f"Send a solution like `x, y, z' such that the `z' is {STEP + 30}-bit: ")
ans = sc()
try:
X, Y, Z = [int(_) for _ in ans.split(',')]
NBIT = Z.bit_length()
except:
die(border, 'Your input is not valid, Bye!')
if 1337*(Z**4 - X**2) == 31337*(Y**2 - Z**4) and NBIT == STEP + 30:
if STEP == level - 1:
die(border, f'Congrats, you got the flag: {flag}')
else:
pr('| good job, try to solve the next challenge :P')
STEP += 1
else:
die(border, 'your answer is not correct, Bye!!')
if __name__ == '__main__':
main()
☆方針・解法
z を 1 つ決めてしまえば、x = y = z^2 という自明な解が塞がれていないので簡単に通ってしまいます。
☆ソルバ
solve.py
import telnetlib
HOST = <省略>
PORT = <省略>
def readline():
return tn.read_until(b"\n")
def sendline(to_send):
tn.write(to_send.encode() + b"\n")
tn = telnetlib.Telnet(HOST, PORT)
for i in range(5):
readline()
for i in range(30, 49):
print(readline())
z = 2**(i-1)
x = z**2
y = z**2
to_send = str(x) + "," + str(y) + "," + str(z)
sendline(to_send)
print(readline())
☆フラグ
CCTF{4_diOpH4nT1nE_3Qua7i0n__8Y__Jekuthiel_Ginsbur!!}
2-7. Keydream (難易度：medium-easy, 105 points, 42 solves)
☆設問
RSA 問です。以下のスクリプト等が提示されます。
keydream.py
#!/usr/bin/env python3
from Crypto.Util.number import *
import string
from flag import flag
def randstr(l):
rstr = [(string.printable[:62] + '_')[getRandomRange(0, 62)] for _ in range(l)]
return ''.join(rstr)
def encrypt(msg, l):
while True:
rstr = 'CCTF{it_is_fake_flag_' + randstr(l) + '_90OD_luCk___!!}'
p = bytes_to_long(rstr.encode('utf-8'))
q = bytes_to_long(rstr[::-1].encode('utf-8'))
if isPrime(p) and isPrime(q):
n = p * q
e, m = 65537, bytes_to_long(msg.encode('utf-8'))
c = pow(m, e, n)
return n, c
n, c = encrypt(flag, 27)
print(f'n = {n}')
print(f'c = {c}')
output.txt
n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609
☆方針・解法
pの（qもですが）十分小さい一部分だけが未知ですので、Coppersmith（SageMath の small_roots）で解けます。
☆ソルバ
solve.sage
from Crypto.Util.number import *
n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609
e = 65537
l = 27
PR.<x> = PolynomialRing(Zmod(n))
base = bytes_to_long(b'CCTF{it_is_fake_flag_' + b'\x00' * l + b'_90OD_luCk___!!}')
f = 256**16 * x + base
f = f.monic()
r = f.small_roots(X=256**l, beta=0.3)
p = int(256**16 * r[0] + base)
q = n // p
assert p * q == n
phi = (p-1)*(q-1)//GCD(p-1,q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(int(c),int(d),int(n))))
☆フラグ
CCTF{h0M3_m4dE_k3Y_Dr1vEn_CrYp7O_5ySTeM!}
2-8. Infinity castle (難易度：medium-easy, 131 points, 32 solves)
☆設問
以下のスクリプト等が提示されます。
RSA 問で、p, q の計算に必要な情報が示されますが、何も考えずそのまま計算式を実行するとベラボーな時間がかかる仕掛けとなっています。
infinity_castle.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from os import urandom
class TaylorSeries():
def __init__(self, order):
self.order = order
def coefficient(self, n):
i = 0
coef = 1
while i < n:
i += 1
coef *= (coef * (1/2-i+1)) / i
return coef
def find(self, center):
sum = 0
center -= 1
i = 0
while i < self.order:
sum += (center**(1/2-i) * self.coefficient(i))
i += 1
return sum
def xor(cip, key):
repeation = 1 + (len(cip) // len(key))
key = key * repeation
key = key[:len(cip)]
msg = bytes([c ^ k for c, k in zip(cip, key)])
return msg
# If you run these 3 functions (diamond, triage, summarize) with big numbers, they will never end
# You need to optimize them first
def diamond(num):
output = 0
for i in range(num):
output += i*2 + 1
return output
def triage(num):
output = 0
index = 0
for i in range(num):
output += (i+index)*6 + 1
index += i
return output
def summarize(b):
order = getRandomRange(1000, 2000)
t = TaylorSeries(order)
output = 0
i = 2
while i < b:
b1 = t.find(i)
b2 = t.find(i+1)
output += (b1+b2) / 2
i += 1
return output
KEY_SIZE = 2048
p, q = [getPrime(KEY_SIZE) for _ in '01']
e, n = 0x10001, p*q
f = open ('./message.txt', 'rb')
message = f.read()
f.close()
msg_length = len(message)
padded_msg = message + urandom(len(long_to_bytes(n)) - msg_length)
padded_msg_length = len(padded_msg)
xor_key = long_to_bytes(int(summarize(n)))[:padded_msg_length]
assert(len(xor_key) == 512)
enc0 = xor(padded_msg, xor_key)
assert(bytes_to_long(enc0) < n)
c0 = abs(diamond(p) - diamond(q))
c1 = triage(p)
c1 += 3*n*(p+q)
c1 += triage(q)
m = bytes_to_long(enc0)
enc1 = pow(m, e, n)
print(f"c0 = {c0}")
print(f"c1 = {c1}")
print(f"enc = {enc1}")
output.txt
c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045
☆方針・解法
「膨大な計算量を数学の力で何とかする」的な問題です。個人的な好き嫌いで言えば、こういうのが「大好き」です。
コードを読み解くと、diamond は平方、triage は立方を計算するものであることが分かります（高校数学のΣ計算を思い出しましょう）。
よって、c0 = |p^2-q^2|、c1 = (p+q)^3 であることがわかり、これらから容易に p, q が計算できます。
また、TaylorSeries の find は平方根の近似計算にほかなりません。summarize は平方根の総和をベースに算出できますが、平方根の総和には近似式
$$\sum_{k=1}^n \sqrt{k} \fallingdotseq \frac{2n^{\frac{3}{2}}}{3} + \frac{\sqrt{n}}{2} $$
があるのでそれを利用します4。
☆ソルバ
solve.sage
from Crypto.Util.number import *
from ptrlib import xor
import gmpy2
def summarize(n):
K = RealField(4096)
x = K(n)
sum = 2 * x^(3/2) /3 + x^(1/2)/2
return sum - 1 - K(2).nth_root(2)/2 - x.nth_root(2)/2
c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045
p_plus_q = gmpy2.iroot(c1,3)[0]
p_minus_q = c0 // p_plus_q
p = int((p_plus_q + p_minus_q) // 2)
q = int(p_plus_q - p)
n = p * q
phi = (p-1)*(q-1)//GCD(p-1,q-1)
d = inverse(0x10001, phi)
m = pow(enc, d, n)
xor_key = long_to_bytes(int(summarize(n)))[:512]
msg = xor(long_to_bytes(int(m)), xor_key)
print(msg)
☆フラグ
CCTF{Mix1ng_c4lcUluS_w17h_Numb3r_The0Rry_S33ms_s7r0ng_cRyp70_Sch3m4!!}
2-9. Aniely (難易度：medium, 66 points, 76 solves)
☆設問
以下のスクリプト等が提示されます。
chacha20 の亜流のような stream 暗号です。
aniely.py
#!/usr/bin/env python3
from struct import *
from os import *
from secret import passphrase, flag
def aniely_stream(passphrase):
def mixer(u, v):
return ((u << v) & 0xffffffff) | u >> (32 - v)
def forge(w, a, b, c, d):
for i in range(2):
w[a] = (w[a] + w[b]) & 0xffffffff
w[d] = mixer(w[a] ^ w[d], 16 // (i + 1))
w[c] = (w[c] + w[d]) & 0xffffffff
w[b] = mixer(w[b] ^ w[c], (12 + 2*i) // (i + 1))
bring = [0] * 16
bring[:4] = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
bring[4:12] = unpack('<8L', passphrase)
bring[12] = bring[13] = 0x0
bring[14:] = [0] * 2
while True:
w = list(bring)
for _ in range(10):
forge(w, 0x0, 0x4, 0x8, 0xc)
forge(w, 0x1, 0x5, 0x9, 0xd)
forge(w, 0x2, 0x6, 0xa, 0xe)
forge(w, 0x3, 0x7, 0xb, 0xf)
forge(w, 0x0, 0x5, 0xa, 0xf)
forge(w, 0x1, 0x6, 0xb, 0xc)
forge(w, 0x2, 0x7, 0x8, 0xd)
forge(w, 0x3, 0x4, 0x9, 0xe)
for c in pack('<16L', *((w[_] + bring[_]) & 0xffffffff for _ in range(16))):
yield c
bring[12] = (bring[12] + 1) & 0xffffffff
if bring[12] == 0:
bring[13] = (bring[13] + 1) & 0xffffffff
def aniely_encrypt(msg, passphrase):
if len(passphrase) < 32:
passphrase = (passphrase * (32 // len(passphrase) + 1))[:32]
rand = urandom(2) * 16
return bytes(a ^ b ^ c for a, b, c in zip(msg, aniely_stream(passphrase), rand))
key = bytes(a ^ b for a, b in zip(passphrase, flag))
enc = aniely_encrypt(passphrase, key)
print(f'key = {key.hex()}')
print(f'enc = {enc.hex()}')
output.txt
key = 4dcceb8802ae3c45fe80ccb364c8de19f2d39aa8ebbfb0621623e67aba8ed5bc
enc = e67a67efee3a80b66af0c33260f96b38e4142cd5d9426f6f156839f2e2a8efe8
☆方針・解法
「rand を固定したとき aniely_encrypt(enc, key) = passphrase」をエスパーしたので解けました。
rand の部分は 2 バイトなので総当たりします。
☆ソルバ
solve.py
from Crypto.Util.number import *
from struct import *
from os import *
from pwn import xor
key = bytes.fromhex("4dcceb8802ae3c45fe80ccb364c8de19f2d39aa8ebbfb0621623e67aba8ed5bc")
enc = bytes.fromhex("e67a67efee3a80b66af0c33260f96b38e4142cd5d9426f6f156839f2e2a8efe8")
def aniely_stream(passphrase):
def mixer(u, v):
return ((u << v) & 0xffffffff) | u >> (32 - v)
def forge(w, a, b, c, d):
for i in range(2):
w[a] = (w[a] + w[b]) & 0xffffffff
w[d] = mixer(w[a] ^ w[d], 16 // (i + 1))
w[c] = (w[c] + w[d]) & 0xffffffff
w[b] = mixer(w[b] ^ w[c], (12 + 2*i) // (i + 1))
bring = [0] * 16
bring[:4] = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
bring[4:12] = unpack('<8L', passphrase)
bring[12] = bring[13] = 0x0
bring[14:] = [0] * 2
while True:
w = list(bring)
for _ in range(10):
forge(w, 0x0, 0x4, 0x8, 0xc)
forge(w, 0x1, 0x5, 0x9, 0xd)
forge(w, 0x2, 0x6, 0xa, 0xe)
forge(w, 0x3, 0x7, 0xb, 0xf)
forge(w, 0x0, 0x5, 0xa, 0xf)
forge(w, 0x1, 0x6, 0xb, 0xc)
forge(w, 0x2, 0x7, 0x8, 0xd)
forge(w, 0x3, 0x4, 0x9, 0xe)
for c in pack('<16L', *((w[_] + bring[_]) & 0xffffffff for _ in range(16))):
yield c
bring[12] = (bring[12] + 1) & 0xffffffff
if bring[12] == 0:
bring[13] = (bring[13] + 1) & 0xffffffff
def aniely_encrypt(msg, passphrase):
if len(passphrase) < 32:
passphrase = (passphrase * (32 // len(passphrase) + 1))[:32]
#rand = urandom(2) * 16
rand = b"\x00"*32
return bytes(a ^ b ^ c for a, b, c in zip(msg, aniely_stream(passphrase), rand))
_passphrase = aniely_encrypt(enc, key)
for i in range(0x10000):
passphrase = xor(_passphrase, i.to_bytes(2,"big"))
flag = xor(passphrase, key)
if b"CCTF{" in flag:
print(flag)
break
☆フラグ
CCTF{7rY_t0_D3cRyPT_z3_ChaCha20}
2-10. Diploma (難易度：medium, 72 points, 68 solves)
☆設問
行列の order を求める問題が複数出されます。
☆方針・解法
Jordan 標準形を求め、対角成分（固有多項式の根）の order の LCM を計算します5。
order の計算では他に乗ずるべき値があるのですが、結果的に 1 になるものしか出題されなかったので無視できました。
（2022/7/26追記：Jordan 標準形の計算を手で行わず、直接 M.multiplicative_order() で行列の order は計算できました。SageMath 強いです。）
☆ソルバ（汚いです。スミマセン。）
solve.sage
from Crypto.Util.number import *
import telnetlib
HOST = <省略>
PORT = <省略>
def readline():
return tn.read_until(b"\n")
def readuntil(stopper):
return tn.read_until(stopper.encode())
def sendline(to_send):
tn.write(to_send.encode() + b"\n")
def linestrip(s):
s = s.strip()
while(True):
_s = s
s = s.replace(" ", " ")
if _s == s:
break
s = s.replace("[ ", "[")
s = s.replace(" ]", "]")
s = s.replace(" ", ",")
return eval(s)
tn = telnetlib.Telnet(HOST, PORT)
for i in range(6):
readline()
while(True):
p = int(readline().decode().replace("| Generating the parameters for p = ", "").replace(", please wait...", ""))
print("p=", p)
readline()
data = readuntil("| Send the order of matrix M:").decode().split("\n")
#print(data)
m = []
for i in range(len(data)-1):
m.append(linestrip(data[i]))
print(m)
M = Matrix(GF(p),m)
s = len(M.rows())
chM = M.charpoly()
K.<a> = chM.splitting_field()
_M = Matrix(K, M)
J, X = _M.jordan_form(transformation=True)
ans = 1
for i in range(s):
ans = LCM(ans, J[i][i].multiplicative_order())
print(ans)
sendline(str(ans))
readline()
result = readline()
print(result)
if b"CCTF" in result:
break
☆フラグ
CCTF{ma7RicES_4R3_u5EfuL_1n_PUbl!c-k3y_CrYpt0gr4Phy!}
2-11. Cantilever (難易度：medium, 79 points, 60 solves)
☆設問
以下の通り、スクリプト等が提示されます。
cantilever.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def gen_primes(nbit, imbalance):
p = 2
FACTORS = [p]
while p.bit_length() < nbit - 2 * imbalance:
factor = getPrime(imbalance)
FACTORS.append(factor)
p *= factor
rbit = (nbit - p.bit_length()) // 2
while True:
r, s = [getPrime(rbit) for _ in '01']
_p = p * r * s
if _p.bit_length() < nbit: rbit += 1
if _p.bit_length() > nbit: rbit -= 1
if isPrime(_p + 1):
FACTORS.extend((r, s))
p = _p + 1
break
FACTORS.sort()
return (p, FACTORS)
def genkey(nbit, imbalance, e):
while True:
p, FACTORS = gen_primes(nbit // 2, imbalance)
if len(FACTORS) != len(set(FACTORS)):
continue
q, q_factors = gen_primes(nbit // 2, imbalance + 1)
if len(q_factors) != len(set(q_factors)):
continue
factors = FACTORS + q_factors
if e not in factors:
break
n = p * q
return n, (p, q)
nbit = 2048
imbalance = 19
e = 0x10001
m_1 = bytes_to_long(flag[:len(flag) // 2])
m_2 = bytes_to_long(flag[len(flag) // 2:])
n, PRIMES = genkey(nbit, imbalance, e)
c_1 = pow(m_1, e, n)
c_2 = pow(e, m_2, n)
print(f'n = {n}')
print(f'c_1 = {c_1}')
print(f'c_2 = {c_2}')
output.txt
n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
☆方針・解法
n の素因数は 2^19-smooth なので、p, q の算出には p-1 法が使えます。
c_1 は通常の RSA で復号できますが、 c_2 は discrete log の計算が必要でしたので SageMath の力を借りました。
☆ソルバ
solve1.py
#https://haru-note3.com/prime/Pollards-p-minus-1-algorithm.html
from sympy import primerange, nextprime
import math
def p_minus_1_method(n, B, a=2):
for prime in primerange(1, B + 1):
l = math.floor(math.log(n) / math.log(prime))
a = pow(a, prime**l, n)
#print(prime)
d = math.gcd(a - 1, n)
if 1 < d and d < n:
return d
else:
return "unsolved"
n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
B = 2**19
a = 2
while(True):
res = p_minus_1_method(n, B, a)
if res != "unsolved":
print(res)
break
a = nextprime(a)
print(a)
#83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519
solve2.sage
from Crypto.Util.number import *
n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
e = 0x10001
p = 83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519
q = n // p
assert p*q == n
phi = (p-1)*(q-1)//GCD(p-1,q-1)
d1 = int(inverse(e, phi))
m1 = int(pow(int(c_1), d1,n))
Fp = GF(p)
Fq = GF(q)
c2p = Fp(c_2)
c2q = Fq(c_2)
ep = Fp(e)
eq = Fq(e)
dp = discrete_log(c2p, ep)
dq = discrete_log(c2q, eq)
m2 = int(crt([dp,dq],[p-1,q-1]))
m = long_to_bytes(m1) + long_to_bytes(m2)
print(long_to_bytes(m1))
☆フラグ
CCTF{5L3Ek_4s__s1lK__Ri9H7?!}
2-12. DBB (難易度：medium, 103 points, 43 solves)
☆設問
ECDLP 問です。以下の通りスクリプト等が提示されます。
dbb.sage
#!/usr/bin/env sage
from Crypto.Util.number import *
from secret import n, B, BASE_POINT, FLAG
m = bytes_to_long(FLAG)
assert m < n
F = IntegerModRing(n)
E = EllipticCurve(F, [31337, B])
BASE_POINT = E(BASE_POINT)
P = m * BASE_POINT
print(f'n = {n}')
print(f'BASE_POINT.x = {BASE_POINT.xy()[0]}')
print(f'P = {P.xy()[0], P.xy()[1]}')
output.txt
n = 34251514713797768233812437040287772542697202020425182292607025836827373815449
BASE_POINT.x = 7331
P = (10680461779722115247262931380341483368049926186118123639977587326958923276962, 4003189979292111789806553325182843073711756529590890801151565205419771496727)
☆方針・解法
n が合成数なので、n の各素因数を法とした楕円曲線での DLP を解き、その結果を CRT して元の楕円曲線での DLP の解を導きます（Pohlig-Hellman法）。
CRT するときの modulo は各楕円曲線における G の order となることに注意します。
☆ソルバ
solve.sage
n = 34251514713797768233812437040287772542697202020425182292607025836827373815449
bx = 7331
P = (10680461779722115247262931380341483368049926186118123639977587326958923276962, 4003189979292111789806553325182843073711756529590890801151565205419771496727)
B = P[1]^2 - P[0]^3 - 31337 * P[0] % n
F = IntegerModRing(n)
E = EllipticCurve(F, [31337, B])
G = E.lift_x(bx)
P = E(P)
ps = [11522256336953175349, 14624100800238964261, 203269901862625480538481088870282608241]
assert n == ps[0]*ps[1]*ps[2]
E0 = EllipticCurve(GF(ps[0]), [31337, B])
P0 = E0(P)
G0 = E0(G)
d0 = G0.discrete_log(P0)
E1 = EllipticCurve(GF(ps[1]), [31337, B])
P1 = E1(P)
G1 = E1(G)
d1 = G1.discrete_log(P1)
E2 = EllipticCurve(GF(ps[2]), [31337, B])
P2 = E2(P)
G2 = E2(G)
d2 = G2.discrete_log(P2)
m = crt([int(d0),int(d1),int(d2)],[G0.order(),G1.order(),G2.order()])
print(long_to_bytes(m))
☆フラグ
CCTF{p0Hl!9_H31LmaN_4tTackin9!}
2-13. Starter ECC (難易度：medium, 103 points, 43 solves)
☆設問
ECDLP 問・・・と見せかけて、実は合成数における平方根算出問題です。
starter_ecc.sage
#!/usr/bin/env sage
from Crypto.Util.number import *
from secret import n, a, b, x, flag
y = bytes_to_long(flag.encode('utf-8'))
assert y < n
E = EllipticCurve(Zmod(n), [a, b])
try:
G = E(x, y)
print(f'x = {x}')
print(f'a = {a}')
print(f'b = {b}')
print(f'n = {n}')
print('Find the flag :P')
except:
print('Ooops, ERROR :-(')
output.txt
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
Find the flag :P
☆方針・解法
n をいくつかに分解し、それぞれの mod. で平方根を計算して CRT をとります。
平方根は各々の mod. で複数存在し得るので、フラグ（b"CCTF{"）を含むものを全探索します。
各 mod. での平方根計算では、sqrt だとなぜか失敗することが多いので、nth_root を使ったところサクッと計算できました。
☆ソルバ（競技で使ったものを一部改良）
solve.sage
from Crypto.Util.number import *
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
n0 = 2^63
n1 = 690712633549859897233^6
n2 = 651132262883189171676209466993073^5
assert n == n0*n1*n2
R0 = Zmod(n0)
x0 = R0(x)
y0s = R0(x0^3 + a*x0 + b).nth_root(2, all=True)
R1 = Zmod(n1)
x1 = R1(x)
y1s = R1(x1^3 + a*x1 + b).nth_root(2, all=True)
R2 = Zmod(n2)
x2 = R2(x)
y2s = R2(x2^3 + a*x2 + b).nth_root(2, all=True)
for y0 in y0s:
for y1 in y1s:
for y2 in y2s:
y = crt([int(y0),int(y1),int(y2)],[int(n0),int(n1),int(n2)])
m = long_to_bytes(y)
if b"CCTF{" in m:
print(m)
break
☆フラグ
CCTF{8E4uTy_0f_L1f7iN9_cOm3_Up!!}
2-14. Oak land (難易度：medium, 122 points, 35 solves)
☆設問
DLP っぽい問題です。以下のスクリプト等が提示されます。
oak_land.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576
x = bytes_to_long(flag.encode('utf-8'))
assert x < p
c = (110 * pow(e, x, p) + 313 * pow(f, x, p) + 114 * pow(g, x, p)) % p
print(f'c = {c}')
output.txt
c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
☆方針・解法
最初見たときは無理ゲーじゃね？と思ったのですが、f や g を e のべき乗で表現して pow(e, x, p) を X と置けば、 c は X の多項式で表せるので、X が計算できさらに DLP で x が分かりそうです。
☆ソルバ（実際は SageMath のコンソールに 1 行ずつ入力して計算を進めました）
solve.sage
from Crypto.Util.number import *
c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576
F = GF(p)
g = F(g)
f = F(f)
e = F(e)
c = F(c)
a = discrete_log(f, e) #p-2
b = discrete_log(g, e) #p-3
PR.<X> = PolynomialRing(F)
pol = (110*X^3 + 313*X + 114 - c * X^2 ).monic()
xx = pol.roots()[0][0] #6621736714803975486469770941631918297557515256645141403866696899656801529069492623812629032566382224631133756513615225604518504150834965984951182186972792703483282014259169249309903503054330793332575590535531
x = discrete_log(xx,e)
#130669746807581038734209381694055163726297497321549047017439654852953086676029610991997
print(long_to_bytes(x))
☆フラグ
CCTF{V33333rY_eeeeZy_DLP_cH41L3n9E!}
2-15. Resign (難易度：medium, 122 points, 35 solves)
☆設問
サーバに接続して解く署名系の問題です。
以下の通り、スクリプトが提示されます。
resign.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from hashlib import sha1
import sys
from flag import flag
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "|"
pr(border*72)
pr(border, " Hi, Try to guess our RSA private key to sign my message, talented ", border)
pr(border, " hackers like you ;) are able to do it, they are *Super Guesser* :) ", border)
pr(border*72)
p, q = [getPrime(1024) for _ in '__']
n, e = p * q, 65537
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
MSG = b'::. Can you forge any signature? .::'
h = bytes_to_long(sha1(MSG).digest())
SIGN = pow(h, d, n)
while True:
pr("| Options: \n|\t[G]uess the secret key \n|\t[R]eveal the parameters \n|\t[S]ign the message \n|\t[P]rint the signature \n|\t[Q]uit")
ans = sc().lower()
if ans == 'g':
pr(border, f"please send the RSA public exponent and PARAMS p, q separated by comma like e, p, q: ")
PARAMS = sc()
try:
E, P, Q = [int(_) for _ in PARAMS.split(',')]
if P.bit_length() == Q.bit_length() == 1024 and P != Q:
N = P * Q
PHI = (P - 1) * (Q - 1)
D = inverse(E, PHI)
if pow(h, D, N) == SIGN:
e, n, d = E, N, D
pr(border, 'Great guess, now you are able to sign any message!!!')
else:
pr(border, 'Your RSA parameters are not correct!!')
else: raise Exception('Invalid RSA parameters!!')
except: pr(border, "Something went wrong!!")
elif ans == 'r':
pr(border, f'e = {e}')
pr(border, f'n = {n}')
elif ans == "p":
pr(border, f'SIGN = {SIGN}')
elif ans == 's':
pr(border, "Please send the signature of this message: ")
pr(border, f"MSG = {MSG[4:-4]}")
sgn = sc()
try:
sgn = int(sgn)
_continue = True
except:
pr(border, "Something went wrong!!")
_continue = False
if _continue:
_MSG = MSG[4:-4]
_h = bytes_to_long(sha1(_MSG).digest())
if pow(sgn, e, n) == _h:
die(border, "Congrats! your got the flag: " + flag)
else:
pr(border, "Sorry, your signature is not correct!")
elif ans == 'q': die("Quitting ...")
else: die("Bye bye ...")
if __name__ == "__main__": main()
☆方針・解法
競技終了が近かったので、思考回路がgdgdで以下のようにしか考えられませんでした。
やるべきこと：pow(sgn, e, n) == _h となる sgn を答える
できること：e, n（,d） を別の E. N (,D) にすげ替える（ただし、D = inverse(E,phi(N)としたとき、pow(h, D, N) == SIGNを満たさなければならない）
どうすればよいか： sign = pow(_h, D, N) を送ればよい。ただし、D, N は pow(h, D, N) == SIGN を満たさなければいけない。
⇒ smooth な P, Q で N を構成し、D = discrete_log(SIGH, h) を探索します。mod.P（mod.Q）でこの DLP が解をもつとは限らないので、解を持つようなもので、なおかつ E = inverse(D, phi(N))が計算できるようなものを選定しなければならない。
⇒ smooth な P, Q で、D に関する DLP が解けて E が計算できるようなものをガチャ
・・・とこんな具合に考えて作ったのが以下のソルバです。
☆ソルバ（競技でつかったものほぼそのままですので、超汚いです）
solve.sage
from Crypto.Util.number import *
import telnetlib
from hashlib import sha1
from random import randint
import sys
HOST = <省略>
PORT = <省略>
def readline():
return tn.read_until(b"\n")
def readuntil(stopper):
return tn.read_until(stopper.encode())
def sendline(to_send):
tn.write(to_send.encode() + b"\n")
S = 20 #20はテキトー
def getSmoothPrime():
base = 1
for i in range(1024 // S):
base *= getPrime(S)
#L = 1024 - int(base).bit_length()
L = 1024 - base.nbits()
print(L)
while(True):
#x = int(base * randint(2**(L-1),2**L) + 1)
x = 2*getPrime(L-1)*base + 1
#print(x.nbits())
#if isPrime(x) and x.bit_length() == 1024:
if isPrime(x) and x.nbits() == 1024:
return x
smoothprimes = []
for i in range(30):#30はテキトー
smoothprimes.append(getSmoothPrime())
print("start:")
tn = telnetlib.Telnet(HOST, PORT)
for i in range(10):
readline()
MSG = b'::. Can you forge any signature? .::'
h = bytes_to_long(sha1(MSG).digest())
sendline("P")
SIGN = int(readline().decode().replace("| SIGN = ",""))
print(f"SIGN={SIGN}")
cands=[]
ok = False
i = 0
while(True):
try:
p = smoothprimes[i]
i += 1
Fp = GF(p)
hp = Fp(h)
SIGNp = Fp(SIGN)
dp = discrete_log(SIGNp, hp)
cand = (int(p), int(dp))
print(cand)
if not cand in cands:
for _cand in cands:
try:
P = cand[0]
Q = _cand[0]
D = int(crt([cand[1],_cand[1]],[P-1, Q-1]))
PHI = (P-1)*(Q-1)
E = inverse(D, PHI)
N = P * Q
if (E*D - 1) % PHI != 0:
print("bad E and D")
print(GCD(E, PHI), GCD(D, PHI))
elif pow(int(h), D, int(N)) != SIGN % N:
print("bad D")
else:
ok = True
break
except Exception as ex:
print(ex)
pass
cands.append(cand)
except Exception as ex:
print(ex)
continue
if ok:
break
if i >= 30: #30はテキトー
exit()
print(f"P={P}")
print(f"Q={Q}")
print(f"E={E}")
print(f"D={D}")
print(f"N={N}")
for i in range(6):
readline()
#print(readline())
sendline("G")
print(readline())
to_send = str(E) + ", " + str(P) + ", " + str(Q)
sendline(to_send)
print(readline())
for i in range(6):
readline()
sendline("S")
print(readline())
print(readline())
_MSG = MSG[4:-4]
_h = bytes_to_long(sha1(_MSG).digest())
sgn = pow(_h, D, N)
to_send = str(sgn)
sendline(to_send)
print(readline())
print(readline())
☆フラグ
CCTF{Unkn0wN_K3y_5h4rE_4t7aCk_0n_Th3_RSA!}
※おそらくもっとスマートに解けるはずです。。。
2-16. Sparse (難易度：medium-hard, 114 points, 38 solves)
☆設問
RSA 問です。以下の通りスクリプト等が提示されます。
sparse.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def sparse(p, k):
nbit = p.bit_length()
while True:
CF = [getRandomRange(-1, 1) for _ in '_' * k]
XP = [getRandomRange(3, nbit - 3) for _ in '_' * k]
A = sum([CF[_] * 2 ** XP[_] for _ in range(0, k)])
q = p + A
if isPrime(q) * A != 0:
return q
p = getPrime(417)
q = sparse(p, 5)
e, n = 65537, p * q
print(f'n = {n}')
m = bytes_to_long(flag.encode('utf-8'))
assert m < n
c = pow(m, e, n)
print(f'c = {c}')
output.txt
n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857
☆方針・解法
p, q の構成法に問題があり、p に対し、q = p - d, d = (1～5個の2冪の和)という形で作っています。
つまり、d を全探索し、X^2 - X*d - n = 0 が素数の解を持った時それが p の候補となります。
実際、d は 2**284 でしたが、もし d が 5 個の 2 ベキの和だと計算時間的に苦しく、う～んと思った問題でした。
☆ソルバ（例によって汚いです）
solve.py
import itertools
import gmpy2
from Crypto.Util.number import *
n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857
e = 65537
def check(d):
if gmpy2.iroot(d**2 + 4*n,2)[1] != True:
return False
D = gmpy2.iroot(d**2 + 4*n,2)[0]
if GCD((d + D) // 2, n) != 1:
p = (d + D) // 2
q = n // p
print(p, q)
phi = (p-1)*(q-1)//GCD(p,q)
d = inverse(e, phi)
print(long_to_bytes(pow(c,d,n)))
return True
else:
return False
table = []
for i in range(3, 414):
table.append(2**i)
for i in [1,5]:
print(i)
for X in itertools.combinations(table, i):
d = 0
for x in X:
d += x
if check(d):
exit()
☆フラグ
CCTF{5pArs3_dIfFeRenc3_f4ct0r1za7iOn_m3th0d!}
2-17. Lagima (難易度：medium-hard, 164 points, xx solves)
☆設問
以下のスクリプト等が提示されます。
対称群における DLP のような問題です。
lagima.sage
#!/usr/bin/env sage
from flag import flag
def genperm(n):
_ = list(range(1, n + 1))
shuffle(_)
return _
def genlatrow(n):
A = []
for _ in range(n): A.append(genperm(n))
return A
def prodlat(A, B):
assert len(A) == len(B)
C, G = [], SymmetricGroup(len(A))
for _ in range(len(A)):
g = (G(A[_]) * G(B[_])).tuple()
C.append(list(g))
return C
def powlat(A, n):
assert n >= 0
B = bin(n)[2:]
c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
if n == 0: return R
else:
for b in B:
if b == '1':
if c == 1: R = prodlat(R, A)
else:
T = A
for _ in range(c - 1): T = prodlat(T, T)
R = prodlat(R, T)
c -= 1
return R
G = genlatrow(313)
secret = int.from_bytes(flag.lstrip(b'CCTF{').rstrip(b'}'), 'big')
H = powlat(G, secret)
print(f'G = {G}')
print(f'H = {H}')
output.txt
G = <313×313の配列、省略>
H = <313×313の配列、省略>
☆方針・解法
数学的なウラをとらず、カンだけで解きました（競技なのでヨシ！）
LCM(1,2,...,313)を考え、各素因数の冪の形で表します。Pohlig-Hellman法のような形で DLP を解きますが、order の倍数が出てきてしまいました。
そこで、各 mod での解のうち 1 は怪しいので除外！のような形で CRT し直したところフラグゲットできました（極めてイイカゲンですけど競技なのでヨシ！）。
問題の本質は違いますが、個人的には「Larisaのツラい版」という印象でした。
☆ソルバ（御多分に漏れず汚いです）
solve.sage
#!/usr/bin/env sage
from Crypto.Util.number import *
import copy
G = <313×313の配列、省略>
H = <313×313の配列、省略>
def genperm(n):
_ = list(range(1, n + 1))
shuffle(_)
return _
def genlatrow(n):
A = []
for _ in range(n): A.append(genperm(n))
return A
def prodlat(A, B):
assert len(A) == len(B)
C, G = [], SymmetricGroup(len(A))
for _ in range(len(A)):
g = (G(A[_]) * G(B[_])).tuple()
C.append(list(g))
return C
def powlat(A, n):
assert n >= 0
B = bin(n)[2:]
c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
if n == 0: return R
else:
for b in B:
if b == '1':
if c == 1: R = prodlat(R, A)
else:
T = A
for _ in range(c - 1): T = prodlat(T, T)
R = prodlat(R, T)
c -= 1
return R
L = 313
od = 1
primes = []
for i in range(2, L+1):
if isPrime(i):
j = 1
while(True):
if i**(j+1) > L:
break
j+=1
primes.append(i**j)
od *= (i**j)
print(primes)
def powl2(A, facs, p):
AA = copy.copy(A)
for f in facs:
if f != p:
AA = powlat(AA, f)
return AA
def dlog(B, X, p):
BB = copy.copy(B)
for i in range(1, p+1):
if BB == X:
return i
BB = prodlat(BB, B)
return None
ms = []
ds = []
for i in range(len(primes)):
p = primes[i]
GG = powl2(G, primes, p)
assert powlat(GG, p+1) == GG
HH = powl2(H, primes, p)
assert powlat(HH, p+1) == HH
d = dlog(GG, HH, p)
print(f"p:{p}")
print(f"d:{d}")
ms.append(p)
ds.append(d)
print(ms)
print(ds)
_ms = []
_ds = []
for i in range(len(ms)):
if ds[i] != 1:
_ms.append(ms[i])
_ds.append(ds[i])
d = crt(_ds, _ms)
print(d)
print(long_to_bytes(d))
☆フラグ
CCTF{3lGam4L_eNcR!p710n_4nD_L4T!n_5QuarS3!}
2-18. Larisa (難易度：medium-hard, 174 points, 22 solves)
☆設問
以下のスクリプト等が提示されます。
「Lagima」と同じく対称群が出てきますが若干毛色が違う問題です。
larisa.sage
#!/usr/bin/env sage
from flag import flag
def genperm(n):
_ = list(range(1, n + 1))
shuffle(_)
return _
def genlatrow(n):
A = []
for _ in range(n): A.append(genperm(n))
return A
def prodlat(A, B):
assert len(A) == len(B)
C, G = [], SymmetricGroup(len(A))
for _ in range(len(A)):
g = (G(A[_]) * G(B[_])).tuple()
C.append(list(g))
return C
def powlat(A, n):
assert n >= 0
B = bin(n)[2:]
c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
if n == 0: return R
else:
for b in B:
if b == '1':
if c == 1: R = prodlat(R, A)
else:
T = A
for _ in range(c - 1): T = prodlat(T, T)
R = prodlat(R, T)
c -= 1
return R
def pad(msg, n):
assert len(msg) <= n
return msg + msg[-1] * (n - len(msg))
def embed(msg, n):
assert len(msg) < n
msg = pad(msg, n)
while True:
r, s = [randint(2, n) for _ in '__']
if gcd(r, len(msg)) == 1:
break
A = []
for _ in range(n):
while True:
R = genperm(n)
if R[(_ * r + s) % n] == ord(msg[_]):
A.append(R)
break
return A
def encrypt(A, e = 65537):
return powlat(A, e)
l, e = 128, 65537
M = embed(flag, l)
C = encrypt(M, e)
print(C)
enc.txt
<127×127の配列、省略>
☆方針・解法
powlat(A, x) == powlat(A, 0) となる x (>0) を考えたとき、e*d = 1 mod x となる e, d について、
powlat(powlat(A, e),d) == A となることに注意します。
このことを用いて C を「decrypt」し、embed の逆操作をすればフラグをゲットできます。
☆ソルバ
solve.sage
from Crypto.Util.number import *
C = <127×127の配列、省略>
def prodlat(A, B):
assert len(A) == len(B)
C, G = [], SymmetricGroup(len(A))
for _ in range(len(A)):
g = (G(A[_]) * G(B[_])).tuple()
C.append(list(g))
return C
def powlat(A, n):
assert n >= 0
B = bin(n)[2:]
c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
if n == 0: return R
else:
for b in B:
if b == '1':
if c == 1: R = prodlat(R, A)
else:
T = A
for _ in range(c - 1): T = prodlat(T, T)
R = prodlat(R, T)
c -= 1
return R
def readflag(A, n):
for r in range(2, n):
for s in range(2, n):
flag = b""
for i in range(n):
flag += (A[i][(i * r + s) % n]).to_bytes(1 , "big")
if b"CCTF" in flag:
return flag
return None
def encrypt(A, e = 65537):
return powlat(A, e)
l, e = 128, 65537
od = 1
for i in range(2, l+1):
if isPrime(i):
j = 1
while(True):
if i**(j+1) > l:
break
j+=1
od *= (i ** j)
d = inverse(e, od)
P = encrypt(C, d)
assert encrypt(P,e) == C
print(readflag(P, l))
☆フラグ
CCTF{pUbliC_k3y_crypt0graphY_u5in9_rOw-l4t!N_5quAr3S!}
3. おわりに
途中細かい休憩や食事は挟みましたが、ほぼ 24 時間稼働していたので疲れました。
この週末の気力体力を全振りしてしまったため、謎解き CTF はそもそも登録しそびれ、Imaginary CTF はほぼ手つかずとなってしまいました。
来年も元気ならばソロ参加してさらに上（順位的にというよりは、solveの数と質の向上）を目指したいと思います。
ジーク、ジオン！