最近まだCryptoに触れていない時期や、触れたばかりで問題の意味も把握出来ていない時期のCTFのCryptoを復習していてTSGCTF 2019から2問解いたのでそのWriteupを書きます。

問題は次のリポジトリで公開されています。

https://github.com/tsg-ut/tsgctf

扱う問題は次の2つです

  • OPQRX
  • Curved

Prerequisite §

下記事項は知っているものとしてWriteupを書きます。

  • 楕円曲線とその上の群における離散対数問題(Curved)

OPQRX §

次のような暗号化スクリプトとその実行結果をくれる

require 'securerandom'

def miller_rabin(n)
  raise ArgumentError unless n >= 2
  return true if n == 2
  return false if n == 1 or n.even?
  return n != 9 if n < 15

  d, r = n-1, 0
  while d.even?
    d >>= 1
    r += 1
  end

  30.times do
    a = rand(2..(n-2))
    x = a.pow(d, n)

    ok = false
    next if x == 1 or x == n-1
    (r-1).times do
      x = (x*x) % n
      if x == n-1
        ok = true
        break
      end
    end

    return false unless ok
  end

  true
end

def getprime(bits)
  loop do
    p = SecureRandom.random_number(1<<bits)
    return p if miller_rabin(p)
  end
end

bits = 4096
P, Q = 2.times.map{getprime(bits)}

F = IO.binread('flag.txt').unpack("H*")[0].hex
X = P^Q
N = P*Q

raise ArgumentError unless F < N

E = 65537
C = F.pow(E, N)

IO.binwrite('flag.enc', [
  'X = %p' % X,
  'N = %p' % N,
  'E = %p' % E,
  'C = %p' % C,
].join("\n"))

4096bitの素数の積で公開鍵を作ったRSA暗号でフラグを暗号化している。Eに関しても65537である事から特に問題は無さそうなので一見解けないように見えるが、X = P^Qで定義された値もくれるのでこれを頼りにP,Qを求めることが目標である。

ここで

$$ \begin{aligned} P &= \sum_i {b_p}_i 2^i \cr Q &= \sum_j {b_q}_i 2^j \cr P\times Q &= \sum_i \sum_j {b_p}_i{b_q}_j 2^{i+j} \end{aligned} $$

この式よりbitはの自身より小さい添字の桁全てに依存することがわかる。これはある2つの数の積の下位bitは2つの数の下位bitに依存する、という事で有るから下のbitからの候補を絞ることが出来る。

問題はこのやり方だと該当する組み合わせが非常に大きく到底計算できる量では無くなってしまう。そこで利用するのがXでこれによってP,Qに新たに制約が追加される事から候補を更に絞ることが出来る。

次のようなスクリプトでを素因数分解した(10分ぐらいかかった)。

