# Daily AlpacaHack Week 2 (2025-12-08 〜 2025-12-14)

## 12/8: Fully Padded RSA (Crypto, Hard)

数学がさっぱりなので，ひたすらAIに聞いていた．
どうやら拡張ユークリッドの互除法を用いて$u e_1 + v e_2 = 3$ となる整数 $u， v$ を求め，
以下の計算を行うことで $m^3 \pmod n$ を導出できるらしかった．

$$
c' \equiv c_1^u \cdot c_2^v \equiv (m^{e_1})^u \cdot (m^{e_2})^v \equiv m^{u e_1 + v e_2} \equiv m^3 \pmod n
$$

ここからmを求めるために，$m^3 = c' + k \cdot n$ としてkの総当たりを考えたが範囲を絞れず断念．
名前だけ知っていたCoppersmithで解けないかAIに聞いたところ実装してくれた．（実行時間は12分くらい．）
後で見直してみると，今回はパディングによりmとNの上位ビットは共通していたため，mの下位ビットを計算できたということだった．

from Crypto.Util.number import long_to_bytes, bytes_to_long

n = 91102717210596990388603678426683097953697889897819753293818443119019220403217013812232251320814152567699322671590559119510246139859891156830672838769529887961956970370968572962306584295059185945752892892100975462391203805852473243296747559459800718013816237662990504689724747628304890125129146326331097856907
c1 = 84316690833236468829386139306045298111202426584048821548102362931269993141514516100633466389955824290011995159677864206138653174440904170622039293036862729884826231898868928186453091113165643576890891297150845933751243965934735328928976655465009980896153972226679588496970771925581698573227941539852081781874
c2 = 74682069306151159606579889187354529286195652598555930926994495384029865435810129236911316774977007932641783161876484392995815937986886903514990618178943843429073696833993271982336114314882872652681858748846455760309012235191324385691614015531641062111894149446939460102878320469041435024347449132388644171970
e1 = 65517
e2 = 65577

# フラグの最大バイト長と対応するビット数
FLAG_BYTES = 40
FLAG_BITS = FLAG_BYTES * 8 # 320 bits

# --- 2. Common Modulus Attack (m^g の導出) ---

# g = gcd(e1, e2) と xgcd (拡張ユークリッドの互除法) を使用
g, u, v = xgcd(e1, e2)
print(f"[*] GCD of e1 and e2 (g) = {g}")
print(f"[*] Bezout coefficients (u, v) = ({u}, {v})")

# c' = m^g mod n を計算 (c1^u * c2^v mod n)
# Python/SageMathの pow() は負の指数も自動でモジュラ逆数を扱ってくれる
c_prime = (pow(c1, u, n) * pow(c2, v, n)) % n
print(f"[*] Computed c' (m^{g} mod n) = {c_prime}")
c_prime_int = Integer(c_prime)

# --- 3. Coppersmith's Attack (Small Roots) ---

