zer0pts CTF 2021 Writeup (2021/03/07)

#1. はじめに
　2021/3/6 9:00 JST ～ 2021/3/7 21:00 JST に開催された「zer0pts CTF 2021」にチーム「N30Z30N」としてソロ参加しました。Welcome と Survey 以外に Crypto を 2 問だけ解いて 90 位（辛うじて二桁）でした。以下、Writeup です。

※2021/07/22 はてなブログから移転

#2. Writeup
##2-1. war(sa)mup (Crypto, 102pt)

Do you know RSA? I know.

ファイル：「task.py」

task.py

from Crypto.Util.number import getStrongPrime, GCD
from random import randint
from flag import flag
import os

def pad(m: int, n: int):
  # PKCS#1 v1.5 maybe
  ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
  ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
  assert len(ms) <= len(ns) - 11

  ps = b""
  while len(ps) < len(ns) - len(ms) - 3:
    p = os.urandom(1)
    if p != b"\x00":
      ps += p
  return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")


while True:
  p = getStrongPrime(512)
  q = getStrongPrime(512)
  n = p * q
  phi = (p-1)*(q-1)
  e = 1337
  if GCD(phi, e) == 1:
    break

m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)

print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)

ファイル：「output.txt」

output.txt

n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

　最近の CTF にしては比較的解きやすい問題でした。SECCONもそうですが、和製 CTF は「提示されるコードは非常にシンプルだけど、解くのは決して容易ではない」みたいなのが多く、解けなかったとしても清々しい気持ちになります。（実際、長いソースコードはまだ許せるにしても、巨大ファイルをダウンロードさせられるのは結構辛いのです…）

　閑話休題。本問は「RSA」による暗号の問題で、c_1 = m^e mod n …①と c_2 = (m//2)^e mod n …② という RSA による暗号文が 2 つ与えられます。

　pad したあとの平文の作り方から、hex(m) の末尾は ord("}") =0x7d なので、m は 奇数です。

　よって c_2 * 2^e = (m-1)^e mod n …③が成立します。

　m は ①と③を同時に満たすので、 x の多項式

　　f_1 := x^e - c1 mod n

　　f_2 := (x-1)^e - c2 * 2^e mod n

の（mod n での x の多項式としての） GCD を計算し、得られた一次式から m が得られます。

　以下、完成した solver（sagemath使用）です。

「solve.sage」

solve.sage

from Crypto.Util.number import *

n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

def poly_gcd(f,g):
  if g.degree() == 1:
    return g
  else:
    return poly_gcd(g, f % g)

R.<x> = PolynomialRing(Zmod(n))

f1 = x^e - c1
f2 = (x-1)^e - c2 * 2^e

f = poly_gcd(f2,f1).monic()
m = -f.coefficients()[0] % n

print(long_to_bytes(m).split(b"\x00")[-1].decode())

zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}

　ちなみに、ここ 1 年間に似たような（多項式のGCD使って解く）問題を何題か見たことがありますので、そろそろ「多項式GCDでサクッとできそうに見えて、出来ない」問題が、どこかで出て来そうな気がします。

##2-2. NOT Mordell primes (Crypto, 209pt)

I found one integral point on an elliptic curve, so there's finite number of integral solutions.
This means You can pick from an finite number of primes... right?
special thanks: https://ctf.cr0wn.uk/challenges#Mordell%20primes-11

ファイル「task.sage」

task.sage

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG


p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177

E = EllipticCurve(GF(p),[a,b])

P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
Q = k*P
R = (k+1)*P

p = int(Q[0])
q = int(R[0])

assert is_prime(p)
assert is_prime(q)


e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

ファイル「output.txt」

output.txt

N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987

　Union CTF 2021に出題された「Mordell primes」のオマージュ問題です（と思われます）。

　ただし、タイトルにあるように、同じ（簡単な）解法ではうまくいきません。