# challenge info
X = 950358059600474305827771380683741458994102949126303386140253951747972276999022342208262800760061154398271068516253175545735456284984933121377404958083314600655447129775868209462982744186518957772122396756451141101530041779955245471472134699242664534814221273939880846730251297763359790557422127540709102136769366092399273623925570872859266548882987518588530617720397165019176108480156876913848103894864771903530413550704276937306948683609983799509662220045635940160920596367820951543381669617525581893239594901173734116054697069635020002486845048804682305078106964316183798068618639241948197675223115348163019048625373765550949273567042933864894263655621306241833349642978696892492213984491118558186425036609374626368657763236619642299850791946710919682040219563850092641243093906165685956695639258845635807997678135071126411514233212329352759106255311517050069284549350052584108601349762457513286109309685191933647198018596263095604001928907171502875081594253618031333487818528683297444472724705834348968685867101260408703944578321377003322277616161558951427955865100991857694166101106561131471922637073992792768831828380493392423497335535612525566590750772745411732685028183267169226764749141325626854817138130631949844771053951960
N = 247465623232529638570403627954515140549125464704817835183645669188472743182462350040656945325450657857795456553396687569720980842982926845337227966696522093282786882561968615864736765752433069546858439815030651380785843674190791402853951236494718634304312751098515936783858994195570922580683332803369701363402529074402664491617600861267722232614873579834618864491313983011984783179171484956546212881647063328679330401752122426273399745247394558879616944190407436620707694460705838905167958310291748206503803245570812818460951229153004100082641961722909449085000926517536505862666390730672438786667437732727892530932043888271965398718458040093563806864200347078192024936196446329155635755682462402577559908583721738674671712235928511130814290140488609275201531091941022025423945245655138749471773951982326940397563668812663911560805472790354465176645654925712665466908761601630548710031513794557078929877256958912825742035898444107900195605803439822642914124421169419665012462368428063174117176948217351889525290996526478175910563577827404884951074164990948585830040593958196959384856700062914243351708318383463054253935630461024868395311859856823997566468043613201152144317218540388233163044090076375023156913766157903266102228806511766874546238501462729789311305353532852243350014435557292562277534441782977536950667942409622824703681942287094306687529563976259226568536477006987758537902779031652725318651412097989762378829049950725567335828279044984627929916893167368380666080846093308718960187199678171390844781410123277536707822610961039098290794321102160488402500912631820436740755297381500867354726950237473157706745732481020409089136649142836959359494679712387674635517522465929790194532886549752549296525326753661396418942921238641862841862062523739794185828404110732054050991100263967931482921549160288056234483320030511150838991553475977254477982555698760709836081377694957203251796012604022819780158470545306037123726144297059699951351522178070972246076273281750790146118258080309984762387853921776334456422671205443649323821265510825075358823620914441131837218471866299818058325805391640744310939129416240071558620256757906619101813132910694274256665801559376989999327799895968742876386311015510228756261286000612508092571831683964733063518480933968224775829439608716169155578215817882852862506665551979130227190512028135937769869149065155592833328152008778223352658264026115418397316311825039015464475393415911842445128662864755158473389001859110809489
E = 65537
C = 38292826706641216197843504024442473810304021733514451674093213928285248206581440804382750412040887271040802347875317791241766024921473228404695871017478971358043108872759997071604134571145632444890962123400867988299720826951697743018301463745437874886471856189203658771918213330370568116597671937234517684350844457560748316765528685035787121369688963100742605146223188219823044747059438808663118931444860689199058383273989761139776185693880705114030744137694916118577357618886718996561416159751609291056288383072188225742693264976539230860895884979155649321473725137314438905587563576686790028504585718870222050725422615608593162022543355433501610656100656390969549536782697723232083896243322848431946061430870092255185038860802722297859103382933439318448178426630322096447063497659583523406322273845339351942166550925881712869778934735961149831772419648770236423703778723709444074774848123177937341096799046441632009391879828882947968574005475222868208181869257328113346954778678246921806895756722458089660774852257216218215808974146798709289339389262445340618875434418284218058428043448686605333666457077432829562549724024902120335397651378232322610446055675419301412421106727875968903348833369153306108013434674775382056357049594636017276583463994846272581542940834432469709833096499918026534841080645909295142106259175030365691510336715363687103695664308943450214512604477679897247821600646499130163417531360091862226215014951623512776412924518253491354722974882416598688799566899430112327839786083498652816075049879123875037397210282458262075630647426596559506653960639198563847404854433138206824762240117486424443541276062622450481252963886447743305106741755625393982965955449252982502400943583974279541514867833295668849211670439562950515041383905926077150598226197512830572160465815250946291000472385227962209742945274795499069129229632516658868321068874484377798039972658708538006538591069685862343473277090657067119342545903879280904833995538022922695355992924800030338000982764572271044035105159200522915596166488049773949980105458112099226431959533158261775419858136750649339995749317237166469933837147003693606374953899602388950411523146406309727420544388352005658922216757121426412510588922115785795472332119978070111697951388862117411170313506043948916399276331265222331256207884612355562474861844964026947655141931410062960340978440773611758524297473204811668212292023445223770150008515042103444551443481759899935450672833801013486294074702610305157


# 下位nbitを抽出する
def extract_bits(n, b):
    return n & ((1<<b) - 1)


if __name__ == "__main__":
    bit = 0
    candidates = [(0, 0)]

    while True:
        _candidate = []
        for p,q in candidates:
            if p*q == N:
                print(p, q)
                exit()
            for i in range(2):
                _p = p + (i << bit)
                for j in range(2):
                    _q = q + (j << bit)
                    if extract_bits(_p*_q, bit+1) == extract_bits(N, bit+1) and extract_bits(_p^_q, bit+1) == extract_bits(X, bit+1):
                        # print(hex(_p), hex(_q), hex(_p*_q), hex(_p^_q))
                        _candidate.append((_p, _q))

            candidates = _candidate
        
        print(bit, len(candidates))

        bit += 1

フラグはTSGCTF{Absolutely, X should be 'S' in 'OPQRX'.}であった。

Curved §

次のような暗号化スクリプトをくれる

require 'test/unit/assertions'
include Test::Unit::Assertions

# P = 2 ** 256 - 2 ** 32 - 977
P = 2 ** 256 - 2 ** 32 - 313441 # We all like hacks, ain't we?
O = [Float::INFINITY, Float::INFINITY]

def inv(n)
  n.pow(P - 2, P)
end

