BSides Ahmedabad CTF 2021 Writeup

1. はじめに

　2021/11/6(土) 12:00 JST ～ 2021/11/7(日) 12:00:00 JST で「BSides Ahmedabad CTF 2021」に参加し、Crypto 問題を 2 問だけ解きました（395点、54位/314チーム）。
　この CTF は zer0pts 作問ですので、競技中解けなかった問題もきっちり補完する予定です。

2. Writeup

2-1. dlppp (warmup, 151 points, 39 solves)

設問

Can you solve DLP?

task.py

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

flag = os.getenv("FLAG", "XXXX{sample_flag}").encode()
m = int.from_bytes(flag, 'big')

p = getPrime(512)
y = pow(1 + p, m, p**3)

assert m < p
print(f"p = {hex(p)}")
print(f"y = {hex(y)}")

output.txt

p = 0xa1c8e1e9b2301cb1f5d424ec6d959d7f275e11507b2177d55f3dc1268c9a3164b72832f362975023f09623814f80fe0ffad179d0e51c40b8a1f882d1f5f28e71
y = 0x6fa0fcc8c9c5f695a5709243698d7640c27c45352375919d538137333ab3a2c748cae5e7c1294d6ffc4007476f6fec6421c992f9fe1919b381306300caa2260953e48f2ec0de7b8c6417faa42001a748b1b367f5211095ddd6bf4e681f7e7ad787e0a7f562f6f0307d6a8d7e8d18cd59bd7572f0c4f430f0fd4fc61503b203f3bcd6dd0b0f84bbdbd42126d95b525fe77e4be62c6dbd083dbcaa284b20a9ea6faf9cbaf20dd88b0180417c9021fa1dcb52b2348c4376bd6b9b38a6c860086af

方針・解法

　法が p^3 なので、局所体 Z_p で log(y)/log(p+1) を計算したものを lift すれば算出可能です。
　想定解は (p+1)^m を二項展開して・・・というやつだったっぽいです（フラグからそう受け取れます）が、手元に Z_p でやるのソルバがあったのでそちらを使って解きました。（ちなみに、SageMath を予め起動していたこともあって 1st blood をいただきました。）

ソルバ

solve.sage

from Crypto.Util.number import *
p = 0xa1c8e1e9b2301cb1f5d424ec6d959d7f275e11507b2177d55f3dc1268c9a3164b72832f362975023f09623814f80fe0ffad179d0e51c40b8a1f882d1f5f28e71
y = 0x6fa0fcc8c9c5f695a5709243698d7640c27c45352375919d538137333ab3a2c748cae5e7c1294d6ffc4007476f6fec6421c992f9fe1919b381306300caa2260953e48f2ec0de7b8c6417faa42001a748b1b367f5211095ddd6bf4e681f7e7ad787e0a7f562f6f0307d6a8d7e8d18cd59bd7572f0c4f430f0fd4fc61503b203f3bcd6dd0b0f84bbdbd42126d95b525fe77e4be62c6dbd083dbcaa284b20a9ea6faf9cbaf20dd88b0180417c9021fa1dcb52b2348c4376bd6b9b38a6c860086af

g = p + 1
F = Zp(p, prec=3)

x_Z = F(y).log() / F(g).log()
x = x_Z.lift()

print(long_to_bytes(x).decode())

フラグ

Neko{b1n0m1al_th3or3m0o00oo000ooo00000ooooo00000000n}

　提示されるスクリプトがシンプルで、スッキリした問題でした。

2-2. floorsa (178 points, 27 solves)

設問

.chall.py

import os
import hashlib
from Crypto.Util.number import getPrime, getRandomNBitInteger
from itertools import product

def floor_sum(n: int, m: int, a: int) -> int:
  """Fast calculation for sum([a * i // m for i in range(n)])
  """
  res, b = 0, 0
  while 0 < n:
    res += n * (n - 1) // 2 * (a // m)
    a %= m
    res += n * (b // m)
    b %= m
    last = a * n + b
    n, m, a, b = last // m, a, m, last % m
  return res

# def floor_sum_tests():
#  for n, m, a in product(range(50), range(1, 50), range(50)):
#    result = floor_sum(n, m, a) 
#    expect = sum([a * i // m for i in range(n)])
#    assert(result == expect)

if __name__ == '__main__':
  #floor_sum_tests()

  flag = os.getenv('FLAG', 'XXXX{sample_flag}').encode()
  flag += hashlib.sha512(flag).digest()
  m = int.from_bytes(flag, 'big')
  assert m.bit_length() < 2048

  p = getPrime(1024)
  q = getPrime(1024)
  n = p * q
  e = 65537
  c = pow(m, e, n)
  s = floor_sum(q, q, p)

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

方針

　floor_sum の値が解くカギとなることは間違いないので、まずは floor_sum の持つ性質を精査しました。雑に言えば n 程度の大きさですので、totioent がある程度絞られればラッキーと思いながらいろいろいじっていたら

　floor_sum(p,p,q) = floor_sum(q,q,p) = ((p-1)*(q-1))//2

なる性質があることに気付きました。つまり、phi = 2s。 これで Case Closed です。

ソルバ

solve.py

from Crypto.Util.number import *
c = 23040235907187792043102377766239160347012425454756214402219399982044253963561544138187423569531882081170834886320190973854626011799820277883217582208960795474430615579336090533683566370889382239077437657567815790536809115842475993748108172855688647606634510990327206587307392015543017884876145469179123535144938693302707229724909443912012098405828416163212773471183275687343852756789315215914149905888864296778004572587778916842514807079884644431138433900314631727531570096879428541834626325720522038566946030094711700613155240677360427005636301342509966941323931780006792225168839057660986447452212763627881844882128
n = 25436172154773316497363731760659809627551021985352168624695689317365040018878195925779734249357382145683534839534348832631746578327288150976696513216052612085728199134879493012682967254530827617417753223998955022174337237825391634619718971640535408277659054217709169558518413217237374290054035438476060534235907848570089739603581573457194953083783917042829987113625590656741008590506988903895998008845547262465276679611851110911540261411521221317990139079888782193797945245078986517794660508171428778191152342783279365287710944280356669999624474416422142006473378042779555537142175392801014489187786764971671239717769
s = 12718086077386658248681865880329904813775510992676084312347844658682520009439097962889867124678691072841767419767174416315873289163644075488348256608026306042864099567439746506341483627265413808708876611999477511087168618912695817309859485820267704138829527108854584779259206608618687145027017719238030267117794390566380531016624830798422997060308480467087130633621890831591995264022449058406630323270130520401030807803477672651197312971884784226103671425190328967548002718406368654056897938481966140031709870266384782295285897095028680666943294657806202686252742158733266700286323555374087306844259404255328911060160

phi = 2 * s
d = inverse(0x10001, phi)
print(long_to_bytes(pow(c,d,n)))

フラグ

Neko{fl00r_func710n_1s_n0t_4n_3rr0r_ac1c29e1b5ff4fcaf0e1a0c1b36bb45c}

「floor_sum(p,p,q) = floor_sum(q,q,p) = ((p-1)*(q-1))//2」実に美しい！・・・とうっとりしてその後は 1 問も解けず、Survey を入れ忘れるという失態をやらかしました。（競技後 submit しました。）

3 おわりに

　zer0pts チームの作問はいつも美しいです。
　zer0ptsCTF 2022 とか CakeCTF2022 とか今から楽しみです。
　zer0ptsCTF 2022 とか CakeCTF2022 とか今から楽しみです。
　（大切な事なので２回記しました。）