　しかし、p を特定さえすればあとは RSA 復号の単純作業だけですので、全力で p をゲットしに行きます。

Phase1: p の特定

　「Mordell primes」では、提示された曲線の Generator をスカラー倍していくとすぐに p が見つかりました。しかし今回はそうはいきません。

　そこで、具体的なスカラーを求めず、

　　R = P + Q

　　p = Q[0]

　　q = R[0]

　　N = pq

という関係式から強引に p を求めることにしました。

STEP1:

STEP1

# p という記号がカブるのでMに変更
M = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387

R.<x,y> = PolynomialRing(GF(M))

# Pのx座標、y座標
x0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991

# Qの座標を(x,y)とおき、楕円曲線の「和」の定義と前記関係式をもとに、以下の f0 を定義する。
# 最終的に、f0 = 0 となる x を見つければよい。
f0 = x*(y-y0)^2 - (x-x0)^2 * (x^2 + x*x0 + N)

　この段階で、

f0 = -x^4 + 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980*x^3 + x*y^2 + 7616677647790201248023988497219633204584422778773890748589023194821078925729962104300972506959099715802194538160749223020533457299488113273930581180238343*x^2 + 596052693888453112936470884532854144315942457752484084697520879068010676549146635369320810006014818416047159135301937994024786558883838310414976908404164*x*y + 10198198459287589877321169997882125783248959634577726377449327028901760605306023709248565202074496754536543203136574857894003894978527760156270025497968883*x + 9365563752815012232239821023982604075654474379330181578118533588730193249444182925300237986995837348314590718101706905694147753093791339035714804255024360

を得ます。

STEP2:

# Eの定義式をもとに、 y^2 を消去します。そのため、以下のように f1 を定義し、f0 の「y^2」を「f1」に置き換えたものを f2 とします。
f1 = x^3 + a*x + b

#f2:  f0 の y^2 を f1 に置き換え
f2 = -x^4 + 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980*x^3 + x*f1 + 7616677647790201248023988497219633204584422778773890748589023194821078925729962104300972506959099715802194538160749223020533457299488113273930581180238343*x^2 + 596052693888453112936470884532854144315942457752484084697520879068010676549146635369320810006014818416047159135301937994024786558883838310414976908404164*x*y + 10198198459287589877321169997882125783248959634577726377449327028901760605306023709248565202074496754536543203136574857894003894978527760156270025497968883*x + 9365563752815012232239821023982604075654474379330181578118533588730193249444182925300237986995837348314590718101706905694147753093791339035714804255024360

　この段階で、

#f2 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980*x^3 + 4613408214920465945819548575797201166548578045502858590984779681097635416461039852646249623442057980376420841341777275586026207238281542191284794265978511*x^2 + 596052693888453112936470884532854144315942457752484084697520879068010676549146635369320810006014818416047159135301937994024786558883838310414976908404164*x*y + 10115764627807940940135882638940254999098785487279147996523897409112442150605131827229523476733357071387677537605661146557558847755832593488173043037431987*x + 9365563752815012232239821023982604075654474379330181578118533588730193249444182925300237986995837348314590718101706905694147753093791339035714804255024360

を得ます。

　あとは y が邪魔なのですが、y^2に置き換えるため小細工を行います。

STEP3:

STEP3

#h1+h2 =f2となるよう以下のようにh1, h2を定義します。
h1 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980*x^3 + 4613408214920465945819548575797201166548578045502858590984779681097635416461039852646249623442057980376420841341777275586026207238281542191284794265978511*x^2 +10115764627807940940135882638940254999098785487279147996523897409112442150605131827229523476733357071387677537605661146557558847755832593488173043037431987*x + 9365563752815012232239821023982604075654474379330181578118533588730193249444182925300237986995837348314590718101706905694147753093791339035714804255024360
h2 =596052693888453112936470884532854144315942457752484084697520879068010676549146635369320810006014818416047159135301937994024786558883838310414976908404164*x*y
assert h1+h2 == f2