def sqrt(n)
  z = 1
  z += 1 while z.pow((P - 1) / 2, P) != P - 1
  q = P - 1
  m = 0
  while q % 2 == 0
    q /= 2
    m += 1
  end
  c = z.pow(q, P)
  t = n.pow(q, P)
  r = n.pow((q + 1) / 2, P)
  m.downto(2) do |i|
    tmp = t.pow(2 ** (i - 2), P)
    if tmp != 1
      r = r * c % P
      t = t * c ** 2 % P
    end
    c = c ** 2 % P
  end
  r
end

def add(a, b)
  return a if b == O
  return b if a == O
  if a[0] == b[0] && a[1] == b[1]
    l = (3 * a[0] ** 2) * inv(2 * a[1])
    x = l ** 2 - 2 * a[0]
  else
    return O if b[0] == a[0]
    l = (b[1] - a[1]) * inv(b[0] - a[0])
    x = l ** 2 - a[0] - b[0]
  end
  [x % P, (l * (a[0] - x) - a[1]) % P]
end

def mul(a, n)
  k = O
  while n != 0
    if n % 2 == 1
      k = add(k, a)
    end
    a = add(a, a)
    n /= 2
  end
  k
end

Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = sqrt(Gx ** 3 + 7)
G = [Gx, Gy]
print(G)

flag = File.read('flag')
h = mul(G, flag.unpack("H*")[0].hex)
assert h == [
  0x56df2adff3c3749cc4c62c9e7da339dc02d157868a1d76f9d058d634d6a9525f,
  0xc167d7eb600437e2d6ead69ebcf2b1b2f88939c0fafda0b19aa3db33f5024b43,
]

有限体上の楕円曲線で演算を定義し、ベースポイントGflag倍しており、その結果であるhが判明している。これだけ見ると至って普通のECDLPである。

この楕円曲線の位数をSageで求めて、factorDBに突っ込むなりSageのfactor()を使うなりするとこの位数は比較的小さい素因数に分解することが出来る。したがってPohlig-Hellmanアルゴリズムが効きそうである。

自前の実装で20分ほどでとなるを求めることが出来たのでこれを文字列に直すとフラグが出て...来ない。これで出てくるなら5 Solvesのはずがないので当然といえば当然である。

考えられるのはflagxより大きい事である。この場合、楕円曲線の位数をとおくととなるを満たす。

というわけでそのようなとおけるのでを総当りすればいつかフラグが出て...来ない。

かなりここで苦しんだが、このWriteupを読んだりしてが原始根で無い可能性が考えられたのでSageMathでG.order()で調べてみたら位数より小さい値が出た。というわけで先程導出したを「の位数」で割った余りがフラグになら...ない。

ここで先程のアプローチを適用しての位数の倍をに足していったらようやくフラグが出た。

自作ライブラリ塗れの使用コードはこちら↓

from xcrypto.ec import EllipticCurve, ECPoint, ec_pohlig_hellman
from xcrypto.prime import factorize_by_factordb
from Crypto.Util.number import long_to_bytes


if __name__ == "__main__":
    p = 2 ** 256 - 2 ** 32 - 313441
    curve = EllipticCurve(0, 7, p)
    G = ECPoint(55066263022277343669578718895168534326250603453777594175500187360389116729240, 82420052799988522717532479648954225145345455265426509542622303173620650331589, curve)
    Q = ECPoint(0x56df2adff3c3749cc4c62c9e7da339dc02d157868a1d76f9d058d634d6a9525f,0xc167d7eb600437e2d6ead69ebcf2b1b2f88939c0fafda0b19aa3db33f5024b43, curve)
    order = p + 1
    g_order = order // 50
    print(g_order)
    factorized_list = factorize_by_factordb(g_order)
    print(factorized_list)
    res = ec_pohlig_hellman(G, Q, factorized_list, log=True)

    # res = 86774096906226060329804261331052874200381065355514102745131142258763659734029
    # res = res % g_order
    print(res)
    print(long_to_bytes(res))
    print(res.bit_length())

    assert res*G == Q

    k = 0
    while True:
        flag = res + k*g_order
        if b"TSGCTF{" in long_to_bytes(flag):
            print(k)
            break

        k += 1

    print(long_to_bytes(flag))

フラグはTSGCTF{BewareOfTheSh@rpCurves!!}であった。

感想 §

2019年の1桁Solvesの問題でも、他人のWriteupを読んで何やってるかわかるぐらいにはなったので良かったです。

CurvedはただのPohlig-Hellmanだと思ったら2重に罠が張ってあって苦戦しました。TSGCTF 2020 - Modulus Amittendusのように簡単な要素から難しい問題を作ってしまうところがTSGらしい問題だと思いました。

ここまで読んでいただきありがとうございました。次は気が向いて面白い問題があったら最近取り組んでいるCrypto CTF 2020の問題から幾つかWriteupを書くかもしれません。