# メッセージmの構造 m = (nの前半) + (flag)
# nのバイト列を取得
n_bytes = n.to_bytes((n.bit_length() + 7) // 8, 'big')

# mの既知部分 (nの最後のFLAG_BYTES分を除いたもの)
# バイト列を整数に戻す
prefix_bytes = n_bytes[:-FLAG_BYTES]
known_prefix = bytes_to_long(prefix_bytes)

# 多項式環を定義 R = Z/nZ [x]
R = Zmod(n)['x']
x = R.gen()

# 多項式 f(x) を定義
# m = known_prefix * 2^FLAG_BITS + x
# m^g - c' = 0 (mod n)
# f = (known_prefix * (2**FLAG_BITS) + x)^g - c_prime
f = (known_prefix * (2**FLAG_BITS) + x)^g - c_prime_int

# Coppersmith's Method (small_roots) で小さな解 x を探す
# beta=1.0: すべての根を探索 (必須ではありませんが確実性を上げる)
# X=2^FLAG_BITS: 根xの最大サイズ
print(f"[*] Starting Coppersmith's small_roots search for X=2^{FLAG_BITS}...")
# Coppersmithの条件: 未知ビット数 < log2(N) / g
# 320 < 1024 / 3 ≈ 341.3 なので成功するはずです。

try:
    # 探索の最大範囲を指定 (X = 2^FLAG_BITS)
    flag_roots = f.small_roots(X=2**FLAG_BITS, beta=1.0, epsilon=0.01)

    if flag_roots:
        # 見つかった解 x がフラグの整数値
        flag_value = flag_roots[0]
        print(f"\n[+] Found flag value (integer): {flag_value}")

        # 整数値をバイト列に戻してデコード
        # flag_bytes = flag_value.to_bytes(FLAG_BYTES, 'big').lstrip(b'\x00')
        flag_bytes = long_to_bytes(int(flag_value)).lstrip(b'\x00')
        flag = flag_bytes.decode()

        print("==============================================")
        print(f"FLAG: {flag}")
        print("==============================================")
    else:
        print("\n[-] Could not find the small root.")

except Exception as e:
    print(f"\n[!] An error occurred during small_roots: {e}")

## 12/9: hit-and-miss (Misc, Easy)

正規表現を入力するとフラグとマッチするかどうかを教えてくれる．
`Alpaca{X\w*}`のような感じで`X`の箇所を調整すれば，一文字ずつフラグを特定できる．
以下，ソルバー.

from pwn import *
import string

context.log_level = 'info'

prefix = "Alpaca{"
suffix = "}"
pad = '\\w*}'

flag = ""

character_set = string.ascii_letters + string.digits + "_"

# io = process(["python", "./app.py"])
io = remote("34.170.146.252", 46849)

while True:
    found_char = False
    for s_char in character_set:
        io.recvuntil(b"regex> ")
        io.sendline((prefix + flag + s_char + pad).encode('ascii'))
        response = io.recvline()
        if response == b"Hit!\n":
            flag += s_char
            io.info(f"Found character: {s_char}")
            io.info(f"Current flag: {prefix}{flag}")
            found_char = True
            break
    else:
        io.success(f"Final flag: {prefix}{flag}{suffix}")
        break

io.close()

## 12/10: Read Assembly (Rev, Medium)

アセンブリのコードが与えられている．
自分なりにpythonに書き起こしてみた．返り値がw0に入る想定だったが，w3に入っていた．
後で直したい．

#! /bin/python

w0 = 0x0
w1 = 0x0
w4 = 0x1
w2 = 0x0

w3 = w2 + w4

while w1 == 0 :
    w0 = w0 + w3
    w1 = w1 + 0x1
    w4 = w2
    w2 = w3
    w3 = w2 + w4

w1 = w1 + 0x1

while w1 != 0x28:
    w4 = w2
    w2 = w3
    w3 = w2 + w4  
    while w1 == 0 :
        w0 = w0 + w3
        w1 = w1 + 0x1
        w4 = w2
        w2 = w3
        w3 = w2 + w4
    w1 = w1 + 0x1

print(w0)
print(w1)
print(w2)
print(w3)
print(w4)

## 12/11: Alpaca Bank (Web, Medium)

transfer部分のコードを見ると次のようになっている．

    const fromBalance = balances.get(fromUser);
    const toBalance = balances.get(toUser);

    /* --- */

    balances.set(fromUser, fromBalance - amount);
    balances.set(toUser, toBalance + amount);

`toBalance`は送金前の値で固定化している．
`Recipient ID`を自分の`Sender ID`とした場合，減った金額は`toBalance + amount`で上書きされ，増やすことができる．
ひたすら手作業で倍々ゲームしてフラグを得た．

## 12/12: Sugoi Flag Checker (Rev, Hard)

gdbで動的解析した．flagの入力は適当な32文字として，ブレークポイントを張って確認すると，strcmp直前に復号化されたフラグがロードされていた．

 ► 0x555555556118 <main+301>    lea    rdx, [rbp - 0xc0]     RDX => 0x7fffffffe7b0 ◂— 'Alpaca{XXX}'
   0x55555555611f <main+308>    lea    rax, [rbp - 0x90]     RAX => 0x7fffffffe7e0 ◂— '12345678901234567890123456789012'
   0x555555556126 <main+315>    mov    rsi, rdx              RSI => 0x7fffffffe7b0 ◂— 'Alpaca{XXX}'
   0x555555556129 <main+318>    mov    rdi, rax              RDI => 0x7fffffffe7e0 ◂— '12345678901234567890123456789012'
   0x55555555612c <main+321>    call   strcmp@plt                  <strcmp@plt>

## 12/13: Safe Prime (Crypto, Easy)

`q = 2 * p + 1` となっていて，二次方程式に持っていける．

import sympy

e = 65537
n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

p = (-1 + sympy.sqrt(1 + 8 * n)) // 4
q = 2 * p + 1
phi = int((p -1) * (q - 1))
d = pow(e, -1, phi)
flag_bytes = pow(c, d, n).to_bytes((n.bit_length() + 7) // 8, 'big')
print(flag_bytes.decode())

## 12/14: 問題名 (Rev, Medium)

powershellが難読化されている．
CyberChefを使って，何とか数字の部分だけ抜き出して文字列に変換してみる．
その際に使ったレシピ

[
  { "op": "Find / Replace",
    "args": [{ "option": "Regex", "string": "\\[char\\](\\d+)" }, "$1", true, true, false, false] },
  { "op": "Find / Replace",
    "args": [{ "option": "Regex", "string": "[a-zA-Z+=&$(){}\\[\\]\\-`.\"]" }, " ", true, false, true, false] },
  { "op": "Find / Replace",
    "args": [{ "option": "Regex", "string": "\\s+" }, " ", true, false, true, false] },
  { "op": "Find / Replace",
    "args": [{ "option": "Extended (\\n, \\t, \\x...)", "string": "" }, "", true, false, true, false] },
  { "op": "Find / Replace",
    "args": [{ "option": "Regex", "string": "^ " }, "", false, false, false, false] },
  { "op": "From Decimal",
    "args": ["Space", true] }
]

base64部分が出て来た際は，次のレシピを使った．

[
  { "op": "From Base64",
    "args": ["A-Za-z0-9+/=", true, false] },
  { "op": "Remove null bytes",
    "args": [] }
]

この操作を数回繰り返すと，フラグが得られた．

## 感想

2週目は冒頭の「Fully Padded RSA」が数論寄りの内容で，AIに頼りっぱなしだった．
ほかの問題についても，solverを書くというよりは手を動かして挙動を確かめるタイプが多く，PowerShell難読化の復号など，実験しながら進める感覚に少し慣れてきた．