#f3 = h1^2 - h2^2と置きます。f3 = 0を満たす x のうち幾つかは f2 = h1+h2=0 すなわち f0=0を満たします。
f3 = h1^2 - h2^2

　この段階で

f3 = 591112058290026548191761730016261447411672257020784975352166947061372333456962089153803364253438588614153428258165215481855069306957839139982635094798555*x^6 + 241948804746934570554473281812725620105978518513567572675735788395443927345412514197058704626861736176948185387517989417357790372147720624291808278595931*x^5 + 8201103076011115656523781451736250636192255240368209333231610177970647227206561559294531900383493615637662518798947589797146529473656877808450782258695423*x^4 + 1877399714162667141605432462672526664587803369638150012132003482442888239792089773211680860131560463732302068064679992182526822446166283265476029872012602*x^2*y^2 + 1123581601427812751271718925323169177584582482864733257622129186080817811973279756920957494414953110052386021342081611136428468774020270943740094978163051*x^3 + 4244999772818405476589822938829930468569342653757984298095368061683011755471959786098915655949375771447086722565499890202075522914834947849590378824255817*x^2 + 2822467528003473617129730568585736642379750485030840574002603988890751258126279160039137099225510028709452886500480109911010892730980414576641336008540328*x + 2808230573168723527148439598622733490814273833311205355970071078196770122975568849235550033769244443994730268044633364086453009826847892135398313097896730

を得ます。f3 の y^2 を f1 で置き換えれば、x だけの式になりますので、因数分解してみます。

STEP4:

STEP4

# f3 の y^2 を f1 で置き換え
f4 = 591112058290026548191761730016261447411672257020784975352166947061372333456962089153803364253438588614153428258165215481855069306957839139982635094798555*x^6 + 241948804746934570554473281812725620105978518513567572675735788395443927345412514197058704626861736176948185387517989417357790372147720624291808278595931*x^5 + 8201103076011115656523781451736250636192255240368209333231610177970647227206561559294531900383493615637662518798947589797146529473656877808450782258695423*x^4 + 1877399714162667141605432462672526664587803369638150012132003482442888239792089773211680860131560463732302068064679992182526822446166283265476029872012602*x^2*f1 + 1123581601427812751271718925323169177584582482864733257622129186080817811973279756920957494414953110052386021342081611136428468774020270943740094978163051*x^3 + 4244999772818405476589822938829930468569342653757984298095368061683011755471959786098915655949375771447086722565499890202075522914834947849590378824255817*x^2 + 2822467528003473617129730568585736642379750485030840574002603988890751258126279160039137099225510028709452886500480109911010892730980414576641336008540328*x + 2808230573168723527148439598622733490814273833311205355970071078196770122975568849235550033769244443994730268044633364086453009826847892135398313097896730

#f4=0 を満たす x が p の候補
print(f4.factor())

　f4 は以下のように因数分解されます。

(591112058290026548191761730016261447411672257020784975352166947061372333456962089153803364253438588614153428258165215481855069306957839139982635094798555) * (x + 7780241193869293703777908276353366054840137077075863660446738842245217567140031758057414863753320876326088434774266474889650910653892295273006953788081622) * (x + 8754360849384784981196558288271096260326352367873944796592649085188836255973684962733961804751052153828451374248776668717277120962203155755263580158538336) * (x + 1763282894498093488335953418281655272275522879423943691312771766626221157294832805869600883835305784318187396642888426756906943957420064166607272774539093)^2 * (x^2 + 11277700471782461668506583297501462698510975339742186390766922981937776526296919605178544953294255573381096637114728547024495037480778364463876874597608228*x + 6021323508021471669255242840985180449995013718594089698765302573049701975337092309445674218722776636140588893776218371696009947672377478724321030307539285)

　したがって、

