最近まだ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} $$

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

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

次のようなスクリプトで$N$を素因数分解した(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,
]

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

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

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

考えられるのはflagがxより大きい事である。この場合、楕円曲線の位数を$\#E_p$とおくと$x' \equiv x \bmod \#E_p$となる$x'$も$x'G = h$を満たす。

というわけでそのような$x'$は$x' = k \times \#E_p + x$とおけるので$k$を総当りすればいつかフラグが出て...来ない。

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

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

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

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!!}であった。