　-7780241193869293703777908276353366054840137077075863660446738842245217567140031758057414863753320876326088434774266474889650910653892295273006953788081622%M = 5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451

　-8754360849384784981196558288271096260326352367873944796592649085188836255973684962733961804751052153828451374248776668717277120962203155755263580158538336%M = 4292528248136861387890911319917455946841411872473250675409509735620572311636407361858881556677385609500178629430025710517411214702704597103005396234440737
　
-1763282894498093488335953418281655272275522879423943691312771766626221157294832805869600883835305784318187396642888426756906943957420064166607272774539093%M =
11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980

が p の候補となります。

　実際、最初の5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451がNを割るので、これを p （q かもしれないが後に影響しないよう計算するのでどちらでもよい）としました。

Phase2: RSA

　p と公開鍵が特定できているので、あとはこれらを使って普通に復号すれば OK です。

「solve2.py」

solve2.py

from Crypto.Util.number import *

N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987
e = 0x10001

p = 5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451

q = N // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,N)
print(long_to_bytes(m).decode())

zer0pts{7h4nk_y0u_j4ck_7h4nk_y0u_cr0wn}

　こういうオマージュ問も素敵ですね。

　綺麗なソルバーになっていませんが、気合と根性で解いた雰囲気を出したかったのであえて実際に解いたときの経過を示しました。

#3. こぼれ話
　上の2問以外、「pure_division」にも挑戦しました。

　以下のソルバーを作りましたが計算が終わらずでした。

　
「そもそも方針がダメ！？」

from Crypto.Util.number import *

p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a1 = 22457563127094032648529052905270083323161530718333104214029365341184039143821
a2 = 82792468191695528560800352263039950790995753333968972067250646020461455719312
#a2 = 7898420268915076480319731074892336110136293952081268416747934850935857299571
Fp = GF(p)

E = EllipticCurve(Fp, [a1, a2])

S = E(201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226, 
      217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835)
#S = (15467263825294344995050490629371217183697718348561273227327096309278021685682, 38640138927564938269923601955629222274494938997200910666516510278608606227876)
T = E(49376632602749543055345783411902198690599351794957124343389298933965298693663616388441379424236401744560279599744281594405742089477317921152802669021421009909184865835968088427615238677007575776072993333868804852765473010336459028, 
      342987792080103175522504176026047089398654876852013925736156942540831035248585067987750805770826115548602899760190394686399806864247192767745458016875262322097116857255158318478943025083293316585095725393024663165264177646858125759)
#T = (39656641567220522350979748368847031338643342456389563479096178299087871562416, 36217515237101119970302808034046124477780724981776232571720679324353075855684)


#E.order() = 74894047922780452080480621188147614680853399736985793708596679454987247185378
#S.order() = 37447023961390226040240310594073807340426699868492896854298339727493623592689
eo = 74894047922780452080480621188147614680853399736985793708596679454987247185378
so = eo // 2

#factors, exponents = zip(*factor(eo))
factors = [13,479,607,190805329565199750497751113,3994072080462502523724792625408506304758529]
exponents = [2,1,1,1,1]
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []
modulos= []

for i in range(len(primes)):
    fac = primes[i]
    t = int(so) // int(fac)
    if(isPrime(fac)):
      dlog = discrete_log_rho(t*T,t*S,orf=fac,operation="+")
    else:
      dlog = discrete_log(t*T,t*S,ord=fac,operation="+")
    if dlog != 0:
      dlogs += [dlog]
      modulos += [fac]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog))

m0 = crt(dlogs, modulos)
print(m0)

#base = bytes_to_long(b"zer0pts{zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz}") // eo * eo = bytes_to_long(b"zer0pts{0000000000000000000000000000000}") // eo * eo
#base = 13635765968586345688 * eo = 1021237709915124582471060126528923410426789759906294923847073065008413084573931082098040526950064
base = 13635765968586345688 * eo
m = base + m0
print(long_to_bytes(m))

う～ん、残念。